Re: [openpgp] Followup on fingerprints

[Phillip Hallam-Baker <[e-mail]>]

On Mon, Aug 3, 2015 at 1:20 PM, Derek Atkins <[e-mail]> 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.


Your original assertion was broken. I don't think it very likely that
someone is going to spend more than a machine year to generate a vanity key
unless they can get someone else to pay for the time.

A hundred machine years for creating a key collision attack is completely
viable.

Also when we are talking about PGP Key fingerprint, the fingerprint is over
the key binding and not just the key and so it is malleable.

I can well imagine someone making use of all that Bitcoin hardware for some
mischief. Hence a reason to go for SHA-2-512.


Again, this is only a security consideration that has to be noted.