Решение ksydfius - Ksydfius-128

Сложность: 1 - Very easy, for newbies
Платформа: Windows
Язык: NET
Дано: Ksydfius-128

Я разработал алгоритм хэширования Ksydfius-128
Взломай его.
Подробности в ReadMe.txt :)

Решение (автор phueghy)
опубликовано 17.10.2012

Читаем README.txt, прилагаемый к задаче.



Как указано в сопроводительном файле README, Ksydfius-128 написан на .NET и легко декомпилируется с помощью Reflector’а (в отличие от автора решения я использую SAE. Пример работы с SimpleAssemblyExplorer можно посмотреть здесь).

Чтобы лучше понять, как работает алгоритм, я скопировал код функций private void button1_Click и private long hehe в Microsoft Visual Studio (при желании можно вообще никуда не копировать, а обойтись только статическим анализом кода). Таким образом, я смог наблюдать за вычислениями в режиме реального времени (к счастью, Visual Studio способен отображать все числа в шестнадцатеричном виде – это очень удобно в данном случае).

Алгоритм стартует с массивом, содержащим четыре константы, и парсит входную строку по кусочкам из 4-х символов. Начальные значения констант:

array = [ 0x12345678, 0x98BADCFE, 0xF00DBEEF, 0xC0FFEEBF]

Функция сжатия алгоритма (процесс хэширования похож на процесс сжатие тем, что на входе берем данные длины N и преобразуем в фиксированный по размеру дайджест, в нашем случае итоговый хэш должен быть длиной в 128 бит)

  • Каждый 4-хсимвольный кусочек преобразуется в число num с помощью функции hehe и это число добавляется к одной из констант в массиве array в соответствии с текущей позицией парсера: array[i % 16 / 4] += num, где i = 0, 4, 8, 12, 16, 20.. (счетчик цикла, анализирующего входную строку). Число, возвращаемое функцией hehe, состоит из ASCII-кодов символов, входящих в один 4-хсимвольный кусочек. Например, hehe("test") вернет 0x74657374, а hehe("11") – 0x31310000
  • Далее следует цикл, где текущий элемент массива, а также следующие за ним элементы массива умножаются (по модулю 232) на значение длины входной строки:
for (int j = i % 16 / 4; j < 4; j++)
    array[j] = (array[j]  * Длина_входной_строки) & 0xFFFFFFFF


Этот процесс повторяется, пока вся входная строка не будет разобрана. В результате, четыре элемента массива array образуют хэш (каждый элемент массива – это 32-битное число, а весь массив – 128-битное число). Теперь значения массива преобразуем в 16-тиричную строку и объединяем. Если хэш равен "ffffffffffffffffffffffffffffffff" (т.е. все элементы массива равны 0xFFFFFFFF), то получим goodboy-сообщение и решим crackme.

Возьмем карандаш и бумагу и запишем, какие вычисления происходят в алгоритме в первых четырех итерациях (все четыре шага цикла отработают в том случае, если длина входной строки кратно 16). В таблице: L = длина текста; A,B,C,D – известные начальные значения массива array; Xi, Xi+1, Xi+2, Xi+3 - входные значения (числа, возвращаемые функцией hehe от каждого 4-хсимвольного кусочка входной строки).



Посмотрите на таблицу. Беда в том, что это совсем не хэш. На коротких данных он полностью обратим. Математика простая (вычисления по модулю 232), достаточно калькулятора:

X0 = A’ / L - A
X1= B’ / L – B*L
X2 = C’ / L – C*L2
X3 = D’ / L - D*L3

Останется только X0, X1, X2, X3 преобразовать из чисел в ASCII-символы (конечно, символы получатся не совсем «красивые», так называемые непечатаемые. Например, ASCII-символ с кодом 0xFE на клавиатуре тяжелее найти, но схема Copy-Paste в этом случае выручит).

Итак, посчитаем. Хэш нам известен - "ffffffffffffffffffffffffffffffff". Пусть нам необходимо получить строку с L = 15 (0x0F). В этом случае деление произойдет без остатка 0xFFFFFFFF / 0x0F = 0x11111111 (если бы мы взяли строку с L = 16 (0x10), то мы никогда не получим нужный хэш 0xFFFFFFFF / 0x10 = 0x0FFFFFFF => 0x0FFFFFFF * 0x10 = 0xFFFFFFF0).

X0 = (0xFFFFFFFF / 0x0F - 0x12345678) & 0xFFFFFFFF = 0xFEDCBA99
X1 = (0xFFFFFFFF / 0x0F - 0x98BADCFE *0x0F) & 0xFFFFFFFF = 0x1E1E1E2F
X2 = (0xFFFFFFFF / 0x0F - 0xF00DBEEF *0x0F2) & 0xFFFFFFFF = 0x14FC4102
X3 = (0xFFFFFFFF / 0x0F - 0xC0FFEEBF *0x0F3) & 0xFFFFFFFF = 0xA2F48900

Значения Xi преобразуем в символы (числа рассматриваются как BIG-ENDIAN).
Найденная строка (длина - 15) включает символы со следующими кодами:
"\xFE\xDC\xBA\x99\x1e\x1e\x1e\x2f\x14\xfc\x41\x02\xA2\xF4\x89"

Вот тут возникает вопрос с кодировками. Значения я искал с помощью скрипта на Python. Если скрипт выполнить в консоли Windows, то найденная строка отобразится в кодировке cp866. Если выполнить скрипт в GUI Python, то символы будут в кодировке windows-1251. А сам crackme ожидает ввод пользователя в кодировке unicode. Решение, которое я нашел – это из скрипта создать текстовой файл в кодировке unicode и записать туда найденную строку. Затем, открывая файл обычным «Блокнотом», копируем строку (Copy-Paste) в поле «Text» crackme.

Код на Python:

# -*- coding: cp1251 -*-
import struct
 
def reverse(L, A, B, C, D):
    X0 = (0xFFFFFFFF / L - A) & 0xFFFFFFFF
    X1 = (0xFFFFFFFF / L - B * L) & 0xFFFFFFFF
    X2 = (0xFFFFFFFF / L - C * L**2) & 0xFFFFFFFF
    X3 = (0xFFFFFFFF / L - D * L**3) & 0xFFFFFFFF
    return X0,X1,X2,X3
 
# Константы
A = 0x12345678
B = 0x98BADCFE
C = 0xF00DBEEF
D = 0xC0FFEEBF
# Длина строки - 15
L = 15
# Считаем значения для хэша "ffffffffffffffffffffffffffffffff"
X0,X1,X2,X3 = reverse(L,A,B,C,D)
# Значения в строку
check = struct.pack(">L", X0)+struct.pack(">L", X1)+\
        struct.pack(">L", X2)+struct.pack(">L", X3)
print ("Key (win-1251)= "+check)
# Строку пишем в текстовой файл в кодировке unicode
# Файл создаем в той папке, где выполняется скрипт
header = "\xFF\xFE"
f = open("sol_unicode.txt","wb")
f.write(header)
for i in range(L):
    f.write(check[i])
    f.write("\x00")
f.close()
print ("Write the solution in file - OK!")

image00.jpg
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License