BLOWFISH

Blowfish è un cifrario a blocchi a chiave simmetrica sviluppato da Bruce Schneier, autore del famoso libro Applied Cryptography. Quest’algoritmo utilizza varie tecniche tra le quali la rete Feistel, le S-box dipendenti da chiavi e funzioni F non invertibili che lo rendono, forse, l’algoritmo più sicuro attualmente disponibile. Le chiavi utilizzate sono di dimensioni variabili fino ad un max. di 448 bit e i blocchi utilizzati per la cifratura sono di 64 bit. Non si conoscono al momento tecniche di attacco valide nei suoi confronti. E' considerato uno degli algoritmi di cifratura a blocchi più veloce (risulta più veloce di DES e IDEA). Blowfish non è brevettato ed è di dominio pubblico.

                                                                                         

DESCRIZIONE DELL’ ALGORITMO

La procedura consiste in due fasi: una fase di espansione della chiave e una fase di cifratura dei dati.

L'espansione chiave converte una chiave di al più 448 bit in un’array di sottochiavi per un totale di 4168 byte.

La cifratura dei dati avviene attraverso 16 round. Ciascun raund consiste di una permutazione chiave-dipendente e di una sostituzione della chiave dipendente da dati ottenuti utilizzando Blowfish stesso.

Le sole operazioni usate sono XOR, somme su parole a 32-bit e quattro letture per round in array di dati indicizzati.

ESPANSIONE DELLA CHIAVE:

Dalla chiave simmetrica vengono ricavati il P-array con 18 sottochiavi a 32 bit (P1, P2,..., P18) e 4 S-box ognuna costituita da 256 sottochiavi a 32 bit.

Le sottochiavi sono calcolate usando la seguente procedura:

1.   Inizializzare nell’ordine il P-array e, a seguire, le quattro S-boxes con una stringa fissa.

2.   Fare lo XOR tra P1 e i primi 32 bit della chiave, poi lo XOR tra P2 e i successivi 32-bit della chiave, e così via per tutti i bit della chiave (eventualmente fino a P14 in quanto la chiave simmetrica è lunga al più 448 = 14*32 bit). Ripetere il ciclo fino a che non è stato eseguito lo XOR dell’intero P-array con i bit della chiave.

3.   Codificare una stringa di tutti 0 con l’algoritmo di Blowfish, usando il P-array ottenuto nel passo 2) e le S-Box inzializzate nel passo 1).

4.   Sostituire P1 e P2 con l’output del passo 3) (output 64 bit = 2*32 bit).

5.   Codificare l’output del passo 3) usando l’algoritmo di Blowfish con le sottochiavi modificate. 

6.   Sostituire P3 e P4 con l’output del passo 5).

7.   Continuare il processo sostituendo tutte le entrate del P-array e, a seguire, tutte le entrate delle quattro S-box.

Poiché ogni iterazione genera due sottochiavi, sono necessarie 521 iterazioni per generare tutte le sottochiavi (18/2 iterazioni per generare il P-array e 256/2 iterazioni per ognuna delle quattro S-box).

 

CODIFICA:

Blowfish è una rete di Feistel che consiste di 16 round (si veda figura 1). 

L’input è un blocco di 64-bit denotato con x.
Dividere x in due blocchi da 32-bit ciascuno (xL e xR)
For i = 1 to 15
   xL = xL xor Pi
   xR = F(xL) xor xR
   Swap xL and xR
xL = xL xor P16
xR = F(xL) xor xR
xR = xR xor P17
xL = xL xor P18
Blocco tradotto = (xL xR)
 

Funzione F (si veda figura 2):

·  Dividere xL in quattro blocchi di 8 bit: a, b, c e d
·  F(xL)=((S1(a)+ S2(b)) xor S3(c))+S4(d)(dove + è l'addizione modulo 232)

 

 

 

DECODIFICA:

La decodifica funziona allo stesso modo della codifica ad eccezione dell’ordine in cui vengono usate le sottochiavi P1, P2,..., P18 che è invertito.

 

PRESTAZIONI

Sebbene ci sia una fase di inizializzazione molto complessa (la costruzione del P-array e delle S-box che comunque può essere precomputata), le fasi di codifica e decodifica dei dati sono molto veloci come viene evidenziato dal seguente schema che confronta il Blowfish con alcuni dei cifrari a chiave simmetrica più conosciuti ed usati.

 

SICUREZZA

Come è stato detto, il Blowfish è un cifrario simmetrico con chiave a lunghezza variabile (max 448 bit). Consideriamo, ad esempio, una chiave a 64 bit che implica 264=1.844.674.407*1019 possibili combinazioni. Supponiamo di avere un computer in grado di processare 1.000.000 di combinazioni al secondo, esso impiegherebbe 300.000 anni per verificare tutte le possibili combinazioni. La possibilità di usare anche chiavi di lunghezza maggiore, rende il Blowfish molto sicuro verso attacchi di tipo "forza bruta" anche se sono condotti da diversi computer contemporaneamente.

Il Blowfish è stato presentato per la prima volta da B. Schneier sulle pagine del noto Dr. Dobb's Journal nel 1994. La stessa rivista   ha poi  sponsorizzato una  gara di crittoanalisi (1000 dollari di premio per il vincitore) terminata nell'aprile del 1995. In questo contesto Jon Kelsey ha sviluppato un attacco capace  di rompere una versione del Blowfish che lavora con solo 3 round, ma non è riuscito ad estendere tale attacco al Blowfish completo. Vikramijit Singh Chhabra ha creato una macchina in grado di rendere efficiente la ricerca della chiave tramite un attacco di tipo "forza bruta", ma senza evidenziare rischi reali per l'algoritmo. I risultati più interessanti sono stati ottenuti da Serge Vaundenay che, oltre a definire attacchi a versioni modificate del Blowfish, ha evidenziato la presenza di chiavi deboli nell'algoritmo.

 

CRYPTANALYSIS OF SERGE VAUNDENAY

1) S-Box conosciute  

In questa sezione assumeremo che l'attaccante conosce la parte di chiave privata che descrive la funzione F, cioè partiremo dal presupposto che l'attaccante conosce tutte le entrate delle S-Box ma non le chiavi  P1, P2,..., P18. 

1.A) weak key attack

Una "weak key" (chiave debole) è una chiave per cui almeno una delle 4 S-Box generate, ad esempio S1, ha almeno una collisione. Ciò significa che per S1 esistono due byte diversi, a ed a', tali che S1(a)=S1(a'). Siano P1, P2,..., P18 sottochiavi generate da una weak key e sia δ lo xor della collisione per S1 cioè sia δ = a xor a’. Per una S-box qualsiasi la probabilità che non ci siano collisioni è:

Quindi, la probabilità che ci sia almeno una collisione per almeno una delle 4 S-box è 2-15. Questo significa che, mediamente, esiste una weak key ogni 215 chiavi.  Consideriamo la seguente figura, che prevede una collisione per S1:

(δ è un valore ad 8 bit e [δ000] è un valore a32 bit)

Assumendo una sola collisione per S1, con differenza δ, la probabilità che si verifichi questo risultato è 2-7. Consideriamo quindi la seguente figura (in cui viene iterato il precedente procedimento per tre volte ottenendo Blowfish su otto round):

([xyzt] rappresenta un valore indeterminato])

Sempre assumendo una sola collisione per S1, con differenza δ, la probabilità che si verifichi questo risultato è 2-21( 2-7*2-7*2-7). Quindi, provando 221 coppie di chosen plaintex con xor [0000δ000], è facile trovare una coppia di ciphertext (C,C’) con xor [δ000xyzt].

Sia C=(L,R). Abbiamo: F(L xor P10) xor F(L xor P10 xor [δ000])=[xyzt].

Provando tutte le 232 possibili combinazioni riusciamo a calcolare il valore di P10 che verifica la precedente equazione. E’ facile dimostrare che il Blowfish con t round e sottochiave  Pt+2 conosciuta è equivalente al Blowfish con t-1 round. In pratica, quindi, questo attacco permette all’attaccante di ridurre il numero di round da 8 a 7. Più in generale ,per il Blowfish con t round che usa una weak key, è possibile calcolare Pt+2 provando 27*ét-2/2ù coppie di chosen plaintex. 

Una coppia casuale di ciphertext ha xor=[δ000xyzt] con probabilità 2-32. Per essere sicuri che il risultato sia valido, è conveniente verificarlo con più coppie di ciphertext con tale xor. E’ possibile dimostrare che con t minore di 11 una sola coppia è sufficiente a garantire, con buona probabilità, che il risultato sia corretto. Viceversa, con t maggiore o uguale ad 11, è possibile trovare circa 27*ét-2/223-ù  coppie di ciphertext con xor = [δ000xyzt] che ci porterebbero ad un risultato errato per Pt+2. Per questo motivo quando t è maggiore o uguale ad 11 bisogna trovare almeno tre coppie di ciphertext che diano lo stesso risultato, il che implica che bisogna tentare mediamente con 3*27*ét-2/2ù coppie di di chosen plaintex con xor = [0000δ000] .

Una volta scoperta la sottochiave Pt+2  è possibile attaccare la chiave Pt+1  usando lo stesso metodo sul Blowfish con t-1 round . Usando questo metodo in modo iterativo possiamo risalire a tutte le t+2 sottochiavi. Poiché ,se t è pari,la complessità dell’attacco su t round è la stessa che su t-1 round, la ricerca di tutte le sottochiavi richiede 3*22+7*ét-2/2ù coppie di chosen plaintex. Per t=16 ,tale valore è 3*251 . Per t=8 ,poiché 8<11, il numero di chosen plaintex richiesto per tale attacco è 223 .

1.B) random key attack e 8-round Blowfish

In questo caso, la chiave privata è una chiave qualsiasi e non necessariamente una “weak key”. La funzione (a,b) in S1(a)+S2(b) è un’espansione da 16 a 32 bit che può portare ad una collisione S1(a)+S2(b) = S1(a’)+S2(b’) con probabilità relativamente alta. Sia δ  = a xor a’, μ = b xor b’ e consideriamo, come fatto in precedenza, la seguente figura:

(δ  e μ sono valori ad 8 bit e [δ μ 00] è un valore a32 bit)

Assumendo una sola collisione per S1+S2, con differenza δ μ, la probabilità che si verifichi questo risultato è 2-15. Consideriamo quindi la seguente figura (in cui viene iterato il precedente procedimento per tre volte ottenendo Blowfish su otto round):

([xyzt] rappresenta un valore indeterminato])

Sempre assumendo una sola collisione per S1+S2, la probabilità che si verifichi questo risultato è 2-45( 2-15*2-15*2-15). Quindi il numero di chosen plaintex richiesto per attaccare P10 è 246 (vogliamo due coppie di ciphertext con xor = [δ000xyzt] in modo da poter verificare il risultato ottenuto con la prima coppia) e 248 coppie per ottenere tutte le sottochiavi. Per Blowfish con più di otto round tale attacco è impossibile perché richiede di provare un numero eccessivo di chosen plaintex.

 2) S-Box non conosciute e 8-round Blowfish

Senza assumere che le S-box siano conosciute, è possibile solo scoprire se la chiave utilizzata è una weak key o meno (non è possibile risalire al P-array, alle S-box né alla chiave stessa). Vediamo in che modo è possibile distinguere una weak key usando un chosen plaintex attack. Consideriamo, per  esempio, un’eventuale collisione su S1 usando la seconda figura della sezione 1.A.

Scegliendo a caso i byte B1, B2, B3, B4, B6, B7, e B8 (non B5 quindi), nella matrice MB di tutte le 28 possibili combinazioni di [B1, B2, B3, B4, B5, B6, B7, B8], abbiamo  27 coppie con buono xor (cioè 27 coppie con xor uguale a [0000δ000] dove δ è il valore dell’eventuale collisione per S1). Sia MC la matrice dei corrispondenti ciphertext  [C1, C2, C3, C4, C5, C6, C7, C8]. 

E’possibile dimostrare che in ogni coppia buna il valore þ=[(B5 xor  C5), C6, C7, C8] è lo stesso per entrambi i messaggi della coppia dove, per coppia buona, si intende la coppia (Bi,Bj) tale che   Bi xor Bj = [0000δ000] e i rispettivi ciphertext hanno xor uguale =[δ000xyzt].

Quindi, per trovare una buona coppia, ci basta verificare se nella matrice ci sono delle coppie per cui è presente una collisione per il valore þ. Se non ci sono buone coppie, cioè se non ci sono collisioni per nessuna delle quattro S-Box, la probabilità di avere una collisione per þ è molto bassa (circa 2-17). 

Con 214 matrici esiste un’alta probabilità di trovare una buona coppia, sempre che ci sia almeno una collisione per almeno una delle S-box. Quindi con 222 chosen  plaintex (214 matrici con 28 chosen  plaintex ciascuna ) siamo in grado, con buona probabilità, di scoprire se ci sono collisioni per le S-box , cioè di scoprire se la chiave utilizzata è una weak key. Lo stesso attacco, però, non è attuabile sul Blowfish completo in quanto richiederebbe un numero enorme di chosen plaintex.

3) Conclusioni  

 Abbiamo dimostrato che è possibile applicare l'analisi differenziale al Blowfish su un numero limitato di round oppure presupponendo la conoscenza della parte di chiave privata che descrive la funzione F. Abbiamo studiato le S-Box che presentano delle collisioni evidenziando la presenza di chiavi deboli nell'algoritmo che diminuiscono la complessità degli attacchi (da 248 a 223 su 8 round quando F è conosciuta). Abbiamo inoltre evidenziato un sistema per rilevare una chiave debole con  222  chosen plaintex (su Blowfish con 8 round).