Jak złamano DES

DES ma 2^56 możliwych kluczy, co odpowiada w przybliżeniu 72 biliardom (72 057 594 037 927 936) kluczy. Choć brzmi to ogromnie, jest to skończona przestrzeń, którą można systematycznie przeszukać przy użyciu odpowiedniej mocy obliczeniowej.

Wyczerpanie przestrzeni kluczy (atak brute force) wymaga średnio sprawdzenia połowy przestrzeni kluczy przed znalezieniem właściwego klucza. W przypadku DES oznacza to około 2^55 prób deszyfrowania, z których każda wymaga kilku operacji na nowoczesnym sprzęcie.

W 1997 roku RSA Data Security zaoferowała nagrodę w wysokości 10 000 USD za złamanie wiadomości zaszyfrowanej DES. Rocke Verser koordynował rozproszone obliczenia prowadzone na dziesiątkach tysięcy komputerów połączonych z Internetem.

Po 96 dniach poszukiwań odnaleziono klucz. Tekst jawny brzmiał: "Strong cryptography makes the world a safer place." Wysiłek ten pokazał, że DES można złamać, choć wymagało to miesięcy pracy i ogromnej koordynacji.

Electronic Frontier Foundation zbudowała Deep Crack za 250 000 USD w 1998 roku. Urządzenie zawierało 1856 niestandardowych układów ASIC, z których każdy mógł testować 2,5 miliona kluczy DES na sekundę. Łączna szybkość Deep Crack przekraczała 90 miliardów kluczy na sekundę.

Deep Crack mógł średnio wyczerpać całą przestrzeń kluczy DES w około 9 dni. Dowodziło to, że zdeterminowany przeciwnik dysponujący inwestycją w wysokości 250 000 USD mógł złamać DES w mniej niż dwa tygodnie.

W ramach DES Challenges II-1 (luty 1998) Deep Crack wraz z ochotniczą siecią obliczeniową distributed.net złamał DES w zaledwie 39 dni. Wyzwanie II-2 (lipiec 1998) zakończyło się po 56 godzinach.

Gwałtowna poprawa — od 96 dni do 56 godzin w ciągu zaledwie jednego roku — pokazała, jak szybko udoskonalenia sprzętu i lepsza koordynacja mogą przyspieszyć ataki brute force.

W styczniu 1999 roku Deep Crack organizacji EFF wraz z distributed.net złamał DES Challenge III w zaledwie 22 godziny i 15 minut, zdobywając nagrodę w wysokości 10 000 USD od RSA Security.

Ten ostateczny dowód, że DES można złamać w mniej niż 24 godziny, skutecznie zakończył dyskusje na temat bezpieczeństwa DES. Wkrótce potem NIST rozpoczął proces wyboru następcy DES, którym został AES.

Distributed.net organizowała działania oparte na obliczeniach ochotniczych, w ramach których zwykli użytkownicy Internetu udostępniali moc obliczeniową swoich procesorów na potrzeby wyzwań DES. W szczytowym okresie uczestniczyły w nich setki tysięcy komputerów.

Każdy komputer sprawdzał inną część przestrzeni kluczy, a koordynacją zajmował się centralny serwer. Był to początek modelu obliczeń rozproszonych na potrzeby kryptoanalizy, który jest stosowany do dziś w wyzwaniach takich jak łamanie starszych szyfrów.

Wyczerpanie przestrzeni kluczy jest możliwe, ponieważ każde deszyfrowanie DES jest szybkie (na sprzęcie trwa mikrosekundy) i niezależne. Testowanie klucza N nie zależy od testowania klucza N+1, dlatego wyszukiwanie można idealnie zrównoleglić na dowolnej liczbie maszyn.

Ta niezależność zadań sprawia, że podwojenie liczby jednostek sprzętowych dokładnie o połowę skraca czas. Dodawanie kolejnych maszyn zapewnia liniowe przyspieszenie, dzięki czemu taki atak jest korzystny ekonomicznie dla przeciwników.

Eli Biham i Adi Shamir opublikowali metodę kryptoanalizy różnicowej w 1990 roku. Technika ta wykorzystuje sposób, w jaki różnice w parach danych wejściowych propagują się przez rundy szyfru. W przypadku DES teoretycznie wymaga ona 2^47 wybranych tekstów jawnych.

Później ujawniono, że S-boxy DES zostały zaprojektowane z myślą o odporności na kryptoanalizę różnicową, co sugeruje, że NSA znała tę technikę już w latach 70. Atak ten jest imponujący z teoretycznego punktu widzenia, ale w praktyce ustępuje sprzętowemu atakowi brute force.

Mitsuru Matsui opublikował metodę kryptoanalizy liniowej w 1993 roku. Do zaatakowania DES wymaga ona 2^43 znanych tekstów jawnych. Matsui zaimplementował ten atak i eksperymentalnie złamał DES w 1994 roku, potwierdzając analizę teoretyczną.

Kryptoanaliza liniowa znajduje liniowe przybliżenia działania S-boxów i wykorzystuje je do odzyskiwania bitów klucza na podstawie odchylenia statystycznego. Teoretycznie wymaga znacznie mniej danych niż brute force, ale przed pojawieniem się ataków sprzętowych była niepraktyczna.

Kryptoanalizę różnicową opublikowano w 1990 roku, ale wymaga ona wybranych tekstów jawnych, co w większości rzeczywistych scenariuszy jest niepraktyczne. Kryptoanalizę liniową opublikowano w 1993 roku; działa ona na znanych tekstach jawnych, ale wymaga ich 2^43.

Sprzętowy atak brute force (Deep Crack) złamał DES w 22 godziny w 1999 roku. W praktyce atak sprzętowy był bardziej dotkliwy niż teoretyczne postępy w kryptoanalizie, ponieważ nie wymagał żadnych specjalnie dobranych par tekst jawny–szyfrogram.

Publiczne i udokumentowane złamanie DES miało natychmiastowe konsekwencje dla polityki bezpieczeństwa. NIST rozpoczął proces konkursu AES w 1997 roku, czyli w tym samym roku, w którym zakończyło się powodzeniem Wyzwanie DES I. Konkurs zaprojektowano konkretnie tak, aby uniknąć słabości procesu standaryzacji DES.

Banki i agencje rządowe zaczęły przechodzić na 3DES jako rozwiązanie tymczasowe, podczas gdy opracowywano AES. Harmonogram łamania DES bezpośrednio wyznaczył pilność i tempo wdrażania AES.

DES łamano coraz szybciej: w 1997 roku zajęło to 96 dni, w 1998 roku 56 godzin, a w 1999 roku 22 godziny. Deep Crack organizacji EFF, kosztujący 250 000 USD, wykorzystywał niestandardowe układy ASIC do testowania 90 miliardów kluczy na sekundę.

Zarówno kryptoanaliza różnicowa (2^47 wybranych tekstów jawnych), jak i kryptoanaliza liniowa (2^43 znanych tekstów jawnych) teoretycznie łamią DES, jednak praktycznym ciosem okazał się brute force z użyciem sprzętu. Złamanie szyfru w 22 godziny zakończyło okres, w którym DES był użytecznym szyfrem.