RSA defeating 'n reversing

Written by Evilcry.

Questo articolo è nato dalla fusione della mia esperienza con qualche altro articolo trovato quà e là. Ringrazio l' admin di crackmes (Zer0) e gli altri di anticrack per i vari consigli.

-Hiew

-SoftICE o qualunque altro debugger

-RSA Tool 2

-Calcolatrice

-Qualche tool per il decripting (tipo powmod)

www.google.it

Lockless 3 CM (se volete fare pratica)

RSA overview

Da qualche tempo a questa parte, ho iniziato ad interessarmi di RSA, sia perchè è interessante da studiare come sistema di crittografia, sia perchè mi è capitato in più di una protezione, ed inizialmente non sapevo nemmeno che cosa fosse!. L' Rsa è un cifrario a chiave pubblica nato al M.I.T. nel 1978, ad opera di Ron Rivest, Adi Shamir e Les Andleman (RSA deriva infatti dal cognome di questi 3 ricercatori). L' Rsa è un crittosistema asimmetrico che si basa su alcune proprietà particolari che hanno i numeri primi. Questo sistema ha trovato un vasto campo di utilizzo, algoritmi come El-Gamal (anche El-Gamal è un sistema asimmetrico e quindi abbastanza sicuro) sono diventati più rari, dato il loro massiccio utilizzo in passato. Vediamo adesso un' ipotetica sessione di crypting: nella quasi totalità dei casi il messaggio viene trasformato in Int cioè in numero intero, e poi si tratta soprattutto di un discorso matematico. Il primo passo per criptare un messaggio è :

n=p*q

N come si può notare dall' equazione ( meglio relazione matematica), è il prodotto tra p e q che sono 2 numeri primi. Con la dovuta cautela si può affermare che più piccoli sono P e Q è minore è la sicurezza, quindi è preferibile usare un modulo N abbastanza grande. Adesso va calcolato Ô(n). Per far ciò si usa:

Ô(n)=(p-1)*(q-1)

Questa è un' implementazione o più precisamente estensione del teorema di Eulero. In pratica Ô(n), è un numero 'RELATIVAMENTE' primo a (p-1)*(q-1). Ma a questo punto qualcuno potrebbe chiedersi, che significa "relativamente primo": un numero è relativamente primo ad un altro quando questi due numeri non hanno fattori in comune, tranne ovviamente 1. Ad esempio 8 e 21 non sono numeri primi, però 8 e 21 saranno relativamente primi ad un altro numero cioè 1, dato che l' unico fattore comune a 8 e 21 è 1. Precisazione (i fattori di 8 sono 1,2,4,8, quelli di 21 sono 1,3,7,21). Spero di aver chiarito un pò questo concetto. {{{ Tnx fly to CyberLaw}}}.

Un altro passo e siamo apposto. Molto semplicemente 'E' si ricava da:

e =Ô(n)

E rappresenta la chiave (o meglio l' Esponente pubblico) con cui sarà criptato il nostro messaggio. Perciò E dev' essere un numero primo. La chiave di decrittazione d si ottiene attraverso:

d = e^(-1) mod ((p-1)*(q-1)) ------->Perciò dobbiamo conoscere 'e', 'p' e 'q'

Ok, adesso sappiamo più o meno come avviene una sessione Rsa, come avrete certamente notato durante quest' operazione ci sono dei valori che conosciamo e altri che vanno scoperti (nel caso di un attacco). Possiamo crearci quindi una tabella che in seguto ci potrebbe essere d' aiuto.

A questa tabella si potrebbe aggiungere x (messaggio in chiaro) ed y (messaggio criptato). Adesso siamo arrivati al cuore dell' algoritmo cioè alla strafamosa:

C=M^e mod n

Dove M è il messaggio da criptare e C è il messaggio criptato. Cercate di ricordarla dato che è il nucleo dell' algoritmo. Spero che sappiate ricavarivi la formula inversa in modo da ottenere il messaggio originale. La formula è la seguente:

M=C^d mod n

Siamo alla fine della nostra panoramica sul Rsa, come avrete sicuramente notato si tratta di un discorso principalmente matematico, ho cercato di sintetizzare al massimo il discorso, vi ho risparmiato tutti i retroscena (teorema di Eulero, Fermat) o si sistemi di fattorizzazione tipo il Metodo della Curva Ellittica (buon metodo per numeri piccoli, se però siamo di fronte a numeri grandi, risulta molto lento), poi ci sono: Pollard's Monte Carlo Algorithm, Continued Fraction Algorithm, Trial Division (questo è il più vecchio metodo di fattorizzazione che conosco). In questo periodo non c'è neanche bisogno di sbattersi molto con calcoli, dato che ci sono tanti programmi (specialmente dopo MIRACL) che fanno questo per noi.

Pratical RSA

In questa sezione iniziamo a fare pratica con il programma RsaTool2 (dei The Egoiste TMG) che ci sarà molto utile per il reversing. Per prima cosa, dopo aver aperto il programma settate il Numer Base) a 10 (cioè lavoriamo in base decimale) , e verifichiamo la veridicità della formula:

n=p*q

Nel riquadro "Modulus N", inserite 47 e premete "Factor N", questo dovrebbe dirvi che è un numero primo, stessa cosa con 53. Adesso otteniamo N=2491 da una semplice moltiplicazione (47*53), facendo finta di non conoscere P e Q, mettiamo 2491 in "Modulus N", e vediamo cosa si ottiene se lo fattorizziamo. Il programma ritorna esattamente in valori P e Q. Se andiamo un attimo a vedere la formula:

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

vediamo che possiamo ricavarci anche la chiave di decripto D, avendo però P e Q, mettiamo i valori P e Q nei loro relativi fields, e premiamo "Calc D", adesso sappiamo anche la chiave di decriptazione. Avendo il messaggio criptato, adesso possiamo decrittarlo. Per far questo basta applicare la formula:

M=(C^d) mod n

Possiamo usare la stessa calcolatrice di windows per decriptare numeri relativamente piccoli, o meglio costruirci un programma che faccia questo per noi.

La fattorizzazione (addendum)

Questa piccola sezione, non è di fondamentale importanza per capire l' algoritmo, ma potrebbe aiutarvi a capire quali sono le problematiche più importanti di un attacco a quest' ultimo. Come spero abbiate capito, per riuscire a violare un codice protetto con Rsa dobbiamo FATTORIZZARE il modulo N. Fin quando si tratta di fattorizzare numeri piccoli non ci sono problemi, ma i problemi sorgono quando si hanno davanti moduli N molto grossi, in questo caso vanno usati algoritmi di tipo probabilistico. Gli algoritmi per la fattorizzazione si dividono in due categorie:

-Algoritmi deterministici.

-Algoritmi di Montecarlo (si basano su una scelta semi-casuale dei dati di partenza).

Più precisamente gli algoritmi deterministici sono a loro volta divisi in tre categorie:

-Algoritmi che restituiscono ad ogni tentativo riuscito un divisore proprio (sia o non sia un numero primo)

-Algoritmi che per ogni tentativo riuscito restituiscono SEMPRE un divisore primo.

-Algoritmi che ad ogni tentativo riuscito restituiscono un divisore comune al numero dato.

L' algoritmo o teorema di Euclide, è quello che viene più usato per gli attacchi. La formula comunemente utilizzata è:

x=(x.a)(x.b)/(x.a.b) mod N

Sia N=777 se si divide per 3 otteniamo 259 (che è >32), 259 si può dividere per 7 e si ottiene 37 (che è < 72). I divisori primi di 259 perciò sono: 3, 7, 37. Provate a fattorizzarlo con RsaTool2 ed otterrete gli stessi fattori. Questo genere di algoritmi deterministici possono essere buoni (per buoni si intende la rapidità di risoluzione) per numeri piccoli, per risolvere numeri molto grandi vengono invece usati gli algoritmi di Montecarlo, cioè di tipo probabilistico.

{{Guardare le referenze a fine art.}}

Reversing corner

Ora che bene o male dovremmo aver acquistato una certa familiarità con questo algoritmo, iniziamo a vedere qualche esempio pratico. Iniziamo con un crackme abbastanza semplice ed utile. Io ho scelto il lockless 3CM, reperibile sul sito dei lockless. Per prima cosa mettiamo due bpx a getdlgitemtexta ed a getwindowtexta. Dopo che sice ha poppato dovremmo essere qui:

Reference To: USER32.GetDlgItemTextA

004137FE Call dword ptr [00428910]

00413804 jmp 00413819 ;Salta sotto

Referenced by a (U)nconditional or (C)onditional Jump at Address:

00413819 pop ebp

0041381A ret 000C

Dopo la chiamata a getdlgitemtexta e dopo il ret ci troveremo qui:

004029B0 push FFFFFFFF

004029B2 push 00419E18

004029B7 mov eax, dword ptr fs:[00000000]

004029BD push eax

004029BE mov dword ptr fs:[00000000], esp

004029C5 sub esp, 00000650

004029CB push esi

004029CC push edi

Possible StringData Ref from Data Obj ->"9901" ; Questo è un valore molto importante,

004029CD push 004200DC

004029D2 lea ecx, dword ptr [esp+000000E4]

004029D9 call 00401130 ;In questa call il numero 9901 viene "copiato" in un' altra locazione

Possible StringData Ref from Data Obj ->"12790891"; Anche questo è importantissimo|

004029DE push 004200D0

004029E3 lea ecx, dword ptr [esp+1C]

004029E7 mov dword ptr [esp+00000664], 00000000

004029F2 call 00401130 ;Chiamata alla solita call, che ora trasferisce 12790891

Possible StringData Ref from Data Obj ->"8483678" ; Altro valore di grande importanza

004029F7 push 004200C8

004029FC lea ecx, dword ptr [esp+00000274]

00402A03 mov byte ptr [esp+00000664], 01

00402A0B call 00401130 ;Idem come sopra

Possible StringData Ref from Data Obj ->"5666933" ;Ultimo valore ma non di meno importante

00402A10 push 004200C0

00402A15 lea ecx, dword ptr [esp+000001AC]

00402A1C mov byte ptr [esp+00000664], 02

00402A24 call 00401130 ;viene richiamata la solita call

00402A29 mov edx, dword ptr [esp+00000668] ;Indirizzo relativo al serial

00402A30 or esi, FFFFFFFF ;

00402A33 mov edi, edx ;| Metodo molto comune usato per calcolare la lunghezza di una stringa

00402A35 mov ecx, esi ;| in questo caso del nostro serial

00402A37 xor eax, eax ;|

00402A39 mov byte ptr [esp+00000660], 03 ;|

00402A41 repnz ;|

00402A42 scasb ;|

00402A43 not ecx ;|

00402A45 dec ecx ;|

00402A46 cmp ecx, 0000000E ;se il serial è diverso da Eh (cioè 14 chars)

00402A49 jne 00402BB2 ;Salta alla beggar off, sennò continua

00402A4F xor ecx, ecx

00402A51 mov al, byte ptr [ecx+edx] ;char relativo al serial

00402A54 cmp al, 30

00402A56 jl 00402BB2 ;Salta alla beggar off, se è più piccolo di 30, cioè 0

00402A5C cmp al, 39

00402A5E jg 00402BB2 ;Salta alla beggar off, se è più grande di 39 cioè 9

00402A64 inc ecx ;Incrementa il contatore

00402A65 cmp ecx, 0000000E

00402A68 jl 00402A51 ;Se è più piccolo di Eh, vai al prossimo ciclo

Adesso soffermiamoci per a fare qualche considerazione. All' inizio viene preso il serial, invece che il name, e questo dovrebbe farci un pò pensare, perchè se quello che viene manipolato è il serial, allora dobbiamo prepararci all' analisi dell' algoritmo.In questo caso fortunatamente sappiamo per certo che si tratta di rsa, e la cosa ci avvantaggia molto. Poi notiamo anche la presenza di quattro numeri fissi, che ci fa pensare (intuitivamente) a E ed N. Vi ricordo la formula:

C=M^e mod n

Inoltre a 00402a51 che inizia una routine che controlla se il seral inserito sia un numero, se non lo è salta ad errore. Da questo ciclo capiamo anche che bisogna lavorare (operazioni di fattorizzazione e varie) in base 10. Arrivati a questo punto, è meglio se tralasciamo l' analisi della routine che segue, poichè è abbastanza lunga ed ingarbugliata. Cercherò quaindi di riassumervi un pò cosa succede:

-Il serial dev' essere di 14 cifre, e poi durante l' algoritmo questo numero verrà "spezzato" in due parti uguali composte da 7 cifre. Ad ognuno di questi "pezzi" di serial saranno applicate una seria di operazioni, che coinvolgono anche in numeri visti sopra (9901 e 12790891). Alla fine, le due parti di serial vengono riunite e poi avviene il check finale, che ci dirà se il serial è giusto o sbagliato. Dalle operazioni che vengono fatte, possiamo capire che 12790891 rappresenta il modulo N e che 9901 E. Adesso ci tocca riuscire a decriptare le due parti di serial. Seguendo la routine, si può notare inoltre che i valori: 5666933 e 8483678, sono le due parti di serial corretto, ma purtroppo sono criptati. Inoltre se avete notato entrambi i valori sono di 7 cifre ciascuno il che dovrebbe insospettirci. Quindi arrivati a questo punto, facciamoci uno schema della situazione e vediamo cosa possiamo fare:

-Conosciamo il seriale corretto ma criptato, cioè conosciamo il parametro C.

-Conosciamo il modulo N con cui sono stati criptati i due valori.

-Conosciamo E (Con E e con P e Q si può trovare il parametro D).

Abbiamo tutto per un corretto decripting, ma dirvi soltanto quale bottoni premere non sarebbe utile a nulla. Quindi cerchiamo di arrivare alla soluzione: per poter decriptare i due spezzoni di serial dobbiamo avere oltre al messaggio criptato (C) , il modulo N ed D. Se vi ricordate N è dato da P*Q che sono due numeri primi, quindi fattorizzandolo dovremmo riuscire a trovare P e Q (2 numeri in questo caso relativamente piccoli). Aprite RsaTool2, ed impostatelo a base 10, dato che come abbiamo precendente visto i valori sono tutti in base 10. Scrivete nell' edit box "Modulus N" e fattorizzatelo "Factor N", il programma vi dirà che questo numero è primo, questo significa che non può essere il modulo N (che dovrebbe essere composto dal prodotto di due numeri primi), però dato che è primo può essere il nostro Esponete Pubblico E. Ora proviamo a fattorizzare 12790891, e da cui otteniamo P (1667) e Q( 7673).. A questo punto dato che abbiamo P, Q e l' esponete pubblico E, possiamo calcolarci la chaive di decripto D, che dipende dalla seguente formula:

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

RsaTool2 ci permette anche di calcolarci D, ricordatevi di mettere 9901 in Public Exp, e poi premete "Calc D". Il valore di D sarà 10961333, adesso abbiamo tutti gli elementi per poter applicare la formula:

M=C^d mod n

Non sognatevi nemmeno di usare la calcolatrice di windows, esistono dei programmi apposta per poter decriptare un numero. Vi consiglio di non effettuare il decripting su un computer lento, ci vorrrebbe molto tempo. Questi sono i valori da usare per il decrypt:

M1=(8483678^10961333) mod 12790891

M2=(5666933^10961333) mod 12790891

Da cui si ottiene:

M1=7167622

M2=3196885

Queste sono le due parti di serial decriptatato, se ricordate, l' algoritmo richiedeva un serial di 14 cifre e successivamente veniva diviso in due, M1 ed M2 rappresentano i 2 pezzi di serial. Quindi per ottenere il seriale corretto M1M2, vanno uniti. Il valore così ottenuto sarà 71676223196885.

Riconoscere l' Rsa.

Riconoscere l' Rsa negli schemi di protezione, non è molto semplice, poichè può presentarsi sotto numerose forme, o peggio può essere "riadattato". Ma ho pensato di elencarvi in modo molto generico le principali caratteristiche che *dovrebbe* avere:

-Viene preso il seriale e viene criptato, solitamente con la formula C=(M^E) mod N, (M non è altro che il serial).

-Di conseguenza dovremo avere 2 valori fissi, che rappresentano il modulo N e l' esponente pubblico E.

-Poi dovrebbe avvenire un confronto tra il serial criptato ed il nome.

Adesso voglio riportarvi un spezzone di codice preso da un crackme, che potrebbe chiarirvi un pò le idee.

0040118D sub_40118D proc near

0040118D mov ebx, eax ;In eax abbiamo il nostro serial, che ora vine messo in ebx

0040118F mov ecx, dword_4030A8 ;in ecx viene messo un valore fisso

00401195 mov esi, dword_4030A4 ; in esi viene messo un altro valore fisso

0040119B mov eax, 1 ; mette 1 in eax

004011A0 loc_4011A0:

004011A0 cdq ;ConvertDoubleToQuad, si prepara ad un divisione

04011A1 mul ebx ; Moltiplica ebx per eax

004011A3 div esi ;divide esi per eax (in esi si trova uno dei valori fissi)

004011A5 mov eax, edx ;Sposta il resto della divisione in edx

004011A7 loop loc_4011A0 ; mette in loop queste operazioni, questo ciclo sarà ripetuto 1109 volte, dato che ecx contiene proprio 1109!

dopo abbiamo un confronto tra il serial corretto ed il seriale inserito da noi e criptato.

VALORI:

004030A4= 0EAD2C511h cioè 3939681553

004030A8=455h cioè 1109

La routine è abbastanza semplice, in ebx abbiamo il serial inserito da noi, il quale viene moltiplicato per eax (che la prima volta contiene 1) e poi viene diviso per esi (in esi abbiamo il valore 3939681553). Poi viene preso il resto della divisione (quindi possiamo considerarlo come un MOD!!!) e spostato in eax, tutte queste operazioni vengono ripetute 1109 volte!. Ormai avreste già dovuto capire di che operazione si tratta, ma comunque vediamo un pò analiticamete cosa avviene:

eax=eax * ebx

dato che viene iterato per 1109 volte equivale a:

eax=(ebx ^ 1109)

di seguito abbiamo eax = eax / esi , ma poichè viene preso solo il resto può essere considerato come:

eax MOD esi (da ricordare che esi è 3939681553)

Quindi da tutto questo si ricava che, C=(Seriale ^ 1109) MOD 3939681553

Bene! abbiamo finito, ho cercato di scrivere qualcosa di sintetico e completo allo stesso tempo, spero di esserci riuscito. Nei vari schemi di protezione l' Rsa si può presentare in modo molto vario, noi abbiamo esaminato solo uno dei casi più semplici. La prossima volta (se ho tempo) scriverò qualcosa su come viene usato l' rsa a 128, 256 e 512 bit.

References:

-Cenni di Aritmetica Superiore per la Crittologia, di Marco Frigerio

-Vari docs letti in giro.

In fine vorrei porgere i miei più cari saluti a chi mi ha insegnato qualcosa e chi mi ha aiutato a capire, o più semplicemente alle persone con le quali ho passato delle ore piacevoli.

Noi reversiamo al solo scopo informativo e di miglioramento del linguaggio Assembly .

Capitoooooooo????? Bhè credo di si ;))))