CrittografiaCorso di Laurea Magistrale in Informatica

Introduzione alla Crittografia

Ugo Dal Lago

Anno Accademico 2018-2019

Crittografia Classica e Crittografia Moderna

I La Crittografia era, fino agli anni Ottanta, una formad’arte.

I Servivano creatività e intuizione, e non esistevano principicerti.

I Con alcuni contributi fondamentali arrivati alla fine deglianni Settanta, la Crittografia diventa una scienza.

I Ciò permise di andare oltre la crittografia classica, che sioccupava solamente di segretezza delle comunicazione.

I Si definirono protocolli per l’autenticazione di messaggi, loscambio di chiavi, la firma digitale, etc.

I Oggigiorno, con crittografia si fa riferimento a qualunquetecnica volta a garantire la sicurezza delle comunicazioni,delle transazioni e, in generale, del calcolo distribuito.

I Ma cosa vuol dire comunicazione sicura?I In questo capitolo cercheremo di capirlo, nel contempo

analizzando alcuni cifrari classici.

Crittografia Classica e Crittografia Moderna

I La Crittografia era, fino agli anni Ottanta, una formad’arte.

I Servivano creatività e intuizione, e non esistevano principicerti.

I Con alcuni contributi fondamentali arrivati alla fine deglianni Settanta, la Crittografia diventa una scienza.

I Ciò permise di andare oltre la crittografia classica, che sioccupava solamente di segretezza delle comunicazione.

I Si definirono protocolli per l’autenticazione di messaggi, loscambio di chiavi, la firma digitale, etc.

I Oggigiorno, con crittografia si fa riferimento a qualunquetecnica volta a garantire la sicurezza delle comunicazioni,delle transazioni e, in generale, del calcolo distribuito.

I Ma cosa vuol dire comunicazione sicura?I In questo capitolo cercheremo di capirlo, nel contempo

analizzando alcuni cifrari classici.

La Crittografia a Chiave SegretaI Partiamo da un particolare scenario, quello dei protocolli

volti a garantire a confidenzialità nello scambio dei dati tradue parti.

Enc Decm m

k kA

I La chiave è unica e deve essere preventivamente scambiatatra le parti.

I Formalmente, possiamo vedere uno schema di codificacome composto da tre spazi K,M e C e da una tripla dialgoritmi (Gen,Enc,Dec) dove

Gen : 1→ K Enc :M×K → C Dec : C × K →M

I Lo schema è corretto quando Dec(Enc(x, k), k) = x.

Il Principio di Kerchoff

I Prima di dare una definizione di sicurezza per uno schemadi codifica, occorre capire cosa possa fare l’avversario A.

I Secondo Kerchoff, A conosce il funzionamento interno diGen, Enc, Dec, quindi l’unico elemento che non conosceè la chiave k.

I Anche in uno scenario in cui A non conosca effettivamentelo schema di codifica, ha senso assumere che lo conosca,perché la conoscenza di A può cambiare nel tempo.

I Cambiare chiave è semplice, cambiare schema di codifica èmolto più complicato.

I Il postulato di Kerchoff è un principio e come tale non puòessere dimostrato.

I In passato, il Principio di Kerchoff è stato ripetutamenteignorato, con conseguenze devastanti.

Possibili Scenari di AttaccoI Ciphertext-Only Attack

I L’avversario A conosce solo un certo numero dicrittogrammi c1, . . . , cm quindi interferisce con lacomunicazione in modo passivo.

I Known-Plaintext AttackI L’avversario A conosce un certo numero di coppie

(m1, c1), . . . , (mk, ck), dove ci è il crittogrammacorrispondente a mi.

I L’attacco rimane passivo.I Chosen-Plaintext Attack

I L’avversario A comincia ad avere un ruolo attivo.I Può, in particolare, calcolare Enck(m)) = Enc(m, k) per

messaggi di sua scelta.I Chosen-Ciphertext Attack

I L’avversario A partecipa in modo ancora più attivo allacomunicazione, avendo accesso ad un “oracolo” Deck(·) perla decrittazione.

I Senza avere ovviamente accesso a k!

Possibili Scenari di AttaccoI Ciphertext-Only Attack

I L’avversario A conosce solo un certo numero dicrittogrammi c1, . . . , cm quindi interferisce con lacomunicazione in modo passivo.

I Known-Plaintext AttackI L’avversario A conosce un certo numero di coppie

(m1, c1), . . . , (mk, ck), dove ci è il crittogrammacorrispondente a mi.

I L’attacco rimane passivo.

I Chosen-Plaintext AttackI L’avversario A comincia ad avere un ruolo attivo.I Può, in particolare, calcolare Enck(m)) = Enc(m, k) per

messaggi di sua scelta.I Chosen-Ciphertext Attack

I L’avversario A partecipa in modo ancora più attivo allacomunicazione, avendo accesso ad un “oracolo” Deck(·) perla decrittazione.

I Senza avere ovviamente accesso a k!

Possibili Scenari di AttaccoI Ciphertext-Only Attack

I L’avversario A conosce solo un certo numero dicrittogrammi c1, . . . , cm quindi interferisce con lacomunicazione in modo passivo.

I Known-Plaintext AttackI L’avversario A conosce un certo numero di coppie

(m1, c1), . . . , (mk, ck), dove ci è il crittogrammacorrispondente a mi.

I L’attacco rimane passivo.I Chosen-Plaintext Attack

I L’avversario A comincia ad avere un ruolo attivo.I Può, in particolare, calcolare Enck(m)) = Enc(m, k) per

messaggi di sua scelta.

I Chosen-Ciphertext AttackI L’avversario A partecipa in modo ancora più attivo alla

comunicazione, avendo accesso ad un “oracolo” Deck(·) perla decrittazione.

I Senza avere ovviamente accesso a k!

Possibili Scenari di AttaccoI Ciphertext-Only Attack

I L’avversario A conosce solo un certo numero dicrittogrammi c1, . . . , cm quindi interferisce con lacomunicazione in modo passivo.

I Known-Plaintext AttackI L’avversario A conosce un certo numero di coppie

(m1, c1), . . . , (mk, ck), dove ci è il crittogrammacorrispondente a mi.

I L’attacco rimane passivo.I Chosen-Plaintext Attack

I L’avversario A comincia ad avere un ruolo attivo.I Può, in particolare, calcolare Enck(m)) = Enc(m, k) per

messaggi di sua scelta.I Chosen-Ciphertext Attack

I L’avversario A partecipa in modo ancora più attivo allacomunicazione, avendo accesso ad un “oracolo” Deck(·) perla decrittazione.

I Senza avere ovviamente accesso a k!

Cifrario di CesareI Vale la pena di dare una scorsa ad alcuni cifrari storici, in

modo da capire le limitazioni dell’approccio classico allacrittografia.

I Nel Cifrario di Cesare:I I messaggi inM sono semplicemente testi in una qualunque

lingua.I L’insieme K delle chiavi è molto semplice K = {4}.I Enc non fa altro che costruire il crittogramma rimpiazzando

ciascuno carattere con il carattere che si trovi nella quartaposizione successiva nell’alfabeto:

S I O R D I N A L A · · ·

Z O S V H O R E P E · · ·

Enc4

I Dec funziona in modo speculare.

I La chiave è unica, e quindi chiunque conosca che Encdecodifica facilmente qualunque messaggio.

Cifrario di CesareI Vale la pena di dare una scorsa ad alcuni cifrari storici, in

modo da capire le limitazioni dell’approccio classico allacrittografia.

I Nel Cifrario di Cesare:I I messaggi inM sono semplicemente testi in una qualunque

lingua.I L’insieme K delle chiavi è molto semplice K = {4}.I Enc non fa altro che costruire il crittogramma rimpiazzando

ciascuno carattere con il carattere che si trovi nella quartaposizione successiva nell’alfabeto:

S I O R D I N A L A · · ·

Z O S V H O R E P E · · ·

Enc4

I Dec funziona in modo speculare.I La chiave è unica, e quindi chiunque conosca che Enc

decodifica facilmente qualunque messaggio.

Cifrario a Rotazione

I È una ovvia generalizzazione del cifrario di Cesare, dove Kdiventa {1, . . . , |Σ| − 1} e Σ è il sottostante alfabeto.

S I O D · · ·

S+ n · · ·

Encn

R

I+ n O+ n R+ n D+ n

I Le chiavi sono molte di più, ma rimangono troppo poche.I A può procedere provando a decrittare un qualunque

crittogramma con tutte le possibili chiavi e dopo al più|Σ| − 1 tentativi ottiene il testo in chiaro.

I È chiaro che questo attacco funziona solo quando ilmessaggio ha testo compiuto. Come formalizzare il fattoche il cifrario è banalmente insicuro?

Cifrario a Sostituzione Monoalfabetica

I Può essere visto come un’ulteriore generalizzazione dei duecifrari precedenti.

I Lo spazio dei messaggiM rimane lo stesso, mentre lospazio delle chiavi diventa:

K = {σ | σ : Σ→ Σ è una permutazione}.

I Diventa quindi:

S I O D · · ·

σ(S) · · ·

Encσ

R

σ(I) σ(O) σ(R) σ(D)

I Ora |K| è il fattoriale di |Σ|, un numero quindi moltogrande. L’attacco brute-force non è più possibile, almeno inun tempo ragionevole.

Gli Attacchi StatisticiI Se i messaggi inM hanno qualche proprietà statistica che li

rende distinguibili da stringhe casuali, allora A potrebbeanalizzare le frequenze q1, . . . , q|Σ| di ciascun simbolo inΣ nel crittogramma c, confrontandola con quella degli stessisimboli nei messaggi inM.

I Per ogni linguaggio naturale, esistono tabelle tramite lequali ricavare le probabilità pi dell’i-esimo simbolo nellefrasi di tale linguaggio.

I Al crescrere di |c|, la probabilità di successo converge ad 1.I Similmente, un attacco statistico contro il Cifrario a

Rotazione potrebbe consistere nel calcolare le seguentiquantità

K =

|Σ|∑i=1

p2i Ij =

|Σ|∑i=1

(pi · qi+j)

e nel determinare per che valore di j le quantità K e Ijsono più simili.

Il Cifrario di Vigenère

I Anche detto Cifrario a Sostituzione Polialfabetica.I Lo spazio delle chiavi è l’insieme delle stringhe di lunghezza

finita in Σ, ossia K = Σ∗.

A1 Am Am+1 A2m · · ·

· · ·

EncB1···Bm

· · · · · ·

A1 + B1 · · ·· · · Am + Bm Am+1+B1 A2m + Bm

I Anche in questo caso, lo spazio delle chiavi sembra esseresufficientemente ampio, impedendo quindi gli attacchi bruteforce.

Il Cifrario d Vigenère — Attacchi StatisticiI Se la lunghezza della chiave k ∈ Σ∗, detta periodo t, è nota,

allora si possono utilizzare le tecniche già viste.I Come determinare il periodo t?

I Se il massimo periodo T non è troppo grande (i.e. seK = ΣT ), potremmo per esempio provare a forzare il cifrariosemplicemente per tentativi, supponendo che t prendavalori via via più grandi in {1, . . . , T}.

I Potremmo anche usare il cosiddetto Metodo di Kasiski,

I Infine, esiste anche il metodo basato sull’indice dicoincidenza. Per valori crescenti di τ numero naturale,tabuliamo i caratteri del crittogramma in posizione1, 1 + τ, 1 + 2τ, 1 + 3τ, . . ., ottenendo le frequenze qτi . Aquesto punto calcoliamo

K =

|Σ|∑i=1

p2i Sτ =

|Σ|∑i=1

(qτi )2

e verifichiamo per quali valre di τ i valori Sτ e K sono vicini.

Cifrari Storici — La Morale

I I cifrari storici non sono mai utilizzati concretamente, ma illoro studio ci lancia due messaggi importanti.

I Da un lato che lo spazio delle chiavi deve esseresufficientemente grande a impedire attacchi brute-force, maquest’ultima è una condizione necessaria ma nonsufficiente alla sicurezza.

I Cf. Il cifrario a sostituzione.I Dall’altro la complessità descrittiva di un cifrario non dà

nessuna garanzia sulla relativa sicurezza.I Per il principio di Kerchoff, l’avversario conosce Gen, Enc,

Dec.

I Tre Principi della Crittografia Moderna

1. Uso di Definizioni Formali e Rigorose dellaSicurezza di Primitive e Protocolli.

I Non ci si può limitare a dare definizioni informali. Occorreessere in grado di eliminare ogni ambiguità.

I Il rischio è quello di diventare troppo restrittivi, ma è unrischio che bisogna correre.

2. Precisione nella Specifica delle SottostantiAssunzioni.

I Senza assunzioni, purtroppo, non si riesce a dimostraremolto circa la sicurezza di primitive e protocolli.

I E anche qui bisogna essere rigorosi e precisi.3. Prove di Sicurezza Scritte nel Linguaggio della

Matematica.I Quando definizioni formali e assunzioni sono prive di

ambiguità, la tentazione è quella di dedurre direttamente lasicurezza dello schema dalle assunzioni.

I La storia insegna che è meglio non dare nulla per scontato.

Formulare Definizioni Precise — Cruciali Quando?

I In fase di Progetto.I Se non sai a cosa stai puntando, come è possibile che tu

vada nella giusta direzione? E come è possibile che tu tirenda conto che l’obiettivo è stato raggiunto?

I In fase di Utilizzo.I Una definizione di sicurezza precisa può essere utilizzata per

dimostrare che uno schema esistente ha (o non ha) leproprietà di sicurezza desiderate.

I In fase di Studio e Confronto.I Possono esistere diverse, più o meno stringenti, definizioni

di sicurezza per lo stesso tipo di schema.I Un modo per scegliere tra schemi diversi diventa quello di

confrontare le garanzie di sicurezza offerte da ciascuno diessi.

Formulare Definizioni Precise — Un EsempioI Nel contesto della crittografia a chiave privata e degli

schemi di codifica, chiediamoci: quando un tale schema sipuò considerare sicuro?

I Idee?1. Quando nessun avversario A può determinare la chiave,

date le informazioni a sua disposizione.I Quindi Enc(k, x) = x è sicuro?

2. Quando nessun avversario A può ricostruire m a partire daEnc(k,m).

I Quindi uno schema che permetta all’avversario diricostruire gli ultimi 10 bit di m da Enc(k,m) è sicuro?

3. Quando nessun avversario A riesce a determinare nessun bitdi m a partire da Enc(k,m).

I Quindi uno schema che permetta all’avversario dideterminare se certi bit in m sono in una certa relazione èsicuro?

4. Quando nessun avversario A riesce a determinare nessunaproprietà (decidibile?) di m a partire da Enc(k,m).

I Qui siamo molto vicini ad una definizione ragionevole,anche se imprecisa.

Formulare Definizioni Precise — Un EsempioI Nel contesto della crittografia a chiave privata e degli

schemi di codifica, chiediamoci: quando un tale schema sipuò considerare sicuro?

I Idee?1. Quando nessun avversario A può determinare la chiave,

date le informazioni a sua disposizione.I Quindi Enc(k, x) = x è sicuro?

2. Quando nessun avversario A può ricostruire m a partire daEnc(k,m).

I Quindi uno schema che permetta all’avversario diricostruire gli ultimi 10 bit di m da Enc(k,m) è sicuro?

3. Quando nessun avversario A riesce a determinare nessun bitdi m a partire da Enc(k,m).

I Quindi uno schema che permetta all’avversario dideterminare se certi bit in m sono in una certa relazione èsicuro?

4. Quando nessun avversario A riesce a determinare nessunaproprietà (decidibile?) di m a partire da Enc(k,m).

I Qui siamo molto vicini ad una definizione ragionevole,anche se imprecisa.

Formulare Definizioni Precise — Un EsempioI Nel contesto della crittografia a chiave privata e degli

schemi di codifica, chiediamoci: quando un tale schema sipuò considerare sicuro?

I Idee?1. Quando nessun avversario A può determinare la chiave,

date le informazioni a sua disposizione.I Quindi Enc(k, x) = x è sicuro?

2. Quando nessun avversario A può ricostruire m a partire daEnc(k,m).

I Quindi uno schema che permetta all’avversario diricostruire gli ultimi 10 bit di m da Enc(k,m) è sicuro?

3. Quando nessun avversario A riesce a determinare nessun bitdi m a partire da Enc(k,m).

I Quindi uno schema che permetta all’avversario dideterminare se certi bit in m sono in una certa relazione èsicuro?

4. Quando nessun avversario A riesce a determinare nessunaproprietà (decidibile?) di m a partire da Enc(k,m).

I Qui siamo molto vicini ad una definizione ragionevole,anche se imprecisa.

Formulare Definizioni Precise — Un EsempioI Nel contesto della crittografia a chiave privata e degli

schemi di codifica, chiediamoci: quando un tale schema sipuò considerare sicuro?

I Idee?1. Quando nessun avversario A può determinare la chiave,

date le informazioni a sua disposizione.I Quindi Enc(k, x) = x è sicuro?

2. Quando nessun avversario A può ricostruire m a partire daEnc(k,m).

I Quindi uno schema che permetta all’avversario diricostruire gli ultimi 10 bit di m da Enc(k,m) è sicuro?

3. Quando nessun avversario A riesce a determinare nessun bitdi m a partire da Enc(k,m).

I Quindi uno schema che permetta all’avversario dideterminare se certi bit in m sono in una certa relazione èsicuro?

4. Quando nessun avversario A riesce a determinare nessunaproprietà (decidibile?) di m a partire da Enc(k,m).

I Qui siamo molto vicini ad una definizione ragionevole,anche se imprecisa.

Precisione nella Specifica delle Assunzioni — Perché?

I Assunzioni imprecise non possono essere validate nérefutate.

I Nonostante le assunzioni non siano né dimostrate nérefutate, sono certamente studiate, e questo studio porta acongetturare la loro verità.

I In assenza di una specifica precisa, lo studio diventadifficile, fondamentalmente impossibile.

I Schemi diversi possono essere confrontati.I Schemi la cui sicurezza si basi su assunzioni deboli sono

ovviamente da preferire a schemi in cui le sottostantiassunzioni siano molto forti.

I Confrontare assunzioni diverse è possibile solo in presenzadi una formalizzazione rigorosa.

I Assunzioni sufficientemente deboli possono nonessere influenzate da un attacco.