Re: [TLS] Consensus Call: FNV vs SHA1

"Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu> Tue, 11 May 2010 17:15 UTC

Return-Path: <prvs=274770b3e0=uri@ll.mit.edu>
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 E75ED3A6A15 for <tls@core3.amsl.com>; Tue, 11 May 2010 10:15:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.079
X-Spam-Level:
X-Spam-Status: No, score=-6.079 tagged_above=-999 required=5 tests=[AWL=0.519, BAYES_00=-2.599, 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 Vi0+6K0ZEG9w for <tls@core3.amsl.com>; Tue, 11 May 2010 10:15:12 -0700 (PDT)
Received: from mx1.ll.mit.edu (MX1.LL.MIT.EDU [129.55.12.45]) by core3.amsl.com (Postfix) with ESMTP id 089E73A6A05 for <tls@ietf.org>; Tue, 11 May 2010 10:14:56 -0700 (PDT)
Received: from LLE2K7-HUB01.mitll.ad.local (LLE2K7-HUB01.mitll.ad.local) by mx1.ll.mit.edu (unknown) with ESMTP id o4BHEheH020156; Tue, 11 May 2010 13:14:44 -0400
From: "Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu>
To: "'Nicolas.Williams@oracle.com'" <Nicolas.Williams@oracle.com>, "'mike-list@pobox.com'" <mike-list@pobox.com>
Date: Tue, 11 May 2010 13:14:43 -0400
Thread-Topic: [TLS] Consensus Call: FNV vs SHA1
Thread-Index: AcrxLBL0Dwc9iAhBQm2sbAA+t/yBjQAAV+PN
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=1.12.8161:2.4.5, 1.2.40, 4.0.166 definitions=2010-05-11_04:2010-02-06, 2010-05-11, 2010-05-11 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 ipscore=0 phishscore=0 bulkscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx engine=5.0.0-0908210000 definitions=main-1005110096
Message-Id: <20100511171457.089E73A6A05@core3.amsl.com>
Cc: "'tls@ietf.org'" <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:15:13 -0000

If you're talking about Birthday Paradox - then just figure out how many bits of hash suffice to minimize the risk to acceptable level.

If you're talking about Birthday Paradox ATTACK - you're in the Crypto realm, and say "welcome" to SHA256 (which you probably already have in your code :-). And don't forget algorithm agility.

Regards,
Uri

----- Original Message -----
From: tls-bounces@ietf.org <tls-bounces@ietf.org>
To: Michael D'Errico <mike-list@pobox.com>
Cc: tls@ietf.org <tls@ietf.org>
Sent: Tue May 11 13:04:19 2010
Subject: Re: [TLS] Consensus Call: FNV vs SHA1

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
-- 
_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls