[Top] [All Lists]

Re: [openpgp] Fingerprints and their collisions resistance

2013-01-05 13:38:58
On 4/01/13 03:01 AM, Andrey Jivsov wrote:
On 01/03/2013 03:08 PM, Daniel Kahn Gillmor wrote:
As i mentioned on the discussion on the GnuPG discussion list, i remain
unconvinced that OpenPGP fingerprints need to be collision-resistant.
They certainly need to be able to resist preimage attacks, but i haven't
seen any convincing attacks that make me think collision resistance is
an issue.
If anyone disagrees with this analysis, i would be interested in hearing
how failed collision-resistance of the fingerprint mechanism could lead
to practical attacks in OpenPGP.

I have this Keccak in OpenPGP darft written, waiting to for the NIST to

Key fingerprints can be designed to be cryptographically strong, so that
it is infeasible to forge them / find collisions for anybody. The
overall system is stronger if we can rely on this stronger assertion.

My understanding is that Key Fingerprints are purposed for humans. RFC4880 says:

   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.

Although see & 5.5.2 for interesting comments. Let's ask for consensus on this point:

  Are fingerprints cryptographically secure?

  Or are they convenient human introduction handles?

OpenPGP is a format on the wire. I need to show only one vulnerable
hypothetical OpenPGP system to prove that Daniel is wrong.

Fingerprints aren't really for the wire, and if you use them for the wire, you're exercising your right to develop your own security model and threat model. For my money - don't do that.

Let's say I have a server that manages a domain of user, each have their
own key, one at a time.

Note, a key can have multiple fingerprints.

Users can update their keys. They cannot remove
keys (other than updating them). The server logs protocol actions and it
uses key fingerprints to log changed to keys. The server decide to log
the whole key on the key material change event, which it identifies by
the change in the key fingerprint. Seems like a reasonable and secure
system at first sight.

I am a malicious member of that domain. I create two keys with the same
fingerprint. Now I can repudiate my document signatures. Document
signatures will refer to either of my keys with the same 8 byte KeyID.
Server logs will have the same 160 bit fingerprints. I can replace my
first key on the server with another and no logs will tell that I have
updated the key. This will invalidate documents signed with my first key.

There is an easy remedy to this problem, but it will essentially mean
that we don't trust the key fingerprint and diligently log whole keys.

Right. That's what you should do anyway. If you are to rely on the digsig for any length of time, you should escrow the full public key.

This means that we moved away from relying on collision resistance of
the fingerprint.

OpenPGP is primarily a wire format, a communication tool, and has steered clear of how you might store the data, leaving this up to the designer. The fingerprint is clearly a useful index, but is not really purposed to be a cryptographically secure index - that's more left for the designer. E.g., you can have the same key with 2 fingerprints:

   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

In more particularity, a document signing system should store the keys in or near the document [0]. Otherwise you have the problem of lost keys, being a serious risk for any long-lived system. And, if you've got the keys, you don't care what indexing technique you use.


[0] ok, so I may be biased.  This is what I recommend and do:
openpgp mailing list