The Feistel Network

Step through a 16-bit Feistel cipher, one round at a time. Then remove the subkey reversal and watch decryption fail.

FeistelDecryptiondemo

Objectives

Apply one Feistel round to a block by hand and check it against the page.
Explain why the round function does not have to be reversible.
Locate a collision in the round function and say why it costs nothing.
Predict what decryption returns when the subkeys run in the wrong order.
Justify why one implementation serves both directions.

33%

Build a reversible cipher from a round function that does not need to be reversible.

L(i) = R(i-1) and R(i) = L(i-1) XOR F(R(i-1), K(i))
F(R, K) = rot3(S(R XOR K)) XOR S((R XOR K) >> 2)

Plaintext (hex, 16 bits)

reads as 1001 1010 0111 1100

Key (hex, 16 bits)

sample schedule, 8 subkeys

Before round 1

The two halves after this round, with the subkey and the value the round function returned.
Value	Binary	Hex
L, left half	1001 1010	9A
R, right half	0111 1100	7C

The block is split in half. Nothing has been mixed yet.

Where the subkeys come from

The key schedule: the key register after each rotation, and the eight bits of it each round uses.
Round	Key register	Subkey
1	3F5B rotl 3 = FAD9	D9
2	FAD9 rotl 3 = D6CF	CF
3	D6CF rotl 3 = B67E	7E
4	B67E rotl 3 = B3F5	F5
5	B3F5 rotl 3 = 9FAD	AD
6	9FAD rotl 3 = FD6C	6C
7	FD6C rotl 3 = EB67	67
8	EB67 rotl 3 = 5B3F	3F

The sample schedule holds the 16-bit key in a register, rotates it left by three bits each round, and uses the low eight bits as that round's subkey. Real ciphers work harder here, and DES is where that starts.

Inside F

F has not run yet. Press Next round and this card derives the value the round XORs into the left half, line by line.

S-box used inside F

The 4-bit S-box F substitutes each nibble through: the output nibble under each input nibble.
In	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
Out	E	4	D	1	2	F	B	8	3	A	6	C	5	9	0	7

The same box the SPN page uses, applied to both nibbles of the eight-bit half. Every line of F is checkable against it.

Every round so far

Each round: both halves in binary and in hexadecimal, the subkey, and the two equalities the round is defined by.
Round	L	L hex	R	R hex	Subkey	F(R(i-1), K(i))	L(i) = R(i-1)	R(i) = L(i-1) XOR F(R(i-1), K(i))
0	1001 1010	9A	0111 1100	7C

The last two columns are the round definition, written out in hexadecimal so every line can be checked by hand. The first says the new left half is the old right half. The second says the new right half is the old left half XORed with what F returned.

Reading the last row left to right gives C15E, and the ciphertext is 5EC1. The halves are swapped once more after the last round, so the ciphertext is R(8) followed by L(8). That final swap is what lets the same circuit decrypt.

Question: does F have to be reversible? Look at the round function on its own first. The sample F adds the subkey, substitutes, rotates, and folds a shifted copy back in. The fold throws two bits away.

The round function is not reversible

How many inputs the round function has, how many distinct outputs it produces, and one pair of inputs that collide.
Measurement	Value
Inputs	256
Distinct outputs	156
One collision	F(0x20, 0x00) = F(0x30, 0x00) = 0x15

Both numbers are measured with the subkey held at 00, and the count does not depend on that choice: F XORs the subkey in first, so a different subkey renames the inputs and leaves the image size alone. Under the round-1 subkey D9 the same collision reads F(0xF9, 0xD9) = F(0xE9, 0xD9).

It seems that some information is lost, so no inverse of F exists. Can this network still decrypt?

Decryption never inverts F. It computes the same F again and XORs the same value back out. F does not need to be invertible, so the designer has much more freedom, but it should still provide strong non-linearity and mixing. DES is the classic Feistel example.

Decryption runs the same circuit with the subkeys in reverse order. Turn the reversal off and the circuit still runs. It just does not give the plaintext back.

Reverse the subkeys during decryption

Round trip

subkey order used to decrypt

3F676CADF57ECFD9

result

The plaintext, the ciphertext, and what decryption returned.
Value	Binary	Hex
Plaintext	1001 1010 0111 1100	9A7C
Ciphertext	0101 1110 1100 0001	5EC1
How it was assembled	R(8) then L(8)	5E C1
Recovered	1001 1010 0111 1100	9A7C

Original plaintext recovered

Feistel decryption reverses the keys, not the function F, so the same datapath can often be reused for encryption and decryption.

step 1/3

CPE 645 / CS 685

The Feistel Network

The Avalanche Effect

Inside an SPN Round