Breaking DES

Corso di Sicurezza RetiDott. 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:

D a t a S e r v e rT i e r 2 / 3

D a t a S e r v e r T i e r 2 / 3

D a t a S e r v e r T i e r 1

C l i e n t

C l i e n t

C l i e n t

C l i e n t

C l i e n t

d e s k o p

d e s k t o p

C E R N –T i e r 0

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 56-bit

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) è:

562)(mt

SP

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:

1

1

1

56

56

56 2

)2(

2

1)(

jm

i

t

j

itSP

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:

572

)1()(

tmtFE

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