Feistel-nettverk: Byggeklosser i moderne chifre

På begynnelsen av 1970-tallet arbeidet Horst Feistel hos IBM Research med Lucifer-chifferet da han utviklet en grunnleggende innsikt: Man kan bygge et inverterbart chiffer ved hjelp av en ikke-inverterbar rundefunksjon.

Dette var revolusjonerende fordi det er vanskelig å utforme inverterbare funksjoner som også er sikre. Feistels konstruksjon omgår dette kravet fullstendig og gjør det mulig å bruke vilkårlig komplekse enveisfunksjoner i rundene.

I et Feistel-chiffer deles inndatablokken i to like store halvdeler: L (venstre) og R (høyre). I hver runde brukes rundefunksjonen F på R, resultatet kombineres med L ved hjelp av XOR, og halvdelene byttes om.

Etter n runder settes de to halvdelene sammen igjen for å produsere chifferteksten. Byttingen sørger for at begge halvdelene behandles i annenhver runde og blandes grundig.

Rundefunksjonen F i et Feistel-nettverk tar høyre halvdel og rundeundernøkkelen som inndata og produserer et resultat som kombineres med venstre halvdel ved hjelp av XOR. Det er avgjørende at F ikke trenger å være inverterbar.

F kan være vilkårlig kompleks: enhver kombinasjon av substitusjoner, permutasjoner, XOR-operasjoner og modulær aritmetikk. Jo mer kompleks og ikke-lineær F er, desto sterkere er chifferet, fordi dekryptering aldri trenger å invertere F.

Dekryptering i et Feistel-chiffer bruker nøyaktig samme struktur som kryptering, men anvender rundeundernøklene i omvendt rekkefølge. Dette er mulig fordi XOR er sin egen invers: Hvis A XOR B = C, så er C XOR B = A.

Fordi dekrypteringen aldri kaller F^-1 (inversen til F), kan rundefunksjonen være en irreversibel hash, en oppslagstabell eller en hvilken som helst kompleks operasjon uten å påvirke chifferets inverterbarhet.

Den matematiske elegansen ved Feistel-nettverk er at XOR-strukturen garanterer inverterbarhet uansett hva F gjør. Selv om F er en enveisfunksjon som SHA-256, forblir det overordnede Feistel-chifferet inverterbart.

Dette gjør Feistel-chifre svært fleksible. Kryptografer kan konsentrere seg helt om å maksimere forvirring og diffusjon i F, vel vitende om at inverterbarheten håndteres av selve nettverksstrukturen.

Data Encryption Standard (DES), publisert i 1977, er et 16-runders Feistel-chiffer som opererer på 64-biters blokker med en 56-biters nøkkel. Hver runde bruker en egen 48-biters undernøkkel som er avledet fra hovednøkkelen.

Rundefunksjonen i DES omfatter ekspansjonspermutasjon, XOR med undernøkkelen, åtte S-bokser som gir ikke-linearitet, og en P-boks-permutasjon. Kombinasjonen gir både forvirring og diffusjon, slik Shannons prinsipper for chifferdesign krever.

Blowfish, utviklet av Bruce Schneier i 1993, er et Feistel-chiffer med variabel nøkkellengde (32–448 bit) og 16 runder. Det bruker nøkkelavhengige S-bokser, noe som gjør forhåndsberegnede angrep upraktiske.

Twofish, en finalist i AES-konkurransen, videreutvikler ideene fra Blowfish med 128-biters blokker og 16 runder. Ingen av dem er blitt brutt, og de brukes i programmer som bcrypt for hashing av passord, der bcrypt bruker en modifisert versjon av Blowfish.

Et balansert Feistel-chiffer deler blokken i to like store halvdeler. Et ubalansert Feistel-chiffer bruker halvdeler av ulik størrelse, for eksempel en deling på 3/4 og 1/4.

Ubalanserte Feistel-nettverk kan gi sikkerhetsfordeler i bestemte sammenhenger og brukes i enkelte spesialiserte chifre. CAST-familien av chifre bruker en balansert 64-biters Feistel-struktur.

I 1988 beviste Michael Luby og Charles Rackoff at et 3-runders Feistel-nettverk med pseudo-tilfeldige rundefunksjoner er en sikker pseudo-tilfeldig permutasjon (PRP), og at en variant med 4 runder er en sterk PRP.

Dette teoretiske resultatet ga Feistel-nettverk et solid grunnlag for bevisbar sikkerhet, ikke bare empirisk tillit. Det bekreftet at selve Feistel-strukturen bidrar til sikkerheten, utover det rundefunksjonen alene gjør.

Substitusjonspermutasjonsnettverket (SPN) som brukes av AES, anvender substitusjon og permutasjon på hele blokken samtidig, i stedet for på én halv blokk per runde. Dette gir raskere diffusjon.

AES oppnår full diffusjon på bare 4 runder, mens DES' Feistel-struktur trenger flere runder for å oppnå tilsvarende diffusjon. SPN-strukturen til AES passer også bedre til moderne prosessorarkitekturer med SIMD-instruksjoner.

Luby-Rackoff-teoremet behandler rundefunksjonen F som en virkelig tilfeldig funksjon. I praksis er F en pseudo-tilfeldig funksjon, for eksempel et nøkkelstyrt chiffer eller en hash, og ikke et virkelig tilfeldig orakel.

Dette skillet mellom teoretiske bevis og praktiske implementasjoner er et tilbakevendende tema i kryptografi. Bevis gir tillit, men bygger på idealiserte modeller. Sikkerheten i den virkelige verden avhenger også av sikre implementasjoner uten sidekanalsårbarheter.

Feistel-nettverk er blokkchifferstrukturer som bruker en rundefunksjon som ikke trenger å være inverterbar. Dekryptering fungerer ved å kjøre den samme strukturen i omvendt rekkefølge, med undernøklene i omvendt rekkefølge.

DES, Blowfish og Twofish er alle Feistel-chifre. Luby-Rackoff-teoremet gir teoretiske sikkerhetsgarantier. AES bruker i stedet en SPN-struktur, som gir bedre diffusjon per runde.