Birthday Attack and Storage

[raddy1313]

Hey guys,

I just submitted an article detailing the probability and statistics behind the birthday attack. While I understand the concept behind it, I still have a question.

For MD5, a 128-bit hash, we must generate 3.1e19 hashes for a 75% chance of finding a collision. However, since the whole point of it is to check the hashes against one another, that means we have to store each hash so that we can compare it later. So with 3.1e19 hashes at 16 bytes per hash, that works out 430 exabytes. That isn't remotely feasible to store the hashes, much less the strings that generated each hash, so how do they do it? Do they use some form of data compression to accomplish this? Any information about this would be greatly appreciated.

EDIT: Never mind, I think I figured it out. Rainbow tables, perhaps?

[tgoe]

yeup, add semi-abstract stuff like social engineering and post-mortem analysis and the playing field seems a bit more level.

[sanddbox]

I think I've got it.

Say your bruteforcer guesses 'a' and then guesses 'b' and then guesses 'c'...and you get the idea.

Assuming it goes in an order, (a-z, aa, ab, ac, etc), then all you would need to store in memory would be the very last attempt. From there, you could figure out the next password to guess.

Now, this is just something that I randomly thought of; I'm not sure if that's how it's actually done.

[raddy1313]

I think I've got it.

Say your bruteforcer guesses 'a' and then guesses 'b' and then guesses 'c'...and you get the idea.

Assuming it goes in an order, (a-z, aa, ab, ac, etc), then all you would need to store in memory would be the very last attempt. From there, you could figure out the next password to guess.

Now, this is just something that I randomly thought of; I'm not sure if that's how it's actually done.

I understand that for matching a hash through brute-forcing you can discard each hash in turn, but when you're working to generate a hash collision (match ANY two hashes), you have to store each hash you calculate to be compared later (at least I assume so), like this:

1. Hash is generated.
2. Hash is compared to a table of hashes.
3. If no match is found in the table, the new hash is added to the table.
4. Goto 1

Since you have to calculate the absurd number I mentioned above to have any decent probability of finding a collision, I was just curious how they stored them. I've been learning about rainbow tables and I think I've got the basic gist, but there are still some parts I don't get.