[openpgp] Fingerprint length and application

[Phillip Hallam-Baker <[e-mail]>]

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:

MB2GK-6DUF5-YGYYL-JNY5E

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:

MIWIY-LTMFTG-CZTRO

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.