6

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?

Ali Ahmad
  • 4,784
  • 8
  • 35
  • 61
Nakedible
  • 4,501
  • 4
  • 25
  • 22

1 Answers1

5

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.

D.W.
  • 98,420
  • 30
  • 267
  • 572
  • 1
    "confusion function" is accepted terminology for that function. – Thomas Pornin Jul 07 '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 07 '11 at 20:59
  • @Thomas-Pornin What tools did you use to test, how long did it take? – this.josh Jul 07 '11 at 21:26
  • @Thomas-Pornin Thank you! That was the first actual concrete result given. – Nakedible Jul 08 '11 at 06: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 08 '11 at 09:00
  • @this.josh: I have a DES implementation, that I wrote myself a few years ago, in Java. It features a `desConf()` method which applies the confusion function on a 32-bit input and a 48-bit subkey. Looping through the 2^32 inputs took a couple of minutes; I just "ticked" the obtained values in a big array of 2^32 bits (that's 500 MB, nothing fancy with today's technology). – Thomas Pornin Jul 08 '11 at 12:01