_ ______________________ _
\ \\ _\ /_ // /
______ | __ | ______
\_ \_|_ / \ __ ___ __|_\_ \
/ /_ \/ \/ \/ \ / _/ /
/____/ / /__/\__\ _ /_/ _/____/___
\______________\__/_/__\___/_________/
wPx| /___/ |
| TEAM-53.TUTORiALS.14 |
!_ _!
(____________________)
"Как взломать rsa-1024? Asprotect 1.0/1.1/1.11c"
автор: Amenesia//TKM!
перевод: lord_Phoenix
Mais le vice n’a point pour m`ere la science,
Et la vertu n’est pas fille de l’ignorance.
Th'eodore Agrippa d’Aubign'e
(прим.пер.-эпиграф не перевел, так красивее)
1. Intro
ДЛя того, чтобы изучить основы, я решил начать с распространенных защит и их дыр.
Я начал с аспра и дырки, которую нашел Recca несколько лет назад. Всем известно, что
Recca удалось сломать рег. схему аспра, используя дыру в генераторе псевдо-случайных числе.
Итак, начнем!
ASProtect - система защиты программ, разработана для быстрой "вставки" функций защиты.
Предоставляет функции по работе с рег. ключами и для создания триал приложений.
2. Asprotect 1.0/1.1 [внутр. ключ]
Когда создается проэкт - генерируются несколько параметров, которые сохраняются в файле проэкта - name.aspr
Самы важные - A, D, E, N, которые являются числами в формате base64 (сохраняются слева направо).
A = INDtrZliM4t...0czFJpN42UQ==
D = U2atlST1lQ...kHcbIGwJU8=
E = EQAAAAAA...AAAAAAAA=
N = X7lD2zsvq3QW...ha6mOrdvULEAM8=
Потом, когда генерируется рег. код:
1 - H1 = RipeMD-160(A)
2 - H2 = MD5(Registration Information—H1)
3 - Key = RSA(D,N, [H2—Registration Information—H1])
Рег. код будет вида:
PYgt/87koSvbYPluc+/crrilfWI+ssZSU7UhgCLmK3D1C+x+
EX9n7ukwM5sKmI+nsH66V7L28BFTziNz5DOPLRHAqnI11wN5
Nd/dm0Esw20mm66V7L28BFTziNz55DOP4kzt+bie/rW4grgG
+e8/hsIuotMqUXguWKBnOXsoQ89Kg92T0MkB4FCZYuZQo=
Так что, с первого взгляда все кажется защищенным.
2.1 Генерация D, N, E
Прцоедура генерации находится в RSAVR.dll
1 - Генерация двух простых чисел - P и Q (512 бит)
1.1 - Генерация случайного числа (512 бит)
1.2 - Поиск самого ближайшего простого числа (очень медленно)
2 - N = P*Q
3 - D = E^(-1)phi(N) (E = 17)
Если мы сможем найти P и Q - дело в шляпе! =)
2.2 Генерация P и Q
unsigned long _rand()
{
Seed *= 214013;
Seed += 2531011;
return( ((Seed >> 16) & 0x7FFF) );
}
unsigned long RandInt()
{
for(i=0;i<4;i++) { rval = ((rval << 8) +_ rand()); }
return(rval);
}
Seed = ( time() + ThreadId()) xor TickCount();
for(ri=0;ri<16;ri++) { BigNumber1[ri] = RandInt(); }
BigNumber1[ri] = BigNumber1[ri] xor C0000000h;
P= nextPrime(BigNumber1);
for(ri=0;ri<16;ri++) { BigNumber2[ri] = RandInt(); }
BigNumber2[ri] = BigNumber2[ri] xor C0000000h;
Q= nextPrime(BigNumber2);
Тоесть, если мы можем "угадать" time()+ThreadId()) xor TickCount - вы можем найти P и Q..
2.3 Атака!
Я не знаю, как Recce узнал правильное значение, но я думаю, что единственный выход - брут
(всего 2^32 возможных значения):
1 - Выберем значение
2 - ВЫчислим BigNumber1 и BigNumber2
3 - Найдем P = nextPrime(BigNumber1) and Q = nextPrime(BigNumber2)
4 - Если N != P*Q выберем другое значение...
В принципе, на это потребуется немало времени, но значений всего 2^32, так что брут очень даже реален.
2.3.1 Ускорение брута
Первое улучшение алгоритма брута основано на том факте, что ThreadId и TickCount - практически всегда очень малы.
Так что за старшие биты "отвечает" time().
Также, мы можем проверять только те значения времени, которые близки к дате релиза программы.
2.3.2 Окончательное улучшение алгоритма
Проверка простое ли число очень медленная, так что нам надо найти алгоритм для проверки - является ли наше значение
правильным, перед вычислением P и Q. Вся фишка в том, что функция nextPrime() модифицирует только младший дворд
BigNumber1 и BigNumber2.
P = BigNumber1+/\1 - где /\1 <= 2^64
Q = BigNumber2+/\2 - где /\2 <= 2^64
N = P *Q = (BigNumber1+/\1)*(BigNumber2+/\2)
N = BigNumber1*BigNumber2+/\3 - где /\3 <= 2^(512+64+2)
Тоесть: N_high = BigNumber1_high *BigNumber2_high
Алгоритм:
1 - Выберем значение
2 - Вычислим BigNumber1_high и BigNumber2_high
3 - Если N_high! = BigNumber1_high*BigNumber2_high берем другое значение
4 - Вычислим BigNumber1 и BigNumber2 (чтобы избежать коллизий)
5 - Найдем P = NextPrime(BigNumber1)
и Q = NextPrime(BigNumber2)
6- Если N != P*Q берем другое значение
(прим.пер. - /\ - дельта =)
2.4 Пример
Аспр 1.1 защищен собой же. Наверное будет ложно найти пример получше =) N и E находим в защищенном файле:
N=EB1D4EADA4815F6277519791BFFA8B4C0B872D1C436515AB
D9572B22BF6A03FECB4E5CC49AF1EE35C31344617A1210663056
90529B9CE7F13ED2D37CD7034A3EDD096853EC61243BCCAC5A58
800B0330A4DD85E9AA237F2F2AE60CA049B1D2777B2E0C5FF51E
058382A86C3EC12F7AB41642022772FF2A2D3DBA704725702199
E = 17
Аспр был релизнут в октябре 2000, тоесть мы можем взять 39000000h как минимальное значение для брута.
За 1 минуту мы находим 398BBB72h (коллизия), затем 399BACC4h (1 час, чтобы проверить все 2^32 значений)
D=l8F1EGKSQWCw9Et5klCpkm9/TIQFw0xOxibd+bQNndzGYoIX
4PmHXcdZtN3VWRQfuYS/cLeEf0i+kG3Cd7kaqKCkBO3xiAFgZMf
vW8D+bov+AfjDICITq5/Lhex7PykLGtUNnH8LSsmIDSWqldwX3Q
9o8U4HcJSjSJIfS4bumc=
3. Asprotect 1.1c
Быстро Солодовников выпустил новую версию аспра, чтобы прикрыть дыру. Я думаю, что ему это не сильно удалось.. =)
ГПСЧ в новой версии:
unsigned long _rand()
{
Seed = ( time() + ThreadId()) xor TickCount();
Seed *= 214013;
Seed += 2531011;
return( ((Seed >> 16) & 0x7FFF) );
}
unsigned long RandInt()
{
for(i=0;i<4;i++)
{ rval = ((rval << 8) +_ rand()); }
return(rval);
}
for(ri=0;ri<16;ri++) { BigNumber1[ri] = RandInt(); }
BigNumber1[ri] = BigNumber1[ri] xor C0000000h;
P= nextPrime(BigNumber1);
for(ri=0;ri<16;ri++) { BigNumber2[ri] = RandInt(); }
BigNumber2[ri] = BigNumber2[ri] xor C0000000h;
Q= nextPrime(BigNumber2);
Тоесть для каждого дворда вычисляется новое значение. И здесь мы опять сделаем брутфорсер.
И опять столкнемся с проверкой значения - а их 4*(2^512) возможных.
3.1 Ускоряемся =)
GetCurrentThreadId - константа, GetTickCount и time() зависят от пройденного времени....
Но генерация такая быстрая, что GetTickCount и time() тоже константы - для каждого большого числа
вычисляется одни и те же значения(но в итоге они разные, изза проверок на простоту).
Ну и rand() возвращает всегда одно и тоже значение близкое к 07FFFh. Тоесть у нас всего
(2^15)*(2^15) значений, вместо 4*(2^512)*(2^512)
but the generation is so fast that GetTickCount and time()
are constants during the generation of a BigNumber, the same Seed is com-
puted for each dword (but the Seed is different for each BigNumber because
of primality testing step) and consequently rand() has always the same
value which is inferior to 07FFFh. So we have only 2^15*2^15 couple of seed
instead of 4*2^512*2^512:
BigNumber1 = [AorC0000000h]AAAA...AAAA
BigNumber2 = [BorC0000000h]BBBB...BBBB
3.2 Еще улучшение
Каждое большое число будет известного нам вида, мы используем этот факт для проверки, правильно
ли наше значение. Тоесть, если результат деления старших двордов N и BigNumber1 имеет вид (B or C0000000h)BB,
то мы можем предположить, что с помощью этого значения мы вычислим такое P, что Q = N/P. Тоесть надо проверить
всего лишь 2^15 значений!
P = [AorC0000000h]AAAA...AAAA+/\1
Q = [BorC0000000h]BBBB...BBBB +/\2
N = BigNumber1*BigNumber2+/\3
Тоесть: N_high/BigNumber1_high = [BorC0000000h]BBBB
1- Выбираем значение (помним про rand())...
2- Вычисляем BigNumber1_high
3- Если N_high/BigNumber1_high не нужного вида - берем след. значение
4- Вычисляем BigNumber1
5- Находим P = NextPrime(BigNumber1)
6- Q = N/P
3.3 Пример
Asprotect 1.11c защищен сам собой и:
N=C7D6E57A0D1C3A9752618FB497A6E4D1DCEC39EF22318F0C
6776E429ACBC3946F2018E643746E3817C8C389EC1D18DBC0716
E2D94C5C37F691A18D13D6E6F122D03D00090AF7AAEBC5B255CE
806D00B13B27AB93F5E25676B09D01596B57AC3C2612571EE0CD
02019B87ACE4564257C710FD02A9CBB7AD8C8672586F416D536D
Используя алго, описанный выше, я за 1 секунду (при проверке третьего значения из 2^15 возможных) узнал,
что "правильный" результат rand() - 5454542Dh. Тоесть:
P = D454542D5454542D...
Q = F0F0F088F0F0F088...
И собссно:
D = HV/nbSNxR14Tvhm4bHRVey+U+qdbHQk8Q+BPfBrY
qZYMa14KmBhtGX4flkK+gVoGGX23485UMFwdxMMux5Aw
DtEsU+ZTzlQmvNX5zEuDRVg/1jZJGc7NIBltCVy+sOt+
iVqzBnopoHPQHrNGzDkr/615Ch40ns4iIWp3i7PbRs
4. Выводы
Смешно, не так ли? =) Это достаточно древний софт, но он является отличным примером, как можно ошибиться при
создании рег. схемы.
PS: Greets to x є {TKM!,FFF,CoRE,GoD,UCF,DAMN,TMG,...}.
PPS. от переводчика - все файлы к статье в rsa.zip