From owner-freebsd-security@FreeBSD.ORG Tue Sep 28 09:25:53 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 9977E16A4CE for ; Tue, 28 Sep 2004 09:25:53 +0000 (GMT) Received: from farside.isc.org (farside.isc.org [204.152.187.5]) by mx1.FreeBSD.org (Postfix) with ESMTP id 836FD43D1D for ; Tue, 28 Sep 2004 09:25:53 +0000 (GMT) (envelope-from Mark_Andrews@isc.org) Received: from drugs.dv.isc.org (localhost [IPv6:::1]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by farside.isc.org (Postfix) with ESMTP id AC35367503 for ; Tue, 28 Sep 2004 09:25:52 +0000 (UTC) (envelope-from marka@isc.org) Received: from drugs.dv.isc.org (localhost [127.0.0.1]) by drugs.dv.isc.org (8.12.11/8.12.11) with ESMTP id i8S9PkDX091228; Tue, 28 Sep 2004 19:25:46 +1000 (EST) (envelope-from marka@drugs.dv.isc.org) Message-Id: <200409280925.i8S9PkDX091228@drugs.dv.isc.org> To: Giorgos Keramidas From: Mark Andrews In-reply-to: Your message of "Tue, 28 Sep 2004 12:14:05 +0300." <20040928091405.GB1800@orion.daedalusnetworks.priv> Date: Tue, 28 Sep 2004 19:25:46 +1000 Sender: Mark_Andrews@isc.org X-Mailman-Approved-At: Tue, 28 Sep 2004 15:12:26 +0000 cc: Jason Stone 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: Tue, 28 Sep 2004 09:25:53 -0000 > On 2004-09-27 10:27, Jason Stone 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