Konstrukcja DES i szyfr Lucifer

W 1971 roku Horst Feistel z IBM Research opracował szyfr o nazwie Lucifer w ramach projektu bezpieczeństwa bankowego dla Lloyd's of London. Lucifer był jednym z pierwszych nowoczesnych szyfrów blokowych, wykorzystującym klucz 128-bitowy i bloki 128-bitowe.

Lucifer pokazał, że można zbudować silny szyfr blokowy z użyciem struktury Feistela: naprzemiennych rund podstawienia i permutacji stosowanych do połówek bloku. Był bezpośrednim poprzednikiem DES.

DES stosuje strukturę Feistela przez 16 rund do bloków 64-bitowych. W każdej rundzie blok 64-bitowy dzieli się na dwie połowy po 32 bity. Prawa połowa jest rozszerzana do 48 bitów, łączona operacją XOR z podkluczem 48-bitowym, przepuszczana przez skrzynki S, poddawana permutacji i łączona operacją XOR z lewą połową.

Połówki są następnie zamieniane i proces się powtarza. Po 16 rundach permutacja końcowa generuje szyfrogram 64-bitowy. Odszyfrowywanie przebiega według tej samej struktury, ale z podkluczami używanymi w odwrotnej kolejności.

DES szyfruje dane w blokach 64-bitowych (8-bajtowych). Taki stały rozmiar bloku był odpowiedni dla sprzętu z 1977 roku, ale z czasem stał się zagrożeniem dla bezpieczeństwa. Przy wystarczającej ilości danych kolizje wynikające z paradoksu urodzinowego stają się prawdopodobne.

Przy blokach 64-bitowych wzorce statystyczne pojawiają się po około 2^32 blokach (~32GB danych zaszyfrowanych z użyciem tego samego klucza). Atak Sweet32 sprawił, że 3DES stał się niebezpieczny w przypadku ruchu o dużym wolumenie, takiego jak HTTPS.

DES używa klucza 64-bitowego, ale 8 bitów to bity parzystości służące do wykrywania błędów, a nie do szyfrowania. Efektywna długość klucza wynosi zatem tylko 56 bitów.

Oznacza to, że istnieje tylko 2^56 (około 72 biliardów) możliwych kluczy DES. Według standardów z 1977 roku uznawano to za wystarczające. W 1997 roku zdecydowany przeciwnik potrafił już w praktyce złamać taki klucz.

DES rozpoczyna od permutacji początkowej (IP), która zmienia kolejność 64 bitów bloku tekstu jawnego, a kończy permutacją końcową (IP^-1), będącą jej dokładnym odwróceniem. Permutacje te nie zwiększają siły kryptograficznej.

Zaprojektowano je z myślą o wydajności sprzętowej na określonych architekturach układów z lat 70., aby umożliwić szybsze ładowanie bitów do rejestrów. Współczesne analizy potwierdzają, że nie wnoszą one nic do bezpieczeństwa.

Osiem skrzynek S (S-boxów, Substitution boxes) stanowi podstawę nieliniowości DES. Każda skrzynka S przyjmuje 6 bitów na wejściu i generuje 4 bity na wyjściu, korzystając ze stałej tablicy wyszukiwania. Zewnętrzne 2 bity wybierają wiersz, a wewnętrzne 4 bity wybierają kolumnę.

Bez nieliniowości zapewnianej przez skrzynki S DES byłby czysto liniowym szyfrem, który można by łatwo złamać za pomocą algebry liniowej. Konkretny projekt skrzynek S DES jest odporny na kryptoanalizę różnicową.

Po skrzynkach S DES stosuje permutację skrzynki P, która zmienia kolejność 32 bitów wyjściowych ze skrzynek S. Zapewnia to dyfuzję, rozpraszając wynik każdej skrzynki S tak, aby wpływał na wiele skrzynek S w następnej rundzie.

Skrzynkę P starannie zaprojektowano w celu maksymalizacji dyfuzji: każdy bit wyjściowy jednej skrzynki S wpływa na co najmniej dwie różne skrzynki S w następnej rundzie, zapewniając szybki efekt lawinowy.

DES wyprowadza z 56-bitowego klucza głównego 16 różnych 48-bitowych podkluczy — po jednym dla każdej rundy. Harmonogram klucza rozpoczyna się od zastosowania permutacji wyboru (PC-1), która usuwa bity parzystości i zmienia kolejność bitów klucza.

56 bitów dzieli się na dwie 28-bitowe połowy, które w każdej rundzie są obracane w lewo o 1 lub 2 pozycje. Następnie permutacja wyboru (PC-2) wybiera 48 z 56 bitów, tworząc podklucz danej rundy.

NSA współpracowała z IBM podczas opracowywania DES, zmniejszając długość klucza ze 128 bitów używanych w szyfrze Lucifer do 56 bitów oraz modyfikując projekty S-boxów. Wywołało to trwające dziesięciolecia kontrowersje dotyczące tego, czy wprowadzono tylne wejścia.

W latach 90. przedstawiciele NSA potwierdzili, że wzmocnili S-boxy pod kątem odporności na kryptoanalizę różnicową — technikę odkrytą przez IBM w 1974 roku. NSA znała kryptoanalizę różnicową na wiele lat przed środowiskiem akademickim, co sugeruje, że zwiększyła odporność DES, a nie ją zmniejszyła.

DES przyjęto jako Federal Information Processing Standard 46 w styczniu 1977 roku po przeprowadzeniu konkurencyjnego procesu oceny. Stał się standardowym szyfrem do ochrony niesklasyfikowanych danych rządowych i został powszechnie przyjęty w bankowości oraz przemyśle.

Standaryzacja DES miała historyczne znaczenie: był to pierwszy publicznie dostępny algorytm kryptograficzny zatwierdzony przez rząd. Przyczyniła się do rozwoju implementacji sprzętowych i ustanowiła wzorzec dla przyszłych procesów standaryzacji szyfrów.

Sam DES jest szyfrem blokowym, który szyfruje dokładnie 64 bity za każdym razem. Rzeczywiste wiadomości są dłuższe, dlatego tryby działania określają sposób stosowania szyfru do wielu bloków. Do typowych trybów należą ECB (szyfrowanie każdego bloku niezależnie), CBC (operacja XOR każdego bloku z poprzednim szyfrogramem przed szyfrowaniem), CFB, OFB i CTR.

ECB jest najsłabszym trybem: identyczne bloki tekstu jawnego dają identyczne bloki szyfrogramu, tworząc widoczne wzorce. Tryby CBC i CTR eliminują tę słabość i są preferowane w praktycznych zastosowaniach DES oraz 3DES.

DES ewoluował z szyfru Lucifer opracowanego przez IBM w 16-rundowy szyfr Feistela z blokami 64-bitowymi i efektywnymi kluczami 56-bitowymi. Jego bezpieczeństwo wynika z 8 nieliniowych S-boxów zapewniających konfuzję, P-boxa zapewniającego dyfuzję oraz 16 rund wzmacniających efekt lawinowy.

Udział NSA w projektowaniu S-boxów był kontrowersyjny, ale ostatecznie poprawił odporność na kryptoanalizę różnicową. 56-bitowy klucz DES, zaprojektowany z myślą o sprzęcie z 1977 roku, okazał się niewystarczający pod koniec lat 90.