Hash n Bake
Рассмотрим один из интересных тасков с TU CTF 2016 под названием Hash n Bake.
Нам дан файл exploit.py
.
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 (где зная исходную строку и закодированную можно получить ключ) спокойно можем написать "анти" функцию.
2. hash_n_bake()
Уже интереснее - посмотрите на следующее изображение. К нашему массиву байтов прибавляется массив битов строки CONST (длиной 64 бита). И уже далее с получившейся строкой происходит следующее по циклу: проходит с 0 до 64 бита и если находит единицу, то XOR-ит последующие 64 бит со строкой CONST2.
Подвох состоит в том, что мы можем написать программу, которая будет делать аналогичные действия в цикле и восстанавливать исходную строку. НО! цикл будет отличаться следующим:
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}
Во время решения тасков была проблема в неправильной реализации алгоритма ( в связи с чем я застопорился на большой временной промежуток ). И честно говоря свою ошибку я нашел совершенно случайно включив вывод всех переменных на экран:)
- Автор: drakylar
- Комментарии: 0
- Просмотры: 3993