The DES symmetric cipher is based on a Feistel network operating repeated on 32-bit halves of the 64-bit block. The usage of Feistel means that the "mangler" function used does not need to be invertible.

The "mangler" function operates by expanding a 32-bit word to 48-bits via a simple algorithm. This 48 bits is the combined with a key and then converted back to 32-bits via S-boxes. The S-boxes obviously are not invertible, because they take a 6-bit input and produce a 4-bit output.

But is the entire construction invertible. Assuming the key is fixed, does each 32-bit input to the "mangler" function map to a distinct 32-bit output? Or are some 32-bit outputs never produced by the mangler function hence making it non-invertible?


No, it is not invertible. It is possible to find two 32-bit inputs that, when fed to the DES "mangler" function, both produce the same 32-bit output. This is one of the benefits of the Feistel structure: the "mangler" function does not need to be invertible, and we still end up with an invertible block cipher.

In fact, Biham and Shamir's famous differential cryptanalysis attack on DES makes important use of this fact. They take advantage of the fact that, when a pair of 32-bit inputs satisfy a certain relationship, then they often produce the same output after applying the "mangler" function. This enables them to find a differential characteristic with relatively high probability, which lets them attack DES. The differential cryptanalytic attack on DES is not really practical, but it was a tremendous advance in the science of cryptanalysis and block cipher design.

P.S. By the way, I've never heard a cryptographer call this function a "mangler" function. I've typically heard it called a Feistel F function. So, if you walk up to a cryptographer and ask them about the DES "mangler" function, they might give you a funny look; now you know how to talk their language.

| improve this answer | |
  • 1
    "confusion function" is accepted terminology for that function. – Thomas Pornin Jul 7 '11 at 20:58
  • 2
    I have just tried: with an all-zero 48-bit subkey, only 68.13% of 32-bit values are possible as output of the confusion function. – Thomas Pornin Jul 7 '11 at 20:59
  • @Thomas-Pornin What tools did you use to test, how long did it take? – this.josh Jul 7 '11 at 21:26
  • @Thomas-Pornin Thank you! That was the first actual concrete result given. – Nakedible Jul 8 '11 at 6:18
  • @D.W. Thanks! The differential cryptanalysis paper actually explains all the specifics about the mapping, including the varying probabilities for the different outputs. – Nakedible Jul 8 '11 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.