Crittograﬁa Corso di Laurea Magistrale in Informatica Introduzione alla Crittograﬁa

(1)

Crittografia

Corso di Laurea Magistrale in Informatica Introduzione alla Crittografia

Ugo Dal Lago

Anno Accademico 2018-2019

(2)

Crittografia Classica e Crittografia Moderna

I

La Crittografia era, fino agli anni Ottanta, una forma d’arte.

I Servivano creatività e intuizione, e non esistevano principi certi.

I

Con alcuni contributi fondamentali arrivati alla fine degli anni Settanta, la Crittografia diventa una scienza.

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

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

I

Oggigiorno, con crittografia si fa riferimento a qualunque tecnica 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.

(3)

Crittografia Classica e Crittografia Moderna

I

La Crittografia era, fino agli anni Ottanta, una forma d’arte.

I Servivano creatività e intuizione, e non esistevano principi certi.

I

Con alcuni contributi fondamentali arrivati alla fine degli anni Settanta, la Crittografia diventa una scienza.

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

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

I

Oggigiorno, con crittografia si fa riferimento a qualunque tecnica 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.

(4)

La Crittografia a Chiave Segreta

I

Partiamo da un particolare scenario, quello dei protocolli volti a garantire a confidenzialità nello scambio dei dati tra due parti.

Enc Dec

m m

k A k

I

La chiave è unica e deve essere preventivamente scambiata tra le parti.

I

Formalmente, possiamo vedere uno schema di codifica come composto da tre spazi K, M e C e da una tripla di algoritmi (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.

(5)

Il Principio di Kerchoff

I

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

I

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

I

Anche in uno scenario in cui A non conosca effettivamente lo 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 ripetutamente

ignorato, con conseguenze devastanti.

(6)

Possibili Scenari di Attacco

I

Ciphertext-Only Attack

I L’avversario A conosce solo un certo numero di crittogrammi c1, . . . , cm quindi interferisce con la comunicazione in modo passivo.

I

Known-Plaintext Attack

I L’avversario A conosce un certo numero di coppie (m1, c1), . . . , (mk, ck), dove ci è il crittogramma corrispondente 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 alla comunicazione, avendo accesso ad un “oracolo” Dec_k(·) per la decrittazione.

I Senza avere ovviamente accesso a k!

(7)

Possibili Scenari di Attacco

I

Ciphertext-Only Attack

I

Known-Plaintext Attack

I

Chosen-Plaintext Attack

I

Chosen-Ciphertext Attack

(8)

Possibili Scenari di Attacco

I

Ciphertext-Only Attack

I

Known-Plaintext Attack

I

Chosen-Plaintext Attack

I

Chosen-Ciphertext Attack

(9)

Possibili Scenari di Attacco

I

Ciphertext-Only Attack

I

Known-Plaintext Attack

I

Chosen-Plaintext Attack

I

Chosen-Ciphertext Attack

(10)

Cifrario di Cesare

I

Vale la pena di dare una scorsa ad alcuni cifrari storici, in modo da capire le limitazioni dell’approccio classico alla crittografia.

I

Nel Cifrario di Cesare:

I I messaggi in M 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 quarta posizione successiva nell’alfabeto:

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

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

I Dec funziona in modo speculare.

I

La chiave è unica, e quindi chiunque conosca che Enc

decodifica facilmente qualunque messaggio.

(11)

Cifrario di Cesare

I

Vale la pena di dare una scorsa ad alcuni cifrari storici, in modo da capire le limitazioni dell’approccio classico alla crittografia.

I

Nel Cifrario di Cesare:

I I messaggi in M 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 quarta posizione successiva nell’alfabeto:

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

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

I Dec funziona in modo speculare.

I

La chiave è unica, e quindi chiunque conosca che Enc

decodifica facilmente qualunque messaggio.

(12)

Cifrario a Rotazione

I

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

S I O D · · ·

S + n · · ·

Enc_n 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 il

messaggio ha testo compiuto. Come formalizzare il fatto

che il cifrario è banalmente insicuro?

(13)

Cifrario a Sostituzione Monoalfabetica

I

Può essere visto come un’ulteriore generalizzazione dei due cifrari precedenti.

I

Lo spazio dei messaggi M rimane lo stesso, mentre lo spazio 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 molto

grande. L’attacco brute-force non è più possibile, almeno in

un tempo ragionevole.

(14)

Gli Attacchi Statistici

I

Se i messaggi in M hanno qualche proprietà statistica che li rende distinguibili da stringhe casuali, allora A potrebbe analizzare le frequenze q

₁

, . . . , q

_|Σ|

di ciascun simbolo in Σ nel crittogramma c, confrontandola con quella degli stessi simboli nei messaggi in M.

I Per ogni linguaggio naturale, esistono tabelle tramite le quali ricavare le probabilità pi dell’i-esimo simbolo nelle frasi 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 seguenti quantità

K =

|Σ|

X

i=1

p

²_i

I

_j

=

|Σ|

X

i=1

(p

_i

· q

_i+j

)

e nel determinare per che valore di j le quantità K e I

_j

sono più simili.

(15)

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 · · ·

· · · Enc_B₁_···B_m

· · · ·

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

I

Anche in questo caso, lo spazio delle chiavi sembra essere

sufficientemente ampio, impedendo quindi gli attacchi brute

force.

(16)

Il Cifrario d Vigenère — Attacchi Statistici

I

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. se K = Σ^T), potremmo per esempio provare a forzare il cifrario semplicemente per tentativi, supponendo che t prenda valori 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 di coincidenza. Per valori crescenti di τ numero naturale, tabuliamo i caratteri del crittogramma in posizione 1, 1 + τ, 1 + 2τ, 1 + 3τ, . . ., ottenendo le frequenze q^τ_i. A questo punto calcoliamo

K =

|Σ|

X

i=1

p²_i Sτ =

|Σ|

X

i=1

(q^τ_i)²

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

(17)

Cifrari Storici — La Morale

I

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

I

Da un lato che lo spazio delle chiavi deve essere

sufficientemente grande a impedire attacchi brute-force, ma quest’ultima è una condizione necessaria ma non

sufficiente 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.

(18)

I Tre Principi della Crittografia Moderna

1.

Uso di Definizioni Formali e Rigorose della Sicurezza di Primitive e Protocolli.

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

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

2.

Precisione nella Specifica delle Sottostanti Assunzioni.

I Senza assunzioni, purtroppo, non si riesce a dimostrare molto 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 la sicurezza dello schema dalle assunzioni.

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

(19)

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 ti renda 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) le proprietà 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 di essi.

(20)

Formulare Definizioni Precise — Un Esempio

I

Nel contesto della crittografia a chiave privata e degli schemi di codifica, chiediamoci: quando un tale schema si può 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 da Enc(k, m).

I Quindi uno schema che permetta all’avversario di ricostruire gli ultimi 10 bit di m da Enc(k, m) è sicuro? 3. Quando nessun avversario A riesce a determinare nessun bit

di m a partire da Enc(k, m).

I Quindi uno schema che permetta all’avversario di

determinare se certi bit in m sono in una certa relazione è sicuro?

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

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

(21)

Formulare Definizioni Precise — Un Esempio

I

Nel contesto della crittografia a chiave privata e degli schemi di codifica, chiediamoci: quando un tale schema si può considerare sicuro?

I

Idee?

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

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

(22)

Formulare Definizioni Precise — Un Esempio

I

Nel contesto della crittografia a chiave privata e degli schemi di codifica, chiediamoci: quando un tale schema si può considerare sicuro?

I

Idee?

(23)

Formulare Definizioni Precise — Un Esempio

I

Nel contesto della crittografia a chiave privata e degli schemi di codifica, chiediamoci: quando un tale schema si può considerare sicuro?

I

Idee?

(24)

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 a congetturare la loro verità.

I In assenza di una specifica precisa, lo studio diventa difficile, 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 sottostanti assunzioni siano molto forti.

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

I