Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
