Slashdot Mirror
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.
Link here: http://www.distributed.net/pressroom/news-20020926 .html
Funny. The RC5 algorithm has just been removed from OpenBSD because of copyrights.
{{.sig}}
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.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
So tell me, was the answer "42"?
Does this mean I can go back to alien hunting now?
Kevin Fox
I'd say not.. in several years time, the average laptop / home PC will be able to crank out the work that the distributed project did in a week or so... meaning in a few years, an individual will be able to decrypt RC5-64 data in a realistic timeframe for (mis)use.
That's the point.... is RC5-64 (effectively) safe today? It sure the heck is.. this project proved that! Will it be safe in 5 years? Heck no, and that was the point.
Department of Homeland Security: Removing the rights real patriots fought and died for since 2001
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.
/. 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.
Of course, some on
"Destroy science and religion. Science would re-emerge exactly the same; but not religion." - Penn Jillette, paraphrased
I don't know why the parent was modded up as funny, but:
There is a difference between saying "in theory, we could do this and that" and actually doing it.
Cryptography specifically is a realm of arbitrary large numbers, theoretical math way, way beyond what 99% of people ever learn in both school and university, and lots of guesswork, estimates, approximations, you name it.
I don't think anyone is really surprised by the outcome, but nevertheless, the only real proof that something can be done is and always will be to actually do it.
Assorted stuff I do sometimes: Lemuria.org
- 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.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..."
The Online Slang Dictionary
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..
"Truth is not decided by majority vote" consensus gentium -- Norman Geisler
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?
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.
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.
"Tell me doctor, with all of your defenses, are there any provisions for an attack by killer bees?"
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.
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.
Don't waste those cycles! Put them to use! http://www.distributed.net/
Wow, this stuff blew all those machines and you still want to do it? :-)
Try NetBSD... safe,straightforward,useful.
In further news all participating Distributed.net users will be issued a check for 1 Cent.
ASCI White (or, even better, Japan's new super computer) could probably crack RC5-64 in a matter of hours.
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).
Now we should see project OGR really kick into gear!
Code, Hardware, stuff like that.
Our peak rate of 270,147,024 kkeys/sec is equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP machines
Am I missing something here? Are they claiming the 800mhz G4 is over 1.4 times as fast as an Athlon 2ghz??
Looks like the writer has been exposed to the "Steve Jobs reality distortion field" for a little too long...
Code, Hardware, stuff like that.
Of course, ASCI White (or, even better, Japan's new super computer) could probably crack RC5-64 in a matter of hours.
According to D.Net's press release, the peak rate achieved by D.Net on this effort was equivalent to ~46,000 2GHZ Athlon XP's working in tandem. Can even ASCI White or Japan's supercomputer match this sort of processing power?
I'll admit that the RC5-64 project had very little practical use, but it was a heck of a proof-of-concept in terms of people's willingness to donate vast amounts of CPU time and the staggering amount of otherwise-wasted computing power that's out there and waiting to be utilized.
I'd stuck with D.Net over the years even as more useful distributed applications cropped up, out of some sort of loyalty since I'd already invested so much (CPU) time in it. Now, I think I'll pick a more "useful" application like protein folding or something to occupy my spare cycles...
OtakuBooty.com: Smart, funny, sexy nerds.
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.
BD Phone Home!
Shameless plug. Like you weren't expecting it.
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.
Don't waste those cycles! Put them to use! http://www.distributed.net/
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.
Rule #1 -- Politics always trumps technology.
You just wait and see who has the last laugh when SETI@home manages to detect an alien signal only to discover that it's rc5 encrypted! :)
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...