PRGN crackme by bart/xt by Tymon

.: info :.

what:          PRGN crackme by bart/xt
tools:         soft-ice, ida, manual do miracl, masm32, lcc
protection:    RSA-512, PRNG
description:   crackme napisane jest w c i skompilowane pod lcc. Nie jest
               niczym spakowane, nie ma adnych junkw, anty-tools'w,
               anty-trace'w itp...

.: start :.

Na pocztku tradycyjne - witam :) Dzisiaj posiedzimy nad crackmesem barta/xt. CrackMe wykorzystuje popularn ostatnio bibliotek miracl. So, moemy si spodziewa kolejnej dawki RSA... Dodatkowo mamy w nazwie swko PRGN (waciwie powinno by PRNG). Co to znaczy?

PRNG - pseudo-random number generator

Wic moemy si spodziewa liczb pseudo-losowych, zobaczmy wic, jakie to ma zastosowanie w crackmesie...

.: let'z go! :.

Wpisujemy w si podstawowe komendy i mamy:

push 100h                           ; nMaxCount
push offset _name                   ; lpString
push 65h                            ; nIDDlgItem
push edi                            ; hDlg
call GetDlgItemTextA
mov ds:_lName, eax
push 100h                           ; nMaxCount
push offset _serial                 ; lpString
push 67h                            ; nIDDlgItem
push edi                            ; hDlg
call GetDlgItemTextA
mov ds:_lSerial, eax

no comments :)

mov eax, ds:_lName                  ; do eax dugo name
or  eax, eax
jz  loc_40156E                      ; if = 0 to fuck you
cmp eax, 64                         ; name musi by mniejsze od 64d
jnb loc_40156E                      ; jeeli nie to fuck you
cmp ds:_lSerial, 0                  ; serial = '' ?
jz  loc_40156E                      ; jeeli tak to fuck you
and ds:_good_bad, 0                 ; czysczenie flagi reg/unreg
jmp short loc_40143E                ; jeeli wszystko oki, to przejd
                                    ; dalej

CrackMe ma maego bug'a (nieznacznego). Znaczy, jeeli wpiszemy poprawny serial, to podczas nastpnej rejestracji kady name wikszy lub rwny 64 i dowolny serial bdzie prawidowy :) Jak nie wierzysz to sprawd, no, ale nevermaind...

loc_4013FB:                             ; CODE XREF: sub_401399+B0j
mov eax, ds:_good_bad
movzx eax, ds:_serial[eax]
mov ds:_temp, eax
cmp eax, 41h
jb  short _nx
cmp eax, 46h
jbe short _seeya2
[...]
mov eax, ds:_lSerial
cmp ds:_good_bad, eax
jb  short loc_4013FB
and ds:_good_bad, 0

Powysza procka sprawdza, czy serial skada si z 0-9;A-F.

push 0
push 4000
call _mirsys                        ; inicjacja systemu miracl
mov [ebp+var_4], eax
push 0
call _mirvar                        ; inicjacja big'w
mov ds:dword_40B928, eax
[..]
push 0
call _mirvar

Najlepiej rozpoznawa funkcj miracl po argumentach, ktre s do nich przekazywane. Wystarczy sobie otworzy miracl.h i znale odpowiedni prototyp funkcji (na podstawie argumentw). Wygodne te jest uywanie sygnaturki do miracl, ale nie zawsze to dziaa (inna wersja biblioteki itd.).

mov dword ptr [eax+238h], 10h

Powysza instrukcja informuje miracl, e bdzie ona operowaa (przy konwersji) na base-16, czyli na systemie szesnastkowym.

push ds:dword_40B118
push offset _name
push ds:_lName              ; name na big
call _bytes_to_big
push offset _serial
push ds:dword_40C140
call _cinstr                ; serial na big
push offset String
push ds:dword_40C138
call _cinstr                ; magic key na big
push ds:dword_40B010
push 10001h
call _convert               ; 10001h na big

10001 - jest to charakterystyczna liczba dla RSA (najbardziej popularne 'e'). Oczywicie 'e' moe by take inn liczb.

push ds:dword_40B928                ; buffer
push ds:dword_40C138                ; big(magic key)
push ds:dword_40B010                ; big(e)
push ds:dword_40C140                ; big(serial)
call _powmod
push ds:dword_40B928                ; sn^e mod magic_key
push ds:dword_40B118                ; big(name)
call _compare                       ; porwnaj
add esp, 58h
or  eax, eax
jnz short loc_40152F                ; jeeli rwne to good serial
mov ds:_good_bad, 1

So, procka powmod robi cos takiego:

powmod = serial ^ e mod magic_key

jak wiemy standardowy wzr RSA wyglda tak:

c = m^e mod n

Co z tego wynika? Oczywicie, e naszym n (kluczem publicznym) jest magic key z crackme. Jak moe ju zauwaye ma on 512 bitw :). Jak wiemy, na zwykym home pc zamanie klucza ~300 bits nie jest zbytnio realne (chocia, pono ju jaki kole rozoy na czynniki pierwsze ~400 bits przy uyciu zmodyfikowanej wersji MPQS). So, crackme jest nieamliwe? No wanie w takich sytuacjach najlepiej poszuka jakiego obejcia.... Pamitasz PRGN w nazwie crackmesa? Przecie to musi mie jakie zastosowanie... Moe ju zauwaye, e magic key jest inny podczas kadego uruchomienia crackme. So, chyba nie wszystko stracone :) Looknijmy wic na procke PRNG.

call GetTickCount
push eax
push [ebp+hDlg]
call _PRNG

ciekawe.... :)

push ebp
mov ebp, esp
push edi
push 0
push 4000
call _mirsys                   ; inicjacja miracl
mov edi, eax
mov dword ptr [edi+238h], 10h  ; base-16
push 0
call _mirvar                   ; inicjacja zmiennych
mov ds:dword_40B11C, eax
push 0
call _mirvar
mov ds:dword_40C13C, eax
push 0
call _mirvar
mov ds:dword_40C138, eax
push [ebp+arg_4]               ; liczba pseudo-losowa (z GetTickCount)
call _obetnij

Powyszy call zmienia dowolna liczb na liczb 16 bitowa. Praktycznie, jest to instrukcja:

x = x & 0xFFFF

push ds:_prime1
push 20h
call _make
push ds:_prime2
push 20h
call _make

Procka _make jest dosy ciekaw posta, so looknijmy:

jmp short loc_4012B6

loc_4012A7:
call _mix_seed
mov edx, eax
mov ds:_string[edi], dl   ; generuje 32 bajtowy string
inc edi

loc_4012B6:
cmp edi, esi
jb  short loc_4012A7
push ebx
push offset _string
push esi
call _bytes_to_big        ; wygenerowany string na big
push ebx
push ebx
call _nxprime             ; generuje kolejna liczbe pierwsza
                          ; wiksz od liczby podanej w argumencie

Jak wida procka _make generuje liczb pierwsz na podstawie naszego 16 bitowego seed. Jak pewnie zauwaye procka wykonywana jest 2 razy, wic na podstawie seed generowane s 2 liczby pierwsze.

push ds:_n
push ds:_prime2
push ds:_prime1
call sub_4024F8                     ; n = prime1 * prime2
push offset _magic_key
push ds:_n
call cotstr                         ; big2ASCII
push offset _magic_key              ; lpString
push 66h                            ; nIDDlgItem
push [ebp+hDlg]                     ; hDlg
call SetDlgItemTextA

Jak wida powyszy kawaek mnoy dwie liczby pierwsze, a nastpnie wynik zmienia na string i pokazuje w okienku magic key. Jak pamitamy N=p*q, gdzie p i q s liczbami pierwszymi - wic wszystko si zgadza, jest to rsa-512. Tylko, jak to rozwiza? Skoro mamy p i q, to moemy obliczy d, a jak mamy d to moemy obliczy serial. Jak pamitamy n liczone jest na podstawie 16 bitowego seed, moemy wic zrobi w naszym keygenie maego brute-force'a. Po prostu bdziemy generowali na podstawie kolejnych wartoci seed [ 0..0xFFFF ] modulus n i porwnywali z magic key. Nastpnie, jeeli znajdziemy odpowiednie seed, to bdziemy posiadali take wartoci dwch liczb pierwszych p i q. Na podstawie nich moemy wygenerowa sobie d i odpowiednio odszyfrowa name. Oki, wrmy jednak do main procki. Warunek jest taki:

jeeli name = serial^e mod n(magic key) to good serial

z tego wynika, e:

serial = name^d mod n(magic key) - oczywicie wszystkie wartoci sa w formacie big.

Warto te wspomnie jak obliczy d na podstawie p i q. Wzr to:

d = e^-1 mod ((p-1)*(q-1))

W kodzie c przedstawia si to mniej wicej tak:
decr(p,1,p);
decr(q,1,q);
multiply(p,q,p);
xgcd(e,p,d,d,d);

Nom i to waciwie wszystko :) Jak napisae sobie takiego keygen'a to pewnie zauwaye, e dziaa on ba...ardzo wolno :). Warto wic zastanowi si jeszcze na sposobami optymalizacji.

.: optymalizacja :.

Standardowo nasz brutal wyglada tak:

cinstr(mk, szMagic);

for (i=0; ix10000; i++)
{
        x = i;                  // x = seed
        genstr(&x,&szPrime1);
        genstr(&x,&szPrime2);

        bytes_to_big(0x20, szPrime1,p);
        nxprime(p,p);
        bytes_to_big(0x20, szPrime2,q);
        nxprime(q,q);
        multiply(p,q,n);

        if (!compare(n,mk))
            break;
}

bleee.... to dziaa bardzooo woooolno. Jak to zoptymalizowa? Moemy zmniejszy ilo wykonywanych instrukcji, przez sprawdzenie, czy magic_key jest podzielne przez nasz wygenerowan liczb pierwsz. Jeeli tak, to generujemy drug liczb pierwsz i liczymy d.

Wyglda to jako tak:

cinstr(mk, szMagic);

for (i=0; ix10000; i++)
{
        x = i;                  // x = seed
        genstr(&x,&szPrime1);
        bytes_to_big(0x20, szPrime1,p);
        nxprime(p,p);

        if(divisible(n,p))
           break;
}

Oki, wyglda ju lepiej, ale cay czas trzeba czeka na wygenerowanie seriala. Moe jeszcze troch optymalizacji? Jak si okazuje jest to moliwe. Na pomys ten wpad Elessar//FHCP (jak dobrze pamitam jest to chyba norweska crack- grupa). So, wpad on na pomys podzielenia bruta na kilka testw. W pierwszym z nich nie uy adnej funkcji z miracl !!! Jak si okazuje jest to bardzo proste. Wystarczy zauway tak zaleno:

12345678 3AA22222 * A2345123 A2132133 = B88D71EB D90DA7CA 37919CAA 1392EC6
12345678          * A2345123          = B88D71E8 CE3CA68

12345678 12345678 * 87654321 87654321 = 9A0CD058 3FA2782E B11E7F57 0B88D78
12345678          * 87654321          = 9A0CD057 0B88D78

Jak wida mnoc pierwsze 32 bity z p i q moemy otrzyma pierwsze 28 bitw n. Jak wiadomo brak funkcji miracl w gwnym tecie brute-forca bardzo przypieszy nam generacj seriala (szczerze mwic, nie mylaem, e przypieszy tak bardzo :o). Gwn prock sprawdzajca najlepiej napisa pod asm. Wygodnie jest tutaj uy Visual C++, ale ja skorzystaem z lcc, a wstawki asm skompilowaem pod masm32. Jak wiadomo lcc tworzy jedne z najmniejszych plikw wynikowych. Keygen powinien by doczony do textu. Wykorzystaem w nim obie metody optymalizacji osigajc naprawd szybki sposb generacji. Razem z nim doczam src. Moe si komu to przyda :)

.: the end :.

Nom, wic crackme poamane. Na koniec mog jeszcze przytoczy cytat z piosenki, ktra przewina si mi w winampie podczas pisania tego textu:

"Ja mam zby w dupie,
ogromne zby w dupie,
kiedy id po ulicy,
ky mi stercz z odbytnicy

Ja mam zby w dupie,
ogromne zby w dupie,
zemsta jest tu oczywista,
niechaj martwi si dentysta"

"Zby" - mr. z'oob (takie fajne rock'n'regge - utwr mona cign ze strony mr. z'oob'a)

I tym, jake optymistycznym wierszykiem, kocz ten tutorial. Do zobaczenia (zemailowania)! Jak masz pytania to pisz: tymon_crk@wp.pl.

.: greetz :.

aaocg + htbteam + tkm! + veneta/mbe + all who knows me