Re: [openpgp] Followup on fingerprints

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

On Mon, August 3, 2015 12:59 pm, Gregory Maxwell wrote:
> On Mon, Aug 3, 2015 at 3:08 PM, Derek Atkins <[e-mail]> wrote:
>> Remember, the fingerprint is over the public key, so you still have to
>> actually perform the ECC g^x operation for each trial.
>
> Take care to not confuse what you would do with what an attacker _must_
> do.
>
> For each new key to generate the attacker can perform only a single
> addition of G or a doubling (whichever is faster for the curve in
> question), then a conversion to affine (which is nearly free--
> marginally, ~one field multiply-- if done in a batch).
>
> E.g. You compute,
> P_0 = xG
> P_1 = P_0 + G  (x_1 = x_0 + 1)
> P_2 = P_1 + G  (x_2 = x_1 + 1)
> ...
>
> There are even faster techniques available for some curves.
>
> If software for this doesn't run in the rough ballpark of a million
> per second on a current gen laptop/desktop or 10 million/sec on a GPU
> even on a fairly generic curve, it's probably completely naieve.

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.

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