Решение Mayhem - Crackme2

Сложность: 2 - Needs a little brain (or luck)
Платформа: Windows
Язык: C/C++
Дано: Crackme2

This crackme involves a bit more math than my previous crackmes. That, and a few other factors, make it (hopefully) more difficult.

Rules:
1. Write a keygen. Serials are extremely easy to bruteforce and for this reason a bruteforcer is not a valid solution.
2. No patching.
3. Have fun!

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

Примечание:
1. badboy-сообщение - это сообщение, которое отображается пользователю в случае неверной пары имя-ключ.
Текст сообщения разный, содержание всегда одно: “Вы ввели неправильное имя или пароль (ключ)”.
2. Из 1-го пункта логично получаем следующий: goodboy-сообщение - это сообщение, которое показывается
пользователю в случае корректной пары имя-ключ.
3. В тексте под словом “ключ” подразумевается значение поля “Serial”

Инструменты: OllyDbg

0. Предисловие

Будучи новичком в реверс-инжиниринге, в этой статье я постараюсь объяснить, насколько смогу свои действия, чтобы другие могли почерпнуть из них что-то для себя. Если же вы опытный реверсер, я надеюсь, что вы вынесите мой спич, в конце концов это всего лишь 2-й уровень сложности CrackMe.

1. Первоначальный анализ

Открыв программу в Olly, я запустил ее на выполнение, надеясь, что смогу поймать badboy-сообщение.

image10.jpg

После ввода имени и ключа, получаю MessageBox: "Извините, попробуйте еще раз”.

image07.jpg

Следуя стандартной логике MessageBox, я попытался “Выполнить код до тех пор, пока не встретим пользовательский”. Однако попытка закончилась неудачей, поскольку программа продолжала выполняться. Я не знаком с вызовами функций MFC, поэтому я могу лишь догадываться, что этот метод не работает в MFC приложениях. К счастью, существуют другие способы, которые мы можем использовать, чтобы найти место с badboy-сообщением. Конечно, можно найти ссылки на строки текста. Так как программа не упакована и не зашифрована, то поиск даст результаты (команда “Search for” > “All referenced text strings”)

image08.jpg

Однако я использовал другой метод. А именно взглянуть на стек вызовов и найти нужную нам функцию вручную, для этого, как только выскочило badboy-сообщение, я в отладчике поставил выполнение программы на паузу (Debug > Pause (F12)). Просматриваем стек до тех пор (минуя череду MFC вызовов функций), пока не встречаем первую ссылку на основной код.

image11.jpg

В данном случае в окошке дизассемблера отладчика переходим на адрес 13319E4 (учтите, что у вас адрес, возможно, будет другой, т.к. данный crackme имеет динамический адрес загрузки) и оказываемся совсем рядом с badboy-сообщением.

image05.jpg

Посмотрим на окружающий код и видим много интересного, помимо уже badboy и goodboy-сообщений замечаем, что имя должно быть не более 40 символов в длину. Для этого ограничения есть причина, и об этом мы узнаем позже. Видим, где происходит переход на goodboy-сообщение, как результат проверки условия. Я поставил ВР на условие по адресу 013319B0, чтобы я мог видеть результат сравнения, после чего ввел случайное имя и ключ, и сработала моя точка останова.

image12.jpg

EAX и EDI сравниваются между собой, если они равны, то ключ правильный. На первый взгляд значения в них никак не связаны с введенными именем и ключом, значит, они должны быть созданы где-то и как-то и представляют собой что-то. Попробуем ввести различные комбинации имени-ключа.
После небольшого тестирования выяснилось, что значение, хранящееся в EAX, изменяется при изменении имени, а значение в EDI при изменении ключа. Таким образом, число создаваемое от имени должно совпадать с числом создаваемым от ключа. Теперь нужно найти, где эти два числа генерируются.
Без глубокого анализа функций, просто давайте пошагово посмотрим на листинг, начиная от строки, где проверяется длина поля “имя”. Довольно быстро станет ясно, где два числа создаются.

image02.jpg

Вызов функции по адресу 01331990 создает первое число и оно лежит в EAX, следующая команда (по адресу 133995) значение из EAX записываем в EDI. EDI в дальнейшем до команды сравнения (адрес 13319В0) не изменяется, значит мы нашли функцию, которая создает число по ключу.
Вызов функции по адресу 013319А6 создает второе число и возвращает его в EAX. Дальше значение в EAX не меняется и сравнивается с EDI. Значит, нашли второй алгоритм (число по имени).
Теперь надо разбирать каждый алгоритм, и на этом шаге наш первоначальный анализ закончен.

2. Создание числа по имени

Анализируем сначала функцию, вызываемую по адресу 013319А6, ибо она легче в понимании.

image04.jpg

Сначала наше имя (ARG.1) заносим в EAX (адрес 01331829), а его длину (DWORD PTR DS:[EAX-C]) сравниваем с EDI (т.е. с 0, чуть выше есть XOR EDI, EDI). Если длина не 0, то мы попадаем в цикл, где и вычисляется нужное нам число, сфокусируемся на нем.

ЕSI в цикле выполняет роль счетчика, и пробегается по всем позициям нашего имени.

С 01331834 по 01331840 получаем код N-символа имени и записываем его в EAX, где N = ESI.

Далее идет целочисленное умножение IMUL значения из EAX на число, но что это за число? Проверим его. Первый символ - D3. Так, а что дальше. Ставим точку останова на IMUL и проверяем оставшиеся символы. 13С, 11А, затем BD. Интересно. А не зависит ли они от разных имен? Пробуем ввести различные имена. Числа те же и в том же порядке. Значит, они жестко заданы. Давайте посмотрим, проследуем по адресу, где лежит первый номер. И здесь действительно есть цифры! И вот сюрприз - их 40, и все разные. Помните, когда я сказал, что должна быть причина почему максимальная длина имени не более 40 символов? Она в этих цифрах.

image03.jpg

Коды символов имени умножаются на жестко заданные числа в порядке обработки строки имени. Выяснив смысл этих мистических чисел, давайте двигаться дальше.

Произведение записываем в ECX и сдвигаем влево. SHL ECX,4 - сдвинуть значение в ECX влево на 4, т.е. умножить значение в регистре на 16. Затем из ECX вычитаем EAX. Значит, формула такова:
значение*16 - значение => значение*15
И, наконец, последнее выражение: LEA EDI,DWORD PTR DS:[EDI+ECX*4+699]
Значение умножаем на 4 и складываем с 0х699 (1689). Результат сохраняем в EDI нарастающим итогом. После окончания цикла EDI записываем в EAX - это то самое число, созданное на основании имени.

(1)
\begin{align} \sum_{n=0}^{len(name)-1} (((name[n] * fixednum(n)) * 15) * 4 + 1689) \end{align}


name(n) - это n-й код символа введенного имени, а fixednum(n) - это n-е число из жестко заданного массива
На этом рассмотрение создания числа по имени завершим.

3. Создание числа по ключу

Для полноценного кейгена остается разобрать процесс создания числа по ключу. Идем по адресу 01331990, здесь находится вызов функции генерации числа по ключу (call 013316E0).
Этот алгоритм является более сложным, чем предыдущий, поэтому важно не углубляться в первые встречные вызовы функций и запутать тем самым себя еще больше, а всегда ориентироваться на общую картину.

image06.jpg

Здесь встречаем еще один цикл, но давайте сначала посмотрим на код, который готовит все необходимое для этого цикла. Если вы еще не видели некоторых из этих команд, не стоит беспокоиться. Это операции с плавающей точкой, но вам действительно не нужно их понимать, чтобы осмыслить общую картину, так как Olly очень хорошо помогает нам в отслеживании чисел с плавающей запятой.

Первый момент, на который нужно обратить внимание - это MFC функция, которую вызываем по адресу 01331710. Даже если мы не будем углубляться в нее, мы можем легко проверить ее результат, который появляется в ECX. А там наш пароль, но в обратном порядке! Поэтому первое, что следует отметить, наш ключ должен быть задом наперед (перевернут).

А сейчас мы готовы отправиться в дебри цикла и разобрать что он делает.

image13.jpg

В 0133174B мы видим, что что-то загружается в стек FPU, причем с фиксированного адреса. Это число 62 и очень похоже на жестко заданное (с такими уже встречались). Оно скоро нам понадобится, давайте просто примем информацию к сведению и двинемся дальше. У нас есть вызов пользовательской функции по адресу 01331753, и если мы выполним ее (step over F8), то заметим - какое-то магическое число появляется на стеке FPU. Этот момент надо поисследовать.

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

Для моего ключа (длина - 5 символов), получил следующие числа: 14776336, 238328, 3844, 62, 0. Далее пробовал различные ключи (той же длины), всегда получал эти числа. Так это же степени числа 62! (хотя, не совсем, потому что 620 = 1, а не 0, но в данном случае это не имеет значения и не важно понять, почему 0). Начиная с магического числа 62, шаблон работает. Значение числа равно значению выражения 62 в степени (позиция текущего обрабатываемого символа ключа, считая от 0). Таким образом, в случае длины строки ключа равной 4, первый обрабатываемый символ даст число 623 (помним, считаем от 0!).

Прежде чем двигаться дальше, обратим внимание, что есть вызов еще одной функции по адресу 0133178F. Если выполнить ее, то странная строка появляется в нашем стеке.

image09.jpg

Своего рода некая таблица символов, а при дальнейшем исследовании видим, что длина алфавита составляет 62! Явно, это не простое совпадение. Примем к сведению и двигаемся дальше, не углубляясь в детали.

Некое число появляется в EAX и оно TESTируется по адресу 0133179D. В моем случае для ключа “1234”, EAX=0х1B на 4-м шаге цикла. Это число умножается (013317A7) на ранее сгенерированный номер (FMUL 0х1В * 0 в моем случае, четвертый цикл был последним - поэтому его счетчик равен 0, а 0х1В = 27 в десятичной системе)! Произведение добавляется к конечному результату (013317AA).

Остальное это просто подготовка к следующему шагу цикла. После окончания цикла есть еще один вызов пользовательской функции по адресу 013317Е1 (имеется в виду, не MFC-функция), где наше сгенерированное число перемещается в EAX из стека FPU (преобразование из десятичной в шестнадцатеричную). По возвращению из рассмотренной функции (создание числа по ключу) в основной код, EAX сохраняем в EDI, где он будет оставаться неизменным до момента сравнения с другим числом.

Только неизвестным остается некое число, участвующее в умножении по адресу 013317A7, каким образом оно создается? Я начал тестировать различные ключи, и выяснил, как эти цифры генерируются. Помните, ту функцию, где была таблица символов? Данная таблица - константа, а возвращаемое некое число - это позиция, обрабатываемого в настоящее время символа, в таблице символов! Т.е. для ‘а’ получим 0, для ‘с’ - 2, и так далее. Для ключа “1234” на 4-м шаге цикла у меня было 27, потому что для ‘1’ = 27-я позиция (почему ‘1’ встретилась нам на 4-м шаге цикла, а не на 1-м, потому что ключ перед циклом алгоритм перестраиваит в обратном порядке).

Итоговая формула создания числа по ключу такова:

(2)
\begin{align} \sum_{n=0}^{len(serial)-1} (62^{n} * charcode(serial(n))) \end{align}


charcode - позиция из таблицы символов для заданного символа, serial(n) - n-й символ ключа

На этом рассмотрение создания числа по ключу завершим.

4. Keygen

Автор туториала писал его на С# NET 2.0. Мы его адаптируем под Python.

Идея такова:
- Посчитать число для имени
- Используя найденное число, вычислить ключ

Сначала создаем константы.

Name_FixedKey = [0xD3,0x13C,0x11A,0xBD,0x9C,0xC3,0x7A,0x171,0x144,0x14F,
                 0xEF,0xAD,0x13A,0x164,0xB3,0xA2,0x118,0xA4,0x161,0xC0,
                 0x14C,0x188,0xDF,0xF5,0x11C,0xD4,0x92,0xA7,0xF4,0x137,
                 0x162,0x134,0x8D,0x156,0x122,0x133,0xB7,0x18E,0x8B,0x124]
 
Serial_FixedKey = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"


Затем, пишим функцию создания числа по имени.
def ComputeNameValue(Name):
     CalculateValue = 0
     for i in range(0,len(Name)):
          CalculateValue += (ord(Name[i]) * Name_FixedKey[i] * 15) * 4 + 1689
 
     return CalculateValue


Функция соответствует вышеописанному уравнению.

Нашли число по имени, что теперь? Теперь чуть сложнее, у нас есть число, но не символы, так что мы должны выяснить, какие символы необходимо сопоставить с заданным числом. Давайте посмотрим на код, и я объясню его чуть ниже.

def ComputeSerial(NameValue):
     KeyLength = 0
 
     # 1-й цикл
     while NameValue > pow(62,KeyLength):
          KeyLength += 1
     KeyLength -= 1
     # конец 1-го цикла
 
     # 2-й цикл
     Serial = ""
     for i in range(KeyLength, 0, -1):
          KeyCharValue = 0
          while (pow(62,i) * KeyCharValue) <= NameValue:
               KeyCharValue += 1
          if KeyCharValue > 0:
               KeyCharValue -= 1
 
          NameValue -= (pow(62,i) * KeyCharValue)
          Serial += Serial_FixedKey[KeyCharValue]
 
     Serial += Serial_FixedKey[NameValue]
     return Serial[::-1]


Чтобы объяснить двумя словами как создается ключ, представьте что введенная строка ключа - это не строка, а число в 62-ричной системе счисления, где для представления чисел используется такой алфавит [a..z0..9A..Z]. Если вам нужен более полный ответ, чтобы понять в чем дело, читайте дальше.

Сначала нам надо найти - какой длины должно быть значение ключа для полученного числа по имени. Для этого надо - найти первое значение степени числа 62 большее, чем значение числа по имени. И тогда длина ключа = значение степени-1. Это то, что происходит в 1-м цикле.
2-й цикл идет в обратном порядке: от найденной длины ключа к 0. На каждом шаге цикла находим наибольшее число (62i * n), которое должно быть меньше, чем значение числа по имени, где ‘i’ счетчик цикла, и «n» то число, которое мы ищем (оно лежит в диапазоне от 0 до 61). Найденное число - это n-я позиция в таблице символов, добавляем его к строке ключа. Затем, значение числа по имени уменьшаем на (62i * n) и идем на следующий шаг цикла.

Остаток числа по имени после цикла - это индекс в таблице символов для крайнего символа в строке ключа.
А возвращаем мы Serial[::-1] - реверс строки (задом наперед) для финального представления ключа.

Вот и все. Кейген готов.


Примеры:
print(ComputeSerial(ComputeNameValue("Caelint")))
> PIIA
print(ComputeSerial(ComputeNameValue("crackmes.de")))
> p4Bfb
print(ComputeSerial(ComputeNameValue("FeS")))
> HwFr

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