## Birthday Attack and Storage

The fear of every surveillance society: citizens protecting their own privacy with strong cryptography

### Birthday Attack and Storage

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?
"If I ever start a software company, I'm going to replace desks with toilets. I do my most inspired programming in the bathroom."

New User

Posts: 27
Joined: Wed Jan 06, 2010 12:22 am
Blog: View Blog (0)

### Re: Birthday Attack and Storage

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

tgoe
Contributor

Posts: 715
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)

### Re: Birthday Attack and Storage

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.

HTS User Composition:
95% Male
4.98% Female
.01% Monica
.01% Goat

sanddbox
Expert

Posts: 2344
Joined: Sat Jul 04, 2009 5:20 pm
Blog: View Blog (0)

### Re: Birthday Attack and Storage

sanddbox wrote: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.
"If I ever start a software company, I'm going to replace desks with toilets. I do my most inspired programming in the bathroom."

New User

Posts: 27
Joined: Wed Jan 06, 2010 12:22 am
Blog: View Blog (0)

### Who is online

Users browsing this forum: No registered users and 0 guests