[Retric]

We can't really store that many passwords. It's even just 30^14 = 500 exabytes per byte and MD5 is 16 bytes at a minimum so you need 8000+ exabytes = 8,000,000,000+ Terabytes.

Note: only "In the third quarter of 2016, approximately 144.6 million hard disk drives were shipped worldwide" aka something like all HDD ever produced might fit that much data.

PS: Plus that 30 was low balling for a full search space it's 26 (lower case letters) + 26 (upper case letters) + 10 (numbers) + some number of special characters. So, ~100^14 or ~20,907,515x as large aka 10^17 TB.

[TheCoelacanth]

You don't have to store all of the possible passwords, just the hashes for all of the real passwords that you are trying to crack.

[Retric]

If you mean after generating a hash you can compare it to your list of hashes then that saves time for cracking every password, but it's slower than cracking one password. Assuming you wanted to crack every Facebook password this way, that's not going to fit into cache and a binary search into RAM is actually rather slow. Yea, you could have more computers doing just this, but it's much slower than computing the hash in the first place.

[TheCoelacanth]

You wouldn't need to do a binary search. The values are already MD5 hashes. You could do a hash table lookup in just a few CPU cycles since computing the hash is free.

[Retric]

Good point, though at a minimum you need to touch main memory twice which is 200+ clock cycles. And in practice that O(1) has an much worse constant factor.

[throwaway76543]

There's no need to store anything. You have a list of hashes you'd like to reverse. You compute the entire search space and compare each.

No storage, other than the hashes you're attempting to reverse -- which for a data dump from even a large site like Yahoo wouldn't be very large at all. Megabytes.

[Retric]

Not at the same hash rate. Sure you can do binary search, but 100^14 or even 30^14 such searches is not fast. So, it's about as fast if you want 2 passwords but not 2 billion passwords.

[TheCoelacanth]

It wouldn't be a binary search, the values are already hashes, so you could do a hash table lookup very cheaply. MD5 isn't great by cryptological standards, but it is extremely robust by hash table standards.

While no extra resources might not have been strictly accurate, the lookup would be practically free compared to the time it takes to compute the hash.

[Retric]

In the example I gave the hashes don't fit on GPU's and for your hash table lookup you would need ~64GB of ram to do the hash table lookups. You can scale this across multiple machines but even the ideal case of 2 lookups to main memory * 100^14 is slow and thus expensive.