[openpgp] Fingerprints and their collisions resistance

[Andrey Jivsov <[e-mail]>]

We exchanged a few emails on gnupg list about this this issue, which I 
think belongs here, the OpenPGP thread.

The issue is that fingerprint calculation method in OpenPGP is hardwired 
to use SHA-1. Some scenarios in which fingerprints are used  depend on 
hash function collision resistance.

It's easy to see the collision resistance requirement of fingerprints by 
making the comparison with document signatures.

Classical collision resistance requirement arises in a situation when 
the owner is free to create two documents that hash to the same hash 
value. The attacker then makes one document available for signing. As a 
result he has acquired an option to use the second document later and 
claim that it was the document that was originally signed.

When viewed as document, the keys fit this pattern. One possible 
exploitation of the hash collision is when the attacker can repudiate 
signatures or repudiate his ability to decrypt messages (because he can 
offer a wrong key with the same fingerprint as a proof supporting his 
inability to perform the private key operation).

Public keys offer a reasonable opportunity to place arbitrary bytes into 
fields that are hashed. For example, DSA P,Q,G, are primes. Every byte 
but the last one of a 2048 bit prime can be fixed, on average, due to 
the high density of primes. It suggests that the task of finding a 
collision with public keys is at least no more difficult than for ASCII 
documents.

Not all scenarios involving fingerprint depend on collision resistance. 
For example, the ability to substitute a designated revoker, which 
fingerprint is stored in a subpacket of a public key, is not assisted by 
compromised collision resistance of SHA-1.

As a remedy to the problem note that the collision resistance only 
arises when the original "document" is not available. Fortunately, keys 
are small, and therefore, the suggested enhancement to the RFC4880 to 
remedy the collision dependence of fingerprints on SHA-1 is to store the 
original key. Continuing the above example with non-repudiation, the 
non-repudiation claims will be made against the application logs (i.e. 
audit trails), thus it will be necessary to include complete keys in 
addition to fingerprints in logs that record protocol exchanges that are 
dependent on public key identification.

This concern will need to be communicated somehow to developers that are 
relying on RFC4880.

An alternative method is outlined next. We introduce a new hardwired 
fingerprint, for example, based on SHA-3. The above-mentioned 
application logs can simply state that "SHA-3 fingerprint is XXX" and 
not bother with storing the whole key (which is unfortunately allowed to 
change, for example, by acquiring new userIDs, making it hard to compare 
the revisions). Any subpacket that currently takes the fingerprint will 
be able to take the new SHA-3 fingerprint as well. Applications will be 
expected to calculate two fingeprints in parallel and perform a match 
with either of them. In addition, we might consider a features packet 
forcing or preferring SHA-3 fingeprint (similar to the MDC feature). 
KeyIDs in messages can also use 8 bytes of the new fingerprint.

Regarding compatibility, note that the fingerprint in the subpackets are 
not affected by collision weakness, so that there is no downgrade 
attack. Fingerprints that are sensitive to collision resistance are 
external features. In addition to mentioned application logs, consider 
the UI implication. When a key is looked up by its fingerprint on a key 
server, the UI can offer to search by SHA-1 or the new style fingerprint 
and this will work with any current key.

I will appreciate your comments on this feature. I don't expect this to 
be a task that needs an urgent resolution. In my mind this is something 
that we agree on, have a simple spec, and then take a few years to 
implement and deploy it in a least disruptive way.

If there is a more elegant/simpler solution? I would like to hear about it.

Thank you.