I Cifrari Perfetti

I Cifrari Perfetti
Alessio Nunzi Fabiola Genevois Federico Russo
Fabiola Genevois
•
•
•
Strategie d’attacco
Sicurezza dei sistemi crittografici
Il cifrario Perfetto
• Enunciato di Shannon
•
Il cifrario di Vernam
•
One-Time Pad come cifrario perfetto
•
Limiti del One-Time Pad
•
Generatori Pseudo-casuali
Strategie d’attacco
• Ciphertext-only :
il crittoanalista, conosce i testi cifrati e da questi
cerca di risalire ai testi in chiaro o alle chiavi
• Know-plaintext :
l'attaccante, conosce uno o più testi in chiaro e le
rispettive cifrature; da questi cerca di risalire alle
chiavi o di decodificare altri testi cifrati
Strategie d’attacco
• Chosen-plaintext :
l'attaccante, è in grado di cifrare senza conoscere
le chiavi. Cerca di risalire alle chiavi o di
decodificare altri testi cifrati
• Adaptative chosen-plaintext :
l'attaccante, è in grado di cifrare ed è in grado di
variare il testo in chiaro, in conseguenza dei testi
cifrati ottenuti. Non conosce le chiavi, cerca di
risalire alle chiavi o di decodificare altri testi cifrati
Strategie d’attacco
• Chosen-ciphertext :
il crittoanalista, è in grado di decifrare, ma non
conosce le chiavi e cerca di risalire ad esse.
• Brute force :
il crittoanalista, tenta di decifrare il testo, provando
tutte le possibili chiavi di cifratura. Questo attacco,
ha efficacia maggiore con l'aumento della potenza
di calcolo.
Sistema Sicuro
• Sicurezza computazionale
Se il miglior algoritmo noto che consente la
violazione del crittogramma, ha complessità
computazionale superiore ad un certo limite N
sufficientemente grande
• Sicurezza dimostrabile
Si cerca di fornire la prova, che la sicurezza di un
crittosistema, è equivalente a quella di un
problema che si ritiene difficile da risolvere
• Sicurezza incondizionale
Si ha se non è violabile, anche utilizzando una
potenza di calcolo illimitata
Cifrario Perfetto
Un cifrario è perfetto se per ogni m
appartenente a Msg e per ogni c
appartenente a Critto vale la relazione
P( M = m | C = c ) = P( M = m )
Cifrario Perfetto
Per comprendere meglio la precedente
affermazione, immaginiamo che sia :
• P(M=m) = p
con 0 < p < 1
• Il cifrario non sia perfetto
Queste assunzioni implicano che
P(M=m|C=c) ≠ P(M=m)
Cifrario Perfetto
• Se P(M=m|C=c) = 0 il crittoanalista, osservando c,
deduce che il messaggio spedito non è m
• Se P(M=m|C=c) = 1 si può dedurre che il messaggio
spedito è proprio m.
• In tutti i casi intermedi, il crittoanalista raffina la sua
conoscenza sul possibile messaggio spedito.
Tale conoscenza rimane quindi inalterata se e solo se
P(M=m|C=c) = P(M=m)
Enunciato di Shannon
“In un cifrario perfetto il numero delle
chiavi deve essere maggiore o uguale
al numero dei messaggi possibili”
Ora dimostreremo che
Nk . Nm
Enunciato di Shannon
Dimostrazione
In un qualsiasi cifrario si deve avere
Nm < |Critto|
Altrimenti non avremmo una funzione iniettiva!
Supponiamo ora, per assurdo, che in un cifrario
perfetto
Nk < Nm
Si ha quindi che
Nk < Nm < |Critto|
Enunciato di Shannon
Fissando un messaggio m con P(M=m) ≠ 0, da
esso, si possono generare al massimo Nk
crittogrammi diversi, applicando tutte le chiavi.
Dato che Nk < |Critto|, esisterà, almeno un
crittogramma c', che non è immagine di m.
Ne segue che
P(M=m|C=c') = 0 ≠ P(M=m)
Abbiamo trovato un assurdo!
•
•
•
Strategie d’attacco
Sicurezza dei sistemi crittografici
Il cifrario Perfetto
•
Enunciato di Shannon
Alessio Nunzi
•
Il cifrario di Vernam
•
One-Time Pad come cifrario perfetto
•
Limiti del One-Time Pad
•
Generatori Pseudo-casuali
Cifrario di Vernam
Nel 1917 Vernam costruì un dispositivo che:
• Prende in input due nastri perforati
• Produce in output un nastro perforato effettuando lo XOR
tra i nastri di input.
• Il dispositivo può essere utilizzato sia per la cifratura , che
per la decifratura (cioè ci = mi ⊕ ki e mi = ci ⊕ ki per la
definizione dell’operazione di XOR)
XOR
0⊕0=0
1⊕1=0
0⊕1=1
1⊕0=1
Cifrario di Vernam
Proprietà
1. La chiave deve essere lunga almeno
quanto il messaggio
2. La chiave deve essere una sequenza
completamente casuale di caratteri
3. La chiave non deve essere riutilizzata (da
questa il nome One-Time Pad)
Cifrario di Vernam
Ad esempio volendo codificare la parola “ALA”,
che ha una codifica Ascii 65 – 76 – 65
m
k
c
Si nota facilmente che nel cifrato viene rotto
qualsiasi pattern presente nel testo in chiaro!
Cifrario di Vernam
La funzione di decodifica è ancora lo XOR!
Il One-Time Pad è perfetto?
La risposta è sì, ma solo se si rispettano due ipotesi:
1.
Tutti i messaggi hanno la stessa lunghezza n
2.
Tutte le sequenze di n bit sono messaggi possibili
Sotto queste ipotesi e utilizzando una chiave
scelta perfettamente a caso per ogni
messaggio, One-Time Pad
•
•
è un cifrario perfetto
utilizza un numero di chiavi minimo
Il One-Time Pad è perfetto?
Per un cifrario perfetto vale la relazione
P(M=m|C=c) = P(M=m)
Applicando la definizione di probabilità
condizionata si ricava:
[1]
P ( M = m ,C = c )
P ( M = m|C = c ) =
P( C =c )
Il One-Time Pad è perfetto?
Considerando quindi anche l’evento di
generazione della chiave possiamo scrivere:
P(M=m,C=c) = P(M=m,C=c,K=k )
Utilizzando a ritroso la definizione di probabilità
condizionata possiamo riscrivere la precedente
uguaglianza come
P( M=m,C =c ) =P( C =c|M=m,K =k ) ×P( M=m|K =k ) ×P( K =k )
Il One-Time Pad è perfetto?
Analizziamo il secondo membro …
• P(C=c|M=m,K=k ) = 1 per l’unicità di k, essa infatti
è definita come ki ⊕ mi = ci ed è unica in quanto:
con 0- i - n
ki = ki ⊕ mi ⊕ mi = ci ⊕ mi
• P(M=m|K=k ) = P(M=m)
perché la generazione
del messaggio e della chiave sono processi
indipendenti
1⎞
⎛
• P(K =k ) =⎜ ⎟
⎝2 ⎠
n
perché la chiave è casuale
Il One-Time Pad è perfetto?
Quindi possiamo riscrivere l’uguaglianza come
n
[2]
1⎞
⎛
P ( M = m ,C = c ) = ⎜ ⎟ × P ( M = m )
⎝2 ⎠
Combinando le equazioni [1] e [2] otteniamo
n
[3]
⎛ 1 ⎞ ×P ( M = m )
⎜ ⎟
2
⎝
⎠
P ( M = m|C = c ) =
P( C =c )
Il One-Time Pad è perfetto?
Calcoliamo ora P(C=c) prendendo in esame
l’insieme Fm = {M=m}
• Sicuramente è vero che
P ( ∪m Fm ) = 1
• Poiché tutti gli eventi in Fm sono disgiunti si
può dire che
P ( C = c ) = ∑ P ( M = m ,C = c )
m
Il One-Time Pad è perfetto?
Dai risultati precedentemente esposti e
dall’equazione [2] si ricava
n
n
1⎞
1⎞
⎛
⎛
P ( C = c ) = ∑ P ( M = m ,C = c ) = ∑ ⎜ ⎟ × P ( M = m ) = ⎜ ⎟
⎝2 ⎠
m
m ⎝2 ⎠
Sostituendo questo risultato nell’equazione [3]
P( M = m | C = c) = P( M = m)
Il One-Time Pad è perfetto?
Dopo aver dimostrato la perfezione del cifrario One-Time
Pad, dimostriamo che esso minimizza il numero delle
chiavi necessarie.
Essendo n la lunghezza del messaggio:
• |Msg| = 2n
• La chiave è una sequenza di n bit, quindi |Key| = 2n
• Dunque |Key| = |Msg| = 2n
Ricordando l’enunciato di Shannon ( |Key| ≥ |Msg| ) è
evidente che One-Time Pad minimizza il numero delle
chiavi
•
•
•
Strategie d’attacco
Sicurezza dei sistemi crittografici
Il cifrario Perfetto
•
Enunciato di Shannon
•
Il cifrario di Vernam
•
One-Time Pad come cifrario perfetto
Federico Russo
•
Limiti dell’ One-Time Pad
•
Generatori Pseudo-casuali
Limiti del One-Time Pad
1. Scambio della chiave
2. Generazione della chiave
3. Generazione costosa - riduciamo la
lunghezza della chiave?
Generazione della chiave
• Attraverso generatori pseudo-casuali:
valore numerico
iniziale
“Seme”
genera
Sequenza di bit
Generazione della chiave
• Il mittente e il destinatario si devono mettere
d’accordo su quale generatore crittografico
utilizzare ( pubblicamente noto)
• Decidere il seme - file binario disponibile nella
rete
Problemi dei generatori
•
Se il generatore è pubblicamente noto:
1. il seme costituisce l’informazione segreta:
•
basta un semplice attacco esaustivo sull’insieme dei semi per
decrittare il cifrato,quindi bisogna aumentare il numero delle cifre
dei semi, cosa non permessa dai generatori pseudo-casuali o
cambiare seme ad ogni messaggio
2. bisogna aumentare il periodo
Problemi dei generatori
• Se generatore non noto:
– Il generatore e il seme sono le informazioni segrete
– Utile se generatori sono implementati con programmi
brevi e perciò facilmente scambiabili
Lunghezza chiave n?
•
•
•
•
Soluzione computazionalmente costosa!
Messaggi lunghi n bit
Non tutti i 2n messaggi sono legittimi
Messaggi validi sono αn, con α < 2 costante
propria del linguaggio
• Allora è possibile ridurre le chiavi, mantenendo la
lunghezza fissa ad n
Lunghezza chiave n?
• Diversi messaggi in chiaro cifrati con diverse
chiavi, danno lo stesso cifrato
2tαn >> 2n
Crittogrammi
generati
t + nlog2α >> n
t >> 0,88n
Tutti i
possibili
messaggi
Limiti del One-Time Pad
• Pregi :
– Senza chiave non è possibile risalire al messaggio in chiaro
– Alto grado di sicurezza (militare)
• Difetti:
– Inutilizzabile su vasta scala ( internet, audio/video, etc…)
– Difficile scambio della chiave su canale sicuro
– Generare una chiave totalmente casuale
Generatori Pseudo-casuali
•
•
•
•
•
Generano sequenze di bit
P(0)=1/2
P(1)=1/2
Bit indipendenti dal precedente
Non esistono generatori casuali, ma
dobbiamo accettare dei compromessi
Generatori Pseudo-casuali
•
Due approcci per generare delle sequenze brevi
1.
Valori campionati del segnale proveniente da un
microfono
Posizione della testina su un disco rigido
2.
Otteniamo sequenze brevi abbastanza casuali, ma a noi
servono molto più lunghe
Generatori Pseudo-casuali
Seme
Seme di lunghezza m
Generatore
Sequenza bit generata: n >> m
0001010001010…
Generatori Pseudo-casuali
•
La sequenza generata deve superare alcuni test:
1.
2.
3.
4.
Test di frequenza
Poker test
Test di autocorrelazione
Run test
Es: Generatori lineari e polinomiali
Generatori Pseudo-casuali
• Generatori lineari
Genera una sequenza x1.... xn a partire da x0, in base alla
relazione
xi = (ax i-1 + b) mod m
• Generatore polinomiale
xi = (a1 xti-1 +a2 xt-1i-1 + ... + at xi-1 +at+1) mod m
Si calcola ri = xi / m e se è dispari il bit varrà 1 , altrimenti 0
Generatori Pseudo-casuali
• Questi generatori non impediscono di fare
previsioni sui bit,anche quando il seme è casuale.
• Bisogna rafforzare gli algoritmi.
• Vengono introdotte le funzioni one-way, facili da
calcolare, ma difficili da invertire
f
x
y
f -1
Generatori Pseudo-casuali
• Nelle applicazioni crittografiche si
utilizzano generatori binari che superano il
test di prossimo bit
Generatori crittograficamente sicuri
Generatori sicuri
• Utilizzano particolari predicati hard-core
Def:
b(x) è hard-core per f(x), se b(x) è facile da
calcolare conoscendo x e difficile da
calcolare conoscendo solo f(x)
y = b(f(x))
Es: BBS
BBS
• F(x) = x2 mod n, n è primo
• B(x) = << x è dispari >>
xi = (xi-1)2 mod n
xi .... xn
bi = 1
xm-i è dispari
bm,bm-1 ,…b0
BBS
• Questi algoritmi sono molto lenti e
generano sequenze casuali corte
• Per generare sequenze più lunghe ci si
affida ad algoritmi meno sicuri, ma molto
efficienti e ancora inviolati (FIPS)
FINE