8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have amended my answer and would appreciate your thoughts $\endgroup$ – kodlu Jun 6 '20 at 13:21
  • $\begingroup$ I have edited the answer again. $\endgroup$ – kodlu Jun 14 '20 at 6:15
6
+1000
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice! last night here in the antipodes I actually made the same observations on the key bits. Not being a decent programmer, and having trouble with DES online implementations in python and other languages, and hex to bit conversions, I was hoping to proceed further with more mathematical reasoning or clumsy attempts at programming. But I am happy you verified the rest by brute force. $\endgroup$ – kodlu Jun 5 '20 at 22:09
  • $\begingroup$ I'm convinced we know a bit more about DES, literally! Since that was the first correct answer, it gets the first bounty. It also gets the second one, since a hand-checkable valid proof has remained elusive within the bounty+grace period. $\endgroup$ – fgrieu Jun 14 '20 at 23:33
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think you are right I will revisit when I can $\endgroup$ – kodlu Jun 2 '20 at 7:10
  • $\begingroup$ Of course, you're right. There are 6 bits per Sbox. $\endgroup$ – kodlu Jun 6 '20 at 20:20
  • $\begingroup$ I think antecedent makes sense to me as well. $\endgroup$ – kodlu Jun 7 '20 at 8:16
  • $\begingroup$ Thanks for your comment. I think since we consider the additive term $K+X$ as it enters the Sbox and $K$ is fixed, it is enough to have antedecent by $E$ in the choice of $X$ and thus reflect this through $\Delta X.$ $\endgroup$ – kodlu Jun 7 '20 at 8:54
  • $\begingroup$ I will re-visit and tighten up the argument. $\endgroup$ – kodlu Jun 8 '20 at 8:28
0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ "Expander is injective but S-boxes are not injective, so in whole $f$ is not injective". That argument is incorrect. Proof that is it: it does not invoke the S-box content, and it is easy to make S-boxes that make the DES function injective for all subkeys. An example is 8 identical S-boxes consisting of 4 identical lines with the integers 0 to 15. I don't bounty easy questions! $\endgroup$ – fgrieu Jun 3 '20 at 10:20
  • $\begingroup$ @ fgrieu: 1. Definitely nobody bounty easy questions, but you didn't explain your question more. 2. If you want to change the S-boxes, yes it can be injective. But the S-boxes of IBM which are published in 1990s are not. 3. If you make S-boxes injective, the final result would be injective, since the composition of injective functions is injective. $\endgroup$ – m123 Jun 3 '20 at 10:40
  • $\begingroup$ I'm not proposing to change the S-boxes, that is explicitly excluded in the problem statement, which strives to be unambiguous. I'm using hypothetically different S-boxes (which remain non-injective since any 6x4 S-box is) only to refute any proof, including the one given in answer, that does not take into account the S-box content. Different refutation of the particular proof given: the composition of an injective and a non injective function can be injective, when (as is the case here) the functions are not from/to the same set. $\endgroup$ – fgrieu Jun 3 '20 at 10:48

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.