Re: [openpgp] Mining protection in fingerprint schemes

[Bryan Ford <[e-mail]>]

On Apr 9, 2016, at 2:35 AM, Jon Callas <[e-mail]> wrote:
> At present, we use the key fingerprint as the authentication string. The mining protection he's suggesting isn't a bad thing. My raised eyebrow comes from conflating the two. We need to have a "DB handle" and I believe the DB handle needs to be easy to compute (key-canonical is an orthogonal issue). The fingerprint gets used all over the place, especially in its truncated form as key-id.

I agree that “fingerprints” used purely as internal DB-handles or indexes are a separate purpose from “fingerprints” presented to users and displayed on business cards and websites, and it may well be worth treating them separately.

With that in mind, here’s one terminology suggestion.  Previous versions of PGP by default tend to use small, weak somethings it calls “key IDs” as the normal user-presentation form of fingerprints.  We know that encouraging users to depend on key IDs for anything - or even to understand that “Key ID” collisions are possible and eminently mineable - and hence we know that “Key IDs” of this kind need to die.  

But if we consider “PGP tradition” terminology to be that “fingerprints” are supposed to be full-length DB handles for internal use, whereas “key IDs” are something related but different for user display and consumption, we could make both of them better in V5 while preserving this terminology convention.

In particular:

- V5 “fingerprint" is just a raw SHA384 or SHA512 hash of the key material (with or without timestamp or other stuff, depending on the WG’s decision on that orthogonal issue).  This is the “DB-handle”.  It’s never expected to be presented into the user or put on business cards.

- V5 “key ID” is derived from the V5 fingerprint and shortened for presentation to the user - but shortened only to ~256 bits, not shortened to the point of insecurity like V3/V4 key IDs are.  That shortening could easily include simple Key ID mining-protection.

This would make new “Key IDs” actually safe to use for the purposes they tend to get used for, while avoiding the usage conflation with the “DB handle” purpose of fingerprints.  PGP implementations could go on displaying “key IDs” by default when listing keys, only for V5 keys these key IDs would now be long enough to provide meaningful protection.

What is the actual function from “fingerprint” to “key ID”?  Three alternatives spring to mind:

1. Truncation, from 384 or 512 bits to 256.  Trivial but offers no possibility of Key-ID mining protection.

2. Simple mining protection: Key ID is one digit representing number of leading zero hex digits in fingerprint, followed by encoded final 256 bits of fingerprint.  Basically PHB’s suggestion.

3. Memory-hardened mining protection: use fingerprint as nonce for a small Argon2 run, then SHA384 or SHA512 hash the output of that, and finally encode as in option 2 above (one-digit representing number of leading zeros followed by encoding of last 256 bits).

All of these alternatives allow the “fingerprint” to be used as an internal DB-handle with no added complexity or inefficiency, while adding only a rather small amount of complexity and cost purely to the conversion from internal-purposed “fingerprint” to user-presentation-oriented “key ID”.  If the WG doesn’t perceive the added protection of memory-hardening in option 3 is worth the costs, then option 2 would seem at least to me to have pretty much negligible cost.

Bryan