Come è stato violato DES

DES ha 2^56 chiavi possibili, equivalenti a circa 72 quadrilioni (72,057,594,037,927,936) di chiavi. Sebbene sembri un numero enorme, si tratta di uno spazio finito che può essere esplorato sistematicamente con una potenza di calcolo sufficiente.

L'esaurimento delle chiavi (forza bruta) richiede in media di provare metà dello spazio delle chiavi prima di trovare quella corretta. Per DES, ciò significa circa 2^55 tentativi di decifratura, ognuno dei quali richiede poche operazioni sull'hardware moderno.

Nel 1997, RSA Data Security offrì un premio di 10.000 $ per decifrare un messaggio cifrato con DES. Rocke Verser coordinò un'iniziativa di calcolo distribuito su decine di migliaia di computer connessi a Internet.

Dopo 96 giorni di ricerca, la chiave fu trovata. Il testo in chiaro era "Strong cryptography makes the world a safer place." L'iniziativa dimostrò che DES poteva essere violato, sebbene fossero necessari mesi e un coordinamento enorme.

La Electronic Frontier Foundation costruì Deep Crack per 250.000 $ nel 1998. Conteneva 1.856 ASIC personalizzati, ciascuno in grado di testare 2,5 milioni di chiavi DES al secondo, raggiungendo una velocità complessiva di oltre 90 miliardi di chiavi al secondo.

Deep Crack poteva esaurire l'intero spazio delle chiavi di DES in circa 9 giorni, in media. Ciò dimostrò che un avversario determinato, con un investimento di 250.000 $, poteva violare DES in meno di due settimane.

Nella DES Challenge II-1 (febbraio 1998), Deep Crack, insieme alla rete di calcolo volontario distributed.net, violò DES in soli 39 giorni. La Challenge II-2 (luglio 1998) fu risolta in 56 ore.

Il rapido miglioramento, da 96 giorni a 56 ore in un solo anno, dimostrò quanto velocemente i miglioramenti dell'hardware e un coordinamento più efficace potessero accelerare gli attacchi a forza bruta.

Nel gennaio 1999, Deep Crack dell'EFF, insieme a distributed.net, violò la DES Challenge III in sole 22 ore e 15 minuti, vincendo un premio di 10.000 $ offerto da RSA Security.

Questa dimostrazione definitiva del fatto che DES poteva essere violato in meno di 24 ore pose di fatto fine a qualsiasi argomentazione a favore della sicurezza di DES. Poco dopo, NIST avviò il processo di selezione di un sostituto per DES, che sarebbe diventato AES.

Distributed.net organizzò iniziative di calcolo volontario in cui normali utenti di Internet mettevano a disposizione i cicli della propria CPU per le DES Challenge. Al culmine dell'iniziativa parteciparono centinaia di migliaia di computer.

Ogni computer testava una porzione diversa dello spazio delle chiavi, coordinato da un server centrale. Questo modello pionieristico di calcolo distribuito per la crittoanalisi è ancora utilizzato oggi per sfide come la violazione di cifrari obsoleti.

L'esaurimento delle chiavi è efficace perché ogni decifratura DES è veloce (richiede microsecondi sull'hardware) e indipendente. Non esiste alcuna dipendenza tra la verifica della chiave N e quella della chiave N+1, quindi la ricerca può essere parallelizzata perfettamente su un numero qualsiasi di macchine.

Questa natura facilmente parallelizzabile fa sì che raddoppiando l'hardware si dimezzi esattamente il tempo. L'aggiunta di macchine produce un'accelerazione lineare, rendendo vantaggioso il rapporto costi-benefici per gli avversari.

Eli Biham e Adi Shamir pubblicarono la crittoanalisi differenziale nel 1990, una tecnica che sfrutta il modo in cui le differenze nelle coppie di input si propagano attraverso i round del cifrario. Nel caso di DES, richiede teoricamente 2^47 testi in chiaro scelti.

In seguito si è scoperto che le S-box di DES erano state progettate tenendo conto della resistenza alla crittoanalisi differenziale, il che suggerisce che la NSA conoscesse questa tecnica già negli anni Settanta. L'attacco è teoricamente notevole, ma sul piano pratico è superato dalla forza bruta eseguita dall'hardware.

Mitsuru Matsui pubblicò la crittoanalisi lineare nel 1993: per attaccare DES erano necessari 2^43 testi in chiaro noti. Implementò l'attacco e nel 1994 violò DES in via sperimentale, confermando l'analisi teorica.

La crittoanalisi lineare individua approssimazioni lineari del comportamento delle S-box e le usa per recuperare bit della chiave sfruttando una distorsione statistica. In teoria richiede molti meno dati della forza bruta, ma prima degli attacchi basati sull'hardware era impraticabile.

La crittoanalisi differenziale fu pubblicata nel 1990, ma richiede testi in chiaro scelti, un requisito impraticabile nella maggior parte degli scenari reali. La crittoanalisi lineare fu pubblicata nel 1993 e funziona con testi in chiaro noti, ma ne richiede 2^43.

La forza bruta basata sull'hardware (Deep Crack) violò DES in 22 ore nel 1999. In pratica, l'attacco hardware fu più devastante dei progressi teorici della crittoanalisi, perché non richiedeva alcuna coppia speciale testo in chiaro-testo cifrato.

La violazione pubblica e documentata di DES ebbe conseguenze immediate sulle politiche di sicurezza. NIST avviò nel 1997 il processo della competizione per AES, lo stesso anno in cui la DES Challenge I ebbe successo. La competizione fu progettata esplicitamente per evitare le debolezze del processo di standardizzazione di DES.

Banche e agenzie governative iniziarono a passare a 3DES come misura provvisoria mentre veniva sviluppato AES. La tempistica delle violazioni di DES determinò direttamente l'urgenza e i tempi del processo di adozione di AES.

Verifichi la Sua comprensione della storia delle violazioni di DES.

DES fu violato in tempi sempre più brevi: 96 giorni nel 1997, 56 ore nel 1998 e 22 ore nel 1999. Deep Crack dell'EFF, costato 250.000 $, utilizzava ASIC personalizzati per testare 90 miliardi di chiavi al secondo.

Sia la crittoanalisi differenziale (2^47 testi in chiaro scelti) sia la crittoanalisi lineare (2^43 testi in chiaro noti) possono teoricamente violare DES, ma la forza bruta basata sull'hardware fu l'elemento decisivo sul piano pratico. La violazione in 22 ore segnò la fine di DES come cifrario utilizzabile.