# Finding collisions for the DES F-function

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?

• 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.
– fgrieu
Dec 1, 2015 at 8:07