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

From: Bryan Ford <[email-masked]>
Date: Wed, 6 Apr 2016 16:20:08 -0300

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

---

From: Jon Callas <[email-masked]>
Date: Wed, 6 Apr 2016 15:37:51 -0700

> On Apr 6, 2016, at 12:20 PM, Bryan Ford <[email-masked]> wrote:
> 
> * PGP - S/MIME Signed by an unverified key: 04/06/2016 at 12:20:08 PM

I've gone back and forth on this over the years. I finally ended up with #2 (or #3) being right enough.

If you do #1, then you make it so that you can't use the same key for multiple purposes. You can't for example use it for aliases and nyms. I think #1 is a bad idea because it tends to turn the fingerprint into a tracking identifier and I think that making your crypto be implicitly tracking-friendly is a bad idea.

So let's talk about #2 and #3 as somewhere on a continuum of saying that the fingerprint is a computable database identifier that provides some onewayness from key to fingerprint.

The way OpenPGP presently does it is kinda meh. It achieves the goal that knowing a fingerprint can find a key, but is merely onto, not one-to-one. It is, however, the way that it is.

If you change it, you end up with unknown breakage. I also don't see a *goal*. What problem are you trying to solve? I recognize that creating a new fingerprint algorithm provides an opportunity, but I have to ask why.

If you specify extra data to be thrown in, it gives the future more places to attack fingerprints in clever ways. Whatever algorithm you pick, it ought to be simple. I can see perhaps that you might want to put some "salt" into it, but if you do, it ought to be relatively small, and if it is variable-length, you need to add in the length as well.

However, despite not being able to say a lot of good things about #2 (the existing one), it is the existing one. Arguably one should keep it unless there's stated goodness to be had.

	Jon

---

From: Bryan Ford <[email-masked]>
Date: Thu, 7 Apr 2016 11:22:19 -0300

Hi Jon, thanks for the comments.

> On Apr 6, 2016, at 7:37 PM, Jon Callas <[email-masked]> wrote:
>> On Apr 6, 2016, at 12:20 PM, Bryan Ford <[email-masked] <mailto:[email-masked]>> wrote:
>> 

That’s a really good point - I definitely agree with the desirability of making fingerprints less useful as tracking identifiers.  On the other hand, one might argue that there are other ways to address this, e.g., by just having separate keys (or subkeys?) representing nyms.  If you *really* want your nyms to be unlinkable to each other it doesn’t seem avoidable that they’ll need to be based on separate keys and not just different fingerprints for the same key.

> If you specify extra data to be thrown in, it gives the future more places to attack fingerprints in clever ways.

Agreed, and this consideration definitely seems to argue for a strict 1-to-1 fingerprint-to-key relationship.

> Whatever algorithm you pick, it ought to be simple. I can see perhaps that you might want to put some "salt" into it, but if you do, it ought to be relatively small, and if it is variable-length, you need to add in the length as well.
> 

There’s nothing wrong with keeping the existing format as a legacy thing, but if we’re not actually going to do anything with the timestamp - and clearly we can’t trust it for anything anyway - I’d be in favor of either eliminating it or just fixing it to 0 as Werner mentioned Google End-to-End does.

B

---

From: Jon Callas <[email-masked]>
Date: Thu, 7 Apr 2016 16:33:56 -0700

> That’s a really good point - I definitely agree with the desirability of making fingerprints less useful as tracking identifiers.  On the other hand, one might argue that there are other ways to ad…

Yes, because I can tell you that it's *really* useful to be able to reuse the key material from [email-masked] for (e.g.) [email-masked] or security, or whatever. I've done it a lot over the years.

There's a related trick that people do in X.509 certs -- you keep a lifetime for your *key* that is longer than the lifetime of the certificate. There are a lot of reasons for it, and a lot of people do it, despite it making the PKIX purists hyperventilate. 

The trick of fingerprint = F(key, stuff) has a lot of uses. We can debate the F, and the stuff, but why toss the principle out? We don't want to make X.509 certs and S/MIME more useful.

> Agreed, and this consideration definitely seems to argue for a strict 1-to-1 fingerprint-to-key relationship.

So here's what I suggest -- either keep the way that at present the creation time serves as salt, or do something simple like add in an optional short buffer. Length of the hash is fine.

	Jon

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 09 Apr 2016 00:15:14 -0300

On Thu 2016-04-07 20:33:56 -0300, Jon Callas <[email-masked]> wrote:
>   Yes, because I can tell you that it's *really* useful to be able to
>   reuse the key material from [email-masked] for (e.g.)
>   [email-masked] or security, or whatever. I've done it a lot over
>   the years.

What is the utility here, specifically?

I appreciate making tracking/linkability harder as a goal, but i'm not
conivnced that this achieves that purpose.

Anyone who has the keys for [email-masked] and [email-masked] can
tell that these are the same keys, and can just join them in their
linkability/trackability database.

Furthermore, it introduces additional management problems for Alice; if
she loses control of the secret key material, she now has to ensure that
she's generated a revocation certificate for each "flavor" of it,
because the revocations are bound to the same material that the
fingerprint is bound to.

If the revocation were bound to the public key material, then Alice
could revoke once and be done with it.

New keys are cheap enough that Alice should be able to solve the
linkability problem y just having an entirely separate key for
[email-masked], no?

      --dkg

---

From: Jon Callas <[email-masked]>
Date: Fri, 8 Apr 2016 21:07:33 -0700

> On Apr 8, 2016, at 8:15 PM, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

Let me rewind then. PGP 2 had key-canonical fingerprints. There were issues with them. Nothing particularly horrible, but they we all of the sort of fun and games that you can play with the emergent properties of hash functions. And really, I can't remember them all that well because that was ages ago.

PGP 3 and thus OpenPGP threw the creation time in there as a quickie salt. I didn't do it. I don't know the full reasons. 

I originally thought this was dumb. I got turned around, and believe that salting the hash is a good thing. I know that I have used this property so that I can re-use key material, but it's not the total reason.

I can think of a bunch of half-assed things someone can do with key-canonical fingerprints if they are, say, the NSA. Nothing that's an attack, but just stuff.

If anything, I think that salting the hash ought to be with more than the timestamp. But really, I'd keep the fingerprint computation the same, just with a more modern algorithm than SHA-1. The problem we're trying to solve is that SHA-1 is old. I like to change only one knob at a time.

Most of all, I think that semantic properties like this shouldn't change without a reason. At present, there are uses, questionable as they are, for this, and why break it just because?

Right now, we know that for every fingerprint there is a key (modulo hash collisions), but a key can have many fingerprints. Why to we want to change it so that there's one-to-one correspondence between keys and fingerprints? This sounds to me like it's vaguely surveillance-friendly.

> because the revocations are bound to the same material that the

So? The reason to break the binding between key material and a certificate is so that there's no binding.

Actually -- this sounds like as much a reason to salt it. There are more reasons to revoke than loss of key material, and this means that revocation is even less useful.

	Jon

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 09 Apr 2016 15:09:48 -0400

On Sat 2016-04-09 00:07:33 -0400, Jon Callas <[email-masked]> wrote:
> Right now, we know that for every fingerprint there is a key (modulo
> hash collisions), but a key can have many fingerprints. Why to we want
> to change it so that there's one-to-one correspondence between keys
> and fingerprints? This sounds to me like it's vaguely
> surveillance-friendly.

i think if people want messages to be sent to different fingerprints, we
should be encouraging them to have different keys entirely, no?

> So? The reason to break the binding between key material and a certificate is so that there's no binding.

if the goal is to break the binding between the key material and the
identity information in the certificate, the right OpenPGP mechanism is
to revoke the User ID, not to revoke the primary key.

The use case i described was an attempt to revoke the primary key
entirely.

> Actually -- this sounds like as much a reason to salt it. There are
> more reasons to revoke than loss of key material, and this means that
> revocation is even less useful.

If the primary goal of key revocation is to render a key permanently
unusuable, then it would be good to be very clear about that, and not
have too many other things that it might mean.

I'm leaning in the direction that if you want to "retire" a key without
revoking it, you should do so by setting the expiration date to "now",
and not by publishing a revocation at all.  That way, direct key
revocations are less complex to reason about, because they mean exactly
one thing.

            --dkg

---

From: KellerFuchs <[email-masked]>
Date: Sat, 9 Apr 2016 19:44:32 +0000

On Wed, Apr 06, 2016 at 04:20:08PM -0300, Bryan Ford wrote:
> 2. [...]

Also, as Werner mentioned in an earlier thread, having a 1-to-1 map
  between pubkey and fingerprint makes it much easier to work with
  smartcards (or any other device) that can store the key itself,
  but no associated data (which seem to currently require
  device-specific hacks).

> 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 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.
> [...] 
> - This information could include a more verifiable analog to a creation-timestamp [...]

A user-chosen timestamp doesn't seem to do much to help check the
  key's validity, and I'm not sure a verifiable timestamp helps
  much either (imagine I put in there an attacker-chosen timestamp,
  and a block which look like a verifiable timestamp, but uses a
  method your client doesn't support).

As an aside, the Bitcoin blockchain could possibly be used as a
  timestamped, append-only log and thus implement your notary
  service (for verifiable time of creation) without using a (list
  of) centraly trusted service(s).

> - 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…

If I understand correctly (I didn't see the subject of hashing scheme
  parameters discussed in the thread you linked), it would be about
  having parameters (iteration count, memory usage, ...) as part of
  the description of the prefered hashing scheme.

Again, it's not obvious why it needs to be part of the hashed data,
  assuming the scheme parameters are displayed as part of the hash.

If I can get a human to accept “Argon2(1,8): 0123456789abcdef” in
  place of “Argon2(1000,1000): 1023456689acbdef”, the difficulty
  of generating a key with such a hash [0] doesn't seem to depend
  on whether the parameters 1 and 8 are part of the hashed data.

[0] Not the exact value 0123456789abcdef, but a “close enough” match
    to fool a human.

On the other hand, if the human carefully compares “Argon2(1,8)”
  and “Argon2(1000,1000)”, having the parameters part of the hashed
  data doesn't change anything: I have to find a close enough match
  with the keyholder's “prefered parameters”.

(Note that I'm not suggesting we use Argon for key hashes, but it
 was the first example of a scheme with “hardness parameters” that
 came to mind.  Put PBKDF2 there, or anything else, if it makes you
 happier.)

> - 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/2…

Even assuming the “Bitcoin blockchain shared RNG” scheme to be perfect,
  the “random value” is random at the time the key is generated, but
  from the perspective of the attacker it is a known constant that must
  be hashed alongside the data they control. (Worse, the attacker can
  choose any value that was previously output by the “Bitcoin RNG”)

As such, I don't see how that makes it harder to generate a key whose
  fingerprint is similar to any other given key.

Best,

  kf

---

From: KellerFuchs <[email-masked]>
Date: Sat, 9 Apr 2016 23:03:48 +0000

I will avoid re-hashing points that dkg already made.

> I can think of a bunch of half-assed things someone can do with key-canonical fingerprints if they are, say, the NSA. Nothing that's an attack, but just stuff.

Given that the NSA can easily keep around a database of all public
  keys and fingerprints they have observed, I would like to know
  what is that hand-wavy “just stuff”.

Moreover, what would be the purpose of reusing the same key material?

> If anything, I think that salting the hash ought to be with more than the timestamp. But really, I'd keep the fingerprint computation the same, just with a more modern algorithm than SHA-1. The pro…

Which purpose does the “salt” serve here?  It doesn't make it harder
  to find keys with a similar-looking fingerprint, at least...

> Right now, we know that for every fingerprint there is a key (modulo hash collisions), but a key can have many fingerprints. Why to we want to change it so that there's one-to-one correspondence be…

Again, please make this explicit.

Best,

  kf

---

From: Derek Atkins <[email-masked]>
Date: Mon, 11 Apr 2016 11:42:58 -0400

Jon Callas <[email-masked]> writes:

> Let me rewind then. PGP 2 had key-canonical fingerprints. There were
> issues with them. Nothing particularly horrible, but they we all of
> the sort of fun and games that you can play with the emergent
> properties of hash functions. And really, I can't remember them all
> that well because that was ages ago.
>
> PGP 3 and thus OpenPGP threw the creation time in there as a quickie
> salt. I didn't do it. I don't know the full reasons.

It threw in both creation time AND the (optional) expiration time!
Please don't forget the expiration time!

Unfortunately that was removed in v4 (but I don't remember why).

> I originally thought this was dumb. I got turned around, and believe
> that salting the hash is a good thing. I know that I have used this
> property so that I can re-use key material, but it's not the total
> reason.
>
> I can think of a bunch of half-assed things someone can do with
> key-canonical fingerprints if they are, say, the NSA. Nothing that's
> an attack, but just stuff.
>
> If anything, I think that salting the hash ought to be with more than
> the timestamp. But really, I'd keep the fingerprint computation the
> same, just with a more modern algorithm than SHA-1. The problem we're
> trying to solve is that SHA-1 is old. I like to change only one knob
> at a time.
>
> Most of all, I think that semantic properties like this shouldn't
> change without a reason. At present, there are uses, questionable as
> they are, for this, and why break it just because?
>
> So? The reason to break the binding between key material and a
> certificate is so that there's no binding.
>

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant