DES f function injective for no fixed subkey?

Question

Let $f$ be the function used in a round of DES, as defined in FIPS 46-3: $$\begin{align} f:\{0,1\}^{32}\times\{0,1\}^{48}&\to\ \{0,1\}^{32}\\ (R,K)\ &\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.

Answer 1

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$.

Answer 2

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$

$$\exists X\neq X’ \in{\{0,1\}^{48}}\text{ with }S(X\oplus K)=S(X’\oplus K).$$

We then show that the way we obtain $X$ and $X’$ is compatible with both of the following equations holding simultaneously $$ X=E(R)\quad and \quad X’=E(R’) $$ for some $R,R’\in \{0,1\}^{32}.$ Thus there are valid right halves $R,R’$ which can be used to demonstrate that $f$ is not injective for any key $K.$ 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.$

Consider the difference distribution tables for the DES Sboxes available at Eli Biham’s homepage here. Focus only on the output difference $\sf 0x$ i.e., $0000$ which is the first column. There is more than one combination to obtain this result, incidentally.

Focus only on the input differences $\sf 33x,37x,3Bx,3Fx$ which are input differences of the form $11\ast\ast11$ where $\ast$ means that bit of the input difference is arbitrary.

For some Sboxes, all these differences result in an output difference of all zeroes, for some only 2 or 3. But there is always one of these differences which can be chosen to get $\sf 0x$ as the output difference.

In particular, examining Biham’s tables makes it clear that we can choose the input difference $\sf 3Fx$ which is $111111$ for all Sboxes, except for $S_6$ and $S_8.$ For those Sboxes we can choose $\sf 33x$ which is $110011.$

Thus for any $K \in \{0,1\}^{48}$ there are two $X,X’\in \{0,1\}^{48}$ with the difference $$ X\oplus X’= ({\sf 3Fx|3Fx|3Fx|3Fx|3Fx|33x|3Fx|33x}), $$ resulting in $$S(X\oplus K)=S(X’\oplus K). $$ Using the lists under the tables in Biham’s site allows explicit construction of $X,X’$ given $K$ since input output pairs yielding a given difference pair are also listed.

Most importantly since the input differences we have chosen have the general form $11\ast \ast11$ they respect the expansion map.

This is because the shared bits between two adjacent Sboxes can both be flipped to obtain $X’$ from $X$ which means that if $X=E(R)$ then $X’=E(R’)$ for some $R’$ where the outer 2 bits of the four bits destined for a given Sbox are both flipped. If we are using the input difference $\sf 3Fx$ the middle two bits are also flipped, otherwise (for Sboxes $S_6,S_8$) they are not flipped.

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

Remark: This is almost like a manifestation of the complementation property except it is an almost collision (instead of complementation) by complementation at the round level. “Almost” since 4 bits are not complemented.

Answer 3

Expander is injective but S-boxes are not injective, so in whole $f$ is not injective. It means that you can make two inputs with different $R$s in which the output of $f$ after just one round be the same. But in this case, since $R_{i-1}$ goes straightly to $L_i$ this causes the final output of DES be different for them.

Explanation:

In expander, you repeat specific bits, so whenever the output of expander is the same you can certainly say that their input was the same. ( For example, it puts the third bit of input as the 4th and 6th bits of output. )It means that expander is injective.

In S-boxes tables you see the same outputs, for example for 000000 and 110111 of S-box1 (first row first column and last row 11th column)

Permutations are injective by definition (See for example Katz and Lindell), this is not only about DES. We can also explain it in this way: Assume we have two outputs of permutation function which are the same, it means that all of the corresponding bits of these outputs are the same.

The permutation function has taken for example the 3rd bit to the 11th. now 11th bits are the same, it means that in the inputs the 3rd bits where the same. (since permutations are deterministic functions)