Решение gim913 - KeygenMe#01

Сложность: 3 - Getting harder
Платформа: Unspecified/other
Язык: C/C++
Дано: KeygenMe#01

Надеюсь, интересный неконсольный keygenme.
Полностью написанный на C++.
Отсутствует обфускация и антиотладка.

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

От переводчика. Решение от ReWolf просто замечательное. Перевожу его как есть. Свои дополнения и объяснения я буду выделять курсивом или отдельным блоком текста. И, конечно, весь код написан на Python'е.

В связи с постоянной нехваткой времени и очень длинным списком собственных дел я не часто решаю crackme, но иногда это хороший повод проверить себя и свои навыки. Я полистал список нерешенных crackme на crackmes.de и обнаружил совершенно новую задачку от gim913, которая висела нерешенной в течение почти 2-х месяцев (да, я знаю, времени прошло не так много:) ). Зная репутацию автора, я решил попробовать свои силы, вероятно, внутри будет что-то интересное. Итак, начнем.

Статический анализ

Crackme написан на чистом C++ без обфускации и антиотладки. Загрузив его в старую версию IDA, дизассемблер выдал мало информации. Т.к. задачка была написана на Visual Studio 2010, мне пришлось обновить в IDA базу сигнатур. Сканирование в PEiD показало, что crackme использует алгоритм MD5 (эта информация нам понадобиться чуть позже). Обнаружить функцию, отвечающую за проверку имя-ключ, довольно легко, достаточно найти ссылки на строки:

.rdata:0041C560 db 'C O N G R A T U L A T I O N S !',0
.rdata:0041C580 db 'Wrong username!',0
.rdata:0041C590 db 'Wrong password!',0

Ссылки на эти строки находятся в функции, стартующая с адреса 0040188E. Эта функция играет главную роль в crackme, поэтому дадим ей имя serial_check() и далее будем обращаться к ней по этому имени. Функция serial_check() немаленькая (почти 3Кб кода) и вызывает множество неопознанных функций. Анализ этих функций вручную может занять приличное время, но есть более простой способ. Поискав среди строк-констант, встроенных в исполняемый файл, и отбросив часто встречаемые строки, которые присутствуют в каждом exe-файле, я нашел нечто подозрительное:

.rdata:004191AC db '3.90625E-3',0
.rdata:004191B8 db '1.5625E-2',0
.rdata:004191C4 db '8.0E-3',0
.rdata:004191CC db '0.85',0
.rdata:004191D4 db '0.5',0
.rdata:004191D8 db '10',0

Погуглив первые два значения, я получил множество результатов, но большинство из них не имеют никакого смысла. То, что искал, я нашел в результатах поиска в конце первой страницы браузера - это была часть исходного кода библиотеки MAPM:

m_apm_set_string(MM_5x_125R, "8.0E-3");
m_apm_set_string(MM_5x_64R, "1.5625E-2");
m_apm_set_string(MM_5x_256R, "3.90625E-3");

MAPM, Портативная Произвольной Точности Математическая Библиотека на С (Portable Arbitrary Precision Math Library in C) http://www.tc.umn.edu/~ringx004/mapm-main.html – старенькая (и мне неизвестная), математическая библиотека для работы с большими целыми числами, а также с большими числами с плавающей запятой. Мне удалось собрать MAPM с Visual Studio 2010 (в исходных кодах библиотеки есть пакетный скрипт для VC 6.0 – MKALLMSC.BAT, и он все еще работает). Сигнатуры для IDA на основании библиотеки mapm.lib решили проблему частично, IDA нашла 23 из ~ 40 функций. Ненайденные функции легко распознаются вручную, сопоставляя исходные коды с общей структурой каждой неопознанной функции и, ориентируясь на ссылки уже обнаруженных функций и констант.


Кроме низкоуровнего API для численных вычислений, в библиотеке MAPM реализован класс-оболочка (wrapper), отвечающий за работу операторов, поэтому его можно использовать практически прозрачно. Упомянутый класс-обертка не входит в саму библиотеку, он часть заголовочного файла (M_APM.h – class MAPM), поэтому мне пришлось также, вручную определять функции из этого класса. После этих телодвижений serial_check() стала выглядеть более дружелюбной, но оставалось еще много неопознанных функций. А все благодаря плотному использованию STL. Как я понял, crackme использует поверх MAPM следующие шаблоны С++: std::string, std::vector и std::list. Я решил не заморачиваться с точным определением всех этих функций, потому что как выяснилось, нет необходимости знать их все.
Это почти всё, что связано со статическим анализом.

Динамический анализ

Чтобы упростить отладку, я выключил ASLR в исполняемом файле.


Прежде всего, я проверил, какие данные хэширует MD5. Установил точку останова на функцию сжатия MD5 и выяснил, что хэш рассчитывается, исходя из имени пользователя – это будет первым шагом в нашем кейгене.

usermd5 = MD5(username);

.text:00401B23 push [ebp+len_name]
.text:00401B26 mov eax, [esp+18Ch+obj_hash]
.text:00401B2D push [ebp+name]
.text:00401B30 lea ecx, [esp+190h+obj_hash]
.text:00401B37 call dword ptr [eax+0Ch] ; MD5_Update
Да, кстати, перед хэшированием стоит проверка на длину имени. Имя должно быть не менее 4-х символов.

Вторая догадка (мой динамический анализ больше всего был похож на игру в "угадайку") была связана с библиотекой MAPM, она использует m_apm_set_long() для инициализации MAPM-объекта из целого числа:

00407E70 void m_apm_set_long(M_APM, long);

Я поставил точку останова на эту функцию и стал ждать. Как оказалось, это было хорошее предположение, вот какое значение я отловил на входе в функцию:
0x67, 0x69, 0x6D, 0x39, 0x31, 0x33, 0x21, 0x95 = "gim913!\x95"
Если по шагам отследить, что делает m_apm_set_long, то функция просто берет входной параметр и преобразует его в длинное целое число.

def createValue(data, dataSize):
    v = 0
    for i in range(dataSize):
        v = v*256 + ord(data[i])
    return v


Т.е. строка «gim913!\x95» станет числом 0x67696D3931332195 (в десятичном виде 7451607150867194261). А это, между прочим, простое число.

p = createValue("gim913!\x95", len("gim913!\x95"))



Следим дальше за программой. Точка останова на m_apm_set_long() сработала еще несколько раз. Анализ показал, что хэш-значение MD5 от имени пользователя используется для инициализации 4-х значений (коэффициентов):

a = createValue(usermd5, 5);
b = createValue(usermd5 + 5, 5);
c = createValue(usermd5 + 10, 5);
d = createValue(usermd5 + 15, 1);

Так, теперь я могу вернуться к функции serial_check() (на адрес 00401CB6), потому что большинство расчетов производится там, задействуя различные библиотечные функции MAPM. Обработав имя пользователя, crackme "выравнивает" коэффициент b:

b = (512 * b) + d

# число 512
00401CCE call _m_apm_set_long
# b = b*512
00401CE2 call m_apm_mul
# b = b+d
00401CF4 call m_apm_add

Затем вычисляем:

D = b*b - 4*a*c

# число 4
00401D6D call _m_apm_set_long
# 4*a
00401D7E call m_apm_mul
# 4*a*c
00401D8C call m_apm_mul
# b*b
00401D9C call m_apm_mul
# b*b - 4*a*c
00401DA7 call m_apm_sub
#D == 0
00401E60 call _m_apm_compare

Формула D – это не что иное, как формула дискриминанта квадратного уравнения и в этом случае он используется для проверки: существует ли корень у квадратного уравнения (т.е. crackme проверяет, существует ли ключ для данного имени пользователя). Если D > 0, то квадратное уравнение имеет два корня и тогда crackme выполняет дополнительные расчеты:

D = D % p
# D(p-1)/2 % p
A = powmod(D, (p - 1)/2, p)
Проверка: А == 1 ?

# D = D % p
00401E97 call div
# A = powmod(D, (p - 1)/2, p)
00401F12 call get_Legendre_symbol

Формула А – это формула Эйлера для вычисления символа Лежандра, который используется для проверки, является ли значение квадратичным вычетом по модулю простого числа (символ Лежандра должен быть равен 1 - т.е. D не делится на p и существует такое целое x, что x2 = D (mod p)). Если это не так, то программа выдаст badboy-сообщение "Wrong username" (Неверное имя пользователя!). Многие, возможно, уже догадались, какая здесь используется защита, но я процитирую слова Стива Джобса:
"Нельзя соединить точки своей судьбы, если смотришь вперёд; соединить их можно только ретроспективно. Так что надо верить, что эти точки как-нибудь, да соединятся в будущем".



Так что, я пока не соединял точки, потому что мои знания о квадратном уравнении буквально равны нулю. Ладно, продолжим анализ serial_check(). Следующая часть функции serial_check(), начиная с адреса 00401F66, представляет собой кучу неопознанных дизассемблером процедур, которые собраны в некий цикл. Да, ситуация печальная, но у меня мелькнуло смелое предположение, и я решил установить точку останова на адрес в памяти, где хранился наш ключ. Как только сработала точка останова, я потрассировал код и обнаружил, что каждый символ ключа преобразуется в целочисленное значение, но не все символы, а только цифры и прописные буквы (по крайней мере, A-F точно, потому что мой пробный ключ состоял из шестнадцатеричных чисел). Затем каждое значение (код символа) обрабатывается по алгоритму:
# 00404E12
def converter(data, dataSize):     
    v = 0
    for i in range(dataSize):
        v = v*36 + ord(data[i])
    return v


Алгоритм определяется довольно легко, это получение числа из 36-тиричной системы счисления. Этот конвертер вызывается 3 раза, при этом каждый раз 5 символов ключа преобразуется в целое значение. Поэтому правильный ключ должен быть длиной 15 символов, состоящий из символов алфавита:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Таким образом, получаем три переменных из ключа:

sn1 = converter(key, 5);
sn2 = converter(key+5, 5);
sn3 = converter(key+10, 5);

Далее sn1, sn2 и sn3 проверяются по алгоритму:

def parity(v):
    v ^= v >> 16
    v ^= v >> 8
    v ^= v >> 4
    v &= 0xf
    return ((0x6996 >> v) & 1)


Этот алгоритм проверяет (за разъяснениями идем сюда http://bits.stephan-brumme.com/parity.html), содержит ли число v четное или нечетное количество единиц (т.е. бит со значением 1). sn1, sn2 и sn3 должны быть с четным количеством единиц, иначе получим badboy-сообщение "Wrong password!"

После проверки, sn1, sn2 и sn3 сдвигаем на один бит вправо:

# 0040208F- 00402091
sn1 >>= 1
sn1 &= 0xFFFFFF
sn2 >>= 1
sn2 &= 0xFFFFFF
sn3 >>= 1
sn3 &= 0xFFFFFF


Благодаря этой операции, контроль четности не влияет на значения, которые будут использоваться в уравнении. И наконец, значения sn1, sn2 и sn3 объединяются в одно значение:

SN = (sn1*0x1000000 + sn2)*0x1000000 + sn3

Как я это узнал? Да, всё то же, пригодилась точка останова, установленная на m_apm_set_long(). И вот последний этап serial_check() – расчет по формуле и сравнение результата с 0:

(a*SN*SN + b*SN + c) % p == 0

Решение квадратного уравнения

Само по себе решение квадратного уравнения несложное, но из-за отсутствия надлежащей квалификации я помучился над ним кое-какое время. Я попросил помочь моего старого друга из http://gdtr.wordpress.com/, и он подсказал мне, где можно почитать информацию по теме. Сначала я попытался решить уравнение на WolframAlfa (математический онлайн-сервис), чтобы убедиться, все ли я правильно делаю. Я получил коэффициенты для имени пользователя "ReWolf", записал уравнение и получил решение:

http://www.wolframalpha.com/input/?i=1066057551438*x%5E2+%2B+108267059694607*x+%2B+613597096232+%3D+0+%28mod+7451607150867194261%29

x1 = 143 821 202 166 254 065
x2 = 4 585 687 363 368 859 247

Взял первый корень (143821202166254065); разобрал его на sn1, sn2, sn3; преобразовал в base36-ключ (000SCJ37Z95RZZ6) и crackme показал мне goodboy-сообщение "C O N G R A T U L A T I O N S !" Теперь, надо понять, как решить уравнение вручную? Процесс решения похож на стандартное решение квадратного уравнения, вот только все операции должны учитывать модульную арифметику.

$x_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a} \pmod p$
$x_2 = \frac{-b + \sqrt{b^2 - 4ac}}{2a} \pmod p$

Есть две проблемы в стандартных формулах, которые надо решить в кейгене:
- вычисление обратного по модулю значения
- вычисление квадратного корня по модулю

Первая проблема решается просто, используя расширенный алгоритм Евклида, вторая - сложнее, но для нее есть несколько алгоритмов, которые нам помогут:

- алгоритм Шенкса или Шенкса-Тонелли алгоритм
- Cipolla алгоритм
- Pocklington алгоритм

Я выбрал алгоритм Шенкса, по крайней мере, самое популярное решение с точки зрения поиска Google. В кейгене я использовал реализацию алгоритма Шенкса от Eli Bendersky.

На посошок

Вот несколько интересных деталей, о которых я узнал от автора crackme, после того как я послал ему кейген:
- MD5 взята из библиотеки Crypto++
- Crackme действительно использует STL: <map>, <list>, <string>, <vector>, <algorithm>
- Crackme использует FC++: Функциональное программирование на C++, чтобы "скрыть" код

Те самые константы, которые я использовал для поиска MAPM библиотеки остались в коде намеренно в качестве подсказки для реверсера.

Автор любезно прислать мне исходный код крякми, вот мои любимые фрагменты:

- Создание MAPM-объекта из std::string

std::string gim913 = "\x67\x69\x6d\x39\x31\x33\x21\x95";
MAPM prime = foldl([](MAPM left, int b) { return 256*left + b; }, mapm_zero, 
                           List<e_ubyte>(gim913.begin(), gim913.end()));


- Парсинг MD5-хэша:
auto res = splitAt(5, chunks_mdu);
coefficients.push_back( foldl([](MAPM left, int b) { return 256*left + b; }, 
                                        mapm_zero, res.first) );


Кейген

Внешние модули для кейгена:
1. euclidean.py - расширенный алгоритм Евклида
2. modular_sqrt.py - реализация алгоритма Шенкса

import hashlib
import modular_sqrt
import euclidean
 
def base36encode(number, pad = 0):
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')
    if number < 0:
        raise ValueError('number must be positive')
 
    alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 
    base36 = ''
    while number:
        number, i = divmod(number, 36)
        base36 = alphabet[i] + base36
 
    if pad > 0:
        while len(base36) < pad:
            base36 = '0' + base36
 
    return base36 or alphabet[0]
 
def base36decode(number):
    return int(number,36)
 
def parity(v):
    v ^= v >> 16
    v ^= v >> 8
    v ^= v >> 4
    v &= 0xf
    return ((0x6996 >> v) & 1)
 
def createValue(data, dataSize):
    v = 0
    for i in range(dataSize):
        v = v*256 + ord(data[i])
    return v
 
def printSerialNumber(x):
    res = x
    sn1 = res % 0x1000000
    res = res / 0x1000000
    sn2 = res % 0x1000000
    res = res / 0x1000000
    sn3 = res
 
    sn1 = (sn1 << 1)
    if parity(sn1) == 1:
        sn1 += 1
    sn2 = (sn2 << 1)
    if parity(sn2) == 1:
        sn2 += 1
    sn3 = (sn3 << 1)
    if parity(sn3) == 1:
        sn3 += 1
 
    return base36encode(sn3,5)+base36encode(sn2,5)+base36encode(sn1,5)
 
################# main #################
p = createValue("gim913!\x95", len("gim913!\x95"))
 
name = raw_input()
if len(name) < 4:
    print ("[-]Error: invalid length. Only 4 chars above for input")
    exit()
 
hname = hashlib.md5(name).digest()
 
a = createValue(hname[:5], 5)
b = createValue(hname[5:10], 5)
c = createValue(hname[10:15], 5)
d = createValue(hname[15:], 1)
 
b = b*512 + d
Dis = b*b - 4*a*c
if Dis < 0:
    # Error: Discriminant < 0
    print ("Wrong username.")
    exit()
 
if modular_sqrt.legendre_symbol(Dis, p) <> 1:
    # Error: Legendre symbol <> 1
    print ("Wrong username.")
    exit()
 
Dis = b*b - 4*a*c
 
Dis = modular_sqrt.modular_sqrt(Dis, p);
 
x1 = ((-b - Dis) * euclidean.invmod(2*a, p)) % p
x2 = ((-b + Dis) * euclidean.invmod(2*a, p)) % p
if x1 < 0:
    x1 += p
if x2 < 0:
    x2 += p
 
print ("[+]Name = "+name)
print ("[+]Key 1 = "+printSerialNumber(x1))
print ("[+]Key 2 = "+printSerialNumber(x2))
print ("Quadratic Equation:")
print (str(int(a))+"*x^2 + "+str(int(b))+"*x + "+str(int(c))+" = 0 (mod "+str(int(p))+")")

image01.jpg

Примеры:
[+]Name = solutionmes
[+]Key 1 = 00UPA49VIUH6NQ7
[+]Key 2 = 00LWP3WT8NF1RJA
Quadratic Equation:
398204722858*x^2 + 121120408951518*x + 981640983542 = 0 (mod 7451607150867194261)

[+]Name = crackmes_de
[+]Key 1 = 00BNY8FKTU5B93L
[+]Key 2 = 0103YIY8D53K39O
Quadratic Equation:
392456139795*x^2 + 195023174131397*x + 598208146374 = 0 (mod 7451607150867194261)

[+]Name = Wow, you did it!
[+]Key 1 = 00JXU7A63D98L0Z
[+]Key 2 = 00VAR1U0IA1C3UP
Quadratic Equation:
466097814223*x^2 + 341891859689683*x + 59471944594 = 0 (mod 7451607150867194261)

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