S-Box
# S-Box

In der Kryptografie bezeichnet eine S-Box (englisch substitution box) eine Grundkomponente symmetrischer Kryptosysteme.

## Verwendung

Eine m×n S-Box ist eine – in der Regel nichtlineare – Substitutionsoperation, bei der eine m-stellige Binärzahl durch eine n-stellige Binärzahl ersetzt wird. Sie kann beispielsweise mit einer Tabelle implementiert werden, die $2^m$ Zellen enthält. Je nach Anwendung kann es notwendig sein, dass diese Abbildung invertierbar (im Sinne von bijektiv) ist.

S-Boxen werden in Blockverschlüsselungen wie beispielsweise DES und Blowfish eingesetzt, um die Beziehung zwischen Klar- und Geheimtext zu verwischen (in der kryptologischen Fachsprache Konfusion genannt).

Der DES-Algorithmus verwendet acht verschiedene S-Boxen, die auch teilweise das Shannon’sche Prinzip der Diffusion umsetzen. Dies kann einfach nachvollzogen werden: Die Änderung eines Input-Bits ändert mindestens 2 Output-Bits. Dieses Verhalten liegt im Design der S-Boxen. Bei vollständiger Diffusion hingegen wäre das Strict Avalanche Criterion (SAC) erfüllt und die Änderung eines Input-Bits würde jedes Output-Bit mit der Wahrscheinlichkeit von 0,5 ändern.

S-Boxen müssen sehr sorgfältig entworfen werden, um einer Kryptoanalyse, insbesondere der linearen und der differentiellen Kryptoanalyse zu widerstehen.

## Anforderungen

Eine S-Box sollte die folgenden Anforderungen erfüllen:

* 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.
* Korrelationsimmunität: Solange nur ein Teil der Eingangsbits bekannt ist, können keine Rückschlüsse auf die Ausgangsbits gezogen werden. Und umgekehrt.

## 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 $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_5)$ von DES:

| $S_5$ | $S_5$ | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes | Mittlere 4 Bits des Eingabewertes |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| $S_5$ | $S_5$ | 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 |
| Äußere Bits | 01 | 1110 | 1011 | 0010 | 1100 | 0100 | 0111 | 1101 | 0001 | 0101 | 0000 | 1111 | 1010 | 0011 | 1001 | 1000 | 0110 |
| Äußere Bits | 10 | 0100 | 0010 | 0001 | 1011 | 1010 | 1101 | 0111 | 1000 | 1111 | 1001 | 1100 | 0101 | 0110 | 0011 | 0000 | 1110 |
| Äußere Bits | 11 | 1011 | 1000 | 1100 | 0111 | 0001 | 1110 | 0010 | 1101 | 0110 | 1111 | 0000 | 1001 | 1010 | 0100 | 0101 | 0011 |

Hier wird ein Eingabewert mit 6-Bit angenommen. Der 4-Bit-Ausgabewert ergibt sich durch die Zeile mit den beiden äußeren Bits und die 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 wäre demnach "1001".

