|
Elgamal study 'n reversing |
||
|
Data |
by Evilcry |
|
|
11/08/2005 |
Published by Quequero |
|
|
Where ones sees a limit |
Grandissimo evil! Ottimo tutorial come al solito, sformattato, chiaro e semplice da capire come nel tuo stile ;p |
the others sees an opporunity |
|
Prepare for what you cannot see, expect the unexpected, a waiting game waiting to see...... |
|
|
|
Difficoltà |
NewBies () Intermedio (X) Avanzato () Master () |
|
|
Introduzione |
|
Tools usati |
|
URL o FTP del programma |
|
Notizie sul programma |
Troverete (crackme + keygen) nell' allegato.
|
Essay |
Elgamal an introduction
L'algoritmo Elgamal appartiene alla categoria di cifrari a chiave asimmetrica applicati alla crittografia a chiave pubblica, cioè a tutta quella categoria di crittosistemi in cui il mittente ed il ricevente del messaggio non devono conoscere la stessa chiave. Infatti usano 2 coppie di chiavi ciascuno: una chiave pubblica ed una privata. A questo genere di cifrari appartiene anche RSA, e da alcune analisi risulta che Elgamal e RSA hanno una sicurezza simile per lunghezze di chiavi equivalenti, ma in termini di velocità Elgamal risulta essere il più lento, ed è quest'ultimo il principale motivo per cui RSA è maggiormente utilizzato. Elgamal basa la sua sicurezza problema di Diffie-Hellman il quale a sua volta basa la propria sicurezza sulla complessità computazionale del calcolo del logaritmo discreto, quindi se riusciamo a risolvere efficientemente il logaritmo discreto, Elgamal potrà essere brekkato facilmente. Per maggior chiarezza ho inserito una piccola spiegazione del logaritmo discreto:
| Problema del logaritmo discreto In aritmetica finita, la potenza di un numero si definisce come: ab = x mod n e come per l'aritmetica ordinaria possiamo stabilire un'operazione inversa rispetto all'esponente, cioè il logaritmo, che nel campo dell'aritmetica finita si definisce come b = loga x mod n Quest'ultimo viene chiamato logaritmo discreto. Se il calcolo della potenza è semplice, il calcolo del logaritmo è computazionalmente molto complesso, può avere più soluzioni o anche nessuna. Ad esempio in un'aritmetica di ordine 7 si avrebbe
perciò se prendiamo il log24 è 2 ma anche 5, non esistono però log23, log25, log26. Anche se non è stato ancora dimostrato, si pensa che la difficoltà computazionale del logaritmo discreto è dello stesso ordine di quella della fattorizzazione. |
Elgamal viene fondamentalmente utilizzato in due campi, quello della cifratura pura e semplice, ed essendo poi un algoritmo a chiave pubblica asimmetrico (come già detto utilizza chiavi diverse per codifica e decodifica), trova applicazione come sistema di firma digitale.
L'algoritmo
La procedura di encrypting/decrypting può essere riassunta in tre fasi:
Generazione dei parametri di dominio (anche chiamati parametri di sistema)
Key Generation
Encrypting/Decrypting (il processo di firma digitale)
Nella prima fase, vengono generati due parametri (detti di dominio) che serviranno alla costruzione delle chiavi:
Viene generato un numero primo p molto grosso (p è scelto molto grosso, per sfruttare, a vantaggio di sicurezza, il problema del logaritmo discreto. Solitamente si raccomanda un modulo di almeno 768 bit)
Viene inizializzato un generatore g, cioè una radice primitiva g modulo p e maggiore di 2 (otteniamo un numero random compreso nell'intervallo [3, p-1] ).
Il generatore appartiene al campo di Galois GF(p), cioè il campo degli interi modulo p, con p numero primo, ma ciò non toglie che il nostro generatore può appartenere ad altri gruppi definiti su altri campi, come i polinomi GF(2m) o il campo dei punti appartenenti a curve ellittiche oppure alle funzioni Lucas (polinomi speciali nel campo intero). E' importante ricordarci del fatto che il nostro generatore può avere varie origini, perchè potremmo avere delle varianti dell'Elgamal stesso.
Passiamo ora alla generazione delle chiavi, operazione strettamente dipendente dai parametri di dominio (p,g):
Viene generato un numero random x, compreso nell'intervallo [2, p - 1]
Si calcola y, come y= gx Mod p
y verrà usato come chiave pubblica mentre x sarà la nostra chiave privata.
Passiamo ora al processo di Firma di un messaggio M :
Viene generato un numero random k compreso nell'intervallo [2, p - 2], in modo che sia relativamente primo con (p -1), ricordo che k sarà relativamente primo se gcd(k,p - 1) = 1
Ottiene a, come a=g^k Mod p
Trova (k-1) (mod p - 1)
Determina b, come b= (M- x * a) * k(-1) (mod p - 1), il segno meno in questo caso è sottrazione modulare in modulo (p - 1)
a e b sono la firma del nostro messaggio M
Siamo alla fase finale, la Verifica della nostra firma, è importante ricordare bene la formula della verifica, perchè molto spesso, è proprio grazie a questa formula che riusciamo a capire se e come è implementanto Elgamal, nel programma che stiamo reversando:
La firma è valida se (ya)(ab) mod (p) = gM mod (p)
Ci potremmo pure limitare a conoscere questa formula, ma siamo qui per imparare e quindi capire, ergo cerchiamo di dimostrare ciò che abbiamo scritto :)
Dato che y ed a si possono scrivere come y = gx e a = g^k, possiamo riscrivere la nostra formula di verifica, in funzione di g:
(g^x)^a * (g^k)^b = g^M = g^(x * a) * g^(k * b) = g^M(mod p)
come vedete ci troviamo di fronte ad una forma esponenziale, e nessuno ci vieta di riscriverla in forma logaritmica:
x * a + k * b = m (mod p - 1)
se adesso andiamo a sostituire alla b, la sua relativa forma esplicita otterremo
x * a + k * (M - (x * a))/ k = M da cui
x * a + (M - x * a) = M
x * a + M - x * a = M
ed infine come per magia M=M :)
Vantaggi/svantaggi nell'uso di Elgamal
Oltre la lentezza (relativa ad RSA) un altro svantaggio di Elgamal è dovuto alla dimensione della firma digitale, che è il doppio della dimensione del modulo (problema che può essere ovviato se adottiamo la variante di Schnorr).
La variante più famosa dell'Elgamal è l'algoritmo di Schnorr, il quale differisce dal nostro algoritmo essenzialmente per l’introduzione di una funzione di hash che associa a ciascun messaggio ed a ciascuna chiave un intero in un intervallo di ampiezza predefinita. Il vantaggio principale che questo algoritmo presenta è la possibilità di scegliere la dimensione della firma selezionando l'intervallo del codominio della funzione di hash.
Elgamal strategies of attack
Come abbiamo precedentemente detto, la sicurezza di Elgamal si basa sul problema del logaritmo discreto, quindi com'è logico intuire, in caso di attacco, la prima prima (e quasi unica) strategia sarà quella di risolvere il logaritmo discreto per determinare alcuni valori incogniti, attraverso i quali potremo successivamente...avere ciò che ci interessa...Come sapete y (la nostra chiave pubblica) è definita come:
y= g^x
dove x è la chiave privata, di conseguenza, se dovessimo "attaccare" una signature, la prima cosa da fare è applicare il problema del logaritmo discreto proprio ad y, per conoscere x. Ottenuta la x possiamo procedere a determinare a e b, per poi esplicitare la formula della signature in base a cosa ci serve.
DLP solving techiques
Alla fine ho aggiunto anche un paragrafetto sulle principali tecniche per risolvere i logaritmi discreti. Attualmente esistono due grosse categorie di algoritmi per la risoluzione dei logaritmi discreti:
Anche se il primo metodo è più veloce del primo, l'algoritmo più usato in questi casi è il metodo Pollard's rho che appartiene alla categoria degli algoritmi per la ricerca di collisioni. Quest'algoritmo produce una lunga serie di numeri che graficamente si rappresentano la lettera greca rho (formata da un cerchietto e da na coda), lo scopo è capire dove il cerchietto s'interseca la coda. Il Pollard's rho method lavora a passi, dove n rappresenta la grandezza del gruppo da risolvere. Altro algoritmo usato per il DLP è il Pohlig-Hellman, leggermente meno performante rispetto al primo.
Elgamal Reversing
Bene!, eccoci arrivati alla parte più interessante, quella incui andremo a reversare un programma che implementa Elgamal. Come target ho scelto il pDriLl's Crypto Keygenme 3. Il crackme implementa il sistema di firma digitale (quindi dobbiamo ricordarci la formula che abbiamo visto prima), e lo fa attraverso l'uso delle librerie MIRACL. Come al solito, mano ad IDA e vediamo di trovare la routine di protezione:
Se la prima edit non è vuota, passa a prelevare i valori contenuti nelle altre due EditBox. Se anche gli altri campi sono validi (non nulli) arriviamo qui:
La routine è abbastanza banale, se il nome che abbiamo inserito è più piccolo di 30 caratteri, lo completa con una serie di asterischi, fino a raggiungere 30 di lunghezza. Ad esempio evilcry diventerà "evilcry***********************" Andiamo avanti con l'analisi:
0040113F mov dword ptr [ebp+238h], 3Ch
Occhio a questa istruzione che ci servirà in seguito, che equivale a scrivere mip->IOBASE=60, serve cioè a stabilire con quale base (nel nostro caso base 60) verranno storati i nostri due serial.
...
Anche questo pezzo di codice è semplice da capire, se conoscete come funzionano le librerie MIRACL, in pratica vengono inizializzati una serie di BigNumber, una particolare struttura adatta a contenere numeri molto grossi, eccone la definizione:
char bytes[24]; } big_num;
Per poter visualizzare il BigNum dobbiamo fare AddressBigNum+0Ch.
Quest'altra semplice routine serve a controllare il formato del primo serial (Seial1) che abbiamo inserito, che può essere composto da numeri e lettere upper/lower case. Lo stesso controllo avviene per il secondo serial (Serial2) e stavolta la routine da 4011E3 a 401228. Se entrambi i seriali rispettano le regole che abbiamo appena visto, possiamo procedere con la prossima routine:
La cosa migliore adesso, è vedere quali sono i cambiamenti in ebp prima e dopo la call senza entrarci ( Zen way docet by Fravia ;)). Notiamo subito che la call altro no fa che ricopiare i nostri serial in base 60 nella variabile BigNum puntata da ebp e successivamente da edx, in altre parole viene usata l'istruzione instr, la quale appartiene al gruppo di funzioni che gestiscono l'Input/Output di MIRACL (mrio1.c se avete voglia di studiarvela meglio)
Come possiamo vedere la call a 4040B0 accetta come argomenti una lunghezza un puntarore ed un big, se andiamo a controllare il manuale MIRACL vediamo che questo corrisponde alla funzione
void bytes_to_big(int len,char *ptr,big x)
Converte cioè una stringa di bytes in BigNum attuando un cambiamento di base (esadecimale nel nostro caso).
Sulla prima call c'è poco da dire, una stringa viene trasformata in BigNum, la seconda funzione invece vediamo che accetta 4 argomenti, 3 big ed un intero. Facendo una piccola ricerca notiamo che l'unica funzione del genere è power, la quale effettua l'elevamento a potenza (nel campo dell'aritmetica modulare sempre) di un BigNum con un intero, nel nostro caso:
Nome ^ 2 mod AC2DB4FEC8C62992DB4F = Risultato1
Il risultato si trova in EBX+0Ch (ricordate AddressBig+0Ch)
004012E6 call Instr
Altre 3 stringhe vengono convertite in BigNum:
Come vedete, questa call sembra essere simile alla power, con l'unica differenza che gli argomenti qui sono tutti Big, andiamo perciò a guardarci il manuale e scopriamo che si tratta della funzione powmod. La powmod funziona essenzialmente come la power, soltanto che l'esponente in questo caso è un Big (vi consiglio di dare un'occhiata a mrpower.c, e studiarvi un pò come funziona, è implementata davvero bene!).
2E0C2DB4FEC8C6299A0C ^ Risultato1 mod B54F430648C6B2A10FFB = Risultato2
0040130A call sub_4034B0
Stesse osservazioni di prima (5 BigNum come argomento di una funzione) e scopriamo immediatamente che si tratta della funzione mad (acronimo di multiply add and divide), alla fine avremo:
(4E0F2ACAD51C4CCDFB51 ^ Serial1) * (Serial1 ^ Serial2) mod B54F430648C6B2A10FFB = Risultato3
E finalmente siamo arrivati all'ultima porzione di codice da analizzare, dopo della quale vi sarà tutto più chiaro
Cominciamo a ragionare su un modello di astrazione più elevato, così il reverse si ridurrà ad una serie di congetture matematiche. Perchè il crackme sia risolto, abbiamo detto che Risultato2 = Risultato3, partendo da questa osservazione esplicitiamo un pò Risultato2 e Risultato3, fino ad ottenere
(4E0F2ACAD51C4CCDFB51 ^ Serial1) * (Serial1 ^ Serial2) mod B54F430648C6B2A10FFB = 2E0C2DB4FEC8C6299A0C ^ (Nome ^ 2 mod AC2DB4FEC8C62992DB4F) mod B54F430648C6B2A10FFB
e già questa forma dovrebbe ricordarvi qualcosa..passiamo adesso a rinominare i BigNum che compaiono nella nostra formula
Riscriviamo ancora una volta la formula che ci siamo ricavati ed otteniamo..
(y^a)(a^b) mod (p) = g^M mod (p)
è proprio la signature di Elgamal! :)
Le nostre incognite sono a e b, definite come
a= g^k mod (p)
b= M=(xa+kb) mod (p-1)
Ci serve la x, che possiamo ricavare dalla y (definita come y=g^x mod p), risolvendone il logaritmo discreto. Fra i link utili all'inizio, vi ho postato quello di un DLP solver, inserita la nostra y, il risultato che ci verrà restituito sarà proprio la x che cercavamo:
x= 299376145767585197811667 in esadecimale -> 3F6536A02CD18F3B67D3
Se facciamo attenzione, notiamo che per avere a ci manca ancora una cosa, la k, che però essendo un numero random lo potremo scegliere a nostra discrezione. La scelta più logica è usare k=1 ...e mi pare :). Infine per conoscere Serial2
Serial2= M-x*serial1 mod (p-1)
Non ci resta che convertire Serial1 e Serial2 in base 60 ed il gioco è fatto :)
Come avete visto, il problema del logaritmo discreto gioca un ruolo chiave nella sicurezza di Elgamal, e quello che abbiamo fatto noi, trovando i due Serial, è un attacco crittografico ad Elgamal in piena regola, dove abbiamo sfruttato il fatto che i parametri usati dal crackme erano piccoli, tanto da poter giustificare la risoluzione del logaritmo discreto.
Note finali |
Salutoni a: Quequero, AndreaGeddon, Ironspark, LonelyWolf, ZaiRoN,Littleluk ,Ntoskrnl. Anticrack: Bon_Scott, Zero, Hell_Master, bLaCk-eye, Stanley_White
Disclaimer |
Noi reversiamo al solo scopo informativo e di miglioramento del linguaggio Assembly.
Capitoooooooo????? Bhè credo di si ;))))