RC5-64 Success

Peter Trei writes "After over four years of effort, hundreds of thousands of participants, and millions of cpu-hours of work, Distributed.net has brute forced the key to RSA Security's 64 bit encryption challenge, winning a US$10,000 prize. Still outstanding Challenges carry prizes as high as $200,000. RSA's PR release is here. d.net's site has not yet been updated." Update: 09/26 16:59 GMT by CN : The good folks over at SlashNET are having a forum with the distributed.net crew on Saturday at 21:00 UTC. It'll be a great time to meet some of the people who made this possible.

Comments

an interesting bit of trivia

[Nugget]

While the prospect of a false-positive key was the subject of much speculation during RC5-56, we did in fact encounter exactly such a beast during RC5-64.

In the interests of speed, only the first "block" of the crypted text is decrypted and evaluated for a solution. This means that it's possible for a key which isn't the correct key to report as a false positive because although it doesn't decrypt the text it does yield a plaintext which matches "The unkn" for the first eight bytes.

There's been much speculation and napkin scribbling on just how frequently such false positives might present themselves. The general consensus seemed to be that such an occurrence is extremely improbable but in a dataset the size of 2**64, extremely improbable may still yield a nonzero frequency.

The key 0xBB27D52F60FD932C does, indeed, decrypt to a plaintext for which the first eight bytes match the known plaintext for the contest. The remainder of the decrypted text, however, is just garbage. This key has actually been returned by clients twice over the course of the contest.

In August 1999, "Edward Scissorhands" turned in the key.

Again in July 2000, Team RC5 Chile submitted it. Since they're unfortunately using a shared email address for their team, there's no way to know which individual was the submitter.

I wasn't the winning key, but was a really unique "near miss". It also represents an interesting datapoint regarding the RC5 algorighim. A brute-force search is really the only way to conclusively determine the liklihood of such false positives.

Re:an interesting bit of trivia

[BovineOne]

Nugget is wrong, the false positive was actually found three times. Most recently, the bymer@ukrpost.net worm found the false-positive on
November 6, 2001. There potentially could be problems identifying the owner of that worm-infected machine and having to explain the
circumstances of a winning solution, but fortunately that was only a false positive.

False positives in RC5-64

[BovineOne]

Naturally there is a lot of interest about finding the solution, but what about "almost solutions" found by false-positive hits?

In the interests of speed, only the first "block" of the crypted RC5-64 text is decrypted and evaluated for a solution. This means that it's possible for a key which isn't the correct key to report as a false positive because although it doesn't decrypt the text it does yield a plaintext which matches "The unkn" for the first eight bytes.

The key 0xBB27D52F60FD932C does, indeed, decrypt to a plaintext for which the first eight bytes match the known plaintext for the contest. This key has actually been submitted three times over the course of the contest, once by three different users.

In August 1999, again in July 2000. Most recently, the bymer@ukrpost.net worm found the false-positive on November 6, 2001. There potentially could be problems identifying the
owner of that worm-infected machine and having to explain the circumstances of a winning solution, but fortunately that was only a false positive.

Fortunately, we eventually found the actual key. But because we were seeing these legitimate false-positives being reported throughout the duration of the contest, we had full confidence that our network and our clients were functioning properly and that we would eventually find the actual solution in time.