Ecco un tentativo di soluzione del 6° corso di Quequero. Dico tentativo perchè la soluzione sarebbe impossibile, almeno stando alle regole: NIENTE PATCHING. Qui abbiamo un chiaro esempio di algoritmo irreversibile, semplice ma letale. L'unico attacco possibile è un brute force. Il crackme si trasforma quindi nella ricerca di un modo per trovare il minor numero di combinazioni possibili.

Soluzione al 6° Corso di Queqeuro
Mamma, che vuol dire Brute Force?
Written by AndreaGeddon

 

Io ho classificato il crackme come intermedio nel suo insieme. A livello di codice sarebbe un Newbie, a livello di soluzione sarebbe un Avanzato. Bohh.. Fate voi. A livello di codice in realtà è per ragazzini delle elementari...è questo il bello della crittografia :) NdQue

Lo scopo principale di questo tutorial è quello di scrivere un brute force che provi il minor numero di combinazioni possibili, ed è quello che ho fatto.

-  SoftIce

-  WinDASM

La bambolina Voodoo (non la scheda video) che ci permetterà di sfogare le nostre frustrazioni!

http://linox.tecnoprogress.it/quequero/prj/corsosei.html

Lo trovate nella sezione Lezioni del sito di Quequero

Solo un seriale fisso. Solo.

Bene. Vi riporto il codice completo della routine di crittazione/confronto del seriale. Sono solo tre paginette, quindi vi conviene stamparlo ed averlo sempre sotto gli occhi quando leggete questo tute e quando debuggate. Trovare il serial in modo semplice, cioè ricalcolandolo a ritroso è impossibile. L'unica via che rimane è quella del brute force. Più giù riporto anche il codice completo del brute force che ho scritto, perfettamente funzionante. Intanto iniziate l'analisi del codice.

Prima di iniziare dichiariamo un pò di termini:

userò la parola SERIAL per indicare il seriale inserito da NOI

userò la parola IRREV per indicare il valore di irreversibilità (00401479)

userò la parola CRITT per indicare il serial giusto crittato

userò la parola DWORD per indicare le varie DWORD del serial

così mi risparmio un pò di scrittura :-)

:00401263 Call 004014C5 USER32.GetWindowTextA  --> Questa sarà la PRIMA ROUTINE

:0040126D imul eax, 93572678                       |

:00401273 mov  ebx, dword ptr [004020D0]           |---> 2° DWORD

:00401279 imul ebx, 26547305                       |

:0040127F mov  ecx, dword ptr [004020D4]           |---> 3° DWORD

:00401285 imul ecx, 37569814                       |

:00401291 imul edx, 89653715                       |         tutta questa routine

:00401297 add  eax, ebx                             |        serve a determinare

:00401299 add  eax, ecx                             |        il valore di IRREV

:0040129B add  eax, edx                             |        che poi sarà salvato

:0040129D push eax                                  |        nella locazione

:0040129E mov  dword ptr [0040145D], eax            |        00401479

:004012A3 xor  eax, eax                             |

:004012A5 mov  eax, dword ptr [004020CC]            |

:004012AA add  eax, dword ptr [004020D0]            |

:004012B0 mov  dword ptr [00401461], eax            |

:004012B5 mov  eax, dword ptr [004020D4]            |

:004012BA add  eax, dword ptr [004020D8]            |

:004012C0 mov  dword ptr [00401475], eax            |

:004012C5 mov  eax, dword ptr [00401461]            |

:004012CA dec  eax                                  |

:004012CB mov  ebx, dword ptr [00401475]            |

:004012D1 dec  dword ptr [00401475]                 |

:004012D7 imul eax, ebx                             |

:004012DA mov  dword ptr [00401479], eax            |----> salva IRREV

:004012DF call 004012E9                             |

:004012E4 Call 00401495 KERNEL32.ExitProcess        |--> qui si esce dal prog

* Referenced by a CALL at Address: 004012DF        |--> Questa è la SECONDA ROUTINE

:004012E9 cmp  eax, FFFFFFFF                       |

:004012EC jg   004012F4                            |

:004012EE nop                                      |

:004012EF nop                                      |

:0040134B neg  dword ptr [00401479]                 |

:00401351 call 00401357                             |

:00401356 ret                                       |

* Referenced by a CALL at Addresses: 00401361 :00401380 :0040139F :004013BE

* Referenced by a CALL at Addresses: 0040135C :0040137B :0040139A :004013B9

* Referenced by a CALL at Address: 004013D3

:00401457 Call 004014E3 USER32.MessageBoxA Serial Giusto

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

|:00401413(C), :00401423(C), :00401433(C), :00401443(C)

:0040148B Call 004014E3 USER32.MessageBoxA Serial Errato

:00401490 Call 00401495 KERNEL32.ExitProcess

Okay, abbiamo il codice. Dobbiamo trovare il seriale. Partiamo dai compare finali. Abbiamo i valori critt1 critt2 critt3 e critt4. Dobbiamo partire da questi. Innanzitutto, dal codice è evidente che il serial viene considerato come 4 dword. Soprattutto nella routine terza vediamo che la crittazione e successivamente il confronto avvengono proprio una dword alla volta. La prima cosa che si può fare è tentare di calcolarci all'indietro le 4 dword partendo dai valori critt. Ci troviamo subito in difficoltà perchè compare il riferimento al valore 00401479. Questo valore viene generato nella prima routine a partire proprio dal serial inserito. Siccome non conosciamo il serial inserito, non possiamo conoscere questo valore. E' per questo che lo chiamo irrev, perchè è il valore che assicura l'irreversibilità dell'algoritmo. Come procedere? Studiando bene il codice, mi sono tristemente ritrovato di fronte all'unica soluzione possibile: il brute force.

Per chi non lo sapesse il Brute Force è la tecnica usata per forzare tutte le combinazioni. Cioè, siccome noi non possiamo calcolarci il serial in modo matematico, ricorriamo al modo probabilistico e iniziamo a provare dalla prima all'ultima tutte le varie combinazioni possibili. Sappiamo che il serial deve essere di 16 char. Male! Non possiamo prendere e provare tutte le combinazioni perchè ci vorrebbe troppo tempo. Facciamo due conti:

Partiamo vedendo cosa succede se proviamo tutte le possibili combinazioni. Abbiamo 16 caratteri in tutto. Ogni carattere è un byte. Ogni byte sono 256 combinazioni. Ognuno dei 16 char può in teoria assumere 256 combinazioni. Le combinazioni totali saranno:

256^16 = 3,4028236692093846346337460743177e+38    (il simbolo ^ sta per elevazione a potenza)

Doh!! Più chiaramente questo significa abbreviato 3,402 * 10^38, cioè un numero di 38 cifre! Questo è il numero TOTALE di combinazioni che si devono provare! Cazzo, sono troppe. Ci vorrebbe troppo tempo. Anche teorizzando una velocità di porva di 1 milione di combinazioni al secondo, ci vorrebbero milioni di anni! Dovete tenere da conto il fatto che l'algoritmo di crittazione è stato create bastardamente lento quindi.....:)

Allora il nostro attacco adesso si basa sul modo di ridurre le combinazioni al minor numero possibile.

Beh, una prima riduzione che si potrebbe fare è questa: consideriamo solo i valori effettivi che un char può assumere. Cioè: non credo che Que abbia utilizzato i caratteri ASCII al di fuori dei 96 comunemente usati, quindi adesso consideriamo un char variabile di 96 combinazioni.

96^16 = 52040292466647269602037015248896  combs

Vaff... Ancora troppe. Che dobbiamo fare per ridurre ulteriormente il codice? Andiamo a studiare meglio l'algo. Que suggeriva di provare con le collisioni. Non essendo un esperto di crittografia, allora non sapevo cosa fossero ste collisioni. Adesso mi sono informato, e praticamente era il metodo che intuitivamente avevo provato a fare. Beh, quello che ho fatto io non sono proprio... collisioni, però gli somigliano. Vi riporto la seguente definizione di collisioni:

"Trovare 2 messaggi che diano lo stesso valore di hash è conosciuto come una collisione ed è exploitabile dal birthday attack. Si tratta di un problema di probabilità statistica preso da un documento del sito di aLT255. Se ne volete sapere di più, andate sul suo sito (http://kz.cjb.net/).

Torniamo a noi. Lo spunto ci viene dal fatto che l'algo tratta il serial come 4 dword diverse. Ci viene quindi in mente che forse possiamo sfruttare questo fatto per ridurre il lavoro su una sola dword invece che su tutto il resto. E così vado a fare. Se analizzate la terza routine, vedete che all'inizio il prog prende il valore irrev e la dword che deve calcolare, le critta, e mette in memoria un valore ottenuto sottraendo il valore crittato alla dword corrispondente. Il problema sarebbe di trovare il valore irrev. Alla terza routine vediamo che il serial entra come lo avevamo inserito solo per la dword2 e la dword4. La 1° e la 3° vengono infatti trasformate da dei ROL nella seconda routine. Il valore irrev usato per le 4 dword è sempre lo stesso. Ora, sebbene il ROL non sia un problema, non potremo utilizzare le dword 1 e 3 per i nostri calcoli. Poi vedremo come risolvere anche questo semplice problemino. Prendiamo in analisi la dword2. Dopo il trattamento di crittazione, viene comparata col valore critt2, che sarebbe 55F2600F. Dobbiamo fare quindi in modo che la dword alla fine del trattamento risulti uguale a critt2. Il problema è che siccome abbiamo questa funzione che è a due variabili, non possiamo esplicitare i calcoli per ottenere un calcolo diretto. Dobbiamo quindi considerare come variabili i due valori DWORD2 e IRREV. Il nostro discorso si può definire come segue: DOBBIAMO TROVARE I VALORI DI DWORD2 e IRREV PER I QUALI IL VALORE CHE ESCE DALLA FUNZIONE DI CRITTAZIONE SIA CRITT2. Abbiamo quindi gli elementi che ci servono, facciamo un paio di calcoli:

le due variabili sono dword2 e irrev. Sono entrambi di 4 byte. Il nostro brute non farà altro che provare tutte le combinazioni di dword2 per tutte le combinazioni di irrev. Essendo entrambe di 4 byte, 1 byte = 256 combs   abbiamo

(256^4)*(256^4) = 18446744073709551616 combs

Sono sempre molte, ma meno di quelle di prima!! Però possiamo ulteriormente ridurre: infatti la variabile irrev non la conosciamo e non possiamo dire nulla, ma la variabile dword2 sappiamo che contiene i secondi 4 char del serial, quindi per ogni char le combinazioni rientrano nel discorso dei 96 caratteri standard che facevo anche prima Anche se è solo un'ipotesti perchè io avrei potuto benissimo usare strani simboli NdQue.

Abbiamo adesso:

(256^4)*(96^4) = 364.791.569.817.010.176  combs

E questo è il minor numero possibile di combinazioni che sono riuscito a trovare.Come vedete all'inizio avevamo teorizzato un numero di combinazioni di 38 cifre, adesso ne stiamo considerando uno di 18 cifre! E' un ottima riduzione. Il problema rimane sempre, però: SONO ANCORA TROPPE!! Teorizzando la velocità di calcolo di 1 milione di combs al secondo, impiegheremmo 11567,4 anni per provarle tutte. Peccato che per allora nessuno di noi sarà più vivo per sapere quale è il risultato! Comunque, è il procedimento quello che conta (diceva sempre così il mio prof di mat alle superiori: ho sempre beccato 4!).

Bene, proviamo tutte le combinazioni. Che succede se troviamo il codice: semplice, mi mandate una mail! Se il crackme si ferma e vi scrive due valori, vuol dire che avete trovato la dword2 e irrev. Quindi avete già i secondi 4 char del serial, ma soprattutto avete IRREV! Con questo infatti potrete ricalcolarvi all'inidietro l'algo, infatti ora avrete una sola variabile (la dword da trovare). Oppure potete riusare il brute usando il valore di irrev trovato come valore di partenza. Sarà quindi questione di pochi secondi e troveremo tutte e 4 le dword. MA NON E' FINITA!!! Vi avevo accennato al problema dei ROL delle dword 1° e 3°. Le dword che avete ottenuto con il calcolo tramite irrev trovato, sono le dword modificate dal ROL. Oh nooo!!! Ancora?? Non disperate! Si tratta di un secondo! Infatti le dword vengono rollate (come le canne) di 5 la prima, di 4 la seconda. Ciò viene effettuato per irrev volte. Il calcolo è facile. O rollate tutto per irrev volte (con ror, però), visto che ora irrev lo conoscete, o fate in quest'altro modo: una simpatica caratteristica di ROL è la Periodicità! Infatti ad intervalli regolari la dword rollata riassume il suo valore originario. ROL dword1 , 5 vuol dire che il periodo del ROL è di 32, e cioè avete 32 possibili posizioni per dword1. E lo stesso vale per dword3, solo che lì avete un ROL 4 con periodo 8,e quindi 8 possibili combinazioni di dword3. Beh, ora o provate tutte le combinazioni (32*8 oohhhh), o provate a naso le combinazioni che diano un serial che abbia senso! Comunque, così avreste risolto!!!

Con questo si conclude l'arrembaggio al 6° corso. Adesso vi posto il brute force che ho scritto.

Scusate se il brute fa schifo, ma l'ho scritto di corsa e quindi non l'ho curato particolarmente!

Sotto vi troverete alcuni commenti sul suo miglioramento.

BEGIN OF CODE

-----------------------------------------------------------------------

; NOTE SULL'INSERIMENTO/LETTURA DEI VALORI
; il serial iniziale va inserito al contrario e viene visualizzato al contrario
; l'irrevers va inserito diritto ma viene visualizzato al contrario
; il final viene visualizzato al contrario e viene inserito diritto

.386                                  ; direttive per il compilatore
.MODEL SMALL
.STACK 200h
.DATA

titolo1        db 13,10,'Brute Forcer per il sesto corso di Quequero',13,10,'$'
titolo2        db 13,10,' Written by AndreaGeddon      ',13,10,'$'
inprova1    db 13,10,'Serial in prova:',13,10,'$'
inprova2    db 13,10,'Irrevers in prova:',13,10,'$'       ; le stringhe di testo che userò nel programma
trovato1    db 13,10,'Il seriale trovato:',13,10,'$'
trovato2    db 13,10,'Irrevers trovato:',13,10,'$'
trovato3    db 13,10,'Final torvato:',13,10,'$'

SERIAL        dd 13,10,'',13,10,'$'          ; Variabile in cui immettere la dword inserita
IRREVERS    dd 13,10,'',13,10,'$'       ; Variabile in cui mettere il valore di irreversibilità
FINAL        dd 13,10,'',13,10,'$'            ; Variabile che ci mostrerà la dword giusta nel
                                                             ; caso venga trovata
.CODE
start:
    mov    ax,@data
    mov    ds,ax                            ; faccio puntare ds al segmento DATA

;TITOLO---------------------------------------------------------------
    mov    dx, OFFSET titolo1
    mov    ah, 9
    int    21h
    mov    dx, OFFSET titolo2
    mov    ah,9
    int    21h
    mov    edi, 000000001h    ; serial iniziale
    mov    [SERIAL], edi
    mov    esi, 000000100h          ; irrevers iniziale
    mov    [IRREVERS], esi

;DISPLAY COMBINAZIONI IN PROVA----------------------------------------
calcoli:
    cmp    edi, 000001000h
    je    trovata
    inc    esi
    mov    [IRREVERS], esi
    mov    edi, 000000001h
   
calcoli2:
    mov    dx, OFFSET inprova1
    mov    ah,9
    int    21h
    mov    [SERIAL], edi
    mov    dx, OFFSET SERIAL
    mov    ah,9
    int    21h
    mov    dx, OFFSET inprova2
    mov    ah,9
    int    21h
    mov    dx, OFFSET IRREVERS
    mov    ah,9
    int    21h

;INIZIO CALCOLI------------------------------------------------------
    push    edi
    mov    eax, edi
    call    proc1                   ; come il crackme, qui chiama la proc1
    call    proc2                   ; e qui chiama la proc2
    sub    edi, ebx
    mov    eax, edi
    cmp    eax, 055F2600Fh    ; confronta se ci abbiamo azzeccato
    je    trovata                        ; se NO, ripeti tutto
    pop    edi
    inc    edi
    jmp    calcoli

trovata:                                     ; in caso la trovassimo...
    push    eax
    mov    dx, OFFSET trovato3             ; display di stringhe e del risultato
    mov    ah,9
    int    21h
    pop    eax
    mov    [FINAL], eax
    mov    dx, OFFSET FINAL
    mov    ah,9
    int    21h
    mov    dx, OFFSET trovato2
    mov    ah,9
    int    21h
    mov    dx, OFFSET IRREVERS
    mov    ah,9
    int    21h
    mov    dx, OFFSET trovato1
    mov    ah,9
    int    21h
    pop    edi
    mov    [SERIAL], edi
    mov    dx, OFFSET SERIAL
    mov    ah,9
    int    21h

;----------TERMINA PROGRAMMA-----------------------------------

mov ah,4ch             ; Dos terminate program
mov al,0                 ; return code = 0
int 21h                    ; termina l'esecuzione


;__________________PROCEDURA PRIMA________________________________________
proc1 proc
    imul    eax,eax          
    cmp    eax, 0FFFFFFFFh
    jg    aaaa
    neg    eax
aaaa:
    ret
proc1 endp
;__________________PROCEDURA SECONDA________________________________________
proc2 proc
    mov    ebx, esi
bbbb:
    sub    ebx, 0000000FFh             ; lentissimo... leggete dopo per vere
    cmp    ebx, 0000000FFh            ; come ottimizzare queste righe
    jg    bbbb
    cdq
    idiv    ebx
    imul    eax, esi
    mov    ebx, eax
    ret
proc2 endp
;_________________________________________________________________________
End start

END OF CODE

DUE PAROLE SUL MIGLIORAMENTO DEL BRUTE

Okay, niente di difficile. Ho copiato le routine del crackme e le ho riscritte con qualche modifica. Il codice è funzionante al 100%. Usate il TASM per compilarlo. L'unico problema è la lentezza. Infatti quando scrissi questo brute ero sotto esame, e così gli dedicai poco tempo. Però raggiunsi il mio obiettivo, che era di scrivere un brute funzionante. Poi visto che comunque le combinazioni sono troppe, non ho più ripreso questo progetto. Comunque vediamo dove doveva essere migliorato.

PROCEDURA SECONDA

In questa procedura viene effettuata una divisione con modulo seguendo il metodo delle sottrazioni successive. Cosa fà? Prende il valore di irreversibilità, gli sottrae di volta in volta il valore FF, fino a che ciò non è più bossibile. Per valori piccoli di IRREVERS questo non è un problema, ma quando il valore di irreversibilità diventa un pò più grande, il programma inizia a perdere anche fino a 3 secondi per questa routine! Beh, aggirarla non è un problema. Praticamente questa routine non fa altro che dividere il valore di irreversibilità e prenderne il modulo. Aritmeticamente sarebbe:

IRREVERS / FF = Risultato intero

Risultato intero * FF = (IRREVERS - MODULO)

IRREVERS - (IRREVERS - MODULO) = MODULO

Ecco un semplice metodo per ottenere il modulo. Così siamo sicuri che il programma effettua sempre 3 operazioni, qualunque sia IRREVERS. Però possiamo ulteriormente ottimizzare il tutto. Infatti, il MODULO è sempre uguale per lo stesso valore di irrevers, quindi siccome IRREVERS cambia solo una volta ogni 96^4 (cioè ogni volta che sono state provate tutte le combinazioni di SERIAL), possiamo fare una routine che calcola il MODULO solo quando viene cambiato il valore IRREVERS, e quindi potremmo eseguire questa routine una volta ogni 96^4 invece che ogni volta. Così risparmiamo un sacco di tempo.

DISPLAY COMBINAZIONI IN PROVA

Anche qui si può ottimizzare. Questo brute scrive sullo schermo tutte le combinazioni che prova. Siccome questa è una operazione che rallenta, sarebbe meglio fare un ciclo che scrive sullo schermo solo una combinazione ogni mille. Anche questo farebbe risparmiare molto tempo.

E sono finite le ottimizzazioni. Come vedete, il brute lo potete fare a vari passi: basta infatti interrompere il brute, ricordarsi gli ultimi valori di SERIAL e di IRREVERS provati, e poi scriverli nel sorgente come valori iniziali. La rottura è che bisogna ricompilare il codice ogni volta, ma si può benissimo aggiungere una routine che chiede da dove iniziare.

Comunque, anche provando il minor numero possibile di combinazioni teorizzato che era (256^4) * (52^4), impiegheremmo circa 995 anni e mezzo! E questo supponendo la velocità di calcolo di 1 milione di combinazioni al secondo (velocità assurda...). Comunque lo scopo di questa soluzione era quello di riuscira a capire come ridurre l'algoritmo. Non escludo che avendo un sistema di calcolo potente con molti porocessori in parallelo (per intenderci i sistemi che usa la NSA), questo crackme sarebbe stato risolto in un pò di giorni.

Se tutto questo vi ha lasciato insoddisfatti, prendete pure la bambolina voodoo di Que e pugnalatela senza pietà! E' colpa sua!! Dehihihi!

Ciauz

AndreaGeddon

Saluto tutti gli amici della mailing list (tutti tutti) con cui ho condiviso questo cracking.

Queste informazioni sono solo a scopo puramente didattico.

 

UIC's page of reverse engineering, scegli dove andare:

Home   Anonimato   Assembly    CrackMe   ContactMe   Forum       
    Iscrizione   Lezioni    Links   NewBies   News   Playstation        
  Tools   Tutorial   Search   UIC Faq

UIC