Is it possible for two different half-block inputs to the DES F-function, with the same round subkey, to produce the same output?

That is, if we feed two different half-block inputs $b_1$ and $b_2$ through the expansion stage, XOR them with a constant subkey $K$, and then pass the expanded and XORed inputs through the S-boxes, is it possible for the outputs $o_1 = F(b_1, K)$ and $o_2 = F(b_2,K)$ to be equal?


Yes, it can; within the DES round function, two different 'right side' inputs can, after the sboxes, come up with the same value to xor into the 'left side'.

This was a deliberate decision by the DES designers, who thought that this was an important property. I don't know their reasoning about why they thought it was important.


A decade or so ago I wrote something to explore what values could be produced by f(R,K) for a particular key.

eightbox -K c034a483 -E c034a485 K=11XX00_00XX00_00XX11_01XX00_10XX10_01XX00_10XX00_00XX11 S=c04212b2 B=5a02d23ca0a1 S[1-8]Row=0,2,1,0,1,0,0,3 1 S=c04212b2 B=553c7a3ca0a1 S[1-8]Row=1,1,3,2,1,0,0,3 2 S=c04212b2 B=ca02d23ca15f S[1-8]Row=2,2,1,0,1,0,1,1 3 K=11XX00_00XX00_00XX11_01XX00_10XX10_01XX00_10XX00_01XX00 S=c04212b2 B=5a02d23ca142 S[1-8]Row=0,2,1,0,1,0,1,0 1 S=c04212b2 B=553c7a3ca142 S[1-8]Row=1,1,3,2,1,0,1,0 2 K=11XX00_00XX00_00XX11_01XX00_10XX10_01XX00_10XX00_01XX01 S=c04212b2 unused 1 loops = 3, unused = 1, maxused = 3

The value B is the 48 input to the eight S boxes comprised of E(R) xor K.

The command line arguments to eightbox represent the starting key and ending key for the 32 bits of key influencing S box inputs affected by shared R bits due to the Expansion permutation.

eighbox takes a candidate range of sbox outputs (S, in this case a single value 0xc04212b2) and a range of key values for the shared E(R) bits and determines the input values (B) that can produced S.

For the three candidate key values we get 3, 2 and 0 output values for S=c04212b2 (a default target single S box output).

It tells us not only can we have duplicate f(R,K) outputs for a fixed K, but some S box outputs are not possible for some values of K.

The remaining 16 bits of K have no other dependencies than the value of unshared R bits. Setting those K values further restricts the value of R to one possibility for each candidate value of B.

The knowledge is of limited usefulness because we can't see the S Box outputs directly, instead requiring things like Differential Cryptanalysis and it's three round deterministic, dependent on the number of shared K bits between rounds.

So yes it's possible to satisfy the criteria outputs o1=F(b1,K) and o2=F(b2,K) to be equal as the above proves. (And proofs are nice.)

There's sufficient information in the above to produce an entire 48 bit K value and matching R values for the 'collisions'. I don't think I've seen more than 8 different R values producing the same S output, I'd have to dig through any collected data to check or re-run over a range of S and/or K values. I may not have printed out the K value previously, I had to enable it for the above.


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.