Reti di Feistel: elementi costitutivi dei cifrari moderni

All'inizio degli anni Settanta, Horst Feistel lavorava presso IBM Research al cifrario Lucifer quando ebbe un'intuizione fondamentale: è possibile costruire un cifrario invertibile usando una funzione di round non invertibile.

Fu una svolta rivoluzionaria, perché progettare funzioni invertibili che siano anche sicure è difficile. La costruzione di Feistel aggira completamente questo requisito, consentendo di usare funzioni di round unidirezionali arbitrariamente complesse.

In un cifrario Feistel, il blocco di input viene diviso in due metà uguali: L (sinistra) e R (destra). Ogni round applica la funzione di round F a R, esegue lo XOR del risultato con L, quindi scambia le metà.

Dopo n round, le due metà vengono ricombinate per produrre il testo cifrato. Lo scambio garantisce che entrambe le metà vengano elaborate in round alternati, mescolandole completamente.

La funzione di round F in una rete Feistel riceve in input la metà destra e la sottochiave del round e produce un output sottoposto a XOR con la metà sinistra. È fondamentale che F non debba essere invertibile.

F può essere arbitrariamente complessa: qualsiasi combinazione di sostituzioni, permutazioni, XOR e aritmetica modulare. Quanto più F è complessa e non lineare, tanto più forte è il cifrario, perché la decifratura non deve mai invertire F.

La decifratura in un cifrario Feistel usa esattamente la stessa struttura della cifratura, ma applica le sottochiavi dei round in ordine inverso. Ciò è possibile perché XOR è il proprio inverso: se A XOR B = C, allora C XOR B = A.

Poiché la decifratura non richiama mai F^-1 (l'inversa di F), la funzione di round può essere un hash irreversibile, una tabella di ricerca o qualsiasi operazione complessa senza compromettere l'invertibilità del cifrario.

L'eleganza matematica delle reti Feistel consiste nel fatto che la struttura XOR garantisce l'invertibilità indipendentemente da ciò che fa F. Anche se F è una funzione a senso unico come SHA-256, il cifrario Feistel complessivo rimane invertibile.

Questo rende i cifrari Feistel estremamente flessibili. I crittografi possono concentrarsi interamente sull'aumentare al massimo la confusione e la diffusione di F, sapendo che l'invertibilità è gestita dalla struttura stessa della rete.

Il Data Encryption Standard (DES), pubblicato nel 1977, è un cifrario Feistel a 16 round che opera su blocchi di 64 bit con una chiave di 56 bit. Ogni round usa una diversa sottochiave di 48 bit derivata dalla chiave principale.

La funzione di round di DES include una permutazione di espansione, lo XOR con la sottochiave, otto S-box che forniscono non linearità e una permutazione con P-box. La combinazione fornisce sia confusione sia diffusione, come richiesto dai principi di progettazione dei cifrari di Shannon.

Blowfish, progettato da Bruce Schneier nel 1993, è un cifrario Feistel con lunghezza della chiave variabile (32-448 bit) e 16 round. Usa S-box dipendenti dalla chiave, rendendo impraticabili gli attacchi precalcolati.

Twofish, finalista nella competizione AES, estende le idee di Blowfish con blocchi di 128 bit e 16 round. Entrambi non sono stati violati e vengono usati in applicazioni come l'hashing delle password di bcrypt, che usa una versione modificata di Blowfish.

Un cifrario Feistel bilanciato divide il blocco in due metà uguali. Un Feistel sbilanciato usa metà disuguali, ad esempio con una divisione 3/4 e 1/4.

Le reti Feistel sbilanciate possono offrire vantaggi in termini di sicurezza in determinati contesti e vengono usate in alcuni cifrari specializzati. La famiglia di cifrari CAST usa una struttura Feistel bilanciata a 64 bit.

Nel 1988, Michael Luby e Charles Rackoff dimostrarono che una rete Feistel a 3 round che usa funzioni di round pseudocasuali è una permutazione pseudocasuale sicura (PRP), mentre una versione a 4 round è una PRP forte.

Questo risultato teorico fornì alle reti Feistel una solida base di sicurezza dimostrabile, non soltanto una fiducia basata sull'esperienza. Confermò che la struttura Feistel contribuisce alla sicurezza oltre il semplice ruolo della funzione di round.

La rete di sostituzione-permutazione (SPN) usata da AES applica sostituzione e permutazione all'intero blocco simultaneamente, anziché a metà del blocco per ogni round. Ciò garantisce una diffusione più rapida.

AES raggiunge la diffusione completa in soli 4 round, mentre la struttura Feistel di DES richiede più round per ottenere una diffusione comparabile. La SPN di AES inoltre si adatta meglio alle architetture dei processori moderni con istruzioni SIMD.

Il teorema di Luby-Rackoff tratta la funzione di round F come una funzione veramente casuale. Nella pratica, F è una funzione pseudocasuale, cioè un cifrario con chiave o un hash, non un vero oracolo casuale.

Questo divario tra le dimostrazioni teoriche e le implementazioni pratiche è un tema ricorrente nella crittografia. Le dimostrazioni forniscono fiducia, ma si basano su modelli idealizzati. La sicurezza nel mondo reale dipende anche da implementazioni sicure prive di vulnerabilità dei canali laterali.

Metta alla prova la Sua comprensione della progettazione delle reti Feistel.

Le reti Feistel sono strutture di cifrari a blocchi che usano una funzione di round che non deve essere invertibile. La decifratura funziona eseguendo la stessa struttura al contrario, con le sottochiavi in ordine inverso.

DES, Blowfish e Twofish sono tutti cifrari Feistel. Il teorema di Luby-Rackoff fornisce garanzie teoriche di sicurezza. AES usa invece una struttura SPN, che offre una diffusione migliore per round.