Feistel-netværk: Byggesten i moderne chiffere

I begyndelsen af 1970'erne arbejdede Horst Feistel hos IBM Research med Lucifer-chifferet, da han fik en grundlæggende indsigt: Du kan konstruere et inverterbart chiffer ved hjælp af en ikke-inverterbar rundefunktion.

Det var revolutionerende, fordi det er vanskeligt at designe inverterbare funktioner, der samtidig er sikre. Feistels konstruktion omgår helt dette krav og gør det muligt at bruge vilkårligt komplekse, envejs rundefunktioner.

I et Feistel-chiffer opdeles inddatablokken i to lige store halvdele: L (venstre) og R (højre). Hver runde anvender rundefunktionen F på R, XOR'er resultatet med L og bytter derefter halvdelene.

Efter n runder samles de to halvdele igen til chifferteksten. Bytningen sikrer, at begge halvdele behandles i skiftende runder, så de blandes grundigt.

Rundefunktionen F i et Feistel-netværk tager den højre halvdel og rundens undernøgle som inddata og producerer et resultat, der XOR'es med den venstre halvdel. Det afgørende er, at F ikke behøver at være inverterbar.

F kan være vilkårligt kompleks: enhver kombination af substitutioner, permutationer, XOR-operationer og modulær aritmetik. Jo mere kompleks og ikke-lineær F er, desto stærkere er chifferet, fordi dekrypteringen aldrig behøver at invertere F.

Dekryptering i et Feistel-chiffer bruger præcis den samme struktur som kryptering, men anvender rundens undernøgler i omvendt rækkefølge. Det er muligt, fordi XOR er sin egen inverse: hvis A XOR B = C, så er C XOR B = A.

Da dekrypteringen aldrig kalder F^-1 (den inverse af F), kan rundefunktionen være en irreversibel hashfunktion, en opslagstabel eller en vilkårligt kompleks operation uden at påvirke chifferets inverterbarhed.

Feistel-netværkenes matematiske elegance er, at XOR-strukturen garanterer inverterbarhed uanset hvad F gør. Selv hvis F er en envejsfunktion som SHA-256, forbliver det samlede Feistel-chiffer inverterbart.

Det gør Feistel-chiffere ekstremt fleksible. Kryptografer kan udelukkende fokusere på at gøre F så forvirrende og diffunderende som muligt, fordi de ved, at inverterbarheden håndteres af selve netværksstrukturen.

Data Encryption Standard (DES), der blev offentliggjort i 1977, er et 16-runders Feistel-chiffer, som arbejder på 64-bit-blokke med en 56-bit-nøgle. Hver runde bruger en forskellig 48-bit-undernøgle, der er afledt af hovednøglen.

Rundefunktionen i DES omfatter en udvidelsespermutation, XOR med undernøglen, otte S-bokse, der tilfører ikke-linearitet, og en P-boks-permutation. Kombinationen giver både forvirring og diffusion som krævet af Shannons principper for chifferdesign.

Blowfish, der blev designet af Bruce Schneier i 1993, er et Feistel-chiffer med variabel nøglelængde på 32-448 bit og 16 runder. Det bruger nøgleafhængige S-bokse, hvilket gør forudberegnede angreb upraktiske.

Twofish, der var finalist i AES-konkurrencen, videreudvikler idéer fra Blowfish med 128-bit-blokke og 16 runder. Ingen af dem er blevet knækket, og de bruges i anvendelser som bcrypt-adgangskodehashing, der benytter en ændret version af Blowfish.

Et balanceret Feistel-chiffer opdeler blokken i to lige store halvdele. Et ubalanceret Feistel-chiffer bruger ulige store halvdele, f.eks. en opdeling på 3/4 og 1/4.

Ubalancerede Feistel-netværk kan give sikkerhedsfordele i bestemte sammenhænge og bruges i nogle specialiserede chiffere. CAST-familien af chiffere bruger en balanceret 64-bit-Feistel-struktur.

I 1988 beviste Michael Luby og Charles Rackoff, at et 3-runders Feistel-netværk med pseudotilfældige rundefunktioner er en sikker pseudotilfældig permutation (PRP), og at en version med 4 runder er en stærk PRP.

Dette teoretiske resultat gav Feistel-netværk et solidt grundlag for beviselig sikkerhed, ikke blot erfaringsbaseret tillid. Det bekræftede, at selve Feistel-strukturen bidrager til sikkerheden ud over rundefunktionen alene.

Substitutions-permutationsnetværket (SPN), der bruges af AES, anvender substitution og permutation på hele blokken på én gang i stedet for på halvdelen af blokken pr. runde. Det giver hurtigere diffusion.

AES opnår fuld diffusion på blot 4 runder, mens DES' Feistel-struktur kræver flere runder for at opnå en tilsvarende diffusion. AES' SPN passer også bedre til moderne processorarkitekturer med SIMD-instruktioner.

Luby-Rackoff-sætningen betragter rundefunktionen F som en virkelig tilfældig funktion. I praksis er F en pseudotilfældig funktion, det vil sige et nøglebaseret chiffer eller en hashfunktion, og ikke et ægte tilfældigt orakel.

Denne kløft mellem teoretiske beviser og praktiske implementationer er et tilbagevendende tema i kryptografi. Beviser giver tillid, men bygger på idealiserede modeller. Sikkerheden i den virkelige verden afhænger også af sikre implementationer uden sårbarheder over for sidekanalangreb.

Feistel-netværk er strukturer for blokchiffere, som bruger en rundefunktion, der ikke behøver at være inverterbar. Dekryptering fungerer ved at køre den samme struktur baglæns med undernøglerne i omvendt rækkefølge.

DES, Blowfish og Twofish er alle Feistel-chiffere. Luby-Rackoff-sætningen giver teoretiske sikkerhedsgarantier. AES bruger i stedet en SPN-struktur, som giver bedre diffusion pr. runde.