Substituční-permutační síť (SPN): definice a princip v kryptografii
Substituční‑permutační síť (SPN) v kryptografii: principy S‑boxů a P‑boxů, lavinový efekt, použití v AES a dalších blokových šifrách. Přehled a vysvětlení.
V kryptografii je síť SP (substitučně-permutační síť, zkráceně SPN) konstrukce složená ze střídajících se vrstev substitucí (S-boxů) a permutací/difuzních lineárních vrstev (P-boxů). SPN se používá v mnoha moderních blokových šifrách, například v AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK nebo Square.
Základní princip
SPN přijme jako vstup blok otevřeného textu a použitý klíč. Šifra provádí několik opakovaných kol; typické kolo se skládá z:
- substituční vrstvy (S-boxy) — nelineární transformace malých bloků bitů,
- difuzní/permutační vrstvy (P-box nebo jiná lineární transformace) — rozptyl bitů mezi různými S-boxy,
- aplikace klíče kola, většinou pomocí XOR (tzv. AddRoundKey).
Po posledním kole může následovat ještě závěrečná klíčová mřížka (round key). Dešifrování se provádí inverzním postupem: použijí se inverzní S-boxy a inverzní lineární transformace a kruhové klíče v opačném pořadí.
S-box: co to je a jaké požadavky má
S-box nahrazuje malý blok bitů jiným blokem stejné délky (u invertibilních SPN musí být S-box bijekce). Důležité vlastnosti dobře navrženého S-boxu:
- bijektivita (pro možnost dešifrování),
- vysoká nelinearita (snižuje účinnost lineární kryptanalýzy),
- nízká diferenciální uniformita (odolnost proti diferenciální kryptanalýze),
- vysoké algebraické stupně výstupních funkcí,
- lavinové chování: změna jednoho vstupního bitu by měla ovlivnit přibližně polovinu výstupních bitů.
Příkladem je S-box AES: jedná se o 8×8 bijekci konstruovanou jako Inverze v konečném poli GF(2^8) následovaná afinní transformací — tato volba dává dobrý kompromis nelinearity a implementační efektivity.
P-box a lineární difuze
P-box obvykle permutuje bity po výstupu S-boxů tak, aby výstupy jednoho S-boxu byly rozptýleny do mnoha různých S-boxů v dalším kole. Místo jednoduché permutace může být použita lineární transformace s dobrými difuzními vlastnostmi (např. MDS matice nebo MixColumns v AES). Důležité kritérium je tzv. branch number (počtová síla difuze): vyšší branch number znamená rychlejší šíření změn napříč blokem.
Kruhové klíče a rozšiřování klíče
V každém kole se do stavového bloku vkládá klíč kola, obvykle XORem. Klíče kol jsou odvozeny z hlavního klíče pomocí rozšiřovacího algoritmu (key schedule). Kvalitní rozšiřování by mělo zajistit, aby i malá změna hlavního klíče vedla k výrazné změně klíčů kol (lavinový efekt) a minimalizovat symetrie, které by umožnily útoky jako slidové útoky nebo útoky meet-in-the-middle.
Shannonovy principy: zmatení a rozptyl
Dobře navržená SPN splňuje Shannonovy principy:
- Difúze (diffusion): změna jednoho bitu vstupu se postupně rozprostře přes S- a P-vrsty tak, že po několika kolech ovlivní značnou část výstupu.
- Zmatení (confusion): nelineární S-boxy zajistí, že vztah mezi klíčem a šifrovým textem je složitý a ne přímo lineární.
Tato kombinace ztěžuje útočníkům rekonstrukci klíče i při známosti některých otevřených textů a odpovídajících šifrových textů.
Bezpečnostní úvahy a typy útoků
I když jediný S-box nebo P-box sám o sobě nemusí být bezpečný, adekvátní počet kol a dobře zvolené S- a P-vrstvy odolávají běžným metodám kryptanalýzy. Mezi hlavní útoky proti SPN patří:
- diferenciální kryptanalýza — řeší se volbou S-boxů s malou diferenciální uniformitou a dostatečným počtem kol,
- lineární kryptanalýza — snižuje se vysokou nelinearitou S-boxů,
- integrační útoky (např. Square attack) — návrh difuzní vrstvy a počet kol se volí tak, aby jim odolával,
- útoky založené na slabém rozšiřování klíče — dobrý key schedule je kritický,
- postranní kanálové útoky (side-channel) — implementace by měla být odolná (constant-time, ochrana před snoopingem paměti apod.).
Výpočet bezpečného počtu kol pro konkrétní SPN bývá výsledkem analýzy vůči výše uvedeným útokům; u standardních šifer (např. AES) je počet kol stanoven konzervativně.
SPN versus Feistelova síť
SPN a Feistelova síť jsou dvě hlavní paradigmata konstrukce blokových šifer. Hlavní rozdíly:
- Paralelismus: SPN typicky umožňuje větší inherentní paralelismus (všechny S-boxy v jedné vrstvě lze zpracovat současně), což je výhoda na moderních procesorech a hardware. Feistelova síť často zpracovává části sekvenčně.
- Inverzibilita S-boxů: u SPN musí být S-boxy invertibilní (pro dešifrování). U Feistela může být vnitřní funkce neinvertibilní, protože struktura Feistela sama zajišťuje možnost dešifrování.
- Implementační aspekty: Feistelova konstrukce může být užitečná tam, kde je obtížné konstruovat efektivní bijektivní S-boxy nebo když je žádoucí jednodušší inverze interních funkcí.
Příklad: AES jako SPN
AES (Rijndael) je typický příklad moderní SPN, i když používá kombinaci operací, které je možné považovat za S- a P-vrsty:
- SubBytes: v každém bytu se aplikuje 8×8 S-box (nelineární),
- ShiftRows: permutace (posuny řádků) — jednoduchá transpozice,
- MixColumns: lineární MDS transformace (silná difuze),
- AddRoundKey: XOR se subklíčem.
AES používá 10, 12 nebo 14 kol podle délky klíče (128, 192 nebo 256 bitů) a navržené vrstvy společně poskytují vysokou odolnost proti známým typům útoků.
Implementace a praktické poznámky
Při implementaci SPN je třeba zvážit:
- bezpečnost proti postranním kanálům — vyhnout se přístupům do tabulek závislým na tajném klíči (cache-timing attacks), použít bitslice nebo constant-time implementace,
- optimalizace pro hardware — jednoduché S-boxy a lineární vrstvy lze efektivně realizovat v ASIC/FPGA,
- paměťová/rychlostní optimalizace — table-based implementace (lookup table) versus bit-slice přístup,
- správné generování a uchovávání klíčů kol, aby se předešlo slabinám key schedule.
Závěr
Substitučně-permutační sítě jsou flexibilní a efektivní konstrukcí pro blokové šifry. Klíč k jejich bezpečnosti spočívá v pečlivém návrhu S-boxů, silné lineární difuzi (P-vrstva), robustním rozšiřování klíče a dostatečném počtu kol. Správná implementace navíc musí brát v úvahu praktická rizika, zejména postranní kanály.
Vyhledávání