Re: [Sks-devel] about ECC and collisions

[Daniel Kahn Gillmor]

On 04/05/2011 11:35 AM, Jeff Johnson wrote:
> 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.

This is basically correct, except for its omission of the creation
timestamp.

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

If it's intended to refer to a full v4 fingerprint, I don't think this
is correct.  Constructing a malicious collision requires being able to
do an SHA1 pre-image attack (which i think is beyond the reach of most
everyone today), and does not require destroying pubkey parameters.  For
example, you could select a valid (different) pubkey and permute the
creation timestamp to introduce 32 bits of variability without having a
useless pubkey.

> 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.

There are significantly worse risks of a colliding fingerprint than
"some signature won't verify".  Among them:

 0) you could believe that something was signed by a given entity based
on that entity's fingerprint, but the signature was made by a different
(colliding) key.  (i.e. forgery)

 1) you could encrypt a message to a recipient, but pick the wrong
(colliding) key, allowing some other party to read your encrypted
message (i.e. snooping)

Fortunately, i don't think we're at the point of a full preimage attack
against full SHA-1 being feasible.

> 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.

Now you're talking about collisions of the long key ID, which is a
subset (the bottom 64 bits) of the 160-bit v4 fingerprint.  This is a
significantly easier problem to attack than a full fingerprint collision.

With sub-$3K off-the-shelf hardware and some clever hacking [0], it
looks possible to do several billion SHA1sums per second.  Assuming
generation of novel RSA keys at the rate of dozens per second, and
testing all past creation timestamps against each generated key, a
reasonably-funded organization could keep the pipelines full on a farm
of 100 of these machines and come up with collisions for all possible
64-bit long Key IDs in well under a year, using brute-force alone :(

I'd be happy to be wrong about this; someone please check my math :)

> 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.

Over on address@hidden, David Shaw convincingly demonstrated that
collisions in the v3 keyID space are very much a "real world" threat
already.

And given my calculations above, I think collisions in the v4 keyID
space (64-bits) are a "real world" threat as well.

Without the inclusion of trivially-manipulable creation timestamps in
the fingerprinting, brute-forcing with valid keys requires the creation
of a valid key for each test.  For RSA and DSA at least, i think key
generation would be significantly more expensive than the
nanosecond-per-fingerprint costs on dedicated hardware.  I don't know
about ECC generation.

Regards,

        --dkg

[0] http://blog.zorinaq.com/?e=42

signature.asc
Description: OpenPGP digital signature