1
$\begingroup$

It's known that for a given subkey, the F-function of the DES is not injective (see Is the DES F-function injective for a given subkey?). I am interested in efficiently finding collisions for this function, i.e. for a given subkey $k$, I want to find two different inputs $x$ and $y$ such that $F(x,k)=F(y,k)$.

I am wondering if there are shortcuts that make finding such key values easier than plain brute-force?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hint: $F(x,k)$ is the concatenation of 8 independent 4-bit functions of 6-bit extracts of $x$ and $k$. Further, these extracts are combined by XOR. $\endgroup$
    – fgrieu ♦
    Dec 1 '15 at 8:07
1
$\begingroup$

If S is a DES S-box, for a given "output", S(input) = output has exctly 4 solutions for "input", or "collisions". You can then find collisions for F by concatenating collisions for each S-box. You can start with setting an output for F and then look for all possible "inputs" for each of the 8 S-boxes on the 4 relevant bits of the output of F.

Improve this answer
$\endgroup$

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.