Что такое Rabbit Hole и как я в очередной раз загнал себя в тупик.
Где-то месяц тому назад я начал решать задачу, которая, как мне казалось, была дико сложной и требующей немалых познаний.
Я получил файл под названием huffpuff.elf и некоторую сопутствующую информацию:
###############################################################
We ran the program with flag inside, and it gave us this:
C=34, I=0, L=35, P=32, R=33, S=38, T=1, _=1, a=7, c=30, d=1, e=1, f=39, g=8, h=36, i=5, k=37, m=31, n=6, o=6, p=58, r=10, s=11, t=9, u=59, y=28 0000000011000110101100101000100100000111000110011001001 1110110000111100001100010110111111110101010000110111011 0101110011000100000110010000011101010111000011001111101 0100010000101110100101110011000001010110111100001101110 1101010110010000010111011000001001000000111110111010000 00100110000100011111011001000011001010100101011100110
Flag begins with 'I_Like_'.
Reverse the algorithm, and decrypt the entire flag!
###############################################################
Требовалось расшифровать указанную в бинарном представлении строку. Сказано, что программа была запущена с флагом внутри и в итоге выдала некоторые данные.
Флаг начинается с 'I_Like_' и необходимо изучить алгоритм, а после расшифровать флаг.
Хорошо, первым делом я решил запустить файл и посмотреть что он будет делать:
Надо полагать, внутри программы уже вставлена какая-то другая фраза, которая зашифровалась и вот получена зашифрованная строка и некоторый алфавит к ней.
Теперь можно пойти в IDA и посмотреть что происходит под капотом:
int __fastcall main(int argc, const char **argv, const char **envp)
{
char *v3; // rax
int j; // [rsp+Ch] [rbp-894h]
__int64 i; // [rsp+10h] [rbp-890h]
char *k; // [rsp+10h] [rbp-890h]
_QWORD *huffman_codes; // [rsp+18h] [rbp-888h]
char s[256]; // [rsp+20h] [rbp-880h] BYREF
char v10[104]; // [rsp+820h] [rbp-80h] BYREF
unsigned __int64 v11; // [rsp+888h] [rbp-18h]
v11 = __readfsqword(40u);
memset(s, 0, 2048uLL); // Выделяется память под s
for ( i = *test; *i; ++i ) // test = 'YYYYAAAAHHHHHHOOOONOOOOTTTTTTFFFFLLLLAAAAGGGGGGGISSSSHEEERRREEEEEGUUUUUYYY', именно эта строка будет закодирована
{
v3 = i;
++*&s[8 * *v3];
}
huffman_codes = create_huffman_codes(s); // Здесь присваивается код к каждому символу
for ( j = 0; j <= 255; ++j )
{
if ( huffman_codes[j] )
{
inttobits(*(huffman_codes[j] + 4LL), *huffman_codes[j], v10);
printf("%c=%d, ", j, *(huffman_codes[j] + 4LL));// Здесь будут выведены коды символов в формате символ=код
}
}
puts(&::s);
for ( k = *test; *k; ++k )
{
if ( huffman_codes[*k] )
{
inttobits(*(huffman_codes[*k] + 4LL), *huffman_codes[*k], v10);
printf("%s", v10); // А здесь будет представлено бинарное представление кодов
}
}
puts(&::s);
free_huffman_codes(huffman_codes); // Последовательность кодов обнуляется
return 0;
}Я просто приведу здесь код декомпилированного мейна. Читать это тяжело, а функции, представленные здесь, читать ещё больнее.
Но по названию я понял, что Хаффман здесь играет не последнюю роль и потому пошёл в гугл, искать кто такой вообще Хаффман и почему эта фамилия здесь фигурирует.
Так я познакомился с алгоритмом сжатия данных за авторством американского учёного Дэвида Хаффмана, который был изобретён в 1952 году. Алгоритм Хаффмана считается базой для сжатия различных файлов, он всё ещё используется, хотя и в модифицированном виде.
Пожалуй, я не буду сотый раз пересказывать как работает этот алгоритм и в чём его суть, у меня есть подборка хороших статей на эту тему:
https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0
https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0 - здесь описано в более академичной манере с формулами и т.д.
https://habr.com/ru/articles/144200/
https://habr.com/ru/articles/438512/
https://habr.com/ru/companies/otus/articles/497566/
Я попытался также посмотреть функции которые есть, исходя из названия мне было примерно понятно их предназначение, но код сложен для понимания.
Функция create_huffman_codes() очевидно создаёт коды для символов:
_QWORD *__fastcall create_huffman_codes(char *s)
{
unsigned int i; // [rsp+14h] [rbp-183Ch]
int i1; // [rsp+14h] [rbp-183Ch]
unsigned int range_256; // [rsp+18h] [rbp-1838h]
int v5; // [rsp+1Ch] [rbp-1834h]
int v6; // [rsp+20h] [rbp-1830h]
unsigned int v7; // [rsp+24h] [rbp-182Ch]
int h_remove; // [rsp+28h] [rbp-1828h]
int h_removea; // [rsp+28h] [rbp-1828h]
int v10; // [rsp+2Ch] [rbp-1824h]
int *heap_dest; // [rsp+30h] [rbp-1820h]
_QWORD *output; // [rsp+38h] [rbp-1818h]
int v13[512]; // [rsp+40h] [rbp-1810h]
__int64 dest[256]; // [rsp+840h] [rbp-1010h] BYREF
__int64 v15; // [rsp+1040h] [rbp-810h] BYREF
range_256 = 256;
memcpy(dest, s, sizeof(dest));
memset(&v15, 0, 2048uLL);
heap_dest = heap_create(512, dest);
if ( !heap_dest )
return 0LL;
for ( i = 0; i <= 255; ++i )
{
if ( dest[i] > 0 )
heap_add(heap_dest, i);
}
while ( heap_dest[2] > 1 )
{
h_remove = heap_remove(heap_dest);
v10 = heap_remove(heap_dest);
dest[range_256] = dest[v10] + dest[h_remove];
heap_add(heap_dest, range_256);
v13[h_remove] = range_256;
v13[v10] = -range_256++;
}
h_removea = heap_remove(heap_dest);
v13[h_removea] = h_removea;
heap_destroy(heap_dest);
output = malloc(2048uLL);
for ( i1 = 0; i1 <= 255; ++i1 )
{
v5 = 0;
v6 = 0;
if ( dest[i1] )
{
v7 = i1;
while ( abs32(v13[v7]) != v7 )
{
v5 |= (v13[v7] >= 0) << v6;
v7 = abs32(v13[v7]);
++v6;
}
output[i1] = malloc(8uLL);
*output[i1] = v6;
*(output[i1] + 4LL) = v5;
}
else
{
output[i1] = 0LL;
}
}
return output;
}Функция inttobits() преобразует десятичные числа в двоичные:
unsigned __int64 __fastcall inttobits(int a1, int a2, __int64 a3)
{
unsigned __int64 result; // rax
int v4; // [rsp+8h] [rbp-8h]
v4 = a2;
result = a2 + a3;
*result = 0;
while ( v4 > 0 )
{
result = (a1 % 2 + 48);
*(v4 - 1LL + a3) = a1 % 2 + 48;
a1 >>= 1;
--v4;
}
return result;
}Функция heap_remove() что-то очищает:
int __fastcall heap_remove(int *heap_dest)
{
if ( heap_dest[2] <= 0 )
return -1;
return *(*heap_dest + 4LL * --heap_dest[2]);
}Функция heap_add() выполняет добавление каких-то значений в heap_dest() и после добавления сортирует массив функцией heap_sort():
void __fastcall heap_add(int *heap_dest, unsigned int *i)
{
if ( heap_dest[2] + 1 > heap_dest[3] )
{
*heap_dest = realloc(*heap_dest, heap_dest[3] + heap_dest[4]);
heap_dest[3] += heap_dest[4];
}
*(4LL * heap_dest[2]++ + *heap_dest) = i; // похоже, что здесь перемешиваются индексы и таким образом присваиваются коды для символов
heap_sort(heap_dest); // сортируем массив по возрастанию
}В общем, таких функций там довольно много, я оставлял какие-то комментарии, пытался разобраться, но надолго меня не хватило.
Я предположил, что скорее всего программа сжимает строку, применяя тот самый алгоритм Хаффмана и в итоге мы получаем сжатую строку + символы с их частотами. Я даже нашёл какая конкретно фраза была зашифрована, она лежала в одной из переменных, но не придал почему-то этому должного значения, решив, что она бесполезна, пока у меня нет написанного дешифратора.
Собственно говоря, здесь я и угодил в кроличью нору (Rabbit Hole), решив не искать лёгких путей. По мере того, как я пытался расшифровать эту строку, проводя вечера за написанием кода по 6-7 часов к ряду, я падал в эту нору всё глубже и глубже, пока совсем не отчаялся.
Начнём с того, что программно реализовать алгоритм Хаффмана, хоть он и считается довольно простым, для программиста-самоучки с маленьким опытом, оказалось не самой простой задачей.
В целом, я писал разные варианты, финальным был этот:
import queue
encoded_string = '0001000100010001110110110110000000000000000000000000100100100100011011100100100100001000100010001000100010011101110111011110101010101010101101101101101111111111111111111110110101011101110111011000001001001001100011000110001001001001001001001011100110011001100110011000100010001'
huffman_codes = [
(6, 'A'), (2, 'E'), (7, 'F'), (7, 'G'), (0, 'H'), (26, 'I'), (10, 'L'), (27, 'N'), (4, 'O'), (12, 'R'), (11, 'S'), (2, 'T'), (3, 'U'), (1, 'Y')]
symbols = list()
binary_tree = list()
q = queue.PriorityQueue()
def is_multiple_by_two():
if len(huffman_codes) % 2 == 0:
return True
else:
return False
def create_queue(huffman_codes, q):
for symbol in huffman_codes:
q.put(symbol)
def clear_queue(q):
while q.qsize() != 0:
q.get()
def delete_descendants(symbol_a, symbol_b):
huffman_codes.remove(symbol_a)
huffman_codes.remove(symbol_b)
def create_last_node(huffman_codes):
a = huffman_codes[1]
b = huffman_codes[2]
huffman_codes.append((a[0]+b[0],a[1]+b[1]))
binary_tree.append((0, a[1]))
binary_tree.append((1, b[1]))
delete_descendants(a, b)
def create_tree(queue):
while True:
a = queue.get()
b = queue.get()
queue.task_done()
queue.task_done()
binary_tree.append((0, a[1]))
binary_tree.append((1, b[1]))
huffman_codes.append((a[0]+b[0],a[1]+b[1]))
delete_descendants(a, b)
if queue.qsize() == 1 or queue.qsize() == 0:
break
def get_symbols(huffman_codes):
for i in huffman_codes:
symbols.append(['',i[1]])
def create_paths(binary_tree, symbols):
for i in symbols:
for j in binary_tree:
if j[1].find(i[1]) != -1:
i[0] += str(j[0])
def reverse_path(symbols):
for i in symbols:
i[0] = i[0][::-1]
def decode_string(encoded_string, symbols):
counter = 0
result = str()
while counter != len(encoded_string):
for i in symbols:
if i[0] == encoded_string[counter:counter+len(i[0])]:
result += i[1]
counter += len(i[0])
print(result)
get_symbols(huffman_codes)
create_queue(huffman_codes, q)
if is_multiple_by_two == True:
while len(huffman_codes) > 2:
create_tree(q)
clear_queue(q)
create_queue(huffman_codes, q)
if len(huffman_codes) > 1:
binary_tree.append((0, huffman_codes[0][1]))
binary_tree.append((1, huffman_codes[1][1]))
else:
while len(huffman_codes) > 3:
create_tree(q)
clear_queue(q)
create_queue(huffman_codes, q)
if len(huffman_codes) > 1:
binary_tree.append((0, huffman_codes[0][1]))
binary_tree.append((1, huffman_codes[1][1]))
create_paths(binary_tree, symbols)
reverse_path(symbols)
print(binary_tree)
print(symbols)
decode_string(encoded_string, symbols)Но он сырой, не совсем работает как надо (я полагаю), я принципиально не хотел копировать какой-то код из гугла, мне хотелось написать всё самому. По идее всё это реализуется с использованием своих классов, методов для этих классов, но я ограничился лишь использованием очереди с приоритетами для построения бинарного дерева и функциями - здесь нет каких-то продвинутых концепций, про архитектуру я вообще не думал, мне хотелось чтобы это хотя бы работало. Теперь вообще нет надобности это дорабатывать, потому что, как оказалось, от Хаффмана в коде задачи одно только название.
- Строит дерево Хаффмана, формируя ветки слиянием листов и продвигаясь к корню (корень дерева не формируется, потому что здесь он мне без надобности).
- Очередь очищается после каждой итерации со слиянием элементов, происходит обновление приоритетов для объединённых элементов.
- На каждом этапе элементам присваивается 0, либо 1.
- Программа проходится по дереву, выстраивая маршрут к каждому символу и записывая этот маршрут в виде двоичного числа.
- На основе этих чисел происходит расшифровка строки.
Вроде бы всё работает в соответствии с алгоритмом, ну или по-крайней мере похоже на то.
И тем не менее, код выдавал мне бредик:
В целом, здесь правильно расшифровывались какие-то символы, вот для сравнения как выглядела исходная строка:
"YYYYAAAAHHHHHHOOOONOOOOTTTTTTFFFFLLLLAAAAGGGGGGGISSSSHEEERRREEEEEGUUUUUYYY"
Где я свернул не туда? Я думал, что наверное неправильно реализовал алгоритм или ещё что-то в таком духе.
Я начал попытки заполнить пробелы в понимании этого алгоритма, читал кучу статей, смотрел много кода. Но даже чужие реализации выдавали бредик, пытаясь расшифровать эту строку!
И здесь я понял, что проблема не во мне и не в моём коде. Задача просто не использует алгоритм Хаффмана, она делает вид, что использует, но не использует. Во всяком случае, мне так кажется. От алгоритма здесь возможно есть только частотность символов и внешнее сходство. Мне дали подсказку в какую сторону копать и я понял, что всё это время летал по кроличьей норе, в то время, как ответы лежали на поверхности. Я собственноручно загнал себя в тупик и потратил много времени в никуда (в плане решения задачи, конечно, в остальном такая практика была мне очень полезна, я узнал много нового).
Итак, как это решается. Можно глянуть на строку в исходном и зашифрованном виде и подметить некоторые вещи:
"0001000100010001110110110110000000000000000000000000100100100100011011100100100100001000100010001000100010011101110111011110101010101010101101101101101111111111111111111110110101011101110111011000001001001001100011000110001001001001001001001011100110011001100110011000100010001"
"YYYYAAAAHHHHHHOOOONOOOOTTTTTTFFFFLLLLAAAAGGGGGGGISSSSHEEERRREEEEEGUUUUUYYY"
Например, в начале строки идут "YYYY", а в зашифрованной строке начало это 0001 0001 0001 0001. 4 одинаковых сегмента. Далее идут "AAAA", а в двоичном коде 110 110 110 110. Снова совпадение. Это даёт основания полагать, что код для "Y" = 0001, а код для "A" = 110. В итоге есть предположение, что двоичные коды для символов это вовсе не маршруты. Хотя бы потому, что чем меньше десятичный код числа, тем реже оно встречается в сжатой строке, а значит и её двоичный код, её маршрут, будет очень длинным, а самые часто встречающиеся символы, наоборот, будут иметь самые короткие коды, в этом и есть суть алгоритма Хаффмана, за счёт этого итоговое количество битов меньше исходного.
Взглянем ещё раз на коды, которые программа присвоила символам:
A=6, E=2, F=7, G=7, H=0, I=26, L=10, N=27, O=4, R=12, S=11, T=2, U=3, Y=1
0001 в десятичной системе это 1, а 110 в десятичной системе это 6, собственно коды это десятичное представление двоичных кодов символов.
Теперь надо перевести для удобства все эти коды в двоичные числа:
code = [['A',6], ['E',2], ['F',7], ['G',7], ['H',0], ['I',26], ['L',10], ['N',27], ['O',4], ['R',12], ['S',11], ['T',2], ['U',3], ['Y',1]]
def get_bin(code):
for i in code:
i[1] = str(bin(i[1]))
i[1] = i[1][2:]
get_bin(code)
print(code)
Теперь по этой схеме можно попытаться расшифровать строку.
0001 Y 0001 Y 0001 Y 0001 Y 110 A 110 A 110 A 110 A
Далее идёт много нулей, как раз символ 'H' имеет код 0, но вот в чём проблема - как понять сколько именно нулей принадлежат 'H'? Ведь 0 в двоичной системе можно представить как 00 или 000 или 0000 или 00000 или 000000 и т.д.
Придётся тыкать ручками и руководствоваться логикой. Давайте подумаем! После 6 символов 'H' идёт 'O', которая обозначена как 100, это значит, что там где мы встретим единицу - начинается другой символ. Итого на 6 'H' выделено 24 бита. Ну а значит мы просто делим 24 на 6 и получаем по 4 бита на символ, значит 'H' = 0000. Ну и так далее, думаю суть ясна.
И вот почему здесь очень сложно автоматизировать декодирование - вы не сможете выловить какой-то чёткий паттерн, вам придётся экспериментировать вручную с такими вот нулями.
При расшифровке флага, например, возникает такая же проблема - там есть несколько символов, у которых десятичный код это 1. А 1 можно представить как 01 или 001 или 00001 или 000001 и так далее, значит один символ будет обозначаться как 01, какой-то другой, обозначенный единицей, будет обозначаться как 001 ну и так далее. Выяснять это уже придётся методом проб и ошибок, что я и сделал. Через 20 минут кропотливого подбора символов, я получил искомую фразу:
Что можно сказать в конце? Я извлёк ценный урок, в процессе мучений изучил алгоритм и даже написал какой-то код для него, по-моему неплохой итог.