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

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

В качестве платформы была выбрана 64-битная версия ОС Windows. 64 бита — потому что использование Hex-Rays Decompiler для x86 сильно упрощает задачу, а под x64 декомпилятора пока нет. Да и вообще, 64-битные приложения уже стали обычным явлением.

Итак, была собрана небольшая программа с использованием Qt (и статических библиотек). При этом исполняемый файл получился размером почти 10 МБ. Но разве это много для настоящего реверсера? Хотя, по отзывам, некоторых участников напугал размер файла. С другой стороны, Qt оставляет кучу полезной информации, а уж отделять зерна от плевел реверсер должен уметь...

Для старта программа требовала наличия в системе двух динамических библиотек (msvcp110.dll и msvcr110.dll). Кое-кто из конкурсантов жаловался, что у него программа вообще не запускалась, а падала с исключением. Но у остальных участников или настройки были заданы как следует, или мотивация оказалась сильнее ;)

На первом этапе требовалось ввести имя пользователя и ключ. Программа проверяла соответствие и сообщала об успехе или неуспехе. Кроме декодирования Base64 (которое элементарно определялось по строке с алфавитом), основная проверка была написана с использованием OpenSSL. Библиотека удобна реверсеру тем, что для нее существует возможность заглянуть в исходники и определить имя практически любой функции за считанные минуты.
В исходниках функция проверки выглядела так:

phdInt checkDSAsig (BIGNUM *h, BIGNUM *r, BIGNUM*s) {
BN_CTX *ctx = BN_CTX_new();
BIGNUM *g = BN_bin2bn(El_g, sizeof(El_g), NULL);
BIGNUM *p = BN_bin2bn(El_p, sizeof(El_p), NULL);
BIGNUM *y = BN_bin2bn(El_y, sizeof(El_y), NULL);
BIGNUM *v1 = BN_new();
BIGNUM *v2 = BN_new();
BIGNUM *t1 = BN_new();
BIGNUM *t2 = BN_new();
phdInt rc = 0;

if (BN_mod_exp(v1, g, h, p, ctx) && BN_mod_exp(t1, y, r, p, ctx) && BN_mod_exp(t2, r, s, p, ctx) && BN_mod_mul(v2, t1, t2, p, ctx) && 0 == BN_cmp (v1, v2)) rc = 1;

BN_clear_free(t2);
BN_clear_free(t1);
BN_clear_free(v2);
BN_clear_free(v1);
BN_clear_free(y);
BN_clear_free(p);
BN_clear_free(g);
BN_CTX_free(ctx);
return rc;

Некоторые познания в криптографии позволяют сразу понять, что это проверка цифровой подписи по алгоритму Эль-Гамаля. Размер модуля El_p, по которому выполняются операции, — 500 бит, и такая подпись считается стойкой. Так что в лоб ключ вычислить не получится.

Отдельная ветка кода проверяла, что длина введенного ключа равна 6 символам, считала от него SHA1 и сравнивала первые 8 байт с последовательностью {0xEE,0xD1,0xAC,0xA8,0xD0,0xCC,0xA3,0x3F}. 6-символьные строки, состоящих из алфавита Base64 — это всего 236 вариантов. Если их перебрать (что было необязательно — достаточно исправить условие перехода), то найдется пасхальное яйцо — слово «PHDays».

При активации пасхального яйца программа начинает что-то усиленно делать, но результата дождаться вряд ли удастся. На каждой итерации генерируется большое число, не превышающее по значению El_p, умножается на открытый ключ Эль-Гамаля El_y по модулю El_p, и результат должен оказаться равен 313373. Если это произойдет, то сгенерированное число используется как ключ шифрования для алгоритма RC4, и этим ключом расшифровывается строка с кодом, содержащая правильную подпись Эль-Гамаля. В теории генератор случайных чисел когда-нибудь выдаст такую последовательность байтов, которая будет являться правильным ключом RC4, но вряд ли это произойдет раньше, чем погаснет Солнце. Поэтому предполагалось, что конкурсанты должны получить правильный ключ RC4 — просто вычислив алгебраическое дополнение при помощи расширенного алгоритма Евклида.

Получение валидной подписи Эль-Гамаля — это еще не решение первого этапа, так как имя, для которого была сгенерирована подпись, содержит нулевые байты: "|<33p y0ur pr1v473 $3cr37\0\0\0". А такую строку невозможно ввести как имя: нулевые байты будут отброшены.

Внимательные криптографы должны были сразу заметить, что в коде проверки подписи отсутствует описанная в алгоритме проверка (0 < r < El_p). На этот случай в книге Handbook of Applied Cryptography (раздел 11.66.iv) приведена атака, позволяющая вычислить подпись для любого сообщения при наличии всего одной валидной подписи. Посредством этой атаки и получается подпись для любого имени, признаваемая программой.

Во второй части задания введенный ключ не был завязан на имя пользователя. Ключ декодировался Base64, потом над ним выполнялись какие-то хитрые действия, и в результате должен был получиться набор байтов, в котором искалась подстрока "PHDays III validator ;)\0". Изначально мы планировали, что подстрока будет искаться в любом месте, но из-за ошибки кодирования (разработчики тоже люди) совпадение проверялось лишь в начале выходного набора байтов.

Сложность задания была в том, что в нем тоже применялись элементы криптографии с открытым ключом, но реализованы они были самостоятельно и не совсем очевидным способом. Фактически введенный ключ возводился в степень по модулю большого (1000-битового) числа, являющегося произведением двух простых чисел. А это именно та математика, которая лежит в основе криптосистемы RSA. Возведение в степень было реализовано через умножение Монтгомери, а входное число должно быть заранее приведено по Монтгомери.

Публичная экспонента имела значение 5, и при правильной реализации проверки вычисление входного секрета требовало бы факторизации 1000-битового числа, что пока никому не удавалось. Но так как проверялось лишь наличие 24-байтовой подстроки, можно было вычислить корень 5-й степени от желаемого результата (не по модулю!), привести его по Монтгомери, закодировать Base64 и получить ключ для второй части.

Третья часть была не совсем обычна с точки зрения привычных crackme-заданий, где предлагается решить задачу математически. Но обо всем по порядку. Алгоритм проверки ключа декодировал введенные пользователем данные в буфер размером sizeof(El_p)*2+1024 по алгоритму Base64. Причем если декодированные данные занимали больше, чем sizeof(El_r), такой ключ не признавался валидным. После от декодированных данных брался хэш SHA-3, который сравнивался со строкой "ESETESETESETESETESETESETESETESET". Очевидно, что даже автор задания не знал правильного входного значения, что должно было спровоцировать участников на поиск альтернативного пути решения.

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

Проверка решения всего задания была строена следующим образом: она проверяла в глобальной переменной 3 бита — по каждому биту на каждую часть задания — и, если все биты выставлены, выводила окошко с поздравлением о прохождении задания. Значит, чтобы решить задание, осталось найти ROP-гаджеты, позволяющие записать по адресу глобальной переменной число 7 и корректно завершить выполнение функции проверки третей части. После чего можно было увидеть окно с поздравлением.

По итогам соревнования пьедестал почета выглядит так:

I место: Виктор Алюшин

II место: Михаил Воронов, Денис Литвинов

III место: Антон Черепанов

Победитель получил фирменный рюкзак PHDays и AR Drone 2.0, остальные призеры соревнования также получили памятные подарки. Поздравляем!



P.S. Виктор Алюшин написал отличный райтап, посвященный конкурсу.