RED ALERT - MD5CRK is 200 Year D.net in disguise?!

[Minty]

Figured this out yesterday, but thought I'd wait until Friday 13th to spill! Hopefully I've made a mistake in the maths somewhere that someone can point out, although much of this is just running through the website stuff ;).

There are 2^128 (3.4x10^38) possible MD5 values, and by the Birthday attack probability of collision approximation 2.16x10^19 outputs are needed before a collision is likely. Using a distinguished point identification method (similar points) the amount of data needed is 4.29x10^9 less i.e. (2.16x10^19 / 4.29x10^9) = 5.03x10^9 DPs needed. That's more than 5,000,000,000 DPs necessary to crack MD5, and we haven't even reached 10,000,000 yet!
Graphically, even if we take a number of digests with a probability of 0.4 of a collision (2^64) we find that -
2^64 (digests to collision) / 4.294x10^9 (digests per DP) = 4296 million DPs needed (reasonably close to 5000 million as above).
4296 million DPs / 100,000 DPs per day / 365 days a year = 117.7 years! And that's not even a realistic estimate bearing in mind 100,000 DPs a day is an over estimate and a probability of 0.4 is poor (Murphy's Law!).

A more accurate figure would probably be around 235 years :shocked: (and that's 0.85 probability and still 100,000 DPs per day!) Using today's rate for D.Net they'll only take 880 years to check all the keyspace! (what's a few hundred years between friends?!) :rotfl:

I was wondering if someone could pass comment on the figures - I'm right aren't I? Maybe jlcooke could help out on the clarification of things?

[Digital Parasite]

I think 200 years at our current rate sounds about right. :cry: But this project is new and doesn't have a lot of horsepower compared to many other projects.

If we had the same power as d.net, we could finish within 2 years.

Jeff.

[magnav0x]

I'd have to agree with Jeff. What did you expect from such a big math project with such little publicity?

[Minty]

I didn't really believe the figures myself - I certainly didn't expect upwards of 235 years @100,000 per day! (At a million a day, that's still more than 23 years). In fact, I was under the misapprehension that it was 25 million DPs we needed!!! (I think I can be forgiven bearing in mind I hadn't looked too closely - others may be in the same boat so this lets everyone know the situation.)

>If we had the same power as d.net, we could finish within 2 years.

Wow - you weren't kidding - if d.net converted to md5crk we'd get over 10 million DPs per day and finish within 2 years easily! However, don't forget that dnet is well established and comparing to this is always going to be unrepresentative.

One last point though regarding the cost of running the project. Taking a P4 2.26GHz as an example (it should be quite representative of a power efficient cruncher), it uses 39W more power on 100% CPU than idling and therefore (assuming better than reality 10Mmd5/sec) uses 23.86 x 39/1000 = 0.93 units (kWhrs) per 200DPs i.e. 4.65 milli units per DP. At 5x10^9 DPs necessary then this means 23.26 million kWhrs used @10 cents per unit this comes to 2.33 million US dollars! This should be halved to take into account those that heat their homes with the CPU heat for half the year i.e. 1.16 million dollars!!! This is an absolute minimum possible figure assuming that people augment their heating for half the year, and only when on anyway, and this rises dramatically ($6 million+) as people start racing each other and leaving machines on when they're not needed (because the increase is not 39W more than normal but maybe 100W and more - and that's just with the PC not the display on). And even then we're ignoring things like equipment failure costs and cooling the place in the summer with aircon.
I guess what I'm trying to say is it would be more sensible to build the cracker machine (if feasible) than run the project, but funding would always be an issue (couldn't CertainKey cough up - offset partial cost against tax and get the kudos?).

[jlcooke]

The cost of making a dedicated MD5CRK machine has been showen to cast only $100,000USD. Much cheeper than using standard PC hardware.

Also, d.net is trying (IMHO) to do something of little-to-no value. 72bit algorithm (2^71 complexity vs 2^65 for md5) on an algorithm almost no-one uses. Too bad.

[echoray]

In the long run, we will perform much better than those equations suggest. MD5crk is getting new users and machines everyday, and participating machines are upgraded with faster hardware.

Are there any statistics available about how MD5crk's computing power in terms of GFLOPS and GigaMD5's has developed over time? Is it linear/exponential/whatever growth?

[Minty]

Originally posted by echoray
In the long run, we will perform much better than those equations suggest.:D - much faster than any of us believed!!!
Who would have thought that less than 4 days after predicting a 200 year end, things could have changed so much! :rotfl: :rotfl: