L' Advanced Encryption Standard

Università degli Studi di Torino

Facoltà di scienze matematiche fisiche e naturali

Corso di laurea in matematica

L’Advanced Encryption Standard

Relatore Candidato

Prof. Umberto Cerruti Chiara Capitani

Anno accademico 2005 - 2006

Indice

Introduzione ........................................................................................................................ iii

L’Advanced Encryption Standard ........................................................................................ iv

1.1 Le origini dell’AES.................................................................................................... iv

1.2 Requisiti per l’AES ......................................................................................................v

1.3 Processo di selezione dell’AES .................................................................................. vi

1.4 Sicurezza ed attacchi................................................................................................. vii

Basi matematiche ................................................................................................................ ix

2.1 I campi di Galois........................................................................................................ ix

2.2 I byte in AES ............................................................................................................ xii

2.2.1 Somma e moltiplicazione tra byte....................................................................... xii

2.3 Le word in AES ........................................................................................................xiv

2.3.1 Somma e moltiplicazione tra word .....................................................................xiv

Descrizione dell’algoritmo..................................................................................................xvi

3.1 Descrizione dell’algoritmo di cifratura ......................................................................xvi

3.1.1 SubBytes............................................................................................................xix

3.1.2 ShiftRows ..........................................................................................................xxi

3.1.3 MixColumns .................................................................................................... xxii

3.1.4 AddRoundKey ................................................................................................ xxiii

3.1.5 KeyExpansion ................................................................................................. xxiii

3.2 Descrizione dell’algoritmo di decifratura .................................................................xxv

3.2.1 AddRoundKey ................................................................................................xxvii

3.2.2 InvShiftRows ..................................................................................................xxvii

3.2.3 InvSubBytes.................................................................................................. xxviii

3.2.4 InvMixColumns ...............................................................................................xxix

Rappresentazione polinomiale dell’AES ............................................................................xxx

4.1 Descrizione dell’algoritmo nell’anello R ..................................................................xxx

Appendice ..................................................................................................................... xxxiii

Gli anelli ed i gruppi: definizione e principali proprietà ............................................. xxxiii

Polinomi: definizione e principali proprietà .................................................................xxxiv

Campi e loro estensioni..............................................................................................xxxvii

Note ...............................................................................................................................xxxix

Bibliografia ........................................................................................................................ xli

ii

Introduzione

Scopo di questa tesi è dare una breve ma esaustiva spiegazione del funzionamento dell’algoritmo crittografico Advanced Encryption Standard.

Nei quattro capitoli vedremo, rispettivamente, la “storia” di AES ed i motivi per i quali venne adottato, le basi matematiche richieste per comprendere al meglio l’implementazione e le operazioni dell’algoritmo, la descrizione dettagliata di tutte le operazioni svolte all’interno di AES e, infine, la sua rappresentazione polinomiale.

E’ inoltre presente un’appendice utile come ripasso di alcuni concetti utilizzati nella spiegazione delle basi matematiche, quali le definizioni e le proprietà principali riguardanti anelli, campi e polinomi. iii

Capitolo 1

L’Advanced Encryption Standard

In Crittografia, l’Advanced Encryption Standard (AES), conosciuto anche come 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) . AES è stato adottato dall’agenzia del dipartimento del commercio National Institute of Standards and Technology (NIST), che ha il compito di approvare gli standard federali per il governo degli Stati Uniti, e dalla US FIPS PUB 197 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”, nome derivato dai nomi degli inventori.

Rijndael è un’evoluzione del primo algoritmo sviluppato da Daemen e Rijmen, Square.

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.

1.1 Le origini dell’AES

Per molti anni il predecessore dell’AES, il DES, rappresentò lo standard per la cifratura e l’autenticazione di documenti. Il National Institute of Standard and Technology (NIST) lo scelse come standard di cifratura nel 1977 con validità quinquennale. Fu riaffermato nel 1983, nel 1988 ed infine nel 1993 con una clausola che ne confermava la validità fino al dicembre del 1998. La clausola specificava che, allo scadere di tale data, il NIST avrebbe dovuto prendere in considerazione alternative che offrissero un maggior grado di sicurezza.

Sin dall’inizio il DES fu oggetto di molte critiche che misero in discussione la sua forza crittografica; in riferimento alla sicurezza dello schema e a dispetto delle 2⁵⁶ chiavi necessarie per un attacco brutale, la metà di esse, in media, ne permetteva la violazione. Ciò portò alla considerazione che la lunghezza della chiave era troppo piccola.

In riferimento all’utilizzo delle S-Box nelle procedure di cifratura e decifratura si sospettava che queste strutture nascondessero delle trapdoor.

In vista della data di scadenza della validità del DES ed a causa di tali critiche, il NIST considerò alternative che offrissero un livello di sicurezza maggiore; una di queste, il triplo DES, venne considerato un valido sostituto, ma il NIST volle selezionare come nuovo standard un algoritmo di cifratura più sicuro ed efficiente.

A tal fine, il 12 settembre del 1997, indisse un concorso pubblico per la nomina dell’Advanced Encryption Standard: l’obiettivo fondamentale del NIST era quello di stabilire un nuovo standard che diventasse un punto di riferimento, nel secolo successivo, nel campo della sicurezza.

Ai partecipanti fu richiesto un completo pacchetto di documentazione che contenesse quanto segue:

• Una completa descrizione dell’algoritmo, comprendente tutte le equazioni matematiche, le tabelle, i diagrammi ed i parametri necessari all’implementazione dell’algoritmo;
• Una stima dell’efficienza computazionale, comprendente le seguenti informazioni:
• Una descrizione della piattaforma utilizzata per generare tale stima;
• Un’analisi dell’algoritmo rispetto agli attacchi di crittoanalisi più conosciuti;
• Un elenco dei vantaggi e dei limiti dell’algoritmo;
• Un’implementazione di riferimento in ANSI C con appropriati commenti;
• Un’implementazione ottimizzata dall’algoritmo in ANSI C e Java.

1.2 Requisiti per l’AES

Il NIST richiese per gli algoritmi candidati i seguenti requisiti:

• L’algoritmo doveva implementare un cifrario a chiave simmetrica;
• L’algoritmo doveva appartenere alla classe dei cifrari a blocchi;
• L’algoritmo doveva supportare chiavi con taglia compresa tra 128 e 256 bit e lunghezza del testo in chiaro di 128 bit (era preferibile che l’algoritmo fosse in grado di gestire ulteriori taglie);
• La struttura dell’algoritmo doveva essere tale da permetterne l’implementazione su smart-card;
• L’algoritmo doveva essere disponibile a livello mondiale, senza esclusive.

Ognuno dei progetti dei candidati venne sottoposto ad una serie di test ed analisi atti a valutare le caratteristiche computazionali e di sicurezza. I criteri di valutazione scaturirono dai commenti pubblici e dalle discussioni tenutesi il 15 aprile 1997, presso il NIST.

A tal proposito si individuarono tre categorie principali che riportiamo di seguito:

i. Sicurezza

La sicurezza rappresentò il fattore più importante della valutazione. Ogni algoritmo, per essere definito minimamente sicuro, doveva essere sottoposto alle seguenti prove:

• La sicurezza dell’algoritmo doveva essere confrontata con quella degli altri candidati;
• L’output dell’algoritmo doveva essere indistinguibile da una permutazione casuale del blocco in input.

ii. Costo

L’algoritmo candidato doveva avere una serie di attributi che ne determinassero un basso costo computazionale. Tale costo fu valutato in base ai seguenti criteri:

• Efficienza computazionale: la valutazione dell’efficienza computazionale dell’algoritmo doveva riferirsi sia all’implementazione hardware che software;
• Requisiti di memoria: si doveva considerare la grandezza del codice e la memoria richiesta.

iii. Algoritmo e caratteristiche di implementazione

La terza area di valutazione riguardò l’algoritmo e le caratteristiche implementative, quali la flessibilità, l’adattabilità software ed hardware e la semplicità. L’algoritmo doveva:

• Gestire dimensioni della chiave e dei blocchi superiori alle taglie richieste;
• Essere implementato in modo sicuro ed efficiente in diversi ambienti;
• Essere implementato come uno stream cipher, un algoritmo di hashing e fornire servizi crittografici addizionali.

1.3 Processo di selezione dell’AES

Il 2 gennaio 1997 il NIST propose un bando per la realizzazione del nuovo algoritmo di cifratura a blocchi che il governo americano avrebbe utilizzato come standard per la cifratura dei dati sensibili e non classificati e indisse quindi un concorso pubblico per la nomina dell’AES, sollecitando la comunità crittografica mondiale per la presentazione di nuovi algoritmi crittografici.

Il 20 agosto 1998, in California, si tenne la prima conferenza per la candidatura all’AES, durante la quale, il NIST annunciò i 15 candidati ufficiali, elencati nella seguente tabella:

Algoritmo Autori

• Mars — IBM
• RC6 — RSA Laboratories
• RIJNDAEL — Joan Daemen, Vincent Rijmen
• SERPENT — Ross Anderson, Eli Biham, Lars Knudsen
• TWOFISH — B. Schneider, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson
• CAST-256 — Entrust Technologies, INC.
• CRYPTON — Future System, INC.
• DEAL — R. Outerbridge, L. Knudsen
• DFC — CNRS
• E2 — Nippon Telegraph and Telephone Corp.
• FROG — TecApro International S.A.
• HPC — L. Brown, J. Pieprzyk, J. Seberry
• LOKI97 — L. Brown, J. Pieprzyk, J. Seberry
• MAGENTA — Deutsche Telekom AG
• SAFER+ — Cylink Corp.

Questi algoritmi furono sottoposti alla comunità crittografica mondiale e, in questa conferenza, il NIST sollecitò commenti pubblici sui candidati. Una seconda conferenza si tenne il 22 marzo 1999 per discutere i risultati delle analisi condotte dalla comunità crittografica mondiale sugli algoritmi candidati. Il periodo dello scrutinio pubblico riguardante le recensioni iniziali si concluse il 15 aprile del 1999.

Utilizzando le analisi ed i commenti ricevuti, il NIST selezionò 5 finalisti dei 15 algoritmi presentati, qui elencati nella seguente tabella:

Algoritmo Autori

• Mars — IBM
• RC6 — RSA Laboratories
• RIJNDAEL — Joan Daemen, Vincent Rijmen
• SERPENT — Ross Anderson, Eli Biham, Lars Knudsen
• TWOFISH — B. Schneider, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson

Dopo l’annuncio dei finalisti, il NIST aprì formalmente il processo di valutazione pubblico accettando fino al 15 maggio 2000 i commenti sugli algoritmi rimasti in gara. Il NIST ricercò attivamente commenti ed analisi su qualsiasi aspetto degli algoritmi candidati.

Il 13 e 14 aprile 2000 a New York il NIST sponsorizzò la Third AES Candidate Conference, un forum pubblico, aperto alla discussione delle analisi sui finalisti. Gli autori degli algoritmi finalisti furono invitati ad assistere e partecipare alla discussione riguardante i commenti sui propri algoritmi.

Dopo il 15 maggio 2000, il NIST studiò tutte le informazioni disponibili e il 2 ottobre 2000 selezionò Rijndael come algoritmo da proporre per l’AES.

Nel febbraio del 2001 l’AES venne presentato come un Draft-Federal Information Processing Standard (Draft-FIPS) e pubblicato per commenti e critiche. Terminato il periodo di 90 giorni di discussione nel maggio del 2001, dopo averlo corretto in modo appropriato in risposta ai commenti, il NIST iniziò una fase di recensione, pubblicazione e diffusione.

Dopo questa fase intermedia, il Segretario del Dipartimento del Commercio americano, il 26 novembre 2001, approvò in via definitiva Rijndael quale nuovo standard AES (con FIPS PUB 197). Lo standard prevede una taglia del blocco di input di 128 bit, mentre per la chiave di cifratura prevede tre possibili lunghezze 128, 192 e 256 bit (rispettivamente AES-128, AES-192 e AES-256).

Lo standard divenne effettivo il 26 maggio del 2002, sei mesi dopo l’approvazione.

1.4 Sicurezza ed attacchi

AES è attualmente lo standard di crittazione utilizzato dal governo degli USA per proteggere documenti classificati SECRET, crittati con chiave a 128 bit, e TOP SECRET, crittati con chiave a 192 o 256. Infatti ad oggi non sono noti attacchi ad AES andati a buon fine né è stata evidenziata alcuna chiave debole o semi debole come per il DES.

Gli unici successi sono stati ottenuti da attacchi “parziali”, ovvero portati ad implementazioni di AES con un numero di round inferiore a quello previsto dallo standard. I risultati migliori sono stati i seguenti:

• (2000) Ferguson et al.: AES a 7 round su chiave a 128 bit e AES a 9 round su chiave a 256 bit tramite l’attacco Square.
• (2003) Jakimoski et al.: AES a 8 round su chiave a 192 bit tramite un attacco di crittanalisi differenziale basato sulle chiavi.

In particolare l’attacco Square è una tipologia di attacco che Rijndael ha ereditato dal suo predecessore, l’algoritmo di cifratura Square appunto, e che è stato documentato dagli stessi autori al momento della presentazione di Rijndael al concorso del NIST.

L’attacco Square è un attacco di tipo chosen plaintext, ovvero in cui il crittoanalista può scegliere una serie di testi in chiaro e i rispettivi testi cifrati per poi risalire alla chiave studiando le differenze prodotte dalla cifratura dei diversi testi.

Esso si basa sulla struttura orientata al byte di Rijndael, utilizzando degli insiemi di state tutti uguali tranne che per un byte, detto “attivo”. Seguendo l’evoluzione della posizione e delle trasformazioni di tale byte, l’algoritmo è in grado di eliminare alcuni valori possibili della chiave riducendo lo spazio di ricerca.

L’attacco Square pur essendo valido, rimane comunque un attacco parziale e necessita di un numero di plain text pari a 2³². Alcuni crittografi hanno invece avanzato dubbi sulla sicurezza dell’AES a causa della sua struttura matematica.

Infatti a differenza di altri algoritmi, AES possiede una struttura molto semplice e molto ben definita e documentata. Proprio su questo spunto si basa una nuova tipologia di attacco che ha suscitato grande clamore in relazione ad AES, ovvero l’attacco chiamato XSL.

L’attacco XSL è un attacco di tipo algebrico virtualmente applicabile a quasi tutti i principali algoritmi di cifratura a blocchi, quindi non soltanto ad AES ma anche ad esempio a SERPENT, ovvero un altro dei cinque algoritmi finalisti del concorso del NIST e in particolare quello riconosciuto come il più sicuro.

In particolare XSL sfrutta la struttura matematica di AES, riducendo il problema di recuperare la chiave di cifratura al problema di risolvere un sistema di equazioni quadratiche multivariate, un sistema che risulta inoltre essere particolarmente sparso.

Secondo uno studio del 2002 combinando la tecnica XSL ad un sistema per la rappresentazione concisa di AES (BES), si può arrivare ad una complessità di 2¹⁰⁰ operazioni.

Comunque al di là del clamore suscitato dagli studi che hanno proposto l’attacco XSL, sono stati avanzati numerosi dubbi sull’efficacia di tale tecnica. Inoltre, pur essendo teoricamente corretta, non è al momento implementabile né si sa se lo sarà mai.