Re: DEADBEEF vs SHA1

David Shaw <dshaw@jabberwocky.com> Fri, 18 February 2011 04:42 UTC

Received: from hoffman.proper.com (localhost [127.0.0.1]) by hoffman.proper.com (8.14.4/8.14.3) with ESMTP id p1I4gtNS049907 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 17 Feb 2011 21:42:55 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
Received: (from majordom@localhost) by hoffman.proper.com (8.14.4/8.13.5/Submit) id p1I4gtni049906; Thu, 17 Feb 2011 21:42:55 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
X-Authentication-Warning: hoffman.proper.com: majordom set sender to owner-ietf-openpgp@mail.imc.org using -f
Received: from walrus.jabberwocky.com (walrus.jabberwocky.com [173.9.29.57]) by hoffman.proper.com (8.14.4/8.14.3) with ESMTP id p1I4gr34049900 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for <ietf-openpgp@imc.org>; Thu, 17 Feb 2011 21:42:54 -0700 (MST) (envelope-from dshaw@jabberwocky.com)
Received: from grover.home.jabberwocky.com (grover.home.jabberwocky.com [172.24.84.28]) (authenticated bits=0) by walrus.jabberwocky.com (8.14.4/8.14.4) with ESMTP id p1I4gqOr004551 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NO) for <ietf-openpgp@imc.org>; Thu, 17 Feb 2011 23:42:52 -0500
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Apple Message framework v1082)
Subject: Re: DEADBEEF vs SHA1
From: David Shaw <dshaw@jabberwocky.com>
In-Reply-To: <4D5DBDF6.5020705@epointsystem.org>
Date: Thu, 17 Feb 2011 23:42:52 -0500
Message-Id: <66543BB1-FCC6-49AE-9730-04BCD1F1E063@jabberwocky.com>
References: <D8E81788-AF18-448F-BA39-56185C1F0672@jabberwocky.com> <4D5DB5A9.9040509@iang.org> <4D5DBDF6.5020705@epointsystem.org>
To: IETF OpenPGP Working Group <ietf-openpgp@imc.org>
X-Mailer: Apple Mail (2.1082)
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by hoffman.proper.com id p1I4gt33049902
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>

I think I wasn't as clear as I should have been, so let me try and clarify my thoughts a bit more.  There are two issues here:

I started looking at this in the context of the signing key collision issue that Daniel Gillmor had posted about.  He was concerned about the chance of a SHA-1 V4-to-V4 64-bit collision, and I pointed out there is also a risk of a V3-to-V4 collision, which is vastly easier to accomplish.  Now, Daniel's proposed fix handles both cases, so that would seem to be the end of it.  We've already discussed his fix, and so here's just another reason why it's a useful idea.  So, done.  No problem.  That's the standards part of the message.

However, wearing my implementation hat, we do have a different problem now.  In trying out the V3-to-V4 collision against current implementations in the field, it turns out to be a denial of service attack, as at least the implementations that I tried (PGP 9 and GPG 1.4) can't cope very well with two different keys with the same 64-bit key ID.  The "fingerprint in each signature" is intended to disambiguate between two different keys with the same key ID in order to find the real signer.  However, we don't even get to that point, as we can't import two different keys with the same key ID in the first place (the RFC even warns about this specifically).

The end result is that if someone makes this sort of collision, they can upload them to keyservers (perhaps ironically, SKS can handle multiple keys with the same 64-bit key ID just fine), thus "poisoning" certain keys.  Once a key is poisoned, requesting it from the keyserver will return both the good and bad keys in a (so far as I can tell) nondeterministic order, so anyone fetching that key risks importing the bad one, causing signature verifications from the real key to fail, blocking encryption to the real key, and generally making a nuisance.

My proposed fix for this is not an OpenPGP standard issue, as I'm not proposing removing V3 support from the standard.  Rather, I'm just taking advantage of the fact that many OpenPGP developers read this list to raise awareness of the issue, and point out that adding a knob to enable or disable V3 (as allowed for in the standard) is a fairly simple way to avoid this problem.

David