Comment by drblast | Hacker News Reader

Comment by drblast | Hacker News Reader

Parent Full thread

Some numbers for you.

Using non-optimized, managed code on my laptop, I just went through 250 million iterations of plain text in ten minutes. You didn't specify what counts as a character, but let's assume it's a printable ASCII character. 95^9 = 630249409724609375 possibilities.

Divide by 250 million, and we get about 2520997639 times ten minutes for the time it would take me to enumerate all possible plain text passwords. That's a long time, about 47000 years. Not going to happen today on my laptop. But if I were a government, maybe I'd get a few thousand laptops together and set about calculating this over the next five years or so. In 1997.

But if I were to throw some purpose built hardware at this problem or use the video card to speed this up and not just laptops with general purpose CPU's, it's very likely I could decrease this time by thousands of times.

At the end I's have all MD5's for all passwords, and now the problem becomes a rainbow table lookup. And I only have to do this once and I forever gain the capability to break any 9 character (and below) password with just a lookup.

And that's assuming that MD5 is a perfectly secure hash with no shortcuts allowing you to narrow down the input set.

Did some more calculations just for the fun of it. It looks like you'd need nearly 16 exabytes of storage to hold the MD5 table for every 9-character hash [1]. Not accounting for any database overhead. In high density, you can fit a petabyte in what now a days? Half a rack? So around 8,500 racks. Certainly in the realm of possibility for a government but it would be a lot for storing just one type of hash list.

[1] https://www.wolframalpha.com/input/?i=%28630249409724609375+...

I feel like there should be a more efficient way to store these things. You have a complete enumeration of possible inputs (passwords), but unfortunately we need to go in the opposite direction, so we couldn't just index into a n*9 bytes array. Depending on how well distributed the md5 hash space is, it's possible a prefix tree might save you a bit of storage (you'd only have to save a couple of bytes per entry to cancel out the overhead) but I couldn't tell you the numbers there. Otherwise I think you're right, and we'd just have to store a map of md5 -> password.

(Edit: Also being limited to alphanumeric for hashes and printable ascii for input gives you pretty good compression potential.)

They are actually much more complicated than just a big table of 'password | hash'. Check out https://www.freerainbowtables.com/en/articles/ for in-depth explanations.

That isn't how a rainbow table works, it doesn't need to store a hash, plaintext pair for every possibility.

Precomputed hash chains are a simplistic way of explaining how rainbow tables work. http://en.wikipedia.org/wiki/Rainbow_table#Precomputed_hash_...

> I just went through 250 million iterations of plain text in ten minutes

Oh I thought you were going to say per second. I can recall reaching 500 MHash on some 2008 nvidia gpu with barswf.

Anyway, you're right of course. A nine character password is not really military-grade safe for countries with a security budget like the NSA's. But 9 characters ought to be many, orders of magnitude easier than 40 characters, and md5 is many orders of magnitude easier than pbkdf2 even at a weak security setting. This md5 might just be within reach of governments, but 40 characters certainly isn't.

To continue a slight derail about MD5:

For some fun performance figures, check http://golubev.com/gpuest.htm

A new AMD Radeon™ R9 295X2 is pretty speedy, clocking in at 23GHash for single MD5 (there are cheaper per $, but this is extremely impressive imo). Dividing 630249409724609375H by 23e9H/s leaves us with 27e6s, or 0.8 years. That means we'd need 42 cards to crack it in a week, costing somewhere in the region of $80k (1.5k/card + extras). That puts us easily within the range of governments, companies and just generally rich geeks. You can get ~ twice the hashes/$ so maybe $40k, and if you're cheap about the computers you connect with then probably lower.

But that's consumer kit. There are also speedy MD5 FPGA cores, I've not got a great reference but found one from 2007 which did 44MHash / core using a Cyclone II which I can only find described as "built for low cost". Assuming a 5x cost/hash reduction would grab us at $8k which would be in the range of hobbyists.

Beyond this, several private companies have been able to build double SHA-256 ASICs (for bitcoin mining). You could buy a while ago kit that did 7GHash for $300ish, and there's supposedly some 1THash ones in development. Granted, double SHA-256 is not equivalent to MD5, but I'd be surprised if MD5 was significantly harder, and expect it to be a lot simpler. Now the development cost of these is the expensive bit, but then your hashing rate would be insane.

Ramble over, if anyone has any figures for FPGAs or ASICs then I'd be really interested.

Reply on news.ycombinator.com