RC5-64 Success 410
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.
Brute Force vs design flaw (Score:3, Interesting)
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?
Re:hmmm (Score:2, Interesting)
32,504 800 MHz G4 vs. 45,998 2 GHz Athlon XP? (Score:2, Interesting)
800 MHz G4 is faster crunching the keys than a 2 GHz Athlon XP
I am reading that right?
an interesting bit of trivia (Score:5, Interesting)
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.
Let's check the math... (Score:2, Interesting)
Cracking RC5-64 took 384,000 computer/hours today. There are 168 hours in a week. So, for one computer to crack RC5-64 in a matter of weeks (less than five) would require a computer about 460 times faster than what we have now; assuming moore's law keeps going, we'll get those in about 13 years (2015).
In five years (48 months), computers will be about 2.6 times as fast powerful as they are now; it'll still take over 147,000 computer-hours to crack the same code; one computer would take 16 years to crack that.
(The same 2000 computers, once upgraded, could replicate their feat in a measly 654 days--still, two years.)
And, of course, this assumes that Moore's Law remains constant, there's no overhead, and distributed.net's brute force test is a good example; it could have gotten lucky, or it could have taken them an unusually short time to find the right code.
For a realisitic cracking scenerio, let's say our cracker has ten computers and wants to crack the code in a week... he'd still have to wait 8 years to be able to do it, and who'd want to bother with 13 year old data for cracking, anyway?
Re:hmmm (Score:3, Interesting)
End of an era (for me, anyway) (Score:4, Interesting)
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 (Score:5, Interesting)
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:an interesting bit of trivia (Score:5, Interesting)
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.
Re:Let's check the math... (Score:2, Interesting)
So, for one computer to crack RC5-64 in a matter of weeks (less than five) would require a computer about 460 times faster than what we have now; assuming moore's law keeps going, we'll get those in about 13 years (2015).
You forget THE major point of Distributed.net: distributed computing. If you put 2 computers to the task, you already cut by half the time needed. Have more money? Put 3000 CPUs (go read the nVidia and ATI tour at Anandtech to see if somebody can afford those now) through it, and the time will shrink by the same amount.
And regarding the time needed to crack it, I get a couple orders of magnitude greater than 384000 computer*hours. More akin to (quoting the PR) 46000*790*24=872 million computer*hour (using an Athlon XP 2GHz). A single CPU computer wouldn't be able to do it on a human scale time (would be about 100000 years), you absolutely need more than one computer to live to see the result.
For a realisitic cracking scenerio, let's say our cracker has ten computers and wants to crack the code in a week... he'd still have to wait 8 years to be able to do it, and who'd want to bother with 13 year old data for cracking, anyway?
I probably miss something about why the 8 years becomes 13, but there are some things that don't change in time, and could be used by somebody even in a few years. My credit card number hasn't changed since I first got it, same thing for my bank account. The goal is not for it to be secure only now, but also in the future. You may think about other examples involving national security if you prefer.
Re:G4 800 faster than Athlon 2Ghz?! (Score:2, Interesting)
*also referred to as VMX by IBM and Velocity Engine by Apple
Re:Yea!!! (Score:3, Interesting)
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.
Clients turn off? (Score:2, Interesting)
Anyhow, my client just starts, tries to connect to the server and gets and error message like the following...
[Sep 26 17:32:37 UTC] NetUpdate::Connect handshake failed. (0.168)
So atleast it's not going to sit there and make up random keys anymore. It may have been a slight security risk (possibly) but maybe dnet should've sent a special request that would show a little message when you click on the cow (or make the cow change color so you would click on it.. ie Chocolate cow) so you'd know to uninstall it if you wern't paying attention to the news.
Oh well, I've been doing rc5 since my junior year of high school and have a lot of memories of installign in, uninstalling it, taking over a friends install, and him taking over mine. It was a lot of good times for this little silly program... installing it on all the computers in high school was a blast. It was truly a great forum to bring a lot of geeks together. The Slashdot team, 2600, FreeBSD and Linux Groups... all competing in a silly encryption game. :)
Re:False positives in RC5-64 - SO IS NEXT? (Score:3, Interesting)
Re:G4 800 faster than Athlon 2Ghz?! (Score:4, Interesting)
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? (Score:4, Interesting)
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:End of an era (for me, anyway) (Score:1, Interesting)
The time I sneaked the client onto all 250 machines at work for a week... before I got caught by a lesser admin and was forced to disable them all (easy cos there was only a single instance launched from the LAN and run entirely in memory).
Racing my friends keyrates and total blocks. I even had a machine still submitting blocks 2 years after I left a site I was working on - that machine must be smokin'!
Re:G4 800 faster than Athlon 2Ghz?! (Score:4, Interesting)
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:Distributed.net no longer in the public eye (Score:2, Interesting)
RC5? How uses that? Really. The DES challanges were at least interesting because you could go to work the next day and say "hey! d.net checked this algo, don't use it!"
So I say d.net needs to move back to attacking an algorithm people use everyday. Don't think they could do it?
Cracking MD5 wide ope can be done in 2 years [certainkey.com] using the same number of people at the RC5-64 project. And you'll get millions of cracks in the algorithm and not just one.
We'll see what nugget says...