2DES

Żeby złamać dwukrotnego DESa:

${\displaystyle C=E_{DES,K_{2}}(E_{DES,K_{1}}(P)).}$

Trzeba wykonać ${\displaystyle 2^{56}}$ szyfrowań żeby otrzymać tablicę wyników pośrednich dla wszystkich ${\displaystyle K_{1},}$ i od 1 do ${\displaystyle 2^{56}}$ (średnio ${\displaystyle 2^{55}}$) żeby znaleźć pasujący ${\displaystyle K_{2}.}$ Razem więc ${\displaystyle 2^{56}+2^{55}\approx 2^{56.58}}$ operacji.

3DES

Żeby złamać trzykrotnego DESa:

${\displaystyle C=E_{DES,K_{3}}(E_{DES,K_{2}}(E_{DES,K_{1}}(P))).}$

Dzielimy go najpierw na mniejszą część, którą będziemy tablicować i większą którą będziemy zgadywać:

${\displaystyle D_{DES,K_{2}}(D_{DES,K_{3}}(C))=E_{DES,K_{1}}(P).}$

Następnie tablicujemy wyniki pośrednie dla wszystkich ${\displaystyle K_{1},}$ co wymaga ${\displaystyle 2^{56}}$ i pamięci rzędu ${\displaystyle 2^{56}.}$ W końcu zgadujemy ${\displaystyle K_{1}}$ i ${\displaystyle K_{2},}$ co wymaga średnio ${\displaystyle 2^{111}}$ operacji. Ponieważ ta pierwsza liczba jest o wiele mniejsza od drugiej, oczekiwany czas to ${\displaystyle 2^{111}}$ operacji a zużycie pamięci to ${\displaystyle 2^{56}}$ bloków.

Podział w którym dwa DESy się tablicuje, a trzeci zgaduje wymagałby ${\displaystyle 2^{112}}$ operacji na przygotowanie tablicy i średnio ${\displaystyle 2^{55}}$ na zgadnięcie, razem ${\displaystyle 2^{112},}$ czyli dwukrotnie więcej operacji. Taki wzrost ilości operacji nie jest wielkim problemem, ale wymagania pamięciowe wzrastają z rozsądnego choć dość dużego ${\displaystyle 2^{56}}$ do zupełnie gigantycznego ${\displaystyle 2^{112}.}$

Różne szyfry

Żeby złamać szyfr w którym blok najpierw szyfruje się 80-bitowym Skipjackiem, a następnie 56-bitowym DESem:

${\displaystyle C=E_{DES,K_{2}}(E_{Skipjack,K_{1}}(P)).}$

Dzielimy szyfr na dwie części:

${\displaystyle D_{DES,K_{2}}(C)=E_{Skipjack,K_{1}}(P).}$

W tym wypadku opłaca się bardziej stablicować wszystkie możliwe deszyfracje lewej strony (tablica rozmiaru ${\displaystyle 2^{56}}$), i iterować po prawej stronie ${\displaystyle 2^{80}.}$

Ograniczona ilość pamięci

Jeśli chcemy złamać dwukrotnego DESa, ale mamy jedynie pamięć rzędu ${\displaystyle 2^{40},}$ zamiast wymaganych ${\displaystyle 2^{56},}$ możemy zastosować następujący sposób:

Iterujemy po wszystkich możliwych 16-bitowych prefiksach, i dla każdego z nich:

• Generujemy tablicę, ale zachowujemy tylko tę część której elementy zaczynają się od aktualnie wybranego prefiksu
• Szukamy klucza.

Wymagana ilość operacji to ${\displaystyle 2^{16}\left(2^{56}+2^{56}\right)=2^{16+57}=2^{73}.}$ Jest to więcej od pełnego meet in the middle ${\displaystyle (2^{56.58}),}$ ale mniej od naiwnego łamania 2DESa ${\displaystyle (2^{111}).}$ Zależnie od ilości pamięci, jaką dysponujemy możemy też wybrać inne kompromisowe rozwiązania.

Przykładowe obliczenia

Załóżmy, że mamy następujący 16-bitowy szyfr (16-bitowe szyfry mogą służyć jedynie jako przykład obliczeń, nie do poważnych zastosowań):

Szyfrujemy blok za pomocą AES, przy czym ostatnie 8 bitów klucza AESa to pierwsza połowa naszego klucza, reszta bitów wynosi 0.

Szyfrujemy otrzymany wynik za pomocą AES, przy czym ostatnie 8 bitów klucza AESa to druga połowa naszego klucza, reszta bitów wynosi 0.

Szyfrowanie bloku tym algorytmem można wykonać następująco (xxyy to klucz):

$ echo -n 'WiadomośćWiadomo' | openssl enc -aes-128-ecb -K 000000000000000000000000000000xx -iv 0 -nopad -nosalt | openssl enc -aes-128-ecb -K 000000000000000000000000000000yy -iv 0 -nopad -nosalt >WYNIK

Podsłuchaliśmy komunikacji zaszyfrowanej tym szyfrem i wiemy, że blok 57 69 6b 69 70 65 64 69 61 20 31 32 33 34 35 36 (Wikipedia 123456) to po zaszyfrowaniu 00 6f 08 ea df 08 00 7c 53 c8 3c 90 b5 81 f3 6e.

Generujemy więc wszystkie wyniki pośrednie po pierwszym AESie (kod w Perlu wywołuje szyfrowanie OpenSSLa i formatuje wyniki):

for(0..255){
  $k=sprintf "%02x", $_;
  $b=`echo -n "Wikipedia 123456" | openssl enc -aes-128-ecb -K 000000000000000000000000000000$k -iv 0 -nopad -nosalt`;
  printf "$k => %s\n", join(" ", map{sprintf "%02x", $_} unpack("C32", $b))
}

Następnie próbujemy zgadywać drugi podklucz, aż otrzymamy wartość z powyższej tabelki (kod w Perlu).

for(0..255){
  $k=sprintf "%02x", $_;
  $b=`echo -en "\\x00\\x6f\\x08\\xea\\xdf\\x08\\x00\\x7c\\x53\\xc8\\x3c\\x90\\xb5\\x81\\xf3\\x6e"
     | openssl enc -aes-128-ecb -d -K 000000000000000000000000000000$k -iv 0 -nopad -nosalt`;
  printf "$k => %s\n", join(" ", map{sprintf "%02x", $_} unpack("C32", $b))
}

Wartości pośrednie dla 4d z pierwszej tabeli i b7 z drugiej są takie same i równe 87 b3 37 3b 07 20 fe 40 24 54 7f eb 1b 0e ad 4b. Klucz wynosi więc 4db7.