L' Advanced Encryption Standard

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

1

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

2

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 256 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.

3

In riferimento all’utilizzo delle S-Box nelle procedure di cifratura e decifratura si sospettava

4

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:

i. una completa descrizione dell’algoritmo, comprendente tutte le equazioni

matematiche, le tabelle, i diagrammi ed i parametri necessari all’implementazione

dell’algoritmo;

ii. una stima dell’efficienza computazionale, comprendente le seguenti informazioni:

una descrizione della piattaforma utilizzata per generare tale stima;

o un’analisi dell’algoritmo rispetto agli attacchi di crittoanalisi più conosciuti;

o iv

un elenco dei vantaggi e dei limiti dell’algoritmo;

o 5

un’implementazione di riferimento in ANSI C con appropriati commenti;

o 6

un’implementazione ottimizzata dall’algoritmo in ANSI C e Java .

o

1.2 Requisiti per l’AES

Il NIST richiese per gli algoritmi candidati i seguenti requisiti:

i. l’algoritmo doveva implementare un cifrario a chiave simmetrica;

ii. l’algoritmo doveva appartenere alla classe dei cifrari a blocchi;

iii. 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)

iv. la struttura dell’algoritmo doveva essere tale da permetterne l’implementazione su

7

smart-card ;

v. 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;

o essere implementato in modo sicuro ed efficiente in diversi ambienti;

o 8 9

essere implementato come uno stream cipher , un algoritmo di hashing e

o fornire servizi crittografici addizionali. v

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 Telegraf and Telephone Corp.

FROG TecApro International S.A.

HPC L.Brown,J.Pieprzyk,J.Seberry

LOKI97 L.Brown,J.Pieprzyk,J.Seberry

MAGENTA Detsche 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. vi

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

32

2

numero di plain text pari a . Alcuni crittografi hanno invece avanzato dubbi sulla

sicurezza dell’AES a causa della sua struttura matematica. Infatti a differenza di altri