From owner-freebsd-security@FreeBSD.ORG Tue Sep 28 22:19:09 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 6AA5C16A4CF for ; Tue, 28 Sep 2004 22:19:09 +0000 (GMT) Received: from VARK.MIT.EDU (VARK.MIT.EDU [18.95.3.179]) by mx1.FreeBSD.org (Postfix) with ESMTP id F404743D31 for ; Tue, 28 Sep 2004 22:19:08 +0000 (GMT) (envelope-from das@FreeBSD.ORG) Received: from VARK.MIT.EDU (localhost [127.0.0.1]) by VARK.MIT.EDU (8.13.1/8.12.10) with ESMTP id i8SMJ48m024627; Tue, 28 Sep 2004 18:19:04 -0400 (EDT) (envelope-from das@FreeBSD.ORG) Received: (from das@localhost) by VARK.MIT.EDU (8.13.1/8.12.10/Submit) id i8SMJ4J8024626; Tue, 28 Sep 2004 18:19:04 -0400 (EDT) (envelope-from das@FreeBSD.ORG) Date: Tue, 28 Sep 2004 18:19:04 -0400 From: David Schultz To: Jason Stone Message-ID: <20040928221904.GA24296@VARK.MIT.EDU> Mail-Followup-To: Jason Stone , freebsd-security@FreeBSD.ORG References: <20040925140242.GB78219@gothmog.gr> <20040927091710.GC914@orion.daedalusnetworks.priv> <20040928161359.GA22274@VARK.MIT.EDU> <20040928125056.C79820@walter> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20040928125056.C79820@walter> 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 22:19:09 -0000 On Tue, Sep 28, 2004, Jason Stone wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > > > One thing to keep in mind is that the collision-resistance of SHA-1 is > > an unproven conjecture. > > sure, I was going to mention that - indeed, md4 is the algorithm used in > rsync, and it _has_ been shown to be less collision-resistant than the > full 128-bits would imply. > > which means that instead of finding only one collision in the entire > lifetime of the universe, you'll find four. No, md4 and md5 are broken, in the sense that it's known how to feasibly generate collisions. For example: das@VARK:~> cmp md4* md4c_1 md4c_2 differ: char 8, line 1 das@VARK:~> cmp md5* md5c_1 md5c_2 differ: char 20, line 1 das@VARK:~> openssl md4 md4* MD4(md4c_1)= 4d7e6a1defa93d2dde05b45d864c429b MD4(md4c_2)= 4d7e6a1defa93d2dde05b45d864c429b das@VARK:~> openssl md5 md5* MD5(md5c_1)= a4c0d35c95a63a805915367dcfe6b751 MD5(md5c_2)= a4c0d35c95a63a805915367dcfe6b751 das@VARK:~> hexdump md4c_1 0000000 9c83 4d7a 927a 56cb a578 b9d5 a5ee 57a7 0000010 8a3c de74 66b3 dcc3 a020 b683 5d9f 3b2a 0000020 71b3 c69d 9198 f9e9 805e d79f b2e8 a63b 0000030 8e31 45dd 1fe5 97e3 bf08 2794 c3e9 b9e8 0000040 das@VARK:~> hexdump md4c_2 0000000 9c83 4d7a 927a d6cb a578 29d5 a5ee 57a7 0000010 8a3c de74 66b3 dcc3 a020 b683 5d9f 3b2a 0000020 71b3 c69d 9198 f9e9 805e d79f b2e8 a63b 0000030 8e31 45dc 1fe5 97e3 bf08 2794 c3e9 b9e8 0000040 das@VARK:~> hexdump md5c_1 0000000 31d1 02dd e6c5 c4ee 3d69 069a af98 5cf9 0000010 ca2f 87b5 4612 ab7e 0440 3e58 fbb8 897f 0000020 ad55 0634 f409 02b3 e483 8388 7125 5a41 0000030 5108 e825 cdf7 9fc9 1dd9 f2bd 3780 5b3c 0000040 0b96 d11d 41dc 9c7b d8e4 f497 655a d555 0000050 7335 c79a ebf0 0cfd 2930 66f1 09d1 8fb1 0000060 2775 797f d530 eb5c e822 baad cc79 5c15 0000070 74ed ddcb c55f 6dd3 9bb1 d80a cc35 e3a7 0000080 das@VARK:~> hexdump md5c_2 0000000 31d1 02dd e6c5 c4ee 3d69 069a af98 5cf9 0000010 ca2f 07b5 4612 ab7e 0440 3e58 fbb8 897f 0000020 ad55 0634 f409 02b3 e483 8388 f125 5a41 0000030 5108 e825 cdf7 9fc9 1dd9 72bd 3780 5b3c 0000040 0b96 d11d 41dc 9c7b d8e4 f497 655a d555 0000050 7335 479a ebf0 0cfd 2930 66f1 09d1 8fb1 0000060 2775 797f d530 eb5c e822 baad 4c79 5c15 0000070 74ed ddcb c55f 6dd3 9bb1 580a cc35 e3a7 0000080 (Acknowledgement: The md5 data comes from the page http://www.freedom-to-tinker.com/archives/000663.html, and the md4 data from an email.)