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.

End of an era (for me, anyway)

[Scutter]

I'm surprised at how stunned and emotional I am upon reading this. After personally investing almost four years and uncounted trillions of clock cycles for over half a quadrillion keys and just like that it's over with. *sigh*

I watched the progression of the computer industry grow just by watching the gradual increase of my daily keyrate.

Four years ago when I first started, I was going through 52 blocks a day. Yesterday, I went through 2784 blocks. Looking at the daily graph is practically a history of my life for four years. I can see spikes where my company bought a dozen computers and I borrowed their cycles for a couple of days while I configured them. I can see dips where I turned my computers off to go on vacation for a weekend. There's the whole flat area from last year when I didn't have a job and so had limited access to extra CPU cycles.

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.

Re:Yea!!!

[Blkdeath]

Hardly. We're talking about a third of a million participants taking 4 years here. Unless someone's developed a time machine and built ASCI from some future technology it's not that fast! (remember, many participants were science labs or other groups utilising several, sometimes hundreds of machines).

We're still talking about machines that don't even hit a single GFLop, whereas ASCI White clocks in at a paltry 7.2TFlops, while Japan's Earth Simulator runs at a tidy 35.86TFlops.

Not to sound too black-helicopterish or anything, but these are only the supercomputers that we know about.

Isn't it entirely possible that in the interests of tracking "terrorists", the Department of Homeland Security might just have assembled something that makes E.S. look like an old laptop?

The technology exists, it's just a simple matter of somebody (read: corporation / government) with the funding and wherewithall to put it together and make it function.

Re:False positives in RC5-64 - SO IS NEXT?

[BovineOne]

Depending on the speed of your machine, OGR stubs may indeed take a very long time (many hours typically). If you have a relatively slow machine, this may indeed keep your machine busy for more than a day--just be patient. The individual size of each OGR workunit can varies greatly from one workunit to the next, by design.

Re:G4 800 faster than Athlon 2Ghz?!

[discstickers]

I can attest to that from personal experience. I have a PowerBook G4 500. My roommate last year had a custom-built P4 1.4 GHz.

I was able to do around 4 million keys/sec. He did around 2 million keys/sec. So, clock for clock, my computer was 4 times faster than his.

Yes, the advantage was because of the Velocity Engine(ake VMX aka AltiVec), but I does show the power of the G4 when it is programmed for correctly.

Re:More worthwhile?

[southpolesammy]

Let me ask you, what did we learn from the breaking of the RC5-64 algorithm? That given enough resources we could break what seems to be a strong algorithm? We knew that long ago. Did we learn any new methods of sequencing that might assist us in determining the innate strength of this algorithm that we could apply to others? Not hardly. We knew beforehand that the sequence would eventually be found at least by brute force, and since that proved to be true, we learned nothing about how to do it better the next time. The only palpable gain was the demonstration of a large distributed network of nodes working together to achieve a goal, but that too has been demonstrated before.

Bottom line -- the whole RC5-64 project was a big freaking no-op. Therefore, yes, I do feel looking for signs of extraterrestrial life, or gene sequencing, or some other task would have been more fruitful than the goal of this pursuit. I realized that years ago and switched to SETI as a direct result of that observation. And the point about whether ET wants to contact us or not is irrelevant. If the SETI project was able to attain their goal, it would literally be the greatest event in history. Because of the ramifcations of this possibility, the end goal is more worthy and will reveal something about the nature of things, rather than prove a hypothesis we already know to be true and provable. The amount of CPU cycles wasted on this project that could have been applied elsewhere is staggering.

Re:G4 800 faster than Athlon 2Ghz?!

[chrysrobyn]

Am I missing something here? Are they claiming the 800mhz G4 is over 1.4 times as fast as an Athlon 2ghz??

You're not missing anything. For some coursework when I was in school, I ended up sending some e-mail to the dnet staff. I mentioned that I needed to design a processor on an FPGA for a class, and asked what would be "ideal". They basically said, "Take Motorola's 7400 specs, that's the ideal processor."

The Velocity Engine / AltiVec / VMX engine really was good at processing multiple keys (2?) simultaneously, and conducting the XOR rotates in record clock cycles (if I remember correctly). The processor architecture itself is mostly 1993 technology (PowerPC 603), but the vector engine is what makes it worth its weight in sand for some specific tasks.

Now, what will I do with my dual 500MHz G4?