StartseiteCipherbrain

The Top 50 unsolved encrypted messages: 45. The World Record Challenge

Von / 26. Februar 2017 / 14 Kommentare
Mehr

The longest key ever publicly broken by exhaustive key search has 64 bits. A challenge I created a few years ago aims to improve this world record by one bit.

Click here for the complete top 50 list

In September 2002 the media reported about a 64 bit cryptographic key that had been cracked by exhaustive search (i.e., brute force).

World-Record-Challenge-Clipping

This news came as no surprise, as five years earlier a 56 bit key had been broken the same way. In both cases computer users all over the world had provided unused processor capacity for testing key candidates. No less than 331,252 users participated to break the 64 bit key. After 1757 days (almost five years), a participant in Japan finally discovered the correct candidate.

 

The RSA Challenges (1997-2007)

Both the organizers of the 56 and the 64 bit key search started their projects in order to win an award endowed by the US company RSA Security (RSA Challenges). In fact, RSA Security paid both winners a prize money of $10,000. There were several more secret key challenges created by RSA Security, each with a $10,000 award.

The logical next step would have been to break the 72 bit key challenge. However, in May 2007 RSA Security announced the termination of all challenges. As the ciphertexts are still available and the solutions not known, you still can try to break the keys. However, there is no prize money any more.

Since the breaking of the 64 bit key in 2002, nobody has claimed to have cracked a longer key than this one by exhaustive search. This means that 64 bit are the current world record.

 

The World Record Challenge

In 2010 I decided to set up a secret key challenge aiming to improve the current world record by one bit. I published this challenge on the crypto puzzle platform MysteryTwister C3. There’s also a German version of it.

MTC3-title

To my regret, there is no prize money. However, chances are good that there will be a broad media echo if this world record is improved after such a long time.

The ciphertext I took was encrypted with CrypTool. I used the AES encryption algorithm 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 of the challenge. 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 within the last 15 years, 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 amount of hardware is used.

After 15 years it is time to improve this record. I wish you good luck trying it!


Further reading: How to Use a Rubik’s Cube for Encryption

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.

Stichworte: ,
Mehr

Kommentare (14)

  1. #1 TWO
    26. Februar 2017

    Klaus a question :

    There are 40161 8 letter words in the Englisg language words according to one list.

    Would it be possible to brute force your challenge by running that list against your challenge?

  2. #2 Klaus Schmeh
    26. Februar 2017

    @TWO:
    I don’t think this is possible, as there is no way to determin if a certain eight letter word is correct.

  3. #3 Jim
    27. Februar 2017

    Doesn’t it depend on the way the challenge is checked? If each participant gets only one try, then your point is well taken. If it’s automated, then it seems TWO’s approach could work if that word is on the list. I think Sanborn took down the Kryptos 4 checker page because somebody was trying that for the first word.

    Back on what the challenge is *trying* to test, I looked up some GPU implementations of AES, and each of them only started showing a benefit over CPU after encrypting large amounts of data with the key, and then only one order of magnitude improvement. Would ASIC be the preferred method these days?

  4. #4 Nils Kopal
    University of Kassel
    27. Februar 2017

    Modern ciphers resist ciphertext-only as well as known-plaintext attacks. Even having the correct one English word does not help since to prove that one has to test ALL AES-Keys. In this case we have to test 2^65 AES keys. Since we do not know the correct word, we would have to test 401618 * 2^65 (all words…) which is about 2^75… thus, in this case, its even less effort to make a brute-force attack (ciphertext-only) case which also needs 2^65 decryptions…

    Modern GPUs helps us to speed up such attacks slightly… with CrypTool 2 (AES known-plaintext) I get about 5mio AES keys/sec with my CPU (AMD FX-8350 Eight-Core @ 4GHz) using AES-NI (AES assembler instruction set) and about 5-6mio AES keys/sec with my GPU (GeForce GTX 1060). I know that my laptops Intel I-7 is about 2times (~10mio AES keys). If I had unlimited budget (NSA like) I would prefer building a (or several) cluster(s) of ASICs. Maybe FPGAs – which would makes a reconfiguration for other ciphers possible.

    One thing about performance of known-plaintext and ciphertext-only. In my experience, known-plaintext can be implemented faster since the cost function in the most easiest way is just a bit-wise comparision of known-plaintext and decrypted plaintext. With ciphertext-only, we need more sophisticated cost functions (entropy, index of coincedence, 3-grams, 4-grams, etc). And those are more costly, thus, it gets slower.

  5. #5 Jim
    27. Februar 2017

    @Nils – Thanks for the information on hardware. I appreciate the well-informed summary.

    For a different challenge (e.g. “find the key that encrypts a suitable plaintext to this ciphertext”) I’d agree with your first paragraph.

    However, the actual challenge says “Your task is to guess the first eight bytes of cleartext. They form an English word written in capital ASCII letters, and this is the codeword for the challenge.” There is no requirement that the key be produced. This is why I thought TWO’s dictionary attack might be feasible depending on how the solution is checked.

  6. #6 Nils Kopal
    University of Kassel
    28. Februar 2017

    yes… but its AES… its impossible to get the cleartext without having the key… thats a requirement for modern cipers. If you find a way to get the text without testing the keys we should write a paper about that 🙂

    the best known attack on AES, the Biclique attack, reduces the effort from 2^128 to ~2^126. A dictionary is useless. A known-plaintext is useless. The only thing that helps you not to search through 2^128 is that Klaus gave you a part of the key 🙂

    There is no way around brute-forcing that keyspace…

  7. #7 Nils Kopal
    University of Kassel
    28. Februar 2017

    And to finally destroy your hopes, i.e. brute-forcing the webapp with the dictionary – sry 4 that – we do not have the correct key at MysterytwisterC3 😉
    Klaus is the only one who (maybe) knows the key… but i guess he intentionally did not memorize the key… thus, you HAVE TO brute-force the keyspace 😉

  8. #8 Jim
    28. Februar 2017

    I’m still confused. In order to get the prize, TWO must submit the right 8-letter English word in all caps. In order to check that TWO entered the right one, Klaus doesn’t need to know the key, and he doesn’t need to run AES on a key TWO provided: TWO wasn’t asked to show a key. All Klaus needs to know is the right 8-letter word to check whether TWO met the challenge. Similarly, TWO doesn’t need to run AES either if he can make a few thousand guesses, and he doesn’t need to show a key that would produce that word.

    What am I missing here?

  9. #9 Klaus Schmeh
    28. Februar 2017

    @Jim:
    >TWO doesn’t need to run AES either if he
    >can make a few thousand guesses
    TWO can certainly hand in a few thousand guessed solutions and hope that one of them is correct. In this sense a brute force attack works. However, I wouldn’t accept so many tries.

  10. #10 TWO
    1. März 2017

    the keyword is hidden in Klaus’s safe at work 😉

  11. #11 Timo Kammerer
    1. März 2017

    is there a howto how i can try this by myself.
    thanks for help

  12. #12 TWO
    1. März 2017

    I personally would start with the following byte mask for the AES key

    00 00 00 00 00 FF FF FF
    FF FF FF FF FF FF FF FF

    This would in my humble opinion be the best starting key

    But what do I know? Im not a cryptoanalyst.

  13. #13 Klaus Schmeh
    3. März 2017

    Timo Kammerer:
    >is there a howto how i can try this by myself.
    I wouldn’t know. You probably need to write a program that tests one key candidate after the other. To do so you can use an existing AES implementation (there should be a few available online). However, a single PC is probably too weak for such a task. You need a lot of hardware and optimized code. It’s not necessarily a beginner’s project.

  14. #14 TWO
    5. März 2017

    Well, that is going to be a huge power bill….

    CRYPTOME 🙂