Substitūcijas–permutācijas tīkls (SPN) — kriptogrāfijas definīcija

Substitūcijas–permutācijas tīkls (SPN) skaidrojums: SPN arhitektūra, S-box, P-box, raundi un loma modernajos blokšifros (AES, Kalyna) — pamati un drošības principi.

Kriptogrāfijā SP tīkls jeb substitūcijas-permutācijas tīkls (SPN) ir determinēta virkne saistītu matemātisku operāciju, ko izmanto daudzu mūsdienīgu blokķīfu konstrukcijās — piemēram, AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK un Square. SPN shēma pārveido ievaddatus (atklātā teksta bloku) par šifrētu bloku, izmantojot vairākus tā dēvētos raundus, kuros tiek lietotas aizvietošanas (S-box) un permutācijas (P-box) transformācijas, kā arī raundu atslēgas.

Kā darbojas SP tīkls

Tipiskā SPN struktūra atkārto vairākus raundus; katrā raundā parasti veic:

• vietējas ne-lineāras aizvietošanas operācijas (S-boxes),
• globālas bitu permutācijas vai lineāras difūzijas slāņus (P-boxes vai lineārās transformācijas),
• atslēgas agregāciju (parasti ar XOR) ar raunda atslēgu.

Atslēga tiek izmantota katrā raundā — parasti no galvenās atslēgas tiek ģenerētas raunda atslēgas ar atslēgu derivācijas (key schedule) algoritmu. Dažās konstrukcijās S-kastes var būt atkarīgas no atslēgas (t.s. key-dependent S-boxes).

S-kastes (S-box)

S-box aizstāj nelielu bitu bloku (S-box ieeja) ar citu bitu bloku (S-box izeja). SPN parasti prasa, lai S-kaste būtu invertējama (bijektīva), jo dešifrēšanai jāizmanto S-kastes inversija; tas atšķir SPN no, piemēram, Feistela tīkla, kur S-veida funkcijas invertējamība nav obligāta. Tomēr citos šifros (piem., DES) S-kastes var mainīt bitu skaitu (DES S-kastes: 6 bitu ieeja -> 4 bitu izeja).

Labi izstrādāta S-kaste mēģina nodrošināt:

• augstu nenelinearitāti (lai pretotos lineārajai kriptoanalīzei),
• zemu diferenciālo uniformitāti (lai samazinātu diferencālās kriptoanalīzes efektivitāti),
• stingro lavīnas kritēriju (Strict Avalanche Criterion, SAC) — ja mainās viens ieejas bits, aptuveni puse izejas bitu mainās),
• labu atkarību starp ieejas un izejas biti (katrs izejas bits atkarīgs no katra ieejas bita).

P-kastes un lineārā difūzija

P-box parasti nozīmē bitu permutāciju vai plašāku lineāru transformāciju, kas sadala S-kastes izejas starp nākamā raunda S-kastēm, tā nodrošinot difūziju. Modernās SPN konstrukcijās P-kastes bieži realizē ar bloku lineāru transformāciju (piem., AES MixColumns), kuras kvalitāti mēra ar tā saukto branch number — lielāks skaitlis nozīmē labāku difūziju pret dažādiem uzbrukumiem.

Raundi, atslēgas un šifrēšana/dešifrēšana

Katrā raundā raunda atslēga (bieži iegūta no galvenās atslēgas ar atslēgu plānošanas algoritmu) tiek apvienota ar starptautas datiem, parasti ar XOR. Lai dešifrētu, procesu vienkārši apgriež: lieto S-kastes un P-kastes inversijas (vai atbilstošas inversās lineārās transformācijas) un pielieto raunda atslēgas apgrieztā secībā.

Parasto SPN dizainā ir noteikts raundu skaits — vairāk raundu parasti palielina drošību pret diferencālo un lineāro kriptoanalīzi, bet palielina izpildes laiku. Piemēram, AES izmanto 10, 12 vai 14 raundus atkarībā no atslēgas garuma.

Sajaukšana (confusion) un difūzija (diffusion)

Labi noformēts SP tīkls realizē Kloda Šenona principus par sajaukšanu un difūziju:

• Difūzija. Ja tiek mainīts viens atklātā teksta bits, S-kaste vietējā līmenī izmaina vairākus bitus; P-kaste šīs izmaiņas sadala starp daudzām S-kastēm nākamajā raundā, un pēc vairākiem raundiem viena lokāla izmaiņa izplatās pa visu bloku. Galarezultātā katra izejas bitu var mainīties aptuveni ar varbūtību 1/2 attiecībā pret jebkuru ieejas bitu (lavīnas efekts), padarot šifrtekstu pseido‑nejaušu.
• Sajaukšana (apjukums). Izmaiņas atslēgā, pat vienā bitā, caur S-kastēm un difūzijas slāņiem ātri noved pie ļoti sarežģītām un grūti prognozējamām izmaiņām šifrtekstā, tādējādi slēpjot atslēgas un atklātā teksta attiecības.

Pat ja uzbrucējs iegūst zināmu atklātā teksta/šifrteksta pāri (uzbrukumi ar zināmu atklātā teksta, izvēlētu atklātā teksta vai izvēlētu šifrteksta modeli), spēcīga sajaukšana un difūzija apgrūtina atslēgas atgūšanu bez milzīgiem resursiem.

Drošības un dizaina kritēriji

SPN drošumu ietekmē vairāki faktori:

• S-kastes kriptogrāfiskās īpašības — nenelinearitāte, diferencālā uniformitāte, algebraiskā pakāpe;
• difūzijas slāņa kvalitāte (piem., branch number vai permutācijas izplatība);
• raundu skaits un atslēgu plānošanas drošība (key schedule);
• kopējā struktūras izturība pret pazīstamajiem uzbrukumiem: lineārā un diferenciālā kriptoanalīze, integrācijas (integral) uzbrukumi, algebraiskie uzbrukumi u.c.

Moderni dizaina rīki un matemātiskie rādītāji palīdz izvērtēt S- un P-bloku kvalitāti, lai nodrošinātu, ka SPN pretoties visdažādāko uzbrukumu tipiem.

Salīdzinājums ar Feistela tīkliem

Feistela tīkls (piemēram, DES) izmanto S-veida iekšējas funkcijas, bet to kopējā struktūra ļauj konstruēt ne-invertējamas iekšējās funkcijas, jo visas operācijas kopā kļūst invertējamas pateicoties Feistela shēmai. SPN savukārt prasa invertējamas S-kastes, lai veiktu dešifrēšanu tieši ar inversajām transformācijām.

Dažas praktiskas atšķirības:

• SPN parasti nodrošina lielāku paralelizāciju (S-kastes var apstrādāt vienlaicīgi), tāpēc mūsdienu procesoros vai aparatūrā to var paātrināt. Tas noder ātriem programmatūras vai aparatūras ievieojumiem. Savukārt Feistela tīklam ir citāda paralelizācijas un caurlaides rakstura ierobežojumi, kas dažkārt labvēlīgāki ierobežotas jaudas ierīcēm (piem., daudām viedkaršu arhitektūrām).
• SPN prasībai pēc invertējamām S-kastēm ir savas konsekvences dizainā; Feistela konstrukcija piedāvā elastību S-funkciju izvēlē, jo tiek garantēta kriptētās funkcijas invertējamība bez nepieciešamības tiešai S-kastes inversijai.

Praktiski piemēri

• AES (Rijndael): klasisks SPN piemērs, kur S-kaste darbojas pa baitu līmenim (8 → 8 biti), bet difūziju nodrošina MixColumns un ShiftRows lineārā permutācija; atkarībā no atslēgas garuma izmanto 10/12/14 raundus.
• PRESENT: viegls SPN šifrs ar nelielām S-kastēm (4 → 4 biti), paredzēts ierobežotas jaudas ierīcēm.
• Kuznyechik un Kalyna: mūsdienu blokķīfi ar SPN elementiem, izmantoti attiecīgos reģionālajos standartos.

Noslēgumā

Substitūcijas–permutācijas tīkls ir plaši izmantota un labi pētīta arhitektūra blokķifos. Pareizi izstrādāts SPN nodrošina spēcīgu sajaukšanu un difūziju, izturību pret daudzām kriptoanalīzes metodēm un efektīvu īstenošanu gan aparatūrā, gan programmatūrā. Tomēr drošs reālas lietošanas SPN prasa rūpīgu S- un P-bloku dizainu, adekvātu raundu skaitu un drošu atslēgu plānošanu.

Meklēt pēc burta