Re: [openpgp] Followup on fingerprints

[Daniel Kahn Gillmor <[e-mail]>]

On Tue 2015-08-04 04:05:03 -0400, Nicholas Cole wrote:
> I'm really struggling to follow what is going on with this whole
> discussion!  Fingerprints need to be robust enough that creating aritrary
> collisions is not feasible. That has always been central to OpenPGP.

Why must fingerprints be collision-resistant?  We've always said that
fingerprints need to be preimage-resistant -- that is, if i know your
fingerprint, i should not be able to forge a new key that has the same
fingerprint.

But collision-resistance is a different property: if the fingerprint
mechanism is not collision-resistant, then an attacker can create two
keys with the same fingerprint.  Why is this a threat?

> If that creates headaches for user interfaces then we will have to
> find ways to deal with that, but that is a separate discussion.

I agree with this.

> I thought that there were some well established, secure as far as anyone
> knows, hash algorithms. We've many years experience of the problems of
> including or not including various extra bits of information along with the
> key material itself, so doesn't the WG just need to pick one of the
> candidate algorithms and have done with it?

The current OpenPGP fingerprint mechanism (in RFC 4880) uses SHA-1,
which is a 160-bit digest.  SHA-1's collision resistance is believed to
be weaker than the 2^80 work factor that an ideal 160-bit digest should
have.  But that doesn't mean that it is necessarily "broken" for
OpenPGP, if there is no way to exploit a collision atack on fingerprints
in general.

That said, the general cryptographic advice on SHA-1 is "don't use it",
so while sticking with SHA-1 may not be a problem for this specific
case, it is a distraction from the cryptanalysis to have to have this
kind of discussion ("actually, maybe it's ok in this particular use")
whenever it comes up.

Our constraints in the WG here are also bound by UI concerns -- the
fingerprint mechanism is one used by humans, and humans have a limited
capacity to process and handle long high-entropy bitstrings (regardless
of their representation).  So we're really trying to navigate a
multidimensional design space here when we talk about what to do for
fingerprints.

I'll try to start a new thread that identifies those choices more
clearly, and ask people to weigh in on simpler questions about
fingerprints rather than having everything tangled up.

             --dkg