Daunting figures for RC5-72! Simple math fun!

[JHutch]

Ok, we all now that the upcoming distributed.net RC5-72 contest is going to be a lot harder than the RC5-64 contest we just finished...

But how many of you have actually "run the numbers" to see just HOW much harder?

Well, I did. And it is rather ... daunting.

First of all, we finished 82.77% of the keyspace in RC5-64 before reaching the key. That took 1726 days. If we extend that out, it "theoretically" would have taken us 2085 days to finish the entire 100%.

Now, every time you add a number to the bits in the key, you DOUBLE the length of the keyspace. For instance, a RC5-65 contest would have exactly twice as many keys as the RC5-64 contest did. A RC5-66 wouldn't have 3 times as many, it would have FOUR times as many (2 to second power). The upcoming RC5-72 contest has 2 to the 8th power as many keys, or 256 times the number of keys in the old RC5-64 contest. See where this is going?

To get 100% of the keys in RC5-72 done with current processing power, it will take us 533,760 days. Thats 1,462 years!

Ok, who plans on seeing this one thru to the end?

JHutch

 

[Mardeth]

Well if they invent how to use quantum mechanics(?) in about 15-25 years in computers it probably wont take to long to solve it. Because those can count 4.1 billion times faster than the fastest CPU on the market at the moment.

 

[NicColt]

I say just skip over RC72 and just start RC128. Perhaps in several hundred years from now it will be known as the most monumental waste of time and resources project known to man.

 

[networkman]

Okay, based on this info, can someone explain to me why we can't just implement the coding of RC256(to take into acount near-future-advances) , call it secure and be done with it?

 

[DJSnairdA]

Originally posted by: NicColt
I say just skip over RC72 and just start RC128. Perhaps in several hundred years from now it will be known as the most monumental waste of time and resources project known to man.

LOL! I'm sure there is a bit of meaning to the project.... somewhere..

Maybe the guys running the project just haven't told you yet

 

[Spleenus]

What they don't realise is is that I crunch with the Borg Collective, and can assimilate it all very fast. Resistance is futile!

Now, if only I could persuade the borg to crunch seti

 

[Robor]

Are they really going to start a project like that? I don't want to say it's pointless but I'll ask the question, what's the point? I do SETI (and some DF) and I realize that SETI might not be "top dog" as far as DC projects with direct benefit to mankind. That said, even I can point the finger at RC5-72 and say "that's a waste of CPU power". RC5-64 came out long before most of the other DC projects we see today. It was new and cool and a lot of participants jumped in and stuck with it. I respect that but what's Dnet thinking now? Why do it again when there's so many "better" options available today?

**NOTE** Please understand I don't say this to trash anyone who did RC5-64. Heck, I even helped out in the failed attempt to keep the DPC at bay. My point is I think it's stupid for Dnet to begin another "math" project when there's plenty of other more "worthy" DC projects that can use the CPU power.

 

[ProviaFan]

Originally posted by: Robor
Are they really going to start a project like that? I don't want to say it's pointless but I'll ask the question, what's the point? I do SETI (and some DF) and I realize that SETI might not be "top dog" as far as DC projects with direct benefit to mankind. That said, even I can point the finger at RC5-72 and say "that's a waste of CPU power". RC5-64 came out long before most of the other DC projects we see today. It was new and cool and a lot of participants jumped in and stuck with it. I respect that but what's Dnet thinking now? Why do it again when there's so many "better" options available today?

**NOTE** Please understand I don't say this to trash anyone who did RC5-64. Heck, I even helped out in the failed attempt to keep the DPC at bay. My point is I think it's stupid for Dnet to begin another "math" project when there's plenty of other more "worthy" DC projects that can use the CPU power.

Good point. Unless major advances are made in computing power Real Soon Now (TM), RC5-72 will be a long time in getting completed (unless they get lucky and find the key toward the beginning of the contest).

 

[ViRGE]

Realize how daunting RC5-64 looked when it started though guys. It started on Oct, 23, 1997. We're talking about Pentium MMX's being brand new that year. On top of that, the clients weren't as optimized as they are now; the MMX client hadn't be developed yet among other things. It may look bad now, but Dnet is saying that they expect this to take less time actually.

 

[Rattledagger]

Hmm, isn't it every 18 months the cpu-power has doubled...

...This will atleast cut down a little bit of the time...

 

[mastertech01]

Originally posted by: Robor
Are they really going to start a project like that? I don't want to say it's pointless but I'll ask the question, what's the point? I do SETI (and some DF) and I realize that SETI might not be "top dog" as far as DC projects with direct benefit to mankind. That said, even I can point the finger at RC5-72 and say "that's a waste of CPU power". RC5-64 came out long before most of the other DC projects we see today. It was new and cool and a lot of participants jumped in and stuck with it. I respect that but what's Dnet thinking now? Why do it again when there's so many "better" options available today?

**NOTE** Please understand I don't say this to trash anyone who did RC5-64. Heck, I even helped out in the failed attempt to keep the DPC at bay. My point is I think it's stupid for Dnet to begin another "math" project when there's plenty of other more "worthy" DC projects that can use the CPU power.

Amen brother. Many of the original crunchers of RC5 have grown older and more mature, and realize that lives are worth saving, and other projects are dedicated to do just that. If it hadnt been for RC5 those projects may never have been created, but now its time to set aside RC5 and SETI and do something that benefits mankind before we burn out on computers all together, or start hearing voices from outer space.
:Q

 

[Assimilator1]

but now its time to set aside RC5 and SETI and do something that benefits mankind

Re SETI,err no it isn't ,SETI will benefit mankind one day & I & some others have no intention of setting SETI aside,RC5 64 is finished,SETI has only just begun.SETI isn't just about finding ET its also a quest for knowledge.

Virge
What was the predicted finish time when RC5 started?

 

[lane42]

To get 100% of the keys in RC5-72 done with current processing power, it will take us 533,760 days. Thats 1,462 years!

Even with everyone running 5 to 10 Gig Processer's, it would take Hundred's of years :Q

 

[PieDerro]

Wow... I'd do it if there was interest in it. But as the interest seems to be with SETI, and I have a keen interest in Sci-Fi and Space in general, I'll stick with that.

I think it'll only take about 10 years or so to complete - that is assuming it gets the same volume of participants as RC5-64 had. That, I don't think is going to happen. Give it a hundred years - or at least until Quantum Computing becomes commercially available. Then the project will end in a hurry!

 

[ProviaFan]

Originally posted by: Assimilator1
but now its time to set aside RC5 and SETI and do something that benefits mankind

Re SETI,err no it isn't ,SETI will benefit mankind one day & I & some others have no intention of setting SETI aside,RC5 64 is finished,SETI has only just begun.SETI isn't just about finding ET its also a quest for knowledge.

Virge
What was the predicted finish time when RC5 started?

I wouldn't do SETI because of the search for ET part of the project, but SETI is about a good deal more than just that. Therefore, I might still consider it as a project to do after ECCp finishes, although I'll be more likely to go with Folding@Home or DF.

 

[Pink0]

To get 100% of the keys in RC5-72 done with current processing power, it will take us 533,760 days. Thats 1,462 years!

Ok, who plans on seeing this one thru to the end?

You're missing a very important factor in your math. Moore's Law. CPU power will double every 18 months. Yes, this applies to our previous attempts but also consider this:
In the next few years, CPU power for DC projects will double every 9 months.

Take a look at the power PC G4. Because of its many, many registers a 1ghz G4 is able to smack down an athlon or p4 running at twice its speed. In fact, the g4 is around 3 times faster in RC5 and ECCP. This has nothing to do with real world performance but only these two projects because of all the registers available to it. That's great but how does that help us PC users? Why, hammer of course. Hammer will have twice as many registers and the extra 8 registers will be double the size!!!! RC5 and ECCP (and the like) can take such advantage of this. Performance should double once properly optomized. Hammer will also introduce SSE2 finally to the other half of the market.

Hyperthreading is exactly the kind of optomization that DC needs the most. These projects can be nearly perfectly optomized for hyperthreading and should see a 60% performance increase just by using that extra FPU, IPU. When the 3.06 P4 is released and the software is properly optomized, that's a potential 60% increase in processor performance in ONE WEEK!

The next step for AMD once they've moved their Opteron onto the .09 process is dual cores. Intel's talking about 4 cores for itanium. Since these projects are almost entirely CPU bound you can surely see the potential.

Since the beginning of DC, CPU speed improvements (on the desktop) have largely come in the form of more megahertz and instruction optomization. In the next 2 years, we are going to see a trend toward continuing this tradition AND increasing speed through using all of the processor at once wherever possible (DC), multiple cores, and 64bit.

You simply can't take the ammount of time from a project that's in the past and apply it to a project that's in the future. It just doens't work because the larger project will be using faster computers. It should take around the same time to do this project as the last as long as computers continue to scale the same or better.

2085 days. If for the next 4 years, we see 9 month doublings, it will take 2085 days. That's 5.71years! there's an extra 1.71 years which is slack to account for not meeting the doubling of performance every 9 months.

We'll get there a LOT sooner than you think. I promise

 

[Pink0]

Sorry I just re-read that post and relized how meandering and confusing it is. Basically here's my point. Forget all the technical stuff.

erm....your math sucks dude.

See, you're assuming that the same conditions will exist at the start of this new project as the last one. That means that you're assuming that everyone will be starting out with 486s and early pentiums!!! NO WAY MAN!
Also, you're assuming that we will start out again in the early days of DC when very few people did it. No, we'll be starting with the large userbase we have now and going up from there.
It will take the same ammount of time to do this project as the last one. Yes, the encryption is much tougher than the original. We're also starting out with computers THOUSANDS of times faster than the ones we started the original project with and with several times the installed user base.
Re-think your math.

 

[Assimilator1]

No, we'll be starting with the large userbase we have now and going up from there.

Are you by chance a member of RC5 HQ's?

 

[DJSnairdA]

Originally posted by: Assimilator1
No, we'll be starting with the large userbase we have now and going up from there.

Are you by chance a member of RC5 HQ's?

Must be, he seems to be referring to "we" all the time :Q

 

[Slatzman]

pinko...no need for the attacks on jhutch...I don't think he was attacking you or the project.

but, I personally fail to see the point of the project, if we all know there is a key that can be found with brute force computing, why not just rent time on one of the supercomputers out there (Cray's are the only one that come to mind right now) and solve it that much quicker.

What are we going to prove by solving this one in 2, 5 or 100 years. At least with Seti or D2OL there is the thrill of possibly finding the proof of alien life or the next drug to fight anthrax.

Just throwing out my $.02

Slatz

 

[RemyCanad]

If I remeber right SETI has to send out copys of things to be calculated becuase they have to many computers running it. So it would seem to me that SETI is a waste also.... A waste in the same fashion that RC5-72 is. Its all about the stats race. If you really cared alot about if you were helping a great cuase wouldn't you switch over to something trying to solve cancer or aids or something?

Just my 5 cents.

 

[Robor]

Originally posted by: RemyCanad
If I remeber right SETI has to send out copys of things to be calculated becuase they have to many computers running it. So it would seem to me that SETI is a waste also.... A waste in the same fashion that RC5-72 is. Its all about the stats race. If you really cared alot about if you were helping a great cuase wouldn't you switch over to something trying to solve cancer or aids or something?

Just my 5 cents.

I do SETI and I can't really argue with your point but Berkeley has done things to fix this. The current client now analyzes more data than previous versions. I believe their original intent was to reduce the need for bandwidth and by analyzing more the WU's take longer. However, SETI is winding down and I'll guarantee you SETI@Home 2 will be looking for a lot more stuff than the original.

 

[Pink0]

pinko...no need for the attacks on jhutch...I don't think he was attacking you or the project.

I wasn't attacking anyone. I was simply correcting him. It's fear uncertainty and doubt (FUD) like this which will drive people away from a valid project simply because they can't be bothered reading up on it or make invalid assumptions such as has happened here.

Anyway, there is definitely a point to RC and ECCP. As you can tell from distributed, different methods are used to find keys through the distribution of blocks which is not possible to simulate on CRAY. Also, this is an accurate similuation of a real-world attempt at a crack. A group of people (terrorists let's say) aren't generally going to have access to a CRAY but they do have enough computers (through a virus or adware maybe) to do a DC project. Most people believe that RC and ECCP is just about seeing how long it will take to break the key. It's important to gather statistical data about this since it is possible to find the key with less than 1% of the keyspace processed and we need to know how likely this is. Information about the effectiveness of the varying methods for block distribution will help to improve crypogrophy and make it harder for DC attacks to crack a key. From the index you'll see information about this:

"The "Bovine" RC5 effort was formed to take the responsibilities of coordinating and maintaining the RC5 servers that are needed to distribute key blocks to work on to all of the participating client programs. We depend heavily - entirely - on the participation of people like yourself, as we intend to solve this project via the use of brute force, trying every possible key there is.

We know this method works! On 19 October 1997 at 1325 UTC, we found the correct solution for RSA Labs' 56-bit secret-key challenge. (That's RC5-32/12/7 56-bit for you stats junkies.) The key was 0x532B744CC20999, and it took us 250 days to locate. Then, on 14 July 2002 at 0150 UTC we found the winning key for the 64-bit secret-key challenge. That key was 0x63DE7DC154F4D039 and took us 1,757 days to locate. "

 

[RemyCanad]

Well its time for me to get to calculating. I don't see why we cannot calculate the time it will take. We have two other processed keys. We have a good idea of the rate technology will increase. Add in the transition from 32 to 64 bit.... Do some math here, some math there and bam you can get a nice graph.

 

[JHutch]

Ok, Pink0, I'll respond... politely.

First, take a look at my DNet stats. I've done literally millions and millions of DNet blocks over the years. I've been around for quite a while and I've never been a DNet basher (except for the whole fiasco with Dave).

Second, the "simple math fun" part of the subject line should have let you in that I did a very simple extrapolation of RC5-64 numbers. I didn't take into account increasing CPU power (see "with current processing power").

Third, you are mistaken on why the G4 is so good at RC5 (and it really is ONLY RC5 that it is so good at). The number of registers in the G4, while a "good thing," are not the reason that the G4 is such a monster. It is because the G4 can do what is called "bitslicing." The G4 can perform the necessary rotate instructions on very large chunks of data (128bit wide) which basically means that the G4 crunches 4 keys at once instead of the 1 key that most any other processor does. This is the same bitslicing that the old DES contest clients used. A regular Pentium CPU could take the shorter DES key at run 4 of them in the same place that it could run 1 RC5 key. Now, the problem with bitslicing is that as the key gets longer, it can grow beyond the CPU's ability to bitslice it. The jury is still out on the G4 if it can bitslice a RC5-72 key. One of the DNet guys made a comment a while back that they hadn't tested the G4 RC5-72 client yet, so he couldn't say if bitslicing was still possible. If not, the G4 keyrate goes down to 25% of what is was. Personally, I'm hoping the G4 can still bitslice RC5-72, because it'd be a shame to lose that much processing power.

Fourth, I really have to take issue with your 9-month doubling assumption. Even if we assume that the hammer will be able to bit-slice like the G4 (and honestly, I'd be surprised if it could, even with 64-bit x86 code), that is a one time pick up. You don't get that increase every 9 months. you get it once and that's it. Also, hyperthreading is going to help DNet (and SETI and many other projects), but it is also a one time increase, not every 9 months. I also don't see it increasing as much as you think. I'd hazard a quess of 25% increase at the most by going to hyperthreading in the DNet client. Maybe less. But since it hasn't been truly tested yet, I'll be optimistic with you and say it gets a 1 time doubling of power. Still not every 9 months. The last one, dual (or more) cores on one CPU. For the near future (i.e., the next 2-3 years), I'd be shocked if the dual core phenomenon is anything but a server chip thing. Beyond that, when it starts becoming feasible on the desktop, I'd say there can be a definite argument that dual core will be the next thing that helps keep Moore's Law moving, not necessarily speeding it up any faster. Remember, Moore's Law has held true for a LONG time, through a LOT of great advances. Just the amount of time it takes to develop new chip technologies would make it very hard to move forward to a 9 month doubling.

That all being said, will RC5-72 take 1,462 years? Heck, no! Was that the true point of this post? Heck, no! The whole point was to have a little fun with the numbers and show people just how much more work is going to be required for RC5-72. Because, no matter how fast computers work, checking the whole RC5-72 keyspace is still 256 times the number of possible keys. Do I think RC5-72 will be over in the 2085 days that you speculate? Very possible. Will they have checked all 100% of the keyspace in that time? I very, very much doubt it.


One thing I did like about reading through the responses in this thread, is that people are willing to question DNet's direction. And even more important, they have alternatives to support that are more to their liking. Personally, I perfer OGR to RC5, but since DNet has put fixing the OGR client on the back-burner, I'm supporting some other projects (SETI) with my fleet for now. RC5-64 served it's purpose as a proof-of-concept, if nothing else. I just don't really see a purpose for RC5-72.

JHutch