Data Encryption Standard (DES) to symetryczny szyfr blokowy pracujący na 64‑bitowych blokach z efektywnym kluczem 56‑bitowym, który ukształtował rozwój współczesnej kryptografii. Opracowany przez IBM na zlecenie NBS (obecnie NIST), był federalnym standardem USA od 1977 do 2001 roku oraz standardem ANSI dla sektora prywatnego. Dziś uznawany jest za niewystarczająco bezpieczny ze względu na podatność na ataki brute force i postęp mocy obliczeniowej.
Historia powstania i standaryzacji algorytmu DES
Pochodzenie projektu i rola IBM
Początki DES sięgają prac IBM nad algorytmem LUCIFER, rozwijanym przez zespół kierowany przez Horsta Feistela. Kluczowa była koncepcja sieci Feistela, która stała się szkieletem konstrukcyjnym DES. W toku prac nad standaryzacją modyfikacje konsultowano m.in. z NSA, co wywoływało wieloletnie spory o przejrzystość procesu.
Najważniejsze fakty dotyczące genezy i wczesnych kontrowersji:
- skrócenie klucza do 56 bitów – decyzja, którą NSA miała rekomendować IBM; od początku budziła obawy o odporność na brute force;
- tajny projekt S‑bloków – brak publicznych zasad konstrukcji rodził podejrzenia o możliwe „trapdoory”;
- jawność specyfikacji w 1975–1977 – upublicznienie szczegółów umożliwiło liczne implementacje programowe i niezależne audyty;
- rola środowiska akademickiego – krytyka rozmiaru klucza (m.in. Diffie i Hellman) i presja na otwartość projektu;
- potwierdzenia FIPS – kolejne rewizje (FIPS 46, 46‑1, 46‑2, 46‑3) utrzymywały DES/3DES w obiegu regulacyjnym.
Proces standaryzacji i kamienie milowe
Przegląd kluczowych wydarzeń w procesie standaryzacji:
- 1973–1974 – NBS publikuje zaproszenia do zgłaszania propozycji standardu szyfrowania;
- 1975 – publikacja zmodyfikowanego LUCIFER jako kandydata na standard i udostępnienie go do recenzji publicznej;
- 1976 – warsztaty poświęcone matematycznym podstawom DES, formalne zatwierdzenie w listopadzie;
- 1977 – publikacja jako FIPS PUB 46, dopuszczenie do szyfrowania informacji wrażliwych, lecz nie tajnych;
- 1983, 1988, 1993, 1999 – kolejne rewizje FIPS (46‑1, 46‑2, 46‑3), z naciskiem na preferencję Triple DES.
Podstawowe charakterystyki i cechy techniczne algorytmu DES
Parametry i właściwości strukturalne
Poniżej kluczowe parametry działania DES:
- blok danych – 64 bity – przetwarzanie niezależnych 64‑bitowych bloków (ostatni blok wymaga ewentualnego paddingu);
- klucz – efektywnie 56 bitów – z 64 bitów wejściowych 8 stanowi bity parzystości; przestrzeń kluczy ≈ 2^56 ≈ 7,2×10^16 kombinacji;
- liczba rund – 16 – iteracyjne stosowanie funkcji rundy F w strukturze Feistela;
- deterministyczne podklucze – harmonogram rotacji i permutacji generuje 16 unikatowych podkluczy 48‑bitowych;
- operacje podstawiania i permutacji – osiem S‑bloków (wejście 6 bitów, wyjście 4 bity) oraz permutacja P dla dyfuzji.
Klasyfikacja i porównanie z innymi algorytmami
DES to szyfr symetryczny blokowy – ten sam klucz służy do szyfrowania i deszyfrowania, a dane dzieli się na bloki 64‑bitowe. W porównaniu z nowszymi konstrukcjami (np. AES) DES ustępuje poziomem bezpieczeństwa ze względu na krótszy klucz.
Dla szybkiego porównania z następcami:
| Algorytm | Rok standaryzacji | Rozmiar bloku | Rozmiar klucza | Rundy | Status bezpieczeństwa |
|---|---|---|---|---|---|
| DES | 1977 | 64 bity | 56 bitów (efektywnie) | 16 | niebezpieczny (brute force) |
| 3DES (TDEA) | 1999 (FIPS 46‑3) | 64 bity | 112/168 bitów | 48 (3×16) | starzejący się, ograniczany regulacyjnie |
| AES (Rijndael) | 2001 (FIPS 197) | 128 bitów | 128/192/256 bitów | 10/12/14 | zalecany standard |
Tryby pracy algorytmu
DES może pracować w kilku trybach definiowanych przez „DES Modes of Operation”:
- ECB – Electronic Codebook – każdy blok szyfrowany niezależnie; najsłabszy, ujawnia wzorce w danych;
- CBC – Cipher Block Chaining – każdy blok łączony XOR z poprzednim szyfrogramem (wymaga IV); maskuje powtórzenia;
- CFB – Cipher Feedback – używa DES do generowania strumienia i łączy go XOR z danymi; nie wymaga paddingu;
- OFB – Output Feedback – podobny do CFB, ale strumień klucza niezależny od danych; odporniejszy na błędy transmisji.
Zasada działania DES – struktura Feistela i algorytmiczne procesy
Struktura Feistela i architektura algorytmu
DES realizuje klasyczną strukturę Feistela: wejściowy blok po wstępnej permutacji dzieli się na połowy L(0) i R(0) po 32 bity. W każdej z 16 rund zachodzi wymiana i mieszanie:
L(i+1) = R(i)
R(i+1) = L(i) XOR F(R(i), K(i))
Po rundach połówki łączy się i stosuje permutację końcową stanowiącą inwersję permutacji wstępnej. Odszyfrowanie przebiega tym samym algorytmem, ale z podkluczami w odwrotnej kolejności.
Etapy przetwarzania i permutacje
Przepływ danych w DES wygląda następująco:
- wstępna permutacja – stałe przestawienie bitów ułatwiające historycznie implementacje sprzętowe;
- 16 rund Feistela – każda z dedykowanym podkluczem K(i) generowanym z klucza głównego;
- permutacja końcowa – inwersja permutacji wstępnej, tworząca 64‑bitowy szyfrogram.
Generowanie podkluczy i zarządzanie kluczami
Klucz 56‑bitowy dzieli się na dwie 28‑bitowe połówki, które w każdej rundzie rotują w lewo. W rundach 1, 2, 9 i 16 rotacja wynosi 1 bit, a w pozostałych – 2 bity. Po rotacjach stosuje się permutację kompresującą wybierającą 48 bitów na podklucz K(i).
Funkcja rundy i podstawianie‑permutacja
Funkcja F realizuje cztery kroki: rozszerzenie 32→48 bitów, XOR z K(i), podstawienie w ośmiu S‑blokach (wejście 6 bitów, wyjście 4 bity) i permutację P. S‑bloki dobrano tak, by zwiększać odporność na kryptoanalizę różnicową, którą IBM i NSA znały już w latach 70.
Bezpieczeństwo, ataki i ewolucja słabości algorytmu DES
Wczesne podejrzenia i teoretyczne ataki
Od publikacji DES (1977) wskazywano na ryzyko ataku wyczerpującego – Diffie i Hellman opisali wykonalny budżetowo atak sprzętowy. W 1992 Biham i Shamir formalnie opisali kryptoanalizę różnicową przeciw DES (pełna wersja wymagała >2^47 wybranych tekstów, co było niepraktyczne, ale istotne teoretycznie).
Pierwsza praktyczna demonstracja złamania DES
Przełom nastąpił w latach 1997–1999 dzięki rozproszonym i sprzętowym atakom brute force:
- DESCHALL (1997) – rozproszony brute force, złamanie po 96 dniach;
- EFF Deep Crack (1998) – dedykowane urządzenie, klucz odzyskany w 56 godzin;
- distributed.net + RSA Labs (1999) – czas skrócony do 22 godzin i 15 minut.
Ewolucja zdolności atakowania DES
Postęp sprzętowy dalej skracał czas łamania: COPACOBANA (2004–2005) schodziła z 9 do 6,4 dnia przy niskim koszcie, RIVYERA (2008) osiągała średnio poniżej doby, a narzędzia GPU (np. hashcat) w 2016 pozwalały przeciętnie odzyskać klucz na pojedynczym GPU w kilkanaście dni, a na zestawie GPU – w mniej niż dwa dni. W 2017 pokazano atak z tęczowymi tablicami dla konkretnego tekstu jawnego 1122334455667788 trwający około 25 sekund (kosztem osobnej tablicy na każdy tekst).
Ataki kryptoanalityczne – różnicowa i liniowa
Kryptoanaliza różnicowa wymaga dla pełnego DES powyżej 2^47 wybranych tekstów, co ogranicza jej praktyczność. Kryptoanaliza liniowa (Matsui) potrzebuje około 2^43 par tekst‑jawny/szyfrogram – mniej niż brute force, ale nadal trudne do zebrania w praktyce.
Słabe klucze i pół‑słabe klucze
DES ma cztery słabe klucze, dla których wszystkie 16 podkluczy jest identycznych (np. 00 00 00 00 00 00 00 00, FF FF FF FF FF FF FF FF), oraz sześć par pół‑słabych, gdzie szyfrowanie jednym kluczem można odwrócić drugim. W praktyce ryzyko jest znikome z powodu rzadkiego trafienia takich wartości.
Modyfikacje, warianty i następcy algorytmu DES
Triple DES (3DES) – wzmacnianie oryginalnego DES
3DES trzykrotnie przetwarza blok (schemat E‑D‑E) w celu podniesienia bezpieczeństwa bez zmiany podstawowej architektury. Z trzema kluczami (3×56 bitów) nominalna długość to 168 bitów, lecz z powodu ataku meet‑in‑the‑middle efektywna siła to około 2^112. FIPS 46‑3 preferował 3DES dla nowych wdrożeń w końcowym okresie DES.
DESX – wzmacnianie poprzez wybielanie
DESX dodaje wybielanie (XOR z dodatkowymi tajnymi słowami przed/po DES), utrudniając brute force i analizy liniowo‑różnicowe. Mimo poprawy bezpieczeństwa nie zdobył szerokiej adopcji, m.in. przez rosnącą popularność 3DES i późniejszego AES.
Uogólniony DES (GDES) i inne warianty
Warianty takie jak GDES (zmienny rozmiar bloku), SnDES (S‑boksy projektowane pod odporność na konkretne ataki) czy RDES (kluczowo‑zależne zamiany połówek) badały modyfikacje DES, lecz część z nich okazała się słabsza wobec kryptoanalizy różnicowej.
Przejście na Advanced Encryption Standard (AES)
W 2001 opublikowano FIPS 197, definiujący Advanced Encryption Standard (AES), który oferuje klucze 128/192/256 bitów i 128‑bitowy blok. W 2005 NIST wycofał FIPS 46‑3, kończąc oficjalny status DES; 3DES przez pewien czas utrzymywał się w systemach dziedziczonych, lecz dla nowych wdrożeń standardem stał się AES.