StartseiteCipherbrain

The world record crypto challenge

Von / 6. Oktober 2016 / 5 Kommentare
Mehr

The longest key ever publicly broken by exhaustive key search was 64 bits long. If you solve the cryptogram I introduce in this blog post, you can set a new record.

Everybody interested in codebreaking should know the web site Mystery Twister C3 (MTC3). MTC3 is a site dedicated to crypto challenges, ranging from pretty easy to hitherto unsolved. If you solve one of these challenges, you get a certain amount of points. The most successful players are listed in a hall of fame.

MTC3-2

MTC3 is organized by Prof. Bernhard Esslinger (University of Siegen), Prof. Dr. Alexander May (Ruhr-University Bochum) and Prof. Dr. Arno Wacker (University of Kassel). There’s a close relationship to the open source crypto training software CrypTool.

 

The challenges

The challenges of MTC3 are devided into four levels: level 1 (easy), level 2 (intermediate), level 3 (hard) and level X (unsolved). The following postcard is presented as a level 1 challenge:

Postkarte-aus-Saloniki

I have been involved in MTC3 myself, too, as a provider of a number of challenges. All of them are either level 3 or level X, which means that I delivered some of the tough ones. Some of my challenges represent well-known crypto mysteries, like Kryptos, Dorabella, Beale Ciphers or D’Agapeyeff. In addition, I provided the DCT challenge, which was solved by George Lasry, and two M-138 challenges.

 

The World Record Challenge

Another one of my MTC3 challenges is titled “World Record Challenge”. It refers to the fact that the longest key ever publicly broken by exhaustive key search was 64 bits long. This world record was set by a team of experts in 2002 after five years of computation. More information is available at Wikipedia (see „RSA Secret-Key-Challenge“) .

The purpose of the World Record Challenge is to improve the current world record by one bit. This means that a 65-bit key is to be cracked by exhaustive search.

The ciphertext I took was encrypted with CrypTool. The encryption algorithm used is AES in ECB mode with a key length of 128 bits. The first 65 bits must be guessed. The remaining 63 bits are set to 1.

The first eight bytes of cleartext represent the solution to be handed in at MTC3. They form an English word written in capital ASCII letters. The remaining eight bytes have the value „CrypTool“ (in ASCII code) or 43 72 79 70 54 6F 6F 6C (in hex code).

Here is the ciphertext of the World Record Challenge (in hex code):

4B 14 55 BC 8D DF 33 AF 57 91 53 90 BB 2C E1 2A

This challenge is certainly a tough one – after all, solving it means a new world record. However, as computer technology has considerably improved since 2002, it should be possible to find the solution in much less than five years. If we assume that computation power doubles every 18 months (Moore’s law), the time needed will be a thousand times less. Instead of five years (~ 1800 days) this would mean 1.8 days, provided that the same hardware budget is available.

I think, after 14 years it is time to improve this record. I wish you good luck trying it!

Further reading: UK crypto blogger Nick Pelling has just posted a campaign on Kickstarter to make a documentary about a 200-year-old pirate treasure mystery involving encryption:  https://www.kickstarter.com/projects/nickpelling/gold-beyond-your-dreams

Stichworte: ,
Mehr

Kommentare (5)

  1. #1 ulfi
    7. Oktober 2016

    your challenge is much different to the previous record. Because in order to evaluate whether the result is legitimate it has to be validated. In typical code breaking applications the clear text is assumed to be known while the key is the entity that is needed. Here additionally a dictionary attack is needed. Moreover it is not even sure that the result is unique. in a keyspace of 2^65 are you sure that no two solutions ending in “CryptTool” exist?

  2. #2 Nils Kopal
    Kassel
    7. Oktober 2016

    Ulfi thats wrong 🙂
    you dont need a dictionary.

    You decrypt two blocks of AES, rate the resulting plaintext using a cost/scoring function. Thats it. We know, that the second block consists of “CrypTool”, thus, a simple string comparision of the last 8 bytes is enough as cost function. Our attack here is is a partially-known plaintext attack.

    You refer to a (full) known-plaintext. In this case, knowing one block of the plaintext is enough for rating. Currently, i am working on distributed cryptanalyis with decentralized p2p networks and implemented this in CrypTool 2. We have a test with DES, which has a block size of 64bit. We also have a block containing “CrypTool” (64bit). With our attack, we generate a “best” list where the ciphertext containing most equal characters of “CrypTool” reach higher positions. Right now, we did not find the correct key, but keys that “generate” plaintexts with “CrypToo” (56bit). The rest of the plaintext is garbage. Clearly, it may be possible that you find a key that generates one complete correct block, but all the following will be wrong. We collect all “CrypTool”-* plaintexts and the one correct one will be inside this set at the end of the exhaustive keysearching attack.

    The most difficult attack is a ciphertext-only attack. But with modern ciphers, the only drawback is, that we do not have as fast cost functions as the string-comparision. Here, we need more sophisticated cost functions like entropy or index of coincedence. Thats it. With 8 bytes, these cost functions are not good enough, but having more, i.e. 16 bytes or more, they may also be suitable.

  3. #3 TWO
    11. Oktober 2016

    so easy : CRACKED!

    j/k 🙂

    TWO

  4. #4 Klaus Schmeh
    12. Oktober 2016

    @TWO: “CRACKED!” would be a valid solution (because it consists of eight characters), but it is wrong.

  5. #5 Nils Kopal
    Kassel
    12. Oktober 2016

    Hehe, we could now just send Klaus every combination of words (A-Z,a-z, and some special chars) with length 8. The correct solution will be most probably inside this set. Nevertheless, the proof that we actually broke it would be the correct AES key. That would require us to send Klaus 2^65 keys to send him the correct one. On average, after sending 2^64 keys, the correct one should be included…

    Maybe its “easier” on less time consuming to just really search through the space instead of annoying Klaus with “guesses” 😉