Afhænger sikkerheden af blokchiffere af at kombinere forvirrings- og diffusionsoperationer mange gange?
Sikkerheden ved blokchiffer er fundamentalt forankret i den iterative anvendelse af forvirrings- og diffusionsoperationer. Dette koncept blev først formaliseret af Claude Shannon i hans banebrydende arbejde om kommunikationsteorien om hemmeligholdelsessystemer, hvor han formulerede nødvendigheden af både forvirring og diffusion i kryptografiske systemer for at modvirke statistiske og strukturelle angreb. Forståelse af, hvorfor flere runder af disse operationer er nødvendige, og hvordan de hænger sammen, er afgørende for at værdsætte designet og sikkerheden ved moderne blokchiffer, såsom Data Encryption Standard (DES) og Advanced Encryption Standard (AES).
Forvirring og diffusion: Definitioner og roller
Forvirring søger at gøre forholdet mellem krypteringsteksten og nøglen så komplekst som muligt. Det gøres ved at maskere den statistiske struktur i klarteksten, ofte ved hjælp af ikke-lineære substitutioner (f.eks. S-bokse i DES og AES). Jo mere ikke-lineær og kompleks denne kortlægning er, desto sværere bliver det for en angriber at udlede information om nøglen, selv givet adgang til mange klartekst-krypteringstekst-par.
Diffusion sigter derimod mod at sprede indflydelsen af hver klartekstbit på tværs af mange krypteringstekstbits, således at en ændring i en enkelt inputbit resulterer i ændringer i mange outputbits. Denne egenskab sikrer, at statistiske egenskaber ved klarteksten spredes gennem krypteringsteksten, hvilket gør det umuligt for angribere at udnytte mønstre via frekvensanalyse eller lignende teknikker. Diffusion opnås typisk gennem lineære blandingsoperationer, såsom permutation, bitvise XOR'er eller matrixmultiplikationer (som i MixColumns-operationen i AES).
Struktur af iterative blokchiffere
De fleste blokchiffere er struktureret som itererede chiffere, hvilket betyder, at de anvender en simpel rundefunktion flere gange for at opnå et højt sikkerhedsniveau. Rundefunktionen kombinerer typisk både forvirring (f.eks. gennem S-box-applikationer) og diffusion (f.eks. gennem permutation eller blandingstrin). Rationalet bag at anvende flere runder er, at en enkelt anvendelse af forvirring og diffusion er utilstrækkelig til at skjule alle strukturelle relationer mellem klartekst, chiffertekst og nøgle. Hver runde øger trinvist kompleksiteten af disse relationer, og først efter flere runder opnår chifferen det ønskede sikkerhedsniveau mod kendte kryptanalytiske angreb.
For eksempel, i betragtning af AES-chifferen, består hver krypteringsrunde af følgende nøgletrin:
1. SubBytes (Forvirring): Hver byte i tilstandsmatricen erstattes med en anden i henhold til en fast ikke-lineær S-boks, hvilket introducerer ikke-linearitet.
2. ShiftRows (Diffusion): Rækker i tilstandsmatricen forskydes cyklisk, hvilket flytter bytes til forskellige kolonner og letter blanding af værdier.
3. Bland kolonner (diffusion): Kolonner i tilstanden blandes ved hjælp af matrixmultiplikation i et endeligt felt, hvilket yderligere spreder indflydelsen af hver inputbyte.
4. AddRoundKey (Forvirring): Tilstandsmatricen kombineres med en undernøgle afledt af hovednøglen, hvilket introducerer nøgleafhængighed i hver runde.
Krypteringens effektivitet afhænger ikke kun af styrken af hver enkelt operation, men også af antallet af gange disse operationer anvendes. Kryptanalytikere har vist, at reduktion af antallet af runder i en kryptering, såsom AES eller DES, kan gøre den sårbar over for angreb som differentiel og lineær kryptanalyse. For eksempel, mens den fulde AES-128 bruger 10 runder, er versioner med kun 6 runder modtagelige for visse kryptanalytiske teknikker.
Nødvendigheden af flere runder
For yderligere at afklare, overvej hvad der sker, hvis der kun anvendes en enkelt runde med forvirring og diffusion. Selv hvis der anvendes stærke S-bokse og blandingslag, kan statistiske sammenhænge og mønstre fortsætte. Angribere kan udnytte disse resterende mønstre ved hjælp af angreb af typen "chosen-plaintext" eller "known-plaintext". Flere runder sikrer, at indflydelsen fra hver nøgle og klartekstbit er grundigt spredt over hele krypteringsteksten, hvilket gør det umuligt at udføre sådanne angreb.
Konceptet "lavineeffekten" er centralt her. En stærk kryptering sikrer, at en lille ændring i klarteksten (såsom at vende en enkelt bit) resulterer i en ændring i cirka halvdelen af bitsene i krypteringsteksten, og denne egenskab opnås først efter flere runder med forvirring og diffusion. Den iterative struktur i moderne blokchifre er specifikt designet til at forstærke denne effekt, hvilket gør krypteringen modstandsdygtig over for angreb, der er afhængige af at spore input-output-forhold.
Eksempler: DES og AES
Den historiske DES-chiffer illustrerer dette princip godt. DES bruger 16 runder i sin Feistel-netværksstruktur, hvor hver runde består af ekspansion, S-box-substitution (forvirring) og permutation (diffusion). Omfattende kryptanalyse har vist, at brug af færre end 16 runder fører til svagheder; differentiel kryptanalyse er effektiv mod versioner med færre runder. Designerne valgte 16 runder for at give en sikkerhedsmargin mod fremskridt inden for kryptanalyse, hvilket understreger vigtigheden af flere iterationer.
AES, designet årtier senere, anvender 10, 12 eller 14 runder afhængigt af nøglestørrelsen (henholdsvis 128, 192 eller 256 bit). Hver runde inkorporerer de kombinerede effekter af forvirring og diffusion gennem dens SubBytes-, ShiftRows- og MixColumns-trin. Antallet af runder blev omhyggeligt valgt baseret på kryptanalytiske fund for at afbalancere sikkerhed og ydeevne.
Driftsformer og deres relation
Mens den interne sikkerhed for blokchiffere bestemmes af gentagen forvirring og diffusion, specificerer driftstilstanden (f.eks. ECB, CBC, CFB, OFB, CTR), hvordan blokchiffere anvendes på data, der er større end en enkelt blok. Sikkerhedsegenskaberne for en blokchiffer i en given tilstand afhænger fundamentalt af blokchifferens modstandsdygtighed over for angreb, hvilket igen er en funktion af, hvor grundigt forvirring og diffusion opnås på tværs af flere runder. Hvis den underliggende blokchiffer er svag (for eksempel med for få runder), kan ingen driftstilstand kompensere for denne mangel.
Kryptanalytiske angreb og runder
Adskillige kryptanalytiske angreb udnytter utilstrækkelig forvirring og diffusion i blokchifre. Differentiel kryptanalyse studerer for eksempel, hvordan forskelle i klartekst påvirker de resulterende chiffertekstforskelle. Hvis chifferen ikke har tilstrækkeligt diffust inputforskelle, kan en angriber forudsige, hvordan disse forskelle udbreder sig, og bruge denne viden til at gendanne nøglen. Tilsvarende søger lineær kryptanalyse lineære tilnærmelser mellem klartekst, chiffertekst og nøglebits. Effektiviteten af disse angreb aftager, efterhånden som antallet af runder stiger, forudsat at hver runde effektivt implementerer forvirring og diffusion.
For at illustrere er DES med 8 runder (halvdelen af standardantallet) modtagelig for differentiel kryptanalyse, men med 16 runder bliver sandsynligheden for at udbrede et nyttigt differentielt spor på tværs af alle runder ubetydelig. Dette viser, at den iterative struktur, og specifikt antallet af runder, er fundamental for at opnå praktisk sikkerhed.
Design afvejninger
Krypteringsdesignere skal afbalancere antallet af runder med ydeevnekrav. Flere runder betyder generelt mere sikkerhed, men også flere beregningsomkostninger. Antallet af runder vælges typisk for at give en sikkerhedsmargin over de mest kendte angreb på designtidspunktet, med forventning om, at fremtidige fremskridt inden for kryptanalyse kan undergrave denne margin. Denne konservative tilgang sikrer, at krypteringen forbliver sikker i løbet af dens forventede levetid.
Matematisk begrundelse
Fra et teoretisk synspunkt kan itererede blokchifferdesigns ses gennem linsen af "itereret produktchiffer"-modellen. Under visse antagelser er det blevet vist, at sammensætningen af flere svage chiffere (der hver især implementerer svag forvirring og/eller diffusion) kan producere en stærk samlet chiffer, forudsat at komponenterne er tilstrækkeligt uafhængige, og antallet af runder er stort. Dette retfærdiggør den iterative tilgang til forvirring og diffusion i praktisk chifferdesign.
Praktiske eksempler
Et lærerigt eksempel er substitution-permutation network (SPN) strukturen, der anvendes af AES. I en SPN udsættes klarteksten for alternerende lag af substitution (forvirring) og permutation (diffusion). Efter flere runder afhænger hver outputbit af hver inputbit på en meget ikke-lineær måde. Denne egenskab opnås ikke med en enkelt runde; det er den kumulative effekt af flere runder, der sikrer, at hver bit af krypteringsteksten er en kompleks funktion af hver bit af klarteksten og nøglen, en egenskab kendt som fuldstændig diffusion.
Feistel-netværket, som det bruges i DES, opnår lignende sikkerhed ved iterativt at anvende en rundefunktion, der kombinerer substitution og permutation, hvor outputtet fra hver runde overføres til den næste. Sikkerheden af sådanne konstruktioner stiger eksponentielt med antallet af runder, forudsat at selve rundefunktionen ikke er trivielt inverterbar eller lineær.
Konklusion: Sikkerhedsafhængighed af iteration
Styrken af blokchifre er uløseligt forbundet med den gentagne anvendelse af forvirrings- og diffusionsoperationer. Moderne chifre er designet med et tilstrækkeligt antal runder til at sikre, at eventuelle resterende statistiske sammenhænge fra klarteksten eller nøglen elimineres, og at hver bit af chifferteksten påvirkes af hver bit af klarteksten og nøglen. Denne iterative proces er ikke blot en implementeringsdetalje, men et grundlæggende princip for chiffersikkerhed. Antallet af runder vælges baseret på omfattende kryptanalyse for at give en sikkerhedsmargin og revurderes med jævne mellemrum, når nye angreb dukker op. I alle praktiske og teoretiske henseender er sikkerheden af blokchifre faktisk afhængig af at kombinere forvirrings- og diffusionsoperationer mange gange.
Andre seneste spørgsmål og svar vedr Anvendelser af blokkoder:
- Hvad bør en blokchiffer indeholde ifølge Shannon?
- Betyder diffusion, at enkelte bits af krypteret tekst er påvirket af mange bits af klartekst?
- Opdeler ECB-tilstanden store input-klartekst i efterfølgende blokke
- Kan vi bruge en blokchiffer til at bygge en hash-funktion eller MAC?
- Kan OFB-tilstand bruges som keystream-generatorer?
- Kan en indskrivning være deterministisk?
- Hvad er driftsformer?
- Hvad gør ECB-tilstanden ved simple blokcifre
- Kan PSRNG laves med blokcifre?
- Kan en MAC bygges med blokcifre?
Se flere spørgsmål og svar i Applications of block ciphers