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?
2
-
1$\begingroup$ Since DES keys are only 56 bits, I would not be surprised if it were plain brute force. $\endgroup$– yyyyyyyJul 7, 2016 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$– primJul 7, 2016 at 10:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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¹:
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.
¹ This links to an archive of the original. Some of that material is still on the current EFF website, but sadly the date was lost in modernization, becoming August 2016 rather than July 1998.
