[Top] [All Lists]

[openpgp] Fingerprints and their collisions resistance

2013-01-03 01:18:54
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.
openpgp mailing list