Re: [TLS] Collisions (Re: Consensus Call: FNV vs SHA1)

"Kemp, David P." <DPKemp@missi.ncsc.mil> Tue, 11 May 2010 17:39 UTC

Return-Path: <DPKemp@missi.ncsc.mil>
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 28B413A6A14 for <tls@core3.amsl.com>; Tue, 11 May 2010 10:39:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.205
X-Spam-Level:
X-Spam-Status: No, score=-4.205 tagged_above=-999 required=5 tests=[AWL=-0.206, BAYES_50=0.001, RCVD_IN_DNSWL_MED=-4]
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 M04zz0p+gauU for <tls@core3.amsl.com>; Tue, 11 May 2010 10:38:59 -0700 (PDT)
Received: from stingray.missi.ncsc.mil (stingray.missi.ncsc.mil [144.51.50.20]) by core3.amsl.com (Postfix) with ESMTP id 400793A6A08 for <tls@ietf.org>; Tue, 11 May 2010 10:38:59 -0700 (PDT)
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
X-MimeOLE: Produced By Microsoft Exchange V6.5
Date: Tue, 11 May 2010 13:38:40 -0400
Message-ID: <201005111738.o4BHchHo004626@stingray.missi.ncsc.mil>
In-Reply-To: <20100510214516.GZ9429@oracle.com>
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Thread-Topic: [TLS] Collisions (Re: Consensus Call: FNV vs SHA1)
Thread-Index: Acrwilbs+Sjm+lK2Ri2Oc1i9XsV9mAAoEbsA
References: <20100510213035.GX9429@oracle.com> <C80DF458.A5A4%uri@ll.mit.edu> <20100510214516.GZ9429@oracle.com>
From: "Kemp, David P." <DPKemp@missi.ncsc.mil>
To: <tls@ietf.org>
X-OriginalArrivalTime: 11 May 2010 17:39:56.0453 (UTC) FILETIME=[F8921D50:01CAF130]
Subject: Re: [TLS] Collisions (Re: 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:39:00 -0000

In general, protocols and standardized data structures may make use of
non-cryptographic hash functions in cases where collisions are
anticipated and well-handled: i.e. as optimizations (optional) rather
than as integrity (required) mechanisms.  PKIX AKI/SKI is an example:

   "The authority key identifier extension provides a means of
   identifying the public key corresponding to the private key 
   used to sign a CRL. ... This extension is especially useful
   where an issuer has more than one signing key, either due to
   multiple concurrent key pairs or due to changeover."

PKIX suggests two SHA-1 -based methods of generating SKIs (including the
4 bit constant 0100 followed by the 60 least significant bits of the
SHA-1 hash of a public key), and says "Other methods of generating
unique numbers are also acceptable."

The same reflexive "broken algorithm" evaluation concerns may exist for
this use of SHA-1, and FNV would perform the function just as well
without raising any eyebrows.

If a collision did occur, an implementation would have to do an extra
signature validation if it first picked the wrong certificate to
validate a signature.  Not much of a penalty, and one which would have
to be handled anyway for the case where AKI/SKI is not populated at all.

Dave



----- Nico wrote: ----

Aside from that, I think FNV is a great hash function.  Its place will
typically not be in Internet protocols, but in implementations.

[*] I _can_ think of non-cryptographic uses of hash functions in
    Internet protocols, starting with the use we made in GS2.  But in
    general I think we'll want to review such uses carefully.  In the
    case of GS2 it saved us the bother of creating a registry of SASL
    mechanism names for GSS-API mechanisms.  Here the hash is used to
    identify cached items, which seems fine provided that collisions are
    well-handled.  In the GS2 case we decided that collisions were not a
    problem for us (after all, we could always assign new OIDs to GSS
    mechanisms that collide).