Re: MD5 and SHA-1 Digest: What is the probability of repeating hash-values?

From: Jim Gillogly (jim_at_acm.org)
Date: 10/24/03 

Date: Fri, 24 Oct 2003 18:51:37 GMT

Anton Spaans wrote:
> MD5 digests create 128-bit hash-values. The maximum number of hash-values is
> therefore no more than 2^128.
> I have this question:
>
> What is a (approximate) chance that two different original messages have the
> same MD5 (or SHA) digest hash-value?

Given the first paragraph as your background, I assume you're asking
whether there are two possible messages that can hash to the same value.
That's a "yes", i.e. probability 1.0: since there are more than 2^128
(resp. 2^160) possible messages, there must be collisions. We haven't
seen any yet for MD5 or SHA1, so far as I know.

If you'd prefer to ask how likely it is that someone can construct a
message that will match one that you just wrote, so far as I know
there's no improvement on a 1/2^128 (resp. 1/2^160) chance for each try.

There's been some work on using the birthday paradox to get the
probability higher in the case where you're trying to construct
two plausible messages at the same time that have the same hash.
(The application is that you get somebody to sign a hash of a
promissory note for one amount while you have another message in
your pocket that you will produce in court.) 

-- 
	Jim Gillogly

Relevant Pages

  • Re: binary file compare...
    ... could you please accept that hashes collide and that no matter how many ... that guarantees a non-zero chance of corrupting your data. ... I'm just going to go ahead and take the above as an admission by you that the chance of collision is non-zero, and that if we accept that fact you cannot rely on a hash function to tell you if two files are identical. ...
    (comp.lang.python)
  • Re: Probabalistic algorithms.
    ... >Nothing personal Mr French, because I know how knowledgeable you are, ... >that has chance as a crucial element. ... >Hashing is typically just an optimisation. ... all the hash does is guarantee that given some ...
    (comp.lang.pascal.delphi.misc)
  • Re: what is probability to create two equal hashes for md5 algorithm
    ... My estimate went to the level of 1024 TB in 512KB pieces, and scales very ... either collide on the block size or to break the hash you choose. ... different estimation for MD5 (resp. ... SHA-1): approximately one collision ...
    (sci.crypt)
  • Re: [SLE] SuSE-related web sites
    ... Hash: SHA1 ... > other SUSErs a chance to use that software. ...
    (SuSE)
  • Re: Linux Advocates Fear Solaris 10.
    ... the rounded part of spoons, ... > Well, didn't you make a hash of that, eh? ... Are you, by any chance, the same nitwit who inspired the Monty Python team ... to write the Black Knight scene in "We are the Knights who say Ni!"? ...
    (comp.unix.solaris)
Quantcast