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 2m 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.[1] 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:[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.
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 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 (S5) 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 | |
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".
Einzelnachweise
- ↑ Don Coppersmith: The Data Encryption Standard (DES) and its strength against attacks. In: International Business Machines Corporation (Hrsg.): IBM Journal of Research and Development. Band 38, Nr. 3, 3. Mai 1994, S. 247, Absch. Design Criteria Nr. S-4 (simson.net [PDF]): „If two inputs to an S-box differ in exactly one bit, the outputs must differ in at least two bits.“
- ↑ Walter Fumy, Hans Peter Rieß: Kryptographie: Entwurf und Analyse symmetrischer Kryptosysteme. Oldenbourg, München / Wien 1988, ISBN 3-486-20868-3.
- ↑ Bruce Schneier: Applied Cryptography. Protocols, Algorithms and Source Code in C. 2. Auflage. John Wiley & Sons, New York 1996, ISBN 0-471-11709-9, S. 349–350.