#StackBounty: #des Proof that no DES key makes encryption identity

Bounty: 500

How can we prove that no DES key makes encryption the identity function?

That is: $;forall Kin{0,1}^{56}quadexists Min{0,1}^{64}quad E_K(M)ne M$

Note: anyone proving this proposition false would gain instant celebrity, which is a meta-proof that this proposition is true, but not an acceptable answer!

That proposition is false for 2DES (EE), even restricted to one key, because twice applying encryption with the all-zero key (and the Final Swap built into the Final Permutation) yields identity.

For the same reason, the proposition would be enough to prove that DES is not closed under function composition, hence not a group [but Keith W. Campbell and Michael J. Wiener’s DES is not a group in proceedings of Crypto 1992 (free access) also proves other facts. See a more extended bibliography there].

Variants of the question:

  • 3DES (EDE) with 3 or 2 keys
  • 3DES EEE variant
  • what if we remove the Final Swap of the Final Permutation (then the proposition becomes very plausible for 2DES)
  • $rge1$ rounds of DES and independent subkeys, with or without Final Swap; clearly the proposition must become false for some $r$ !

Inspired by this question.

Update: towards a solution, I have thought of

  • Pure brute force. Plausibly, that requires no (or very little) more than $2^{55}$ DES encryption of a constant plaintext block $M_0$, say all zero (for we can fix a key bit thanks to the DES complementation property, and a single test is enough to eliminate overwhelmingly most keys). Using the all-zero block for $M_0$, or any one invariant under final swap, has the advantage that we can answer the question for DES both with and without final swap using essentially the same amount of work.
  • Some work reduction, possible by enumerating the keys in a way that allows caching of the external rounds (as was done in DESCHALL, see this).
  • Devising a function $F:{0,1}^{56}to{0,1}^{64}$ that slightly simplifies the evaluation of $E_K(F(K))=!!!!?;,F(K)$ compared to that of $E_K(M_0)=!!!!?;,M_0$; it seems possible to save even more work.
  • Expressing the problem as a Boolean satisfiability problem in Conjunctive Normal Form and throwing a state of the art solver at it. I’m pessimistic about this approach, though.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.