From owner-freebsd-security@FreeBSD.ORG Mon Sep 27 17:27:06 2004 Return-Path: Delivered-To: freebsd-security@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 9C60B16A4CE for ; Mon, 27 Sep 2004 17:27:06 +0000 (GMT) Received: from dfmm.org (walter.dfmm.org [66.180.195.210]) by mx1.FreeBSD.org (Postfix) with ESMTP id 674DF43D54 for ; Mon, 27 Sep 2004 17:27:06 +0000 (GMT) (envelope-from freebsd-security@dfmm.org) Received: (qmail 1328 invoked by uid 1000); 27 Sep 2004 17:27:06 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 27 Sep 2004 17:27:06 -0000 Date: Mon, 27 Sep 2004 10:27:04 -0700 (PDT) From: Jason Stone X-X-Sender: jason@walter To: Giorgos Keramidas In-Reply-To: <20040927091710.GC914@orion.daedalusnetworks.priv> Message-ID: <20040927095906.I79820@walter> References: <20040925140242.GB78219@gothmog.gr> <20040927091710.GC914@orion.daedalusnetworks.priv> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: freebsd-security@freebsd.org Subject: Re: compare-by-hash (was Re: sharing /etc/passwd) X-BeenThere: freebsd-security@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Security issues [members-only posting] List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 27 Sep 2004 17:27:06 -0000 -----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-----