[openpgp] Should fingerprints be "key-canonical"?

[Bryan Ford <[e-mail]>]

Getting back to DKG’s question of whether the Unix creation-timestamp should be included in the octet-stream passed to a (future) OpenPGP fingerprint scheme…  I want to generalize the question into a choice between three options:

1. The fingerprint covers *only* the public-key material itself, in a verifiably and enforceably canonical form.

2. The fingerprint covers the public-key material and some other fixed-format stuff like version info and Unix timestamp, as in rfc4880.

3. The fingerprint covers the public-key material and some extensible variable-length information, e.g., parameters the key-holder specifies in its self-signed cert at key creation time.

As you can guess I think choice 2 really makes no sense, as it’s kind of an uncomfortable midpoint between two design approaches that has important downsides of both but doesn’t really achieve the benefits of either.  So I’ll just focus now on #1 versus #3.

The advantages I see to approach #1 (fingerprint covers public-key ONLY) are: (a) simplicity in specification and implementation; and (b) there may be security benefits in any public-key having one and only one fingerprint - IF canonical encoding is 100% enforced in current OpenPGP implementations, which may or may not be the case.

The advantages I see to approach #3 (fingerprint covers public-key and some extensible information) are that the key’s creator can bind to the key, at creation time, additional information that other parties might subsequently use in checking the validity or revocation status of a key, when importing or checking its fingerprint.  The current fixed-format bundling of Unix creation-time into the fingerprinted octet-string is just a ridiculously restrictive special-case of this otherwise potentially not-bad idea.  The question, as DKG brought up in the session, is what the range of benefits are that we might get from this flexibility, and whether they justify the added complexity, and any security risks that may arise from non-canonical fingerprints.

The general (potential) risk here - although I’m not sure how “real” it is - is that either the key-holder, or someone who manages to steal the key, can tweak the creation-timestamp and/or any other non-canonical bits that the fingerprint depends on, to create a new “public key” with a different fingerprint but the same key material as the old one.  One obvious “bad thing” that might happen is if a key-thief could use this to trick other people into not realizing a revoked key was revoked, because the key-thief is reusing the key under a different fingerprint.  But so far I haven’t been able to put together realistic-sounding attack scenarios.  I think this is in part because for anyone to trust that key in the first place, they presumably need to have verified it somehow, typically by doing something with the fingerprint, and hence an attacker who reuses a stolen/broken key with a new fingerprint doesn’t get any benefit because the new fingerprint isn’t verified/trusted by anyone.  The question is where these assumptions might fail, e.g., some application attaches trust to keys directly without verifying their fingerprints, and becomes vulnerable to this class of attack.

On the upside of allowing the fingerprint to depend on non-canonical (e.g., creator-provided) information, I understand Phil is going to post a document listing some of the uses for this type of functionality, and I look forward to seeing that.  But just to list a few potential uses I can think of:

- This information could include a creation-timestamp as a Unix time, as it is now.

- This information could include a more verifiable analog to a creation-timestamp, e.g., a signed timestamp record from a digital timestamp or notary service that actually vouches for the timestamp and publishes the timestamp in a public log.  OpenPGP implementations that receive a public key and validate it against this fingerprint could (but wouldn’t necessarily always have to) verify the signed timestamp record, and could even (again optionally) check its presence in the public log.  This might be the way to get closer to the actual security benefit that presumably motivated the inclusion of the creation timestamp in the original OpenPGP spec: e.g., it would provide some actual publicly-verifiable evidence of when the key was first created, and make it difficult for an attacker to “re-create” a broken key later without that attack being detectable.

- The information covered by the fingerprint could include “hardness parameters” that feed into the fingerprint scheme itself, enabling the key creator to obtain a configurable level of protection for the key from fingerprint-mining attacks where an attacker tries to search for other keys with fingerprints that match in the first several digits.  This was discussed at the last IETF meeting, and subsequently on this mailing list thread, so I won’t repeat it at length here: https://www.ietf.org/mail-archive/web/openpgp/current/msg08478.html <https://www.ietf.org/mail-archive/web/openpgp/current/msg08478.html>

- The information covered by the fingerprint could include hash-pointers to blockchain transactions in order to incorporate blockchain-randomness into the fingerprint (see https://eprint.iacr.org/2015/1015.pdf <https://eprint.iacr.org/2015/1015.pdf>), thereby making it extremely expensive, if not effectively impossible, for  an attacker to produce another key with the same or even a similar-looking fingerprint without the attack likely being detected.  Not every OpenPGP implementation would necessarily be expected to know how to actually verify this blockchain-randomness; implementations that don’t support it would just see it as an opaque blob of information that the fingerprint covers but that they otherwise don’t interpret.

- The information covered by the fingerprint could specify additional “canary” or revocation conditions by which parties using the key might more quickly/securely detect if and when the key might have been compromised.  For example, this information could contain a “financially incentivized auto-revocation”: e.g., a hash-pointer to an unspent Bitcoin transaction output which, if and when it is ever spent, is to be interpreted by everyone as an implicit revocation of the associated PGP key.  The key-holder funds a “key compromise bounty” by depositing some amount of Bitcoin in an account whose private key can be derived from the PGP private key.  Then if a hacker ever steals the private PG key, they get access to the bounty - but in transferring/spending it they effectively cause the PGP key to be publicly revoked, making that immediately detectable to any OpenPGP implementations that happen to support this auto-revocation mechanism.  Of course the hacker might choose to leave the bounty unspent in order to avoid compromise detection, but the higher the bounty, the fewer attackers will want to make that choice.

I’m not going to make the case that any of these potential benefits of non-canonical fingerprints are absolutely essential, but rather just explore the possibly interesting space of potential benefits from being able to use fingerprints to verify more than just a raw public key alone.  Further thoughts welcome.

Cheers
Bryan