Diapositiva 1 - Unicam

Crittografia
moderna:
i principali algoritmi
Storia della crittografia
Nel 1883 Kerckhoffs pubblica La Cryptographie Militaire ove
enuncia il principio di separazione tra chiave ed algoritmo
(Principio di Kerkchoffs):
“La sicurezza di un sistema crittografico è
basata esclusivamente sulla conoscenza
della chiave; in pratica si presuppone noto
a priori l’algoritmo di cifratura e
decifratura”.
Storia della crittografia
Shannon nel 1948 pubblicò “A Mathematical Theory of
Communication”, un articolo destinato a fare epoca.
L’idea geniale di Shannon fu che il contenuto di
un’informazione non ha nulla a che vedere col contenuto del
messaggio, ma col numero di 0 e 1 necessari per trasmetterlo.
Per anni la regola generale era stata di creare algoritmi semplici
e di impiegare chiavi molto lunghe per rendere indecifrabile il
messaggio. Ma la potenza di calcolo raggiunta minava questa
concezione di crittografia: essa stava volgendo rapidamente
verso nuove “regole guida” che avrebbero portato alla
crittografia moderna.
Crittografia moderna
Partiamo dal considerare le proprietà che dovrebbe possedere
una chiave segreta per poter essere realisticamente utilizzata:
la chiave deve essere il più breve possibile,
la chiave deve poter essere riutilizzata più volte,
la chiave non può essere perfettamente
casuale.
Dunque l’onere del garantire la sicurezza passa all’algoritmo
che deve essere complicato in quanto deve cercare di generare
testi casuali utilizzando un algoritmo deterministico e partendo
dal testo in chiaro e da una chiave segreta.
Crittografia moderna
Uno dei concetti su cui si basa la crittografia moderna è quello
di One-way-trapdoor function.
Cioè una funzione matematica f, utilizzata per cifrare i dati,con
le seguenti 3 proprietà:
 f è facile da calcolare;
 f è praticamente impossibile (matematicamente
parlando) da invertire, ovvero calcolare nella
direzione inversa;
 f è facile da invertire se si conosce una
informazione ulteriore, una chiave segreta
(trapdoor).
DES: storia
Nel 1972 negli Stati Uniti il National Bureau of Standard
(NBS) - una parte dell US Department of Commerce - iniziò un
programma per la stesura di uno standard per la protezione dei
dati.
L’Institute for Computer Science and Tecnology (ICST), una
delle maggiori unità operative dell’NBS, produsse delle linee
guida e degli standard.
Fu scelto uno standard che richiedeva specificazioni complete
di funzioni di base e suoi formati, mantenendo comunque
l’indipendenza dall’implementazione fisica. Fu così definito
l’ambiente in cui verrà sviluppato il sistema che poi diventerà
il DES (Data Encryption Standard).
DES: storia
La pubblicazione del 15 Maggio 1973 suggeriva dei requisiti
che lo standard doveva possedere:
un alto grado di sicurezza;
specifica completa e semplicità di comprensione;
segretezza basata sulla chiave e non sull’algoritmo;
disponibilità per tutti gli utenti;
adattabilità per diverse applicazioni;
implementabilità economica su dispositivi differenti;
efficienza;
possibilità di essere certificato;
esportabilità.
DES: storia
L’IBM sottomise il suo algoritmo all’NBS il 27 Agosto 1974.
L’NBS chiese che fosse la National Security Agency (NSA) a
testare l’algoritmo riguardo ad un insieme informale di
requisiti. Contemporaneamente richiese che l’IBM accordasse
diritti non esclusivi e senza copyright per costruire e vendere
apparecchiature che implementassero l’algoritmo.
Nel 1975, nonostante le pressioni, l’NBS continuò a valutare
l’algoritmo, le richieste di sicurezza nel settore pubblico e
privato e le alternative allo standard.
Nell’ottobre dello stesso anno Hellman presentò le sue critiche
asserendo che, a dispetto delle 256 chiavi necessarie per un
attacco a forza bruta dell’ algoritmo, la metà di esse avrebbe
permesso in media la violazione di DES.
DES: storia
Per questo motivo l’NBS organizzò due workshop allo scopo
di analizzare eventuali tranelli e punti oscuri dell’algoritmo, e
per valutare la possibilità di incrementare la lunghezza della
chiave. Ai workshop vennero invitati implementatori,
progettisti, acquirenti e matematici affinché si potesse dar vita
ad uno standard che soddisfacesse tutte le richieste da parte
degli addetti ai lavori.
Il risultato fu la approvazione di DES come standard il cui
algoritmo non presentava alcun tipo di tranello. L’NBS
evidenziò, tuttavia, la necessità di rivedere il DES
periodicamente.
L’NBS continuò a valutare l’algoritmo DES che venne
pubblicato definitivamente il 15 gennaio 1977.
DES: storia
Successivamente l’RSA Data Security (fondata nel 1982 da
Rivest, Shamir e Adleman, gli autori dell’RSA), indisse delle
vere e proprie gare, dette challenges, per rompere il DES. Tale
società offriva 10000 dollari a chi per primo rompeva la sua
challenge a patto che venisse rotta entro il 25% del miglior
tempo precedente.
nel Luglio del 1997 furono impiegati 39 giorni e fu testato il 24%
di tutte le possibili chiavi;
nel Luglio del 1998 una società Americana, l’EFF, spendendo
250000 dollari riuscì a costruire una macchina per rompere il DES
impiegando solo 56 ore;
nel Gennaio 1999 sono stati impiegati 22 ore e 15 minuti testando
245 miliardi di chiavi per secondo.
DES: funzionamento
TESTO IN CHIARO
CHIAVE
IP
64 bit
56 bit
ITERAZIONE 1
64 bit
…
SCHEDULAZIONE
CHIAVI
…
48 bit
ITERAZIONE 16
64 bit
SCAMBIO DX SX
64 bit
TESTO CIFRATO
IP1
DES: IP
Sia x una stringa binaria di
testo in chiaro lunga 64 bit.
L’algoritmo costruisce una
stringa binaria x0 di 64 bit
tramite la permutazione
iniziale fissata IP:
X0=IP(x)=L0 R0.
Dove L0 e R0 sono due stringhe binarie che comprendono
rispettivamente i primi e gli ultimi 32 bit della stringa x0.
DES: i-esima iterazione
Li  R i 1
R i  Li1  f  R i1 , ki 
DES: funzione f
DES: E e P
DES: S-box
Dato Bi (l’input a 6 bit dell’S-box Si), il primo e l’ultimo bit di
Bi vengono interpretati come indice di riga, mentre i bit centrali
come indice di colonna.
Si consulta la tabella Si alle coordinate prescritte e il valore in
uscita dall’S-box è l’equivalente binario del decimale trovato.
DES: S-box
DES: schedulazione delle chiavi
DES: schedulazione delle chiavi
LS1 è uno shift ciclico a sinistra di una o due posizioni a
seconda del valore di i (lo shift riguarda una sola posizione alle
iterazioni 1, 2, 9 e 16 e due posizioni a tutte le altre iterazioni).
DES: weak key
Una weak key DES è una chiave k tale che Ek(Ek(x))=x per
tutti gli x, il che equivale a dire che è un’involuzione.
DES: semi-weak key
Una coppia di semi-weak key DES è una coppia (h,k) tale che
Eh(Ek(x))=x per ogni x.
Cifratura a blocchi
ECB. I dati vengono suddivisi in blocchi di 64 bits ed ogni
blocco viene cifrato singolarmente indipendentemente dal
precedente.
CBC. In questa modalità, ogni blocco di testo, dopo essere
stato cifrato in modalità ECB, viene sottoposto ad un ulteriore
operazione di xor con il successivo blocco ancora da cifrare.
CFB/OFB. Questa modalità permette di cifrare blocchi in
chiaro inferiori a 64 bits. Il testo in chiaro viene sottoposto ad
un’operazione di xor con i dati uscenti dall’algoritmo, generati
utilizzando inizialmente un blocco casuale di 64 bits, chiamato
Shift Register.
CTR. A ciascun blocco del testo in chiaro viene applicato uno
xor con un contatore crittografico.
TDES
E’ altamente improbabile che, per una coppia di chiavi (k, h)
esista una chiave t tale che, per ogni testo in chiaro x
DESk (DESh (x))=DESt (x).
Da questo risultato nasce l’algoritmo Triplo DES:
y = DESk (DES-1h (DESk (x))).
Lo svantaggio è che risulta meno efficiente del DES singolo di
un fattore 3.
Coppersmith ha osservato però che un attacco di forza bruta
per la ricerca della chiave è dell’ordine di 2112 = 5×1035 .
AES
Il 2 gennaio 1997 il National Institute of Standards and
Technology (ex NBS) propose un bando per la realizzazione
del nuovo algoritmo di cifratura a blocchi: l’Advanced
Encryption Standard (AES).
I requisisti del nuovo standard erano molto restrittivi. Doveva
essere un algoritmo a blocchi, doveva gestire chiavi di 128,
192 e 256 bit. Doveva essere sicuro, veloce sia in hardware che
in software e funzionare anche con apparecchiature come le
smartcard. Quindici diversi algoritmi vennero presentati da
partecipanti provenienti da sette nazioni.
Il 2 ottobre 2000, il NIST ha annunciato che Rijndael era stato
selezionato per diventare la base dell’AES.
AES
AES opera utilizzando matrici di 4×4 byte chiamate Stati
(States). 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.
Tranne l’ultimo round in cui si salta il MixColumns.
IDEA
IDEA (International Data Encryption Algorithm) è nato nel
1991sotto il nome di IPES (Improved Proposed Encryption
Standard), ed è stato progettato da due famosi ricercatori in
Svizzera: Xuejja Lai e James L. Massey. Come il DES è un
codice cifrato a blocchi di 64 bit, la differenza sta nel fatto che
questa volta la chiave è di 128 bit.
La cifratura con IDEA comporta una divisione del blocco di 64
bit del testo normale in 4 sottoblocchi di 16 bit. Ogni
sottoblocco subisce 8 passi in cui sono coinvolte 52 sottochiavi
diverse a 16 bit ottenute dalla chiave a 128 bit. Le sottochiavi
sono generate in questo modo.
IDEA
1. La chiave a 128 bit è divisa in 8 blocchi di 16 che
costituiscono le prime 8 sottochiavi .
2. Le cifre della chiave a 128 sono spostate di 25 bit a sinistra
in modo da generare una nuova combinazione, il cui
raggruppamento ad 8 bit fornisce le prossime 8 sottochiavi .
3. Il secondo passo è ripetuto finché non sono generate tutte le
52 sottochiavi.
IDEA è al momento il cifrario a chiave segreta più utilizzato
per quanto riguarda i software commerciali di crittografia vista
la sua velocità di codifica e decodifica e la sua elevata
sicurezza.
Scambio chiavi
Sebbene sono ormai disponibili diversi sistemi di cifratura
sufficientemente sicuri, permane un altro problema: la
distribuzione delle chiavi.
Prima di poter comunicare, infatti, è necessario stabilire una
chiave comune con cui i messaggi verranno cifrati e decifrati,
ma la distribuzione della chiave spesso presenta notevoli
problemi. Per concordare una chiave con il proprio
interlocutore c’è bisogno di mettersi preventivamente in
contatto con lui. Se lo scambio della chiave avviene tramite un
canale non sicuro, anche i messaggi che verranno cifrati con
essa sono soggetti a intercettazione e decifrazione.
Due lucchetti
Alice mette il messaggio in una valigetta e la chiude con un
lucchetto, la chiave del lucchetto resta in mano ad Alice.
Bob riceve la valigetta, che ovviamente nessuno ha potuto
aprire poiché chiusa con il lucchetto di Alice, nemmeno Bob
può aprire la valigetta, ma può aggiungere pure lui un
lucchetto e tenere la chiave con sé
Quindi Bob rispedisce indietro la valigetta, che ora ha due
lucchetti, ad Alice la quale non può rimuovere il lucchetto di
Bob ma può togliere quello che lei ha inizialmente messo.
La valigetta, che ora ha solo un lucchetto, viene rispedita a Bob
che può agevolmente togliere il lucchetto (il suo) e leggere il
messaggio contenuto nella valigetta
Diffie-Hellman
Il metodo di Diffie-Hellman si basa sulla presunta difficoltà del
logaritmo discreto ed opera in questo modo.
Alice e Bob scelgono di comune accordo due numeri: un
numero primo grande p e un'altro numero d (che deve
rispettare alcune restrizioni, tra le quali d < p).
Alice sceglie un numero intero a minore di p e trasmette a Bob
il valore da (mod p).
Bob sceglie un numero intero b minore di p e trasmette ad
Alice il valore db (mod p).
Alice calcola dab (mod p) = (db (mod p))a (mod p).
Bob calcola dab (mod p) = (da (mod p))b (mod p).
Diffie-Hellman
La chiave che entrambi devono usare è dab, in quanto è uguale
per entrambi e solo loro hanno questo risultato.
Una terza persona potrebbe aver intercettato le comunicazioni
di Alice e Bob, e quindi avere a disposizione da (mod p) e db
(mod p) ma con questi valori non è in grado di calcolare in
modo rapido dab (mod p).
Poiché la generazione della chiave è affidata sia ad Alice sia a
Bob entrambi devono essere disponibili ogni volta che viene
creata una chiave: ciò non sempre è possibile o conveniente.
Fu così che Diffie non si accontentò ma continuò la ricerca di
un metodo meno macchinoso di quello già trovato.
Massey–Omura
Tutti gli utenti di questo crittosistema scelgono di comune
accordo un numero primo grande p, che viene reso pubblico.
Ciascun utente poi sceglie due interi d ed e con la proprietà che
de = 1 (mod (p-1)).
L’utente A sceglierà dunque da ed ea e B sceglierà db ed eb.
Se A vuole spedire a B il messaggio M
A calcola M1=Mda (mod p) e lo spedisce a B (A mette il suo
lucchetto),
B calcola M2=M1db (mod p) e lo spedisce ad A (B mette il suo
lucchetto),
A calcola M3=M2ea (mod p) e lo spedisce a B (A toglie il suo
lucchetto)
B calcola M3=M2eb (mod p) e questo coincide con M.
RSA
Vediamo schematicamente come un utente A può mandare un
messaggio segreto a B usando il metodo RSA.
Innanzitutto B sceglie in modo casuale:
due primi titanici p, q, calcola N = pq e
  N  = (p - 1)(q - 1);
due naturali d ed e, l’uno inverso dell’altro modulo   N  .
Cioè tali che d  e  1(mod (N)).
Poi rende noti N ed e: questo forma la sua chiave pubblica.
Tiene invece gelosamente segreto d: la sua chiave privata.
RSA
L’utente A per mandare un messaggio a B compie allora le
seguenti operazioni:
1. eleva ogni unità del messaggio, a, ad e modulo N
a  a e (modN) = b;
2. invia a B ogni unità b così ottenuta.
Per decodificare il messaggio B calcola
b  a
d

e d
 a  mod N  .
RSA
Ciò che ottiene B è proprio M grazie ad un classico teorema di
Fermat-Eulero, che in questo caso, afferma che:
(a e )d  a (modN).
Infatti da
d  e  1(mod (N))
si ha che
d  e = t (N) + 1
da cui
(a e )d  a ed  a (N)t+1  (a (N) ) t  a  a (modN).