Решение happytown - CrackMe.HappyTown.VC.0040

Сложность: 3 - Getting harder
Платформа: Windows
Язык: C/C++
Дано: CrackMe.HappyTown.VC.0040

Знание математики - обязательно!

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

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

Подготовка

Crackme легче, чем он кажется. Автор redoC благодарит тех, кто помогли ему в поисках решения - tomkol и HMX0101.
Crackme использует free LIP (Arjen K. Lenstra) - библиотеку для работы с большими числами. Для каких целей? Для схемы шифрования RSA. Чтобы функции работы с большими числами (такие, как zhsread, zexpmod, zcompare) были распознаны дизассемблером IDA, рекомендую использовать сигнатуры для библиотеки free LIP. К примеру, эти сигнатуры включены в пакет сигнатур http://www.woodmann.com/collaborative/tools/index.php/RE-SIGS.

Процесс

Запускаем crackme. Под восхитительную музыку Дзё Хисаиси (звуковая тема для мультфильма «Небесный замок Лапута» Хаяо Миядзаки) мы должны ввести имя (Name), ключ (Serial) и некий Magic.

image00.jpg

По кнопке «Check» мы перейдем непосредственно к проверке указанных данных, начиная с адреса 00404700:

image01.jpg

Первая проверка основана на криптосистеме RSA (смотрите описание RSA).
SomeHashFunc (Name) == RSAEncrypt (Serial)

Самый обычный способ атаки на RSA – это факторизация модуля N, с последующим нахождением секретной экспоненты D. Но в нашем случае – такая атака может затянуться на месяцы и годы… Потому что длина модуля N в нашем случае составляет 512 бит.

N = 6F907AAA920DAF37AD19DD6974540903…188BDCFB9

Не стоит отчаиваться. Присмотритесь к ключу шифрования E. Он довольно длинный.

E = 12754A064C91DD0A8E26385EC9335A2…8AEA613F70D

Общеизвестно, что в алгоритме RSA для ускорения операций с открытым ключом используют малые шифрующие экспоненты. В некоторых приложениях этой криптосистемы существеннее ускорить процессы расшифрования. Поэтому имеет смысл выбирать небольшую расшифровывающую экспоненту D. Ясно, что при этом получается большое значение открытого ключа E. Слишком маленькое число в качестве секретной экспоненты D мы брать не можем, поскольку атакующий определит ее простым перебором. Более того, учитывая изощренную атаку Винера (см. атаки на RSA - теорема Винера), опирающуюся на непрерывные дроби (continued fraction), необходимо выбирать D среди чисел, размер которых меньше, чем $\frac{1}{3} * N^{\frac{1}{4}}$

Пишем код, использующий теорему Винера:

# -*- coding: cp1251 -*-
## Атака Винера на криптосистему RSA - раскрытие малого секретного показателя
 
# функции для разложения числа в непрерывную дробь
def convergents(cf):
    r, s, p, q = 0, 1, 1, 0
    for c in cf:
        r, s, p, q = p, q, c*p+r, c*q+s
        yield p, q
 
def contfrac(p, q):
    while q:
        n = p // q
        yield n
        q, p = p - q*n, q
 
# экспонента Е
isE = 0x12754A064C91DD0A8E26385EC9335A268192B730DE8541535695C9EC68ADD24F22C5DDC3CD9D44EC38FA2F708640CB7189069E956FE84F10301128AEA613F70D
# модуль N
isN = 0x6F907AAA920DAF37AD19DD6974540903FBC772FE38F314F4B058076B097911FEA8E7BE75254BDB6536F96C1A2F5BDB8C69EF81C61E369837F3B9CBC188BDCFB9
 
# по теореме Винера считаем ограничение для секретной экспоненты D
limitD = int(pow(0.33 * isN, 0.25))
print ("Find D < 1/3*N^^1/4: D < "+str(limitD))
 
# раскладываем число E/N в непрерывную дробь и проверяем знаменатель
# каждой подходящей дроби: не является ли он секретным ключом
# "Проверяем" - означает что берем любое свое сообщение (М), шифруем его
# С = М^^E mod N
# а затем расшифровываем его найденным знаменателем подходящей дроби
# M = C^^D mod N
# Если сообщения совпадают - значит мы нашли секрет D.
myM = 0x01010101
 
contf = list(convergents(contfrac(isE,isN)))
for i in range(len(contf)):
    current = contf[i]
    if current[1] > limitD:
        break
    # С = М^^E mod N
    isC = pow(myM,isE,isN)
    # M = C^^D mod N
    myM2 = pow(isC,current[1],isN)
    if myM == myM2:
        print ("is fraction: "+str(current[0])+"/"+str(current[1])+
        ". Need check denominator: "+str(current[1])+". VALID VALUE")
    else:
        print ("is fraction: "+str(current[0])+"/"+str(current[1])+
        ". Need check denominator: "+str(current[1])+". Invalid")


Результат:

Find D < 1/3*N^^1/4: D < 209550798302683308657166054060688670720
is fraction: 0/1. Need check denominator: 1. Invalid
is fraction: 1/6. Need check denominator: 6. Invalid
is fraction: 22/133. Need check denominator: 133. Invalid
is fraction: 23/139. Need check denominator: 139. Invalid
is fraction: 45/272. Need check denominator: 272. Invalid
is fraction: 68/411. Need check denominator: 411. Invalid
is fraction: 249/1505. Need check denominator: 1505. Invalid
is fraction: 5297/32016. Need check denominator: 32016. Invalid
is fraction: 5546/33521. Need check denominator: 33521. Invalid
is fraction: 10843/65537. Need check denominator: 65537. VALID VALUE

Значит, D = 65537 (0x10001)

Находим Serial = pow (SomeHashFunc(Name), 0x10001) mod N

Я не смог определить, что за хэш используется в этом crackme (да, да – это функция, которую я обозначаю как SomeHashFunc). Поэтому я распарсил код, отвечающий за создание хэша, и написал HappyTownHash (модуль happytownhash.py).

Но это еще не все. Есть вторая проверка, которая никак не зависит от первой. Она расшифровывает goodboy-сообщение (шифр RC4 - смотрите описание RC4 и качаем его Python-реализацию модуль rc4.py). Crackme использует строку Magic как ключ для потокового шифра RC4. Crackme расшифровывает жестко заданные 16 байт «A4 8F 9B FF 6D 3A FD 7D 56 CB AC D6 46 27 50 65», которые пишутся на стек вначале функции CheckProc. Существует несколько концепций атак на RC4, но обычно они требуют наличия немалого количество зашифрованных данных. В любом случае мы можем попытаться выполнить брутфорс. Через какое-то время мы получим значение Magic-строки – "10001" (возможно, это подсказка тем, кто застрял на первой проверке) и тогда мы сможем расшифровать goodboy-сообщение: "Wow, you did it!".

Кейген

# -*- coding: cp1251 -*-
try :
  from happytownhash import HappyTownHash
except :
  print "To work this keygen need the HappyTownHash implementation located here:"
  print "http://solutionmes.wdfiles.com/local--files/mod-py/happytownhash.py"
 
# Example:
# name = "crackmes.de"
name = raw_input()
if len(name) < 2:
    print ("[-]Error: invalid length. Only 2 chars above for input")
    exit()
 
# exponent D
isD = 0x10001
# module N
isN = 0x6F907AAA920DAF37AD19DD6974540903FBC772FE38F314F4B058076B097911FEA8E7BE75254BDB6536F96C1A2F5BDB8C69EF81C61E369837F3B9CBC188BDCFB9
 
# module N
hash_name = HappyTownHash(name).hexdigest()
res = "%X" % pow(int(hash_name, 16), isD, isN)
 
print ("[+]Name = "+name)
print ("[+]Magic = 10001")
print ("[+]Serial = "+res)


Примеры:
[+]Name = solutionmes
[+]Magic = 10001
[+]Serial = 576A66EA66D8A33AAF7E0C5E3541CE62FAF0DE3A43E3167BE68EB846C5FC00A6B2ADD7BDF5AF9EA2DCF
38AF73B4C9FFBBD4A382B0B17C6DFFF59AF828AA0A24

[+]Name = crackmes.de
[+]Magic = 10001
[+]Serial = 5D145538F0B3919DF6455C7824A038BDAA3B4F6AB49437A599AFE6D2FF99589AE018080A951BBAE5B111
89AF84A70C549292506E60EC51C17C73133C585D1E46

[+]Name = redoC
[+]Magic = 10001
[+]Serial = F42643D623F9DB243F928FF8E3728998B7DBACCF3E1873A8FB58330D29F1A9F7CC198D9030D74B665DC38
A84CF3E0B4E8139BBABE587DE3D166A35796898708


image02.jpg

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