Twofish

Da Wikipedia, l'enciclopedia libera.

Nel 1997, in risposta al crescente desiderio di rimpiazzare DES, NIST (National Institute of Standards and Technology) annunciò il programma AES (Advanced Encryption Standard). NIST richiedeva un cifrario a blocchi con i seguenti requisiti di progettazione: maggiore lunghezza della chiave, maggiore lunghezza dei blocchi, maggiore velocità, e maggiore flessibilità. Twofish è stato progettato da Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, e Niels Ferguson; il team esteso che ha avuto il compito di eseguire ulteriore crittoanalisi di Twofish include Stefan Lucks, Tadayoshi Kohno, e Mike Stay. Twofish è un cifrario a blocchi di 128-bit che accetta chiavi di lunghezza variabile fino a 256 bit. Il cifrario è una rete di Feistel di 16 round con una funzione biettiva F composta da 4 s-box dipendenti dalla chiave 8 a 8 bit, una matrice fissa 4x4 MDS su GF(s^8), una trasformata pseudo-Hadamard, rotazioni di un bit, ed un accurato progetto delle sottochiavi. Su molte piattaforme software Twofish è leggermente più lento di Rijndael per chiavi di 128-bit, ma leggermente più veloce per chiavi di 256-bit. Ad oggi, non si conosce alcun attacco a Twofish più efficiente della forza bruta.

Indice 1 Obiettivi del progetto Twofish 2 Blocchi di Twofish 2.1 Reti di Feistel 2.2 S-BOX 2.3 Matrici MDS 2.4 Trasformata pseudo-Hadamard 2.5 Whitening 2.6 Sottochiavi 3 Algoritmo 4 Crittoanalisi di Twofish

[modifica] Obiettivi del progetto Twofish

• Un cifrario a blocchi simmetrico da 128-bit
• Lunghezza delle chiavi di 128, 192, 256 bit
• Nessuna chiave debole
• Efficienza
• Progettazione flessibile
• Progettazione semplice

[modifica] Blocchi di Twofish

[modifica] Reti di Feistel

Una rete di Feistel è un metodo generale per trasformare una funzione qualunque F in una permutazione. Inventata da Horst Feistel nel progetto di Lucifer e divenuta famosa grazie a DES, è la base di molti popolari cifrari a blocchi (FEAL, GOST, Khufu e Khafre, LOKI, CAST-128, Blowfish). Il blocco fondamentale che costituisce la rete di Feistel è la funzione F: una mappatura dipendente dalla chiave di una stringa in ingresso in una stringa in uscita. Una funzione F è sempre non lineare e possibilmente non suriettiva:

dove n è la dimensione del blocco della Rete di Feistel, e F è una funzione che prende in ingresso n/2 bit del blocco e N bit della chiave, e un output di lunghezza n/2 bit. In ogni round, il "blocco sorgente" è l'input di F, e l'uscita di F è combinata tramite un’operazione XOR con il "blocco obiettivo", dopo il quale questi due blocchi sono scambiati di posto per il round successivo. L'idea qui è di prendere una funzione F, che potrebbe essere un debole algoritmo crittografico presa da sola, e iterarla ripetutamente per creare un robusto algoritmo crittografico. Due round di una Rete di Feistel sono chiamati "ciclo". In un ciclo, ogni bit del blocco di testo è stato modificato una volta. Twofish è una Rete di Feistel di 16 round con una funzione F biettiva.

[modifica] S-BOX

Nei blocchi di cifratura le S-box sono utilizzate per oscurare relazioni tra il testo in chiaro e il testo cifrato seguendo il principio della confusione e diffusione enunciato da Shannon. Confusione e diffusione sono due proprietà che un algoritmo sicuro deve possedere. Queste proprietà sono state identificate da Shannon nel suo lavoro "La teoria della comunicazione nei sistemi crittografici" pubblicato nel 1949. Nel documento di Shannon si definisce la confusione il fatto che la relazione tra la chiave e il testo cifrato sia quanto più complessa e scorrelata possibile. La diffusione è invece la capacità dell'algoritmo di distribuire le correlazioni statistiche del testo lungo tutto l'alfabeto utilizzato dall'algoritmo di cifratura rendendo quanto più difficile possibile un attacco statistico. La diffusione è associata alla dipendenza dei bit d’uscita dai bit d’ingresso. In un algoritmo con un’ottima diffusione la variazione di un bit in ingresso dovrebbe cambiare tutte le uscite con probabilità del 50%. Spesso le S-box vengono appositamente progettate per resistere alla crittoanalisi. In generale le S-box ricevono m bit d’ingresso e li trasformano in n bit d’uscita. Una S-box n x m è formata da una matrice. Una S-box è un’operazione di sostituzione non-lineare guidata da una tabella usata in molti cifrari a blocchi. Gli S-box variano sia per dimensione dell'ingresso sia dell'uscita, e possono essere creati sia casualmente sia algoritmicamente. In Twofish vengono create S-box 8x8 algoritmicamente da S-box 4x4 casuali. Gli S-box furono usati per primi da Lucifer, in seguito da DES, e poi dalla maggior parte degli algoritmi crittografici. Twofish usa 4 differenti S-box biettive 8x8 dipendenti dai bit della chiave. Queste S-box sono costruite usando due permutazioni fisse.

[modifica] Matrici MDS

Un codice MDS (Maximum Distance Separable) su un campo è una mappatura lineare dagli elementi del campo a a quelli di b, producendo un vettore composto d’a+b elementi, con la proprietà che il minimo numero d’elementi diversi da zero in ogni vettore non nullo è almeno b+1. In altre parole la distanza (numero d’elementi che differiscono) fra due distinti vettori prodotti dalla mappatura MDS è almeno b+1. Le mappature MDS possono essere rappresentate da matrici MDS di a x b elementi. Una condizione necessaria e sufficiente affinché una matrice a b sia MDS è che tutte le possibili sottomatrici quadrate, ottenute scartando righe o colonne, siano non singolari. Twofish usa una singola matrice 4x4 su GF( ).

[modifica] Trasformata pseudo-Hadamard

Una trasformata pseudo-Hadamard (PHT) è una semplice operazione di mescolamento che gira velocemente in software. Dati due ingressi, a e b, la PHT a 32-bit è definita come:

a'=a+b mod b'=a+2b mod

Twofish usa una PHT di 32-bit per mescolare l'uscita dalle sue funzioni g parallele.

[modifica] Whitening

Whitening è la tecnica di eseguire operazioni di XOR sul materiale della chiave prima del primo round e dopo l'ultimo. E' stato dimostrato che la tecnica di whitening incrementa sostanzialmente la difficoltà d’attacchi sui resti del cifrario alla ricerca della chiave. Twofish esegue lo XOR su 128 bit della sottochiave prima del round Feistel, e su altri 128 bit dopo l'ultimo round Feistel. Queste sottochiavi sono calcolate allo stesso modo delle sottochiavi del round, ma non sono usate in nessun’altra parte del cifrario.

[modifica] Sottochiavi

Il termine sottochiavi indica che i bit della chiave sono stati convertiti nelle chiavi di round che possono essere usate dal cifrario. L’algoritmo key schedule distribuisce il materiale della chiave alle differenti parti del cifrario che ne hanno bisogno, “espandendo” la chiave durante il processo. Ciò è necessario per tre ragioni:

1. I bit della chiave forniti come input al cifrario sono inferiori a quelli di cui quest’ultimo necessita.
2. I bit della chiave usati in ogni round devono essere unici in ogni round, per evitare attacchi di tipo “slide” (creati da David Wagner e Alex Biryukov nel 1999. In quest’attacco il numero dei round del cifrario è irrilevante. Si attacca il key schedule cercando ripetizioni cicliche della chiave).
3. Il cifrario deve essere sicuro contro attacchi con conoscenza parziale o controllo sui bit della chiave.

I progettisti congetturano che, durante tutti i 16 round Feistel di Twofish, non ci siano coppie di chiavi equivalenti. Non sono stati però in grado di dimostrarlo.

[modifica] Algoritmo

Twofish usa una rete di Feistel di 16 bit con un whitening addizionale dell'ingresso e dell'uscita. Gli unici elementi non-Feistel sono le rotazioni di 1-bit. Il testo in chiaro è suddiviso in 4 parole da 32-bit. Nel passo iniziale di whitening, queste sono suddivise mediante XOR in 4 parole chiave. In ogni round, le due parole sulla sinistra sono usate come input della funzione g (una di queste è prima rotata di 8 bit a destra). La funzione g consiste di 4 S-box la cui lunghezza dipende dai byte della chiave, seguiti da un passo in cui sono combinate linearmente con una matrice MDS. I risultati delle due funzioni g sono combinati usando una trasformata pseudo-Hadamard (PHT), ai quali sono sommati due parole chiave. Questi due risultati sono quindi combinati medianti l'operazione di XOR nelle parole situate a destra (una delle quali è rotata a sinistra di 1-bit prima, e l'altra è rotata a destra dopo). Le metà di destra e di sinistra sono quindi scambiate per il round successivo. Dopo tutti i 16 round, viene invertito lo scambio dell'ultimo round, e le 4 parole vengono combinate con XOR con altre 4 parole chiave per produrre il testo cifrato. Formalmente, i 16 byte di testo in chiaro p0,...,p15 sono prima divisi in 4 parole P0,...P3 ognuna di 32 bit usando la convenzione little-endian (noto anche come LSB least significant ("littlest") byte first).

Nel passo di whitening iniziale, queste parole sono combinate mediante XOR con 4 parole della chiave espansa.

In ognuno dei 16 round, le prime due parole sono usate come input della funzione F, che prende come input anche il numero di round. La terza parola combinata con XOR al primo output di F e quindi ruotata a sinistra di 1-bit e quindi combinata con XOR alla seconda parola d’output di F.

L'uscita del passo di whitening "annulla" lo scambio dell'ultimo round, ed esegue uno XOR dei dati con 4 parole della chiave espansa.

Le 4 parole di testo cifrato sono allora scritte come 16 byte c0,...c15 usando la stessa conversione litle-endian usata per il testo in chiaro.

[modifica] Crittoanalisi di Twofish

Il team ha speso 1000 ore (umane) cercando di crittoanalizzare Twofish. Essi congetturano che il metodo più efficiente per forzare Twofish sia la forza bruta. Affermano che l’attacco più efficiente ad una chiave di 128-bit abbia una complessità di 2^128, chiave di 192-bit ha complessità 2^192, chiave di 256-bit ha complessità di 2^256.