Re: compare-by-hash (was Re: sharing /etc/passwd)

From: Mark Andrews (Mark_Andrews_at_isc.org)
Date: 09/28/04

  • Next message: Colin Percival: "Re: compare-by-hash (was Re: sharing /etc/passwd)" 
    To: Giorgos Keramidas <keramida@linux.gr>
Date: Tue, 28 Sep 2004 19:25:46 +1000

    > On 2004-09-27 10:27, Jason Stone <freebsd-security@dfmm.org> wrote:
    > > > Henson notes that since there's no absolutely guaranteed proof that
    > > > there are *no* collisions with a given hashing algorithm,
    > >
    > > true - quite the opposite, in fact - with a finite hash length and an
    > > infinite number of inputs, you are guaranteed an infinite number of
    > > collisions in any hashing algorithm - you're just going to have to spend
    > > longer than the lifetime of the universe to find them....
    >
    > There is one difference between ``looking for collisions'' and being
    > bitten by undetected collisions though.
    >
    > If the probability of a collision just happening with random user data
    > is 1/(2^128) we can't be sure that it will necessarily take the
    > transfer of an average number of 2^127 blocks before a collision
    > happens. You might get one at the very first pair of blocks and then
    > no collisions ever after until the Sun burns out.
    >
    > Using two different hashes for the same set of input data, which David
    > G. Andersen proposed, seems like a nice idea though.

            Assuming the hashes are independent all it does is multiply the
            probabilities. If the hashes are not independent you won't get
            as much improvement.

            In either case all you are doing is creating yet another hash
            function.

            Mark 

    --
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: Mark_Andrews@isc.org
_______________________________________________
freebsd-security@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-security
To unsubscribe, send any mail to "freebsd-security-unsubscribe@freebsd.org"
  • Next message: Colin Percival: "Re: compare-by-hash (was Re: sharing /etc/passwd)"

    Relevant Pages

    • Re: compare-by-hash (was Re: sharing /etc/passwd)
      ... > infinite number of inputs, you are guaranteed an infinite number of ... bitten by undetected collisions though. ... If the probability of a collision just happening with random user data ...
      (FreeBSD-Security)
    • Re: compare-by-hash (was Re: sharing /etc/passwd)
      ... > If the probability of a collision just happening with random user data ... > no collisions ever after until the Sun burns out. ... > Using two different hashes for the same set of input data, ... This paper needs a lot more peer review, ...
      (FreeBSD-Security)