hi, Consider a one-way hash function producing an m-bit output,as an example let us consider a 4 bit output of a hash function,where M is the message fed and H is the hashing function.
For a 4 bit hash function,in order to brute force,i.e to find a message that hashes to the same value would take (2^m)+1 random messages,which is 2^4=16+1=17 random messages. P(two random messages hashing to the same value)=1/16=0.0625 P(two random messages not hashing to the same value)=1-0.0625=0.9375 Method 1 -------- we find P(5 random messages not hashing to the same hash value) When we choose 5 random messages,the number of message pairs formed are n*(n-1)/2 i.e 5*4/2=10 pairs Thus P(5 random messages not hashing to the same hash value)=0.9375^10 = 52% Similarly P(5.2 random messages not hashing to the same hash value)=0.9375^10.92 = 50% Method 2 -------- The number of random messages needed for the chance to be 50% that 2 random messages hash to the same value is also given as 1.2*(k^0.5) For our example k=16 and 1.2*(16^0.5)=4.8 random messages are needed so that 2 random messages hash to the same value. Method 3 -------- Book says finding 2 messages that hash to the same value takes hashing only 2^(m/2) random messages. i.e in our example 2^(4/2)=4 random messages. So how many random messages do I need to hash to the same value. 1. Is it 5.2 random messages or 4.8 or 4? 2. Is not Method 1 that yields the accurate solution? 3. Are Method 2 and 3 approximations and how is 1.2*(k^0.5) actually obtained? 4. Is it that Method 2 is approximated to Method 3,since eg. for a 160 bit output Method 2 yields 1.2*(2^(160/2))= 1.2*2^80 which is the number of random messages required so that they hash to the same value.While Method 3 simply gives 2^(m/2) which would be 2^(160/2)=2^80 Book further says-"If you want to drop the odds of some one breaking your system to less than 1 in 2^80,use a 160 bit one-way hash function". The birthday attack only works when we find 2 random messages that hashes to the same value. Here we know one message and we hash it to obtain an output value.Now we are trying to find a random message that hashes to the same value. P(One random message that hashes to the same value)=1/2^160. We will have to hash 2^159 messages,assuming that we succeed at 50% and will not be 2^80 as book says. How do we justify this? Thank you. Regards Sarath. __________________________________________________ Do you Yahoo!? Yahoo! Shopping - Send Flowers for Valentine's Day http://shopping.yahoo.com
