Hvad bør en blokchiffer indeholde ifølge Shannon?
Claude Shannon, ofte betragtet som faderen til moderne kryptografi og informationsteori, leverede grundlæggende principper, der har haft stor indflydelse på designet af sikre kryptografiske systemer. Hans skelsættende artikel fra 1949, "Communication Theory of Secrecy Systems", introducerede adskillige teoretiske koncepter, der fortsat vejleder kryptografer, især med hensyn til strukturen og kravene til blokchiffer. Når man overvejer, hvad en blokchiffer bør indeholde ifølge Shannon, er det nødvendigt at diskutere ikke kun de matematiske og strukturelle kriterier, men også begreberne forvirring og diffusion, deres praktiske anvendelse og deres implikationer for design og drift af blokchiffer i moderne systemer.
Shannons principper: Forvirring og spredning
Shannon identificerede to hovedegenskaber, som et robust chiffersystem bør besidde: forvirring og diffusion.
1. Forvirring:
Forvirringsegenskaben har til formål at tilsløre forholdet mellem krypteringsteksten og nøglen. Enklere sagt burde det være vanskeligt for en modstander at udlede nøglen, selvom de har adgang til krypteringsteksten og i nogle tilfælde den tilsvarende klartekst. Forvirring opnås typisk ved at bruge komplekse, ikke-lineære transformationer inden for krypteringsstrukturen, såsom substitutionsbokse (S-bokse). Effekten er, at ændring af en enkelt bit af nøglen fører til uforudsigelige og vidt varierende ændringer i krypteringsteksten, hvilket modvirker statistiske og algebraiske angreb.
*Eksempel:* I Advanced Encryption Standard (AES) skabes der forvirring ved brugen af S-bokse i SubBytes-trinnet, som erstatter hver byte i blokken med en anden i henhold til en fast, ikke-lineær transformation.
2. Distribution:
Diffusion er den egenskab, der sikrer, at indflydelsen af ét almindeligt tekstsymbol spredes over mange krypteringstekstsymboler. Formålet er at sprede den statistiske struktur af almindelig tekst over størstedelen af krypteringsteksten, så enhver statistisk sammenhæng mellem almindelig tekst og krypteringstekst minimeres. Dette opnås ofte ved permutationsoperationer, såsom bit- eller byte-omblanding inden for blokken. Lavineeffekten er et direkte resultat af korrekt diffusion: en lille ændring i almindelig tekst eller nøgle fører til en betydelig og uforudsigelig ændring i krypteringsteksten.
*Eksempel:* I Data Encryption Standard (DES) sikres diffusion via permutationsoperationer og blanding af bits i hver runde, således at ændring af én bit i klarteksten efter flere runder påvirker mange bits af krypteringsteksten.
Produktcifre: Kombination af forvirring og diffusion
Shannons analyse viste, at en enkelt anvendelse af forvirring eller diffusion er utilstrækkelig til stærk kryptering. I stedet anbefalede han at konstruere "produktchiffere", som består af flere runder eller lag, der hver kombinerer forvirring og diffusion. Denne tilgang øger eksponentielt chifferens sikkerhed ved at forstærke virkningerne af hver egenskab.
*Eksempel:* Både DES og AES bruger flere runder (16 for DES, 10-14 for AES, afhængigt af nøglestørrelse), der hver især inkorporerer både substitutions- (forvirring) og permutations-/blandings- (diffusions-) trin.
Strukturelle krav til en blokchiffer ifølge Shannon
Baseret på Shannons principper bør en blokchiffer indeholde:
- Ikke-lineære substitutionsoperationer (til forvirring):
Disse operationer erstatter inputværdier med outputværdier baseret på en ikke-lineær transformation, hvilket gør forholdet mellem klartekst, krypteret tekst og nøgle komplekst og modstandsdygtigt over for lineær og differentiel kryptanalyse.
- Permutations-/transpositionsoperationer (til diffusion):
Disse operationer omarrangerer blokkens bits eller bytes og sikrer, at den statistiske struktur af klarteksten er spredt i hele krypteringsteksten.
- Flere runder af forarbejdning (produktstruktur):
Kombinationen af substitution og permutation anvendes iterativt over flere runder, hvilket forværrer effekterne af forvirring og diffusion.
- Nøgleblanding:
Krypteringsdesignet bør inkorporere nøglen i transformationsprocessen på flere stadier, normalt i hver runde, for at forhindre angreb, der udnytter fast eller forudsigelig nøglebrug.
- Modstand mod kendte kryptanalytiske angreb:
Selvom Shannon ikke eksplicit har angivet det, kræver en moderne fortolkning af hans principper, at designet er robust over for statistiske, brute-force og avancerede kryptanalytiske angreb (såsom lineær og differentiel kryptanalyse), som udnytter svagheder i forvirring eller diffusion.
Anvendelse til moderne blokchifferdesign
Moderne blokchiffere som DES, AES og andre er direkte implementeringer af Shannons produktchifferkoncept. Hver runde inkluderer typisk:
- Nøgletilføjelse: Blanding af den runde nøgle med den aktuelle blok (normalt via XOR).
- Substitutionslag: Anvendelse af en ikke-lineær S-boks på hver byte eller gruppe af bits.
- Permutationslag eller diffusionslag: Blanding eller ombytning af bits, så outputbits afhænger af flere inputbits.
AES bruger for eksempel følgende trin i hver runde (efter den første tilføjelse af nøgler):
1. *SubBytes:* Ikke-lineær substitution af hver byte (forvirring).
2. *ShiftRows:* Cyklisk forskydning af bytes i hver række (delvis diffusion).
3. *MixColumns:* Blanding af hver kolonne i tilstanden (fuld diffusion).
4. *AddRoundKey:* XOR-funktion med en rundespecifik nøgle afledt af hovednøglen.
DES, selvom det nu anses for usikkert på grund af sin lille nøglestørrelse, følger også Shannons framework:
1. *Initial permutation:* Omarrangering af inputbits.
2. *Seksten runder:* Hver runde involverer udvidelse, substitution (via S-bokse), permutation og tastblanding.
3. *Endelig permutation:* Endnu en omorganisering af bits.
Driftsformer og deres forhold til Shannons principper
Blokchiffere er designet til at kryptere datablokke med fast størrelse (f.eks. 128 bit for AES). Praktiske meddelelser er dog ofte meget større eller mindre. Driftstilstande, såsom ECB, CBC, CFB, OFB og CTR, definerer, hvordan blokchiffere anvendes på datastrømme af vilkårlig længde. Mens driftstilstande styrer, hvordan blokke kædes sammen, og hvordan fejl udbreder sig, afhænger den underliggende sikkerhed for blokchifferen i enhver tilstand af korrekt implementering af forvirring og diffusion som specificeret af Shannon.
For eksempel:
- ECB (elektronisk kodebogstilstand):
Hver almindelig tekstblok krypteres uafhængigt. Denne tilstand giver ikke yderligere diffusion på tværs af blokke og lækker dermed mønstre, hvis den samme almindelige tekstblok gentages i en besked.
- CBC (Cipher Block Chaining):
Hver almindelig tekstblok XOR-behandles med den foregående krypteringsblok før kryptering, hvilket øger diffusionen mellem blokke og gør mønstre mindre synlige.
- CTR (tællertilstand):
Anvender blokchifferen på en tællerværdi og udfører XOR-er på resultatet med klarteksten, hvilket omdanner blokchifferen til en strømchiffer. Mens kerneblokchifferen stadig skal skabe forvirring og diffusion, sikrer tilstanden, at identiske klartekstblokke krypteres til forskellige krypteringstekstblokke på grund af den skiftende tæller.
Eksempler, der illustrerer Shannons kriterier
Overvej en hypotetisk blokchiffer med lav forvirring: Antag, at substitutionstrinnet er en simpel, lineær kortlægning (f.eks. øge hver byte med 1). En angriber kan nemt udlede transformationen og vende den, hvilket afslører nøglen eller klarteksten. Tilsvarende, hvis diffusionstrinnet er utilstrækkeligt - såsom kun at bytte tilstødende bytes - påvirker lokaliserede ændringer i klarteksten kun små dele af chifferteksten, hvilket gør chifferen modtagelig for analyse.
På den anden side, ved stærk forvirring og diffusion, som i AES, vil ændring af en enkelt bit af klarteksten eller nøglen efter flere runder påvirke alle bits af krypteringsteksten på en uforudsigelig måde. Dette er lavineeffekten, en direkte manifestation af Shannons principper.
Teoretisk begrundelse og praktiske implikationer
Shannon introducerede begrebet "unicity-afstand", den minimale mængde krypteret tekst, der er nødvendig for entydigt at bestemme nøglen for en given kryptering. Unicity-afstanden afhænger af nøglerummets størrelse, redundansen af klartekstsproget og krypteringens evne til at ødelægge statistiske strukturer (diffusion). En kryptering med høj forvirring og diffusion øger unicity-afstanden, hvilket gør det umuligt for en angriber at gendanne nøglen, selv med betydelig krypteret tekst.
Desuden er Shannons principper ikke kun relevante for design af krypteringer, men også for deres evaluering. Når kryptografer vurderer sikkerheden af en blokkryptering, analyserer de graden af forvirring og diffusion i hver runde og den overordnede struktur, hvilket sikrer, at der ikke er genveje til angreb, der udnytter statistiske sammenhænge eller strukturelle svagheder.
Opsummeringsparagraf
Shannons kriterier for en sikker blokchiffer er både teoretiske og praktiske. I bund og grund bør en blokchiffer inkorporere stærk forvirring og diffusion, opnået gennem ikke-lineære substitutioner, permutationer og gentagne behandlingsrunder. Kombinationen af disse elementer forstyrrer statistiske mønstre, tilslører nøglen og sikrer, at selv små ændringer i klarteksten eller nøglen resulterer i udbredte, uforudsigelige ændringer i chifferteksten. Disse principper, der først blev formuleret i midten af det 20. århundrede, forbliver fundamentet for alle moderne blokchifferdesign og er uundværlige for at sikre fortrolighed og sikkerhed i digital kommunikation.
Andre seneste spørgsmål og svar vedr Anvendelser af blokkoder:
- Afhænger sikkerheden af blokchiffere af at kombinere forvirrings- og diffusionsoperationer mange gange?
- 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