Re: [openpgp] Fingerprints and their collisions resistance

[ianG <[e-mail]>]

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.2.3.15 & 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
    fingerprints.

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.

iang



[0] ok, so I may be biased.  This is what I recommend and do:
http://iang.org/papers/ricardian_contract.html