Dimensione del blocco

Nella moderna crittografia, gli algoritmi a chiave simmetrica vengono usualmente divisi in due famiglie. La famiglia degli algoritmi a blocchi e la famiglia degli algoritmi a stream. Gli algoritmi a blocchi lavorano su un insieme di simboli per volta e li cifrano o decifrano tutti in parallelo. Il primo requisito di un algoritmo di questo tipo è che il blocco di partenza e il blocco d'arrivo sia della stessa dimensione e il secondo requisito è che la funzione utilizzata per cifrare sia invertibile sempre, altrimenti, alcune volte, pur avendo la chiave corretta, la procedura di decifrazione potrebbe non svolgersi correttamente.

Prima che il NIST annunciasse il concorso per la definizione dell'AES la maggior parte degli algoritmi di cifrazione a blocchi utilizzavano blocchi di 64 bit come il DES. Il paradosso del compleanno enuncia che se si riesce ad accumulare un numero di dati cifrati uguali alla radice quadrata del numero totale di combinazioni dei dati cifrabili si ha una probabilità del 50% che due o più blocchi si ripetano e questi possono essere utilizzati per forzare l'algoritmo. Il numero totale di combinazioni per un algoritmo con blocchi di 64 bit (8 byte) è di $2^{32}\times 8$ B = 32 GB. Questo numero teorico va ridotto molto dato che si desidera rimanere molto sotto il 50% di probabilità e, quindi, i dati cifrabili con sicurezza sono poche centinaia di Megabyte. Una volta questo numero era considerato enorme e, quindi, sufficiente per tutte le necessità, ma nella nostra epoca è troppo piccolo e limitante considerando che, se l'algoritmo non gestisce adeguatamente i dati di ingresso sparpagliando i simboli più frequenti, la probabilità di cadere nel paradosso del compleanno aumenta notevolmente.

Di conseguenza, i candidati a diventare l'AES dovevano trattare blocchi a 128 bit (16 byte). Questo blocco produce $2^{64}\times 16$ B = 256 Exabyte di dati, un numero di dati sufficiente per i prossimi decenni.

Alcuni cifrari come l'RC5 gestiscono lunghezze di blocco variabile mentre il cifrario di Joan Daemen, il 3-Way ha blocchi di 96 bit.

La costruzione di Luby-Rackoff e la costruzione di Richard Outerbridge riescono ad aumentare la dimensione dei blocchi cifrati riducendo il problema derivato dal paradosso dei compleanni.