[openpgp] Fingerprint length and application

Phillip Hallam-Baker <phill@hallambaker.com> Mon, 10 October 2016 18:38 UTC

Return-Path: <hallam@gmail.com>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id AB561129739 for <openpgp@ietfa.amsl.com>; Mon, 10 Oct 2016 11:38:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.597
X-Spam-Status: No, score=-2.597 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id dHU_G3LbSzeX for <openpgp@ietfa.amsl.com>; Mon, 10 Oct 2016 11:38:43 -0700 (PDT)
Received: from mail-qt0-x22a.google.com (mail-qt0-x22a.google.com [IPv6:2607:f8b0:400d:c0d::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5DAA7129750 for <openpgp@ietf.org>; Mon, 10 Oct 2016 11:38:43 -0700 (PDT)
Received: by mail-qt0-x22a.google.com with SMTP id s49so62615561qta.0 for <openpgp@ietf.org>; Mon, 10 Oct 2016 11:38:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:message-id:subject:to; bh=ctJAEA+VJaPkATPJPGDq2LUk5OvubO2vzc9pJm5dJcA=; b=wHiar77Mn7p+ashP+MZTpWkX6hwjRdNuILirwJwSW8sbr7iRssWsqAg6ruiOLAfrX2 iko2XzZ3YnNR1Oc9K3cOEgO7kHjf9L1J9l302IRaK1WRzLjxcJT3JgUmQzIfW6pC3yuE 19ZZWBsNajA7bI29zOyHzVrSp5K0rdAJjMyxLDyKsXyAVPN/WVMu9ENvIrXqa8bXGQ0c eNX8Tqna9zULbf8S2JfAP7xvsqIak9mDu41kLg723bgK1HHs4YMJ9HA5mJT4bpzwYN7s uHEH9kzyi6oxrzVEdYzu4wHYYjHq5/e59UruCUqgZdN6AkD8yiRHkT5GW/sxswi/3E+o Xk9Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:from:date:message-id:subject :to; bh=ctJAEA+VJaPkATPJPGDq2LUk5OvubO2vzc9pJm5dJcA=; b=HGEFa7Geq/EGUoX76XTvGQ2YuJs2w9JPO4FPGT8vBOrsU/8dkcDEP/C8Pv2q04iQkE KDbEc1/nsa03CtkcHruRo51YC8/NOBaXh3ilPt3sq/vnQFUeVkvRw4TMMmQylY9tBkkV aXdtyyGjhakPcZv6accrvitABVykCpW2AEEJ2CCweSfSZqyrEcmU3wSqNJM8WO8bVWsC jY+wTA4hZLFjLPqfLCjKKNNPeGSDV+PU69riWIHnlVZfHog7YDYcwHf6Sed1wzUG5cxM RYT4bgwuvUUdcqdPbnt5XIX3F+wTIjaLeekbHc6Ag8ecClgeqlUiFhfN5h2umWlKGAoJ hUqQ==
X-Gm-Message-State: AA6/9RmrpTZ+CYUHcNIUxtOtSPuDj47DfPeShaTWjzb2+adhtquQu49zlhdgK1iBm7Uxj//LClIy75cnb/uAsA==
X-Received: by with SMTP id gz2mr31754323wjc.182.1476124722215; Mon, 10 Oct 2016 11:38:42 -0700 (PDT)
MIME-Version: 1.0
Sender: hallam@gmail.com
Received: by with HTTP; Mon, 10 Oct 2016 11:38:41 -0700 (PDT)
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Mon, 10 Oct 2016 14:38:41 -0400
X-Google-Sender-Auth: WRmhrNWafKfX9IOaj0iFCLA7VIU
Message-ID: <CAMm+LwgSMHvrH4x5473mm0_j=_4vyyMdE2Yep+CLkZjfr4ZNgQ@mail.gmail.com>
To: IETF OpenPGP <openpgp@ietf.org>
Content-Type: multipart/alternative; boundary="047d7bb70adcb642a3053e87119e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/DlIlL4FSRpzwV9bucBXsi2H1HxI>
Subject: [openpgp] Fingerprint length and application
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 10 Oct 2016 18:38:59 -0000

At the last couple of WG F2F meetings DKG asserted that we should make sure
that a given public key MUST have exactly one fingerprint representation.

This troubled me because while I don't necessarily disagree with the
statement, I can't come up for a justification for it. I now think I have a
solid justification.

The main use for fingerprints in OpenPGP is to establish direct trust. The
shortest fingerprint that is safe to use has a work factor of 96 bits and
has 20 characters:


With the compression scheme I have developed (and I am working on the IPR
implications of) we can generate a 15 character fingerprint with the same
96 bit work factor:


Which requires us to generate 2^25 keypairs

Now that 96 bits gives us a work factor of 2^96 against a second pre-image
attack but only 2^48 against a collision attack.

So consider two common uses of fingerprints:

Case 1: OpenPGP key
Case 2: PKIX trust root

These appear to be similar but they are totally different in the first case
it is quite possible for Alice to generate two OpenPGP keys that both have
the same fingerprint. And this does allow her to do some mischief. She can
sign a document such that it will be accepted by some parties and rejected
by others depending on which public key she presents to a party that trusts
the fingerprint. This is a concern but it is not one that creates a large
opportunity for malice.

The second is a much bigger concern as PKIX certificates contain use
constraints. And so the risk of collision is much greater. Let us say that
example.com has a self signed private root that has a name constraint so
that it is only trusted to sign certs for *.example.com. A malicious party
might create a pair of root certs such that one has the constraint and the
other does not. They then present the certificate with the constraint in
and the user accepts it for the limited purpose of trusting certs for
example.com. Then the attacker sends out trust paths with the second root
for bank.com etc.

So extraneous data does make a difference. It provides a salt that reduces
the cost of performing any collision type attack. But that isn't actually
an advantage for ECC keys as they are quite cheap to make and require only
an addition operation to modify. If the key is e^p, it is easy to generate
e^(p+1), e^(p+2)... till the desired criteria is met. This can be used for
work factor hardening as well.

But it makes a much bigger difference in applications like PKIX where the
fingerprint is being taken not of just a public key but a public key and
associated policy statement.

In short, don't do that. Only use short fingerprints for actual public
keys, not policy statements or data.