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

From: Jason Stone (freebsd-security_at_dfmm.org)
Date: 09/27/04

  • Next message: Giorgos Keramidas: "Re: compare-by-hash (was Re: sharing /etc/passwd)" 
    Date: Mon, 27 Sep 2004 10:27:04 -0700 (PDT)
To: Giorgos Keramidas <keramida@freebsd.org>

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    > 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....

    > What I pointed out was that when a non-zero possibility of two data
    > blocks comparing as equal (even though they are no) exists, the method
    > in question should not be used for password data

    well, when you consider that sha1 has a 160-bit hash length and the total
    expected lifetime of the universe (by most cosmological theories) is
    "only" about 2^60 seconds, that means that if you generated and compared a
    million hashes per second, you would only find one collision in the entire
    lifetime of the universe. when you consider the case of trying to match a
    given input (ie, your passwd file) then you have to do the full 2^160
    hashes to generate a collision. this would require you to hash and
    compare 2^100 inputs per second for the entire lifetime of the universe to
    find just one collision. for a little bit of perspective, hashing and
    comparing 2^100 inputs per second would require a
    1,180,591,620,717,411,303,424 Ghz computer to do both the hash and the
    compare in just one clock cycle.

    the point is that it's so not worth while to consider the collision rate
    in these kinds of applications - the probability of your computer bursting
    into flames and killing you is (absolutely literally) way way higher.
    the probability of the earth opening up and swallowing your datacenter is
    (absolutely literally) way way higher. or, more practically speaking, the
    probability of your computer getting hacked or your data lost/damaged in
    some other, much more mundane way is infinitely higher, so spend your time
    worrying about that instead.

     -Jason

     --------------------------------------------------------------------------
     Freud himself was a bit of a cold fish, and one cannot avoid the suspicion
     that he was insufficiently fondled when he was an infant.
            -- Ashley Montagu
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.2.3 (FreeBSD)
    Comment: See https://private.idealab.com/public/jason/jason.gpg

    iD8DBQFBWE1qswXMWWtptckRAnY6AKC3B9sWK5zlSAC8FsljTKyEj43E4wCbBgv/
    ogxLESxZzJXr8G8yY2lvj0g=
    =kZmz
    -----END PGP SIGNATURE-----
    _______________________________________________
    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: Giorgos Keramidas: "Re: compare-by-hash (was Re: sharing /etc/passwd)"