S-box

In cryptografie is de S-box (substitutiebox) een basiscomponent van cijfersystemen die substitutie uitvoeren. In blokcijfers worden ze vaak gebruikt om de overeenkomsten van de sleutel en de cijfertekst te verbergen. Een goede s-box zorgt voor Shannons eigenschappen van verwarring en diffusie. Deze eigenschappen zorgen voor non-lineairiteit wat essentieel is zodat een encryptiealgoritme bestand is tegen lineaire cryptoanalyse. Wiskundig gezien is een S-box een niet-lineaire vectoriële Booleaanse functie.

Normaal gesproken neemt een S-box een gegeven aantal invoerbits m, en transformeert deze in een aantal uitvoerbits n, waarbij n niet even veel bits hoeft te zijn als m. Een m × n S-box kan worden geïmplementeerd als een tabel met 2m woorden van elk n bits. Dus stel dat m=8 bits en n=8 bits dan krijg je 256 woorden van 8 bits ofwel 1 byte. De S-box zou dan dus een tabel met 16 rijen en 16 kolommen worden.

Normaal gesproken worden tabellen gebruikt met een vaste grootte, zoals in de Data Encryption Standard (DES) of de Advanced Encryption Standard (AES), maar in sommige codes worden de tabellen dynamisch gegenereerd tijdens het proces op basis van de sleutel (bijvoorbeeld de Blowfish- en Twofish-encryptie-algoritmen).

Voorbeeld

Een voorbeeld van een vaste tabel is een van de S-boxen van DES (S-box5), die 6-bits invoer omzet in een 4-bits uitvoer:

S5 Middelste 4 bits van de invoer
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Buitenste 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

Gegeven 6 bits als invoer, worden de 4 output bits gevonden door de buitenste twee bits en binnenste vier bits van de invoer te nemen. Dat houdt in dat een input van 011011 als buitenste bits 0 en 1 heeft (011011) en als binnenste vier bits 1101 (011011). Als men de buitenste en binnenste bits van de invoer nu invult in de S-box (zoals in de tabel hierboven uitgelicht) krijgt men daaruit de 4 output bits, in dit geval 1001.

Analyse en eigenschappen

Toen DES in 1977 voor het eerst werd gepubliceerd, werden de ontwerpcriteria van de S-boxen geheim gehouden om te voorkomen dat de techniek van differentiële cryptoanalyse (die toen nog niet publiekelijk bekend was) bekend zou worden. Als gevolg hiervan was er destijds weinig onderzoek gedaan naar hoe een goede S-box in elkaar zit. De acht S-boxen van DES werden daarentegen jarenlang intensief bestudeerd uit bezorgdheid dat er een achterdeur (een kwetsbaarheid die alleen bekend was bij de ontwerpers) in de code zou zijn geplant door de NSA.

Ze werden hiervan verdacht aangezien de maker van DES (IBM) niet de ontwerpcriteria wou geven en de NSA de S-boxen aangepast zou hebben teruggegeven nadat IBM ze naar Washington had verzonden. Later bleek dat de NSA in plaats van het verzwakken van de S-boxen hun juist sterker had proberen te maken tegen differentiële cryptoanalyse. Omdat de S-boxen het enige niet-lineaire deel van de code vormen, zou het compromitteren daarvan de hele code in gevaar brengen.

De S-box-ontwerpcriteria werden uiteindelijk gepubliceerd door Don Coppersmith na de publieke herontdekking van differentiële cryptoanalyse, waaruit bleek dat ze zorgvuldig waren afgestemd om de weerstand tegen deze specifieke aanval te vergroten, zodat deze niet beter was dan een brutekrachtaanval op de sleutel. Biham en Shamir ontdekten dat zelfs kleine aanpassingen aan een S-box DES significant konden verzwakken.

S-boxen kunnen worden geanalyseerd met behulp van lineaire cryptoanalyse en differentiële cryptoanalyse in de vorm van een lineaire benaderingstabel (LAT) of Walsh-transformatie en een Difference Distribution Table (DDT) of autocorrelatietabel en spectrum. De sterkte ervan kan worden bepaald door de niet-lineariteit (gebogen, bijna gebogen) en differentiële uniformiteit (perfect niet-lineair, bijna perfect niet-lineair).

Zie ook

Bronnen

  1. ↑ Daemen & Rijmen 2013, p. 22.
  2. ↑ Chandrasekaran, J. (2011). Advances in Networks and Communications: First International Conference on Computer Science and Information Technology, CCSIT 2011, Bangalore, India, January 2-4, 2011. Proceedings, Part 2. Springer, 'A Chaos Based Approach for Improving Non Linearity in the S-box Design of Symmetric Key Cryptosystems', p. 516. ISBN 978-3-642-17877-1.
  3. ↑ Buchmann, Johannes A. (2001). Introduction to cryptography, Corr. 2. print.. Springer, New York, NY [u.a.], '5. DES', 119–120. ISBN 978-0-387-95034-1.
  4. ↑ Schneier, Bruce. Applied Cryptography (2nd ed.), p. 280. ISBN 9780471128458.
  5. ↑ Schneier, Bruce, Saluting the data encryption legacy (27 september 2004). Geraadpleegd op 28 oktober 2025.
  6. ↑ Coppersmith, D. (May 1994). The Data Encryption Standard (DES) and its strength against attacks. IBM Journal of Research and Development 38 (3): 243–250. ISSN: 0018-8646. DOI: 10.1147/rd.383.0243.
  7. ↑ Coppersmith, Don (1994-5-31). The Data Encryption Standard (DES) and its strength against attacks. Gearchiveerd op 25 maart 2009. IBM Journal of Research and Development. 1994 (Volume 38): 243–250
  8. ↑ Heys, Howard M., A Tutorial on Linear and Differential Cryptanalysis.
  9. ↑ S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography. doc.sagemath.org. Geraadpleegd op 30 april 2021.
  10. ↑ (en) Saarinen, Markku-Juhani O. (2012). Selected Areas in Cryptography. Springer, Berlin, Heidelberg. DOI:10.1007/978-3-642-28496-0_7, 'Cryptographic Analysis of All 4 × 4-Bit S-Boxes', 118–133. ISBN 978-3-642-28496-0.

Andere bronnen