Re: [openpgp] Fingerprints and their collisions resistance

[Andrey Jivsov <[e-mail]>]

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.

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

Let's say I have a server that manages a domain of user, each have their 
own key, one at a time. 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. 
This means that we moved away from relying on collision resistance of 
the fingerprint.