Re: [Sks-devel] about ECC and collisions

[Jeff Johnson]

On Apr 5, 2011, at 11:07 AM, Daniel Kahn Gillmor wrote:

> On 04/05/2011 09:33 AM, Jean-Jacques Brucker wrote:
>> I didn't know that fingerprint was calculated with a timestamp. Do you have 
>> any idea of the reason(s) to do that ?
> 
> You should read RFC 4880 (or just skim it and read the parts that most
> interest you):
> 
>  https://tools.ietf.org/html/rfc4880
> 
> and this kind of discussion is probably best had on the ietf openpgp WG
> list, in which anyone can participate:
> 
>  http://www.imc.org/ietf-openpgp/
> 
> My impression from thinking about the problem is that the creation
> timestamp is actually a critical piece of information about a key. For
> example, it constrains the range of possible valid timestamps for
> signatures or certifications made by the key (you can't make a
> certification before your key ever existed).  Embedding such a
> constraint in the fingerprint makes it tightly-bound to the key.  (note:
> i'm not saying this is a great argument, or that i think it's a good
> idea; i'm undecided myself about the utility of putting the creation
> timestamp in the fingerprint)
> 
> Some suggestions within the working group around possible new
> fingerprint models have proposed fingerprinting only the public key
> material itself, and not including the creation timestamp, so i think
> there is room for discussion there.
> 

The current V4 scheme (from memory, see RFC 4880 for specifics) to assign
a fingerprint to a pubkey (including all of RSA/DSA/ECC) involves running
a SHA1 digest across conventionally defined plaintext that involves the 
alogrithm
parameters and using the SHA1 as a fingerprint for the pubkey.

One can construct a "malicious" collision only by destroying the algorithm 
parameters
and rendering a pubkey useless.

Which leaves accidental fingerprint collisions as the main risk factor,
where the wrong pubkey will be retrieved and some signature that
references a pubkey through a fingerprint won't verify.

The collision probability will be related to the (64bit iirc) truncated SHA1 
typically used
for pubkey algorithms (like ECC/RSA/DSA), i.e. vanishingly small probability, 
and with
mostly harmless DoS related consequences if an accidental collision is 
encountered.

Whether the conventionally defined plaintext includes creation time as a nonce
(or not) is mostly a theoretical design issue, not a "real world" threat of
any consequence. Sure design/theory matters, that isn't what I'm saying here.

JMHO and a statement of my "trust" decisions: YMMV.

73 de Jeff