Date sent: Tue, 26 Jul 2005 07:11:24 +0100
From: Labib Ramy <Ramy.Labib@eg.fujitsu.com>
In Cryptographic Domain:
Can someone please explain the following:
MD5 produces a 128 bit digest. Birthday attacks mounted against MD5 use only
(128/2) 64 bit (2 to the power of 64 possibilities) SHA-1 produces a 160 bit
digest. Birthday attacks mounted against SHA use only (160/2) 80 bit (2 to the
power of 80 possibilities)
Question is: Why 64 bits & 80 bits ???
The Birthday Attack is based on the fact that comparing many items to many
items results in a greater chance of a match than simply matching one to one.
The formula (extremely simplified) boils down to the result that you need a
cluster
the size of the square root of the address space. Thus, (roughly) 20 people's
birthdays will generate a match out of the (roughly) 400 days in a year. (OK,
I
*said* this was extremely simplified: for birthdays the actual numbers are 23
and
365.)
The square root of 2^128 is 2^64, and for 2^160 is 2^80.
(Note also that recent work has shown that SHA is subject to an analytic attack
that greatly reduces the cluster size needed for a Birthday Attack, and that
MD5
may be subject to the same or similar exploit.)
====================== (quote inserted randomly by Pegasus Mailer)
rslade@vcn.bc.ca slade@victoria.tc.ca rslade@sun.soci.niu.edu
Metabolically challenged - politically correct term for dead
http://victoria.tc.ca/techrev or http://sun.soci.niu.edu/~rslade
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/CISSP-Discuss/
<*> To unsubscribe from this group, send an email to:
CISSP-Discuss-unsubscribe@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
