Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

38
Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo

Transcript of Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Page 1: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Algoritmi crittografici

AES

(Advanced Encryption Standard)

Elennio Paolo

Page 2: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Argomenti1. Definizione di crittografia2. Definizione cifrario

– Perfetto– Computazionalmente sicuri– Condizionalmente sicuri

3. Problema della standardizzazione 4. AES

– Requisiti– Criteri di valutazione– Uso delle risorse– Es. algoritmo simmetrico (RC6)

Page 3: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Argomenti• Caratteristiche• Espansione chiave• Cifratura• Decifratura• Compatibilità (es CPU 8 bit)

• Implementazione dei comandi• Modifiche per renderlo piu efficiente• Versatilità implementativa

• Sicurezza e vari apetti• Attacchi lineari• Attacchi differenziali

Page 4: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Definizioni generali

La crittografia è la tecnica con la quale, attraverso l’uso di determinati algoritmi, si cerca di codificare documenti (testo in chiaro) per renderli incomprensibili (testi cifrati) alle persone che non sono in possesso della chiave per decodificarli.

Tali algoritmi si suddividono in 2 categorie:

1. Algoritmi a chiave simmetrica (o a chiave privata);

2. Algoritmi a chiave asimmetrica (o a chiave pubblica)

Page 5: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Definizioni generaliNel 1949 C. Shannon pubblicò un articolo che diede inizio a quella che oggi viene chiamata Teoria dell’informazione che unita a:

• Teoria della Probabilità• Teoria della Complessità • Teoria dei Numeri

da origine alla Crittografia Moderna. Definizione: Un crittosistema è una quintupla (P,C,K,FC,FD)P : insieme finito di testi in chiaroC : insieme finito di testi cifratiK : insieme delle possibili chiavi FC : funzione di cifraturaFD : funzione di decifratura

Page 6: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Definizioni generali

Definizione: un cifrario si dice perfetto se x*,y* si ha

P(x=x*)=P(x=x*|y=y*) dove x è chiaro e y è cifrato.

In altre parole la conoscenza del testo cifrato non aggiunge informazioni utili per risalire al testo in chiaro.

I cifrari perfetti (dimostrabilmente sicuri) sono stati utilizzati per la protezione della hot-line USA-URSS durante la guerra fredda.

Page 7: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Definizioni generali

In realtà esistono anche cifrari:

1. Computazionalmente sicuri – La Teoria dell’informazione ci dice che non possono essere sicuri ma il problema crittoanalitico e’ intrattabile (soluzione necessita svariati anni);

2. Condizionalmente sicuri – Sono cifrari di cui è stata dimostrata l’inattaccabilità a meno che si verifichino eventi probabilisticamente improbabili.

I cifrari moderni appartengono alla 1° classe in quanto i secondi sono inutilizzabili perché necessitano di tabelle casuali sterminate (Ueli Mauer – Moon Cipher)

Page 8: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Definizioni generali

Teorema di Shannon: in un sistema crittografico perfetto, la lunghezza della chiave deve essere almeno uguale a quella del testo in chiaro.

Tale teorema va contro la necessità di ogni persona di avere una chiave piccola e mnemonica per cifrare i propri documenti di cui vuol mantenere la privacy.

Perciò sono stati introdotti degli algoritmi che utilizzando come input, chiavi ridotte (pochi bit n), generano chiavi speudocasuali su dominio più ampio 2n con probabilità similare altrimenti sarebbero predicibili.

Page 9: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Standardizzazione

Gli algoritmi di crittografia col passare del tempo diventano sempre più utilizzati per la comunicazione tra personal computer oltre che per codificare documenti per uso personale, per cui necessita una standardizzazione degli algoritmi con la conseguente pubblicazione degli stessi.Vantaggi:1. I criptoanalisti, inoltre, possono esaminare gli algoritmi e

tentare di violarli valutandone così eventuali difetti dando la possibilità ai loro inventori di modificarli per renderli più sicuri.

2. Maggior scambio di informazioni tra PC diversi, possibilità di sviluppare nuove applicazioni come E-commerce.

Page 10: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

StandardizzazioneSvantaggi:

1. La pubblicazione degli algoritmi fa si che la loro sicurezza dipenda solo dalla chiave, cioè dal numero di combinazioni possibili che essa può assumere;

2. La standardizzazione implica che gli algoritmi debbano essere compatibili con più macchine, ciò implica la possibilità di commettere più errori;

3. Lo sforzo fatto per violare un algoritmo da parte dell’attaccante può essere utilizzato per venire a conoscenza di altri dati su altre macchine quindi più conveniente.

Page 11: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Introduzione - AESFino ad oggi il DES, inventato dall’IBM e poi modificato dall’NSA, ha rappresentato lo standard per la cifratura e l’autenticazione di documenti. Il National Institute of Standard and Technology (NIST) lo scelse, fin dal lontano 1977, come standard ma la sua validità è scaduta nel 1998. Sin dagli inizi, il DES è stato oggetto di numerose critiche:

• in riferimento alla sicurezza dello schema a dispetto delle 256

chiavi necessarie per un attacco di forza bruta, perché la metà di esse, in media, ne permette la violazione → chiave troppo piccola (vedi grafico)

• In riferimento all’utilizzo delle S-box(1) nelle procedure di cifratura e decifratura molti sospettano che le strutture nascondano delle Trapdoor(2)

Page 12: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Introduzione - AESNote:

(1) Le tecniche di sostituzione di bit vengono riprodotte attraverso circuiti elettronici noti come S-box, questi circuiti vengono in generale chiamati Product cipher.

(2) Una funzione trapdoor è una funzione facile da computare, ma la cui inversa è di difficile calcolo (es. Moltiplicare due numeri primi è facile ma fattorizzare il risultato è difficile), tuttavia, possiede una scappatoia: se si conosce una parte dell’informazione diventa facile calcolarne l’inversa.

Page 13: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Introduzione - AES

A conferma di quanto detto sulla chiave del DES (dimensioni ridotte) riporto una statistica effettuata nel 1998 (4 anni fa, tecnologicamente parlando si tratta di periodo molto lungo) sul tempo necessario per individuare la chiave.

(fonte: Schneier, 1998)

Tipo di Atttaccante

Chiave a

40 bit

Chiave a

56 bit

(Es. DES)

Chiave a

64 bit

Chiave a

80 bit

Chiave a

128 bit

Hacker 5 h 37

anni

10000

anni

700mila

anni1027

anni

PMI 2 s 35 h 1

anno

70000

anni1019

anni

Grossa

Impresa

2 ms 2 m 9 gg 7000

anni1016

anni

Intelligence

Agency

2 ms 13 s 9 h 7

anni1015

anni

Page 14: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Caratteristiche AES Il NIST, a seguito delle numerose critiche mosse al DES, fu

costretto a indire, nel 1997, un concorso per stabilire un nuovo algoritmo che potesse diventare un punto di riferimento per la sicurezza e che fosse in grado di sostituire il triplo-DES ritenuto abbastanza valido.

Il NIST stabilì perciò i requisiti:1. cifrario a chiave simmetrica a blocchi;2. lunghezza della chiave tra 128 e 256 bit;3. lunghezza del testo in chiaro 128 (anche da 64 a 256

bit);4. permettere l’implementazione su smart-card;5. disponibile a livello mondiale senza limitazioni (royalty-

free);

Page 15: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Criteri di valutazione: Sicurezza

Inoltre il NIST nella valutazione degli algoritmi ha:

1. confrontato la sicurezza del singolo algoritmo con tutti gli altri in gara;

2. controllato che l’output (testo cifrato) non derivasse da una permutazione casuale del blocco in input;

3. controllato che la sicurezza derivasse da una buona base matematica.

Page 16: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Criteri di valutazione: Utilizzo delle risorse

Per stabilire il costo computazionale il NIST prese in considerazione:

1. la grandezza del codice;

2. la memoria utilizzata;

3. il tempo di calcolo (efficienza);

4. l’implementazione in modo sicuro ed efficiente in diversi ambienti.

Page 17: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Algoritmi finalistiNome dell'algoritmo Proponente(i)

MARS IBM

RC6 Ron Rivest, 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

Page 18: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Caratteristiche degli algoritmi:RC6

RC6:

1. è un’algoritmo di dimensioni contenute e semplice;

2. facile da implementare in modo compatto sia in software che in hardware;

3. non utilizza tavole di sostituzione (s-box);

4. la rotazione dei dati dipende dalla loro quantità;

5. è veloce soprattutto sulle piattaforme che supportano efficientemente le operazioni di rotazione e moltiplicazione.

Page 19: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 - Notazione

E’ un cifrario a blocchi parametrico in cui si ha:

w - Lunghezza in bit delle parole da cifrare, w>0 solitamente 32r - Numero di iterazioni (o round) solitamente 20b - Lunghezza della chiave in byte [0,32]Vengono usate come operazioni fondamentali le seguenti: Moltiplicazione di interi mod 2w + Addizione di interi mod 2w (senza riporto). XOR bitwise<<< Rotazione ciclica a sinistra.>>> Rotazione ciclica a destra.La parte non lineare del cifrario consiste in rotazioni data-depending

Page 20: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 – Espansione chiaveFase 1- Espansione della chiave:Viene costruito un vettore di 2r+4 parole di w bit S[0,..,2r+3]. Nel fare ciò vengono usate due costanti “magiche”:

Pw=Odd[(e-2)2w] Qw=Odd[(Φ-1)2w]

dove: [e e Φ dipendono dalla lunghezza della chiave]Odd(x) è l’intero dispari più vicino a x,

e è la base dei logaritmi naturali Φ è il numero aureo (1+√5)/2=1.618033988740…Nota:

e =2.718281828459Φ interviene nella Teoria del Caos, dove sembra essere il numero più caotico che esista.Φ è il rapporto fra la diagonale e il lato del pentagono

regolare.

Page 21: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 – Costanti magiche

In particolare nella seguente tabella vengono riportati i valori di Pw e Qw in esadecimale per w = 16, 32, 64

W 16 bit 32 bit 64 bit

Pw B7 e1 b7 e1 51 63 b7 e1 51 62 8° ed 2a 6b

Qw 9e 37 9e 37 79 b9 9e 37 79 b9 7f 4a 7c 15

Page 22: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 – Espansione chiave1. La chiave k[0…b-1] di b byte viene convertita in parole di w bit → L[0…c-1] dove c = 8b/w eventualmente L[c-1] contiene 0

[quante volte sta la chiave nel testo da cifrare]2. Inizializzazione

for i=b-i downto 0 do L[i/u]=(L[i/u]<<<8)+k[i]3. Creazione di una tabella S (espansione vera e propria):

s[0]=Pwfor i=1 to 2r+3 do S[i]=S[i-1]+Qw [solitamente max (i) =43]i=j=A=B=0v = 3 max(c,2r+4) [num dei round e num vedi sopra]for s=1 to v do [v = 132 con 2r+4=44]

A=S[i]=(S[i]+A+B) <<< 3 [al primo ciclo s(0)=Pw]B=L[j]=(L[j]+A+B) <<< (A+B) [al primo passaggio B=0]i=(i+1) mod (2r+4) [tutti e due ricominciano almeno ]j=(j+1) mod c [3 volte da 0(il più grande)]

Page 23: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 - CifraturaL’input consiste in quatto registri A,B,C,D di w bit, l’output consiste nei medesimi quattro registri.Cifratura:B = B+S[0]D = D+S[1]For i=1 to r do

t = (B (2B+1)) <<< log w [=2B2+B] 6 addizioniu = (D (2D+1)) <<< log w [=2D2+D] 2 “”A = ( (A t) <<< u ) + S[2*i] 2 “quadrati”C = ( (C u) <<< t ) + S[2*i+1] 2 “<<< 5”(A,B,C,D) = (B,C,D,A) 2 “<<< variabile”

A = A+S[2r+2] [2r+2=42] NB log232=5C = C+S[2r+3] [2r+3=43]

Page 24: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6: Iterazione

55

ff

A B C D

<<<<<<

<<< <<<

S[2i] S[2i+1]

A B C D

t u

Page 25: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Iniettività B*(2B+1) mod 2w

Prova: per assurdo.

Se B ≠ C ma B * (2B + 1) = C * (2C + 1) mod 2W

allora (B - C) * (2B + 2C + 1)=0 (mod2w)

Ma (B - C) è diverso da zero e (2B + 2C + 1) è dispari;

per cui il loro prodotto non può essere zero!!

Page 26: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 - DecifraturaL’algoritmo di decifratura prende in input il testo cifrato memorizzato nei quatto registri A,B,C,D di w bit, l’output consiste nei medesimi quattro registri con memorizzato il testo in chiaro.Decifratura:C = C-S[2r+3]A = A-S[2r+2]For i=r downto 1 do

(A,B,C,D)=(B,C,D,A)u = (D (2D+1)) <<< log wt = (B (2B+1)) <<< log wC = ( (C-S[2*i+1]) >>> t) uA = ( (A-S[2*i]) >>> u) t

D = D-S[1]B = B-S[0]

Page 27: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Compatibilità RC6 (es. CPU a 8 bit)

Le operazioni sopra esposte possono essere implementate su un processore a 8 bit come segue:

1. L’addizione a 32 bit può essere computato con 4 addizioni a 8 bit con riporto (ADDC);

2. L’ XOR a 32 bit può essere computato con 4 XOR a 8 bit (XRL);3. Un quadrato a 32 bit può essere computato mediante 6

moltiplicazioni (MUL) (a noi interessano solo i 32 bit meno significativi) di stringhe di 8 bit ed 11 addizioni con riporto (ADDC);

4. Per quanto riguarda la rotazione ciclica a sinistra di 5 bit su stringa di 32 bit, può essere convertita in una rotazione a destra di 1 bit di una stringa di 32 bit, eseguita 3 volte e successivamente la permutazione dei byte risultanti (vedi figura). La rotazione a destra di 1 bit è implementata mediante 4 rotazioni ad 8 bit (RRC)

Page 28: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Implementazione “<<< 5”x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11…….. x32

x6 x7 x8 x9 x10 x11 x12 x13 x14 …….. x5

x30 x31 x32 x1 x2 x3 x4 x5 x6 x7…….. x29

x30… x5 x6… x13 x14… x21 x22… x29

x30… x5x22… x29x14… x21x6… x13

Permutazione byte

x6 x7 x8 x9 x10 x11 x12 x13 x14 …….. x5

“<<5”

“>>3”

Page 29: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Implementazione “<<<Z”

Generalizzando, si può procedere nello stesso modo con qualunque scorrimento a sinistra (quelli non predicibili data-depending), usando però la seguente notazione:

Calcolare z’ = (ultimi 5 bit di z) mod 8

Se z’ = 1,2,3,4 → z’ volte “<<<1”

Se z’ = 5,6,7 → 8 - z’ volte “>>>1”

Poi, eseguire la “permutazione byte” in genere < 2 shift

N.B. Ogni permutazione puo essere controllata mediante i salti (JB)

Page 30: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Implementazione “<<<Z”

Motivazione:

- Se z è multiplo di 8 è possibile effettuare una rotazione ciclica a sinistra di z bit con la sola permutazione dei 4 bytes quindi non occorrono operazioni di “<<<”

- Se z non è multiplo di 8 allora si può scrivere così:

z =8k+z’ con k ≥ 0 e 1 ≤ z’ ≤ 7

Il valore z’ è l’equivalente decimale di 3 bit meno significativi di z.

E’ necessario eseguire k rotazioni cicliche sui 4 byte per ottenere la sequenza giusta su cui effettuare la rotazione ciclica a sinistra di z’ bit per concludere l’operazione.

Page 31: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Java Borland C Assembly

Chiave 110000 2300 ~1000

Cifratura 16200 616 254

Decifratura 16500 566 254

Velocità di calcolo

Meno di due clocks per bit del testo in chiaro !

Page 32: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Sicurezza RC6La sua forza crittografica dipende dal pesante utilizzo delle rotazioni dipendenti dai dati, le quali non permettono di collezionare statistiche ed evitano attacchi di crittoanalisi sia differenziale che lineare, l’unico consentito è la ricerca esaustiva (forza bruta) il quale comporta un numero di operazioni pari a MIN(28b,21408)

Nota: Differenziale : Il metodo si basa sull'analisi delle differenze tra

due testi in chiaro cifrati con la stessa chiave.L'utilizzo di questa tecnica ha portato gli studiosi Biham e Shamir al successo nella forzatura dell'algoritmo DES.Lineare : è un attacco che usa testi in chiaro conosciuti. Permette di conoscere bit della chiave essendo noti sia il testo in chiaro che crittogramma corrispondente usando un’approssimazione lineare.

Page 33: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Sicurezza: Attacchi lineariUna stima fatta da Rivest sul numero di coppie di testi in chiaro / testi cifrati occorrenti per un attacco lineare.

(Solo 2128 di tali coppie sono disponibili.)

Rounds Coppie

8 247

12 283

16 2119

20 RC6 2155

24 2191

Irrealizzabile

Page 34: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Sicurezza: Attacchi differenzialiUna stima fatta da Rivest sul numero di coppie di testi in chiaro occorrenti per un attacco differenziale.

(Solo 2128 di tali coppie sono disponibili.)

Rounds Coppie

8 256

12 297

16 2190

20 RC6 2238

24 2299

Irrealizzabile

Page 35: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Esempio di cifraturaTesto in chiaro

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Chiave usata

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Testo cifrato

8f c3 a5 36 56 b1 f7 78 c1 29 df 4e 98 48 a4 1e

Testo in chiaro

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Chiave usata

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Testo cifrato

6c d6 1b cb 19 0b 30 38 4e 8a 3f 16 86 90 ae 82

Testo in chiaro

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Chiave usata

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Testo cifrato

8f 5f bd 05 10 d1 5f a8 93 fa 3f da 6e 85 7e c2

Page 36: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

Valutazione esempio

Si può notare nella figura sopra esposta 2 importanti rilievi:

1. La possibilità di inserire la chiave nulla, cioè, quella chiave il cui valore per ogni suo bit è 0, non sempre possibile in altri algoritmi;

2. La cifratura, quindi il testo cifrato, dipende anche dalla lunghezza della chiave infatti come si può vedere a “parita” di chiavi nulle il testo cifrato cambia.

Page 37: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

RC6 Vs DESIn conclusione possiamo riassumere le caratteristiche più significative che l’RC6 ha in più rispetto al DES:

1. Il N° delle chiavi è di gran lunga maggiore;

2. Non usa s-box quindi non nasconde trapdoor;

3. Usa rotazioni data-depending;

4. Resiste ad attacchi lineari e differenziali;

5. Si basa su versioni precendenti ampiamente criptoanalizzate.

Page 38: Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo.

BibliografiaUna trattazione a carattere algoritmico può essere trovata in:

→Cryptographic Hardware and Embedded Systems – CHES 2001

– Cetin K. Koc, David Naccache, Christof Paar

→Applied Cryptography – Bruce Schneier – John wiley e Son

Fra i siti in cui trovare informazioni cito

→ http://theory.lcs.mit.edu/

Ed inparticolare:

→ http://theory.lcs.mit.edu/~rivest

In cui è possibile trovare un’enorme pagina di link.