Transcript No Slide Title


If the hash algorithm is properly designed and distributes the
hashes uniformly over the output space, "finding a hash
collision" by random guessing is exceedingly unlikely (it's
more likely that a million people will correctly guess all the
California Lottery numbers every day for a billion trillion years).

This astonishing fact is due to the astonishingly large number
of possible hashes available: a 128-bit hash can have 3.4 x
10^38 possible values, which is:
340,282,366,920,938,463,463,374,607,431,768,211,456
possible hashes
1 gig numbers / sec
1 gig = 10^9 = 2^30
128 bit will take 2^98 secs
= 2^73 years
= 10^20 years
100,000,000,000,000,000,000 years
(1 year = 2^25 secs)
atoms in the universe =
1078 to just under 1081 =
i.e. 2246 to 2256
Hash collisions


Thought to be impossible
Only one known so far for a “good” algorithm
 MD5 hash collision
3
SHA-1: 160 bit hash

Start with 512 bit blocks of input, pad
it if needed.
 Expand to 80 32-bit subkeys (Wt)





Initialize some hash blocks (A, B,
…E)
Use input to generate Wt, Kt is a
constant.
F is a changeable functions,
constructed from shifts, and XORs.
Do 80 rounds. Then use more input.
Can be made to be fast.
4