Re: [Sks-devel] about ECC and collisions

[Jeff Johnson]

On Apr 5, 2011, at 12:46 PM, Daniel Kahn Gillmor wrote:

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

I used "conventionally defined plaintext" as a generic sunstitute
for the details of how a fingerprint is attached to pubkey parameters.

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

I've made no claim about threat models or have I said that collisions
aren't a risk factor. I've instead described as simply as possible
to answer a specific question regarding fingerprint collisions on ECC 
parameters.

I will leave OpenPGP design issues to others, my "trust" model is
not outrageously paranoid.


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

Yes. Meanwhile there's lots of phear around based on attaks on SHA1.
I'm quite sure that there will be changes to existing OpenPGP 2440/4880
with years of time to change as more sophisticated attacks on SHA1 are
found.

>> 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 you can estimate the resources/time cost of an attack on
the fingerprint, there's really nothing of value in the pubkey
parameters. Real worl threats will NOT be coming through fingerprint
collisions, but rather aagainst the private key protection, or
by triggering a collision on the hash of the plaintext that is
signed.

These are many different threat models more important than collisions on 
fingerprints
of ECC pubkeys imho, and that was the starting point of this thread.

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

I did specify V4, not V3. Yes there's a reason for using V4 signatures
and pubkeys,

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

Maybe, maybe not, we will see, won't we?

I'm quite sure that the attacks on OpenPGP are analyzed by people (like you ;-)
who are more sophisticated (and more paranoid) than I am.

I don't trust computers whatsoever, and crypto math and design is for the
few who do that work professionally. I am but a a mere user,
albeit technically sophisticated.


73 de Jeff