Решение Zeronights Crackme 2013 и причём тут матрицы

Привет всем. Недавно на Хабре появилась статья, расписывающая взлом crackme от лаборатории Касперского с конференции ZeroNights 2013. У меня тоже получилось взломать этот crackme, но я использовал несколько иной подход для создания ключей, чем Дарвин, потому что заметил, что в crackme используются матричные операции. В отличие от Дарвина я использовал только дебаггинг при помощи OllyDbg.

Вводим случайные значения. Получаем MessageBox с Fail:

image

Открывем окно Modules( большая M) в олли. Нажимаем Ctrl + B (Search). Вводим в поле ASCII значение fail. Хит на поиск — нашли:

image

Правой кнопкой мыши на первый байт сообщения, Breakpoit -> Memory -> On Access.

Запускаем отладку. Вводим те же значения в поля crackme. Попадаем на передачу параметров MessageBox:

image

Перед push с нашей строчкой виден условный переход JNZ. Перед ним TEST EAX,EAX. То есть, если EAX не равен нулю, то вылетает MessageBox со строкой
Good work, serial is valid!
. Смотрим, откуда получаем EAX. Перед сравнением есть CALL. Видимо, в этой функции и происходит проверка ключа. Посмотрим, что ей передается. Через стэк происходит передача длины пароля и указатель на строку с почтой. В регистре ECX передается указатель на строку с паролем. Входим в функцию:

image

Смотрим на первый JNZ. Перед ним длина пароля сравнивается с 0x12 (18 в десятеричной). Если не соответствует — Fail. Дальше идет цикл (он выделен черной скобой слева), в котором идет проверка символов пароля. Они должны принадлежать множествам 0-9, A-Z и a-z. По комментариям справа можно понять, что не все функции важны для реверса. Некоторые — это просто функции копирования или выделения массивов и не представляют особого интереса. Первая функция после цикла очень важна, поэтому подробно ее рассмотрим:

image

Сразу заметны два цикла. Что же в них происходит? В первом мы заполняем массив в памяти значениями от 0 до 255.
Во втором цикле все не так просто. Взяты два указателя: на массив, заполненный в первом цикле, и на строку с почтой. Берется элемент массива по номеру цикла и символ из почты по номеру цикла по модулю длины почты. Эти байты суммируются по модулю 256 (операция AND EDI, 0xFF эквивалентна __edi % 0x100 в синтаксисе С). Получаются 2 номера элемента по шагу цикла и полученный за счет почты. Эти 2 элемента меняются местами. Почта — это ключ, при помощи которого осуществляется подстановка элементов от 0 до 256. Попросту перемешали массив. Выходим из этой функции назад в общую. Далее происходит выделение массива на 9 байт и копирование в него первых 9-ти символов пароля. Не будем рассматривать эти функции. Зайдем в функцию с комментарием на транслите, начинающимся с «hHeap zabivajetsa»:

image

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

В EDX помещается первый символ массива из 9-ти байт. То есть первый символ пароля. Дальше магия:

MOV EAX,EDX
SHR EAX,4
SHL EAX,3
SUB EDX,EAX
AND EDX, 0F

На C это будет:
EDX=(EDX- ((EDX >>4 )<<3))%16


Заменяем символ пароля в hHeap на значение из нашего замешанного массива по номеру EDX. Для остальных символов аналогично. Выходим из функции.

Выделяется еще один массив на 9 байт и в него переносятся значения из первого массива, но по определенным правилам:

image

Перемещение -это блок из MOV и MOVZX. Пусть первый массив A, а второй — B. На С:
b[0]=a[0];
b[1]=a[1];
b[2]=a[2];
b[3]=a[5];
b[4]=a[3];
b[5]=a[4];
b[6]=a[8];
b[7]=a[6];
b[8]=a[7];


После этого копируем из второго в первый. Получается, просто перемешали.

Все действия с массивом из девяти байт повторяются для второй части пароля. Получаем два массива:

image

Заходим в функцию «moshnaja obrabotka kuchi»:

image

Видим перенос второго массива в стэк. Массив обозначим B, а начало области, в которую переносим — D. На С:

D[0]=B[0];
D[1]=B[3];
D[2]=B[6];
D[3]=B[1];
D[4]=B[4];
D[5]=B[7];
D[6]=B[2];
D[7]=B[5];
D[8]=B[8];


Дальше длинный цикл, который проходит 3 раза:

image

image
Не у всех хватит терпения, поэтому просто заменим его на алгоритм на С. Пусть A — первый массив, D — массив в стэке, а E — новый массив на вывод все остальное — промежуточные переменные, а я — декомпилятор. Тогда:
for(int i=0;i<3;i++){
X[0]=A[0+i*3];
X[1]=A[1+i*3];
X[2]=A[2+i*3];
E[0+i*3]=((X[0]*D[0])%7+(X[1]*D[1])%7+(X[2]*D[2])%7)%7;
E[1+i*3]=((X[0]*D[3])%7+(X[1]*D[4])%7+(X[2]*D[5])%7)%7;
E[2+i*3]=((X[0]*D[6])%7+(X[1]*D[7])%7+(X[2]*D[8])%7)%7;
}


Выходим из функции, и массив значений в E сравнивается с массивом [1,0,0,0,1,0,0,0,1]:

image

Если совпал, то серийник правильный.

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

b[0]=a[0];
b[1]=a[1];
b[2]=a[2];
b[3]=a[5];
b[4]=a[3];
b[5]=a[4];
b[6]=a[8];
b[7]=a[6];
b[8]=a[7];


Каждая строчка матрицы сдвигается на свой номер.

Теперь внимательнее посмотрим на перенос второго массива в стэк:

D[0]=B[0];
D[1]=B[3];
D[2]=B[6];
D[3]=B[1];
D[4]=B[4];
D[5]=B[7];
D[6]=B[2];
D[7]=B[5];
D[8]=B[8];


А это интерполяция матрицы. Зачем нужна интерполяция? Да потому что функция, принимающая на вход два массива по девять байт, перемножает их как матрицы. А при чем здесь % 7? Все просто. В ячейках матрицы используется модульная арифметика в поле по модулю 7.
Тогда понятен и массив [1,0,0,0,1,0,0,0,1]. В матричном представлении — это единичная матрица.

Итак, как же нам найти ключ под свою почту? Кейген я не писал, потому что не под любую почту существует ключ, и сейчас вы поймете почему.

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

image

Главное — не забыть про смещение на номер строки.

Как мы подбираем противоположные матрицы:
Находим символ, превращающийся в 0 и находим два символа, превращающиеся в противоположные элементы (например 4 и 2).
Если у нас есть 1 — нам повезло.

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

Любые советы и комментарии приветствуются. Спасибо, что дочитали до конца.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 4

    0
    Эх, совсем математику забывать стал. Странно, что они не сделали проверку поля email на наличие @ и.
      0
      Она не нужна. Серийник и почта вводятся на странице на их сайте. На почту приходит письмо с подтверждением и, по идее, еще должно прийти приглашение на экскурсию. Так что без реальной почты никак
        +3
        >>Проблема Кейгена в том, что не всегда у нас есть элемент, который переходит в ноль. В таком случае найти две противоположные матрицы невозможно.
        Вы серьезно? Простейшим брутом легко находится множество матриц без 0 элементов, дающие единичную. Там же модуль
        "
        |3 2 2| |3 2 2|
        |1 1 2|x|2 2 3|
        |2 3 2| |1 2 1|
        
        |2 3 2| |2 2 3|
        |1 1 2|x|3 2 2|
        |3 2 2| |1 2 1|
        "
        и т.д.
        
          0
          Проверил, согласен. Придется подправить статью. Но все равно есть адреса, для которых не получится. Например, если проецируется только в 1 и 2.

        Only users with full accounts can post comments. Log in, please.