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.

d.net's site update

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

No more RC5 in OpenBSD

Funny. The RC5 algorithm has just been removed from OpenBSD because of copyrights.

Heh

While it's debatable that the duration of this project does much to devalue the security of a 64-bit RC5 key by much, we can say with confidence that RC5-64 is not an appropriate algorithm to use for data that will still be sensitive in more than several years' time.

Heh, it took a world-wide effort of thousands of computers over 1700 days. I don't think there is any debate at all; they proved the opposite of what they set out to prove. :)

Re:G4 800 faster than Athlon 2Ghz?!

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:G4 800 faster than Athlon 2Ghz?!

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?

Re:Heh

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.

With apologies to Douglas Adams

So tell me, was the answer "42"?

Re:With apologies to Douglas Adams

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

FINALLY.

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

Re:FINALLY.

No, you can still work on the optimal golomb ruler [distributed.net] 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.

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.

Brute Force vs design flaw

I've always thought that if you use brute force then you aren't really finding a flaw in the design. Brute force is just that, and as keys become bigger and bigger (yes even with bigger and bigger processors) it becomes harder with this method. Especially since it won't do you much good unless you can do it in a short amount time, minutes instead of months or years.

I think those that find actual flaws in the design or math are worthy of admiration. For good reading on the history of such read the code book. It will truly broaden your understanding.

3 legged dog walks into a bar, says" who shot my paw?

IRC discussion

From the distributed.net announcment [distributed.net]

Also, please consider joining us on SlashNET IRC on Saturday 28-Sep-2002 @ 21:00 UTC (5:00PM EDT) for an online Q+A session on the RC5-64 project and the future plans for the distributed.net network.

Re:hmmm

Don't waste your idle cpu power looking for ET -even if you find an ET signal the results immediately applicable.

Help out cancer research right now with these projects:

Folding@Home [stanford.edu] and United Devices [purdue.edu].

Help out their customers !

while seti is truly for the benefit of mankind, who is gonna really benefit from a cure to cancer, you think that cure is going to be dispensed for free ? even if the rest of the world solves the problem for them ?

while they do say they will not sell the results to drug companies , how are they going to distribute and manufacture these drugs, who will be in charge of pricing, how do you price a drug that is the cure for one of the most horrible diseases on the planet ?

the trouble i have with United devices is they call their relationships with these research groups "customers"

taken from their license agreement

Intellectual Property Rights. Member acknowledges and agrees that both the Licensed Program and any data distributed to Member's computer for processing constitute confidential and proprietary information belonging to UD and/or its customers and partners ("Customer/Partner Data"), and contain trade secrets and intellectual property protected under United States copyright and other laws, international treaty provisions and laws of other jurisdictions. Member agrees not to remove, obscure, or alter any notice of patent, copyright, trademark, trade secret or other proprietary right in the Licensed Program or Customer/Partner Data. This Agreement does not grant Member any rights in connection with any trademarks or service marks of UD or its customers and partners.

so AFAICS the data is a trade secret and of course you sign away all rights if a cure is discovered to them , remember finding the cure to cancer is akin to having a license to print money.

also

Incorporated Software. The Licensed Program may contain software from one or more third parties. Use of such third party software is subject to the terms and conditions of applicable third party license agreements, if any

meaning spyware ? who exactly am i donating my cycles to ?

maybe iam cynical i just think this project is not going to help many people except the drugs companies and those people who can afford the drugs, and you will buy them or you will die , pretty good sales incentive egh? ,

Remember the fight Africa had to get Aids drugs for cheap ?, and remember that wasnt even a cure all that drug did was treat the symptoms, so imagine how hard the people that need it most are going to fight when an actual cure is found.

ironically when a few people get anthrax attacks in the western world there is suddenly a drug available for free in massive quantities.

Sorry, while i agree that finding a cure for cancer is a good thing(TM) , this company (as in profit driven) just leaves a bad taste in my mouth, at least with the seti project no big corp is going to benefit financially from disovering there is other intelligent life out there and then hold the rest of the world to ransom with a chequebook as a release term.

Re:Are they going to share the prize?

Hmmm... as it says here [distributed.net]:

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:More worthwhile?

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.

Congratulations

While this is an admirable achievement, I found another distributed computing project which I think is more worthwhile -- namely, Folding @Home [stanford.edu], 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.

I think many posters here are missing the point

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?

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..."

Distributed.net no longer in the public eye

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

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" [distributed.net] turned in the key.

Again in July 2000, Team RC5 Chile [distributed.net] 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

Nugget is wrong, the false positive was actually found three times. Most recently, the [e-mail] 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)

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.

Sponsored by your local electric company...

300 Watts * 1 million hours = 300,000 kilowatt hours. 300,000 kilowatt hours * $0.10 = $30,000.

I wonder how many U.S. and Iraqi soldiers died to make this great display of wasted energy possible.

False positives in RC5-64

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 [e-mail] 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.

Lets see $10,000/1million= :(

In further news all participating Distributed.net users will be issued a check for 1 Cent.

LOST: RC5 block crunching machine

I left a machine turned on at one of my former jobs, and it's crunching rc5 blocks still.

I HAVE NO IDEA WHERE IT IS!

Is there any way to find out where the rogue machine is? heh..
It's submitting about 200 blocks a day. I just wish that I could FIND it...