Subject: [openpgp] Fingerprint requirements for OpenPGP

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 11 Apr 2016 20:40:22 -0400

Hi all--

I was hoping to see someone write up the specific use cases for the
OpenPGP fingerprint, but i haven't seen it yet, so i'm trying to do that
here.

I tend to agree with the discussion elsewhere in this thread that
"internal database ID" is *not* the defining use case for the
fingerprint, so i'm not including it here.

I think there are only two use cases:

 a) looking up a particular OpenPGP key in some remote database like a
    public keyserver
 
 b) confirming that a particular key matches some out-of-band
    communication

These are things that might happen by fingerprint transfer via any of:

 * business cards (pre-planned, printed)

 * scraps of paper (impromptu, hand-written)

 * over the telephone or other voice channels

 * copy and paste from a non-OpenPGP-specific message (chat, e-mail,
   etc)

Note that a human is always in the loop in these transfers.  If no human
is in the loop, we do not need the fingerprint, and can (and probably
should) use some other technique.

As such, i think we have these human-specific constraints:

 * the fingerprint should be identifiable as a fingerprint, including
   where it starts and where it stops.

 * it should avoid ambiguity -- readers shouldn't have to puzzle over
   whether a character is an "o" or an "O" or a "0", for example, and
   writers shouldn't have to worry about it either.

 * there should be one (and exactly one) fingerprint per key; otherwise
   comparisons become impossible.

 * it should be as close as possible to the human attention span -- this
   is Vincent's point, i think.  Humans really can't reliably deal with
   512 bits of entropy when doing any kind of data entry or comparison.

 * data entry should be easy to do with standard tools

And we have these machine-specific constraints:

 * it should be cheap to compute from a given key -- you shouldn't need
   a gig of RAM or a minute of CPU to calculate the fingerprints of any
   key.

 * it should be strong enough that we do not believe anyone can create a
   key with a fingerprint that collides with another key's fingerprint

And these spec constraints:

 * it should be easy for implementers to understand and generate

Is this problem framed correctly?

If not, what's missing?

If so, can someone try to apply it to one of the fingerprint proposals
and see what the takeaway is?

   --dkg

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 12 Apr 2016 10:34:09 +0200

>    512 bits of entropy when doing any kind of data entry or comparison.

Yes.

>    a gig of RAM or a minute of CPU to calculate the fingerprints of any

Strictly speaking, we can be slightly less restrictive: It must be cheap
to verify, given a fingerprint, that it's the correct one for a key.
This distinction does not make a difference unless we store the
fingerprints as part of the data format (which we probably shouldn't),
so this is more of an academic point.

>    key with a fingerprint that collides with another key's fingerprint

Quite importantly, this should be "another *independent* key's
fingerprint", i.e. the requirement is preimage resistance, not collision
resistance.  Creating two keys with colliding fingerprints is fine, at
least noone could come up with a attack scenario where it mattered.

 - V

---

From: Joseph Lorenzo Hall <[email-masked]>
Date: Tue, 12 Apr 2016 09:06:11 -0400

> least noone could come up with a attack scenario where it mattered.

I don't think I'm understanding this. If you have two keys that map to
the same fingerprint, then an attacker can decide to serve you
whichever is in their best interest. Doesn't that mean that
fingerprint collisions from different keys is specifically something
we want to avoid? Or am I missing the "*independent*" element of your
comment here?

-- 
Joseph Lorenzo Hall
Chief Technologist, Center for Democracy & Technology [https://www.cdt.org]
e: [email-masked], p: 202.407.8825, pgp: https://josephhall.org/gpg-key
Fingerprint: 3CA2 8D7B 9F6D DBD3 4B10  1607 5F86 6987 40A9 A871

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 12 Apr 2016 15:15:45 +0200

Joseph Lorenzo Hall([email-masked])@Tue, Apr 12, 2016 at 09:06:11AM -0400:
> If you have two keys that map to the same fingerprint, then an
> attacker can decide to serve you whichever is in their best interest.

The premise of your scenario is that you are already using a key
generated by the attacker. What could an attacker possibly gain by
possessing a second key with the same fingerprint?

 - V

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 12 Apr 2016 10:32:47 -0400

On Tue 2016-04-12 04:34:09 -0400, Vincent Breitmoser wrote:
> Strictly speaking, we can be slightly less restrictive: It must be
> cheap to verify, given a fingerprint, that it's the correct one for a
> key.  This distinction does not make a difference unless we store the

Right, i don't think we should store the fingerprint as part of the data
format, so we still need to be able to rapidly generate it, not just
verify it.

> fingerprint", i.e. the requirement is preimage resistance, not
> collision resistance.  Creating two keys with colliding fingerprints
> is fine, at least noone could come up with a attack scenario where it
> mattered.

This clarification also matches my understanding.  Thanks for the
precision, Vincent.

  --dkg

---

From: Derek Atkins <[email-masked]>
Date: Tue, 12 Apr 2016 10:38:29 -0400

Hi,

Thank you for your writeup....

Daniel Kahn Gillmor <[email-masked]> writes:

[snip]
>  b) confirming that a particular key matches some out-of-band

I would argue that (b) is more important than (a).  Your use-case (a)
sounds more like a DB Handle, so arguably it should be elided because
you've scoped your specification saying that "internal database ID is
not the defining use case".   Or are you saying that we have both an
internal database ID and an external database ID?

Beyond that, I agree with the rest of what you said.

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

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 12 Apr 2016 12:13:18 -0400

> internal database ID and an external database ID?

yeah, i thought about this and went ahead with an inclusion of (a)
anyway; think we don't need to specify any internal DB handles, but we
do need a way to communicate across external database boundaries.

I concede that if we define the fingerprint for use as an *external* DB
handle, it's entirely likely (and reasonable) for implementers to use it
as an internal DB handle as well, but i don't think we need to specify
it as a target use case.

If we say that use case (a) isn't a motivating use case for the
fingerprint, do we have a story to tell about how an implementation
might retrieve a specific key from an external database?  or do we not
need to tell that story?

     --dkg

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 12 Apr 2016 12:23:26 -0400

Hi,

[snip]
> do need a way to communicate across external database boundaries.

Do we?

> as an internal DB handle as well, but i don't think we need to specify

That's kind of what's happened already, and it's what brought us to where
we are.

> might retrieve a specific key from an external database?  or do we not

When a human needs to look up a key there is usually some other identifier
involved.  Most likely it would be the UserID.

The way I see the process is:
1) I receive business card or some other form that has email + Fingerprint
2) I download key from some server using the email address
3) I verify the key using the fingerprint (to make sure it's the right one).

The fact that the fingerprint *could* be used as an identifier is what led
us to these questions.

If I want to verify a signature it can use the internal database ID -- no
human interaction required.

So I just don't see the use case where a human ONLY has a fingerprint
without any other identifying information and needs to download the key.

-derek

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 12 Apr 2016 12:47:14 -0400

> The fact that the fingerprint *could* be used as an identifier is what led

right, thanks for pushing on this.  I'm curious what the rest of the WG
thinks about this use case.  if we can simplify the requirement down to
just (b) that would be nice.

One concern i have with existing keyserver infrastructure is that anyone
can upload a key with any e-mail address.  This could result in a lookup
that returns dozens or hundreds of keys.

Being able to constrain a lookup by a stable, unforgeable identifier
mitigates this flooding attack.

I'm not saying that mitigation is necessarily important enough to make
it a guiding requirement for the fingerprint, though.

And perhaps this lookup-flood is an issue that could be fixed some other
way too?

wdyt?

        --dkg

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 12 Apr 2016 16:52:49 +0000

> One concern i have with existing keyserver infrastructure is that anyone can
> upload a key with any e-mail address.  This could result in a lookup that
> returns dozens or hundreds of keys.

It would be nice if PGP were so successful :)

The keyservers can address this by sending PGP-encrypted "please confirm" email.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 12 Apr 2016 13:02:25 -0400

> It would be nice if PGP were so successful :)

I agree with you, but this concern isn't about success, it's about a
malicious flooding attack :/

> The keyservers can address this by sending PGP-encrypted "please confirm" email.

that doesn't work with the model of the keyserver network, where
untrusted peer keyservers gossip data between each other.  i'm pretty
sure we don't want a "please confirm" e-mail from each keyserver
operator, and i think most keyserver operators don't want the
responsibility of running such a vetting service.

If the answer is "throw away the keyserver network" then that's one
thing; but if we think there needs to be a public directory lookup, then
we need a clear explanation of how that works.  i understand from
Vincent's recent thread that people seem to be actively thinking about
alternatives, which is a Good Thing.  but even Vincent's thread doesn't
seem to cover revocation.

               --dkg

---

From: Werner Koch <[email-masked]>
Date: Tue, 12 Apr 2016 19:01:14 +0200

> should) use some other technique.

Given that the fingerprint is of constant size or at least has an upper
limit, it has advantages in protocol design too.  I can see only two
other options:

 - Some newly made-up identifier.  This brings us back to
   the X.509 mess of several ways to locate a key.

 - Using the the full public key: This would be fine for ECC, is
   troublesome for RSA, and for PQC it would be ridiculous large.

Thus I think a binary fingerprint is even preferable with no humans in
the loop.

>    a gig of RAM or a minute of CPU to calculate the fingerprints of any

According to Peter, this means SHA-256.  There may be no proof-of-work
to for creating a key and thus a structured fingerprint.  (Sometimes you
have to create a lot of one-off keys.)

>    key with a fingerprint that collides with another key's fingerprint

As Vincent pointed out, we only need preimage resistance.

> If not, what's missing?

Whether to hash a

  a) fixed string and a creation date,
  b) fixed string and creation date and a hard expiration date,
  c) fixed string,
  d) nothing

in addition to the algorithm parameters.  My conclusion from the
discussions is that we should to decide between a) and c).  I don't
really care given that using a creation date of 0 can be used when
needed.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Werner Koch <[email-masked]>
Date: Tue, 12 Apr 2016 19:18:04 +0200

> sounds more like a DB Handle, so arguably it should be elided because

(a) is required to lookup a key for a signature.  Sure this could also
be done using mail address included in the signature.  But a fingerprint
can work even if a mail provider re-assigns a mail address (assuming the
mail provider uses OpenPGP DANE or PKA).

Right now a signature includes only a keyid but for rfc4880bis we will
add a new subpacket for the fingerprint.

Shalom-Salam,

   Werner

---

From: KellerFuchs <[email-masked]>
Date: Tue, 12 Apr 2016 17:22:46 +0000

> This clarification also matches my understanding.  Thanks for the

I think it is sane here to require collision resistence, because that's what
  multi-target preimages devolves to: an attacker might not want to target
  one specific key, but one amongst a large set of key (says, the developers
  of a popular software, or perhaps any “widely signed” key in the WoT).

In that case, the attacker gets a non-trivial speedup, and as the set of
  targets grows larger, the hardness of the problem devolves into that of
  finding a collision.

Moreover, colision resistence implies second-preimage resistence, and hash
  functions are usually considered “broken” by cryptographers once there is
  an attack for colisions, so it seems OK to be somewhat cautious here and
  require collisions to be hard.

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 12 Apr 2016 13:44:17 -0400

Werner,

> add a new subpacket for the fingerprint.

This would fall under an "internal DB Identifier."  DKG called that out of
scope for this discussion topic.

There is no human in the loop here.  That means it does not need to be
"the same" as the user-visible "fingerprint".

-derek

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 12 Apr 2016 14:18:25 -0400

> have to create a lot of one-off keys.)

The one proposal i've heard that keeps things somewhat simple but still
allows the possibility of an increased cost to an adversary intent on a
preimage attack is related to floating point implementations, and was
suggested by PHB.  I try to describe my understanding of the scheme
below, but writing it all down makes me think that "somewhat simple"
might be overselling it; there are quite a few complications.

Here goes:

 * Start from a design of a fingerprint of X bits, using a truncation of
   digest of size Z (where Z > X).  for example, a 200-bit fingerprint
   from sha-256.  this would typically mean an adversary has to do about
   2^200 sha-256 operations to find a match.  (this is an impossibly
   high bar if we're talking about brute force, but if we assume that
   most cryptanalysis of SHA-256 allows an attacker to shave off some
   sizeable work factor, it represents the "safety margin" against
   unknown cryptanalysis of this type)

 * Instead, make the fingerprint X+N bits, where the first N bits
   indicate the number of leading zeros of the digest.  Now if i do a
   bit of work to generate keys with, say, 10 leading zeros, an attacker
   will probably need to do about 2^10 more digests to find a match.

So if we're doing a 200-bit truncation of sha-256, and we have an 8-bit
count of leading zeros, and the digest produced is (in hex -- i'm not
making an argument about choice of textual representation here, just
showing in hex for discussion):

 001a1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da52e6ccc26fd2

then it would result in a fingerprint of (again in hex for discussion):

  0ba1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da5

That is: 11 (0x0b) bits of zeros, followed by a 1 bit, followed by
a1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da5

More precisely, under this scheme, fingerprint generation looks like:

scan1(x) : the position of the left-most 1 bit in bitstring x
  A[n:m] : bits n through m-1 of bitstring A
enc(n,b) : a bitstring of length b encoding n as an unsigned int
 dgst(x) : a fixed-length bitstring digest of bitstring x (e.g. sha-256)
       X : number of explicitly-represented bits
       N : size of bitfield for counting leading zeros
      || : bitstring concatenation

 def fpr(z):
    h = dgst(z)
    k = scan1(z)
    return enc(k,N) || h[z+1:z+1+X]

 * note that first bit that is set to 1 is omitted from the
   representation (it's present by implication).  This isn't just a hack
   to squeeze one more bit of entropy out of the fingerprint, it's
   arguably necessary to ensure that there is exactly one fingerprint
   that corresponds to any given digest. Otherwise, i can represent a
   fingerprint with 3 leading zero bits as:

 <3> 1100101...

   or:

 <2> 01100101...

   or:

 <1> 001100101...

   or:

 <0> 0001100101...

    The other alternative is to require that the leading bit after the
    zero-run prefix is always 1 (unless the zero-run prefix is maxed
    out?), which would mean that certain fingerprints are simply invalid
    (we'd want tools to reject them?)

  * note also that for some choices of dgst and N it would mean there
    could be some keys that are un-fingerprintable.  For example, if we
    chose dgst = sha-256 and N = 5, then any key that has a sha-256
    digest with a leading run of more than 31 zeros might be
    unrepresentable.

With all these caveats, i confess the much-simpler construction "200-bit
truncation of sha-256" looks pretty appealing :)

           --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 12 Apr 2016 14:38:05 -0400

>   targets grows larger, the hardness of the problem devolves into that of

The size of the set of possible targets is relevant here, though, right?
if the pool of available targets is 2^16, you're not going to get more
than a 2^16 speedup by targeting them.  Even if we had a separate key
for every IPv4 address, that'd only be a 32-bit reduction in work
factor.

by comparison, a pre-image brute force costs 2^(2X) when a collision
attack costs 2^X due to the "birthday paradox".

We're talking about fingerprints in the range of 2^160 (the OpenPGPv4
fingerprint) and 2^256 (probably the upper bound of what we can expect
humans to be able to deal with).

so you'd need a pool of keys to attack on the order of 2^80 or 2^128 to
get a comparable speedup.

>   require collisions to be hard.

I think we're in quite a bit of trouble if we actually need both
collision resistance and any sort of plausible human-accessibility for
high-entropy strings.

          --dkg

---

From: Werner Koch <[email-masked]>
Date: Tue, 12 Apr 2016 21:51:10 +0200

> scope for this discussion topic.

It is not "internal" because it is part of the OpenPGP protocol
(Signature Packet) and thus visible by all who are verifying a
signature.

I define "internal" as a property of the implementation - maybe this is
the misunderstanding.

> "the same" as the user-visible "fingerprint".

Need not, right.  But adding yet another identifier to a key only leads
to more confusion and more complex error handling.  I do not expect that
you want OpenPGP to repeat the error made by X.509.

Salam-Shalom,

   Werner

---

From: Jon Callas <[email-masked]>
Date: Tue, 12 Apr 2016 15:26:42 -0700

> On Apr 11, 2016, at 5:40 PM, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

Actually, I don't think it's framed correctly.

I don't think distinguishing between local and remote databases is necessary; I know I'm picking a nit here, but the design of many systems is such that there isn't a difference. But moreover, a real remote database is as likely to need to answer the question, "give me the key(s) for <identifier>" where the identifier might be a fingerprint and might be something like an email address.

Like I wrote before, there are two major uses for a "fingerprint," a handle and an auth string. 

Moreover the auth-string use case of fingerprints is actually the auth string of the crypto key that is the top-level signing key of the "PGP key", which is a data structure that usually consists of at least two crypto keys.

But the handle that turns into a key id is presently derived from the fingerprint of a subkey that's used for encryption.

I think it's completely reasonable to update the standard to take the old-style fingerprint into better hash functions than SHA-1. It's imperfect but it's the devil we know.

If you want to move into devils we don't know, then why *not* make an auth-string that is a different thing than handle?

As you're describing the use cases, you've described something that you can't solve. There's nothing wrong with noting that both circles and squares have desirable properties, but you're not going to get space-filling circles or a square that's got the perimeter equidistant from the center. 

	Jon

---

From: Bill Frantz <[email-masked]>
Date: Tue, 12 Apr 2016 18:00:51 -0700

I have not heard anyone arguing that we don't need some form of 
fingerprint that can be typed into a computer for comparison. 
(Several have argued that eyeball comparison is error prone.)

Well, typing random data is error prone too. Perhaps we should 
have some form of check digit(s) so the program processing the 
type in can flag bad data entry and not confuse it with 
fingerprint match failure.

Cheers - Bill

--------------------------------------------------------------
Bill Frantz        | There are now so many exceptions to the
408-356-8506       | Fourth Amendment that it operates only by
www.pwpconsult.com | accident.  -  William Hugh Murray

---

From: Werner Koch <[email-masked]>
Date: Wed, 13 Apr 2016 09:20:45 +0200

> really care given that using a creation date of 0 can be used when

Of course we would add a creation date self-signature subpacket which is
used iff the creation date from the public key packet is 0.  This allows
to see which scheme implementations will prefer.

Salam-Shalom,

   Werner

---

From: Derek Atkins <[email-masked]>
Date: Wed, 13 Apr 2016 10:20:36 -0400

> format, so we still need to be able to rapidly generate it, not just

Nothing stops an implementation from storing the computed fingerprint
alongside the key/certificate.  Indeed, I would encourage
implementations to do just that for speed, especially with extremely
large keyrings.

-derek

---

From: Derek Atkins <[email-masked]>
Date: Wed, 13 Apr 2016 10:22:17 -0400

> get a comparable speedup.

This was my thought, too.  The pool isn't going to get large enough to
really bring the preimage work down to collision-level work.

> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp

---

From: Derek Atkins <[email-masked]>
Date: Wed, 13 Apr 2016 10:27:04 -0400

Werner,

> I define "internal" as a property of the implementation - maybe this is

Probably.  To me the key part of "internal" means "a human never sees
it".  I'm considering "internal" to be "in the data formats", which can
be used between implementations and not just within a single
implementation.

> you want OpenPGP to repeat the error made by X.509.

We already, to some degree, have that issue.  There's the keyID and
there's the fingerprint.  They are different (although with v4 one is
derived from the other).

I think we need to step back again and keep in mind that the (human)
authenticaton fingerprint may (should?) be different from the (internal
or external) database identifer string.

-derek

---

From: Derek Atkins <[email-masked]>
Date: Wed, 13 Apr 2016 10:30:05 -0400

> Thus I think a binary fingerprint is even preferable with no humans in

Agreed.

> really care given that using a creation date of 0 can be used when

I still believe we should use b, with the knowledge that the hard
expiration is optional (could be 0).  This would protect against an
attack where you lose control of your secret material and the attacker
creates a new self-sig with a new expiration time.

-derek

---

From: Joseph Lorenzo Hall <[email-masked]>
Date: Wed, 13 Apr 2016 11:23:44 -0400

> possessing a second key with the same fingerprint?

Sorry so slow to respond... my premise is that increasingly I query
for full fprs to obain keys from keyservers and if that maps onto two
different keys with the same UserID that would be bad.

I guess what the rest of the thread here is saying is that it would be
so computationally difficult for a malicious keyserver to find a
collision that this isn't a problem.

(apologies for being somewhat dense)

---

From: Werner Koch <[email-masked]>
Date: Wed, 13 Apr 2016 17:59:07 +0200

> there's the fingerprint.  They are different (although with v4 one is

In GnuPG 2.1 we removed support for v3 keys and thus we do not need to
care about the difference between keyid and fingerprints anymore.  This
takes away a lot of burden we had with them (in particular storing the
keyid for fast lookups).  Using a truncated fingerprint for the keyid, as
we have in v4, is easier. 

> or external) database identifer string.

Okay.  But the new scheme should allow to derive the human
authentication fingerprint from the internal fingerprint w/o the need
for additional input.

Shalom-Salam,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Wed, 13 Apr 2016 18:02:09 +0200

> creates a new self-sig with a new expiration time.

Although I do not see a real need for this, I would accept this.

Salam-Shalom,

   Werner

---

From: Vincent Breitmoser <[email-masked]>
Date: Wed, 13 Apr 2016 19:07:51 +0200

>   usually considered “broken” by cryptographers

This is not the general case cryptographers talk about, but a specific
use case with a very specific set of requirements.

>   so it seems OK to be somewhat cautious here and require collisions
>   to be hard.

If we could get it for free, maybe. But collision resistance is a factor
two in bitsize, which is not only not free, but pretty darn costly.

Just to get a feeling for the numbers, let's do some good old
pessimistic math:

We take a 128 bit fingerprint. We say the attacker wants to attack a
pool of 65000 keys, so 2^16. That leaves 112 bits of fingerprint to
attack. We also assume that an attacker can test as fast as they can
generate sha-256 hashes, and give no penalties for key generation,
multi-target attack, collisions or stuff like that.

Top of the line hashing ASICs are at about 5 terahashes per second. But
let's just say our attacker has 10 terahashes/s (2^43) per device for
ease of math. Then let's say our attacker has one *billion* of those
devices (2^30), which is a ridunculous number to have.

In this scenario, our attacker needs 2^(128-16-43-30) = 2^39 seconds to
find a single preimage, which is 17432 years.

From a different angle, for one Joule of energy (= 1 watt-second) you
can very optimistically get about 5T (2^42) sha256 hashes for one Joule
of energy. For 2^112 hashes, that's 2^(112-42) = 2^70 Joule of energy,
or 2^19 terawatt-hours of energy. For comparison, the total world energy
consumption is around 2^17TWh per year, so that's something like four
years of energy (not even only power) used by people in the world.

 - V

---

From: Joseph Lorenzo Hall <[email-masked]>
Date: Wed, 13 Apr 2016 19:42:02 -0400

that is pretty damn convincing to me, thanks

---

From: Derek Atkins <[email-masked]>
Date: Thu, 14 Apr 2016 11:17:48 -0400

> authentication fingerprint from the internal fingerprint w/o the need

Well, this then begs the question of whether this internal fingerprint
may include additional information or if it's purely on the actual key
material.  I've lost the mental context for the argument that the
identifier should be on the actual public key and not the "key
certificate".

Provided that the fingerprint is over the "public key certificate"
(i.e., public key parameters plus some additional data such as creation
and expiration times) I have no objection to the "human authentication
fingerprint" being derived from that.

-derek

---

From: Derek Atkins <[email-masked]>
Date: Thu, 14 Apr 2016 11:20:49 -0400

> collision that this isn't a problem.

That's not a collision, that's a preimage attack.

A collision is where Eve generates a pair of keys together with the same
fingerprint, but doesn't care what that key/fingerprint is -- only that
they are the same.  A preimage attack is where you're trying to find a
key that matches a specific (existing) fingerprint.  That's a MUCH
harder attack.

So yes, it would be extremely difficult for Eve to generate a key with
the same fingerprint as Alice's key.

-derek

---

From: Joseph Lorenzo Hall <[email-masked]>
Date: Thu, 14 Apr 2016 12:39:46 -0400

> the same fingerprint as Alice's key.

Thanks for this, and for putting up with my relatively cryptographic
naivete for this WG!

best, Joe

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 14 Apr 2016 19:29:52 +0000 (UTC)

Sent from Outlook Mobile

    _____________________________
From: Bill Frantz <[email-masked]>
Sent: Tuesday, April 12, 2016 9:01 PM
Subject: Re: [openpgp] Fingerprint requirements for OpenPGP
To: IETF OpenPGP <[email-masked]>

Cheers - Bill

There are many use cases for typing in a fingerprint. I want to send someone a mail, I read their fingerprint off a business card or they read it over the phone or I cut n'paste from somewhere.Comparison is more common though. And that allow us to use 'big dictionary' type approaches.
I am working on a doc, but there are some important points from the WG meeting. One is that there seems to be a confusion between whether the fingerprint or the key is a root of trust. If you think it is the key that is the root of trust then the fingerprint has to be canonical, must not include a date stamp (like it does at present). If however you regard the fingerprint of the key as the root of trust then it does not need to be canonical. Invalidating a key in one context does not necessitate invalidating it in all contexts. The catch being that when the key is presented for validation, you have to also present all the original attributes bound to it.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 16 Apr 2016 11:56:21 -0400

This is almost the scheme I am looking at. The main practical
difference is that I don't see the need to be quite so granular. If
people are going to use proof of work, then I would start off with a
threshold designed to take about an hour of processing on contemporary
machines, for the sake of argument, say that is 24 bits. Then I would
allow for prefixes of 24, 34, 40 bits.

This approach can be encoded using a leading 1s approach. So each
increase in work saves 7 bits.

The increase in work may look dramatic, but it really isn't because I
expect people would throw parallel machines at the problem. Also note
moving from RSA to ECC saves a huge chunk of keygen time. So any
compression scheme is having to deal with a vast difference in
computing demands and capabilities.

The wonderful thing about exponents is that they tend to quickly
balance any mismatch in such things.

The other trick I think is very useful is to use truncated
fingerprints as keyIds. Lets say that we start with a SHA-51

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 16 Apr 2016 12:57:57 -0400

@#($*@#(!! Gmail sent the other one too soon.

On truncation, there are some game we can play. Lets say that we start
off with a 256 bit hash. Now I am only using SHA-2-512 and SHA-3-512
because I want to have as many rounds as possible even if I am going
to discard bits

I distinguish between the following

1) The hash output size (512 bits for UDF)
2) The fingerprint size (250 bits for UDF)
3) The presentation size (varies from 25 bits to 250 bits in 25 bit increments)

So the has output is 512 random bits which give the following fingerprint:

MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ-SV75J-C4OZQ-5GIN2-GQ7FQ-EEHFI

This may be presented as

phill-6DUF5@hallambaker
MB2GK-6DUF5-YGYYL-JNY5E
MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ
...
MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ-SV75J-C4OZQ-5GIN2-GQ7FQ-EEHFI

Depending on the context.

Now note here that I am assuming that users will be using subkeys and
so in most contexts, a PGP fingerprint is of a key that under best
practice is only ever used to sign other keys. The only case where it
is not is when someone has already identified the signing key and is
looking for the correct sub key for a specific operation.

At the moment, a general overhaul of the OpenPGP key distribution
system is out of scope. But it is my view that we should consider the
possibilities for a new key distribution infrastructure when we design
a new fingerprint scheme. Our choices here will open or close future
options.

In particular, I am assuming that there will be a convergence of the
OpenPGP, SSH and S/MIME key distribution mechanisms (all suck today)
and that this convergence will result in the emergence of a new
infrastructure that looks somewhat like 'BaL's MIT key server plus
blockchain'.

This is what I am currently building in the Mesh. The idea is that the
Mesh is a hash chain notarized, append-only log that can be written to
from multiple input streams (portals) and finalizes every hour or so.

So if you have that type of backing infrastructure, you can take a
short presentation of a fingerprint, 'MB2GK-6DUF5-YGYYL-JNY5E' and
consult the Mesh to receive back a record that gives you the
corresponding public key record and the full length fingerprint.

This allows me to make fingerprints really short since all that is
necessary is to distinguish them in context. phill-6DUF5@hallambaker
only needs a 25 bit fingerprint presentation because it is only
necessary to distinguish the key from any prior keys for
[email-masked] that have been checked in previously.

[Yes, this uses the second block of the fingerprint. That is because
the first block ends up filled with control information]

This approach is similar to the 'last four digits' of your credit card
number which is rather hilariously used as an abstract for the whole
card number. It is hilarious because the first six digits are the bank
identification number and there is one digit of checksum. Many small
banks have less than 100,000 accounts and so they only actually use
the last 6 digit fields.

In our context, the approach is secure because people won't be
creating a thousand fingerprints for their own use and expecting them
to work.

There are two considerations for fingerprint size

1) How many data items do we want to hash?
2) What is the work factor we want to set for breaking any one of them?

When we are talking about OpenPGP fingerprints, I think the first
number is about 2^40 the global population is roughly 8 billion (2^33)
and a hundred trust roots per user seems enough for a lifetime.

For work factor, the very lowest lower bound would be 2^85 right now
which gives us a total work factor of 2^125 as the very lowest
fingerprint size to be considered 'safe'.

Using the 'work hardening' approach described in the earlier message,
we can create a 100 bit signature that has a work factor of 2^125.
Which is short enough to fit on a business card.

There are many contexts where I would not want to do work hardening
though. Particularly in an enterprise network where I am creating keys
for individual devices.

The considerations for sub keys are rather simpler as there we only
need to consider how many keys the parent has signed. Lets say the sub
key distinguisher is E34TG, we might represent that in a config file
as follows:

MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ/E34TG

Now all this is quite a bit more complex than OpenPGP alone needs or
you are going to accept right now. But it is mechanism that delivers a
lot of power and convenience if it can be applied to all a user's
cryptographic applications.

Wouldn't it be nice if you could cut and paste your single Mesh master
key fingerprint into a PGP application, an SSH application and an
S/MIME application and have them all 'just work'?

Another game that can be played with master keys is the one I outlined
in the Arcing BOF and I am writing up a paper on. A key fingerprint is
a root of trust. It is convenient to be able to embed roots of trust
into other identifiers. Over the past few years I have played with the
following embedding schemes:

MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ?[email-masked]
[email-masked]
[email-masked]

The last is my preferred approach. It would be pretty easy to
configure a DNS client to consider any TLD of 19 characters or more to
be a fingerprint of a root of trust that governs the interpretation of
the rest.

The client begins by resolving MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ using
whatever infrastructure exists for that task (lets call it the Mesh
because we have already used nets and webs and mesh was the only one
left I could think of).

So the root of trust signs some record that says something like:

{"DNSSEC" : "MLFXX-KIDDN-BSWG2-3FMQQ-GE5LU-EBXG6",
 "TLS" :  "MKRUG-S4ZAN-FZSAY-LMONX-SAZTB" }

These are two trust roots that can be used to interpret the address
"[email-masked]". The first is the ICANN DNSSEC root, the
second is a local intermediate PKIX cert for the TLS.

[It isn't necessary to identify a new trust root for OpenPGP of course
because that key would simply be signed in OpenPGP]

Yes, there are a lot of options. But creating a lot of options does
not mean that we have to have a lot of complexity. Right now, the UDF
draft is an 8 pager, most of which is boilerplate:

https://tools.ietf.org/html/draft-hallambaker-udf-03

I will drop in the description of the work hardening. It is simply a
new algorithm type.

The only impact this has on the OpenPGP use is that instead of the
fingerprint being

Fingerprint = H (OpenPGPFormat (Key))

It is instead:

Fingerprint = VersionID + H ( "application/open-pgp-key" + H
(OpenPGPFormat (Key)))

Making that one change (i.e. adopting my draft) makes the fingerprint
format the cornerstone of integration of OpenPGP, SSH and more into a
single interoperable cryptographic infrastructure.