Hash n Bake

Рассмотрим один из интересных тасков с TU CTF 2016 под названием Hash n Bake.

Нам дан файл exploit.py exploit.py.zip [715 b] (cкачиваний: 6) .

exploit.py:

#!/usr/bin/env python

def to_bits(length, N):
    return [int(i) for i in bin(N)[2:].zfill(length)]

def from_bits(N):
    return int("".join(str(i) for i in N), 2)

CONST2 = to_bits(65, (2**64) + 0x1fe67c76d13735f9)
CONST = to_bits(64, 0xabaddeadbeef1dea)

def hash_n_bake(mesg):
    mesg += CONST
    shift = 0
    while shift < len(mesg) - 64:
        if mesg[shift]:
            for i in range(65):
                mesg[shift + i] ^= CONST2[i]
        shift += 1
    return mesg[-64:]

def xor(x, y):
    return [g ^ h for (g, h) in zip(x, y)]

PLAIN_1 = "goatscrt"
PLAIN_2 = "tu_ctf??"

def str_to_bits(s):
    return [b for i in s for b in to_bits(8, ord(i))]

def bits_to_hex(b):
    return hex(from_bits(b)).rstrip("L")

if __name__ == "__main__":
    with open("key.txt") as f:
        KEY = to_bits(64, int(f.read().strip("\n"), 16))
    print(PLAIN_1, "=>", bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_1)))))
    print("TUCTF{" + bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_2)))) + "}")

#  Output
#  goatscrt => 0xfaae6f053234c939
#  TUCTF{****REDACTED****}


Вкратце: у нас есть пример ввода и вывода программы (последние комментарии), и нам требуется получить вывод программы при вводе строки "tu_ctf??".

Изучение процессов.

Главная последовательность выполнения действий заключена в следующей строке:
print(PLAIN_1, "=>", bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_1)))))


Давайте последовательно разберем что же происходит со строкой PLAIN_1


1. xor(KEY, str_to_bits(PLAIN_1))

Тут происходит следующее: вначале наша строка преобразовывается в массив битов (длиной 64 бита - по 8 на символ) и XOR-ится с массивом бит ключа (тоже длиной 64 бита). Ну и вспоминая особенности XOR (где зная исходную строку и закодированную можно получить ключ) спокойно можем написать "анти" функцию.

Hash n Bake


2. hash_n_bake()

Уже интереснее - посмотрите на следующее изображение. К нашему массиву байтов прибавляется массив битов строки CONST (длиной 64 бита). И уже далее с получившейся строкой происходит следующее по циклу: проходит с 0 до 64 бита и если находит единицу, то XOR-ит последующие 64 бит со строкой CONST2.

Hash n Bake

Подвох состоит в том, что мы можем написать программу, которая будет делать аналогичные действия в цикле и восстанавливать исходную строку. НО! цикл будет отличаться следующим:

1. Мы будем XOR-ить со строкой CONST2 не когда встретим единицу, а когда XOR последнего бита в CONST и последнего бита в CONST2 будут равны последнему биту в данном массиве (длиной 128 символов).

2. После проверки бита мы удаляем его из исходной строки и из строк CONST и CONST2. То есть после каждого действия длины трех массивов будут уменьшаться на единицу.


Обьясняю что у нас происходит - каждый раз мы делаем проверку, проводился ли XOR строки во время последней проверки. И если XOR проводился, то тогда наш последний бит в строке будет совпадать с OR-ом последних бит в строках CONST и CONST2.

(Если данный момент кому то не понятен, то напишите https://vk.com/drakylar)


Ну и в общем то все! Нам остается написать две обратные функции и получить ключ. А уже после подставить его и получить нужную нам строку. Приступим к написанию кода.

Написание кода

Вначале просто скопируем нужные нам функции и переменные:
def to_bits(length, N):  
    return [int(i) for i in bin(N)[2:].zfill(length)]

def from_bits(N): 
    return int("".join(str(i) for i in N), 2)

CONST2 = to_bits(65, (2**64) + 0x1fe67c76d13735f9)
CONST = to_bits(64, 0xabaddeadbeef1dea)

PLAIN_1 = "goatscrt"

def str_to_bits(s):
    return [b for i in s for b in to_bits(8, ord(i))]

def xor(x, y):
    return [g ^ h for (g, h) in zip(x, y)]


Далее обозначаем нашу строку, с которой мы будем работать и переведем ее в массив байтов (переменная s2):
s1 = 'faae6f053234c939'
s2 =  list(str(bin(int(s1,16))[2:]))
x = 0
while x<len(s2):     #переводим символы
    s2[x]=int(s2[x]) #бит в
    x+=1             #целые числа


Ну и непосредственно написание функции, обратной hash_n_bake().
s3 = [0 for x in range(64)]+s2 #создание доп. ячеек
x = 0
while x<64:
    if s3[-1]^CONST2[-1]==CONST[-1-x]: #проверка на наличие XOR-а по совпадению бит
        e = 1
        while e<=64: #если был XOR, то проXORить последующие 65 символов
            s3[-e] = s3[-e]^CONST2[-e]
            e+=1
        s3 = s3[:len(s3)-1]
        s3[-65]=1
    else:  
        s3 = s3[:len(s3)-1]
        s3[-65]=0
    x+=1
#s3 будет являться массивом битов нужной нам строки.


Последний пункт - у нас есть строка до преобразования
PLAIN_1 = "goatscrt"

и строка после преобразования (s3).

Весь код solve.py:
def to_bits(length, N):
    return [int(i) for i in bin(N)[2:].zfill(length)]

def from_bits(N):
    return int("".join(str(i) for i in N), 2)

CONST2 = to_bits(65, (2**64) + 0x1fe67c76d13735f9)
CONST = to_bits(64, 0xabaddeadbeef1dea)

PLAIN_1 = "goatscrt"

def str_to_bits(s):
    return [b for i in s for b in to_bits(8, ord(i))]

def xor(x, y):
    return [g ^ h for (g, h) in zip(x, y)]

#########################################################################
s1 = 'faae6f053234c939'
s2 =  list(str(bin(int(s1,16))[2:]))
x = 0
while x<len(s2):
    s2[x]=int(s2[x])
    x+=1


s3 = [0 for x in range(64)]+s2
c = CONST2[1:]
x = 0
while x<64:
    if s3[-1]^CONST2[-1]==CONST[-1-x]:
        e = 1
        while e<=64:
            s3[-e] = s3[-e]^CONST2[-e]
            e+=1
        s3[-65]=1
        s3 = s3[:len(s3)-1]
    else:
        s3[-65]=0
        s3 = s3[:len(s3)-1]
    x+=1
PLAIN1 =str_to_bits(PLAIN_1)

print(xor(s3, PLAIN1))



После чего нам выведется ключ в виде массива бит:
[0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1]



И напоследок меняем в исходном скрипте следующие строки:
with open("key.txt") as f:
     KEY = to_bits(64, int(f.read().strip("\n"), 16))

||
\/

KEY = [0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1]


Вывод программы:
goatscrt => 0xfaae6f053234c939
TUCTF{0xf38d506b748fc67}

Видим, что первая строка совпала с ответом. Это означает что ключ и флаг верный!

FLAG: TUCTF{0xf38d506b748fc67}

Во время решения тасков была проблема в неправильной реализации алгоритма ( в связи с чем я застопорился на большой временной промежуток ). И честно говоря свою ошибку я нашел совершенно случайно включив вывод всех переменных на экран:)скачать dle 10.5фильмы бесплатно

  • Автор: drakylar
  • Комментарии: 0
  • Просмотры: 1092

Добавить комментарий

Вы не авторизованы и вам запрещено писать комментарии. Для расширенных возможностей зарегистрируйтесь!