Re: Is MD5 outdated ?
From: Michael Amling (nospam_at_nospam.com)
Date: 09/27/03
- Next message: Paul Rubin: "Re: Human-answerable challenge response login"
- Previous message: Roger Schlafly: "Re: controversial paper"
- In reply to: Gregory G Rose: "Re: Is MD5 outdated ?"
- Next in thread: Paul Rubin: "Re: Is MD5 outdated ?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sat, 27 Sep 2003 01:25:50 GMT
Gregory G Rose wrote:
> The formula for the *expected number* of
> collisions is simple: if N is the number of
> samples, and k is the length in bits of the hash,
> you expect to have C = N * (N-1) / 2^(k+1)
> collisions.
>
> Now, by asking for the 1% confidence interval,
> you're effectively asking for the N that
> corresponds to a C of 0.01. Simply shuffling the
> formula around gives a quadratic that you can
> solve in the traditional formula to get:
> N = 1/2 + sqrt(2^(k+3) * C)/2.
Or, rather than using an expectation value and a confidence interval,
the OP could use the exact probability of zero collisions in n
evaluations of a perfectly random 128-bit hash, namely 1.0 -
n*(n-1)/(2**129), and use that as a lower bound and approximation to the
probability of zero collisions for MD5. That probability remains less
than 0.001 until you reach 824,963,474,247,118,971 trials.
--Mike Amling
- Next message: Paul Rubin: "Re: Human-answerable challenge response login"
- Previous message: Roger Schlafly: "Re: controversial paper"
- In reply to: Gregory G Rose: "Re: Is MD5 outdated ?"
- Next in thread: Paul Rubin: "Re: Is MD5 outdated ?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
