Blowfish study 'n reverse

Written by Evilcry.

In this tutorial, we will study the cipher called Blowfish. We will know how Blowfish works and if there are some weakness. Obviously we will see Blowfish not only from a 'cryptographer point of view' but also and *mainly* from a reverser point. I tried to make a deep dettailed analysis, my intent is to make you able to understand suddenly a code that implements blowfish.

• Ida
• Ollydbg
• Buone basi di crittografia

www.google.it

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

Blowfish overview

Blowfish is a cipher based on blocks and uses also a secret-simmetric key (so there is only a key, used both for encryption and decryption. Blowfish is based also on a Feistel-Network, for people that do not know what a Feistel, iterates a specific function a certain number of time, each cycle is called round. Usually blowfish had a round number of 16. Further the Feistel Network, blowffish bases his action on 4 SBox (could be considerated as array), indipendant from the keys, there is also a function F() OneWay, in other words a function NOT reversible. Previously we said that we're in front of a block cipher, precisely each block is 64 bits long, while the key can be long max 448 bits. Until this moment there known effective attacks techniques, blowfish is also really fast. A little curiosity, cause some good features Blowfish was implemented in some microchips, one of which is the 68HC11. Note for the attackers: the Sbox used "results to be resistant to attacks of differential cryptoanalysis". After this introduction, we can begin to study deeply this algorithm. It's important to say that the general fuctioning mechanism will be foundamental to recognize blowfish in a protection scheme. The encryption procedure can be divided in two steps:

• Expansion Step (or initialization function, this is the most complex phase).

In which the key, long max 448 bits, is "transformed" into an array of subkeys for a total of 4168 bytes

• Encryption step:

The encryption process happens in 16 rounds, are used operation as XOR and addictions, the size used is the Dword. All this, is placed into some indicized arrays. From the key, are extracted two king of arrays: P-Array and S-Box. P-Array is composed of 18 elements and each subkey is 4 bytes long:

P1,P2,P3.....P18

While the S-Box are 4, each of them is composed by 256 subkeys at 32 bits. Let's see now what happens in dettail, in the expansion phase:

.1 P-Array and the 4 S-Box are initialized, the most important thing to say, is that, the 4 Sboxes begins all with constant values.

.2 There is a XOR between P-Array and the choised key.

.3 Repeat this procedure until all subkeys of P-array are "codified" into the form:

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

.4 With the "new" P-array, begin the substitution work of the S-Box, an important thing to say is that these S-Box are modified by each round that happens.

Now we know a bit how Blowfish works in the encryption phase. So we can say that Blowfish bases is work on randomized sboxes. Indeed the algorithm builds some big lookup tables with pseudorandom data. The 'PSEUDO' casuality depends properly from the key itself. As you can see this procedure is a bit complex, indeed if we will try to analyze the "implications" that coexists between sboxes obtained and used key, we will see that these realions are really complex!. The direct consequence of all this, is that Blowfish seems to be not attackable (except some case) by differential and linear cryptoanalysis. The only well known attacks to Blowfish works essentially on the use of waek-keys, in which there is minimum a collision into one of the four sboxes.

Now let's see how should be a generical protection routine taht uses Blowfish:

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

An attack for Blowfish (addendum)

This section is not foundamental important to understand the future "reverse approach" to Blowfish, but can be interessant for people who want to know something more on blowfish cryptoanalysis. The most successful attack to blowfish was the Vaundenay attack, which demonstrated the presence of some weak keys in the cipher. The condition of "weak key" occours when there is AT LEAST ONE collision into one of the 4 Sboxes. Thi condition can be expressed as:

Sbox1(X)=Sbox1(Y)

Where X and Y are two different bytes. Now if the attacker wnows all Sboxes entrances (not P1 P2 etc.), or better knows the key described by the F() function, he can see the following relation:eguente condizione:

d= X xor Y

"d" while is the key (in this case obviously weak). As consequence also the P-array (P1 P2 etc.) are generated from the weak key, so if we assume at least one collision for S1, the probability that this collision happens is of 2^(-7). Let's consider also that we're in front of a Feistel Network, so we can espect that the things will grows round by round!. Indeed if we repeat the procedure ( d X xor Y) tre times, we will obtain 2^(-7)^3 in other words 2^(-21)!. Now we can suddenly perform a "chosen plaintext" attack, in which we have:

xor (0000d000), using a choised couple (c,c') we land at a xor(d000xyzt), c' can be considerated divided into two groups c(L,R), now if we apply in avalance F(), we will obtain the following equation:

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

And finally with a bruteforce of 2^32 we will obtain P10, that verifies the previous equation.

An analytic/reverse approach to Blowfish

Wow, we are ready to start a reversing session of Blowfish!. First of all we will analyze a little portion of Raskgme1 crackme in which is implemented Blowfish. This crackme implements also bignums and other thing that we will not consider.

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

Let's see now what happens inside our initialization function:

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 ; Number of iterations (100h=256d)

00401146 mov edi, dword ptr [eax]

00401148 add eax, 00000004

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

0040114D add ecx, 00000004 ; Avance of a dword the array index

00401150 dec edx ;decrase the counter

00401151 jne 00401146 ; Repeat this cycle 256 times

00401153 cmp eax, 00409118

00401158 jl 00401141 ; Repeat the previous cycle 4 times

This piece of code creates an array of 256 elements! and at each cycle a dword is copyed, we have also an external cycle that repeats 4 times the internal cycle. If you studied with attention the teoretical part, you should have no problems in understandind what this routine does ;). Let's translate it 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]; }

Surely you will demand what ctx is?, easly from the ->, we understand that ctx is a struct, but what should contain this struct?:

typedef struct {

unsigned long P[16 + 2];

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

Sintetically it's a Blowfish context, intside which we can found the definition of the P-array anf of the Sboxes. By returning to the previous for cycle, we can see that inside are iterated the 4 Sboxes, each of them composed by 256 subkeys at 32 bits. In other words we're in the expansion phase.

0040115A mov ebp, dword ptr [esp+20] ;| this will be important because will contains xL ed xR

0040115E mov edx, dword ptr [esp+1C] ;| or better contanins "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 will works as index (12h=18d)

00401173 xor ecx, ecx ; Null a index (j=0) first to begin a cycle with the algorithm itself

00401175 mov [esp+20], 00000004 ;Other index

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, represents the lenght of the key

0040118A jl 0040118E

0040118C xor eax, eax ;J=0

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

00401192 dec ebx ; Ebx starts from 4 and lands to 0

00401193 mov dword ptr [esp+20], ebx

00401197 jne 0040117D ;Repeat until is 0

00401199 mov ebx, dword ptr [edi+esi]

0040119C add esi, 00000004

0040119F xor ebx, ecx ; Xor two values contained in ecx and ebx (ctx->P[i] = ORIG_P[i] ^ data; )

004011A1 mov ecx, dword ptr [esp+10] ; In ecx the value 18

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

004011A8 dec ecx

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

004011AD jne 00401173 ;repeat the two 2 cycles, 18 times

This piece of code need a little explaination, we have again two cycles, one it's iterated 4 times, the other 18 times (what do you remember about the value 18?...yes the P-array ;). So let's translate also this piece of code to better understand how works:

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