Subject: [openpgp] V5 Fingerprint again

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 1 Mar 2017 12:30:14 -0500

Given the SHA-1 break, Could we return to the V5 fingerprint discussion?

The issue we are seeing the the SHA-1 break is that a LOT of software is
based on the assumption that SHA-1 is unique. And this is causing software
to crash in real world applications.

For example, lets say you are using a GIT like system and some joker has
uploaded different versions of the the colliding PDF into different
instances of the same repository. The two repositories can function quite
happily for quite a while without noticing anything amiss. The problem
comes when we then take SHA-1 hash of the bulk data in both repos:

SHA1(Evil) = SHA1(Evil')

But

SHA1 (Evil + M0 + .... ) != SHA1 (Evil' + M0 + .... )

We really do need to push to get SHA-1 eliminated before the cost of this
attack falls to the point where you only need 50 GPU years to do it....

The proposal I made introduces a context into the fingerprint so that
S/MIME, OpenPGP, etc. can all use the same fingerprint format without
semantic substitution attacks being possible.

##V5 Fingerprint calculation and presentation

A V5 fingerprint value is a sequence of bits that provides a sufficiently
unique identifier for a public key. In addition to generating and accepting
the text string presentation used in earlier versions of OpenPGP
applications
MAY support such additional presentation formats as are found to be useful.

Conforming V5 OpenPGP implementations MUST support the V5 Fingerprint
text presentation format for display and entry of fingerprint values.
Support for all other fingerprint values is optional.

###V5 Fingerprint value calculation

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>

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

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 construction of the data sequence over which the hash value
is calculated follows the construction used in V4 with the omission
of the key creation timestamp field. This ensures that a given set
of public key parameters has exactly one V5 fingerprint value.

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.

###V5 Fingerprint Text Presentation.

The Binary Fingerprint Value is truncated to an integer multiple
of 25 bits regardless of the intended output presentation.

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]

A modified version of Base32 [!RFC4648] encoding is used to present
the fingerprint in text form grouping the output text into groups of
five characters separated by a dash ‘-‘.

# IANA Requirements

Register a new content type for application/pgp-v5-key

---

From: KellerFuchs <[email-masked]>
Date: Wed, 1 Mar 2017 18:08:27 +0000

Hi,

> to crash in real world applications.

Not entirely sure what a standard change can do about that, except from
using a collision-resistant hash function which is expected to stay so
for the forseeable future, and have the ability to switch to a new
fingerprint format.

> semantic substitution attacks being possible.

This seems sensible to me, but I don't see how it would protect against
a future weakness of the hash function.

However, it is useful to stop attacks where a single document would be
valid as a v5 key and as S/MIME (for instance), with both interpretations
having identical fingerprints.

I don't see an immediate attack vector there, but I'm very much not an
expert on polyglots.

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

Why a colon, rather than a NUL byte?
(It's not obvious that Content-Type strings, esp. auxiliary parameters,
 cannot contain colons)

Best,

  Keller

---

From: Thijs van Dijk <[email-masked]>
Date: Wed, 1 Mar 2017 20:41:45 +0100

> to crash in real world applications.

Thanks for reviving this discussion. While as I previously stated your
proposal for the new fingerprint format still looks good to me, I don't
agree that this newest break against SHA-1 is grounds for alarm.

Note, software does not require a hash break to crash, it's perfectly
capable of doing that even if the hash algorithm is sound. I remember a
story of some app crashing because someone reused the key material from the
primary key as a subkey packet, so the subkey and primary would have shared
their fingerprint regardless of the hash used. This is just something apps
will have to deal with no matter what; the only thing that's different from
a few days ago is that bugs like this may just have become a lot easier to
reproduce.

Until I see evidence to the contrary, I'm going to assume the sky is not
falling. Not this week.

However, there certainly are some interesting avenues of investigation in
light of this recent discovery:

1) Should we deprecate SHA1 in signatures? (Or did we already?)
2) How does SKS handle disambiguation? If I submit different keys with
matching fingerprints at different endpoints in the sync network, how will
those keys propagate to the other nodes?
3) Does GnuPG have any way to disambiguate? Do the different automatable
interfaces expose this capability?

I'd say question 1 is the most pressing of the tree, and it's also the one
question we could answer at the standards level. If we manage to make a
decision on that, we're definitly on the right track w.r.t. letting go of
SHA1. (Hint: the answer should be "yes.")

-Thijs

---

From: Thijs van Dijk <[email-masked]>
Date: Wed, 1 Mar 2017 20:42:35 +0100

> (It's not obvious that Content-Type strings, esp. auxiliary parameters,

Well, if it helps: if you look closely, the data is hashed twice, once
without the content ID and a second time with content ID prepended, so
there's no chance of ambiguity, if that's what you were worried about.
Anything from the question of "should there be any separator at all?"
onwards is a matter of personal preference, really.

-Thijs

---

From: Werner Koch <[email-masked]>
Date: Wed, 01 Mar 2017 20:56:49 +0100

> to crash in real world applications.

It is not an issue for us because we are not affected by a collision
attacks and signatures are anyway done for quite some time using SHA-2.

The proposal we made in Berlin was to use use SHA-256 truncated to 25
octets for the new v5 key format.  Unfortunately I have been too busy to
push this forward but it is now on my short list.

The rationale for SHA-256 is that it is faster on small systems and
anyway needed for backward compatibility with existing RSA signatures.

Truncating from 32 to 25 octets allows for easy human fingerprint
verification and also to keep the size of signatures small (note that we
now include the fingerprint in the signatures for easy public key
lookup).

> S/MIME, OpenPGP, etc. can all use the same fingerprint format without

Unfortunately your proposal diverts heavily from the existing standard
and would thus not be an easy change.  Recall that a OpenPGP is used by
small device and thus we need to have an easy migration path towards a
v5 key.  The proposal also adds a textual representation format which
has always been out of scope in OpenPGP.

Salam-Shalom,

   Werner

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

---

From: Werner Koch <[email-masked]>
Date: Wed, 01 Mar 2017 21:15:58 +0100

> 1) Should we deprecate SHA1 in signatures? (Or did we already?)

This would break all existing signatures for no good reason.  Instead a
new v5 key format MUST NOT be used with signatures "weaker" than
SHA-256.

It is up to an implementation to decide what to do with old keys and
signature material.  The question is related to the old question what to
do with an expired or revoked signature key: are all signatures are then
suddenly untrustworthy or is there enough external context which allows
to decide that the signed document is still intact?

Salam-Shalom,

   Werner

---

From: "Robert J. Hansen" <[email-masked]>
Date: Wed, 1 Mar 2017 16:02:05 -0500

> This would break all existing signatures for no good reason.  Instead a
new v5
> key format MUST NOT be used with signatures "weaker" than SHA-256.

Deprecation is not the same as obsoleting.  Deprecation doesn't break
existing signatures; it just says new signatures MUST NOT use SHA-1.

It sounds as if you're agreeing with the deprecation suggestion.  Or am I
badly misunderstanding something?

---

From: Leo Gaspard <[email-masked]>
Date: Thu, 2 Mar 2017 00:27:22 +0100

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

Hoping this hasn't been discussed before, but... is there a reason for
not picking SHA3-512? (or SHAKE256 with 25*8 bits of output if willing
to stay at 25 octets for the fingerprint)

This should push back the next required switch to a v6 key.

---

From: Werner Koch <[email-masked]>
Date: Thu, 02 Mar 2017 08:27:04 +0100

> existing signatures; it just says new signatures MUST NOT use SHA-1.

You are right.  De-facto SHA-1 is already deprecated and I am sure that
is is common understanding in the WG that this will also be written down
in 4880bis.

Shalom-Salam,

   Werner

---

From: Thijs van Dijk <[email-masked]>
Date: Thu, 2 Mar 2017 09:05:00 +0100

> badly misunderstanding something?

Sorry if I wasn't clear before; I meant what Werner said.

-Thijs

---

From: Vincent Breitmoser <[email-masked]>
Date: Thu, 02 Mar 2017 12:41:27 +0100

I think we can go slightly further here for depreciation in implementation logic: if a primary key is self signed with a stronger algorithm, a sha1 signature can be considered a security error. This avoids a downgrade scenario and catches misconfigurations but should have little potential for false positives.

The only scenario I can think of where this heuristic is off, is when the sender doesn't create their key themselves and isn't itself capable of stronger hashes. Not sure if that ever happens? 

 - V

---

From: Thijs van Dijk <[email-masked]>
Date: Thu, 2 Mar 2017 14:13:41 +0100

>
> I think we can go slightly further here for depreciation in implementation
> logic: if a primary key is self signed with a stronger algorithm, a sha1
> signature can be considered a security error. This avoids a downgrade
> scenario and catches misconfigurations but should have little potential for
> false positives.
>

Interesting. How do you envision handling an updated selfsig (e.g. to move
the expiration date forward) with a stronger hash than before?
To me, this seems like the most obvious upgrade path (i.e. a way for users
to force moving to a stronger hash), but when taken literally we've just
retroactively revoked all previous signatures.

> The only scenario I can think of where this heuristic is off, is when the
> sender doesn't create their key themselves and isn't itself capable of
> stronger hashes. Not sure if that ever happens?

One could have a gnuk or yubikey generate the key, and if the user agent
*defaults* to sha1 (regardless of whether or not it can support stronger
hashes) you'll have triggered this scenario.

-Thijs

---

From: Vincent Breitmoser <[email-masked]>
Date: Thu, 2 Mar 2017 14:31:05 +0100

> retroactively revoked all previous signatures.

I don't think this works as an upgrade path really. Both for the reason
you mention, and also because packets can be suppressed. The best we can
probably do here is try and not allow worse than the weakest link.

> hashes) you'll have triggered this scenario.

Seems like a good outcome if this type of misconfiguration is punished.

 - V