Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo

Click here to load reader

download Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo

of 38

  • date post

    02-May-2015
  • Category

    Documents

  • view

    243
  • download

    14

Embed Size (px)

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

  • Slide 1
  • Algoritmi crittografici AES (Advanced Encryption Standard) Elennio Paolo
  • Slide 2
  • Argomenti 1.Definizione di crittografia 2.Definizione cifrario Perfetto Computazionalmente sicuri Condizionalmente sicuri 3.Problema della standardizzazione 4.AES Requisiti Criteri di valutazione Uso delle risorse Es. algoritmo simmetrico (RC6)
  • Slide 3
  • 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
  • Slide 4
  • Definizioni generali La crittografia la tecnica con la quale, attraverso luso 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)
  • Slide 5
  • Definizioni generali Nel 1949 C. Shannon pubblic un articolo che diede inizio a quella che oggi viene chiamata Teoria dellinformazione 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 chiaro C : insieme finito di testi cifrati K : insieme delle possibili chiavi FC : funzione di cifratura FD : funzione di decifratura
  • Slide 6
  • 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.
  • Slide 7
  • Definizioni generali In realt esistono anche cifrari: 1.Computazionalmente sicuri La Teoria dellinformazione 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 linattaccabilit 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)
  • Slide 8
  • 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 2 n con probabilit similare altrimenti sarebbero predicibili.
  • Slide 9
  • 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.
  • Slide 10
  • Standardizzazione Svantaggi: 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 dellattaccante pu essere utilizzato per venire a conoscenza di altri dati su altre macchine quindi pi conveniente.
  • Slide 11
  • Introduzione - AES Fino ad oggi il DES, inventato dallIBM e poi modificato dallNSA, ha rappresentato lo standard per la cifratura e lautenticazione 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 2 56 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 allutilizzo delle S-box(1) nelle procedure di cifratura e decifratura molti sospettano che le strutture nascondano delle Trapdoor(2)
  • Slide 12
  • Introduzione - AES Note: (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 dellinformazione diventa facile calcolarne linversa.
  • Slide 13
  • 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 Hacker5 h37 anni 10000 anni 700mila anni 10 27 anni PMI2 s35 h1 anno 70000 anni 10 19 anni Grossa Impresa 2 ms2 m9 gg7000 anni 10 16 anni Intelligence Agency 2 ms13 s9 h7 anni 10 15 anni
  • Slide 14
  • 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 limplementazione su smart-card; 5.disponibile a livello mondiale senza limitazioni (royalty- free);
  • Slide 15
  • 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 loutput (testo cifrato) non derivasse da una permutazione casuale del blocco in input; 3.controllato che la sicurezza derivasse da una buona base matematica.
  • Slide 16
  • 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.limplementazione in modo sicuro ed efficiente in diversi ambienti.
  • Slide 17
  • Algoritmi finalisti Nome dell'algoritmoProponente(i) MARSIBM RC6Ron Rivest, RSA Laboratories RIJNDAELJoan Daemen, Vincent Rijmen SERPENTRoss Anderson, Eli Biham, Lars Knudsen TWOFISHB. Schneider, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson
  • Slide 18
  • Caratteristiche degli algoritmi: RC6 RC6: 1. unalgoritmo 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.
  • Slide 19
  • RC6 - Notazione E un cifrario a blocchi parametrico in cui si ha: w- Lunghezza in bit delle parole da cifrare, w>0 solitamente 32 r - Numero di iterazioni (o round) solitamente 20 b - Lunghezza della chiave in byte [0,32] Vengono usate come operazioni fondamentali le seguenti: Moltiplicazione di interi mod 2 w + Addizione di interi mod 2 w (senza riporto). XOR bitwise > Rotazione ciclica a destra. La parte non lineare del cifrario consiste in rotazioni data-depending
  • Slide 20
  • RC6 Espansione chiave Fase 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)2 w ] Qw=Odd[(-1)2 w ] dove:[e e dipendono dalla lunghezza della chiave] Odd(x) lintero 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.
  • Slide 21
  • RC6 Costanti magiche In particolare nella seguente tabella vengono riportati i valori di Pw e Qw in esadecimale per w = 16, 32, 64 W16 bit32 bit64 bit PwPw B7 e1b7 e1 51 63b7 e1 51 62 8 ed 2a 6b QwQw 9e 379e 37 79 b99e 37 79 b9 7f 4a 7c 15
  • Slide 22
  • RC6 Espansione chiave 1. La chiave k[0b-1] di b byte viene convertita in parole di w bit L[0c-1] dove c = 8b/w eventualmente L[c-1]