Beror säkerheten för blockchiffer på att man kombinerar förvirrings- och diffusionsoperationer många gånger?
Säkerheten hos blockchiffer är fundamentalt förankrad i den iterativa tillämpningen av förvirrings- och diffusionsoperationer. Detta koncept formaliserades först av Claude Shannon i hans banbrytande arbete om kommunikationsteori för sekretesssystem, där han formulerade behovet av både förvirring och diffusion i kryptografiska system för att motverka statistiska och strukturella attacker. Att förstå varför flera omgångar av dessa operationer krävs, och hur de samverkar, är avgörande för att uppskatta designen och säkerheten hos moderna blockchiffer som Data Encryption Standard (DES) och Advanced Encryption Standard (AES).
Förvirring och diffusion: Definitioner och roller
Förvirring syftar till att göra förhållandet mellan chiffertexten och nyckeln så komplext som möjligt. Den gör det genom att maskera den statistiska strukturen i klartexten, ofta genom användning av icke-linjära substitutioner (t.ex. S-rutor i DES och AES). Ju mer icke-linjär och komplex denna mappning är, desto svårare blir det för en angripare att härleda information om nyckeln, även med tillgång till många klartext-chiffrerad text-par.
Diffusion, å andra sidan, syftar till att sprida inflytandet av varje klartextbit över många chiffertextbitar, så att en förändring av en enda inmatningsbit resulterar i förändringar av många utmatningsbitar. Denna egenskap säkerställer att statistiska egenskaper hos klartexten sprids genom chiffertexten, vilket gör det omöjligt för angripare att utnyttja mönster via frekvensanalys eller liknande tekniker. Diffusion uppnås vanligtvis genom linjära blandningsoperationer, såsom permutation, bitvisa XOR:er eller matrismultiplikationer (som i MixColumns-operationen i AES).
Strukturen för iterativa blockchiffer
De flesta blockchiffer är strukturerade som itererade chiffer, vilket innebär att de tillämpar en enkel rundfunktion flera gånger för att uppnå en hög säkerhetsnivå. Rundfunktionen kombinerar vanligtvis både förvirring (t.ex. genom S-box-applikationer) och diffusion (t.ex. genom permutation eller blandningssteg). Motivet bakom att använda flera rundor är att en enda tillämpning av förvirring och diffusion är otillräcklig för att dölja alla strukturella relationer mellan klartext, chiffertext och nyckel. Varje runda ökar stegvis komplexiteten hos dessa relationer, och först efter flera rundor uppnår chiffern önskad säkerhetsnivå mot kända kryptanalytiska attacker.
Om man till exempel använder AES-chiffern består varje krypteringsrunda av följande viktiga steg:
1. SubBytes (förvirring): Varje byte i tillståndsmatrisen ersätts med en annan enligt en fast ickelinjär S-box, vilket introducerar ickelinjäritet.
2. ShiftRows (Diffusion): Rader i tillståndsmatrisen förskjuts cykliskt, vilket flyttar byte till olika kolumner och underlättar blandning av värden.
3. Blandkolumner (diffusion): Kolumner i tillståndet blandas med hjälp av matrismultiplikation i ett ändligt fält, vilket ytterligare sprider inflytandet från varje ingångsbyte.
4. AddRoundKey (förvirring): Tillståndsmatrisen kombineras med en undernyckel som härrör från huvudnyckeln, vilket introducerar nyckelberoende vid varje runda.
Chifferns effektivitet beror inte bara på styrkan hos varje enskild operation utan också på hur många gånger dessa operationer tillämpas. Kryptanalytiker har visat att en minskning av antalet omgångar i en chiffer som AES eller DES kan göra den sårbar för attacker som differentiell och linjär kryptanalys. Till exempel, medan den fullständiga AES-128 använder 10 omgångar, är versioner med bara 6 omgångar mottagliga för vissa kryptanalytiska tekniker.
Nödvändigheten av flera rundor
För att ytterligare klargöra, överväg vad som händer om bara en enda omgång av förvirring och diffusion tillämpas. Även om starka S-boxar och blandningslager används kan statistiska samband och mönster kvarstå. Angripare kan utnyttja dessa kvarvarande mönster med hjälp av attacker av typen "chosen plaintext" eller "known plaintext". Flera omgångar säkerställer att inflytandet från varje nyckel och klartextbit sprids ordentligt över hela chiffertexten, vilket gör det omöjligt att utföra sådana attacker.
Konceptet med "lavineffekten" är centralt här. En stark chiffer säkerställer att en liten förändring i klartexten (som att vända en enda bit) resulterar i en förändring av ungefär hälften av bitarna i chiffertexten, och denna egenskap uppnås först efter flera omgångar av förvirring och diffusion. Den iterativa strukturen hos moderna blockchiffer är specifikt utformad för att förstärka denna effekt, vilket gör chiffern motståndskraftig mot attacker som förlitar sig på att spåra input-output-relationer.
Exempel: DES och AES
Det historiska DES-chiffern illustrerar denna princip väl. DES använder 16 rundor i sin Feistel-nätverksstruktur, där varje runda består av expansion, S-box-substitution (förvirring) och permutation (diffusion). Omfattande kryptanalys har visat att användning av färre än 16 rundor leder till svagheter; differentiell kryptanalys är effektiv mot versioner med färre rundor. Designarna valde 16 rundor för att ge en säkerhetsmarginal mot framsteg inom kryptanalys, vilket understryker vikten av flera iterationer.
AES, som designades årtionden senare, tillämpar 10, 12 eller 14 rundor beroende på nyckelstorleken (128, 192 respektive 256 bitar). Varje runda innehåller de kombinerade effekterna av förvirring och diffusion genom sina steg SubBytes, ShiftRows och MixColumns. Antalet rundor valdes noggrant baserat på kryptanalytiska fynd för att balansera säkerhet och prestanda.
Driftsätt och deras relation
Medan blockchifferns interna säkerhet bestäms av upprepad förvirring och spridning, specificerar funktionssättet (t.ex. ECB, CBC, CFB, OFB, CTR) hur blockchiffer tillämpas på data större än ett enda block. Säkerhetsegenskaperna för ett blockchiffer i ett givet läge beror fundamentalt på blockchifferns motståndskraft mot attacker, vilket i sin tur är en funktion av hur grundligt förvirring och spridning uppnås över flera omgångar. Om det underliggande blockchiffern är svagt (till exempel med för få omgångar) kan inget funktionssätt kompensera för denna brist.
Kryptanalytiska attacker och rundor
Flera kryptanalytiska attacker utnyttjar otillräcklig förvirring och diffusion i blockchiffer. Differentiell kryptanalys studerar till exempel hur skillnader i klartext påverkar de resulterande chiffertextskillnaderna. Om chifferet inte har diffunderat inmatningsskillnader tillräckligt kan en angripare förutsäga hur dessa skillnader sprids och använda denna kunskap för att återställa nyckeln. På liknande sätt söker linjär kryptanalys linjära approximationer mellan klartext, chiffertext och nyckelbitar. Effektiviteten hos dessa attacker minskar när antalet omgångar ökar, förutsatt att varje omgång effektivt implementerar förvirring och diffusion.
För att illustrera detta är DES med 8 rundor (hälften av standardantalet) mottagligt för differentiell kryptanalys, men med 16 rundor blir sannolikheten för att sprida ett användbart differentiellt spår över alla rundor försumbar. Detta visar att den iterativa strukturen, och specifikt antalet rundor, är grundläggande för att uppnå praktisk säkerhet.
Design avvägningar
Chifferkonstruktörer måste balansera antalet rundor mot prestandakrav. Fler rundor innebär generellt sett mer säkerhet, men också mer beräkningskostnad. Antalet rundor väljs vanligtvis för att ge en säkerhetsmarginal över de mest kända attackerna vid designtillfället, med förväntan om att framtida framsteg inom kryptanalys kan urholka denna marginal. Denna konservativa metod säkerställer att chiffern förblir säker under sin förväntade livslängd.
Matematisk motivering
Ur ett teoretiskt perspektiv kan itererade blockchifferdesigner ses genom linsen av den "itererade produktchiffer"-modellen. Under vissa antaganden har det visats att sammansättningen av flera svaga chiffer (som var och en implementerar svag förvirring och/eller diffusion) kan producera en stark övergripande chiffer, förutsatt att komponenterna är tillräckligt oberoende och antalet rundor är stort. Detta motiverar den iterativa metoden för förvirring och diffusion i praktisk chifferdesign.
Praktiska exempel
Ett lärorikt exempel är substitution-permutation network (SPN)-strukturen, som används av AES. I en SPN utsätts klartexten för alternerande lager av substitution (förvirring) och permutation (diffusion). Efter flera rundor beror varje utmatningsbit på varje inmatningsbit på ett mycket icke-linjärt sätt. Denna egenskap uppnås inte med en enda runda; det är den kumulativa effekten av flera rundor som säkerställer att varje bit av chiffertexten är en komplex funktion av varje bit av klartexten och nyckeln, en egenskap som kallas fullständig diffusion.
Feistel-nätverket, som det används i DES, uppnår liknande säkerhet genom att iterativt tillämpa en rundfunktion som kombinerar substitution och permutation, där utdata från varje runda matas in i nästa. Säkerheten för sådana konstruktioner ökar exponentiellt med antalet rundor, förutsatt att själva rundfunktionen inte är trivialt inverterbar eller linjär.
Slutsats: Säkerhetsberoende av iteration
Blockchifferns styrka är intrikat kopplad till den upprepade tillämpningen av förvirrings- och diffusionsoperationer. Moderna chiffer är utformade med ett tillräckligt antal rundor för att säkerställa att eventuella kvarvarande statistiska samband från klartexten eller nyckeln elimineras, och att varje bit av chiffertexten påverkas av varje bit av klartexten och nyckeln. Denna iterativa process är inte bara en implementeringsdetalj, utan en grundläggande princip för chiffersäkerhet. Antalet rundor väljs baserat på omfattande kryptanalys för att ge en säkerhetsmarginal och omvärderas regelbundet när nya attacker uppstår. I alla praktiska och teoretiska avseenden är säkerheten för blockchiffer verkligen beroende av att kombinera förvirrings- och diffusionsoperationer många gånger.
Andra senaste frågor och svar ang Tillämpningar av blockkoder:
- Vad bör ett blockchiffer innehålla enligt Shannon?
- Betyder diffusion att enskilda bitar av chiffertext påverkas av många bitar av klartext?
- Bryter ECB-läget upp stor indata klartext i efterföljande block
- Kan vi använda ett blockchiffer för att bygga en hashfunktion eller MAC?
- Kan OFB-läge användas som nyckelströmsgeneratorer?
- Kan en inskrivning vara deterministisk?
- Vilka är driftsätten?
- Vad gör ECB-läget med enkla blockchiffer
- Kan PSRNG göras med blockchiffer?
- Kan en MAC byggas med blockchiffer?
Se fler frågor och svar i Tillämpningar av blockchiffer