Reversing e Analisi BrainTeaser di Spider

Reversing e Analisi BrainTeaser di Spider
Data	by "T4N4T0S"
gg/mese/aaaa	UIC's Home Page	Published by Quequero
La teoria è quando si sa tutto e niente funziona. La pratica è quando tutto funziona e nessuno sa il perché. In questo caso, abbiamo messo insieme la teoria e la pratica: non c'è niente che funziona... e nessuno sa il perché! Albert Einstein	Qualche mio eventuale commento sul tutorial :)))	Il reversing e come il vento e come il vento non si puo’ fermare
....	Home page: http://www.pilusci.org E-mail: tanatos@pilusci.org T4N4T0S, #crack-it	....
Difficoltà	(R)NewBies (S)Intermedio ( )Avanzato ( )Master

Dunque dovremmo trovare un seriale attraverso lo studio di un algoritmo matematico
(Leggenda Difficolta’: R = Reversing, S = Trovare il seriale)

Reversing e Analisi del BrainTeaser di Spider

Written by T4N4T0S

Introduzione

Bene signori, inanzitutto grazie per avermi dedicato 5 minuti (spero di + ;-P).

Il nostro lavoro oggi, sara' pressoche' simile al lavoro di un crittanalista in quanto il reversing del programma non sara' certo difficile ma l'algoritmo di

controllo è un vero rompicapo matematico.

Tools usati

Ida Pro

SoftIce

Calcolatrice esadecimale (quella di windows va bene)
Rsa Tool 2

URL o FTP del programma

http://quequero.org/crackme/filez/braintsr.zip

Notizie sul programma

Questo programma è il risultato di un problema che Spider ha risolto tempo fa ulteriormente complicato

Cmq nell’allegato c’è il leggimi.txt.

Essay

Mini Indice:

I. Reversing e soluzione(accetatela per il momento come Dogma di Fede ;-P)

II. Matematica delle sommatorie

I. Reversing e soluzione(accetatela per il momento come Dogma di Fede ;-P)

Leggendo il txt allegato mi è caduto subito l'occhio sul consiglio di evitare il bruteforcing poiche' come vedremo il nostro caro Spider ha implementato un codice lentissimo e dopo una analisi piu' approfondita capiremo anche il perche'.

Allora facciamo partire il programma clikkiamo su help, su registra, ecco la nostra dialog box immettiamo un seriale a caso e appare una bella messagebox che ci dice praticamente che siamo delle cippe in matematica.

Ok mano all'ida e disassembliamolo, pochi secondi e tutto e pronto.

Nella string reference diamo una veloce lettura e troviamo un paio di stringhe interessanti, compresa quel simpatico ammonimento quindi doppioclick sulla stringa di errore ("Non provare a casaccio :P")

.text:004011CA loc_4011CA:

.text:004011CA call sub_40122B

.text:004011CF jz short loc_4011EB

.text:004011D1 inc eax

.text:004011D2 dec ecx

.text:004011D3 jnz short loc_4011CA

.text:004011D5 push 30h ; uType

.text:004011D7 push offset aWhatABeautiful ; lpCaption

.text:004011DC push offset aComplimentiRev ; lpText

.text:004011E1 push [ebp+hWnd] ; hWnd

.text:004011E4 call MessageBoxA

.text:004011E9 jmp short loc_401215

.text:004011EB ; ---------------------------------------------------------------------------

.text:004011EB

.text:004011EB loc_4011EB:

.text:004011EB push 30h ; uType

.text:004011ED push offset aBrainless ; lpCaption

.text:004011F2 push offset aNonProvareACas ; lpText

.text:004011F7 push [ebp+hWnd] ; hWnd

.text:004011FA call MessageBoxA

.text:004011FF jmp short loc_401221

Salendo un po' si puo' leggere una cosa interessante:

.text:00401117 loc_401117:

.text:00401117 cmp [ebp+arg_4], 111h

.text:0040111E jnz loc_401217

.text:00401124 mov eax, [ebp+arg_8]

.text:00401127 cmp ax, 1

.text:0040112B jnz loc_401201

.text:00401131 push 0 ; bSigned

.text:00401133 push 0 ; lpTranslated

.text:00401135 push 3E8h ; nIDDlgItem

.text:0040113A push [ebp+hWnd] ; hDlg

.text:0040113D call GetDlgItemInt

Una chiamata a GetDlgItemInt, vediamo che fa

UINT GetDlgItemInt(

HWND hDlg, // handle to dialog box

int nIDDlgItem, // control identifier

BOOL *lpTranslated, // points to variable to receive success/failure indicator

BOOL bSigned // specifies whether value is signed or unsigned

);

Praticamente legge dalla editbox "int nIDDlgItem", ad uno a uno i caratteri della edit box si ferma se il carattere è diverso da un numero e mette in eax il valore convertito ad intero (gli ultimi 2 parametri vengono solitamente lasciati a zero (sono entrambi putatori a bit). Ok qua inizia la nostra procedura, continuiamo....

Da questo punto abbiamo il seriale in eax.

.text:00401142 cmp eax, 100

.text:00401145 jb Errore

.text:0040114B cmp eax, 30000000

.text:00401150 ja Errore

Il valore preso deve essere + grande di 100 e piu' piccolo di 30.000.000, cioe' rimangono 29.999.901 (gli stremi sono compresi) possibili chiavi.

Proviamo a vedere questo algoritmo quanto tempo macchina utilizza per criptare e confrontare il + grande numero e il piu' piccolo inseribile.

Addirittura 6 secondi sul mio celeron 700 e istantaneamente il piu' piccolo.

Non vi sto ad annoiare con i conti ma ci impiegherebbe circa ......... tanto tempo

.text:00401156 push eax ; Mette nello stack eax

Ricordiamocelo :-PPP

Allora ricapitoliamo prende un intero vede se è compreso tra 100 e 30 Milioni e lo pusha nello stack. Tenete presente che un qualsiasi numero puo' essere sempre espresso come somma tra un quadrato e un altro numero.

Se chiamo N = seriale e n = int(seriale^0.5) ; Vedremo in seguito

I-------------------------------------------------------------------------------I

I Rifletteteci è fondamentale che abbiate pienamente compreso il significato di I

I "Intero della radice quadrata di seriale", continuate a leggere se non capite I

I ritornate qui' I

I-------------------------------------------------------------------------------I

Allora N= n^2 + d

dove d è la "distanza" tra N e il primo quadrato perfetto minore di N.

Esempio)

N = n^2 + d

12345 = (111)^2 + 24

Rapidamente per calcolare n si fa la radice quadrata si prende la parte intera e la si sottrae al seriale

Qunque ora che abbiamo l'algoritmo analizziamolo

.text:00401157 finit

.text:0040115A fstcw word_4030A0

.text:00401161 and word_4030A0, 3FFh

.text:0040116A or word_4030A0, 0C00h

.text:00401173 fldcw word_4030A0

Allora quando viene inizializzata la fpu,lui esegue queste operazioni

FPUControlWord <--- 037Fh

FPUStatusWord <--- 0

FPUTagWord <--- FFFFh

FPUDataPointer <--- 0

FPUIstructionPointer <--- 0

FPULastInstructionOpcode <--- 0

Quello che ci interessa è la prima poiche fstcw non fa niente altro che salvare la Controlword in memoria (esattamente qui' word_4030A0, nel nostro caso) gli fa un AND con 3ffh e poi un OR con 0c00h. Se vi fidate fa esattamente xxxx1111xx111111 dove x indica un bit non utilizzato.

Per i piu' sfaticati:

0000|0011|0111|1111 037f (word_4030A0)

0000|0011|1111|1111 03ff

------------------- AND

0000|0011|0111|1111 037F

0000|1100|0000|0000 0C00

------------------- OR

0000|1111|0111|1111 0F7F

Questo risultato lo salva nella ControlWord

Se andate a leggervi The Intel Basic Architeture I, praticamente scoprirete che non fa niente altro che lasciare tutto inalterato mettendo pero' il round control (tipo di arrotondomento) su Trunched (11, brutalmente troncato).

Fate prima pero' se andate a leggere quest'indirizzo

http://webster.cs.ucr.edu/Page_AoALinux/HTML/RealArithmetic.html#1000010

.text:00401179 mov ebx, offset unk_4030A4 ; Punta ebx ad una loc di memoria vuota

.text:0040117E mov [ebx], eax ; Muove il seriale (n^2+d) in ebx

.text:00401180 fild dword ptr [ebx] ; Lo carica nel FPU Stack

.text:00401182 ; Fa la ridice quadrata intera di ST(0) cioe del TOS del FPU STACK

.text:00401182 fsqrt ; Cioe' intero(n^2+d)^0.5 = ????? A quanto è uguale

.text:00401182 ; A n (se non capisci prova con dei numeri :)

.text:00401184 fistp dword ptr [ebx] ; lo carica in ebx [ebx] = n

.text:00401186 mov eax, [ebx] ; Lo mette in eax eax = n

.text:00401188 inc eax ; eax = n+1

.text:00401189 mul eax ; eax = (n+1)^2

.text:0040118B xor edx, edx ; edx = 0

.text:0040118D inc edx ; edx = 1

.text:0040118E push eax ; lo mette nello stack

Prende il seriale gli fa la radice quadrata (troncata) lo eleva al quadrato e lo pusha (vi ricordo che nello stack era stato prima pushato il seriale).

Quindi nello stack nell'ordine di "pop" c'è (n+1)^2 n^2+d

Ora arrivano un paio di sommatorie che mi hanno dato un bel po' da pensare

I-------->.text:0040118F loc_40118F:

I .text:0040118F pop dword ptr [ebx] ; caccia il primo valore dallo stack e lo mette in [ebx]

I .text:00401191 fldz ; pusha zero (+0.0) nello FPUStack

I .text:00401193

I I----->.text:00401193 loc_401193:

I I .text:00401193 fild dword ptr [ebx] ; Pusha nell FpuStack ebx (ebx = (n+1)^2)

I I .text:00401195 fsqrt ; radice quadrata intera (n+1)

I I .text:00401197 frndint ; Operazione inutile in quanto CW ha il round su trunched

I I .text:00401199 ; Somma i due valori nello stack

I I .text:00401199 faddp st(1), st ; Li mette in St(1)

I I .text:00401199 ; Poppa (praticamente la somma si trova in st(0)

I I .text:0040119B dec dword ptr [ebx] ; decrementa (n+1)^2

I -------.text:0040119D jnz short loc_401193 ; e ripete il ciclo (per n+1)^2 volte

I .text:0040119F

I .text:0040119F dec edx

I---------.text:004011A0 jns short loc_40118F

Le ultime due righe di codice non le ho commentate perchè vi volevo fare vedere lo snapshot del FPU stack nei vari passaggi del primo loop

I-------------I I-------------I I-------------I I-------------I

I I I I I I I I

I I I-------------I I-------------I I-------------I

I I I +0.0 I I +0.0 I I I

I-------------I I-------------I I-------------I I-------------I

I +0.0 I I (n+1)^2 I I (n+1) I I (n+1)+0.0 I

I-------------I I-------------I I-------------I I-------------I

Poi esegue il loop.

Secondo giro

I-------------I I-------------I I-------------I I-------------I

I I I I I I I I

I-------------I I-------------I I-------------I I-------------I

I I I (n+1) I I (n+1) I I I

I-------------I I-------------I I-------------I I-------------I

I (n+1)+0.0 I I (n+1)^2 -1 I I (n) I I (n+1)+n I

I-------------I I-------------I I-------------I I-------------I

Adesso scrivo una formula un po' brutta (E = simbolo di sommatoria)

(n+1)^2+2

K1= E intero(n+1)^(1/2^i-1) ; Nota bene la formula non è precisissima, tanto non serve poi vi spiego

i=2

Poi esegue un altro giro (edx = 1, lo decrementa, edx = 0, ZF=1, SF=0) salta perche' SF=0, al giro dopo edx = ffffffff SF=1

Loop esterno

.text:0040118F pop dword ptr [ebx] ; caccia il secondo valore dallo stack e lo mette in [ebx]

.text:00401191 fldz ; pusha zero (+0.0) nello FPUStack

Snapshot del registro

I-------------I

I I

I-------------I

I K1 I Prima sommatoria

I-------------I

I +0.0 I

I-------------I

Alla fine del loop esterno ci troviamo in questa situazione

I-------------I

I I

I-------------I

I K1 I Prima sommatoria

I-------------I

I K2 I Seconda sommatoria

I-------------I

(n^2+d) +2

K2= E intero(n^2+d)^(1/2^i-1) ; Nota bene la formula non è precisissima,

i=2 ; tanto non serve poi vi spiego

.text:004011A2 fsubp st(1), st

.text:004011A4 fistp dword ptr [ebx]

Esegue le differenze e la mette in [ebx]

Vi stare di dicendo "Porca pupazza non ho capito un cavolino ?!?!?!??!?!", lo so sono poco chiaro, ma della matematica alla base ne parlemo dopo.

Diciamo che dato un seriale il risultato della diff delle sommatorie è

K(seriale)=K(n^2 + d) = 2n^2 + (1-d)n +1

Esempio)

k(59877)= k(111^2 + 24) = 2*(111^2) + (1-24) + 1 = 12299

Verificatelo reversando il BrainTeaser con il softice (non lo sapete fare????? Ma non dite fesserie lo so fare io, lo sapete fare anche voi :-P)

.text:004011A6 mov eax, [ebx]

.text:004011A8 sub eax, 0EC5h

.text:004011AD lea ebx, [eax+1]

Prende il seriale gli sottrae 3781 e lo mette in eax, e mette in ebx questo valore + 1

.text:004011B0 call sub_40122B

Questa call non fa niente altro che vedere se in eax c'è un quadrato perfetto e setta Z=1 altrimenti Z=0

.text:004011B5 jnz short Errore

In eax c'e' un quadrato perfetto, Si continua, No salta

.text:004011B7 add eax, 2559h

Aggiunge a eax 9561

.text:004011BC call sub_40122B

.text:004011C1 jnz short Errore

In eax c'e' un quadrato perfetto, Si continua, No salta. Prima di passare alla funzione successiva analizziamo i dati

K(n^2+d) - b1 = q^2 = q*q Questa differenza deve fare un quadrato perfetto

Q^2 +b2 = p^2 Questa somma deve fare un quadrato perfetto

La successiva funzione verifica che tra Q^2 e Q^2+(b2-1) non ci siano quadrati perfetti.

Questa funzione devo dire che ha permesso al programma di non essere bruteforzato in quanto ci dice che p^2 = (q+1)^2, equazione indispensabile per la risoluzione del problema

Bene abbiamo tutto, dopo quest'ultima funzione infatti c'è l'agognata Messagebox

Ok ora è questione di conti

b2 = (q+1)^2 - q^2

svolgendo

b2 = q^2 - q^2 +2q +1

b2 - 1 9561 -1

q= --------- = ---------- = 4780

2 2

K(n^2+d) = q^2 + b1 = 4780^2 + 3781 = 22852181

Bene noi sappiamo che

K(n^2+d) = 22852181 = 2n^2 + (1-d)n +1

Cioe'

22852180 - 2n^2

--------------- = 1-d

Quindi:

22852180

---------- -2n = 1-d

Allora adesso abbiamo un problema dobbiamo trovare un n che divide 22852180 in maniera precisa (come sono belli gli interi).

Facciamo un paio di considerazioni:

Il massimo numero (30 milioni si puo' esprimere come)

30 Milioni = (5477)^2 + 2741

Allora n deve essere minore di questo valore (ho cmq trovato un n > 5477 che fa funzionare tutto se non fosse per i secondo cmp ;-P)

Ottimo prendiamo Rsa Tool 2, se ve lo volete fattorizzare a mano fate pure e buon lavoro :-P.

Facciamo partire e facciamo lavorare con i decimali (number base in alto a destra = 10) Mettiamo 22852180 in Modulus (N) e premiamo su fact N e vedremo che questo valore è il prodotto di

2^2 * 5 * 13 ^ 2 * 6761 = 3380 *6761

U la la ... adesso sappiamo che n o è 3380 o 6761 (potrebbe essere anche un altro qualsiasi fattore ma è evidente che otterremmo un d troppo alto), e non puo' essere 6761 perchè > 5477. Proviamo a mettere 3380 nella formula e otteniamo

22852180

---------- - 2*3380 = 1-d ===> 6761 - 6760 = 1 - d ====> d=0

3380

Allora il nostro seriale è un numero quadrato, con n = 3380

Seriale allora è 3380^2 = 11424400

Mettiamo nella Box di registrazione aspettiamo un paio di secondi e TA TA ecco la vostra message box di congratulazioni, infatti

K(seriale)= K(11424400)=K(3380^2 + 0) = 2*(3380)^2 + (1-0)3380 +1 = 22852181

II. Matematica delle sommatorie

Bene bene bene, siamo dunque arrivati alla parte piu' complicata del brainteaser, ma noi non ci scoraggiamo.

Prime considerazioni

Quanti numeri ci sono tra 2 quadrati perfetti successivi?

Beh come sappiamo 2 quadrati perfetti successivi matematicamente si scrivono cosi:

q^2 E (q+1)^2 e la loro differenza dunque è:

(q+1)^2 - q^2 ========> q^2 + 2q +1 - q^2

svolgendo

Risultato: 2q +1 (che matematicamente per i meno esperti è l'espressione di un numero dispari)

Esempio

q= 10; q+1 = 11; q^2 = 100 ; (q+1)^2 = 121

Quindi

121 - 100 = 21 = 2*(10) +1

e se volessi sapere (n^2 + d) e (n+1)^2 ???

/ \

---

(vi ricordate vero come si esprimeva il seriale in funzione della radice intera + distanza)

svolgendo viene:

n^2 + 2n +1 - n^2 - d ==========>>>> 2n -d +1

Bene ora è giunto il momento di fare un paio di conti veri.

Dal codice che abbiamo visto lui esegue un certo numero di cicli, la prima volta, ne esegue (n+1)^2 la seconda

n^2+d, bene vediamo che significa

N= 100; n = 10; n+1=11; (n+1)^2 = 121