Re: [TLS] Consensus Call: FNV vs SHA1

Nicolas Williams <Nicolas.Williams@oracle.com> Tue, 11 May 2010 17:04 UTC

Return-Path: <Nicolas.Williams@oracle.com>
X-Original-To: tls@core3.amsl.com
Delivered-To: tls@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 57D683A69CA for <tls@core3.amsl.com>; Tue, 11 May 2010 10:04:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.248
X-Spam-Level:
X-Spam-Status: No, score=-4.248 tagged_above=-999 required=5 tests=[AWL=0.861, BAYES_05=-1.11, RCVD_IN_DNSWL_MED=-4, UNPARSEABLE_RELAY=0.001]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hla85vzoSxzU for <tls@core3.amsl.com>; Tue, 11 May 2010 10:04:57 -0700 (PDT)
Received: from rcsinet10.oracle.com (rcsinet10.oracle.com [148.87.113.121]) by core3.amsl.com (Postfix) with ESMTP id 295E03A6985 for <tls@ietf.org>; Tue, 11 May 2010 10:04:57 -0700 (PDT)
Received: from acsinet15.oracle.com (acsinet15.oracle.com [141.146.126.227]) by rcsinet10.oracle.com (Switch-3.4.2/Switch-3.4.1) with ESMTP id o4BH4hxI029409 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 11 May 2010 17:04:44 GMT
Received: from acsmt355.oracle.com (acsmt355.oracle.com [141.146.40.155]) by acsinet15.oracle.com (Switch-3.4.2/Switch-3.4.1) with ESMTP id o4BCuasJ030975; Tue, 11 May 2010 17:04:42 GMT
Received: from abhmt012.oracle.com by acsmt353.oracle.com with ESMTP id 232148681273597464; Tue, 11 May 2010 10:04:24 -0700
Received: from oracle.com (/129.153.128.104) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Tue, 11 May 2010 10:04:23 -0700
Date: Tue, 11 May 2010 12:04:19 -0500
From: Nicolas Williams <Nicolas.Williams@oracle.com>
To: "Michael D'Errico" <mike-list@pobox.com>
Message-ID: <20100511170418.GN9429@oracle.com>
References: <AC1CFD94F59A264488DC2BEC3E890DE50A43B479@xmb-sjc-225.amer.cisco.com> <20100511160434.GK9429@oracle.com> <4BE98807.6070404@pobox.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <4BE98807.6070404@pobox.com>
User-Agent: Mutt/1.5.20 (2010-03-02)
X-Auth-Type: Internal IP
X-Source-IP: acsinet15.oracle.com [141.146.126.227]
X-CT-RefId: str=0001.0A090201.4BE98E2D.00A7:SCFMA922111,ss=1,fgs=0
Cc: tls@ietf.org
Subject: Re: [TLS] Consensus Call: FNV vs SHA1
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 11 May 2010 17:04:59 -0000

On Tue, May 11, 2010 at 09:38:31AM -0700, Michael D'Errico wrote:
> With a birthday collision of 64 bits (thanks Dave for reminding me of
> this), you would need about 6 million server certificates to achieve a
> probability of 1 in a million that 2 of those 6 million certificates
> hash to the same value.  Since servers change certificates about once
> a year, and a client doesn't need to remember any hashes of expired
> certificates, and there is no problem if the certificates of unrelated
> servers collide, this seems to be a non-issue.

I agree that collisions will be extremely unlikely.  My concern is how
to recover from them if they occur.

> The only question is whether FNV is as good of a hash function as is
> required to resist the birthday attack.  My simple test showed that it
> might be, but IANAC and don't know how to determine that.

Based on a gut feeling I'd rather go with a cryptographic hash if
collision resistance is desired.  (Though, of course collision
resistance is not the same thing as having a low rate of collisions
with real world inputs.)

Nico
--