SP-võrk (substitutsioonipermutatsioonivõrk) krüptograafias — definitsioon

SP-võrk (substitutsioonipermutatsioonivõrk) krüptograafias: selge ülevaade S- ja P-kastidest, vooruvõtmetest ja AES-st – mõistmiseks ja rakendamiseks.

SP-võrk ehk substitutsioonipermutatsioonivõrk (SPN) on krüptograafias kasutatav arhitektuur plokkšifreeringute loomiseks. SP-võrk koosneb mitmest vahelduvast kihist, kus asenduskastid (S-kastid) ja permutatsioonikastid või muud lineaarset tüüpi kihid (P-kastid / segavad kihid) töötlevad sisendploki bitte, ning igas voorus segatakse tulemust võtmega. Levinud näited SP-võrkudel põhinevatest šifritest on AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK ja Square.

Kuidas SP-võrk töötab

SP-võrk võtab sisendiks lihtteksti ploki ja võtme. Krüpteerimine toimub mitme vooru kaupa: igas voorus rakendatakse tavaliselt järjekorras

• võtme segamine (või rongi-/vooruvõtme lisamine, tavaliselt XOR),
• S-kastid — lokaalsed asendused väikeste bittide plokkide kohta,
• P-kast või lineaarne kiht — bittide permutatsioon või muu lineaarne segamine, mis levitab S-kastide väljundeid järgmise vooru sisenditesse.

S-kastide (S-box) omadused ja disainikriteeriumid

S-kast on funktsioon, mis asendab väikese bittide ploki (näiteks 4- või 8-bitti) teise plokiga. SP-võrgus kasutatakse tavaliselt inverteeritavaid S-kaste (bijektiivne funktsioon), et oleks võimalik dekrüpteerida. Hea S-kasti disain nõuab:

• Inverteeritavust — et krüpteeritud andmed oleks võimalik tagasi pöörata;
• Kõrget mitte-lineaarsust — et vähendada lineaar- ja algebraatiliste rünnakute efektiivsust;
• Väikest differentseeruvat ühtlust (differential uniformity) — et vähendada diferentseerrünnakute edu tõenäosust;
• Avagaadi- ja SAC-omadusi — ühe sisendbiti muutus peaks mõjutama umbes pool väljundbitte (laviini efekt), ning iga väljundbit peaks sõltuma kõigist sisendbititest;
• Madalat algebrailist astet — et takistada lihtsate algebraatiliste lähenemiste kasutamist.

Praktilised näited: AES kasutab 8×8-bitiset bijektiivset S-kasti, mis on hoolikalt disainitud mitte-lineaarsuse ja diferentseeruvaltomaduste osas. Kergkaalulistes šifrites (nt PRESENT) kasutatakse sageli väiksemaid 4×4 S-kaste, mis on ruumi- ja energiakulude tõttu eelistatud.

P-kastide ja lineaarsete kihtide roll

P-kast ehk permutatsioonikiht levitab S-kastidest tulenevat teavet üle kogu ploki: see paigutab bittide asukohad ümber või rakendab laiemalt lineaarset transformatsiooni (näiteks mitmemõõtmeline maatriks, nagu AES-i MixColumns). Hea P-kast tagab, et ühe S-kasti väljundbittide mõju jaotub võimalikult paljude järgmise vooru S-kastide sisenditele, parandades hajutamist (diffusion).

Mõned SP-võrgud kasutavad lihtsat P-kasti (puhtalt bitipermutatsioon), teised kombineerivad permutatsiooni ja lineaarsed segamised (MDS-maatriksid), et saavutada suuremat haru numbrit ja paremat hajutust väikese vooru arvu juures.

Võtme kasutamine ja dekrüpteerimine

Iga voor kasutab tavaliselt vooruvõtit, mis on tuletatud peavõtmest võtmeplaneerimise ehk key schedule'i abil. Vooruvõtme segamine teostatakse sageli XOR-iga. Dekrüpteerimine toimub protsessi ümberpööramisega: rakendatakse S-kastide ja lineaarsete kihtide inversioone ning vooruvõtmeid kasutatakse vastupidises järjekorras. Seega peavad S-kastid ja lineaarne kiht olema inverteeritavad (või kokkuvõttes šifri teisendused pööratavad), et tagada korrektne dekrüpteerimine.

Turvalisus: segadus, hajutus ja rünnakud

SP-võrk on loodud realiseerima Claude Shannoni kahte põhikontseptsiooni:

• Hajutus (diffusion) — üks lihtteksti bit mõjutab lõpuks mitmeid salateksti bitte; P-kastid ja lineaarne segamine aitavad selle saavutada. Põhimõtteliselt muutub ühe sisendbiti muutus pärast mitut vooru paljude väljundbittide väärtuseks juhuslikult (laviini efekt); see on seotud ka SAC-iga (Strict Avalanche Criterion).
• Segadus (confusion) — keeruline sõltuvus võtme ja salateksti vahel; S-kastide mitte-lineaarsus ning mitmekordne võtme segamine iga vooru käigus suurendavad segadust.

Tavapärased analüüsimeetodid, millega disainerid arvestavad, on diferentseerrünnak (differential cryptanalysis) ja lineaarne rünnak (linear cryptanalysis). S-kasti omadused ning P-kasti (või lineaarse kihi) branch number ja struktuur määravad, mitu vooru on vajalik, et rünnakud muutuksid ebaefektiivseks. Kui SP-võrk on korralikult disainitud ja forumi piisavalt palju fürusid rakendatud, siis isegi teada-tuntud lihtteksti-salateksti paaride olemasolul (known-plaintext) või valitud lihtteksti rünnakute puhul on võtme leidmine keeruline.

Rakendused, jõudlus ja praktilised kaalutlused

SP-võrgud pakuvad head loomulikku paralleelsust: mitmed S-kastid töötlevad sama vooru eri plokiosi samaaegselt, mis teeb need sobivaks riistvaraseks ja SIMD-kiirendusega tarkvaraliseks rakendamiseks. Mõned kaalutlused:

• Riistvaras saab SP-võrku sageli väga kiiresti implementeerida, kasutades paralleelset loogikat;
• Vähese riistvariga seadmetes (näiteks smart-kaardid) ei pruugita paralellisest disainist palju kasu olla;
• S-kastide tabelipõhised (lookup table) implementeerimised võivad olla haavatavad küljeinfoviidete (side-channel) nagu vahemälu- või ajastuslekete suhtes; sellepärast kasutatakse mõnikord bitsliced- või constant-time-tehnikaid;
• Võtmeplaneerimine ehk key schedule võib oluliselt mõjutada turvalisust: nõrk või liigse korrelatsiooniga võtme tuletamine võib anda ründajatele eelise.

Võrdlus Feisteli võrguga

Feisteli võrk (nt DES) kasutab teisiti organiseeritud voorufunktsiooni ja ei nõua, et iga vooru sisemine funktsioon oleks inverteeritav — seega on võimalik kasutada ühesuunalisi (non-invertible) konstruktsioone. Peamised erinevused:

• SP-võrgud nõuavad inverteeritavaid S- ja P-kihti (või kokkuvõttes pööratavat struktuuri) dekrüpteerimise jaoks; Feisteli võrgus piisab, et poolfunktsioon ja ringistruktuur võimaldavad tagasiarvutamist ilma ühefunktsiooni invertsuseta.
• SP-võrkude loomulik paralleelsus teeb need tihti kiiremad protsessorites ja riistvaras, kus paralleelsust saab ära kasutada;
• Feisteli võrk võib olla paindlikum mõningates disainides (nt lihtsam konstruktsioon ühesuunaliseks hashinguks või muudeks ärilist eesmärkidel).

Kokkuvõte

SP-võrk on tugev ja laialt kasutatav plokkšifrite arhitektuur, mis kombineerib lokaalset mitte-lineaarset asendust (S-kastid) ja globaalseid permutatsioonilisi või lineaarseid segamiskihte (P-kastid). Turvalisus sõltub S-kastide omadustest, lineaarse kihi disainist, võtmeplaneerimisest ja piisavast voorude arvust, et takistada tuntud krüptanalüütilisi rünnakuid. Praktilises maailma on SP-võrgud levinud nii suure jõudlusega süsteemides (nagu AES) kui ka kergkaalulistes skeemides (nagu PRESENT), sõltuvalt disainilisi nõuetest ja ressursipiirangutest.

Otsing