At the NSA Symposium on Cryptologic History, I gave a presentation about brute-force attacks. After a subsequent discussion with Whitfield Diffie, I realized that we need a new DES challenge. Here it is.
I’m still totally flashed about the NSA Symposium on Cryptologic History I attended last week. It was the sixth time I took part, and over the years the people I know at this event has grown to almost 100. I couldn’t even say hello to everybody who looked familar to me. When I did, I usually found myself immediately in a conversation about questions like “what is your talk about?”, “what projects are you currently working on?”, or “can we have a more comprehensive talk at the dinner tonight?”. Most of the people I met know my blog, so I had a lot of discussions about things I wrote about, which was very interesting, too.
One of the two presentations I gave was about brute-force attacks on block ciphers.
This presentation was one of four given in a panel session about the history of block ciphers. The other three panelists were Whitfield Diffie, Nicolas Courtois, and Marek Grajek.
A brute-force attack checks one key after another until the correct one is found. The plaintext is usually assumed as being known, which makes checking whether a key candidate is correct quite easy.
The amount of computing power necessary to perform a brute-force attack depends, of course, on the key length. The following slide explains the difference between brute-forcing a 56-bit and a 128-bit key.
Why do I say that a 56-bit key can be broken within one day? It’s because the current world record for breaking a DES ciphertext (the DES encryption system uses a 56-bit key) is about 22 hours. As can be seen on the following slide, this record is already 21 years old.
A part of the panel discussion was about this codebreaking success from 1998. As Whitfield Diffie pointed out correctly, it should be no problem to do much better today. According to Moore’s law, computing power has increased by a factor of about ten thousand within the last 21 years. However, as it seems, nobody has been interested in breaking this record in a decade or more.
After this discussion, I realized that there is not even a current DES challenge that could be attacked by somebody interested in breaking the record. So, I decided to create one. To do so, I used the software CrypTool 2.
As you see, the ciphertext to break consists of one DES block (64 bit). Here it is (noted as a hexadecimal number):
17 69 4D 67 6B C0 69 D7
The key to be found has 56 bit (like every DES key). The plaintext is a 64 bit block derived from eight ASCII characters (details about the encoding are available in the CrypTool 2 documentation):
To solve the challenge, the key needs to be found.
If somebody finds the solution, it is, of course, hard to verify whether it has been found in less than 22 hours. So, if somebody wants to break the current world record, I am happy to provide another DES challenge at a certain point of time, which makes it possible to measure the time until the ciphertext is broken.
Even if you can’t break the record, I encourage you to solve this challenge. At least, you will be the fastest DES breaker in this millenium.
Edited to add: In the original version of this article, I only provided six letters of the plaintext. Nils Kopal and Dave Howe pointed out that this might lead to a non-unique solution. In the new version of the post, the whole plaintext is given.
Further reading: The Top 50 unsolved encrypted messages: 45. The World Record Challenge