Date: Mon, 27 Sep 2004 10:27:04 -0700 (PDT) From: Jason Stone <freebsd-security@dfmm.org> To: Giorgos Keramidas <keramida@freebsd.org> Cc: freebsd-security@freebsd.org Subject: Re: compare-by-hash (was Re: sharing /etc/passwd) Message-ID: <20040927095906.I79820@walter> In-Reply-To: <20040927091710.GC914@orion.daedalusnetworks.priv> References: <Pine.LNX.4.33.0111071900280.24824-100000@moroni.pp.asu.edu> <20040925140242.GB78219@gothmog.gr> <20040927091710.GC914@orion.daedalusnetworks.priv>
next in thread | previous in thread | raw e-mail | index | archive | help
-----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-----
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040927095906.I79820>