Sieci Feistela: podstawy współczesnych szyfrów

Na początku lat 70. XX wieku Horst Feistel, pracując w IBM Research nad szyfrem Lucifer, sformułował fundamentalną obserwację: można zbudować odwracalny szyfr z użyciem nieodwracalnej funkcji rundy.

Było to przełomowe, ponieważ projektowanie funkcji, które są jednocześnie odwracalne i bezpieczne, jest trudne. Konstrukcja Feistela całkowicie omija ten wymóg, umożliwiając stosowanie dowolnie złożonych, jednokierunkowych funkcji rundy.

W szyfrze Feistela blok wejściowy dzieli się na dwie równe połowy: L (lewą) i R (prawą). W każdej rundzie funkcja rundy F jest stosowana do R, a jej wynik jest łączony operacją XOR z L, po czym połowy są zamieniane miejscami.

Po n rundach obie połowy są ponownie łączone, tworząc szyfrogram. Zamiana zapewnia, że obie połowy są przetwarzane naprzemiennie, co dokładnie je miesza.

Funkcja rundy F w sieci Feistela przyjmuje jako dane wejściowe prawą połowę oraz podklucz rundy i zwraca wynik, który jest łączony operacją XOR z lewą połową. Co ważne, funkcja F nie musi być odwracalna.

F może być dowolnie złożona: może obejmować dowolne połączenie podstawień, permutacji, operacji XOR i działań arytmetycznych modulo. Im bardziej złożona i nieliniowa jest funkcja F, tym silniejszy jest szyfr, ponieważ podczas deszyfrowania nie trzeba odwracać funkcji F.

Deszyfrowanie w szyfrze Feistela wykorzystuje dokładnie tę samą strukturę co szyfrowanie, ale stosuje podklucze rund w odwrotnej kolejności. Jest to możliwe, ponieważ XOR jest własną operacją odwrotną: jeśli A XOR B = C, to C XOR B = A.

Ponieważ podczas deszyfrowania nigdy nie wywołuje się F^-1, czyli odwrotności funkcji F, funkcją rundy może być nieodwracalna funkcja skrótu, tablica przeglądowa lub dowolna złożona operacja — bez wpływu na odwracalność szyfru.

Matematyczna elegancja sieci Feistela polega na tym, że struktura XOR gwarantuje odwracalność niezależnie od działania funkcji F. Nawet jeśli F jest funkcją jednokierunkową, taką jak SHA-256, cały szyfr Feistela pozostaje odwracalny.

Sprawia to, że szyfry Feistela są niezwykle elastyczne. Kryptografowie mogą w pełni skupić się na tym, aby funkcja F zapewniała jak największe pomieszanie i rozpraszanie, mając pewność, że za odwracalność odpowiada sama struktura sieci.

Data Encryption Standard (DES), opublikowany w 1977 roku, jest 16-rundowym szyfrem Feistela działającym na blokach 64-bitowych z kluczem 56-bitowym. W każdej rundzie używany jest inny podklucz 48-bitowy wyprowadzony z klucza głównego.

Funkcja rundy w DES obejmuje permutację rozszerzającą, operację XOR z podkluczem, osiem S-boxów zapewniających nieliniowość oraz permutację P-box. Połączenie tych elementów zapewnia konfuzję i dyfuzję wymagane przez zasady projektowania szyfrów sformułowane przez Shannona.

Blowfish, zaprojektowany przez Bruce’a Schneiera w 1993 roku, jest szyfrem Feistela o zmiennej długości klucza (32–448 bitów) i 16 rundach. Wykorzystuje S-boxy zależne od klucza, co sprawia, że ataki z użyciem wcześniej obliczonych danych są niepraktyczne.

Twofish, finalista konkursu AES, rozwija idee Blowfish, używając bloków 128-bitowych i 16 rund. Oba szyfry pozostają niepokonane i są używane w takich zastosowaniach jak funkcja skrótu haseł bcrypt, która wykorzystuje zmodyfikowany Blowfish.

Zrównoważony szyfr Feistela dzieli blok na dwie równe połowy. Niezrównoważony szyfr Feistela wykorzystuje nierówne połowy, na przykład w proporcji 3/4 do 1/4.

Niezrównoważone sieci Feistela mogą zapewniać korzyści w zakresie bezpieczeństwa w określonych kontekstach i są używane w niektórych wyspecjalizowanych szyfrach. Rodzina szyfrów CAST wykorzystuje zrównoważoną strukturę Feistela z blokiem 64-bitowym.

W 1988 roku Michael Luby i Charles Rackoff udowodnili, że 3-rundowa sieć Feistela wykorzystująca pseudolosowe funkcje rund jest bezpieczną pseudolosową permutacją (PRP), a wersja 4-rundowa jest silną PRP.

Ten wynik teoretyczny dał sieciom Feistela solidne podstawy bezpieczeństwa możliwego do udowodnienia, a nie tylko potwierdzenie empiryczne. Potwierdził, że sama struktura Feistela przyczynia się do bezpieczeństwa, wykraczając poza właściwości pojedynczej funkcji rundy.

Sieć podstawień i permutacji (SPN) używana przez AES stosuje podstawienie i permutację jednocześnie do całego bloku, a nie do jego połowy w każdej rundzie. Zapewnia to szybszą dyfuzję.

AES osiąga pełną dyfuzję już w 4 rundach, podczas gdy struktura Feistela w DES wymaga większej liczby rund, aby uzyskać porównywalną dyfuzję. Sieć SPN szyfru AES lepiej pasuje również do architektur współczesnych procesorów wykorzystujących instrukcje SIMD.

Twierdzenie Luby’ego–Rackoffa traktuje funkcję rundy F jak prawdziwie losową funkcję. W praktyce F jest funkcją pseudolosową — szyfrem kluczowanym lub funkcją skrótu — a nie prawdziwą losową wyrocznią.

Ta różnica między dowodami teoretycznymi a praktycznymi implementacjami jest stałym motywem w kryptografii. Dowody zwiększają zaufanie, ale opierają się na wyidealizowanych modelach. Bezpieczeństwo w rzeczywistym świecie zależy również od bezpiecznych implementacji wolnych od podatności na ataki z kanałów bocznych.

Sprawdź swoją wiedzę na temat projektowania sieci Feistela.

Sieci Feistela są strukturami szyfrów blokowych wykorzystującymi funkcję rundy, która nie musi być odwracalna. Deszyfrowanie polega na uruchomieniu tej samej struktury w odwrotnej kolejności, z podkluczami zastosowanymi w odwróconej kolejności.

DES, Blowfish i Twofish są szyframi Feistela. Twierdzenie Luby’ego–Rackoffa zapewnia teoretyczne gwarancje bezpieczeństwa. AES wykorzystuje zamiast tego strukturę SPN, oferując lepszą dyfuzję w każdej rundzie.