The Magic of the S-Box

The Magic of the S-Box

A substitution box — or S-box — is one of these things used in encryption that many people don’t quite understand. But, they are actually quite simple.

So, let’s look at how AES works. With this, we go through various rounds. For 128-bit AES, this is 10 rounds, and where we use a part of the 128-bit key for each round (Figure 1). Overall, we take a block of 16 bytes and then perform the rounds. These 16 bytes are arranged in a 4x4 matrix. The substitution bytes elements are known as the S-box.

Each round then uses an S-box to scramble the bytes. After the S-box, we shuffle the rows of the 16-byte matrix, and then shuffle the columns. On the decrption part, we just do this in a reverse order and perform a reverse operation.

This is a little like shuffling a deck of cards and then handing someone the shuffled deck. These cards should now look randomly placed. The receiver of the cards — if they have a secret — can then reverse every move of the shuffle to get the cards back in their original place in the deck.

The role of a S-box is key to the encryption process as it hides the operations of the column and the row. In AES, we use an 8x8 matrix to map each of the 16 bytes.

When have the reverse of this S-box in the decryption process:

If we take an input byte of 0x00, this will be mapped to an output byte o 0x52. Then if we look in the table in Figure 3, we see that 0x52 maps back to 0x00, and so we reverse our substitution back.

Reversing the S-box

An S-box does a substitution for one value to another using a lookup table. We can then have a reverse S-box which will map the substitution back to the original value:

To perform the reverse operation, we can use the Sage code of [here]:

import sys
from sage.crypto.sbox import SBox
str=sys.argv[1]
a=eval(str.split(";")[2])
S = SBox(a)
Sinv = S.inverse()

print ("S-Box=",a)
print ("\n\nReverse S-Box")
print ("Inverse S-Box=",Sinv)

Let’s say we have an eight-element S-box:

S-Box= [0, 1, 3, 6, 7, 4, 5, 2]

The inverse of this gives:

Inverse S-Box= (0, 1, 7, 2, 5, 6, 3, 4)

If we try, a data value of d=2:

    2
    |
0 1 3 6 7 4 5 2

Thus, for an input of 2, we get an output of 3. We now need to reverse this, so the value of 3 goes in:

      3
      |
0 1 7 2 5 6 3 4

And, so we get an output value of 2, and thus have reversed the operation. If we try and input of 5, we get:

          5
          |
0 1 3 6 7 4 5 2

The output value is 4. Now we need to reverse back and use the inverse S-box:

        4
        |
0 1 7 2 5 6 3 4

And do we get a value of 5 back again. The code used is [here]:

import sys
from sage.crypto.sbox import SBox
str=sys.argv[1]
a=eval(str.split(";")[2])
try: 
 S = SBox(a)
 Sinv = S.inverse()

 print ("S-Box=",a)
 print ("\n\nReverse S-Box")
 print ("Inverse S-Box=",Sinv)
except TypeError as error:
 print("Error: ",error)

And a sample run [here]:

S-Box= [0, 1, 3, 6, 7, 4, 5, 2]
Reverse S-Box
Inverse S-Box= (0, 1, 7, 2, 5, 6, 3, 4)

and [here]:

...
S-Box= [0, 1, 3, 6, 7, 4, 5, 1]
Error:  S-Box must be a permutation

and [here]:

S-Box= [0, 1, 3, 6, 7, 4, 5, 2, 3]
Error:  Lookup table length is not a power of 2

Weak S-boxes

We need to be very careful with the design of the S-box, as David Coppersmith showed that a weak S-box can reveal information on the encryption process [here]:

Some people worry that some of the S-boxes have been carefully designed, so that the NSA have a backdoor into the encryption process. Up to the current time, no backdoor or weakness has been founded in the AES method.