28
$\begingroup$

The DES key 0E329232EA6D0D73 has the unusual property that decrypting a ciphertext block consisting entirely of zeros gives a plaintext block consisting of eight repetitions of the same byte (0x87).

How was this key originally found?

$\endgroup$
  • $\begingroup$ Since DES keys are only 56 bits, I would not be surprised if it were plain brute force. $\endgroup$ – yyyyyyy Jul 7 '16 at 10:44
  • $\begingroup$ This is my hunch too. DES-cracking hardware has been around for ages, and I can't think of any plausible alternative approach. $\endgroup$ – prim Jul 7 '16 at 10:55
48
$\begingroup$

That value 0E329232EA6D0D73 was found by brute force. I would be surprised if there was a significantly better method: that would be tantamount to a cryptanalytic break of DES, very different from the few we know.

A sketch of the brute force method (with details about parallelization omitted) goes:

  • for each $K$ of 64 bits among the $2^{56}$ valid DES keys
    • decrypt with key $K$ a ciphertext block consisting entirely of zeroes, giving $P$
    • if the eight bytes in $P$ are equal
      • output $K$ and stop
  • output nothing found and stop.

For a perfect cipher, $P$ would be essentially 8 random bytes for each $K$ tried, therefore the if condition would be met with odds $2^{-56}$ for each $K$. Under that approximation for DES (which is not invalidated by the complementation property, since the ciphertext is fixed), odds that nothing found is output are $(1-2^{-56})^{(2^{56})}\approx1/e\approx36.8\%$. Correspondingly, odds that a value of $K$ is found are $1-(1-2^{-56})^{(2^{56})}\approx1-1/e\approx63.2\%$.

It turns out that we are in the second (and most likely) case (proof: the assertion in the question holds). Knowing this, finding a solution $K$ by the method outlined requires at most $2^{56}$ decryptions. That's not much harder than finding a DES key by brute force from plaintext/ciphertext pairs, which was feasible in few days with a budget of \$250,000 (including NRE) in 1998, see the EFF DES Cracker. The only difficulty compared to that is the slightly unusual stop condition. But in a FPGA-based implementation like Copacobana, or a GPU-based one, that adds very little cost.


Update: the EFF DES Cracker was designed to have a flexible enough stop criteria, and was used to first publicly find that particular key, as a demonstration that it works. Quoting the EFF website:

The EFF DES Cracker first solved a challenge posed [circa 1996] by world-renowned cryptographer and AT&T Labs research scientist, Matt Blaze. The "Blaze Challenge" was designed to only be solvable by "brute force" cryptanalysis of DES. Mr. Blaze challenged the world to find matching pairs of plaintext and ciphertext numbers, consisting of nothing but repeated digits. Blaze himself was unaware of any such pairs until the EFF DES Cracker revealed the first known pair. It found that a hexadecimal key of 0E 32 92 32 EA 6D 0D 73 turns a plaintext of 8787878787878787 into the ciphertext 0000000000000000.

$\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.