Subject: Re: [openpgp] Proposed text for V5 fingerprint

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 6 Sep 2016 00:47:26 -0400

Here is the revised proposed text. I am trying to work out what the
instructions on using gitlab mean. How does making a pull request put
updates into a repo?

There is a piece of technology that I would very much like to propose using
but it is very much encumbered :-( So I am going to propose that separately
and see if we can get the IPR sorted in time to use it. For the time being
it is not in the draft.

## {12.2} Legacy Key IDs and Fingerprints

For a V3 key, the eight-octet Key ID consists of the low 64 bits of
the public modulus of the RSA key.

The fingerprint of a V3 key is formed by hashing the body (but not the
two-octet length) of the MPIs that form the key material (public
modulus n, followed by exponent e) with MD5.  Note that both V3 keys
and MD5 are deprecated.

A V4 fingerprint is the 160-bit SHA-1 hash of the octet 0x99, followed
by the two-octet packet length, followed by the entire Public-Key
packet starting with the version field.  The Key ID is the low-order 64
bits of the fingerprint.  Here are the fields of the hash material,
with the example of a DSA key:

    a.1) 0x99 (1 octet)

    a.2) high-order length octet of (b)-(e) (1 octet)

    a.3) low-order length octet of (b)-(e) (1 octet)

         b) version number = 4 (1 octet);

         c) timestamp of key creation (4 octets);

         d) algorithm (1 octet): 17 = DSA (example);

         e) Algorithm-specific fields.

    Algorithm-Specific Fields for DSA keys (example):

    e.1) MPI of DSA prime p;

    e.2) MPI of DSA group order q (q is a prime divisor of p-1);

    e.3) MPI of DSA group generator g;

    e.4) MPI of DSA public-key value y (= g\*\*x mod p where x is secret).

Note that it is possible for there to be collisions of Key IDs -- two
different keys with the same Key ID.  Note that there is a much
smaller, but still non-zero, probability that two different keys have
the same fingerprint.

Also note that if V3 and V4 format keys share the same RSA key
material, they will have different Key IDs as well as different
fingerprints.

Finally, the Key ID and fingerprint of a subkey are calculated in the
same way as for a primary key, including the 0x99 as the first octet
(even though this is not a valid packet ID for a public subkey).

## {12.3} V5 Fingerprint

A V5 Fingerprint is a 512 bit cryptographic digest truncated to provide
a presentation form that is a multiple of 25 bits. In the default
presentation
format using BASE32 encoding, this gives a fingerprint that is a multiple
of five significant characters.

The design of the V5 fingerprint format anticipates the possibile
introduction of additional presentation formats and the use of the same
fingerprint format with other applications. For example the use of
a 2D barcode presentation format.

To enable this separation the calculation of the V5 digest value is
described
separately from the presentation.

### {12.3.1} V5 Key Format

The key data over which the digest value is calculated is the same as
the V4 key data field with the ommission of the creation timestamp.

<pgp-v5-key> =

a.1) 0x99 (1 octet)

a.2) high-order length octet of (b)-(d) (1 octet)

a.3) low-order length octet of (b)-(d) (1 octet)

b) version number = 5 (1 octet);

c) algorithm (1 octet): 17 = DSA (example);

d) Algorithm-specific fields.

### {12.3.2} V5 Fingerprint Digest Calculation

A V5 fingerprint

The OpenPGP V5 fingerprint value is calculated as follows

Fingerprint = <Version-ID> + H (<Content-ID>  + ‘:’ + H(<data>))

Where:

Version-ID = 0x60

Content-ID = "application/pgp-v5-key"
<<MIME Content-Type string TBS by IANA>>

H(x) = SHA-2-512(x)

<data> = <pgp-v5-key>

The value of Version-ID is intentionally chosen so that
the first character of every V5 fingerprint in the text presentation
format is 'M', a character that is guaranteed not to appear in a V4
or earlier fingerprint format where hexadecimal values were used.
Thus ensuring that V5 fingerprints are not accidentally confused.

The Content-ID is a MIME content type identifier that indicates that
fingerprint value is of data in the pgp-v5-key format specified
above and is intended for use with an OpenPGP application.

If a fingerprint value is to be calculated for a public key value
specified in a different format (e.g. a PKIX certificate or key)
or for a future version of OpenPGP with a different <data> format,
a different Content-ID value MUST be used.

### {12.3.3} V5 Fingerprint Digest Truncation

The Binary Fingerprint Value is truncated to an integer multiple
of 25 bits regardless of the intended output presentation. Applications
MUST not use Fingerprint Values

The output of the hash function is truncated to a sequence of n bits
by first selecting the first n/8 bytes of the output function. If n
is an integer multiple of 8, no additional bits are required and
this is the result. Otherwise the remaining bits are taken from the
most significant bits of the next byte and any unused bits set to 0.

For example, to truncate the byte sequence [a0, b1, c2, d3, e4] to
25 bits. 25/8 = 3 bytes with 1 bit remaining, the first three bytes
of the truncated sequence is [a0, b1, c2] and the final byte is
e4 AND 80 = 80 which we add to the previous result to obtain the
final truncated sequence of [a0, b1, c2, 80]

Fingerprint Digest Values MUST NOT be truncated to less than 100 bits
in length.

### {12.3.3} V5 Fingerprint BASE32 Presentation

Except where prevented by the affordances of the device on which it is
deployed
(e.g. lacks keyboard), applications MUST support generation and use of the
BASE32 Presentation format.

The Truncated digest value is converted to BASE32.

For ease of entry and verification, the five character blocks SHOULD be
separated by a dash '-'. Applications MUST generate and accept V5
fingerprints
that include separators.

Applications SHOULD accept V5 fingerprints with the dash characters
ommitted.

Applications MUST accept V5 fingerprints with lower case characters,
treating
these as equivalent to the corresponding upper case character.

### {12.3.4} V5 Fingerprint Strengthening.

When an application successfully authenticates a key against a truncated
fingerprint, the application MAY record a longer presentation of the
fingerprint
presentation for future use. This is called key strengthening.

Wherever practical, applications SHOULD support the use of key
strengthening.

For most purposes, strengthening to 250 bits offers a sufficient workfactor
for
almost any application while limiting the resulting fingerprint to 59
characters.

---

From: Thijs van Dijk <[email-masked]>
Date: Mon, 12 Sep 2016 15:27:11 +0200

Hi Phillip,

As promised, I'll post my two cents' worth about your proposal.

In your talk last Thursday, you've revealed some details about the larger
design of which this V5 fingerprint proposal is a part. I can see now you
weren't kidding when you described it as "encumbered." Though your talk was
certainly interesting, I'll try and stay on topic and evaluate your
proposal as a self-contained unit rather than as a tiny part of a larger
design.

To wit:

+1 on dropping SHA-1 in favour of SHA-2. This is kind of a no-brainer.
+1 on prepending a version number to the output for futureproofing.
?? on embedding a content-ID field in the final hash input.
+1 on changing the default fingerprint representation from hex to base32.
+1 on changing the definition of the short/long key ID to n bits from the
start rather than from the end, so even the truncated versions will include
the version ID.

On the content-ID, it's unclear from the above draft which problem you're
trying to solve.
If I were to guess, I'd say it would open the door to unification of
OpenPGP and X509 somewhat, but currently it's not obvious how exactly this
fingerprint format would help. Could you elaborate a bit?

--
Thijs van Dijk

6A94 F9A2 DFE5 40E3 067E  C282 2AFE 9EFA 718B 6165

On 6 September 2016 at 06:47, Phillip Hallam-Baker <[email-masked]>
wrote:

> There is a piece of technology that I would very much like to propose
> using but it is very much encumbered :-( So I am going to propose that
> separately and see if we can get the IPR sorted in time to use it. For the
> time being it is not in the draft.
>
> [...]
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 12 Sep 2016 16:32:07 -0400

> proposal as a self-contained unit rather than as a tiny part of a larger

​The only part that I believe is encumbered is the 'work hardening' scheme
that is not currently in the drafts at all. All the rest is pretty well
covered by prior art, albeit that is not an absolute guarantee.​

> If I were to guess, I
> ​​
> 'd say it would open the door to unification of OpenPGP and X509 somewhat,
> but currently it's not obvious how exactly this fingerprint format would
> help. Could you elaborate a bit?
>

​Today there are several formats that are regularly used to describe trust
anchors:

PGP Key format
X.509 / PKIX root cert​
​Certificate Trust List (Microsoft)
SSH Public Key format
SAML
DNSSEC

It would be really nice if we could all use the same format to identify a
root of trust. But that is of course not going to happen unless we can get
all six of the major PKI infrastructures to agree on one approach and that
probably isn't even desirable.

The traditional way to solve this problem is with a URI type scheme:

OpenPGP:mwj3e-wj3id-2kqai-2iwiq

But that uses up a lot of bits and not for any real purpose because all you
have is a fingerprint, you don't know how to interpret those bits.

The idea of putting the content-type into the fingerprint calculation is
that it allows each of the six applications described to make use of one
fingerprint format without risk of someone working out how to cause a
semantic attack by confusing one content type for another. It would of
course be a bad thing if someone could generate an OpenPGP key that turns
out to be a legal X.509v3 certificate.

The other reason for having the content-id in is to allow versioning within
OpenPGP. So for example, lets say that there is a V6 key format but we
don't want to change the digest value. We can change the OpenPGP content
definition format as many times as we like without having to use up any of
those scarce fingerprint version IDs.

---

From: Thijs van Dijk <[email-masked]>
Date: Wed, 14 Sep 2016 15:39:35 +0200

Hi Phillip,

Thanks for clearing that up.

> probably isn't even desirable.

Yes. Out of curiosity, are you currently working with any of the other five
groups to adopt a similar proposal there?
I realise that one has to be the first, and it might as well be us, but I
wouldn't want to be the one to add the n+1'th competing standard. [1]

> those scarce fingerprint version IDs.

Ah, so the version ID pertains to the fingerprint method only and not the
underlying key? That's good to know, and probably a good thing to document
for posterity if we choose to adopt this scheme.
In that case I'll have to lower my previous +1 on prepending a version ID.
I'd have loved to have been able to tell at a glance if a fingerprint
belongs to a v5 or a v6 key even if we keep the hash format the same, but I
see now that that isn't going to be possible without downloading the keys
in full.

Also, one other consequence of prepending a version ID to a key fingerprint
and reading the key ID from the start of the fingerprint rather than the
back is that the Public-Key Encrypted Session Key packet now only has 24
useful bits of key ID, down from 32. I don't think this will be problematic
since the probability of a collision is negligible in normal use [2], and
the opportunities for malice are very limited [3]. Furthermore, it could go
hand in hand with removing the key ID from the PKESK altogether and
defaulting to "anonymous" encryption / trial decryption - of which I would
be in favour. Nonetheless, it's something to keep in mind.

About the text, the last paragraph feels out of place. Did you add it in
anticipation of many backreferences to the term "fingerprint strengthening"
[4], or are you just describing client behaviour? In my understanding, most
operations (verifying a signature, encrypting to someone, etc. [5]) will
require one to have the full public key anyway, not just the fingerprint.
It might therefore be better served by e.g. the following:

```
Client applications MAY import a public key from an external source using
only the short 50-bit key ID as a reference. However, when checking a key's
integrity, applications SHOULD use the full fingerprint for verification.
```

Your thoughts?

-Thijs

[1]: A tale as old as time - https://xkcd.com/927/
[2]: One would need 2^12+ private keys in their keyring in order to be
affected by this (down from 2^16).
[3]: At best, an attacker could force many trial decrypts.
[4]: Or "key strengthening". Are those terms interchangeable?
[5]: In fact, any operation which isn't "select a key from my keyring" or
"download and import a key from a keyserver".

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 17 Sep 2016 17:43:06 -0400

On Wed, Sep 14, 2016 at 9:39 AM, Thijs van Dijk <[email-masked]>
wrote:

> Yes. Out of curiosity, are you currently working with any of the other
> five groups to adopt a similar proposal there?

​That is a really bad cartoon to bring up at a standards body.

The point is that we create another standard and THE OTHER ONES DIE. It
really does happen. Before SAML there were 30+ single sign on schemes in
use. Now everything supports SAML.

But in this case we are already proposing a new OpenPGP fingerprint. So
designing that so that other applications can use the same spec is no
additional cost.​

​The SMIME group has been talking about a fingerprint mode. There is no
guarantee that they will do it. BUT if they do it, they would be doing so
to converge with OpenPGP so it is logical to expect them to do the same
thing.​

> The other reason for having the content-id in is to allow versioning
>> within OpenPGP. So for example, lets say that there is a V6 key format but
>> we don't want to change the digest value. We can change the OpenPGP content

​The current design neither forces the version ID to stay the same nor to
change it. So that isn't a decision we need to take now.

The only thing that forces a change of VersionID is a change in digest
algorithm. Which is probably the thing that would lead to a V6 format
anyway.​

> Also, one other consequence of prepending a version ID to a key
> fingerprint and reading the key ID from the start of the fingerprint rather
> than the back is that the Public-Key Encrypted Session Key packet now only
> has 24 useful bits of key ID, down from 32.
>

​Which bits OpenPGPv5 uses for the session key can be defined separately.
Since the key must be a v5 key, there is no need for a version ID.​

> It might therefore be better served by e.g. the following:

​I added it out of my usual intent to create as wide a prior art trail as
possible in developing a spec.​

```
> integrity, applications SHOULD use the full fingerprint for verification.

​I think we should kill fingerprints with a work factor of less than 2^92 ​
​as unsafe.​ No matter what, they just keep coming back and biting in bad
ways.

---

From: Thijs van Dijk <[email-masked]>
Date: Mon, 19 Sep 2016 12:36:04 +0200

> ​That is a really bad cartoon to bring up at a standards body.

Right. Sorry.

>> In that case I'll have to lower my previous +1 on prepending a version
>> ID. I'd have loved to have been able to tell at a glance if a fingerprint

That's a good point. In fact, I'll hazard a guess and say that that's
likely to be the only event to warrant a key version bump.

> ​as unsafe.​ No matter what, they just keep coming back and biting in bad

Fair enough.
At the other end of the spectrum, do you have any thoughts on what we can
consider the "full" fingerprint? This scheme has an implied maximum length
of 500 bits (the largest multiple of 25 less than 512+8). Apart from
specifying a minimum (100 bits), do you think we should make a
recommendation for what is an appropriate level of assurance? (E.g. 250
bits - 10 groups of 5 base32 characters, similar in size and grouping to V4
fingerprints.)

Apart from this, you'll be glad to know that I've kicked the tyres of this
proposal about all I can, and I like it a lot. Eagerly awaiting someone
else to chime in at this point.

-Thijs

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 19 Sep 2016 09:24:14 -0400

On Mon, Sep 19, 2016 at 6:36 AM, Thijs van Dijk <[email-masked]>
wrote:

> On 17 September 2016 at 23:43, Phillip Hallam-Baker <[email-masked]
> > wrote:
>
>> ​
>>

​Yep, if it wasn't for the fact that we need to get rid of the issue time
and use SHA2 and Base32, maybe we wouldn't ​be doing it now. I hope
OpenPGPv6 won't need to rev the format.

> bits - 10 groups of 5 base32 characters, similar in size and grouping to V4

​I think that for virtually all purposes, a 50+9 character (i.e. 2^242 work
factor) fingerprint is sufficient.​ I don't see more being useful unless
you are really keen on keeping the full 256WF of AES-256.

This is a manageable length for configuration files (looking at you SSH).
So yesterday, I was working on a IoT project to develop a secure means of
controlling the garage door etc. on the house. The config file looks like:

Remote1 = M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-RVXOZ-LGNJW-GW53K-MVTGY-2LKNR
Remote2 = MF3WU-23FNR-VWU4L-XMVTG-Y23RN-J3WK3-DGNNY-XO3DL-MVTGU-3DLOF
...

In this case the remote is currently a Teensy 3.2 device ($12) that has a
32 bit processor and so I am using public key (cos I can). But I might well
want to use a Kerberos type approach and a cheaper CPU (Arduino Nano,
$1.30) instead. I can still use the same approach to authenticate and
authorize the remote.

Note that the configuration file does not need to specify the type of key
because that will be specified when the public portion of the key is
presented. Whether that is a Curve25529 key or a Kerberos ticket, the
message that presents the public key will specify what it is.

I could well see the same approach for SSH authorized_keys files. In fact
my project for this morning/week is to get something like this working:

mesh M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-RVXOZ-LGNJW-GW53K-MVTGY-2LKNR
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAIEA0KJDLOiiXj9XdMxiCT9Kv
​... (5000 chars)..

ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAIEAywWhrwq4FjHt+UuwZcZ
​... (5000 chars)..

​The first lines is the actual trust anchor which is a fingerprint of a
master key of a mesh profile. This is a long term (100 year) key and is not
expected to change. The next two lines are keys that have been fetched from
the mesh and are the latest SSH keys for the two devices the user has
connected to that profile for SSH use.

​The equivalent for OpenPGP would be to manually edit your keyring. In this
case Carol enters the following:

[email-masked]
M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-RVXOZ-LGNJW-GW53K-MVTGY-2LKNR
[email-masked] ​MF3WU-23FNR-VWU4L-XMVTG

When a mail from Bob is received, the mail client updates its copy of the
keyring with the strengthened fingerprint:

[email-masked]
M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-RVXOZ-LGNJW-GW53K-MVTGY-2LKNR
[email-masked] ​MF3WU-23FNR-VWU4L-XMVTG-Y23RN-J3WK3-DGNNY-XO3DL-MVTGU-3DLOF

> else to chime in at this point.

​Thanks for doing so.​

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 19 Sep 2016 12:24:46 -0400

I just found an even more compelling use case for a single fingerprint
format. Let us say that we have the following entry in /etc/passwd (or
something equivalent):

jsmith:M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-RVXOZ-LGNJW-GW53K-MVTGY-2LKNR:1001:1000:Joe
Smith,Room 1007,(234)555-8910,(234)555-0044,email:/home/jsmith:/bin/sh

OK, so we are still working within the clunky /etc/passwd format. But the
point is that we can put the fingerprint of a public key in the password
file. And that could then be used to validate all interactions with that
user:

* Single sign on tokens
* SSH login
* OpenPGP emails to/from system admins.

Now obviously, you probably wouldn't want to put an OpenPGP key in the
password file. But you might want to put the key that is used to sign a
policy statement describing the keys for all the above in that file. And
you might well want to use OpenPGP key format to do that.

On Mon, Sep 19, 2016 at 9:24 AM, Phillip Hallam-Baker <[email-masked]

>> On 17 September 2016 at 23:43, Phillip Hallam-Baker <
>> [email-masked]> wrote:
>>
>>> ​
>>>
>>> ​as unsafe.​ No matter what, they just keep coming back and biting in
>>> bad ways.
>>>
>>
>> Fair enough.
> ​I think that for virtually all purposes, a 50+9 character (i.e. 2^242
> work factor) fingerprint is sufficient.​ I don't see more being useful
> unless you are really keen on keeping the full 256WF of AES-256.
>
> ​The equivalent for OpenPGP would be to manually edit your keyring. In
> this case Carol enters the following:
>
> [email-masked] M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-
> RVXOZ-LGNJW-GW53K-MVTGY-2LKNR
> [email-masked] M5VWK-ZTIO5-WGWZL-GNRVX-OZLGN-
> RVXOZ-LGNJW-GW53K-MVTGY-2LKNR