Blowfish study 'n reverse

Written by Evilcry.

In questo tutorial, studieremo il sistema di cifratura Blowfish. Ne studieremo il funzionamento e le eventuali debolezze. Ovviamente vedremo il Blowfish non solo dal lato "crittografico" ma anche e soprattutto dal punto di vista del reversing. Ho cercato di fare un'analisi approfondita e dettagliata, capisco che può essere lungo è pesante da studiare, ma secondo un reverser è proprio questo, bisogna andare oltre il solito jz->jnz. Con un pò d' impegno, dopo sarete in grado di riconoscere il Blowfish subito e soprattutto sarete in grado di riconoscerne le varianti. Spero di far seguire a questo tutorial, uno più "pratico" in cui cioè reverseremo un target vero e proprio.

• Ida
• Ollydbg
• Buone basi di crittografia

www.google.it

 

Raskgme1----> crackme che ho usato come target per spiegare blowfish.

Blowfish overview

Il Blowfish è un cifrario a blocchi a chiave segreta-simmetrica (quindi un'unica key vale sia per l'encrypt sia per il decrypt). Blowfish si basa fondamentalmente su di un Feistel network, per chi no lo sapesse un Feistel network itera (ripete) una certa funzione di encrypt un certo numero di volte (ogni ciclo è detto round) normalmente vengono fatti 16 rounds. Oltre al Feistel-Network, si basa anche su delle S-Box (sono come degli array) indipendenti da chiavi, e si basa anche su una funzione F oneway, in altre parole non invertibile. Abbiamo detto che si tratta di un cifrario a blocchi, per la precisione, la grandezza di questi blocchi è di 64 bits, mentre la chiave può essere di una qualsiasi lunghezza purché non superi i 448 bits. Fino a questo momento non si conoscono tecniche di attacco "sicure", inoltre blowfish è molto veloce se non il più veloce fra IDEA e DES. Una curiosità, data la compattezza del Blowfish, questo è stato implementato in alcuni microcontrollori tra cui il 68HC11. Nota di reversing: le grandi S-Box (aka array) risultano essere molto resistenti ad attacchi di crittoanalisi differenziale. Dopo quest'introduzione possiamo cominciare a studiare l'algoritmo vero e proprio. E' importante innanzitutto mettere in evidenza i meccanismi generali di funzionamento che poi saranno fondamentali per poter riconoscere blowfish in uno schema di protezione. La procedura di encrypting può essere divisa in due fasi:

• Fase di espansione (o di inizializzazione, è la più complessa)

In cui la chiave lunga al massimo 448 bits, viene "trasformata" in un array di sottochiavi per un totale di 4168 bytes.

• Fase di crittazione vera e propria:

Nella fase di crittazione vera e propria che avviene in 16 "rounds", sono usate operazioni come XOR e somme, il size usato è DWORD. Tutto ciò viene posto in array indicizzati. Sempre dalla chiave simmetrica vengono ricavati 2 tipi di array: P-Array e S-Box. Il P-Array è di 18 elementi ed ogni sottochiave è lunga 4 bytes:

P1,P2,P3.....P18

Mentre le S-Box sono in tutto 4 ognuna delle quali è costituita da 256 sottochiavi a 32 bits. Vediamo ora in dettaglio cosa avviene nella fase di espansione:

.1 Viene inizializzato il P-array e le 4 S-Box, la cosa importante da ricordare è che quest'ultime vengono inizializzate con una stringa fissa.

.2 Avviene uno XOR tra il P-array e la chiave scelta.

.3 Si ripete questa procedura fino a quando tutte le sottochiavi del P-array sono state "codificate" nella forma:

P-array= {xL1,xR1,xL2,xR2,......,xL18,xR18}

.4 Utilizzando la nuova codifica del P-array, si passa alla sostituzione delle sottochiavi delle S-Box, la cosa importante da sapere qui è che le S-Box modificate vengono riutilizzate nel round successivo.

Ora che abbiamo visto un pò come funziona la fase di encrypt, possiamo dire che il Blowfish si basa su S-Box randomizzate. L'algoritmo infatti crea delle grandi tabelle di lookup con dati pseudorandom. La semi-casualità è data proprio dalla key stessa. Come avrete certamente capito questa procedura è abbastanza complessa, se poi andassimo a vedere le "implicazioni"che ci sono tra le S-box ottenute e la chiave usata, vedremmo che queste relazioni sono mostruosamente complesse. Tutto ciò ha come conseguenza il fatto che blowfish è "immune" (tranne qualche caso) agli attacchi di crittoanalisi differenziale e lineare. Gli unici attacchi conosciuti al blowfish sono fondati sull'uso di chiavi deboli, in cui cioè in almeno una delle 4 s-box generate occorre una collisione.

In fine vediamo come dovrebbe presentarsi il Blowfish in una routine di protezione:

• Blowfish_Initialization( )
• Blowfish_encrypt( )
• Blowfish_decrypt( )

An attack for Blowfish (addendum)

Questa parte non è di fondamentale importanza per capire poi il reversing del blowfish, però potrebbe interessare a chi vuol sapere qualcosa di più sulla crittoanalisi. L'attacco a Blowfish meglio riuscito è stato quello di Vaundenay, il quale ha anche dimostrato la presenza di chiavi deboli nel cifrario. Perché occorra la condizione di "chiave debole" ci dev'essere almeno UNA collisione nelle 4 S-box generate. La condizione quindi è:

Sbox1(X)=Sbox1(Y)

Dove X e Y sono 2 bytes diversi. Se a questo punto chi attacca conosce tutte le entrate delle S-box (ma non P1, P2 ecc), o meglio la chiave descritta dalla funzione F. Possiamo considerare la seguente condizione:

d= X xor Y

"d" invece è la chiave (in questo caso ovviamente debole). Ora P1 P2 ecc. sono di conseguenza generati da chiave debole, se consideriamo una collisione sola in S1, la probabilità che questa si verifichi è di 2^(-7). Siamo davanti ad un Fiestel Network perciò aspettiamoci che le "cose" crescano di round in round :). Se infatti ripetiamo il procedimento (d X xor Y) tre volte otterremo (2^-7)^3 cioè 2^(-21). Quindi ora si tratta di proseguire con un attacco di tipo "chosen plaintext" in cui cioè abbiamo:

xor (0000d000), usando una coppia scelta (c,c') arriviamo a xor(d000xyzt), C primo lo consideriamo diviso in 2 parti c(L,R), se ora applichiamo la funzione F a cascata, otteniamo un'equazione:

F(L xor P10) xor F(L xor P10 xor [d000])=[xyzt]

Applicando un bruteforce (2^32 possibilità) otteniamo proprio P10 che verifica l'equazione precedente.

An analytic/reverse approach to Blowfish

Finalmente siamo arrivati alla parte più interessante...la parte dedicata al reversing :).Vedremo qualche esempio pratico di blowfish, cercheremo di capire com'è implementato e come "reversarlo". Analizziamo ora una piccola parte del crackme Raskgme1 il quale tra le altre cose implementa il blowfish. Questo crackme implementa anche Bignums, Elgamal ecc., a noi però interessa solamente la parte relativa al blowfish.

004018A2 push 0040A0B8 ; ptr alla dtKey
004018A7 push ecx
004018A8 call 00401130 ; Blowfish_Init()

Vediamo ora cosa accade dietro la nostra funzione d'inizializzazione:

00401130 push ecx

00401134 mov esi, dword ptr [esp+14]

00401138 push edi

00401139 mov eax, 00408118

0040113E lea ecx, dword ptr [esi+48]

00401141 mov edx, 00000100 ; Numero di iterazioni (100h=256d)

00401146 mov edi, dword ptr [eax]

00401148 add eax, 00000004

0040114B mov dword ptr [ecx], edi ;copia in ecx (array), edi

0040114D add ecx, 00000004 ; Avanza di una dword l'indice dell'array

00401150 dec edx ;decrementa il contatore

00401151 jne 00401146 ; Ripeti il ciclo 256 volte

00401153 cmp eax, 00409118

00401158 jl 00401141 ; Ripeti il ciclo precedente 4 volte

Bene!, in questo pezzo di codice si viene a creare un array grande 256!, ad ogni ciclo viene copiata una dword, questo ciclo a sua volta viene ripetuto 4 volte. Se avete studiato con attenzione la parte precedente, non dovreste aver problemi a capire cosa fa, :P. Trasformiamoci questa routine in C:

int i, j, k;

unsigned long data, datal, datar;

for (i = 0; i < 4; i++) {

for (j = 0; j < 256; j++)

ctx->S[i][j] = ORIG_S[i][j]; }

Vi starete certamente chiedendo cos'è ctx?, come si può intuire dal -> , ctx è una struttura, ma cosa ci può essere in quella struct? :

typedef struct {

unsigned long P[16 + 2];

unsigned long S[4][256]; } BLOWFISH_CTX;

Sinteticamente, è un Blowfish Context, all'interno del quale troviamo la definizione dei P-array e delle S-box, che tanto care sono al nostro Blowfish :). Tornando al ciclo for di prima, vediamo che all'interno sono iterate le 4 S-box di cui abbiamo parlato prima!, ognuna delle quali formata da 256 sottochiavi a 32 bits. In altre parole siamo nella fase di espansione.

0040115A mov ebp, dword ptr [esp+20] ;| Saranno importanti perchè poi conteranno xL ed xR

0040115E mov edx, dword ptr [esp+1C] ;| o per meglio dire saranno "Data"

00401162 mov edi, 004080D0 ;Viene messo un valore in edi, a non non interessa sapere cosa sia

00401167 xor eax, eax ;

00401169 sub edi, esi

0040116B mov [esp+10], 00000012 ; 12h farà da indice (12h=18d)

00401173 xor ecx, ecx ; Azzera un indice (j=0) prima di iniziare il ciclo (serve ad evitare "interferenze") con l'algo vero e proprio

00401175 mov [esp+20], 00000004 ;Altro indice

0040117D xor ebx, ebx

0040117F mov bl, byte ptr [eax+edx]

00401182 8 shl ecx, 08 ; data = (data << 8) OR key[j]

00401185 or ecx, ebx ;

00401187 inc eax ; j = j + 1;

00401188 cmp eax, ebp ;| if (j >= keyLen) ----> keyLen, rappresenta la grandezza della chiave

0040118A jl 0040118E

0040118C xor eax, eax ;J=0

0040118E mov ebx, dword ptr [esp+20]

00401192 dec ebx ; Ebx parte da 4 fino ad arrivare a 0

00401193 mov dword ptr [esp+20], ebx

00401197 jne 0040117D ;Ripeti finchè non è 0

00401199 mov ebx, dword ptr [edi+esi]

0040119C add esi, 00000004

0040119F xor ebx, ecx ; Xora i due valori contenuti in ecx ed ebx (ctx->P[i] = ORIG_P[i] ^ data; )

004011A1 mov ecx, dword ptr [esp+10] ; In ecx va il valore 18

004011A5 mov dword ptr [esi-04], ebx

004011A8 dec ecx

004011A9 mov dword ptr [esp+10], ecx

004011AD jne 00401173 ;ripeti i 2 cicli (quello di quattro) 18 volte

Questo pezzo di codice merita qualche spiegazione, abbiamo nuovamente due cicli nidificati, uno viene iterato 4 volte l'altro 18 volte (a cosa vi fa pensare il 18?...bbrravi ai P-array :-D). Cerchiamo di vedere un pò più chiaramente cosa fa questo pezzo di codice trasformandolo in C:

for (i = 0; i < N + 2; ++i) {

data = 0x00000000;

for (k = 0; k < 4; ++k) {

data = (data << 8) | key[j];

j = j + 1;

if (j >= keyLen) j = 0;

}

ctx->P[i] = ORIG_P[i] ^ data; } // ctx AKA Blowfish Context

La parte che più c'interessa è l'ultima riga, in cui possiamo vedere uno Xor un array (P-array) è i dati, il risultato di questo xor va a finire in un altro array (il nuovo P-array). Ed è proprio in questo punto che si avvengono le relazioni (non pensate male :)) più ganze tra key e P-array. Se non capite bene in che fase stiamo andare a rivedervi il .2 sopra. Il prossimo pezzo di codice farà uso della funzione encrypt del blowfish, quindi, open your brain.

004011BD mov esi, ebx

004011BF mov edi, 00000009

004011C4 lea eax, dword ptr [esp+1C] ;DataR

004011C8 lea ecx, dword ptr [esp+20] ; DataL

004011CC push eax ; Data R (simile ad xR, che trovate nella prima parte)

004011CD push ecx ;Data L (simile ad xL, che trovate nella prima parte)

004011CE push ebx ; Ctx (il bowfish context che abbiamo visto nella routine precedente)

004011CF call 00401000 ; Blowfish_encryption(ctx,&DataL,&DataR ), prende tre parametri

  Per capire meglio cosa succede trasformiamoci anche questa routine in C:

for (i = 0; i < N + 2; i += 2) { // ......ho saltato un pezzo di codice, che cmq abbiamo visto prima

Blowfish_Encrypt(ctx, &datal, &datar);

ctx->P[i] = datal; // Li analizzeremo dopo

ctx->P[i + 1] = datar; // Li analizzeremo dopo

}

Fate attenzione a quante volte viene ripetuta quest'operazione, esattamente fino a quando tutti gli array saranno stati espansi cioè riempiti con i nuovi dati, in questo caso è iterata per quant'è grande il P-array. La cosa interessante da notare è che quando vi provate in una routine d'inizializzazione del Blowfish, all'interno sicuramente troverete la funzione di encrypt. Passiamo ora a vedere proprio la funzione di encrypt:

00401000 mov eax, dword ptr [esp+08] ;DataL in eax

00401004 mov ecx, dword ptr [esp+0C] ;DataR in ecx

0040100A mov eax, dword ptr [eax]

0040100C push esi

0040100D mov esi, dword ptr [ecx]

0040100F push edi

00401014 mov [esp+14], 00000010 ; Si prepara per un for (10h=16d)

Semplicemente in questo pezzo di codici, DataL e DataR sono assegnate alle variabili locali della nostra funzione, si prepara per eseguire un for. Vediamo cosa c'è dopo, nella nostra routine di encrypt:

0040101E xor eax, dword ptr [ebx] ; left ^= p[0];

00401020 push eax ;parametro che sara usato dalla call 00401060, chiamiamolo Y

00401021 57 push edi ;altro parametro che sara usato dalla call 00401060, chiamiamolo X

00401022 mov ebp, eax

00401024 call 00401060 ;chiamiamola Getbyte(X,Y)

Per capire cosa fa questa call, potrei postare il codice asm, ma non credo sia necessario, così eccovi direttamente il codice in C:

#define GETBYTE(x, y) (unsigned int)(((x)>>(8*(y)))&255)

In pratica questa è la famosa funzione F, in questo caso prende come input il ctx (context) ed xL. Procediamo ora con la routine di encrypt:

00401029 mov ecx, dword ptr [esp+1C] ;Mette in ecx 10h, 16d cioè i 16 rounds del Feistel risordate?

0040102D add esp, 00000008

00401030 xor eax, esi

00401032 add ebx, 00000004 ;avanza di una dword

00401035 dec ecx ;decrementa il contatore

00401036 mov esi, ebp

00401038 mov dword ptr [esp+14], ecx

0040103C jne 0040101E ;ripeti 16 volte

Toh un ciclo a 16 rounds!!!potrebbe essere il Feistel Network a lavoro! :), un'altra cosa sospetta è l'uso di F( ), direi che ormai non ci sono dubbi, siamo proprio nel cuore della routine di encrypt!. Quello che notiamo subito è che tutto il processo si basa sugli Xor, xor che avvengono tra i due spezzoni di dato (ognuno dei quali a 32 bits).

for (i = 0; i < N; ++i) {

Xl = Xl ^ ctx->P[i]; // xor tra DataL ed il valore puntato in questo momento dal P-array

Xr = F(ctx, Xl) ^ Xr;

temp = Xl;

Xl = Xr;

Xr = temp; }

Continuiamo con l'ultima parte di codice dell'encrypter. Nella quale parte possiamo vedere altri xor:

Xr = Xr ^ ctx->P[N];

Xl = Xl ^ ctx->P[N + 1];

*xl = Xl;

*xr = Xr;

}

Ecco abbiamo finito di analizzare la routine di encryption!, quindi torniamo alla routine d'inizializzazione, e vediamo cosa succede immediatamente dopo l'encrypt:

004011D4 8B54242C mov edx, dword ptr [esp+2C] ; sposta il nuovo DataL in edx

004011D8 8B442428 mov eax, dword ptr [esp+28] ; sposta il nuovo DataR in edx

004011DC 8916 mov dword ptr [esi], edx ; Mette DataL , nel ctx->P (che sarebbe il P-array)

004011DE 894604 mov dword ptr [esi+04], eax; ; Mette DataR , nel ctx->P successivo (locazione del p-array successiva)

Quindi a questo punto capiamo che la funzione di encrypt ci restituisce 2 dword (DataL e DataR), questi vengono messi nel p-array. Assumendo così alla fine di tutto il ciclo for, questa forma:

P-array {DataL1,DataR1,....,DataL18,DataR18}

Nella blowfish_init(), la funzione di encrypt è chiamata due volte, una è quella che abbiamo appena visto, la seconda è quella che vedremo ora :) :

004011F2 mov edi, 00000080 ;l' indice del counter viene settato a 80h, cioè 128d

004011F7 ecx, dword ptr [esp+1C] ;DataR

004011FB lea edx, dword ptr [esp+20] ;DataL

004011FF push ecx ;DataR

00401200 push edx ;DataL

00401201 push ebx ;context

00401202 call 00401000 ;Blowfish_encrypt()

00401207 mov eax, dword ptr [esp+2C] ;DataL va in ctx->S[i][j]

0040120B mov ecx, dword ptr [esp+28] ;DataR ctx->S[i][j+1] (cioè all'elemento successivo)

Come al solito, abbiamo DataL e DataR in uscita dalla funzione d'encrypt, che vanno in un array, cerchiamo di capire quale.... Innanzitutto il for è settato a 128 (cioè 256/2), anche se non l'ho messo questo ciclo si trova dentro un altro for, quest'ultimo si ripete quattro volte. I valori di questi due cicli for dovrebbe farvi insospettire ...e farvi pensare alle 4 S-box... :D. Infatti vediamo che:

S-box[1] {DataL1,DataR1,....,DataL128,DataR128}

Stesso dicasi con le rimanenti tre S-box.

Wow! abbiamo sminuzzato ed analizzato il blowfish ragà, mica bruscolini :P. Ora possiamo riconoscere al volo blowfish in tutte le sue varianti!!. Ora dire qualcosa a riguardo della funzione di decrypt. Ecco come si presenta:

Blowfish_Decrypt(BLOWFISH_CTX *ctx, unsigned long *xl, unsigned long *xr)

Come la funzione di encrypt, prende come input il context, DataL e DataR, come valore di ritorno abbiamo DataL e DataR decriptati. Bisogna fare molta attenzione perchè come avete potuto vedere vengono usati molto gli xor, e come ben sapete per ottenere l'inverso (in questo caso aka decrypt) basta riutilizzare lo xor. Perciò encrypt() e decrypt() saranno molto simili tra loro. Comunque la decrypt() può essere riconosciuta principalmente per:

Xr = Xr ^ ctx->P[1];

Xl = Xl ^ ctx->P[0];

Spesso negli schemi di protezione, per riconoscere un determinato algoritmo, si usa controllare la presenza di eventuali valori costanti (come ad esempio per gli MDx,TEA,Ghost etc). Nel blowfish non abbiamo veri e propri valori costanti che sono utilizzati "direttamente", ma abbiamo comunque i valori di partenza originali, per il p-array il primo elemento è:

0x243F6A88L

e per la S-box1 il primo elemento è:

0xD1310BA6L

Un'altra cosa che ci aiuta a riconoscere il Blowfish, è il numero di iterazioni fatte nei cicli for. Esiste anche un apposito programma che analizzando i programmi va alla ricerca delle signatures degli algoritmi. Questo programma si chiama CrypTool ed è di Christal.

Keygen del Blowfish

Scrivere dei keygenerator per blowfish, non è una cosa difficile, anzi.... Dobbiamo avere innanzitutto i sorgenti scritti da Paul Kocher (i files sono blowfish.c e blowfish.h) questi li potete trovare molto facilmente con una ricerca sul web. Le cosa da tener presente durante la fase di coding non sono poi molte, per prima cosa dobbiamo avere la chiave usata per codificare il serial, possiamo scrivere una cosa tipo:

unsigned char szSetKey[]="BAPCRHJTET5DF4TR5YEWERKTY879432";

Inoltre, spesso viene usata una xor mask, che possiamo codare alla stessa maniera:

 unsigned char szxortable[8]={0x6B, 0x74, 0x17, 0x69, 0x65, 0x1D, 0x67, 0x52};

Molto spesso ho anche notato che nome e serial, vengono trasformati da lowercase ad uppercase. Poi al nostro nome viene applicato uno xor. Da qualche parte troveremo sempre una funzione d'inizializzazione, che possiamo emulare nel nostro keygen in questo modo:

BLOWFISH_CTX blowfishctx;

Blowfish_Init(&blowfishctx, &szSetKey, 0x1f);

Dove in questo caso l'ultimo parametro è la grandezza della nostra key. Immediatamente dopo dobbiamo crearci qualche artificio per mettere in DataL e DataR i dati giusti (questo non accade spesso):

 __asm{

  lea esi,szName

 mov eax,dword ptr [esi]

 mov     dtA,eax

mov eax,dword ptr [esi+4]

 mov     dtB,eax

           }

Di seguito possiamo chiamare subito la chiamata di encrypt:

Blowfish_Encrypt(&blowfishctx, &dtA, &dtB);

Ovviamente queste non sono strutture rigide da mantenere durante il coding del keygen, poiché i casi possono essere molteplici. Qui vi ho presentato semplicemente il caso generale con il quale avrete più spesso da fare. Il caso peggiore che si potrebbe presentare è quello del blowfish modificato, in pratica si tratta di schemi di protezione che utilizzano porzioni di algoritmo modificate. Le modifiche che vengono apportate all'algoritmo sono le più svariate, ma tutte queste routine modificate hanno punti in comune:

• Numero di Feistel rounds alterato (spesso è 32)
• La S-box ha dei valori di partenza, diversi da quelli solitamente usati
• La funzione F è modificata, spesso restituisce S[2][d]-S[1][b])^(S[0][c]+S[3][a]

Spero di essere stato chiaro e comprensibile nella spiegazione. Volutamente qui non ho voluto reversare nessun target commerciale che usasse Blowfish, perchè lo scopo di questo tutorial è "uno studio del blowfish dal punto di vista del reverser/crittografo". In un prossimo tutorial reverseremo un target vero e proprio. Come sempre, per qualsiasi commento idea chiarimento, la mail è sopra.

Saluto:Tutta la UIC, Quequero, Ironspark, kratorius, LonelyWolf, Graftal, nu (bella gatta da pelare mi hai dato ;P), all my friends on Anticrack especially Hell_Master, Bon_Scott (hey man you will win your struggle ;) ). Ebbasta

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

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