The Feistel Cipher Structure, Confusion and Diffusion

The rule to remember: confusion is about the KEY, diffusion is about the PLAINTEXT. Students reverse them, and it is the single commonest slip in this topic.

Neither alone is enough. A cipher with confusion and no diffusion leaves the plaintext's patterns intact within each small unit, which is a monoalphabetic cipher. A cipher with diffusion and no confusion moves the patterns around without disguising them, which is a transposition. Alternating the two over many rounds is a product cipher, and it is what every block cipher on this syllabus does.

The proof, performed

The listing below builds a four-round Feistel cipher on a 16-bit block, with a round function that is deliberately not invertible: it throws away the high four bits of its input. Then it encrypts, decrypts, and searches for two inputs to the round function that give the same output.

def f(half, subkey):
    """Not invertible on purpose: the high four bits are thrown away."""
    low = half & 0b00001111
    return (((low * 13) + 7) ^ subkey) & 0xFF

def rounds(left, right, subkeys):
    trace = [(0, left, right)]
    for i, k in enumerate(subkeys, 1):
        left, right = right, left ^ f(right, k)
        trace.append((i, left, right))
    return left, right, trace

def encrypt(block, subkeys):
    left, right = block >> 8, block & 0xFF
    l, r, trace = rounds(left, right, subkeys)
    return ((r << 8) | l), trace

def decrypt(block, subkeys):
    left, right = block >> 8, block & 0xFF
    l, r, trace = rounds(left, right, subkeys[::-1])
    return ((r << 8) | l), trace

SUBKEYS = [0x5A, 0x3C, 0xF0, 0x0F]
plain = 0x1234

cipher, etrace = encrypt(plain, SUBKEYS)
print("plaintext  = %04X" % plain)
print("subkeys    =", " ".join("%02X" % k for k in SUBKEYS))
print()
print("encryption, round by round:")
for i, l, r in etrace:
    print("   after round %d:  L = %02X  R = %02X" % (i, l, r))
print("   swap the halves: ciphertext = %04X" % cipher)
print()
back, dtrace = decrypt(cipher, SUBKEYS)
print("decryption, the SAME rounds with the subkeys reversed:")
for i, l, r in dtrace:
    print("   after round %d:  L = %02X  R = %02X" % (i, l, r))
print("   swap the halves: plaintext = %04X" % back)
print("recovered the plaintext:", back == plain)
print()
print("the round function is NOT invertible. Two different inputs, one output:")
seen = {}
for x in range(256):
    y = f(x, 0x5A)
    if y in seen:
        print("   f(%02X) = f(%02X) = %02X" % (seen[y], x, y))
        break
    seen[y] = x
print("   so a Feistel cipher does not need an invertible round function,")
print("   which is the whole reason the structure exists.")

plaintext  = 1234
subkeys    = 5A 3C F0 0F

encryption, round by round:
   after round 0:  L = 12  R = 34
   after round 1:  L = 34  R = 73
   after round 2:  L = 73  R = 26
   after round 3:  L = 26  R = D6
   after round 4:  L = D6  R = 7C
   swap the halves: ciphertext = 7CD6

decryption, the SAME rounds with the subkeys reversed:
   after round 0:  L = 7C  R = D6
   after round 1:  L = D6  R = 26
   after round 2:  L = 26  R = 73
   after round 3:  L = 73  R = 34
   after round 4:  L = 34  R = 12
   swap the halves: plaintext = 1234
recovered the plaintext: True

the round function is NOT invertible. Two different inputs, one output:
   f(00) = f(10) = 5D
   so a Feistel cipher does not need an invertible round function,
   which is the whole reason the structure exists.

Now read the two traces against each other, because that is the proof.

Encryption produced, in order, the pairs (12, 34), (34, 73), (73, 26), (26, D6), (D6, 7C). Decryption produced (7C, D6), (D6, 26), (26, 73), (73, 34), (34, 12). The second list is the first list read from the bottom up, with each pair swapped. The same rounds, in the same direction, with the subkeys reversed, walked the cipher backwards. Nothing was inverted.

And the round function is provably not invertible: f(00) and f(10) are both 5D, so given 5D you cannot say which input produced it. Yet the cipher decrypts exactly. That is the Feistel property, and the reason for it is worth stating as one sentence: the round function's output is never something you have to undo, it is only something you exclusive-or in, and an exclusive-or is undone by repeating it.

Why it works, in symbols

At round i, encryption computes L(i) = R(i-1) and R(i) = L(i-1) XOR F(R(i-1), K(i)).

To go backwards you need L(i-1) and R(i-1) from L(i) and R(i). Take them in the easy order:

R(i-1) = L(i), directly, because that is what the first equation says.

L(i-1) = R(i) XOR F(R(i-1), K(i)), and you now know R(i-1), so you can compute F again and exclusive-or it out. You never needed to invert F; you only needed to be able to run it forwards on a value you already had.

That is the whole argument, and it is worth five marks on its own.

The parameters of a Feistel cipher

A question asking you to "discuss the design features of a Feistel cipher" wants this list, each with the trade-off.

Block size. Larger means greater diffusion and greater security, and slower. 64 bits was traditional; 128 bits is the modern choice.

Key size. Larger means greater resistance to brute force, and slower. 64 bits was once thought adequate, 56 bits was DES's and is now inadequate, and 128 bits is the modern minimum.

Number of rounds. A single round gives very little; multiple rounds give increasing security. The usual figure is 16. The right number is the one after which no known attack does better than brute force.

Subkey generation algorithm. Greater complexity makes cryptanalysis harder. It must produce a different subkey per round from one master key.

Round function F. Greater complexity makes cryptanalysis harder. This is where confusion lives, and it is the part that is designed rather than chosen.

Two further considerations, which are engineering rather than security.

Fast software encryption and decryption. A cipher is often embedded in an application rather than a chip, so the speed of a software implementation matters.

Ease of analysis. A cipher whose design is easy to explain is easier to argue about, and therefore easier to trust. DES's designers did not publish their reasoning, which is exactly why DES was distrusted for years.

Distinctions that carry marks

That second table is the most useful comparison in this part of the syllabus, because the next two chapters are about DES and the one after is about AES, and their difference is exactly this.

What beginners get wrong here

Swapping confusion and diffusion. Confusion is about the key; diffusion is about the plaintext. Write it down.

Saying the round function must be reversible. It must not be, in the sense that nothing requires it, and DES's S-boxes are not. This is the point of the structure and the thing to say.

Forgetting the final swap. After the last round the halves are swapped before the ciphertext is assembled. Without it, decryption with reversed subkeys does not work, and it is the detail that breaks a hand-worked answer.

Thinking more rounds always means more security. Each round costs time, and past a certain point the gain is nothing because brute force is already the best attack. Sixteen is DES's answer, not a law.

Calling AES a Feistel cipher. It is not. It is a substitution-permutation network, it operates on the whole block each round, and its stages are individually invertible.

Quick revision

• Feistel: L(i) = R(i-1), R(i) = L(i-1) XOR F(R(i-1), K(i)), halves swapped after the last round.
• Decryption is the same algorithm with the subkeys in reverse order.
• The round function need not be invertible: proved in the run, where f(00) and f(10) both gave 5D and the cipher still decrypted.
• Why: R(i-1) = L(i) directly, and then F is recomputed forwards and exclusive-ored out.
• Confusion relates the key to the ciphertext, by substitution. Diffusion relates the plaintext to the ciphertext, by permutation. Shannon, 1949.
• Parameters: block size, key size, number of rounds, subkey algorithm, round function; plus fast software operation and ease of analysis.
• A Feistel cipher works on half the block per round; a substitution-permutation network on the whole block, and its stages must be invertible.
• DES and 3DES are Feistel. AES is not.

Test yourself

1. Write the Feistel round equations and say what happens after the last round. L(i) = R(i - 1) and R(i) = L(i - 1) XOR F(R(i - 1), K(i)). After the last round the two halves are swapped before the ciphertext is assembled.

2. How is a Feistel cipher decrypted? By running exactly the same algorithm on the ciphertext with the subkeys applied in reverse order, so K(n) first and K(1) last, with the same final swap. No separate decryption algorithm is needed.

3. Why does the round function not need to be invertible? Give the argument. Because the round output is combined by exclusive-or rather than substituted in. Going backwards, R(i - 1) is available immediately since it equals L(i); the function can then be recomputed forwards on that value and exclusive-ored out of R(i) to recover L(i - 1). The function is therefore only ever evaluated in the forward direction. The chapter's run confirms it: a round function for which f(00) and f(10) both give 5D still yields a cipher that decrypts exactly.

4. Define confusion and diffusion and say which operation provides each. Confusion makes the relationship between the key and the ciphertext as complex as possible and is provided by substitution. Diffusion spreads the statistical structure of the plaintext across the whole ciphertext, dissipating its redundancy, and is provided by permutation.

5. List the design parameters of a Feistel cipher. Block size, key size, number of rounds, subkey generation algorithm and the round function, with the two further engineering considerations of fast software encryption and decryption, and ease of analysis.

6. Why is a cipher with confusion but no diffusion weak? Give an example. Because the plaintext's statistical structure survives inside each unit that is substituted, so frequency analysis applies. A monoalphabetic substitution cipher is exactly that: the key's effect on each letter is arbitrary, but each letter keeps its own frequency and the cipher falls to counting.

7. Is AES a Feistel cipher? Justify your answer. No. AES is a substitution-permutation network: each round transforms the whole block rather than half of it, and each of its stages is individually invertible, so decryption requires the inverse of each stage rather than the same code with reversed subkeys. A Feistel cipher transforms half the block per round and needs no inverse of its round function.