1
$\begingroup$

In Paar's Understanding Cryptography, it is stated that

This mapping [each round in Feistel structure] remains bijective for some arbitrary function $f$, i.e., even if the embedded function $f$ is not bijective itself. In the case of DES, the function $f$ is in fact a surjective many-to-one mapping. It uses nonlinear building blocks and maps $32$ input bits to $32$ output bits using a $48$-bit round key $k_i$, with $1 \leq i \leq 16$.

But they give no justification for this statement, which seems nontrivial to me. Why is $f$ necessarily surjective in DES? How can one show this?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

When, as in the second part of the question, DES's $f$ function is viewed as mapping $32$ input bits (a half block) to $32$ output bits (that get XORed with the other half block) for a fixed $48$-bit round key, $f$ is not injective, regardless of the fixed 48-bit round key that we consider(1). Since $f$ is a function from a finite set to itelf, it's thus not bijective, thus not surjective.

Therefore we assume from now on that the question asks why, and proof that, $f$ is surjective when viewed as mapping $32+48$ input bits (including round key) to $32$ output bits.


As of a proof: $f$ is defined in FIPS 46-3 as: $$\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. Fix to zero all $32$ bits of $R$, so that the input of the S-boxes is the $48$ bits of $K$. Further fix to zero the $16$ bits $1,6,7,12,\cdots,59,64$ of $K$, corresponding to the input bits of S-boxes that select an S-box row. This insures that the first row of each S-box is the one used. Each row of each S-box is a permutation. It follows that the function of the remaining $32$ bits of subkey $2,3,4,5,8,9,10,11,\cdots,60,61,62,63$ to the $32$ bits of output is a permutation. We can thus exhibit a $80$-bit input ($48$ bits of which zero) to any $32$-bit output of $f$, proving that $f$ is surjective(2).

As of the rationale (why): from a design perspective, the ideal for $f$ is arguably to behave like a random function of $80$ to $32$ bits. And with high likelihood, a random such function is surjective(3). The designers of DES did not want to chose one of the rare $f$ that are not surjective. In fact, they have selected an $f$ where the distribution of the outputs is exactly even, which is antagonist to not surjective.


(1) See my question and Thomas Pornin's un-challenged answer. In a nutshell his proof uses that each of the 4 rows of the 8 S-boxes is a permutation to show that the problem of checking surjectivity of $f$ for a given subkey is independent of $32$ out of $48$ bits of the subkey. He uses a program to find a collision for each of the $2^{16}$ remaining classes of subkeys, proving that $f$ is not injective.

(2) Further, we can prove that each $32$-bit output has exactly $2^{48}$ matching inputs. Sketch: For each $32$-bit output, for each $32$-bit $R$, each of $2^{16}$ choices of S-box rows matches a unique distinct choice of bits $1,6,7,12,\cdots,59,64$ of $K$, and then a single choice of the other $32$ bits of $K$.

(3) Non-rigorous argument: any fixed of the $2^{32}$ outputs is not reached by any of the $2^{80}$ inputs with probability $\approx 2^{-48}$, so under the approximation that these $2^{32}$ events are independent the probability that a random function is not surjective is $\approx 2^{-16}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.