The S-Box

Build your own four-bit S-box. The page tests whether it is still reversible and still non-linear, then runs the cipher with it.

S-boxNon-linearitydemo

Objectives

Test whether a lookup table is a bijection.
Measure how many output bits one input bit changes.
Apply the XOR test that separates a linear box from a non-linear one.
Explain why a linear S-box leaves the whole cipher linear.
Predict what a duplicated output does to decryption.

33%

Edit the box, then watch the network stop decrypting.

A 4-bit S-box is a lookup table with sixteen entries. Heys' box is loaded. Change any output and every measurement below is recomputed.

The lookup table

in 0

in 1

in 2

in 3

in 4

in 5

in 6

in 7

in 8

in 9

in A

in B

in C

in D

in E

in F

reversible

Every output appears once

output bits changed by one input bit

2.44 of 4 on average, over all 16 inputs and all 4 input bits

Half the output bits is the target, so 2.00 of 4. A box far below that leaves the next round with less to spread. In this SPN the box must also be reversible, and real S-box design considers differential and linear properties as well.

Key addition and bit permutation are both linear, and the S-box provides the non-linearity. The test is whether S(x XOR y) equals S(x) XOR S(y).

How linear is this box?

S(x XOR y) = S(x) XOR S(y) holds for 6 of 256 pairs

Most pairs fail, which is what a designer wants. A linear box would satisfy all of them.

A linear box is still a perfectly good permutation. It is reversible, it passes the bijection test, and the cipher built on it is broken. Reversibility is necessary and it is not sufficient.

Now run the whole SPN with the box as it stands. An SPN inverts every step to decrypt, so it needs the box to be reversible in a way a Feistel round function never does.

What the network is run with

Every input the encryption below uses.
Input	Value
Plaintext	9A7C
Key	3F5B
Rounds	4
Round keys	3F5B EB67 6CFD 9FAD F5B3
S-box	E4D12FB83A6C5907

The key register rotates left five bits between round keys, and the bit permutation is Heys'. Only the S-box row changes when you edit the box above.

Every step, under the box as it stands

The state after every operation of the network, under the current S-box.
Step	State	Hex
plaintext	1001 1010 0111 1100	9A7C
round 1 add key	1010 0101 0010 0111	A527
round 1 substitute	0110 1111 1101 1000	6FD8
round 1 permute	0111 1110 1100 0110	7EC6
round 2 add key	1001 0101 1010 0001	95A1
round 2 substitute	1010 1111 0110 0100	AF64
round 2 permute	1100 0111 1110 0100	C7E4
round 3 add key	1010 1011 0001 1001	AB19
round 3 substitute	0110 1100 0100 1010	6C4A
round 3 permute	0101 1110 1001 0000	5E90
round 4 add key	1100 0001 0011 1101	C13D
round 4 substitute	0101 0100 0001 1001	5419
ciphertext	1010 0001 1010 1010	A1AA

Round trip through the network

The plaintext, the ciphertext under the edited S-box, and what decryption returned.
Value	Binary	Hex
Plaintext	1001 1010 0111 1100	9A7C
Ciphertext	1010 0001 1010 1010	A1AA
Recovered	1001 1010 0111 1100	9A7C

S-box is reversible

This block came back

Every output appears once, so the inverse box exists and every block comes back, not just this one.

step 1/3

CPE 645 / CS 685

The S-Box

Inside an SPN Round

The Brute-Force Baseline