Breaking DES
Corso di Sicurezza Reti
Dott. Giovanni Ciraolo
Anno Accademico 2003-2004
I sei modi di “rompere” DES
•
•
•
•
•
•
Ricerca esaustiva della chiave
Elaboratore dedicato
Cluster di Computer
Time-Memory Tradeoff
Criptoanalisi Differenziale
Criptoanalisi Lineare
Ricerca esaustiva della chiave
• Supponendo di avere un Blocco C del ciphertext
(64-bits) e di una parziale conoscenza del
contenuto del plaintext è possibile applicare la
funzione di decryption DK[C] su tutto lo spazio
delle chiavi.
• In un elaboratore capace di eseguire una
decryption alla frequenza di 300 Mhz
occorrerebbero all’incirca 7 anni!
Elaboratore dedicato
• Nel 1998 L’EFF (Electronic Frontier Fundation)
costruisce l’elaboratore “Deep Crack”.
• Deep Crack esegue decription alla frequenza di
85 Ghz, ed è capace di trovare la chiave
mediamente in 4 giorni!
• Occorrono 200,000 $ per costruirlo.....(Non sono
poi molti...)
• Dopo questo esperimento la NSA (National
Security Agency) ha dichiarato che DES non è
più sicuro.....
Cluster di computer
• E’ un’alternativa molto meno costosa a “Deep
Crack”, si sfrutta internet e un gran numero di
volontari che donano il tempo di “Idle” dei loro
computer.
• Nel gennaio 1999 la Distribuited.Net usando più
di 100,000 computer collegati ad internet ha
trovato una chiave in 23 giorni.
• Si può usare anche il sistema di calcolo
distribuito “Grid” sviluppato al CERN.
GRID
:
CERN –
Tier 0
Client
Client
Client
Data Server
Tier 1
Client
Data Server
Tier 2/3
Data Server
Tier 2/3
desktop
Client
deskop
Time-Memory Tradeoff
• Cerchiamo di diminuire il tempo della
ricerca esaustiva memorizzando un
dizionario di chiavi.
• Le chiavi vengono ricercate sul dizionario.
• In media è possibile criptoanalizzare ogni
Criptosistema simmetrico con N chiavi in
N2/3 operazioni utilizzano N2/3 word di
memoria.
Time-Memory Tradeoff
• L’algoritmo DES opera su blocchi di plaintext P
di 64-bit e produce blocchi di ciphertext C
usando una chiave a 56-Bit.
C=EK(P)
• Sia P0 un blocco di plaintext fissato definiamo
f(K)=R[EK(P)]
Dove R è una qualsiasi riduzione da 64-bit a 56bit
Costruzione della funzione f(k)
La funzione f(K)
• Si calcola facilmente.
• La sua complessità è equivalente alla
funzione di criptatura di DES.
• Calcolare K da f(K) è molto difficile, è un
problema equivalente alla Criptoanalisi di
DES.
• Può essere considerata una funzione
One-Way.
Precomputazione: Costruzione
della Matrice delle immagini di f.
• Scegliamo uniformemente nello spazio
delle chiavi {1,...,256} una distribuzione
casuale di m punti di partenza:
SP1,SP2,...,SPm
• Poniamo Xi0=SPi, con 1≤i≤m
• Calcoliamo Xij=f(Xi,j-1), con 1≤i≤t
• Chiamiamo EPi = ft(SPi) i punti di arrivo.
Precomputazione:
Matrice delle Immagini di f
Precomputazione:
Riduzione della memoria e
memorizzazione della matrice
•
•
Un metodo per ridurre l’occupazione
della memoria è quella di memorizzare
solamente le coppie:
{EPi,SPi}, con i=1,..m
Le coppie sono memorizzate in ordine
crescente rispetto ai punti di arrivo.
Computazione:
Ricerca della chiave
• Supponiamo di conoscere un plaintext P0 con il
relativo ciphertex C0 criptato con una chiave
sconosciuta K.
• C0=EK(P0)
• Applichiamo la funzione di riduzione R
• Y1=R(C0)=f(K)
• E’ possibile verificare rapidamente se Y1 è un
EPi.
• Nota: Se Y1 non è EPi la chiave K non è nella
colonna precedente a quella degli EPi.
Computazione:
Ricerca della Chiave
• Se Y1=EPi
1. K=Xi,j-1 (K è nella colonna precendente al
punto di arrivo) , calcoliamo Xi,j-1 e
controlliamo se decifra C0 in P0.
2. EPi ha più di una immagine
inversa.(Falso allarme)
Computazione: Ricerca della
Chiave
•
Se Y1 non è un punto di arrivo o è un falso
allarme calcoliamo Y2=f(Y1) se:
1. Y2=EPi e controlliamo se Xi,t-2 decifra C0 in P0.
2. Altrimenti la chiave non è nella t-2-esima colonna e
calcoliamo Y3=f(Y2)
•
Analogamente calcoliamo Y4=f(Y3),.., Yt=f(Yt-1)
per controllare rispettivamente che la chiave
sia nella colonna t-4,.....,0
Stima del Successo
• Se tutti gli mt elementi che vanno dalla colonna 0
alla colonna t-1 sono diversi e se K è scelta
uniformemente dall’insieme di tutti i possibili valori
la probabilita di successo P(S) è:
mt
P ( S )  56
2
Ecco un bel Teorema
Teorema: Se f:{1,..,256}→ {1,..,256} è una funzione
casuale e K è scelta uniformenete in {1,..,256}
allora la probabilità di successo è limitato dalla
sequente relazione:
 (2  it ) 
1

P( S )  56  
56
2 i 1 j  2

m
t 1
56
j 1
Dimostrazione: La dimostrazione è strettamemente
correlata al problema del compleanno.
Note
• Il teorema dimostra che non guadagnamo
molto se incrementiamo m o t raggiunta la
relazione mt2=256
• Quando mt2=256 la probabilità di
successo è P(S)≈0.75
La funzione di riduzione R:
“Il Diavolo si annidia nei particolari”
• La scelta della funzione di riduzione condiziona
pesantemente le prestazioni dell’algoritmo.
• Ad ogni R è associata una matrice delle
immagini.
• Lo spazio delle scelte di R è (64!)/(8!)=3x1084.
• Fortunatamente DES può essere considerato un
buon generatore pseudocasuale di numeri,
perciò la funzione R non varia molto la struttura
ciclica della generazione dei numeri.
I falsi allarmi
• Teorema: Il numero atteso E(F) dei falsi allarmi
per matrice è limitato dalla seguente relazione:
mt (t  1)
E(F ) 
57
2
Nota: Quando occorre un falso allarme, sono
necessarie al massimo t operazioni per scartarlo.
Se mt2=256 il contributo dato dal controllo sui falsi
allarmi incrementa al massimo del 50% il tempo di
computazione.
Una piccola prova
• Utilizzando un DES con chiave ridotta a
16-bit e m=t=16 e utilizzando 30 differenti
funzioni di riduzione abbiamo ottenuto una
probabilità di successo pari a al 10% con
un tempo di 3-4 ore.
• I tempi possono essere facilmente ridotti
se utilizziamo un sistema distribuito
(...purtroppo sono stato fermato....).