Substitúčno-permutačná sieť (SPN) v kryptografii — definícia a príklady
SPN v kryptografii: jasná definícia, fungovanie S-box a P-box, príklady (AES, Kuznyechik), bezpečnosť a dešifrovanie. Praktické vysvetlenie pre študentov a vývojárov.
V kryptografii je sieť SP alebo substitúčno-permutačná sieť (SPN) sekvencia prepojených matematických operácií používaná v mnohých moderných blokových šifrách, napríklad v AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK a Square. SPN transformuje blok otvoreného textu pomocou opakujúcich sa kôl, v ktorých sa striedajú netriviálne substitučné prvky (S-boxy) a permutačné prvky (P-boxy), pričom do každej vrstvy vstupuje tiež kľúč (kľúč kola).
Ako SPN funguje
Sieť prijíma blok otvoreného textu a kľúč ako vstupy a vykoná niekoľko kôl. Každé kolo typicky obsahuje:
- aplikáciu S-boxov — nelineárnych substitučných funkcií na malé (pod)bloky bitov,
- permutačnú vrstvu (P-box) — ktorá premiešava bity medzi jednotlivými S-boxmi,
- pridanie kľúča kola (AddRoundKey) — obyčajne pomocou XOR operácie.
Výsledkom je blok šifrového textu; dešifrovanie sa vykoná obrátením procesu, teda použitím inverzií S- a P-vrstiev a aplikovaním kruhových kľúčov v opačnom poradí.
S-box (substitučné pole)
S-box nahrádza malý blok bitov iným blokom bitov. Aby bola transformácia vratná (invertovateľná), musí byť S-box zvyčajne bijektívny (jeden na jedného) a so stejnou dĺžkou výstupu ako vstupu (napríklad 4→4 alebo 8→8 bity). Dobrý S-box má niekoľko dôležitých vlastností:
- vysoká nelinearita — ťažko aproximovateľný lineárnymi funkciami (odolnosť voči lineárnej kryptanalýze),
- nízka diferenciálna uniformita — malé pravdepodobnosti konkrétnych rozdielov na vstupe spôsobujú očakávateľné rozdiely na výstupe (odolnosť proti diferenciálnej kryptanalýze),
- lavínový efekt — zmena jedného vstupného bitu mení približne polovicu výstupných bitov,
- každý výstupný bit závisí na každom vstupnom bita.
S-boxy preto neposkytujú samotné veľkú bezpečnosť, ale sú kľúčovým zdrojom nelinearity v SPN.
P-box (permutačné pole)
P-box je permutácia bitov, ktorá rozptyľuje bity medzi S-boxmi nasledujúceho kola. Cieľom P-boxu je dosiahnuť difúziu: bity, ktoré sa zmenia na výstupe jedného S-boxu, by mali byť rozdelené tak, aby ovplyvnili čo najviac rôznych S-boxov v ďalšom kole. Dobrý P-box maximalizuje prekryv vstupov a výstupov medzi S-boxmi, aby sa zmeny rýchlo rozšírili po celom stave šifry.
Kľúč a kľúčový rozvrh (key schedule)
V každom kole sa používa kľúč kola, ktorý sa odvádza z hlavného kľúča pomocou key schedule (generovania kruhových kľúčov). Zvyčajnou operáciou zoskupenia kľúča s položkami stavu je XOR, ale v key schedule sa môžu využiť aj ďalšie transformácie vrátane S-boxov, permutácií či aritmetických operácií. Kvalitný key schedule zabezpečí, že malá zmena v hlavnom kľúči ovplyvní všetky kruhové kľúče a tým aj výsledný šifrový text.
Shannonove vlastnosti: difúzia a zmätok
Dobre navrhnutá SPN spĺňa Shannonove požiadavky na difúziu a zmätok:
- Difúzia: Zmena jedného bitu otvoreného textu sa cez S-boxy a P-boxy počas niekoľkých kôl rozšíri tak, že výsledný šifrový text sa javí pseudonáhodný. Pre náhodne zvolený vstupný blok, ak sa otočí i-ty bit, pravdepodobnosť, že sa zmení j-ty výstupný bit, sa pri dostatočnom počte kôl blíži 1/2 — to je praktické lavínové kritérium.
- Zmätok (confusion): Zmena jedného bitu kľúča ovplyvní viacero kruhových kľúčov a cez difúziu sa táto zmena prejaví zložito na celom výsledku, čím sa komplikuje priame odhalenie vzťahu medzi kľúčom a šifrovým textom.
- Spolu tieto vlastnosti sťažujú útočníkovi rekonštrukciu kľúča, aj keď má k dispozícii páry otvorený text — šifrový text (útok známym otvoreným textom), alebo dokonca možnosť zvoliť otvorený text (útok zvoleným otvoreným textom).
Konštrukčné poznámky a odporúčania
- Počet kôl: musí byť dostatočný, aby zabezpečil úplnú difúziu a odolnosť proti diferenciálnej a lineárnej kryptanalýze; napríklad AES používa 10, 12 alebo 14 kôl v závislosti od dĺžky kľúča.
- Veľkosť S-boxov: často 4×4 alebo 8×8; menšie S-boxy sú jednoduchšie implementovať v hardvéri, väčšie môžu poskytnúť silnejšiu lokálnu nelinearitu.
- Nelinearita a algebraická zložitosť: S-boxy by mali mať vysokú algebraickú zložitosť, aby sa zabránilo algebraickým útokom.
- Implementačná bezpečnosť: dizajn by mal brať do úvahy bočné kanály (side-channel) — napr. tabuľkové implementácie S-boxov sú rýchle, ale náchylnejšie na útoky meraním spotreby energie alebo časovania; techniky ako bitslicing a maskovanie zvyšujú odolnosť.
Príklady SPN v praxi
- AES (Rijndael): používa 8×8 S-box, permutačné prvky realizované ako kombinácia ShiftRows a MixColumns a pridanie kľúča cez XOR. AES je SPN s výrazným paralelizmom a dobre vyváženým dizajnom pre softvérovú aj hardvérovú implementáciu.
- PRESENT: je minimalistická ľahká SPN pre zabudované zariadenia; používa 4×4 S-box a jednoduchú bitovú permutáciu, pričom je optimalizovaný pre nízke hardvérové náklady.
- Kuznyechik, Kalyna: moderné blokové šifry s SPN konštrukciou používané alebo navrhnuté v rôznych štandardoch (napr. ruské štandardy); kombinujú S-boxy, lineárne vrstvy a robustný key schedule.
Porovnanie so Feistelovou sieťou
Feistelova sieť a SPN sú príbuzné konštrukcie, ale majú rozdielne vlastnosti:
- Feistelove šifry (napr. DES) rozdeľujú stav na dve polovice a v každom kole aplikujú nelineárnu funkciu len na jednu polovicu, potom ju skombinujú s druhou; pri dešifrovaní stačí použiť opačné poradie kľúčov bez nutnosti invertovania vnútorných S-boxov.
- SPN má väčší "vrodený paralelizmus" — všetky S-boxy v jednom kole sa dajú spracovať súbežne, čo je výhodné na modernom hardvéri s viacerými vykonávacími jednotkami; na druhej strane vyžaduje invertovateľné S-boxy pre dešifrovanie.
- Feistelova konštrukcia umožňuje použiť jednosmerné vnútorné funkcie, preto sa návrh S-boxov s prísnou invertibilitou nie je taký obmedzujúci ako v SPN.
Bezpečnostné hrozby a útoky
Bezpečnosť SPN závisí od kvality S-boxov, P-boxov, počtu kôl a key schedule. Migrácia útokov, ktoré treba brať do úvahy:
- diferenciálna a lineárna kryptanalýza — hlavné formy útokov na blokové šifry, ktorým možno čeliť rozsiahlym počtom kôl a starostlivým návrhom S-boxov a permutácií,
- algebraické útoky — ak je možné vyjadriť šifru jednoduchým systémom polynómových rovníc, môže to viesť k zraniteľnostiam; preto sa minimalizuje algebraická štruktúra S-boxov,
- bočné kanálové útoky (side-channel) — útoky z merania spotreby, elektromagnetického vyžarovania či časovania; návrh implementácie musí používať ochranné techniky (maskovanie, constant-time implementácie),
- útoky s použitím vybraného otvoreného textu alebo šifrového textu — návrh by mal minimalizovať možnosti získania výraznej informácie o kľúči z takýchto útokov.
Zhrnutie
Substitúčno-permutačná sieť je univerzálna a dobre pochopená konštrukcia blokových šifier, ktorá dosahuje bezpečnosť kombináciou nelineárnych S-boxov a difúznych P-boxov spolu s pevne navrhnutým key schedule a dostatočným počtom kôl. Jej silné stránky zahŕňajú vysoký paralelizmus a dobrú teoretickú oporu (Shannonova difúzia a zmätok), pričom implementačné a bezpečnostné detaily (S-boxy, permutácie, odolnosť voči bočným kanálom) rozhodujú o praktickej bezpečnosti konkrétnej šifry.
Prehľadať