Serpent (cifrario)

Serpent
	La funzione di mescolamento lineare del Serpent
Generale
Progettisti	Ross Anderson, Eli Biham, Lars Knudsen
Prima pubblicazione	1998
Derivato da	Square
Dettagli
Dimensione chiave	128, 192, 256 bit
Dimensione blocco	128 bit
Struttura	Rete a sostituzione e permutazione
Numero di passaggi	32
Migliore crittanalisi
	La crittanalisi lineare/differenziale può violare 11 dei 32 passaggi del Serpent

Il Serpent è un cifrario a blocchi a chiave simmetrica progettato nel 1998 da Ross Anderson, Eli Biham e Lars Knudsen. È famoso perché è stato uno dei finalisti del processo di standardizzazione dell'AES, dove è arrivato secondo dietro al Rijndael, selezionato come standard. L'algoritmo non è brevettato e può essere liberamente utilizzato.

Struttura

Come altri candidati per l'Advanced Encryption Standard (AES), il Serpent è un cifrario che opera su blocchi di 128 bit e supporta una chiave con dimensione variabile di 128, 192 e 256 bit. Il cifrario si basa su una rete a sostituzione e permutazione con 32 passaggi che opera su gruppi di 4 word di 32 bit ciascuna. Ogni passaggio applica 32 volte in parallelo una delle 8 S-box da 4x4 bit.

Il Serpent è stato disegnato affinché tutte le operazioni siano eseguite in parallelo, utilizzando 32 parti da 1 bit l'una. Questo massimizza il parallelismo ma permette anche di usare l'abbondante lavoro di crittanalisi condotto sul DES.

L'approccio degli sviluppatori

Gli sviluppatori dell'algoritmo hanno pensato al Serpent seguendo un approccio più conservativo alla sicurezza rispetto agli altri finalisti dell'AES, optando per un margine di sicurezza più elevato: essi ritenevano che 16 passaggi fossero più che sufficienti contro i più noti tipi di attacco, ma nonostante questo hanno scelto 32 passaggi come assicurazione contro eventuali future scoperte nella crittanalisi.

Il Serpent paragonato al Rijndael

Il Rijndael è strutturato come una rete a sostituzione e permutazione con 10, 12 o 14 passaggi, a seconda della dimensione della chiave, e con blocchi dati grandi 128, 192 o 256 bit, selezionabili indipendentemente. Il Serpent è strutturato sulla stessa rete ma con 32 passaggi, con in aggiunta una permutazione iniziale ed una finale per semplificare un'implementazione ottimizzata. La funzione interna del Rijndael è costituita da 3 parti: un livello non lineare, un livello di mescolamento non lineare ed un livello di mescolamento della chiave con operazioni di XOR. La funzione del Serpent consiste di un mescolamento della chiave con XOR, dell'applicazione parallela della stessa S-box per 32 volte, e di una trasformazione lineare, eccetto che nell'ultimo passaggio dove questa viene sostituita da un'altra operazione di XOR per il mescolamento della chiave.

Il livello non lineare del Rijndael utilizza una S-box da 8x8 pixel mentre il Serpent usa 8 differenti S-box da 4x4 pixel. Serpent, con i suoi 32 passaggi, ha un margine di sicurezza più ampio rispetto a Rjindael; per contro, il Rijndael con 10 passaggi è più veloce e facile da implementare per blocchi di piccole dimensioni. Per questo il Rijndael è stato selezionato come vincitore della competizione che ha portato all'AES.

Sicurezza

L'attacco XSL potrebbe rivelare delle debolezze nel Serpent (non diversamente da come potrebbe fare con il Rijndael, che è divenuto l'AES). Comunque, molti crittanalisti ritengono che l'implementazione di un attacco XSL, se anche fosse fattibile, risulterebbe più dispendioso di un attacco a forza bruta.

Nel 2000 T. Kohno, J. Kelsey e B. Schneier hanno pubblicato una crittanalisi preliminare del Serpent,^[1] in cui dimostravano come forzare con la crittanalisi differenziale ed attacchi meet-in-the-middle una versione del Serpent con 6 passaggi, e con un attacco a boomerang una versione con 8 passaggi.

Nel 2003 Eli Biham, Orr Dunkelman e Nathan Keller hanno dimostrato come con la crittanalisi lineare/differenziale si può violare una versione del Serpent con 11 passaggi utilizzando 2^125,3 testi in chiaro scelti ed un tempo di 2^139,2.^[2]