# Is the DES F-function injective for a given subkey?

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?

## 2 Answers

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.