A review of hash function brittleness in OpenPGP

Daniel Kahn Gillmor <dkg@fifthhorseman.net> Thu, 08 January 2009 19:12 UTC

Return-Path: <owner-ietf-openpgp@mail.imc.org>
X-Original-To: ietfarch-openpgp-archive@core3.amsl.com
Delivered-To: ietfarch-openpgp-archive@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 3176F3A6ACE for <ietfarch-openpgp-archive@core3.amsl.com>; Thu, 8 Jan 2009 11:12:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.933
X-Spam-Level:
X-Spam-Status: No, score=-1.933 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1, SARE_FWDLOOK=1.666]
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 ld0AxtIjYe8J for <ietfarch-openpgp-archive@core3.amsl.com>; Thu, 8 Jan 2009 11:12:51 -0800 (PST)
Received: from balder-227.proper.com (properopus-pt.tunnel.tserv3.fmt2.ipv6.he.net [IPv6:2001:470:1f04:392::2]) by core3.amsl.com (Postfix) with ESMTP id C6B273A688F for <openpgp-archive@ietf.org>; Thu, 8 Jan 2009 11:12:50 -0800 (PST)
Received: from balder-227.proper.com (localhost [127.0.0.1]) by balder-227.proper.com (8.14.2/8.14.2) with ESMTP id n08Ivslb066583 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 8 Jan 2009 11:57:54 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
Received: (from majordom@localhost) by balder-227.proper.com (8.14.2/8.13.5/Submit) id n08IvsHM066582; Thu, 8 Jan 2009 11:57:54 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
X-Authentication-Warning: balder-227.proper.com: majordom set sender to owner-ietf-openpgp@mail.imc.org using -f
Received: from relay01.pair.com (relay01.pair.com [209.68.5.15]) by balder-227.proper.com (8.14.2/8.14.2) with SMTP id n08Ivg9K066569 for <ietf-openpgp@imc.org>; Thu, 8 Jan 2009 11:57:53 -0700 (MST) (envelope-from dkg@fifthhorseman.net)
Received: (qmail 36098 invoked from network); 8 Jan 2009 18:57:41 -0000
Received: from 216.254.116.241 (HELO ?192.168.13.75?) (216.254.116.241) by relay01.pair.com with SMTP; 8 Jan 2009 18:57:41 -0000
X-pair-Authenticated: 216.254.116.241
Message-ID: <49664D21.50403@fifthhorseman.net>
Date: Thu, 08 Jan 2009 13:59:45 -0500
From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
User-Agent: Mozilla-Thunderbird 2.0.0.17 (X11/20081018)
MIME-Version: 1.0
To: IETF OpenPGP Working Group <ietf-openpgp@imc.org>
CC: Monkeysphere Developers <monkeysphere@lists.riseup.net>
Subject: A review of hash function brittleness in OpenPGP
X-Enigmail-Version: 0.95.7
OpenPGP: id=D21739E9
Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="------------enig7B8AC4F50DA64063949DE949"
Sender: owner-ietf-openpgp@mail.imc.org
Precedence: bulk
List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>
List-Unsubscribe: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>
List-ID: <ietf-openpgp.imc.org>

Hey folks--

I've been trying to evaluate RFC 4880's resistance to a hash function
compromise in light of the recent activity exploiting weaknesses MD-5 in
That Other PKI [0].

I'm quite pleased with the bulk of what i've found.  OpenPGP's use of
message digests is almost entirely parameterized, leaving the door open
to forward-looking adoption of new hash algorithms and the smooth
deprecation as older ones are demonstrated to be weak.

So I've been looking for places in the spec where the choice of digest
function is not parameterized.  In particular, explicit and hardcoded
reliance on SHA-1 could become problematic as it is already being
deprecated.  For example, reliance on SHA-1 must be eliminated in all US
Gov't federal agencies by the end of 2010 [1].

Here are the concerns i've found so far:

MDC
---

The modification detection packets (sections 5.13 and 5.14) explicitly
specify SHA-1, and basically acknowledge that this choice may need to be
made more flexible in the future.

Fingerprints
------------

Fingerprints (section 12.2) are specified as an SHA-1 computation.
While this isn't an explicit reliance on SHA-1 for cryptographic
security (and the RFC makes it clear that there is a non-zero chance of
fingerprint collisions), the real-world use of fingerprints as unique
identifiers for keys poses a serious risk to OpenPGP infrastructure
should SHA-1 become further compromised.

Revocation keys
---------------

Section 5.2.3.15 defines a way that key A can allow key B to
authoritatively issue revocation signatures on A's behalf, including key
 revocation (sigtype 0x20), subkey revocation (sigtype 0x28), and
certification revocation (sigtype 0x30).  However, this mechanism relies
on the fingerprint of B being unique.  Since the fingerprint itself is
bound to SHA-1, this presents a risk to users of this feature of the
specification should SHA-1 become further compromised.



As the IETF working group for OpenPGP, we probably should start actively
working to resolve these issues so we can have infrastructure in place
well before SHA-1 is similarly compromised.  Any suggestions?  I'm new
to the WG, so i don't have any experience addressing concerns like this.

I'm particularly concerned about fingerprints, since they is used widely
in the real world (e.g. i have my fingerprint on my business card).  I
can imagine relatively straightforward technical measures to resolve the
other concerns.

Also, it's quite likely that i've missed things in my reading of the
spec.  If anyone sees any other problematic areas, it would be great to
air them as soon as possible.

Regards,

	--dkg

[0] http://www.phreedom.org/research/rogue-ca/
[1] http://csrc.nist.gov/groups/ST/hash/statement.html