Crittografia
MITTENTE
DESTINATARIO
messaggio
messaggio
chiave-1
chiave-2
crittografia
decrittografia
messaggio cifrato
1
Crittografia a chiave privata
2
Crittoanalisi
• Ciphertext only
• algoritmo di crittografia
• testo cifrato
• Known plaintext
• algoritmo di crittografia
• testo cifrato
• una o più coppie testo in chiaro / testo cifrato
• Chosen plaintext
• algoritmo di crittografia
• testo cifrato
• messaggi in chiaro scelti dal criptoanalista con i
corrispondenti messaggi cifrati
3
Lunghezza delle chiavi private
• se l’algoritmo è ben progettato l’unico
attacco possibile è quello esaustivo
– numero medio di tentativi richiesti: 2N-1 con
N=lunghezza della chiave
• tempo medio di attacco
lungh. chiave
(bit)
tempo richiesto
a 1 decr/s
tempo richiesto
a 106 decr/s
56
128
168
255 s = 1142 anni
2127 s ~ 1024 anni
2167 s ~ 1036 anni
10 ore
~ 1018 anni
~ 1030 anni
4
Cipher Block Chaining Mode
• Produce un blocco di testo cifrato per ogni
blocco di testo in chiaro in input
• per evitare regolarità si fa in modo che il
blocco cifrato di ogni blocco dati dipenda
da tutto il testo in chiaro precedente
5
DES (Data Encryption Standard)
• sviluppato alla IBM, adottato dal NIST nel
1977 come standard per le applicazioni
governative e commerciali
• chiave da 56 bit, blocco dati da 64 bit
• efficiente in hardware (implementato in VLSI)
• molto studiato, non sono note debolezze
• violato nel 1998 con attacco esaustivo su
macchina special-purpose in meno di 3 giorni
6
DES: schema complessivo
7
DES: schema dell'i-ma iterazione
8
Triplo DES
• standardizzato per le applicazioni finanziarie nel
1985, dal 1999 incorporato nello standard DES
• tre esecuzioni del DES secondo uno schema EDE
• stessa resistenza del DES alla crittoanalisi
• tre chiavi da 56 bit equivalenti a una da 168 bit
9
AES (Advanced Encryption Standard)
• Call for proposal emessa dal NIST nel 1997
• specifiche:
– sicurezza almeno pari a quella del Triplo DES
– maggiore efficienza
– blocco dati da 128 bit, chiavi da 128/192/256 bit
• criteri di valutazione:
– sicurezza, efficienza, uso di risorse, adattabilità hw e sw,
flessibilità
• standard finale pubblicato nel 2001
10
Altri algoritmi a chiave privata
• IDEA (International Data Encryption Algorithm)
–
–
–
–
–
–
sviluppato nel 1991
blocco dati da 64 bit, chiave da 128 bit
operazioni: XOR, addizione e moltiplicazione a 16 bit
efficiente in software
finora appare altamente resistente alla crittoanalisi
usato nel PGP e in molti prodotti commerciali
• RC5
–
–
–
–
–
–
sviluppato da Ron Rivest (RC = Ron’s code)
algoritmo proprietario di RSA Data Security Inc.
adatto sia per hw che per sw
veloce (word oriented)
parametrizzabile (dimensione word, numero di round, lunghezza chiave)
adatto a smart card e dispositivi con ridotta memoria
11
Distribuzione delle chiavi
• OOB (Out Of Band)
• key distribution center
12
Crittografia a chiave pubblica
• proposta nel 1976 da Diffie e Hellman
• usata per distribuire chiavi segrete e per la
firma digitale
Bob
Alice
13
Requirements
• deve essere computazionalmente semplice per un
utente B generare una coppia di chiavi KUb, KRb
• deve essere computazionalmente semplice per un
mittente A ottenere il testo cifrato C = EKUb(M)
• deve essere computazionalmente semplice per il
ricevente B recuperare il testo originale M = DKRb(C)
• deve essere computazionalmente complesso per un
impostore determinare KRb da KUb
• deve essere computazionalmente complesso per un
impostore ricavare M da KUb e C
• le chiavi KUb e KRb devono avere funzionalità
reciproche
14
RSA (Rivest - Shamir - Adleman)
• sviluppato nel 1977 da Rivest, Shamir, Adleman
• algoritmo a chiave pubblica più diffuso
Encryption
Plaintext:
M<n
Ciphertext: C = Memodn
Decryption
Ciphertext: C
Plaintext:
M = Cdmodn
Key Generation
Select p, q
p and q both prime
Calculate n = p x q
Calculate (n) = (p-1)(q-1)
Select integer e
gcd((n),e)=1; 1<e< (n)
Calculate d
de mod(n) = 1
Public key
KU = [e, n]
Private key
KR = [d, n]
15
RSA: un esempio
•
•
•
•
Si scelgono due numeri primi p=7, q=17
si calcola n = pq = 7 x 17 = 119
si calcola (n) = (p-1)(q-1) = 6x16 =96
si sceglie e < (n), relativamente primo con (n),
e=5
• si determina d tale che de mod 96 = 1 e d<96,
d = 77 (infatti 77x5 = 385 = 96x4+1)
16
Sicurezza di RSA
• Possibile attacco esaustivo: nella scelta di e e
d trade-off tra sicurezza e prestazioni
• Crittoanalisi: fattorizzazione di n
– 1977: sfida degli inventori su un testo criptato con
una chiave pubblica n di 129 cifre decimali (circa
428 bit)
– 1994: sfida vinta su Internet con 1600 calcolatori in
otto mesi di lavoro
– attualmente chiavi di 1024 bit sono considerate
sufficientemente sicure
17
Diffie - Hellman
• primo algoritmo a chiave pubblica proposto (’76)
• tecnica per lo scambio di chiavi segrete
• si basa sulla difficoltà di calcolare il log discreto
q

Global Public Elements
prime number
<q and  primitive root of q
User A Key Generation
Generation of secret key by A
Select private XA
XA<q
K = (YB)XAmodq
Calculate public YA YA = XAmodq
User B Key Generation
Generation of secret key by B
Select private XB
XB<q
K = (YA)XBmodq
Calculate public YB YB = XBmodq
Diffie - Hellman: un esempio
• Si scelgono un numero primo q=71 e una sua
radice primitiva =7
• A sceglie la chiave privata XA=5 e calcola la
chiave pubblica YA = 75mod71 = 51
• B sceglie la chiave privata XB=12 e calcola la
chiave pubblica YB = 712mod71 = 4
• A e B si scambiano le chiavi pubbliche
• A calcola la chiave segreta K = 45mod71 = 30
• B calcola la chiave segreta K = 5112mod71 = 30
19
Diffie - Hellman: aspetti critici
• non protegge da attacchi di tipo replay
• possibile attacco man-in-the-middle
A
YA
YM
M
YM
B
YB
• richiede pre-autenticazione
A
YA, firma A(YA)
B
YB, firma B(YB)
20
Uso della crittografia a chiave
pubblica per l'autenticazione
Bob
Alice
21
Firma digitale
• Garantisce che:
– il messaggio è autentico
– il messaggio è integro
– il mittente non può disconoscere il messaggio
22
Funzione di hash
• Produce un'impronta del messaggio
• Deve possedere le seguenti proprietà:
–
–
–
–
–
accetta un messaggio di dimensione variabile
produce un digest di lunghezza fissa
è veloce da calcolare
è difficilmente invertibile
è estremamente improbabile che messaggi
diversi generino lo stesso digest
23
Esempi di funzioni di hash
• MD5 (Message Digest 5)
– sviluppata da Ron Rivest
– digest da 128 bit
– era la più usata, ora non più considerata sicura
• SHA (Secure Hash Algorithm)
– sviluppata dal NIST nel 1993, SHA-1 revised
version nel 1995
– digest da 160 bit
– ogni bit del digest è funzione di tutto l'input
24
Uso della crittografia a chiave pubblica
per la distribuzione di chiavi segrete
• Bob vuole comunicare con Alice in forma
riservata
• Bob prepara il messaggio
• lo cripta usando la crittografia a chiave privata
con una chiave di sessione
• cripta la chiave di sessione usando la crittografia
a chiave pubblica con la chiave pubblica di Alice
• acclude al messaggio la chiave di sessione
criptata e invia il messaggio
25