Still unsolved: The world record challenge

The world record for the longest cryptographic key solved by complete search is almost 20 years old. When will a new record finally be set?

Deutsche Version

First of all, I would like to thank you for all the letters that have reached me in the last three weeks regarding my recently published comic book “Versutus”. Above all, I am very happy about constructive criticism. “Versutus” is available for purchase on Amazon. As a PDF you can even download the whole comic adventure for free!

Quelle/Source: Schmeh

An old world record

Now let’s get to the actual topic of the day. As computer technology has advanced considerably in recent decades, it may be hard to believe that one of the most significant cryptographic world records has stood for almost 20 years. It involves the longest key ever cracked by trial and error (also known as full key search or “brute force”).

In September 2002, the media reported extensively on the record, which still stands today. At that time, a team from the Distributed.net initiative had cracked a 64-key symmetric RC5 key in five years of work using a full search. 331,252 users around the world had provided computing capacity. In the end, a participant in Japan found the right candidate.

Quelle/Source: ITProToday

The RSA Challenges (1997-2007)

The 64-bit key search took place as part of the so-called RSA Secret-Key Challenges. For this crypto puzzle series, the US company RSA Security published 13 encrypted texts in 1997, which had to be solved with a complete key search. 12 of them were encrypted with the RC5 method, one with the DES. The winner received a cash prize. The texts were encrypted with keys of different lengths. In order to test key candidates, a part of the plaintext was known in each case.

It started with a 32-bit RC5 key, which was quickly cracked. The 40-bit and 48-bit RC5 keys were also no great hurdle for some of the challenge participants. Solving 56 bits, on the other hand, took 140 days (DES) and 265 days (RC5). And finally, as mentioned, the 64-bit RC5 key was also solved. Distributed.net was able to collect 10,000 dollars in prize money for this.

The logical next step would have been to crack the 72-bit challenge. In fact, a Distributed.net project was created for this purpose, but it was not successful. As far as I know, it is no longer active.

In May 2007, the organizer announced the discontinuation of the eight secret key challenges that were still open. The solutions were not revealed, but there was no more prize money. So if you feel like it, you can still try your hand at the challenges with key lengths of 72, 80, 88, 96, 104, 112, 120 and 128.

Since the breaking of the 64-bit key in 2002, no one has claimed to have cracked a longer key than that through full search. This means that 64 bits is the current world record.

My world record challenge

Already 12 years ago I decided to publish a challenge to crack a 65 bit key by complete key search. The calculation behind it should be clear: Whoever solves the challenge will set a new world record. To be more precise, the world record will be improved by exactly one bit in this way.

I published my world record challenge on the crypto puzzle platform MysteryTwister C3 (in German and English). I blogged about it for the first time in 2017.

Quelle/Source: MysteryTwister C3

Unfortunately, there is no prize money. But it could lead to some media coverage if this world record is finally improved after 20 years.

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

The first eight bytes of the plaintext are the solution to the task. They form an English word written in large ASCII letters. The remaining eight bytes have the value “CrypTool” (in ASCII code) or 43 72 79 70 54 6F 6C (in hexadecimal code).

Here is the cipher text of the world record challenge (in hexadecimal code):

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

Since computer technology has improved over the last 20 years, it should now be possible to find the solution in significantly less than five years. If we assume that computing power doubles every 18 months (Moore’s Law), the time required should be eight thousand times less. Instead of five years, that would be no more than a few hours, assuming the same amount of hardware is used as back then.

So the world record challenge should be solvable. Perhaps a reader would like to try his hand at it.

If you want to add a comment, you need to add it to the German version here.
Follow @KlausSchmeh

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/