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

d.net's site update

[ChronoZ]

Link here: http://www.distributed.net/pressroom/news-20020926 .html

FINALLY.

[KFury]

Does this mean I can go back to alien hunting now?

Re:FINALLY.

[McCart42]

No, you can still work on the optimal golomb ruler project (OGR), which is an interesting distributed project that becomes exponentially more difficult for each added mark. Currently they are working on a 25-mark ruler, and verifying the 24-mark ruler. From the linked page: "OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. Golomb rulers can also play a significant role in combinatorics, coding theory and communications, and Dr. Golomb was one of the first to analyze them for use in these areas."

Re:FINALLY.

[Matt2000]

Seriously though, can anyone tell me what the attraction to the d.net project was? It seems like a colossal waste of cycles to me. Everyone knew it was going to be successful, it was just a matter of wasting enough time to eventually find the right block.

Now that it's over, what do we have to show for it? A whole lot of nothing it seems.

Congratulations

[Dirtside]

While this is an admirable achievement, I found another distributed computing project which I think is more worthwhile -- namely, Folding @Home, which is a distributed protein-folding simulation effort. This is the kind of research that will end up curing things like Alzheimer's, and I think it's a better use of your processing time than brute-forcing encryption keys (or even SETI, or Primenet). I encourage everyone to participate in F@H instead, as I think it will provide a greater benefit to us all in the long run.

Of course, some on /. may need to be reminded that they are indeed free to run whatever distributed computing software they feel like; I am merely requesting that they run this one.

Re:With apologies to Douglas Adams

[affenmann]

No, it is: "some things are better left unread". This doesn't apply to Douglas Adams, of course.

I think many posters here are missing the point

[watanabe]

I think many posters here are missing the point of this. RSA wants people to crack these weaker crypto offerings; it makes their story better, not worse.

• They know exactly how insecure RC5-64 is. They want other IT groups, industry groups and tech managers to know it. The easiest way to do that is to offer open challenges with cash prizes. It's never hard for RSA to up their bit-length to 4096, say, a year before 2048 RSA is broken, and someone collects their $200,000. It is hard to make PHBs understand that RC5-64 is not secure if nobody has broken it.

Secondly, Distributed.net clearly isn't doing it for the cash. I didn't do it for the cash, either. (Although I wouldn't have minded winning.) They're doing it because:

• Breaking codes gives nerds their kicks.
• Building a distributed computing architecture is a difficult and interesting problem.

With current technology, as RSA likes to demonstrate, the winners are the cryptographers, not the cryptologists (the code breakers.) Quantum computing may change that, and make the cryptologists the winners. Until then, RSA can happily give cash prizes for increasing length keys: the numbers are on their side.

How crazy is this?

[WalterGR]

From the press release - "a coordinated team of computer programmers and enthusiasts, known as distributed.net, has solved the RC5-64 Secret-Key Challenge."

If you remove a single element - the $10,000 award offered by RSA - then the press release would read more like,

"A group of degenerate hackers [sic] cracked an encryption method owned by RSA Security Inc. The company has contacted law enforcement authorities, and an attempt to track down these hackers [sic] is currently under way. Under the DMCA, these criminals, when caught, faces sentances of up to..."

Re:Are they going to share the prize?

[miltimj]

Hmmm... as it says here:

RSA Labs is offering a US$10,000 prize to the group that wins this contest. The distribution of the cash will be as follows:

$1000 to the winner
$1000 to the winner's team - this would go to the winner if he wasn't affiliated with a team
$6000 to a non-profit organization, decided by vote
$2000 to distributed.net for building the network and supplying the code

The vote will be decided on through an extension of the statistics engine, with one vote per block per person.

And to think.. it took a few seconds to find that, and a couple minutes to type your post..

Re:Heh

[Papineau]

Not really. If you consider that over 5 years, the average keyrate is 105.5 GKeys/sec, and the latest day averages were somewhere around 180 GKeys/sec, it means the same thing could have been finished in almost half the time, if it was started now with today's computers. Moore's law being what it is, if it really was started again now, it would take around half that time again, because more powerful CPUs are to be unveiled in that timeframe.

By their own estimates, it would take ~46000 Athlon XP 2GHz (now, where are you to find those right now?) to have 270 GKeys/sec (their peak rate in 5 years), which gives completing the keyspace in 790 days. Who would buy that much CPUs? Good question. With 2 dual MP motherboards in 1U (too lazy to find a link, I know somebody offers something like that), it would only take about 300 40U racks. Would you bet future national security on it? I don't think I would (and I'm not even american).

What it really shows is that brute-force can succeed, given enough time. But of course the more effective way to attack an encrytion algorithm is on the algorithmic side, because it helps you to find not only one cleartext, but all cleartexts encrypted with that algorithm.

Distributed.net no longer in the public eye

[HoserHead]

It's sad, really, that so much focus has moved off Distributed.net to SETI@Home and the other distributed computing projects when Distributed.net was one of the real pioneers of this style of computing (that is, harnessing regular people's CPU time).

In one of my CS classes, we were discussing distributed computing, and a question of any well-known distributed computing projects was asked. I answered "Distributed.net" - and the instructor promptly asked "What's that?" The next student to respond, of course, said SETI: the answer he was looking for.

Maybe I'm biased, as the former maintainer of distributed-net for Debian, but has Distributed.net really become this unimportant and forgotten?

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.