Re: [TLS] Consensus Call: FNV vs SHA1

Michael D'Errico <> Tue, 11 May 2010 16:39 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 84F703A69FB for <>; Tue, 11 May 2010 09:39:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.555
X-Spam-Status: No, score=-0.555 tagged_above=-999 required=5 tests=[AWL=-0.556, BAYES_50=0.001]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id N9uiiKyy9jmd for <>; Tue, 11 May 2010 09:38:59 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id BD2283A6840 for <>; Tue, 11 May 2010 09:38:48 -0700 (PDT)
Received: from (unknown []) by (Postfix) with ESMTP id 3FA04B2F43; Tue, 11 May 2010 12:38:37 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed;; h=message-id :date:from:mime-version:to:cc:subject:references:in-reply-to :content-type:content-transfer-encoding; s=sasl; bh=XA7DM8GhCfPX PgMn6JTPUQpAB1k=; b=e3ADEWF9j2bn04A8Xc2RExHLT7IWwYGp0RAcyxSYM31G Kk0g9HilzTeRWAgGSDnRLewSaqapbVCEUp2th5iBoP24d9Sam/7/u0azc6liJtjf D4djlF+ho1Sv5uKSY577+cd5S2EzLiV8MVvXPAKuuBlg0orei8dNwZrgNGFwx/E=
DomainKey-Signature: a=rsa-sha1; c=nofws;; h=message-id:date :from:mime-version:to:cc:subject:references:in-reply-to :content-type:content-transfer-encoding; q=dns; s=sasl; b=Q4OCgj SchtBIWqIFFHtBnjwt9hofoajmSBddHaFpMVlbRGrNbjqs7fYA+S3D9XH/hRDmgM +V+tUVtvNDtvcLmIp9eh1h5NXCW6jDoWzdoykf2H9iafGhESzlEXuSxyNo2ztAPv aFaJ2kikm9WToXlurqNH4KcqSM2cxaiVZ9bSM=
Received: from a-pb-sasl-quonix. (unknown []) by (Postfix) with ESMTP id 1B817B2F42; Tue, 11 May 2010 12:38:35 -0400 (EDT)
Received: from administrators-macbook-pro.local (unknown []) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPSA id 5BB96B2F3D; Tue, 11 May 2010 12:38:32 -0400 (EDT)
Message-ID: <>
Date: Tue, 11 May 2010 09:38:31 -0700
From: Michael D'Errico <>
User-Agent: Thunderbird (Macintosh/20090812)
MIME-Version: 1.0
To: Nicolas Williams <>
References: <> <>
In-Reply-To: <>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Pobox-Relay-ID: A48FA770-5D1B-11DF-BE4B-D033EE7EF46B-38729857!
Subject: Re: [TLS] Consensus Call: FNV vs SHA1
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." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 11 May 2010 16:39:00 -0000

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.

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.


Nicolas Williams wrote:
> On Mon, May 10, 2010 at 10:39:28AM -0700, Joseph Salowey (jsalowey) wrote:
>> I don't see much new being added to this discussion at this point.  I'd
>> like to close on this.  If you have an opinion please indicate if:
>> a) You favor SHA-1
>> b) You favor FNV-1a
> Subsequent discussion shows that hash collisions are a problem for this
> protocol, though not a security problem.  As such I believe that (b) is
> now out of order, and therefore I now favor (a), with less or no
> truncation.
> I believe additional text is required to explain what to do when
> collisions result, and also how to detect collisions (I think collisions
> can only be detected heuristically on handshake failure, but can
> confirmed on subsequent retry).
> I believe too that a protocol design where collisions are avoided
> altogether is not desirable.  But something to consider might be to send
> not just a checksum/hash of cached objects, but also the name of the
> first cert in any cert/cert chain or other nameable object -- this would
> make collisions entirely avoidable by having operators check for them
> before installing new certs.
> Nico