In
Crittografia, l'Advanced Encryption Standard (AES),
conosciuto anche come Rijndael (benché, più propriamente, AES sia una
particolare implementazione dell'algoritmo Rijndael), è un algoritmo di
cifratura a blocchi utilizzato come standard dal governo degli
Stati Uniti d'America. Data la sua sicurezza e le sue specifiche pubbliche
si presume che in un prossimo futuro venga utilizzato in tutto il mondo come è
successo al suo predecessore, il
Data Encryption Standard (DES). È stato adottato dalla
National Institute of Standards and Technology (NIST) e dalla US
FIPS PUB nel
novembre
del 2001 dopo 5
anni di studi e standardizzazioni.
L'algoritmo è stato sviluppato da due crittografi
Belgi,
Joan
Daemen e
Vincent Rijmen, che lo hanno presentato al processo di selezione per l'AES
con il nome di "Rijndael", derivato dai nomi degli inventori. Rijndael, in
fiammingo, si pronuncia approssimativamente "rèin-daal".
Sviluppo
Rijndael è un'evoluzione del primo algoritmo sviluppato da Daemen a Rijmen,
Square.
Square era stato sviluppato per
SHARK.
A differenza del DES, Rijndael è una
rete a sostituzione e permutazione, non una
rete di Feistel. AES è veloce sia se sviluppato in
software
sia se sviluppato in
hardware,
è relativamente semplice da implementare, e richiede poca
memoria. Il nuovo standard di cifratura sta sostituendo i precedenti
standard e la sua diffusione continua ad aumentare.
Descrizione dell'algoritmo
Nel passaggio SubBytes, ogni byte della matrice è
sostituito con i dati contenuti nella trasformazione S; bij
= S(aij).
|
Nel passaggio ShiftRows, i byte di ogni riga vengono
spostati verso sinistra dell'ordine della riga. Vedi figura per i
singoli spostamenti.
|
Nel passaggio MixColumns ogni colonna di byte viene
moltiplicata per un polinomio fisso c(x).
|
Nel passaggio AddRoundKeys ogni byte della matrice viene
combinato con la sua sottochiave tramite un'operazione di
XOR.
|
Formalmente AES non è equivalente al Rijndael (sebbene nella pratica siano
intercambiabili) dato che il Rijndael gestisce differenti dimensioni di
blocchi e di chiavi. Nell'AES il blocco è di dimensione fissa (128 bit) e la
chiave può essere di 128, 192 o 256 bit mentre il Rijndael specifica solo che
il blocco e la chiave devono essere un multiplo di 32 bit con 128 bit come
minimo e 256 bit come massimo.
AES opera utilizzando matrici di 4×4 byte chiamate Stati (States). Quando
l'algoritmo ha blocchi di 128 bit in input, la matrice State ha 4 righe e 4
colonne; se il numero di blocchi in input diventa di 32 bit più lungo, viene
aggiunta una colonna allo State, e così via fino a 256 bit. In pratica, si
divide il numero di bit del blocco in input per 32 e il quoziente specifica il
numero di colonne. Per cifrare, ogni round (fase) dell'AES (eccetto l'ultimo)
consiste nei seguenti quattro passaggi:
- SubBytes – Sostituzione non lineare di tutti i byte che vengono
rimpiazzati secondo una specifica tabella.
- ShiftRows – Spostamento dei byte di un certo numero di
posizioni dipendente dalla riga di appartenenza
- MixColumns – Combinazione dei byte con un'operazione lineare, i
byte vengono trattati una colonna per volta.
- AddRoundKey – Ogni byte della tabella viene combinato con la
chiave di sessione, la chiave di sessione viene calcolata dal gestore delle
chiavi.
L'ultimo round salta il MixColumns.
SubBytes
Nel passaggio SubBytes ogni byte della matrice viene modificato
tramite la S-box
a 8 bit. Questa operazione provvede a fornire la non linearità all'algoritmo.
La S-box utilizzata è derivata da una funzione inversa nei
campi
finiti (28), conosciuta per avere delle ottime proprietà
di non linearità. Per evitare un potenziale attacco basato sulle proprietà
algebriche la S-box è costruita combinando la funzione inversa con una
trasformazione affine invertibile. La S-box è stata scelta con cura per
non possedere punti fissi e nemmeno l'inversa possiede punti fissi.
ShiftRows
Il passaggio ShiftRows provvede a scostare le righe della matrice
di un parametro dipendente dal numero di riga. Nell'AES la prima riga resta
invariata, la seconda viene spostata di un posto verso sinistra, la terza di
due posti e la quarta di tre. In questo modo l'ultima colonna dei dati in
ingresso andrà a formare la
diagonale
della matrice in uscita. (Rijndael utilizza un disegno leggermente diverso per
via delle matrici di lunghezza non fissa.)
Tutte le operazioni sono effettuate utilizzando l'indice della colonna “modulo”
il numero di colonne.
MixColumns
Il passaggio MixColumns prende quattro byte di ogni colonna e li
combina utilizzando una trasformazione lineare invertibile. Utilizzati in
congiunzione, ShiftRows e MixColumns provvedono a far
rispettare il criterio di diffusione e confusione nell'algoritmo (teoria
di Shannon). Ogni colonna è trattata come un polinomio in
GF(28) e viene moltiplicata modulo
x4 + 1 per un polinomio fisso
c(x) = 3x3 + x2 + x +
2.
AddRoundKey
Il passaggio AddRoundKey combina con un
XOR la chiave di
sessione con la matrice ottenuta dai passaggi precedenti (State). Una chiave
di sessione viene ricavata dalla chiave primaria ad ogni round (con dei
passaggi più o meno semplici, ad esempio uno shift di posizione dei bit)
grazie al
Key Scheduler.
Sicurezza
Durante il 2004
non si sono verificate forzature dell'AES. La
National Security Agency (NSA) segnalava che tutti i finalisti del
processo di standardizzazione erano dotati di una sicurezza sufficiente per
diventare l'AES ma che fu scelto il Rijndael per via della sua flessibilità
nel trattare chiavi di lunghezza diversa, per la sua semplice implementazione
in hardware e in software e per le sue basse richieste di memoria che ne
consentono un'implementazione anche in dispositivi con scarse risorse come le
smart
card. L'AES può essere utilizzato per proteggere le informazioni
classificate. Per il livello SECRET è sufficiente una chiave a 128 bit mentre
per il livello
TOP
SECRET si consigliano chiavi a 192 o 256 bit. Questo significa che per la
prima volta il pubblico ha accesso ad una tecnologia crittografica che NSA
ritiene adeguata per proteggere i documenti TOP SECRET. Si è discusso sulla
necessità di utilizzare chiavi lunghe (192 o 256 bit) per i documenti TOP
SECRET. Alcuni ritengono che questo indichi che l'NSA ha individuato un
potenziale attacco che potrebbe forzare una chiave relativamente corta (128
bit), mentre la maggior parte degli esperti ritiene che le raccomandazioni
della NSA siano basate principalmente sul volersi garantire un elevato margine
di sicurezza per i prossimi decenni contro un potenziale attacco esaustivo.
La maggior parte degli algoritmi crittografici viene forzata riducendo il
numero di round. L'AES effettua 10 round per la chiave a 128 bit, 12 round per
la chiave a 192 bit e 14 round per la chiave a 256 bit. I migliori attacchi
sono riusciti a forzare l'AES con 7 round e chiave di 128 bit, 8 round e
chiave di 192 bit e 9 round e chiave di 256 bit.
Alcuni crittografi hanno fatto notare che la differenza tra i round
effettuali dall'AES e quelli massimi prima che l'algoritmo non sia più
forzabile è ridotta (specialmente con chiavi corte). Questi temono che
miglioramenti nelle tecniche di analisi possano permettere di forzare
l'algoritmo senza verificare tutte le chiavi. Attualmente una ricerca
esaustiva è impraticabile: la chiave a 128 bit produce 3,4 · 1038
combinazioni diverse. Uno dei migliori attacchi a forza bruta è stato svolto
dal progetto
distributed.net su una chiave a 64 bit utilizzando l'algoritmo
RC5; l'attacco ha
impiegato quasi 5 anni, utilizzando il tempo "libero" di migliaia di CPU di
volontari sparsi per la rete. Anche considerando che la potenza dei computer
aumenta nel tempo, servirà ancora moltissimo tempo prima che una chiave da 128
bit sia attaccabile con il
metodo forza bruta.
Un altro dubbio riguardante l'AES deriva dalla sua struttura matematica. A
differenza della maggior parte degli algoritmi a blocchi, per l'AES esiste
un'approfondita descrizione matematica
[1],
[2]. Sebbene non sia mai stata utilizzata per condurre un attacco su
misura, questo non esclude che in futuro questa descrizione non venga
utilizzata per condurre un attacco basato sulle sue proprietà matematiche.
Nel 2002
l'attacco teorico chiamato
attacco XSL annunciato da
Nicolas Courtois e
Josef Pieprzyk ha mostrato un potenziale punto debole dell'AES (e di altri
cifrari). Sebbene l'attacco sia matematicamente corretto, è impraticabile
nella realtà per via dell'enorme tempo macchina richiesto per metterlo in
pratica. Miglioramenti nell'attacco hanno ridotto il tempo macchina richiesto
e quindi, in un futuro, questo attacco potrebbe diventare attuabile.
Ultimamente, alcuni esperti hanno fatto delle osservazioni agli autori
dell'attacco. Sembra che abbiano commesso degli errori teorici e che, in
realtà, le loro stime siano ottimistiche. Allo stato attuale, la reale
pericolosità dell'attacco XSL è un punto interrogativo. Comunque, attualmente,
l'AES è considerato un algoritmo veloce, sicuro e gli attacchi, fino ad ora
presentati, si sono rivelati degli interessanti studi teorici ma di scarsa
utilità nella pratica.
Voci correlate
Collegamenti esterni
Implementazioni
Bibliografia
- Nicolas Courtois, Josef Pieprzyk, "Cryptanalysis of Block Ciphers with
Overdefined Systems of Equations". pp267–287, ASIACRYPT 2002.
- Joan Daemen and Vincent Rijmen, "The Design of Rijndael: AES - The
Advanced Encryption Standard." Springer-Verlag, 2002.
ISBN 3540425802.
- Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Michael Stay,
David Wagner and Doug Whiting: Improved Cryptanalysis of Rijndael. FSE 2000,
pp213–230
Link originale
Tutti i testi sono disponibili nel rispetto dei termini della
GNU Free Documentation
License
Sicurezza Informatica
Glossario Sicurezza Informatica
|