1

Crittografia

MITTENTE DESTINATARIO

messaggio

chiave-1

crittografia

messaggio

decrittografia

chiave-2

messaggio cifrato

2

Crittografia a chiave privata

3

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

4

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 tempo richiesto tempo richiesto(bit) a 1 decr/s a 106 decr/s

56 255 s = 1142 anni 10 ore128 2127 s ~ 1024 anni ~ 1018 anni168 2167 s ~ 1036 anni ~ 1030 anni

5

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

6

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

7

DES: schema complessivo

8

DES: schema dell'i-ma iterazione

9

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

10

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

11

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

12

Distribuzione delle chiavi• OOB (Out Of Band)

• key distribution center

13

Crittografia a chiave pubblica• proposta nel 1976 da Diffie e Hellman• usata per distribuire chiavi segrete e per la firma

digitale

Bob Alice

14

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

15

RSA (Rivest - Shamir - Adleman)• sviluppato nel 1977 da Rivest, Shamir, Adleman

• algoritmo a chiave pubblica più diffuso

EncryptionPlaintext: M<nCiphertext: C = Memodn

DecryptionCiphertext: CPlaintext: M = Cdmodn

Key GenerationSelect p, q p and q both primeCalculate n = p x qCalculate (n) = (p-1)(q-1)Select integer e gcd((n),e)=1; 1<e< (n)Calculate d de mod(n) = 1Public key KU = [e, n]Private key KR = [d, n]

16

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)

17

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

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

Global Public Elementsq prime number <q and primitive root of q

User A Key GenerationSelect private XA XA<qCalculate public YA YA = XAmodq

User B Key GenerationSelect private XB XB<qCalculate public YB YB = XBmodq

Generation of secret key by AK = (YB)XAmodq

Generation of secret key by BK = (YA)XBmodq

19

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

20

Diffie - Hellman: aspetti critici

• non protegge da attacchi di tipo replay

• possibile attacco man-in-the-middle

A M BYA

YM

YM

YB

• richiede pre-autenticazione

A BYA, firma A(YA)

YB, firma B(YB)

21

Uso della crittografia a chiave pubblica per l'autenticazione

Bob Alice

22

Firma digitale

• Garantisce che:– il messaggio è autentico– il messaggio è integro– il mittente non può disconoscere il messaggio

23

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

24

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

25

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