SP-Netzwerk

In der Kryptographie ist ein SP-Netzwerk oder Substitutionspermutationsnetzwerk (SPN) eine Reihe von verknüpften mathematischen Operationen, die in Blockchiffrieralgorithmen wie AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK und Square verwendet werden.

Ein solches Netzwerk nimmt einen Block des Klartextes und des Schlüssels als Eingabe und wendet mehrere abwechselnde "Runden" oder "Schichten" von Substitutionsboxen (S-Boxen) und Permutationsboxen (P-Boxen) an, um den Chiffriertextblock zu erzeugen. Die S-Boxen und P-Boxen wandeln (Unter-)Blöcke von Eingabebits in Ausgabebits um. Es ist üblich, dass es sich bei diesen Transformationen um Operationen handelt, die in Hardware effizient durchzuführen sind, wie z. B. exklusive oder (XOR) und bitweise Rotation. Der Schlüssel wird in jeder Runde eingeführt, gewöhnlich in Form von "runden Schlüsseln", die daraus abgeleitet werden. (Bei einigen Designs hängen die S-Boxen selbst vom Schlüssel ab).

Die Entschlüsselung erfolgt durch einfache Umkehrung des Prozesses (mit den Inversen der S-Boxen und P-Boxen und Anwendung der runden Schlüssel in umgekehrter Reihenfolge).

Eine S-Box ersetzt einen kleinen Block von Bits (den Eingang der S-Box) durch einen anderen Block von Bits (den Ausgang der S-Box). Diese Substitution sollte eins zu eins erfolgen, um die Invertierbarkeit (also die Entschlüsselung) zu gewährleisten. Insbesondere sollte die Länge des Ausgangs gleich der Länge des Eingangs sein (das Bild rechts zeigt S-Boxen mit 4 Eingangs- und 4 Ausgangsbits), was sich von S-Boxen im allgemeinen unterscheidet, die ebenfalls die Länge ändern können, wie z.B. bei DES (Data Encryption Standard). Eine S-Box ist normalerweise nicht einfach eine Permutation der Bits. Vielmehr hat eine gute S-Box die Eigenschaft, dass die Änderung eines Eingangsbits etwa die Hälfte der Ausgangsbits ändert (oder einen Lawineneffekt). Sie hat auch die Eigenschaft, dass jedes Ausgabebit von jedem Eingabebit abhängt.

Eine P-Box ist eine Permutation aller Bits: sie nimmt die Ausgaben aller S-Boxen einer Runde, permutiert die Bits und speist sie in die S-Boxen der nächsten Runde ein. Eine gute P-Box hat die Eigenschaft, dass die Ausgangsbits einer beliebigen S-Box auf möglichst viele S-Box-Eingänge verteilt werden.

Bei jeder Runde wird der Rundenschlüssel (der mit einigen einfachen Operationen, z.B. mit S-Boxen und P-Boxen, aus dem Schlüssel gewonnen wird) mit Hilfe einer Gruppenoperation, typischerweise XOR, kombiniert.

Eine einzelne typische S-Box oder eine einzelne P-Box allein hat nicht viel kryptographische Stärke: eine S-Box könnte man sich als Substitutions-Chiffre vorstellen, während man sich eine P-Box als Transpositions-Chiffre vorstellen könnte. Ein gut konzipiertes SP-Netzwerk mit mehreren abwechselnden Runden von S- und P-Boxen erfüllt jedoch bereits Shannons Verwirrungs- und Diffusionseigenschaften:

• Der Grund für die Diffusion ist der folgende: Ändert man ein Bit des Klartextes, so wird dieser in eine S-Box eingespeist, deren Ausgabe sich um mehrere Bits ändert, dann werden alle diese Änderungen von der P-Box auf mehrere S-Boxen verteilt, so dass die Ausgaben aller dieser S-Boxen wiederum um mehrere Bits verändert werden, und so weiter. Bei mehreren Runden ändert sich jedes Bit mehrmals hin und her, so dass sich der Geheimtext am Ende auf pseudozufällige Weise vollständig verändert hat. Insbesondere wenn man bei einem zufällig gewählten Eingabeblock das i-te Bit umdreht, dann beträgt die Wahrscheinlichkeit, dass sich das j-te Ausgabebit ändert, für jedes i und j ungefähr die Hälfte, was das Strenge Lawinenkriterium ist. Umgekehrt, wenn man ein Bit des Chiffriertextes ändert und dann versucht, ihn zu entschlüsseln, ist das Ergebnis eine Nachricht, die völlig anders ist als der ursprüngliche Klartext - SPS-Chiffren sind nicht leicht formbar.
• Der Grund für die Verwirrung ist genau derselbe wie bei der Diffusion: Die Änderung eines Bits des Schlüssels verändert mehrere der runden Schlüssel, und jede Änderung in jedem runden Schlüssel diffundiert über alle Bits und verändert den Chiffriertext auf sehr komplexe Weise.
• Selbst wenn ein Angreifer auf irgendeine Weise einen Klartext erhält, der einem Chiffretext entspricht - ein Angriff mit bekanntem Klartext oder schlimmer noch, ein ausgewählter Klartext oder ein ausgewählter Chiffretext - erschweren Verwirrung und Verbreitung dem Angreifer die Wiederherstellung des Schlüssels.

Obwohl ein Feistel-Netzwerk, das S-Boxen (wie DES) verwendet, den SP-Netzwerken recht ähnlich ist, gibt es einige Unterschiede, die dieses oder jenes in bestimmten Situationen besser anwendbar machen. Für ein gegebenes Maß an Verwirrung und Diffusion hat ein SP-Netzwerk mehr "inhärente Parallelität" und kann daher - bei einer CPU mit vielen Ausführungseinheiten - schneller berechnet werden als ein Feistel-Netzwerk. CPUs mit wenigen Ausführungseinheiten - wie die meisten Smartcards - können diese inhärente Parallelität nicht ausnutzen. Auch SP-Chiffren erfordern, dass S-Boxen invertierbar sind (um die Entschlüsselung durchzuführen); innere Feistel-Funktionen haben keine solche Einschränkung und können als Einwegfunktionen konstruiert werden.

Suche nach Buchstaben