Feistel-netværk (Feistel-chiffer): Definition og anvendelse i blokchifre

Feistel-netværk: Klar gennemgang af Feistel-chifferets struktur, fordele og anvendelser i blokchifre samt hvordan det effektivt sikrer kryptering og dekryptering.

Inden for kryptografi er en Feistel-chiffer en symmetrisk struktur, der anvendes til konstruktion af blokchiffer, opkaldt efter den tyske IBM-kryptograf Horst Feistel; den er også almindeligvis kendt som et Feistel-netværk. En lang række blokchiffrer anvender dette skema, herunder Data Encryption Standard

Feistel-strukturen har den fordel, at krypterings- og dekrypteringsoperationer er meget ens, i nogle tilfælde endog identiske, og at det kun kræver en omvendt nøgleplanlægning. Derfor er størrelsen af den kode eller det kredsløb, der kræves for at implementere en sådan kryptering, næsten halveret.

Feistel-konstruktionen er iterativ i sin natur, hvilket gør det lettere at implementere kryptosystemet i hardware.

Feistel-netværk og lignende konstruktioner er produktchiffrer og kombinerer derfor flere runder af gentagne operationer, f.eks:

• Bit-shuffling (ofte kaldet permutationsbokse eller P-bokse)
• Simple ikke-lineære funktioner (ofte kaldet substitutionsbokse eller S-bokse)
• Lineær blanding (i modulalgebraens forstand) ved hjælp af XOR for at frembringe en funktion med store mængder af det, som Claude Shannon beskrev som "forvirring og spredning".

Bit shuffling skaber diffusionseffekten, mens substitution bruges til at skabe forvirring.

Hvordan en Feistel-runde virker

I et klassisk, afbalanceret Feistel-netværk opdeles et blokdata-stykke i to lige store halvdele, kaldet venstre (L) og højre (R). En enkel runde beskrives ofte som:

L_{i+1} = R_i og R_{i+1} = L_i XOR F(R_i, K_i)

Her er F en (typisk ikke-inverterbar) runde-funktion, og K_i er rundens nøgle (fra nøgleplanlægningen). Efter flere runder byttes halvdelenes roller gentagne gange. Fordi L_{i+1} kun er en kopi af R_i, og R_{i+1} kombinerer L_i og en funktion af R_i, behøver F ikke at være invertibel for at hele cifren kan dekrypteres — dekryptering udføres blot ved at køre samme konstruktionstrin i omvendt rækkefølge med rundefunktionerne anvendt i reverse nøglerækkefølge.

Varianter

• Afbalanceret Feistel: Halvdelene er lige store (mest almindeligt).
• Uafbalanceret Feistel: Halvdelene kan have forskellig størrelse; anvendt i nogle specialiserede cifre for at håndtere inputstørrelser, der ikke er lige.
• Generaliserede Feistel-netværk: Flere end to blokke (f.eks. 4-vejs Feistel), hvor runderoterende kombinationer bruges mellem flere ord.

Sikkerhed og teoretiske resultater

Feistel-netværkets sikkerhed afhænger af rundefunktionernes kvalitet, antallet af runder og nøgleplanlægningen. Et vigtigt teoretisk resultat er Luby–Rackoff-teoremet, som viser, at under antagelsen af uafhængige tilfældige rundefunktioner kan et lille antal runder give stærke sikkerhedsegenskaber:

• Med tre uafhængige tilfældige rundefunktioner får man en pseudotilfældig permutation (PRP) — dvs. opfører sig som et tilfældigt bijektivt kortlægning for en angriber uden ubegrænsede ressourcer.
• Med fire runder opnås ofte stærkere sikkerhedsegenskaber (såkaldt strong PRP) mod bredere angrebstyper.

I praksis kræver sikre, konkrete design typisk flere runder end det teoretiske minimum, og man skal være opmærksom på kendte svagheder i selve rundefunktionen og i nøgleplanlægningen.

Anvendelser

Feistel-konstruktionen er brugt i mange kendte blokchifre. Den mest berømte anvendelse er Data Encryption Standard, som bruger 16 runder og en bestemt type rundefunktion baseret på S-bokse og permutationer. Andre eksempler (uden links i denne artikel) inkluderer Blowfish, CAST og 3DES (som bruger DES-kerner i en itereret struktur).

Fordele og ulemper

• Fordele:
  • Enkel dekryptering: samme struktur som kryptering, blot omvendt nøgleordre.
  • Rundefunktionen behøver ikke at være inverterbar, hvilket giver designfrihed.
  • Let at implementere effektivt både i hardware og software.
• Ulemper:
  • Kræver ofte mange runder for at opnå ønsket sikkerhed, hvilket kan påvirke ydeevnen.
  • Fejl i rundefunktionen eller nøgleplanlægningen kan svække hele cifren.

Implementeringsnoter

Når man implementerer et Feistel-baseret chiffer, er følgende praktiske forhold vigtige:

• Nøgleplanlægning: En sikker og effektiv udledning af rundekeyes er afgørende. Enkel ombytning af nøgler kan gøre dekryptering trivialt, men en dårlig nøgleplanlægning kan lække information om nøglen.
• Rundefunktionens design: F bør indeholde både ikke-lineariteter (S-bokse) og spredning (permutationer / P-bokse) for at undgå statistiske svagheder.
• Antal runder: Vælg et passende antal runder baseret på både teoretiske analyser og praktisk erfaring i forhold til ønsket sikkerhedsniveau.
• Sidekanalangreb: Implementationsmodståelsesmekanismer (time-masking, konstante-tidsoperationer osv.) er vigtige for virkelige systemer.

Sammenfatning

Et Feistel-netværk er en fleksibel og velafprøvet metode til at bygge blokchifre. Dets hovedfordele er enkel implementering, symmetri mellem kryptering og dekryptering og muligheden for at anvende ikke-inverterbare rundefunktioner. Sikkerhed afhænger dog stærkt af rundefunktionens kvalitet, nøgleplanlægningen og antallet af runder — og derfor testes og analyseres konkrete Feistel-baserede cifre nøje før brug i kritiske systemer.

Byggeri

Lad F {\displaystyle {\rm {F}}}} være rundens funktion, og lad K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}}være undernøglerne for henholdsvis runde 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}}.

Den grundlæggende operation er så som følger:

Opdel den klare tekstblok i to lige store stykker ( L 1 {\displaystyle L_{1}}} , R 1 {\displaystyle R_{1}}} )

For hver runde i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} , beregne (beregne)

L i + 1 = R i {\displaystyle L_{i+1}=R_{i}\,}

R i + 1 = L i ⊕ F ( R i , K i ) {\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}}(R_{i},K_{i})} .

Så er den krypterede tekst ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} . (Almindeligvis byttes de to dele R n {\displaystyle R_{n}}} og L n {\displaystyle L_{n}}} ikke om efter den sidste runde).

Dekryptering af en krypteringstekst ( R n , L n ) {\displaystyle (R_{n},L_{n})} opnås ved at beregne for i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1}

R i = L i + 1 {\displaystyle R_{i}=L_{i+1}\,}

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}}(L_{i+1},K_{i})} .

Så er ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} igen den klare tekst.

En fordel ved denne model er, at den runde funktion F {\displaystyle {\rm {F}}}} ikke behøver at være invertibel og kan være meget kompleks.

Diagrammet illustrerer krypteringsprocessen. Dekryptering kræver blot, at rækkefølgen af undernøglen K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}}} omvendes ved hjælp af den samme proces; dette er den eneste forskel mellem kryptering og dekryptering:

Ubalancerede Feistel-krypteringer anvender en modificeret struktur, hvor L 1 {\displaystyle L_{1}}} og R 1 {\displaystyle R_{1}}} ikke er lige lange. MacGuffin-chifferet er et eksperimentelt eksempel på en sådan chiffer.

Feistel-konstruktionen anvendes også i andre kryptografiske algoritmer end blokchiffrer. F.eks. bruger OAEP-ordningen (Optimal Asymmetric Encryption Padding) et simpelt Feistel-netværk til at randomisere ciphertexter i visse asymmetriske krypteringsordninger.

Feistel-netværksoperation på blokcifring, hvor P er klarteksten og C er cifferteksten

Spørgsmål og svar

Spørgsmål: Hvad er en Feistel-ciffer?

Sp: Hvilke fordele er der ved at bruge en Feistel-struktur?

Spørgsmål: Hvordan beskriver Claude Shannon "forvirring og spredning"?

Spørgsmål: Hvilke teknikker anvendes til at skabe forvirring og spredning?

Spørgsmål: Hvilken type kryptering er et Feistel-netværk?

Spørgsmål: Hvem har udviklet denne type kryptografi?

Spørgsmål: Er Data Encryption Standard baseret på denne type kryptografi?

Søg efter bogstav