Sådan blev DES knækket

DES har 2^56 mulige nøgler, hvilket svarer til cirka 72 billiarder (72.057.594.037.927.936) nøgler. Selvom det lyder enormt, er det et endeligt område, som systematisk kan gennemgås med tilstrækkelig regnekraft.

Udtømning af nøgleområdet (udtømmende søgning) kræver i gennemsnit, at man afprøver halvdelen af nøgleområdet, før den korrekte nøgle findes. For DES betyder det cirka 2^55 dekrypteringsforsøg, hvor hvert forsøg kun kræver få operationer på moderne hardware.

I 1997 udlovede RSA Data Security en præmie på $10.000 for at bryde en DES-krypteret meddelelse. Rocke Verser koordinerede en distribueret databehandlingsindsats på tværs af titusindvis af internetforbundne computere.

Efter 96 dages søgning blev nøglen fundet. Klarteksten var "Stærk kryptografi gør verden til et sikrere sted." Indsatsen viste, at DES kunne brydes, selvom det krævede måneder og massiv koordinering.

Electronic Frontier Foundation byggede Deep Crack til $250.000 i 1998. Den indeholdt 1.856 specialdesignede ASIC'er, som hver kunne afprøve 2,5 millioner DES-nøgler i sekundet, hvilket gav Deep Crack en samlet hastighed på over 90 milliarder nøgler i sekundet.

Deep Crack kunne i gennemsnit udtømme hele DES' nøgleområde på cirka 9 dage. Det beviste, at en målrettet modstander med en investering på $250.000 kunne bryde DES på under to uger.

I DES Challenges II-1 (februar 1998) brød Deep Crack sammen med det frivillige databehandlingsnetværk distributed.net DES på blot 39 dage. Challenges II-2 (juli 1998) blev brudt på 56 timer.

Den hurtige forbedring fra 96 dage til 56 timer på blot ét år viste, hvor hurtigt hardwareforbedringer og bedre koordinering kunne fremskynde udtømmende angreb.

I januar 1999 brød EFFs Deep Crack sammen med distributed.net DES Challenge III på blot 22 timer og 15 minutter og vandt en præmie på $10.000 fra RSA Security.

Denne afgørende demonstration af, at DES kunne brydes på under 24 timer, satte reelt en stopper for alle argumenter for DES' sikkerhed. Kort efter begyndte NIST processen med at udvælge en erstatning for DES, som blev AES.

Distributed.net organiserede frivillige databehandlingsindsatser, hvor almindelige internetbrugere donerede CPU-cyklusser til DES-udfordringerne. På det højeste deltog hundredtusindvis af computere.

Hver computer afprøvede en forskellig del af nøgleområdet, koordineret af en central server. Det banede vejen for modellen med distribueret databehandling til kryptoanalyse, som stadig bruges i dag til udfordringer som at bryde ældre chiffere.

Udtømning af nøgleområdet fungerer, fordi hver DES-dekryptering er hurtig (mikrosekunder på hardware) og uafhængig. Der er ingen afhængighed mellem at afprøve nøgle N og nøgle N+1, så søgningen kan paralleliseres perfekt på et vilkårligt antal maskiner.

Denne oplagt paralleliserbare egenskab betyder, at en fordobling af hardwaremængden nøjagtigt halverer tiden. Flere maskiner giver en lineær hastighedsforøgelse, hvilket gør økonomien attraktiv for angribere.

Eli Biham og Adi Shamir offentliggjorde differential kryptoanalyse i 1990, en teknik der udnytter, hvordan forskelle i inddata-par forplanter sig gennem chifferets runder. For DES kræver den teoretisk 2^47 valgte klartekster.

Det blev senere afsløret, at DES' S-bokse var udformet med modstandsdygtighed over for differential kryptoanalyse for øje, hvilket tyder på, at NSA kendte til denne teknik i 1970'erne. Angrebet er teoretisk imponerende, men i praksis overgået af hardwarebaseret udtømmende søgning.

Mitsuru Matsui offentliggjorde lineær kryptoanalyse i 1993, hvor der kræves 2^43 kendte klartekster for at angribe DES. Han implementerede angrebet og brød eksperimentelt DES i 1994, hvilket bekræftede den teoretiske analyse.

Lineær kryptoanalyse finder lineære tilnærmelser til S-boksenes funktion og bruger dem til at gendanne nøglebit med en statistisk skævhed. Den kræver teoretisk langt mindre data end udtømmende søgning, men var upraktisk før hardwareangrebene.

Differential kryptoanalyse blev offentliggjort i 1990, men kræver valgte klartekster, hvilket er upraktisk i de fleste virkelige scenarier. Lineær kryptoanalyse blev offentliggjort i 1993 og fungerer med kendte klartekster, men kræver 2^43 af dem.

Hardwarebaseret udtømmende søgning (Deep Crack) brød DES på 22 timer i 1999. I praksis var hardwareangrebet mere ødelæggende end de teoretiske fremskridt inden for kryptoanalyse, fordi det slet ikke krævede særlige klartekst-chiffertekst-par.

Det offentligt dokumenterede brud på DES fik umiddelbare konsekvenser for sikkerhedspolitikken. NIST begyndte konkurrenceprocessen for AES i 1997, det samme år som DES Challenge I lykkedes. Konkurrencen var specifikt udformet for at undgå svaghederne ved DES-standardiseringsprocessen.

Banker og myndigheder begyndte at gå over til 3DES som en midlertidig foranstaltning, mens AES blev udviklet. Tidslinjen for bruddet på DES bestemte direkte, hvor hurtigt AES skulle indføres, og hvornår det skulle ske.

DES blev brudt stadig hurtigere: 96 dage i 1997, 56 timer i 1998 og 22 timer i 1999. EFFs Deep Crack til $250.000 brugte specialdesignede ASIC'er til at afprøve 90 milliarder nøgler i sekundet.

Både differential kryptoanalyse (2^47 valgte klartekster) og lineær kryptoanalyse (2^43 kendte klartekster) kan også teoretisk bryde DES, men hardwarebaseret udtømmende søgning var det angreb, der i praksis fældede DES. Bruddet på 22 timer satte en stopper for DES som brugbart chiffer.