Re: [openpgp] Followup on fingerprints

[Peter Pentchev <[e-mail]>]

On Mon, Aug 03, 2015 at 01:20:08PM -0400, Derek Atkins wrote:
> 
> 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.

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.

G'luck,
Peter

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