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):

SCHMEHc2

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

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (7)

  1. #1 TWO
    Thule sanctuary
    25. Oktober 2019

    But Klaus,

    ASCII is encoded in 7 bits so every 8 bits (byte) start with zero.

    Is this not a weakness?

    SCHMEHc2 what is this?
    Explain please.

    I will not take part in this challenge after the first RSA debacle.

    A well meant Hals und Beinbruch!

  2. #2 Klaus Schmeh
    27. Oktober 2019

    >Is this not a weakness?
    I don’t think it is a weakness. The plaintext is known anyway. Knowing that every byte has one bit set to zero, doesn’t provide any additional help.

  3. #3 TWO
    Gelsenkirchen
    28. Oktober 2019

    They claim to solve it in 26 seconds but charge fee

    https://crack.sh/

  4. #4 Matthias
    28. Oktober 2019

    > They claim to solve it in 26 seconds

    isn’t that 26h ?

    I had a look into this, but I really don’t see how anybody would do it without expensive HW, a service as above or a distributed approach. Using `openssl` one get’s maybe 10.000.000 checks / s, multiply that with the number of available cores and being very optimistic, one might have a 100 fold speed-up in comparison to 20 years ago on OTC HW. Then it was estimated with around 2000 years, 20 years would still be a lot 🙂
    GPUs don’t seem to give a real additional speed-up (no order of magnitude).

    But I might be wrong of course, missing recent development in DES cracking.

  5. #5 TWO
    BRUNSSUM
    28. Oktober 2019

    It is not my claim nor is it my challenge,
    I only reported their claim.

    Don’t shoot the the messenger

  6. #6 Gerd
    28. Oktober 2019

    still no solution posted.
    I feel this one needs less coding effort than the 1000 bigrams challenge. A factor of 10.000 in speed is roughly the difference between dedicated FPGA hardware and a computer.

  7. #7 TWO
    Acapulco
    29. Oktober 2019

    I have decoded the first letter of they key string : T

    I used my old Atari 130XE with sophisticated cryogenic cooling but it caught fire 🙁

    I am sure somebody will fully decode it soon.