# How can an S-Box be reversed?

So, as an exercise to greater understand some things about cryptography, I decided to try and implement GOST 28147-89, which uses eight 4x4 S-Boxes. I can grasp the concept of putting 4 bits through the S-Box and getting four out, but how would one reverse this?

Furthermore, how would one reverse uneven S-Boxes, such as DES's 6x4 S-Box, when multiple inputs give the same output (e.g., for DES's S-Box S5, where inputs of 100011, 101110, 011101, and 010000 all give an output of 1000).

## 1 Answer

Ciphers that use S-boxes are typically in the form of a Feistel network. This has the property that inverting the cipher does not involve inverting the round function, but simply applying the rounds in the opposite order. Therefore one doesn't need to invert the S-box to decrypt.

• I think you should make it clear that S-boxes often ARE invertible. For instance, the S-box in AES is invertible. @Liam Inverting S-boxes can be very easy: you simply create a lookup table that reverse all the possible substitutions of the S-box. E.g. if the S-box maps 0xA5 to 0x3F (this would be an 8x8 S-box), then the inverse transformation would map 0x3F to 0xA5. Thus, you simply enumerate all the possible values the S-box can have, and create an inverse table that "undoes" all those transformations (this effectively limits how large the S-boxes can be in practice). – hakoja Feb 16 '13 at 15:54
• @hakoja Why does invertability restrict size in practice? – Paul Uszak Aug 29 '17 at 14:59