Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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