Re: [openpgp] Followup on fingerprints

["Derek Atkins" <[e-mail]>]

On Mon, August 3, 2015 1:32 pm, Peter Pentchev wrote:

>> Luckily my computations (which you unfortunately cut out) were based on
>> 30
>> million attempts per second, so my results (the attack taking over a
>> year)
>> is still correct!  Indeed, your numbers are still 3x slower than my
>> computation estimates.
>
> Um, I believe that the point is that Mallory doesn't *need* to brute-force
> anything to create two keys with almost-identical hashes.  ICBW, but I
> think
> that the idea is that Mallory, in the process of creating the first key,
> is in possession of some intermediate information that enables him to
> create
> a related key much cheaper, with a single run.

They do still need to brute-force -- they still need to find a hash
collision.  Whether they do this randomly or forcing it still requires on
the order of 2^50 operations (assuming they want to match 100 bits of a
hash).

My previous statements assumed the hashing was free, but we all know
that's not true.  On my laptop I can perform on the order of 3 to 5
million SHA operations per second (3.4 SHA256, and 4.6 SHA1) on 16 bytes
of data.  So we're still well within the 30 million trials per second. 
But how about this, I'll be nice and give you yet another order of
magnitude to 300 million attempts per second.  That STILL limits you to
~46 days to find a 100-bit collision.  But the data being hashed is more
than 16 bytes so I still think it's going to be closer to 30 vs 300
million attempts per second.

Thanks,

>
> G'luck,
> Peter

-derek

> --
> Peter Pentchev  [e-mail] [e-mail] [e-mail]
> PGP key:        http://people.FreeBSD.org/~roam/roam.key.asc
> Key fingerprint 2EE7 A7A5 17FC 124C F115  C354 651E EFB0 2527 DF13
> _______________________________________________
> openpgp mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/openpgp
>


-- 
       Derek Atkins                 617-623-3745
       [e-mail]             www.ihtfp.com
       Computer and Internet Security Consultant