DES f function injective for no fixed subkey? Let $f$ be the function used in a round of DES, as defined in FIPS&nbsp;46-3:
$$\begin{align}
f:\{0,1\}^{32}\times\{0,1\}^{48}&amp;\to\ \{0,1\}^{32}\\
(R,K)\ &amp;\mapsto f(R,K)\underset{\mathsf{def}}=P(S(E(R)\oplus K))\end{align}$$
where $E$ is the expansion, $S$ is the combination of S-boxes, and $P$ is the permutation.

Prove or disprove:

$$\forall K\in\{0,1\}^{48},\ \exists R,R'\in{\{0,1\}^{32}}\text{ with }f(R,K)=f(R',K)\text{ and }R\ne R'$$

or equivalently: the DES $f$ function is injective for no fixed subkey.



The answer is independent of $P$, because a permutation is injective, and injective functions compose. It depends on $S$ and $E$. If it is trivial for those of DES, I missed it.



Inspired by the question DES F function never injective?, where the OP intends never to mean if we change the S-boxes, a possibility that we disregard.
First thing to observe is that a DES-like confusion function can be a permutation, depending on the contents of the S-boxes. DES S-boxes are formally defined as $6\rightarrow 4$ functions, with the leftmost and rightmost bits selecting a row, which itself defines a $4\rightarrow 4$ function applied on the four central bits of the input. This last function is, in DES, a permutation (over the space of 4-bit strings). If we change S-boxes such that all these $4\rightarrow 4$ permutations are the identity function, then, for subkey $0$, the whole confusion function is the identity, which is bijective. Therefore, we must take into account the exact definition of the S-boxes in DES, since the answer will depend on that.

Some notations:


We number bits from left to right, starting at 1 on the left (this is the notation used in the DES specification).
Subkey is $K$ and has length 48 bits.
We consider the function $f(K,R)$ for a 48-bit subkey $K$ and 32-bit input $R$. This is the DES confusion function, with the expansion step, but without the permutation $P$.


We can observe that changing bits 3 of the subkey does not change the injectivity status of the function: if there are two inputs $R$ and $R'$ such that $R \neq R'$ and $f(K, R) = f(K, R')$, then $f(K \oplus M_1, R \oplus M_2) = f(K \oplus M_1, R' \oplus M_2)$ for masks $M_1 = 2^{45}$ (i.e. bit 3 is set, all other bits are cleared) and $M_2 = 2^{30}$ (i.e. bit 2 is set, all other bits cleared). This applies to all bits $6j+3$ and $6j+4$, for $0 \leq j \leq 7$.

Similarly, if we flip both bit 5 and 7 of $K$, the injectivity status of the function is not changed: the assertion above stands for $M_1 = 2^{43}+2^{41}$ and $M_2 = 2^{28}$. This applies to all pairs of bits $6j+b \bmod 48$ and $6j+b+2 \bmod 48$ for $0 \leq j \leq 7$ and $b \in \{5,6\}$.

Using these two facts, we can say that $f$ is be injective for a subkey $K$ if and only if it is injective for subkey $K'$ such that:


$k'_i = k_i$ if $i \bmod 6 = 1$ or $2$;
$k'_i = 0$ otherwise.


Thus, if we want to check things exhaustively, we only have $2^{16}$ possible subkeys $K'$ to investigate.

At that point, I made a small program which tries all subkeys $K'$, using Floyd's cycle detection algorithm to find a collision. The program is written in C and can be found there. On my laptop, this program takes on 66 seconds to go through all possible $K'$, and finds a collision for each one.

Therefore, assuming that this program is correct (you can check the collisions, there are "only" 65536 of them), and modulo the epistemological reservations that some mathematicians have about computer-assisted proofs, one can say that it is proven that the DES confusion function is never a permutation, for any possible subkey $K$.