Feistel-netwerken: bouwstenen van moderne cijfers

Begin jaren 1970 werkte Horst Feistel bij IBM Research aan het Lucifer-cijfer toen hij een fundamenteel inzicht ontwikkelde: je kunt een inverteerbaar cijfer bouwen met een niet-inverteerbare rondefunctie.

Dit was revolutionair, omdat het moeilijk is om functies te ontwerpen die zowel inverteerbaar als veilig zijn. De constructie van Feistel omzeilt deze vereiste volledig, zodat je willekeurig complexe, eenrichtings-rondefuncties kunt gebruiken.

In een Feistelcijfer wordt het invoerblok opgesplitst in twee gelijke helften: L (links) en R (rechts). Elke ronde past de rondefunctie F toe op R, voert XOR uit met het resultaat en L, en verwisselt daarna de helften.

Na n rondes worden de twee helften weer samengevoegd om de cijfertekst te produceren. Door het verwisselen worden beide helften in afwisselende rondes verwerkt en grondig vermengd.

De rondefunctie F in een Feistelnetwerk neemt de rechterhelft en de rondedeelsleutel als invoer en produceert een uitvoer die met de linkerhelft wordt gecombineerd via XOR. Belangrijk is dat F niet inverteerbaar hoeft te zijn.

F kan willekeurig complex zijn: elke combinatie van substituties, permutaties, XOR-bewerkingen en modulaire rekenkunde. Hoe complexer en niet-lineairder F is, hoe sterker het cijfer, omdat voor ontsleuteling F nooit hoeft te worden geïnverteerd.

Ontsleuteling in een Feistelcijfer gebruikt precies dezelfde structuur als versleuteling, maar past de rondedeelsleutels in omgekeerde volgorde toe. Dit is mogelijk omdat XOR zijn eigen inverse is: als A XOR B = C, dan is C XOR B = A.

Omdat voor ontsleuteling nooit F^-1, de inverse van F, wordt aangeroepen, kan de rondefunctie een onomkeerbare hash, een opzoektabel of een willekeurig complexe bewerking zijn zonder de inverteerbaarheid van het cijfer aan te tasten.

De wiskundige elegantie van Feistelnetwerken is dat de XOR-structuur de inverteerbaarheid garandeert, ongeacht wat F doet. Zelfs als F een eenrichtingsfunctie zoals SHA-256 is, blijft het volledige Feistelcijfer inverteerbaar.

Hierdoor zijn Feistelcijfers uiterst flexibel. Cryptografen kunnen zich volledig richten op het zo verwarrend en diffuus mogelijk maken van F, omdat de inverteerbaarheid door de netwerkstructuur zelf wordt geregeld.

De Data Encryption Standard (DES), gepubliceerd in 1977, is een Feistelcijfer met 16 rondes dat werkt op blokken van 64 bits en een sleutel van 56 bits. Elke ronde gebruikt een andere rondedeelsleutel van 48 bits die van de hoofdsleutel is afgeleid.

De rondefunctie in DES omvat een expansiepermutatie, XOR met de rondedeelsleutel, acht S-boxes die voor niet-lineariteit zorgen en een P-box-permutatie. De combinatie zorgt voor zowel verwarring als diffusie, zoals vereist door Shannons ontwerpprincipes voor cijfers.

Blowfish, ontworpen door Bruce Schneier in 1993, is een Feistelcijfer met een variabele sleutellengte van 32 tot 448 bits en 16 rondes. Het gebruikt sleutelafhankelijke S-boxes, waardoor vooraf berekende aanvallen onpraktisch worden.

Twofish, een finalist in de AES-competitie, bouwt voort op ideeën uit Blowfish met blokken van 128 bits en 16 rondes. Beide zijn nog steeds niet gekraakt en worden gebruikt in toepassingen zoals bcrypt voor het hashen van wachtwoorden, dat een aangepaste versie van Blowfish gebruikt.

Een gebalanceerd Feistelcijfer splitst het blok in twee gelijke helften. Een ongebalanceerde Feistel gebruikt ongelijke helften, zoals een verdeling van 3/4 en 1/4.

Ongebalanceerde Feistelnetwerken kunnen in bepaalde contexten beveiligingsvoordelen bieden en worden in sommige gespecialiseerde cijfers gebruikt. De CAST-familie van cijfers gebruikt een gebalanceerde Feistelstructuur van 64 bits.

In 1988 bewezen Michael Luby en Charles Rackoff dat een Feistelnetwerk met 3 rondes en pseudowillekeurige rondefuncties een veilige pseudowillekeurige permutatie (PRP) is en dat een versie met 4 rondes een sterke PRP is.

Dit theoretische resultaat gaf Feistelnetwerken een stevige, aantoonbare basis voor beveiliging en niet alleen empirisch vertrouwen. Het bevestigde dat de Feistelstructuur zelf bijdraagt aan de beveiliging, naast alleen de rondefunctie.

Het Substitution-Permutation Network (SPN) dat AES gebruikt, past substitutie en permutatie tegelijk toe op het volledige blok in plaats van op de helft van het blok per ronde. Dit zorgt voor snellere diffusie.

AES bereikt volledige diffusie in slechts 4 rondes, terwijl de Feistelstructuur van DES meer rondes nodig heeft voor vergelijkbare diffusie. De SPN van AES sluit ook beter aan op moderne processorarchitecturen met SIMD-instructies.

De stelling van Luby en Rackoff behandelt de rondefunctie F als een echt willekeurige functie. In de praktijk is F een pseudowillekeurige functie, zoals een cijfer met sleutel of een hash, en geen echt willekeurig orakel.

Deze kloof tussen theoretische bewijzen en praktische implementaties is een terugkerend thema in de cryptografie. Bewijzen geven vertrouwen, maar zijn gebaseerd op geïdealiseerde modellen. Beveiliging in de echte wereld hangt ook af van veilige implementaties zonder kwetsbaarheden via zijkanalen.

Feistelnetwerken zijn structuren voor blokcijfers die een rondefunctie gebruiken die niet inverteerbaar hoeft te zijn. Ontsleuteling werkt door dezelfde structuur in omgekeerde richting uit te voeren met de deelsleutels in omgekeerde volgorde.

DES, Blowfish en Twofish zijn allemaal Feistelcijfers. De stelling van Luby en Rackoff biedt theoretische beveiligingsgaranties. AES gebruikt in plaats daarvan een SPN-structuur, die per ronde betere diffusie biedt.