Crittoanalisi
Monica Bianchini
[email protected]
Dipartimento di Ingegneria dell’Informazione
Università di Siena
Introduzione  1
• I principali tipi di attacco alla sicurezza dei crittosistemi
si distinguono in…
o Ciphertext-only  l’intruso è venuto a conoscenza di
una stringa di testo cifrato y
o Known plaintext  l’intruso conosce una stringa di
plaintext x, ed il corrispondente testo cifrato y
o Chosen plaintext  l’intruso ha ottenuto accesso
temporaneo al meccanismo di cifratura: può quindi
scegliere un plaintext x e costruire il corrispondente
testo cifrato y
o Chosen ciphertext  l’intruso ha ottenuto accesso
temporaneo al meccanismo di decifratura: può quindi
scegliere un testo cifrato y e costruire il
corrispondente plaintext x
Introduzione  2
•
•
•
•
Le tecniche per raggiungere la sicurezza discusse finora
si basano tutte sulla premessa di validità del…
Principio di Kerckhoff
L’intruso, Oscar, conosce il tipo di crittosistema in uso
Se ciò non fosse, il suo compito risulterebbe,
ovviamente, ancora più difficile
In prima istanza, esamineremo il tipo di attacco più
debole, il Ciphertext-only; assumeremo inoltre che le
stringhe di plaintext rappresentino testo inglese
ordinario, senza segni di punteggiatura né spazi
 la crittoanalisi è più difficile in questo caso
Introduzione  3
•
Molte tecniche di crittoanalisi si basano su proprietà
statistiche della lingua inglese, in particolare su stime
della frequenza relativa dei 26 caratteri costituenti
l’alfabeto
•
Sulla base di un esame statistico, le 26 lettere
dell’alfabeto possono essere suddivise in cinque gruppi:
o
E, con una probabilità pari a 0.12
o
T,A,O,I,N,S,H,R, ciascuna
compresa tra 0.06 e 0.09
o
D,L ognuna con probabilità  0.04
o
C,U,M,W,F,G,Y,P,B,
ognuna
compresa fra 0.015 e 0.028
o
V,K,J,X,Q,Z, con probabilità minore di 0.01
avente
con
probabilità
probabilità
Introduzione  4
•
Più in dettaglio…
Lettera Probabilità Lettera Probabilità
A
B
C
D
E
F
G
H
I
J
K
L
M
.082
.015
.028
.043
.127
.022
.020
.061
.070
.002
.008
.040
.024
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
.067
.075
.019
.001
.060
.063
.091
.028
.010
.023
.001
.020
.001
Introduzione  5
• Può essere utile considerare anche sequenze di due o tre
lettere consecutive, chiamate rispettivamente digrammi e
trigrammi
• I 30 digrammi più comuni, in ordine decrescente, sono
TH,HE,IN,ER,AN,RE,ED,ON,ES,ST,EN,AT,TO,NT,HA,
ND,OU,EA,NG,AS,OR,TI,IS,ET,IT,AR,TE,SE,HI,OF
• I 12 trigrammi più comuni sono (in ordine decrescente)
THE,ING,AND,HER,ERE,ENT,THA,NTH,WAS,ETH,FOR,
DTH
Esempi di crittoanalisi
Affine cipher  1
•
Per vedere un semplice esempio in cui l’indagine
statistica può essere proficuamente utilizzata per fare
crittoanalisi, si consideri Affine cipher
•
Esempio 1
Supponiamo che Oscar
seguente testo cifrato
sia
venuto
in
possesso
del
“fmxvedkaphferbndkrxrsrefmorudsdkdvshvufedkaprkdlyevlrhhrh”
Lettera Frequenza Lettera Frequenza
Frequenza
delle 26 lettere
dell’alfabeto
A
B
C
D
E
F
G
H
I
J
K
L
M
2
1
0
7
5
4
0
5
0
0
5
2
2
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
1
1
2
0
8
3
0
2
4
0
2
1
0
Esempi di crittoanalisi
Affine cipher  2
• Vi sono soltanto 57 caratteri nel testo cifrato, ma sono
sufficienti per crittoanalizzare Affine cipher
• I caratteri cifrati più frequenti sono R (8 occorrenze),
D (7), E,H,K (5) ed F,S,V (4)
• In prima istanza si può ipotizzare che R codifichi e, D
la lettera t; numericamente, ek(4)=17, ek(19)=3
• Ricordando che ek(x)=ax+b, si ottiene
lineare di due equazioni in due incognite
{
un
sistema
4a +b =17
19a +b =3
che ha come unica soluzione a =6 e b =19: illegale poichè
MCD(a,26)=2  IPOTESI ERRATA
Esempi di crittoanalisi
Affine cipher  3
• Le prove successive sono:
 R codifica e, E codifica t; si ottiene a =13, che è
una soluzione illegale  IPOTESI ERRATA
 R codifica e, H codifica t; si ottiene a =8, che è
ancora illegale  IPOTESI ERRATA
 R codifica e, K codifica t; si ottiene a =3, b =5,
che è invece una chiave legale
• Con k=(3,5), dk(y)=9y-19, ed il testo decrittato
risulta…
“algorithms are quite general definitions of arithmetic processes”
 IPOTESI CORRETTA: IL CIFRARIO È VIOLATO
Esempi di crittoanalisi
Substitution cipher  1
• Esempio 2
Si consideri il seguente testo cifrato
yifqfmzrwqfyvecfmdzpcvmrzwnmdzvejbtxcddumj
ndifefmdzcdmqzkceyfcjmyrncwjcszrexchzunmxz
nzucdrjxyysmrtmeyifzwdyvzvyfzumrzcrwnzdzjj
xzwgchsmrnmdhncmfqchzjmxjzwiejyucfwdjnzdir
Lettera Frequenza Lettera Frequenza
Frequenza
delle 26 lettere
dell’alfabeto
A
B
C
D
E
F
G
H
I
J
K
L
M
0
1
15
13
7
11
1
4
5
11
1
0
16
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
9
0
1
4
10
3
2
5
5
8
6
10
20
Esempi di crittoanalisi
Substitution cipher  2
•
•
•
•
Poiché Z occorre molto più spesso di tutti gli altri
caratteri del testo cifrato, si può congetturare che
dk(Z)=e
I restanti caratteri con più di dieci occorrenze sono
C,D,F,J,M,R,Y che, presumibilmente, codificano un
sottoinsieme di t,a,o,i,n,s,h,r, con frequenze che,
tuttavia, non variano a sufficienza per poter fare
ipotesi più precise
Guardando ai digrammi, specialmente quelli della forma
–Z e Z-, si può vedere come i più frequenti siano DZ e
ZW (4 volte ciascuno), NZ e ZU (3), RZ,HZ,XZ,
FZ,ZR,ZV,ZC,ZD,ZJ (2)
Poiché ZW compare quattro volte mentre WZ mai, e
W è in assoluto la lettera a più bassa frequenza, si
può ipotizzare che dk(W)=d
Esempi di crittoanalisi
Substitution cipher  3
• Poiché ZRW e RZW sono presenti entrambi all’inizio del
testo cifrato, ed RW compare anche nel seguito,
essendo nd un digramma comune, si può supporre dk(R)=n
------end---------e----ned---e-----------yifqfmzrwqfyvecfmdzpcvmrzwnmdzvejbtxcddumj
--------e----e---------n--d---en----e----e
ndifefmdzcdmqzkceyfcjmyrncwjcszrexchzunmxz
-e---n------n------ed---e---e--ne-nd-e-e--
nzucdrjxyysmrtmeyifzwdyvzvyfzumrzcrwnzdzjj
-ed-----n-----------e----ed-------d---e--n
xzwgchsmrnmdhncmfqchzjmxjzwiejyucfwdjnzdir
Esempi di crittoanalisi
Substitution cipher  4
• Si può quindi tentare la decodifica dk(N)=h, poichè NZ
compare molte volte mentre ZN no
• Se l’ipotesi è corretta, allora il segmento di plaintext
ne-ndhe suggerisce che dk(C)=a
------end-----a---e-a--nedh--e------a----yifqfmzrwqfyvecfmdzpcvmrzwnmdzvejbtxcddumj
h-------ea---e-a---a---nhad-a-en--a-e-h--e
ndifefmdzcdmqzkceyfcjmyrncwjcszrexchzunmxz
he-a-n------n------ed---e---e--neandhe-e-nzucdrjxyysmrtmeyifzwdyvzvyfzumrzcrwnzdzjj
-ed-a---nh---ha---a-e----ed-----a-d--he--n
xzwgchsmrnmdhncmfqchzjmxjzwiejyucfwdjnzdir
Esempi di crittoanalisi
Substitution cipher  5
• Consideriamo ora M, il secondo carattere, in ordine di
frequenza, del testo cifrato
• Il segmento di codice cifrato RNM che dovrebbe
corrispondere a nh-, suggerisce che h- sia l’inizio di una
parola  dk(M) {i,o} e, poiché ai è più comune di ao, il
digramma cifrato CM suggerisce dk(M) =i
-----iend-----a-i-e-a-inedhi-e------a---iyifqfmzrwqfyvecfmdzpcvmrzwnmdzvejbtxcddumj
h-----i-ea-i-e-a---a-i-nhad-a-en--a-e-hi-e
ndifefmdzcdmqzkceyfcjmyrncwjcszrexchzunmxz
he-a-n-----in-i----ed---e---e-ineandhe-e-nzucdrjxyysmrtmeyifzwdyvzvyfzumrzcrwnzdzjj
-ed-a--inhi--hai--a-e-i--ed-----a-d--he--n
xzwgchsmrnmdhncmfqchzjmxjzwiejyucfwdjnzdir
Esempi di crittoanalisi
Substitution cipher  6
• Occorre ora determinare quale lettera codifica o
o Poiché o è molto comune, dovrebbe corrispondere a
una delle lettere D,F,J,Y nel testo cifrato
o Y sembra la più probabile, altrimenti nel plaintext
esisterebbero trigrammi di vocali (aoi, per CFM o
CJM)  dk(Y)=o
• Le lettere più frequenti rimaste ancora da decrittare
sono D,F,J, che congetturiamo corrispondere a r,s,t
(in qualche ordine)
o Due occorrenze del trigramma NMD suggeriscono
dk(D)=s, che produrrebbe his nel plaintext
o Il segmento HNCMF potrebbe corrispondere a chair
 dk(F)=r, dk(H)=c e, per esclusione, dk(J)=t
Esempi di crittoanalisi
Substitution cipher  7
o-r-riend-ro--arise-a-inedhise--t---ass-it
yifqfmzrwqfyvecfmdzpcvmrzwnmdzvejbtxcddumj
hs-r-riseasi-e-a-orationhadta-en--ace-hi-e
ndifefmdzcdmqzkceyfcjmyrncwjcszrexchzunmxz
he-asnt-oo-in-i-o-redso-e-ore-ineandhesett
nzucdrjxyysmrtmeyifzwdyvzvyfzumrzcrwnzdzjj
-ed-ac-inhischair-aceti-ted--to-ardsthes-n
xzwgchsmrnmdhncmfqchzjmxjzwiejyucfwdjnzdir
• A questo punto diviene molto semplice completare le
lettere mancanti a comporre…
“Our friend from Paris examined is empty glass with surprise, as if
evaporation have taken place while he wasn’t looking. I poured some
more wine and he settled back in his chair, face tilted up towards
the sun”
Esempi di crittoanalisi
Hill cipher  1
•
•
•
•
•
Hill cipher è più difficile da violare con un attacco
Ciphertext-only, ma soccombe facilmente ad attacchi del
tipo Known plaintext
Supponiamo che l’invasore abbia determinato il valore di
m e che sia in possesso di almeno m coppie distinte di
m-uple xj=(x1j,x2j,…xmj) e yj=(y1j,y2j,…ymj), con yj=ek(xj),
1jm
Siano X=(xij) e Y=(yij) le due matrici m  m
che
racchiudono l’informazione dell’invasore  Y=XK, dove la
matrice K è la chiave da calcolare
Se la matrice X è invertibile, Oscar può calcolare
K=X-1Y e quindi violare il sistema
Se X non è invertibile, l’informazione in possesso
dell’invasore non è sufficiente a decrittare la chiave
 occorrono altre coppie plaintext-ciphertext mdimensionali
Esempi di crittoanalisi
Hill cipher  2
•
Esempio 3
Supponiamo che il plaintext “friday” sia stato codificato
utilizzando Hill cipher con m =2, fornendo “pqcfku”
Si ha: ek(5,17)=(15,16), ek(8,3)=(2,5), ek(0,24)=(10,20)
Dalle prime 2 coppie plaintext-ciphertext si ottiene
l’equazione matriciale…
( )( )
( )( )
( )( ) ( )
15 16
Poiché
2
5
5 17
8
K =
9
3
1
2 15
=
-1
=
5 17
8
3
K
9 1
Si può provare
che K
“funziona”
anche per
la terza
coppia
plaintextciphertext
2 15
15 16
2
5
=
7 19
8
3
Esempi di crittoanalisi
Hill cipher  3
•
Come può comportarsi Oscar nel caso in cui non
conosca il valore di m ?
•
Può procedere per tentativi, provando m = 2,3,…,fino a
calcolare un valore “plausibile” per m
•
Se il valore supposto di m non è corretto, la matrice
K, m  m, calcolata utilizzando l’algoritmo appena
descritto, non si accorderà con le altre coppie
plaintext-ciphertext, diverse da quella con cui è stata
ottenuta
Esempi di crittoanalisi
LFSR Stream cipher  1
•
Poiché tutte le operazioni eseguite all’interno del
crittosistema sono lineari, si può supporre che esso sia
vulnerabile ad un attacco di tipo Known plaintext, come
Hill cipher
•
Ipotizziamo che Oscar conosca il valore di m, la stringa
di plaintext x1x2…xn ed il corrispondente testo cifrato
y1y2…yn  può calcolare zi= xi+yi (mod 2), 1  i  n
•
Oscar deve dunque calcolare le costanti c0,c1,cm-1 per
ricostruire l’intero keystream, cioè deve essere in grado
di valutare le m incognite c0,c1,cm-1
Esempi di crittoanalisi
LFSR Stream cipher  2
m-1
Poiché, per ogni i 1, zm+i= cj zi+j, se n 2m, allora ci
j=0
sono m equazioni lineari, in m incognite, risolubili per
ottenere c0,c1,…,cm-1
• Il sistema di m equazioni lineari può essere riscritto, in
forma matriciale, come…
•
(zm+1,zm+2,…, z2m )=(c0,c1,…,cm-1)
(
z1 z2 … z m
z2 z3 … zm+1
… … …
zm zm+1 … z2m-1
)
Se la matrice dei coefficienti ammette inversa (mod 2),
(c0,c1,…,cm-1)=(zm+1,zm+2,…,z2m )
(
z1 z2 … z m
z2 z3 … zm+1
… … …
zm zm+1 … z2m-1
)
-1
Esempi di crittoanalisi
LFSR Stream cipher  3
In effetti, la matrice ammetterà un’inversa se m è il
grado di ricorrenza utilizzato per generare il flusso di
chiavi
• Esempio 4
Supponiamo che Oscar sappia che m=5 e sia in
possesso del testo cifrato 101101011110010,
corrispondente al plaintext 011001111111000  i bit
del keystream sono
110100100001010
mentre il sistema lineare da risolvere, utilizzando i
primi dieci bit del flusso di chiavi è:
•
1
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
( )
(0,1,0,0,0)=(c0,c1,c2,c3)=
Esempi di crittoanalisi
LFSR Stream cipher  4
•
Si può verificare che…
1
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
-1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
1
0
1
0
1
1
0
( )( )
( )
=
da cui
(c0,c1,c2,c3)=(0,1,0,0,0)
0
1
0
0
1
Pertanto la regola di ricorrenza è
zi+5=zi+zi+3 (mod 2)
=(1,0,0,1,0)