S-Box

Eine S-Box (englisch substitution box) ist eine Komponente von kryptografischen Algorithmen. Sie ersetzt (substituiert) eine Bitfolge durch eine andere.

Eine a×b S-Box ist eine – in der Regel nichtlineare – Substitutionsoperation, bei der eine a-stellige Binärzahl (a-Tupel von Bits) durch eine b-stellige Binärzahl ersetzt wird. Je nach Anwendung kann es notwendig sein, dass diese Abbildung invertierbar (bijektiv) ist.

Verwendung

S-Boxen werden vor allem in Blockverschlüsselungen wie beispielsweise DES und Blowfish eingesetzt, um die Beziehung zwischen Klar- und Geheimtext zu verwischen (in der kryptologischen Fachsprache Konfusion genannt). Eine S-Box trägt auch zur Diffusion bei, da ein eingegebenes Bit im Allgemeinen alle Ausgabebits beeinflusst.

Der DES-Algorithmus verwendet acht verschiedene stark nichtlineare S-Boxen, die für Widerstandsfähigkeit gegen die Differentielle Kryptoanalyse optimiert sind. Auch die Diffusion wird hier vor allem von den S-Boxen erzeugt: Die Änderung eines Input-Bits ändert mindestens 2 Output-Bits, welche dann durch Bitpermutation in der nächsten Runde in verschiedene S-Boxen eingegeben werden.^[1]

Anforderungen

Eine S-Box sollte die folgenden Anforderungen erfüllen:^[2]

• Vollständigkeit: Jedes Ausgangsbit ist von jedem Eingangsbit abhängig.
• Avalanche: Die Änderung eines Eingangsbits zieht im Mittel die Änderung der Hälfte aller Ausgangsbits nach sich.
• Nichtlinearität: Kein Ausgangsbit ist linear oder affin von einem Eingangsbit abhängig. Dies sollte auch nicht näherungsweise der Fall sein.^[3]
• Korrelationsimmunität: Solange nur ein Teil der Eingangsbits bekannt ist, können keine Rückschlüsse auf die Ausgangsbits gezogen werden. Und umgekehrt.

S-Boxen werden meist sorgfältig entworfen, um einer Kryptoanalyse, insbesondere der linearen und der differentiellen Kryptoanalyse, bestmöglich zu widerstehen.

Statisch oder Dynamisch

Man unterscheidet zwischen statischen und dynamischen S-Boxen: Während viele Blockchiffren wie DES oder AES festgelegte (statische) S-Boxen verwenden, initialisieren beispielsweise RC4 und Twofish aus dem Schlüssel die S-Box dynamisch (sogenannte: key-dependent S-box). Statische S-Boxen haben Vorteile bei der Implementierung in Hardware hinsichtlich Geschwindigkeit und Speicherbedarf; dynamische S-Boxen können die Kryptoanalyse erheblich erschweren.

Implementierung

Naheliegend ist die Realisierung als Array mit ${\displaystyle 2^{a}}$ Elementen, deren jedes eine b Bit lange Ausgabe enthält. Die a Eingabebits werden als Zahl interpretiert, die das Array-Element mit der zugehörigen Ausgabe bezeichnet.

Die S-Box kann auch mit booleschen Operationen verwirklicht werden. Die Eingabebits stehen in a Datenwörtern jeweils an der gleichen Bitposition, und die b Ausgabebits werden durch Verknüpfen dieser Datenwörter mit bitweisen Operatoren berechnet. Bei einer Wortbreite von w Bit erfolgen dadurch w Substitutionen parallel. Serpent ist eine Blockverschlüsselung, die für diese Methode ausgelegt ist.

Beispiel

Ein Beispiel ist diese statische 6×4-Bit S-Box (S₅) von DES:

S5		Mittlere 4 Bits des Eingabewertes
		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Äußere Bits	00	0010	1100	0100	0001	0111	1010	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
	01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1010	0011	1001	1000	0110
	10	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

Der Eingabewert ist 6 Bit lang. Der 4-Bit-Ausgabewert steht in der Zeile mit den beiden äußeren Bits und der Spalte mit den 4 inneren Bits des Eingabewertes. Im Beispiel hat der Eingabewert "011011" die äußeren Bits "01" und die inneren Bits "1101". Der zugehörige Ausgabewert ist demnach "1001".

Siehe auch

• Lawineneffekt (Kryptographie).