Hi Brian,
Brian Hurt wrote:
agreed, and you analogy is that the original message which can give the same hash is also evenly distributed.
Lecture warning.
On Mon, 14 Mar 2005, alok wrote:
Well i know nothing about that "birthday attacks".
Yeah, you need large key sizes- 128 bits keys just aren't enough (they allow birthday attacks to be computationally feasible). But I note that all the AES finalists went to 256 bit key sizes. This would put a birthday attack at about 128 bits of complexity- sufficient. Anything less than about 160 bits of key space is a bad idea.
Generally, the bit sizes work out, for obvious reasons.
The phrase comes from the well known trick question. About how many people (pulled randomly off the street) do you need together so that you have about a 50% chance that two of them will have the same birthday? If you assume that birthdays are spread evenly over the year- i.e. that there is a 1 in 365 chance that any random pairing of people will have both people having the same birthday. The answer is that with as few as 27 people, you have a 50% chance. This is because with 27 people, there are 27*26/2 = 351 different pairs of people. Loosely, the number of pairings goes up with the square of the number of people.
The same argument applies when you ask how many different random messages you need to has before you have about a 50% chance that two messages you have hashed will have the same hash value? The answer is, again, about the square root of the hash space. So if your hash algorithm produces, say, 64-bits hashs, then if you hash around 4 billion (2^32) messages, you're likely to have two that hash to the same value. This is because with 2^32 messages, you will have about 2^64 pairs.
For those of you who know statistics and combinatorics, yes I'm handwaving past a number of details.
This is why DES is a bad algorithm to use in this way- with 2^56 messages, I'm only having to hash about 2^28 messages- 256 million or so- to get a collision. MD-5 with it's 128-bit hash values was already becoming long in the tooth, as collisions could be forced with about 2^64 messages. Spendy, but doable today. SHA-1 and RIPE-MD, with their 160 bit hash values, are somewhat safer, as they require about 2^80 messages for a birthday attack. This is why they invented SHA-256 and SHA-512.
My problem is not that algorithm, what confuses me is that "protocols" or "well known messages/known plain texts" are sent inside the same.
My point simply was that there has to be a one to one mapping if you use md5 the way telnet/pam uses it for example else 2 people with different passwds could end up.
By the pigeonhole principal, there will always be the possibility of collisions. But this isn't a problem, as it's the equivelent to being able to brute-force crack a private key cipher. Let's say that our hash function outputs 128-bit values. I start encrypting messages. Lets say that by sheerest coincidence, the first 2^128 messages I encrypt all hash to different values. The problem is, at that point I have a message that encrypts to every single possible value. The next message I encrypt will have to have the same hash value as some previous message. This is exactly the same reasoning as saying that if you have 366 (367 if you include Feb. 29th) people in a room, you are gaurenteed to have (at least) two people in that room with the same birthday.
For passwods and the like, this isn't a problem. The birthday attack presumes I don't care which two people (messages) have the same birthday (hash value)- just that I can find two that do. If you're trying to find a message that hashes to a known/given value, this is equivelent to trying to find someone with a given birthday, say the 14th of March. If you started pulling people off the street and asking their birthday, you'd have to pull about 183 people or so off the street before hitting one whose birthday was today. So, for example, given a hashing function that produced 64-bit hashes, to find a message that hashed to 0xDEFACEABADFACADE I'd probably have to encrypt about 2^63 or so messages. This is about the same effort I'd have to do to brute force guess a private key.
Brian
______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
