SP-netwerk
In de cryptografie is een SP-netwerk, of substitutie-permutatienetwerk (SPN), een reeks gekoppelde wiskundige bewerkingen die gebruikt worden in blokcoderingsalgoritmen zoals AES (Rijndael), 3-Weg, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, en Square.
Zo'n netwerk neemt een blok van de platte tekst en de sleutel als invoer, en past verschillende afwisselende "rondes" of "lagen" van substitutieboxen (S-boxen) en permutatieboxen (P-boxen) toe om het cijfertekstblok te produceren. De S-boxen en P-boxen zetten (sub)blokken van invoerbits om in uitvoerbits. Het is gebruikelijk dat deze transformaties efficiënt in hardware worden uitgevoerd, zoals exclusief of (XOR) en bitwise rotatie. De sleutel wordt in elke ronde geïntroduceerd, meestal in de vorm van "ronde sleutels" die ervan zijn afgeleid. (In sommige ontwerpen zijn de S-boxen zelf afhankelijk van de sleutel).
Ontcijfering gebeurt door het proces eenvoudigweg om te keren (met behulp van de inversies van de S-boxen en P-boxen en de ronde toetsen in omgekeerde volgorde aan te brengen).
Een S-box vervangt een klein blokje bits (de invoer van de S-box) door een ander blokje bits (de uitvoer van de S-box). Deze vervanging moet één op één zijn, om de invertibiliteit (dus de ontcijfering) te garanderen. In het bijzonder moet de lengte van de uitgang gelijk zijn aan de lengte van de ingang (het plaatje rechts heeft S-boxen met 4 invoer- en 4 uitvoerbits), wat anders is dan S-boxen in het algemeen die ook de lengte zouden kunnen veranderen, zoals bijvoorbeeld in DES (Data Encryption Standard). Een S-box is meestal niet zomaar een permutatie van de bits. Een goede S-box heeft eerder de eigenschap dat het veranderen van een invoerbit ongeveer de helft van de uitvoerbits verandert (of een lawine-effect). Het zal ook de eigenschap hebben dat elk uitgangsbit afhankelijk is van elk invoerbit.
Een P-box is een permutatie van alle bits: het neemt de uitgangen van alle S-boxen van de ene ronde, permuteert de bits, en voert ze in de S-boxen van de volgende ronde. Een goede P-box heeft de eigenschap dat de uitgangsbits van een willekeurige S-box worden verdeeld over zoveel mogelijk S-box ingangen.
Bij elke ronde wordt de ronde sleutel (verkregen uit de sleutel met enkele eenvoudige handelingen, bijvoorbeeld met behulp van S-boxen en P-boxen) gecombineerd met behulp van een aantal groepsbewerkingen, meestal XOR.
Een enkele typische S-box of een enkele P-box alleen heeft niet veel cryptografische kracht: een S-box zou kunnen worden gezien als een substitutiecode, terwijl een P-box zou kunnen worden gezien als een transpositiecode. Een goed ontworpen SP-netwerk met meerdere afwisselende rondes S- en P-boxen voldoet echter al aan Shannon's verwarrings- en verspreidingseigenschappen:
- De reden voor de verspreiding is de volgende: Als men één bit van de platte tekst verandert, dan wordt deze in een S-box ingevoerd, waarvan de uitgang bij meerdere bits verandert, dan worden al deze veranderingen door de P-box verdeeld over meerdere S-boxen, vandaar dat de uitgang van al deze S-boxen weer bij meerdere bits verandert, enzovoorts. Door verschillende rondes te doen, verandert elk bit meerdere keren heen en weer, waardoor de cijfertekst aan het eind volledig is veranderd, op een pseudorandom manier. In het bijzonder, voor een willekeurig gekozen invoerblok, als men het i-de bit omdraait, dan is de kans dat het j-de uitvoerbit verandert ongeveer de helft, voor elke i en j, wat het strikte Avalanche-criterium is. Omgekeerd, als men een bit van de cijfertekst verandert en vervolgens probeert te ontcijferen, is het resultaat een bericht dat totaal anders is dan de originele plaintext-SP-cijfers zijn niet gemakkelijk te vervormen.
- De reden voor de verwarring is precies dezelfde als voor de verspreiding: het veranderen van een bit van de toets verandert verschillende van de ronde toetsen, en elke verandering in elke ronde toets verspreidt zich over alle bits, waardoor de cijfertekst op een zeer complexe manier verandert.
- Zelfs als een aanvaller op de een of andere manier één klaartekst krijgt die overeenkomt met één cijfertekst - een bekende klaartekst-aanval, of erger nog, een gekozen klaartekst of gekozen cijfertekst-aanval - dan nog maken de verwarring en de verspreiding het moeilijk voor de aanvaller om de sleutel te herstellen.
Hoewel een Feistel netwerk dat gebruik maakt van S-boxen (zoals DES) vrij gelijkaardig is aan SP netwerken, zijn er enkele verschillen die dit of dat meer toepasbaar maken in bepaalde situaties. Voor een bepaalde hoeveelheid verwarring en verspreiding heeft een SP-netwerk meer "inherent parallellisme" en kan dus - gezien een CPU met veel uitvoeringseenheden - sneller worden berekend dan een Feistel-netwerk. CPU's met weinig uitvoeringseenheden - zoals de meeste smartcards - kunnen niet profiteren van dit inherente parallellisme. Ook SP-cijfers vereisen dat S-boxen inverteerbaar zijn (om decodering uit te voeren); Feistel-binnenfuncties hebben een dergelijke beperking niet en kunnen als eenrichtingsfuncties worden geconstrueerd.
