Le discussioni sulla possibile debolezza del DES dovuta alla dimensione troppo ridotta della chiave sono continuate praticamente senza sosta nella comunità crittologica, ma senza approdare a qualcosa di concreto.
In effetti il DES, è passato già attraverso ben tre revisioni periodiche, una ogni cinque anni, che ne hanno riconfermato la validità come standard federale.
Agli inizi del 1997 l'RSA, decise di verificare se i 56 bit del vecchio DES erano ancora sufficienti contro l'attacco di forza bruta.
Il 28 gennaio 1997, l'RSA lanciò una pubblica sfida, estesa a chiunque, avente come oggetto la decifrazione di alcuni brevi testi cifrati col DES e con l'RC5 secondo chiavi di varie lunghezze.
I messaggi da decifrare consistevano in una prima parte nota, in modo che per il decifratore era possibile accorgersi di aver trovato la giusta chiave di decifrazione, ed in una seconda parte segreta che costituiva la prova dell'avvenuta decifrazione.
I messaggi da decifrare furono pubblicati alle 9:00 a.m. del 28 gennaio 1997 sul sito web dell'RSA, e subito partì la gara. In palio, vi erano i seguenti premi in denaro:
Alle 12:30 a.m. dello stesso 28 gennaio, dopo solo tre ore e mezza dall'inizio della sfida, l'RC5 a 40 bit venne forzato da uno studente con una workstation.
Che 40 bit fossero davvero troppo pochi lo sospettavano tutti, ma che ci volesse davvero così poco per forzarli lo immaginavano in pochi.
Il passo successivo, la forzatura dell'RC5 a 48 bit, arrivò poco dopo: per la precisione il 10 febbraio alle 10:00 a.m. a sole 313 ore di distanza dalla pubblicazione dei messaggi cifrati da parte dell'RSA. Un intero "campus" universitario si era mobilitato per questa prova.
Attacco distribuito
Lo spazio delle chiavi del DES è formato da 256 elementi, che in notazione decimale equivale a circa 72 milioni di miliardi di combinazioni distinte, per cui un ipotetico computer a 500 MHz che potesse sondare una chiave ad ogni ciclo di clock impiegherebbe 144 milioni di secondi ad esaminarle tutte; supponendo che sia sufficiente esaminare solo la metà delle chiavi occorrerebbero comunque ben 834 giorni, pari a 2 anni e 3 mesi di lavoro continuativo. Da ciò possiamo concludere che 56 bit sono sufficienti, per cui non basterebbe un supercomputer e nemmeno i calcolatori di un’intera università per effettuare una ricerca esaustiva.
Così il 13 marzo 1997 Rocke Verser, un programmatore di Loveland nel Colorado, fece partire una gigantesca iniziativa, chiamata DESCHALL, con la quale mirava a demolire il DES utilizzando la potenza di calcolo, altrimenti inutilizzata, di migliaia di computer sparsi in tutto il mondo.
Il progetto prevedeva la partecipazione cooperativa, volontaria e disinteressata, di migliaia di partecipanti, singoli utenti od organizzazioni. Costoro coordinarono i propri sforzi servendosi della rete Internet, suddividendo lo spazio delle chiavi ed esaminandone ciascuno una parte, a seconda delle proprie disponibilità di hardware e di tempo macchina.
Verser scrisse un apposito client di ricerca che venne distribuito gratuitamente a tutti i partecipanti. Di giorno in giorno aumentarono coloro che si dedicavano a questa impresa.
La sera del 17 giugno un programmatore, Michael K. Sanders, con un computer con le seguenti caratteristiche:
riuscì a vincere la gara.
Bastò cercare solo il 24,6% dello spazio delle chiavi. La ricerca coinvolse complessivamente circa 70000 computer e procedette ad un ritmo costantemente crescente: la velocità media negli ultimi giorni era di circa sette miliardi di chiavi esaminate al secondo, ossia lo 0,7% dell'intero spazio delle chiavi al giorno; se si fosse mantenuto questo ritmo già dall'inizio allora l'intera ricerca sarebbe durata solo 32 giorni, anziché 39 giorni. Il messaggio segreto era: "Strong cryptography makes the world a safer place".
I diecimila dollari del premio furono divisi in due quote: il 60% a Verser ideatore del progetto DESCHALL ed il 40% a Michael Sanders che effettivamente trovò la chiave giusta.
Ora questo costituisce un attacco di tipo distribuito che portò i responsabili della FBI e della NSA ad affermare che il DES era praticamente indecifrabile, dato che per riuscire a decifrarlo occorreva lo sforzo congiunto di migliaia di computer per settimane di tempo macchina.
Attacco tramite chip
Per decenni si pensava di costruire un computer specializzato in grado di forzare il DES mediante ricerca esaustiva delle chiavi.
Nel 1977 Diffie ed Hellman, due importanti crittologi americani, cominciarono a chiedersi pubblicamente se 56 bit di chiave non fossero davvero pochi, e giunsero alla conclusione che il Governo di una potenza industriale avrebbe potuto tranquillamente investire una ventina di milioni di dollari necessari, a realizzare una macchina superparallela per forzare il DES.
Essi suggerirono che si sarebbe potuto costruire un chip a tecnologia VLSI che avrebbe potuto testare 106 chiavi al secondo. Una macchina che utilizzava 106 chip di questo tipo avrebbe rotto il sistema in un giorno. Il costo di tale macchina era di $20.000.000.
Al loro primo studio ne seguirono altri di persone diverse, che comunque concordavano che la realizzazione di una macchina del genere fosse realmente possibile, anzi, qualcuno sosteneva che essa fosse stata realmente costruita e venisse utilizzata correntemente dalla NSA e forse da qualche altra organizzazione.
Fra questi ci fu Michael Wiener, che alla Rump Session di CRYPTO 1993 propose il progetto di una macchina composta da vari chip collegati tra loro (pipelined) che operassero in parallelo. Ogni chip costava $10,50, per cui con una macchina costruita con 5760 chip (e per un costo di 100.000 dollari) si sarebbe rotto il sistema all'incirca in un giorno e mezzo. Con 10 di tali macchine e quindi con 1.000.000 di dollari si sarebbe rotto il DES in tre ore e mezzo.
Altre macchine (con costi simili) sono state progettate e costruite, ma nonostante ciò il problema non è stato risolto in quanto bisognava "cablare" tale macchina sul canale di comunicazione, avendo, quindi, tutta una serie di problemi di natura diversa.
Una di queste macchine fu progettata dall'EFF, che per mostrare che il DES non era più sicuro condusse una ricerca che mostrava che il DES poteva essere rotto con un costo basso (vedi Deep Crack).
Il sistema della EFF fu messo alla prova il 15 luglio 1998 quando la RSA diede il via ad una nuova sfida, ottenendo come risultato che in sole 56 ore il Deep Crack ricavò la chiave di cifratura, battendo ogni record.
Il costo reale del DES Cracker era stato di poco superiore ai $200.000, di cui circa $130.000 di spese per i chip e circa $80.000 per il progetto e il suo sviluppo.
Ultima sfida RSA
L'ultima sfida "DES Challenge III", è stata pubblicata alle ore 9.00 a.m. del 18 gennaio 1999. In essa vi era il seguente testo cifrato: 92 2C 68 C4 7A EA DF F2 ricavato da un messaggio sconosciuto di testo in chiaro, che aveva un messaggio fisso e conosciuto come header.
La chiave segreta era generata in modo random e poi distribuita fra il software che generava la disputa così che nessuno, neanche gli amministratori della disputa, sapevano quale fosse. La distribuzione del premio per questa challenge è stata la seguente:
I vincoli di tempo hanno suggerito ai due vincitori delle dispute precedenti di collaborare, infatti per battere il record precedente di 56 ore, Distributed.Net, una coalizione mondiale di quasi 100.000 entusiasti di computer, ha lavorato con il "Deep Crack" dell' EFF, riuscendo a vincere la sfida dell'RSA, DES Challenge III, in un tempo record di 22 ore e 15 minuti.
I PC coinvolti in questa sfida vanno da modesti PC del 1990 fino alle più potenti macchine multiprocessore.
Partendo come base dalla RSA Data Security Conference & EXPO, una grande conferenza sulla sicurezza dei dati e sulla crittografia, che è stata tenuta a San Jose, California, il "Deep Crack" dell'EFF e i computer di Distributed.Net hanno testato 245 miliardi di chiavi per secondo finché la chiave non è stata trovata.
Il messaggio in chiaro ricavato è: "See you in Rome (second AES conference, March 22-23, 1999)" .
L'RSA ha dato un premio di 10.000 dollari ai vincitori. Lo scopo della sfida DES Challenge III era non solo quello di recuperare la chiave segreta usata per cifrare il messaggio con il DES, ma anche di farlo più rapidamente della sfida precedente.
Conclusioni
La lunghezza della chiave di cifratura DES, considerata più che sicura nel 1977, è ormai assolutamente insufficiente per resistere ad un attacco di forza bruta, come l'iniziativa DESCHALL ha dimostrato in maniera evidente.
Per avere una reale sicurezza nei sistemi crittografici non bastano più chiavi brevi, ma occorrono chiavi lunghe almeno il doppio in modo da portare la lunghezza fuori dalla portata di supercomputer attuali e futuri.
L'ultima challenge mostra che stiamo giungendo rapidamente al momento in cui chiunque, con un PC standard, può potenzialmente costituire una vera minaccia per i sistemi che si basano su un tipo di chiave così vulnerabile.
Tuttavia i sistemi che sfruttano il DES non sono compromessi del tutto, ma chi lo usa è invitato a riconsiderare i livelli di sicurezza richiesti e passare a sistemi ben più sicuri quali il TRIPLO DES, proposto da Tuchmann e già standardizzato dall'ANSI e dall'ISO, che con i suoi 112 bit offre una protezione più che adeguata.