Data Encryption Standard

DES (ang. Data Encryption Standard) – symetryczny szyfr blokowy zaprojektowany w 1975 roku przez IBM na zlecenie ówczesnego Narodowego Biura Standardów USA (obecnie NIST). Od 1976 do 2001 roku stanowił standard federalny USA, a od roku 1981 standard ANSI dla sektora prywatnego (znany jako Data Encryption Algorithm). Od kilku lat uznawany jest za algorytm niezapewniający odpowiedniego bezpieczeństwa, głównie ze względu na niewielką długość klucza, która sprawia, że jest bardzo podatny na atak siłowy. W 2001 roku w USA został zastąpiony w ramach standardu federalnego przez AES. Jest jednym z najlepiej przeanalizowanych algorytmów szyfrujących.

Data Encryption Standard

Funkcja Feistela algorytmu DES
Rodzaj algorytmu	symetryczny szyfr blokowy
Data stworzenia	1975
Autorzy	IBM
Wielkość bloku wejściowego	64 bity
Długość klucza	56 (+8 parzystości) [bit]
Liczba rund	16
Data złamania	1997
Złamany przez	DESCHALL Project
Skuteczne ataki	kryptoanaliza liniowa, kryptoanaliza różnicowa

Historia

DES powstał jako część zapoczątkowanego w 1972 roku przez Narodowe Biuro Standardów USA programu zabezpieczania informacji, w ramach którego planowano stworzyć jeden algorytm kryptograficzny do szyfrowania danych – taki sam dla ich przechowywania i przesyłania. 15 maja 1973 roku po konsultacjach z NSA w Rejestrze Federalnym opublikowane zostały wymagania projektowe stawiane potencjalnemu algorytmowi: miał zapewniać duży stopień bezpieczeństwa, być kompletnie określony i nietrudny do zrozumienia oraz łatwy do zaimplementowania sprzętowego. Miał ponadto spełniać warunki umożliwiające jego eksport. Dodatkowo jego bezpieczeństwo, zgodnie z zasadą Kerckhoffsa, nie mogło opierać się na tajności algorytmu, lecz na kluczu.

Wymagania te były, jak na owe czasy, tak rygorystyczne, że pomimo dużej liczby zgłoszeń pierwsza tura konkursu nie wyłoniła zadowalającego algorytmu. W związku z tym 27 sierpnia 1974 NBS ponownie opublikował informacje o zapotrzebowaniu na algorytm kryptograficzny. Wkrótce potem IBM zgłosił do konkursu swój algorytm, oparty na szyfrze blokowym Lucifer, spełniający podane kryteria. Nad rozwojem zgłoszonego szyfru pracowali Roy Adler, Don Coppersmith, Horst Feistel, Edna Grossman, Alan Konheim, Carl Mayer, Bill Notz, Lynn Smith, Walt Tuchman oraz Bryant Tuckerman. W celu oceny bezpieczeństwa algorytmu NBS zwróciło się o pomoc do NSA, a IBM rozpoczął procedurę jego patentowania.

Szczegóły algorytmu oraz oświadczenie IBM zezwalające na jego wykorzystanie w dowolnym celu zostały opublikowane 17 maja 1975 roku w Rejestrze Federalnym, a kilka miesięcy później, 1 sierpnia 1975 roku, Narodowe Biuro Standardów wydało komunikat zachęcający wszystkich zainteresowanych do wypowiedzenia się na temat jego bezpieczeństwa i przydatności. Po wielu ocenach krytycznych oraz zarzutach wobec NSA o celowe osłabienie szyfru poprzez skrócenie długości klucza oraz modyfikację S-bloków zorganizowano dwie konferencje naukowe, mające na celu ocenić algorytm. Na pierwszej z nich szyfr oceniono od strony matematycznej, na drugiej natomiast omawiano sensowność wydłużenia klucza.

23 listopada 1976 Data Encryption Standard został zaakceptowany jako standard federalny – możliwe było jego używanie do szyfrowania wszelkich nietajnych danych rządowych USA. Publikacja pełnego opisu algorytmu odbyła się 15 stycznia 1977 roku w ramach dokumentu FIPS PUB 46 – Data Encryption Standard. Pozostałe dokumenty związane ze standardem zostały opublikowane w roku 1980 (FIPS PUB 81 – DES Modes of Operation) oraz w roku 1981 (FIPS PUB 74 – Guidelines for Implementating and Using the NBS Data Encryption Standard). Algorytm kilkukrotnie (1983, 1988 – FIPS-46-1, 1993 – FIPS-46-2 oraz 1999 – FIPS-46-3) zdobywał certyfikat przedłużający jego ważność jako standardu federalnego. Ostatecznie został wycofany w 2001 roku, kiedy standardem federalnym stał się Advanced Encryption Standard.

W 1981 roku ANSI uznało DES za standard sektora prywatnego (ANSI X3.92-1981), jednocześnie przemianowując go na Data Encryption Algorithm.

Chronologia

Data	Wydarzenie
15 maja 1973	Narodowe Biuro Standardów USA po raz pierwszy publikuje informacje o zapotrzebowaniu na algorytm kryptograficzny
27 sierpnia 1974	NBS po raz drugi publikuje informacje o zapotrzebowaniu na algorytm kryptograficzny
17 marca 1975	Opis algorytmu DES zostaje opublikowany w Rejestrze Federalnym
Sierpień 1976	Pierwszy warsztat naukowy na temat DES
Wrzesień 1976	Drugi warsztat naukowy, na którym dyskutowano podstawy matematyczne algorytmu
23 listopada 1976	DES zostaje zatwierdzony jako standard
15 stycznia 1977	Opis algorytmu DES zostaje wydany jako dokument FIPS PUB 46
1983	Certyfikat ważności DES po raz pierwszy zostaje przedłużony na kolejne 5 lat
22 stycznia 1988	Certyfikat ważności DES po raz drugi zostaje przedłużony na kolejne 5 lat; wydana zostaje poprawiona wersja standardu FIPS PUB 46-1
1992	Biham oraz Shamir opisują pierwszy teoretyczny atak, który jest bardziej skuteczny niż atak brutalny: kryptoanalizę różnicową. Wymaga jednak nieralistycznej liczby tekstów jawnych: $2^{47}.$
30 grudnia 1993	Certyfikat ważności DES po raz trzeci zostaje przedłużony na 5 lat; opublikowany zostaje FIPS PUB 46-2
1994	Pierwsza próba kryptoanalizy DES z wykorzystaniem kryptoanalizy liniowej (Matsui, 1994).
czerwiec 1997	Projekt DESCHALL jako pierwszy odszyfrowuje wiadomość zaszyfrowaną DES.
1998	Projekt distributed.net odtwarza klucz w ciągu 41 dni.
lipiec 1998	EFF DES cracker (znany też jako Deep Crack) stworzony przez EFF odtwarza klucz algorytmu DES w 56 godzin.
19 stycznia 1999	Deep Crack wspólnie z distributed.net łamie klucz algorytmu w 22 godziny i 15 minut
25 października 1999	Certyfikat ważności DES po raz czwarty zostaje przedłużony; opublikowany zostaje FIPS PUB 46-3, który określa 3DES jako preferowany system szyfrowania
26 listopada 2001	Opublikowany zostaje standard AES jako FIPS 197
26 lipca 2004	NIST na łamach Federalnego Rejestru proponuje wycofanie FIPS 46-3 (wraz z kilkoma innymi standardami)
19 maja 2005	NIST wycofuje FIPS 46-3

Kontrowersje związane z udziałem NSA

Gdy 1 sierpnia 1975 Narodowe Biuro Standardów wydało komunikat zachęcający wszystkich zainteresowanych do oceny algorytmu, pojawiło się wiele głosów oskarżające NSA o celowe osłabienie szyfru w taki sposób, aby nikt poza nimi nie mógł go złamać. Podstawowym zarzutem było osłabienie klucza szyfrującego – w algorytmie Lucifer, na którym opierał się DES, klucz ten miał początkowo 128 bitów, NSA zdołało jednak przekonać IBM do jego skrócenia do 56 bitów. Podejrzewano także, że NSA umieściło w S-blokach tylne wejście, umożliwiające im proste odszyfrowanie szyfrogramów. Alan Konheim, jeden z twórców DES, stwierdził, że wysłane do NSA struktury S-bloków zostały zmienione przez Agencję. Sprawa podejrzanej ingerencji NSA w strukturę szyfru była w 1978 roku badana przez Komisję Wywiadu Senatu USA, która w nieutajnionym podsumowaniu zwolniła Agencję Bezpieczeństwa z zarzutów.

Zarzuty związane z osłabieniem S-bloków były nieuzasadnione. Okazało się bowiem, że DES jest wyjątkowo odporny na kryptoanalizę różnicową, opublikowaną w roku 1990 przez Eli Bihama i Adi Shamira (nie byli oni pierwszymi odkrywcami). Zarówno IBM, jak i NSA znały już wcześniej tę technikę kryptoanalizy i zaprojektowali S-bloki w taki sposób, aby były na nią odporne.

Algorytm

Schemat początkowa permutacji bloku – tabela powinna być czytana od lewej do prawej strony, od góry do dołu. Na miejsce bitu pierwszego podstawiany jest bit 58, na miejsce bitu drugiego podstawiany jest bit 50, i tak dalej

DES jest szyfrem blokowym z blokami o długości 64 bitów. Do szyfrowania i deszyfrowania danych wykorzystywanych jest 56 bitów klucza, który zapisany jest w postaci 64-bitowego ciągu, w którym co 8 bit jest bitem kontrolnym i może służyć do kontroli parzystości. Kilka z kluczy uważanych jest za klucze słabe oraz klucze półsłabe.

Algorytm szyfrowania danych jest następujący: na początku tekst jawny, który ma zostać zaszyfrowany, dzielony jest na bloki 64-bitowe. Następnie dla każdego bloku wykonywane są następujące operacje:

• dokonywana jest permutacja początkowa bloku przestawiająca bity w pewien określony sposób – nie zwiększa ona bezpieczeństwa algorytmu, a jej początkowym celem było ułatwienie wprowadzania danych do maszyn szyfrujących używanych w czasach powstania szyfru
• blok wejściowy rozdzielany jest na dwie 32-bitowe części: lewą oraz prawą
• wykonywanych jest 16 cykli tych samych operacji, zwanych funkcjami Feistela, podczas których dane łączone są z kluczem. Operacje te wyglądają następująco:
  • bity klucza są przesuwane, a następnie wybieranych jest 48 z 56 bitów klucza
  • prawa część danych rozszerzana jest do 48-bitów za pomocą permutacji rozszerzonej
  • rozszerzona prawa połowa jest sumowana modulo 2 z wybranymi wcześniej (i przesuniętymi) 48 bitami klucza
  • zsumowane dane dzielone są na osiem 6-bitowych bloków i każdy blok podawany jest na wejście jednego z S-bloków (pierwszy 6-bitowy blok na wejście pierwszego S-bloku, drugi 6-bitowy blok na wejście drugiego S-bloku itd.). Pierwszy i ostatni bit danych określa wiersz, a pozostałe bity kolumnę S-BOXa. Po wyznaczeniu miejsca w tabeli, odczytuje się wartość i zamienia na zapis dwójkowy. Wynikiem działania każdego S-bloku są 4 bity wyjściowe – tworzą one 32-bitowe wyjście S-bloków. Każdy S-Blok ma inną strukturę
  • wyjście S-bloków poddawane jest permutacji w P-blokach
  • bity tak przekształconego bloku są sumowane modulo 2 z bitami lewej połowy danych
  • tak zmieniony blok staje się nową prawą połową, poprzednia prawa połowa staje się natomiast lewą połową – cykl dobiega końca
• po wykonaniu 16 cykli operacji prawa i lewa połowa danych jest łączona w 64-bitowy blok
• dokonywana jest permutacja końcowa

Deszyfrowanie polega na zastosowaniu tych samych operacji w odwrotnej kolejności (różni się od szyfrowania tylko wyborem podkluczy, który teraz odbywa się od końca).

Tryby pracy algorytmu

W dokumencie DES Modes of Operation określono cztery tryby pracy algorytmu:

• elektroniczna książka kodowa – w tym trybie pracy każdy blok tekstu jawnego szyfrowany jest w blok szyfrogramu, dzięki czemu możliwe jest stworzenie książki kodowej tekstu jawnego oraz odpowiadającego mu szyfrogramu
• wiązanie bloków zaszyfrowanych – tryb ten wykorzystuje mechanizm sprzężenia zwrotnego: w operacji szyfrowania bieżącego bloku tekstu jawnego wykorzystywany jest poprzedni blok szyfrogramu, w związku z czym każdy blok szyfrogramu zależny jest zarówno od bloku tekstu jawnego, jak i od poprzedniego bloku szyfrogramu
• sprzężenie zwrotne szyfrogramu – tryb ten umożliwia szyfrowanie danych strumieniowych; do procesu szyfrowania informacji wykorzystywany jest rejestr, najczęściej o pojemności odpowiadającej wielkości bloku, a rozpoczęcie szyfrowania możliwe jest dopiero po odebraniu pełnego bloku danych. W jednym przebiegu n zaszyfrowanych bitów z rejestru sumowanych jest modulo 2 z n bitami tekstu jawnego – tak powstaje pierwszych n bitów szyfrogramu, bity te są następnie dodawane na koniec kolejki
• sprzężenie zwrotne wyjściowe – tryb ten jest podobny do trybu sprzężenia zwrotnego szyfrogramu – z tą różnicą, że na koniec kolejki dodawane jest n bitów poprzedniego bloku wyjściowego, a nie szyfrogramu

Kryptoanaliza algorytmu

Pomimo tego, że DES jest jednym z najlepiej przeanalizowanych szyfrów blokowych, nadal najbardziej praktycznym atakiem na niego jest atak brutalny. Istnieją skuteczniejsze metody kryptoanalizy szyfru, jednak z powodu narzuconych wymagań rozważane były tylko teoretycznie.

Atak siłowy

Atak brutalny jest jedną z najpopularniejszych metod łamania wszelkich szyfrów. Polega on na wygenerowaniu wszystkich możliwych kluczy i sprawdzeniu, który z nich umożliwia odszyfrowanie szyfrogramu. W przypadku tego ataku długość klucza definiuje trudność złamania szyfru. Już krótko po opublikowaniu algorytmu pojawiły się teoretyczne rozważania na temat możliwości budowy urządzeń łamiących szyfr w rozsądnym czasie. W 1977 Diffie i Hellman zasugerowali, że za 20 milionów dolarów można zbudować wyspecjalizowane urządzenie, które będzie w stanie odtworzyć klucz szyfrujący w ciągu jednego dnia. W 1981 roku Diffie dokonał korekty tego stwierdzenia i oświadczył, że odtworzenie klucza będzie możliwe w ciągu dwóch dni, pod warunkiem, że atakujący będzie miał do dyspozycji specjalistyczny sprzęt o wartości 50 milionów dolarów. W 1993 Michael Weiner zaproponował maszynę, która potrafiła by złamać DES w ciągu 2,5 godzin – miała kosztować milion dolarów. Nikt jednak publicznie nie przyznał się do skonstruowania takiego urządzenia.

Praktyczna możliwość złamania szyfru została zademonstrowana publicznie pod koniec lat dziewięćdziesiątych. W styczniu 1997 RSA Security zaoferowała 10 000 dolarów pierwszej drużynie, która zaprezentuje urządzenie łamiące szyfr DES. Zwycięzcą konkursu zostali uczestnicy projektu DESCHALL założonego przez Rocke’a Versera, Matta Curtina oraz Justina Dolske’a, którzy 18 czerwca 1997 roku jako pierwsi w znanej historii złamali szyfr DES – zajęło im to 96 dni. Projekt ten do łamania szyfru wykorzystywał nieużywane cykle zegara tysięcy rozsianych po całym internecie komputerów. Kolejną edycję konkursu – w 1998 – wygrał projekt distributed.net, który zdobył klucz w 41 dni. W tym samym roku Electronic Frontier Foundation zademonstrowało warte 250 000 dolarów urządzenie DES Cracker, które z szyfrem uporało się w 56 godzin. Rok później, 19 stycznia 1999, distributed.net oraz RSA Labs złamały szyfr w niecałe 24 godziny.

Pozostałe ataki

Istnieje kilka ataków, które w teorii są skuteczniejsze od metody brutalnej. Jednym z nich jest atak w wykorzystaniem kryptoanalizy różnicowej, który polega na porównywaniu par szyfrogramów powstałych w wyniku zaszyfrowania tym samym kluczem pewnych tekstów jawnych, różniących się w pewien szczególny sposób. Przeprowadzenie tego ataku wymaga przygotowania dużej ilości danych i z tego powodu jest on niepraktyczny.

Innym niepraktycznym atakiem jest kryptoanaliza metodą powiązanych kluczy (ang. related-key attack), w której rozpatrywane są różnice pomiędzy kluczami szyfrującymi.

Klucze słabe i półsłabe

Pary kluczy półsłabych w DES (zapis w formacie 64-bitowym)
01 FE 01 FE 01 FE 01 FE	FE 01 FE 01 FE 01 FE 01
1F E0 1F E0 01 FE 01 FE	E0 1F E0 1F F1 0E F1 0E
01 E0 01 E0 01 F1 01 F1	E0 01 E0 01 F1 01 F1 01
1F FE 1F FE 0E FE 0E FE	FE 1F FE 1F FE 0E FE 0E
01 1F 01 1F 01 0E 01 0E	1F 01 1F 01 0E 01 0E 01
E0 FE E0 FE F1 FE F1 FE	FE E0 FE E0 FE F1 FE F1

Niektóre klucze stosowane w algorytmie DES nazywane są kluczami słabymi. Przy wykorzystaniu takiego klucza podklucz wykorzystywany do szyfrowania będzie taki sam w każdym cyklu. Do kluczy słabych w DES należą następujące klucze (zapis w systemie szesnastkowym):

• klucz składający się z samych zer: 00 00 00 00 00 00 00
• klucz składający się z samych jedynek: FF FF FF FF FF FF
• klucze, w których połowy składają się z samych zer lub jedynek: FF FF FF F0 00 00 00 oraz 00 00 00 0F FF FF FF

Dodatkowo stwierdzono, że istnieje sześć par takich kluczy, które dany tekst jawny szyfrują do takiego samego szyfrogramu – klucze takie nazywane są kluczami półsłabymi. Oznacza to także, że tekst zaszyfrowany jednym kluczem półsłabym może zostać odszyfrowany za pomocą drugiego klucza z pary.

Modyfikacje DES

Istnieje wiele różnych modyfikacji algorytmu DES. Do najważniejszych z nich zaliczane są:

• 3DES – wykorzystujący do szyfrowania i deszyfrowania trzy klucze. Najpierw wiadomość jest szyfrowana pierwszym kluczem, następnie deszyfrowana drugim i ponownie szyfrowana trzecim kluczem. Szyfrogram uzyskany w ten sposób jest dużo bezpieczniejszy, ponieważ DES nie tworzy grupy. Atak brutalny wymaga sprawdzenia $2^{112}$ kluczy.
• DESX – wykorzystuje metodą wybielania rozmywającą zależność pomiędzy danymi wejściowymi oraz wyjściowymi. Wykorzystuje 64-bitowy klucz wybielający, który przed pierwszym cyklem jest sumowany modulo 2 z tekstem jawnym. Wybielanie uodparnia algorytm na atak brutalny, kryptoanalizę liniową i różnicową.
• CRYPT(3) – wykorzystywany do tworzenia skrótów haseł w systemach z rodziny UNIX. Klucz szyfrujący tworzony jest poprzez pobranie niższych 7 bitów z każdego z ośmiu pierwszych bajtów hasła i wykorzystywany jest do szyfrowania stałego ciągu znaków (najczęściej samych zer). W tej wersji algorytmu permutacja rozszerzona jest zależna od klucza.
• Uogólniony DES (ang. Generalized DES, GDES, G-DES)– opracowany przez Ingrida Schaumuller-Bichla w 1981 w celu przyspieszenia i wzmocnienia pierwotnego algorytmu. Operuje na blokach danych zmiennej długości. W 1990 Eli Biham oraz Adi Shamir udowodnili, że ta odmiana algorytmu jest podatna na kryptoanalizę różnicową i ogólnie mniej bezpieczna od pierwowzoru.
• RDES – algorytm, w którym zamiana lewej i prawej połowy na końcu każdego cyklu zależna jest od klucza. Odmiana ta jest odporna zarówno na kryptoanalizę różnicową, jak i liniową.
• S$^{n}$DES – rodzina algorytmów, w której S-bloki miały zostać zaprojektowane w taki sposób, aby były odporne na kryptoanalizę różnicową oraz liniową. Ostatecznie tylko S$^{3}$ jest odporny na obie metody ataku.
• DES z S-blokami zależnymi od kluczy – S-bloki wykorzystywane podczas szyfrowania są generowane na podstawie bitów klucza.
• DES ze zmienionymi S-blokami – grupa odmian algorytmu DES, w których skupiono się na ulepszaniu S-bloków.
• DES z niezależnymi podkluczami – odmiana algorytmu, która w każdym cyklu wykorzystuje inny podklucz do szyfrowania danych. Długość klucza w tej odmianie DES wynosi 768 bitów. Algorytm jest odporny na kryptoanalizę liniową, nie jest jednak odporny na kryptoanalizę różnicową (może zostać złamany, jeżeli atakujący ma do dyspozycji $2^{61}$ wybranych tekstów jawnych). Atak brutalny wymaga sprawdzenia $2^{768}$ kluczy.

Linki zewnętrzne

• Prezentacja „krok po kroku” szyfrowania i deszyfrowania DES. dhost.info. [zarchiwizowane z tego adresu (2008-04-11)]. (ang.)