bits.

FREE HISTORICAL FIGURES OF COMPUTING PROFILE

Horst Feistel

1915–1990 · Cryptographer

Horst Feistel

Cryptographer · 1915–1990 · Germany and United States

Horst Feistel helped develop block-cipher designs at IBM that influenced DES and a wider family of ciphers. The structure named after him offers a useful mathematical separation: a whole encryption round can be invertible even when its internal round function is not. That is an architectural property. It is not a proof that an arbitrary choice of round function produces secure encryption.

A documented design within a team history

IBM's account places Feistel at the head of a cryptography research group associated with Lucifer. NIST's history identifies a wider DES team, including Walter Tuchman, Alan Konheim, Don Coppersmith, Carl Meyer, and Mike Matyas. It describes Tuchman's role in the final DES algorithm. Calling DES simply Feistel's personal cipher loses this distinction. IBM research history, NIST DES history

Feistel's Block cipher cryptographic system patent was filed on 30 June 1971 and granted on 19 March 1974. The patent documents a technical design and its legal chronology. It does not establish that every later block cipher uses its architecture. AES, for example, is specified through substitutions, row shifts, column mixing, and round-key addition rather than the conventional two-half Feistel round developed below. Patent US3798359A, AES specification

Worked mechanism: invertibility without inverting F

Split a block into equal-width halves L and R. With a round key K, define:

L' = R

R' = L XOR F(R, K)

The output contains the old R directly as L'. Therefore the inverse is:

R = L'

L = R' XOR F(L', K)

This works because XORing the same bit string twice cancels it. There is no need to compute an inverse of F. F must produce the correct number of bits and be evaluated consistently with the same key; its own mapping may be many-to-one.

Here is an original toy calculation using four-bit halves. It is deliberately insecure and is not DES or Lucifer. Let F(R,K) = (R + K) mod 16, start with (L,R) = (6,9), and use keys 3 then 5. In round 1, F is 12, whose binary form is 1100. Since 0110 XOR 1100 = 1010, the new pair is (9,10). Round 2 computes F as 15 and 9 XOR 15 = 6, giving (10,6).

To reverse the last round, recover R=10 and L=6 XOR F(10,5)=6 XOR 15=9, so the preceding pair was (9,10). Reverse the first round: R=9 and L=10 XOR F(9,3)=10 XOR 12=6. The original (6,9) returns exactly.

Descriptions that say decryption merely reverses the keys must specify the input/output swapping convention. The explicit inverse above is unambiguous. A network reusing the forward-round form needs the appropriate boundary swaps as well as reversed round keys.

Invertibility is weaker than security

Take F(R,K)=0 for every input and key. Every round just swaps the halves. Two rounds return the plaintext unchanged. This is perfectly invertible and completely useless for secrecy. Adding more rounds does not rescue that particular construction: an even number is the identity, and an odd number is a visible swap.

An attacker should not be able to predict useful relationships between plaintext and ciphertext without the key. A cipher must also resist attacks that exploit many observations, not only appear scrambled in one example. In particular, an avalanche experiment that changes one input bit is a diagnostic, not a security proof. A public, easily inverted linear transformation can change many output bits and still reveal all plaintext.

DES uses 64-bit blocks, 56 effective key bits, and 16 rounds. Its S-boxes provide nonlinear substitutions. Coppersmith's 1994 designer account describes IBM's knowledge of differential cryptanalysis during design and the criteria used against it. The history therefore cannot responsibly be reduced to an unsupported story that NSA alone invented, weakened, or strengthened every relevant feature. NIST history, Coppersmith's paper

NIST withdrew FIPS 46-3 in 2005. DES is useful here as a historical and mathematical case study, not as a recommendation for protecting new systems. NIST withdrawal record

A block cipher is not a complete communication protocol

Even an ideal block cipher maps an identical plaintext block to an identical ciphertext block under a fixed key. A protocol needs a specified mode of operation, handling of nonces or initialization values where required, and an integrity mechanism. Encryption alone does not prove that a received message was created by an authorized sender or that it is fresh.

This is a general design lesson, not a retrospective claim that Feistel's early system implemented today's authenticated-encryption interfaces. Distinguish the permutation, its implementation, the surrounding protocol, and the operational key-management system. A correct proof about one layer cannot substitute for evidence about the others.

Exercises

  1. Trace and reverse. In the four-bit toy construction, start at (3,12) with keys 7 then 2. Compute both rounds and decrypt using the explicit inverse. Explain why addition modulo 16 and XOR must not be interchanged.
  2. Prove the boundary. Show algebraically that a Feistel round is invertible even when F(R,K)=R AND K. Then set K to zero for every round and explain why this family can still be insecure. What claim has the algebra proved, and what claim has it not proved?
  3. Critique a source claim. An article says: “A patent proves Feistel invented all modern encryption; 16 rounds guarantee security; the same design became AES.” Identify the unsupported inference in each clause. Name the kind of evidence needed to replace each clause with an accurate statement.
Compare your reasoning with the worked solutions
  1. First, F(12,7)=3, so (3,12) becomes (12,3 XOR 3)=(12,0). Next, F(0,2)=2, giving (0,12 XOR 2)=(0,14). Reverse round 2: R is 0 and L is 14 XOR 2=12. Reverse round 1: R is 12 and L is 0 XOR 3=3. Modular addition carries between bit positions; XOR does not. For example, 3+3 mod 16=6 whereas 3 XOR 3=0. Confusing these operations would change the cipher being analyzed.
  2. Given output (a,b), the unique input is (b XOR (a AND K),a). Substituting this input into the round recovers (a,b) because (a AND K) cancels itself under XOR. With K=0, F is zero and the network reduces to swaps, regardless of how many rounds are advertised. The proof establishes a permutation for each fixed key. It gives no computational bound against an adversary and no useful secrecy guarantee for this family.
  3. A patent documents specified claims at a particular date; priority and influence require comparison with earlier work and later designs. A round count must be evaluated together with the round function, key schedule, attack model, and cryptanalysis; the zero-function counterexample refutes a universal guarantee. The AES specification directly supplies a different structure. An accurate replacement would identify the documented patent, Feistel's influence on DES, and the actual assumptions behind any cited security result, without extending those statements to all encryption.

Sources and further study