From owner-freebsd-security@FreeBSD.ORG Tue Sep 28 09:40:07 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 9753F16A4CE for ; Tue, 28 Sep 2004 09:40:07 +0000 (GMT) Received: from pd3mo3so.prod.shaw.ca (shawidc-mo1.cg.shawcable.net [24.71.223.10]) by mx1.FreeBSD.org (Postfix) with ESMTP id B264A43D1D for ; Tue, 28 Sep 2004 09:40:06 +0000 (GMT) (envelope-from cperciva@wadham.ox.ac.uk) Received: from pd2mr8so.prod.shaw.ca (pd2mr8so-qfe3.prod.shaw.ca [10.0.141.11])2004))freebsd-security@freebsd.org; Tue, 28 Sep 2004 03:39:50 -0600 (MDT) Received: from pn2ml7so.prod.shaw.ca ([10.0.121.151]) by pd2mr8so.prod.shaw.ca (Sun ONE Messaging Server 6.0 HotFix 1.01 (built Mar 15 2004)) with ESMTP id <0I4Q00GRTW6DWDI0@pd2mr8so.prod.shaw.ca> for freebsd-security@freebsd.org; Tue, 28 Sep 2004 03:39:50 -0600 (MDT) Received: from [192.168.0.60] (S0106006067227a4a.vc.shawcable.net [24.87.233.42])2003)) freebsd-security@freebsd.org; Tue, 28 Sep 2004 03:39:49 -0600 (MDT) Date: Tue, 28 Sep 2004 02:39:49 -0700 From: Colin Percival In-reply-to: <20040928091405.GB1800@orion.daedalusnetworks.priv> To: Giorgos Keramidas Message-id: <41593165.10406@wadham.ox.ac.uk> MIME-version: 1.0 Content-type: text/plain; format=flowed; charset=us-ascii Content-transfer-encoding: 7bit X-Accept-Language: en-us, en References: <20011107211316.A7830@nomad.lets.net> <20040925140242.GB78219@gothmog.gr> <41575DFC.9020206@wadham.ox.ac.uk> <20040927091710.GC914@orion.daedalusnetworks.priv> <20040927095906.I79820@walter> <20040928091405.GB1800@orion.daedalusnetworks.priv> User-Agent: Mozilla Thunderbird 0.7.3 (X11/20040922) 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:40:07 -0000 Giorgos Keramidas wrote: > There is one difference between ``looking for collisions'' and being > bitten by undetected collisions though. True. But if the best known collision-finding algorithm takes f(p) operations in order to achieve a probability p of having found a collision, and you've performed less than f(p) operations, then either the chance of you being bitten by an undetected collision is less than p, or you've managed to improve upon the best-known collision-finding algorithm. For f(p) = 2^80 * sqrt(p), none of us are ever going to perform enough operations to make the chance of stumbling across a collision by accident a significant risk. Colin Percival