Birthday Attack and Storage

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

Birthday Attack and Storage

Post by raddy1313 on Tue Feb 16, 2010 5:52 pm
([msg=35184]see Birthday Attack and Storage[/msg])

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."
User avatar
raddy1313
New User
New User
 
Posts: 27
Joined: Wed Jan 06, 2010 12:22 am
Blog: View Blog (0)


Re: Birthday Attack and Storage

Post by tgoe on Sat Feb 20, 2010 9:31 pm
([msg=35446]see Re: Birthday Attack and Storage[/msg])

yeup, add semi-abstract stuff like social engineering and post-mortem analysis and the playing field seems a bit more level.
User avatar
tgoe
Contributor
Contributor
 
Posts: 650
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)


Re: Birthday Attack and Storage

Post by sanddbox on Sat Feb 20, 2010 9:59 pm
([msg=35448]see Re: Birthday Attack and Storage[/msg])

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.
Image

HTS User Composition:
95% Male
4.98% Female
.01% Monica
.01% Goat
User avatar
sanddbox
Expert
Expert
 
Posts: 2331
Joined: Sat Jul 04, 2009 5:20 pm
Blog: View Blog (0)


Re: Birthday Attack and Storage

Post by raddy1313 on Sun Feb 21, 2010 1:16 am
([msg=35452]see Re: Birthday Attack and Storage[/msg])

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."
User avatar
raddy1313
New User
New User
 
Posts: 27
Joined: Wed Jan 06, 2010 12:22 am
Blog: View Blog (0)



Return to Crypto

Who is online

Users browsing this forum: No registered users and 0 guests