Return to Answer

Explicit Demonstration: One can choose by hand unequal $X$ and $X'$ so that the expansion map is respected and $S(X\oplus K)=S(X'\oplus K),$ Of course $X\oplus X'=(X \oplus K)\oplus (X\oplus K'),$ and thus this works for all Sboxes, giving a collision for the chosen right halves $(R,R')=(E^{-1}(X),E^{-1}(X'))$. The inputs are listed from $S_1$ to $S_8$:

Explicit Demonstration: One can choose by hand unequal $X$ and $X'$ so that the expansion map is respected and $S(X\oplus K)=S(X'\oplus K),$ Of course $X\oplus X'=(X \oplus K)\oplus (X'\oplus K),$ and thus this works for all Sboxes, giving a collision for the chosen right halves $(R,R')=(E^{-1}(X),E^{-1}(X'))$. The inputs are listed from $S_1$ to $S_8$:

Let us ignore $P$ (as the question points out it's irrelevant) and consider the equivalent map $$\begin{align} f_0:\{0,1\}^{32}\times\{0,1\}^{48}&\to\ \{0,1\}^{32}\\ (R,K)\ &\mapsto f_0(R,K)\underset{\mathsf{def}}=S(E(R)\oplus K)\end{align}$$ where $E$ is the expansion, and $S$ is the parallel application of the DES S-boxes. Define $X:=E(R)$ and focus on $X$. We first show that for arbitrary $K$

TL;DR

It is possible to choose 32 bit right halves $R\neq R’$ for arbitrary 48 bit round key $K$ and obtain $S(E(R)\oplus K)=S(E(R’)\oplus K)$ proving the $F-$ function is never injective.

Explicit Demonstration: One can choose by hand unequal $X$ and $X'$ so that the expansion map is respected and $S(X\oplus K)=S(X'\oplus K),$ Of course $X\oplus X'=(X \oplus K)\oplus (X\oplus K'),$ and thus this works for all Sboxes, giving a collision for the chosen right halves $(R,R')=(E^{-1}(X),E^{-1}(X'))$. The inputs are listed from $S_1$ to $S_8$:

$$ X=({\sf 3Ex|28x|06x|03x|31x|1Dx|17x|3Fx}), $$ $$ X'=({\sf 01x|17x|33x|3Cx|0Ex|2Ex|2Ex|0Cx}), $$ and $$ X'\oplus X=({\sf 3Fx|3Fx|3Fx|3Fx|3Fx|33x|3Fx|33x}). $$ Writing down the bits we get $$ X=(111110|101000|001100|000011|110001|011101|010001|111111) $$ and $$ X'=(000001|010111|110011|111100|001110|101110|101110|001100). $$ Regardless of the key $K$ all the inputs to all the Sboxes can be seen to respect the expansion map.

Detailed Answer:

Let us ignore $P$ (as the question points out it's irrelevant) and consider the equivalent map $$\begin{align} f_0:\{0,1\}^{32}\times\{0,1\}^{48}&\to\ \{0,1\}^{32}\\ (R,K)\ &\mapsto f_0(R,K)\underset{\mathsf{def}}=S(E(R)\oplus K)\end{align}$$ where $E$ is the expansion, and $S$ is the parallel application of the DES S-boxes. Define $X:=E(R)$ and focus on $X$. We first show that for arbitrary $K$

Earlier incomplete answer: (leaving up for now for reference) Let us ignore $P$ (as the question points out it's irrelevant) and consider the equivalent map $$\begin{align} f_0:\{0,1\}^{32}\times\{0,1\}^{48}&\to\ \{0,1\}^{32}\\ (R,K)\ &\mapsto f_0(R,K)\underset{\mathsf{def}}=S(E(R)\oplus K)\end{align}$$ where $E$ is the expansion, and $S$ is the parallel application of the DES S-boxes. Define $X:=E(R)$ and note by additivity that it is enough to prove that for an arbitrary but fixed $K\in\{0,1\}^{48}$

$$\exists X\neq X’ \in{\{0,1\}^{48}}\text{ with }S(X\oplus K)=S(X’\oplus K),$$ provided $X$ and $X'$ are valid expansions of some $R\neq R'\in \{0,1\}^{32}.$

As it is clear from image of the expansion map from Wikipedia here each Sbox shares two (input) bits of $R$ with the Sbox to its left and two bits of $R$ with the Sbox to its right while two bits in the middle are unshared. Therefore $X=(X_1,\ldots,X_48)$ is a valid expansion of $R=(R_1,\ldots,R_{32})$ if $X=E(R),$ i.e., the outer 2 bits input into each Sbox as a result of the expansion are shared between adjacent Sboxes. Thus, we have, e.g. $$ \ldots,X_5=R_4,X_6=R_5,\quad\textrm{in Sbox 1}~(1a) $$ $$ X_7=R_4,X_8=R_5,X_9=R_6,X_{10}=R_7,X_{11}=R_8,X_{12}=R_9,\quad\textrm{in Sbox 2} ~(1b) $$ $$ X_{13}=R_8,X_{14}=R_9,\ldots \quad\textrm{in Sbox 3}~(1c) $$ and so on.

Therefore it will be enough to prove, for arbitrary $K$, that two different vectors $X\neq X'$ obeying relations like $(1a)-(1c)$ above give the same output.

We refer to constraints as in $(1a)-(1c)$ as respecting the expansion $E.$

Since $K$ is arbitrary, and $(X\oplus K)\oplus(X'\oplus K)=X\oplus X':=\Delta X$ if we can find $Y$ and $Y'$ both respecting the expansion $E$ which give the same output when passed through the Sbox layer, i.e., which give $S(Y)=S(Y')$ then the result follows. This is because given an arbitrary $K,$ we would pick $X=Y\oplus K,$ and $X'=X\oplus \Delta X,$ as the two inputs respecting $E$ which give the same output.

Examining the Sbox tables and denoting the input to the $i^{th}$ Sbox as $X_i,$ (respectively $X_i'$) the following two sets of inputs respect $E$ and give the same output.

Input $X=(X_1,\ldots,X_8)$ (throughout rightmost 2 bits of $X_i$ equal leftmost 2 of $X_{i+1}$ as required for respecting $E$)

• $X_1=000000$ which gives output $14;$
• $X_2=001000$ which gives output $6;$
• $X_3=001100$ which gives output $15;$
• $X_4=000000$ which gives output $7;$
• $X_5=000100$ which gives output $4;$
• $X_6=000000$ which gives output $12;$
• $X_7=000011$ which gives output $0;$
• $X_8=111000$ which gives output $15;$

Input $X'=(X'_1,\ldots,X'_8)$ (throughout rightmost 2 bits of $X'_i$ equal leftmost 2 of $X'_{i+1}$ as required for respecting $E$)

• $X'_1=110111$ which gives output $14;$
• $X'_2=110011$ which gives output $6;$
• $X'_3=110011$ which gives output $15;$
• $X'_4=111011$ which gives output $7;$
• $X'_5=111011$ which gives output $4;$
• $X'_6=001011$ which gives output $12;$
• $X'_7=111000$ which gives output $0;$
• $X'_8=000011$ which gives output $15;$

Finally, note that the rightmost two input bits in Sbox 8 match the leftmost two input bits in Sbox 1 for both $X$ and $X'.$

Thus we have proved that the DES $f$ function is not injective.