Re: [TLS] Consensus Call: FNV vs SHA1

Michael D'Errico <mike-list@pobox.com> Tue, 11 May 2010 16:39 UTC

Return-Path: <mike-list@pobox.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 84F703A69FB for <tls@core3.amsl.com>; Tue, 11 May 2010 09:39:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.555
X-Spam-Level:
X-Spam-Status: No, score=-0.555 tagged_above=-999 required=5 tests=[AWL=-0.556, BAYES_50=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 N9uiiKyy9jmd for <tls@core3.amsl.com>; Tue, 11 May 2010 09:38:59 -0700 (PDT)
Received: from sasl.smtp.pobox.com (a-pb-sasl-quonix.pobox.com [208.72.237.25]) by core3.amsl.com (Postfix) with ESMTP id BD2283A6840 for <tls@ietf.org>; Tue, 11 May 2010 09:38:48 -0700 (PDT)
Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 3FA04B2F43; Tue, 11 May 2010 12:38:37 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; 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; d=pobox.com; 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 [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 1B817B2F42; Tue, 11 May 2010 12:38:35 -0400 (EDT)
Received: from administrators-macbook-pro.local (unknown [24.234.114.35]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTPSA id 5BB96B2F3D; Tue, 11 May 2010 12:38:32 -0400 (EDT)
Message-ID: <4BE98807.6070404@pobox.com>
Date: Tue, 11 May 2010 09:38:31 -0700
From: Michael D'Errico <mike-list@pobox.com>
User-Agent: Thunderbird 2.0.0.23 (Macintosh/20090812)
MIME-Version: 1.0
To: Nicolas Williams <Nicolas.Williams@oracle.com>
References: <AC1CFD94F59A264488DC2BEC3E890DE50A43B479@xmb-sjc-225.amer.cisco.com> <20100511160434.GK9429@oracle.com>
In-Reply-To: <20100511160434.GK9429@oracle.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Pobox-Relay-ID: A48FA770-5D1B-11DF-BE4B-D033EE7EF46B-38729857!a-pb-sasl-quonix.pobox.com
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 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.

Mike



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