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 <derek(_at_)ihtfp(_dot_)com>
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 roam(_at_)ringlet(_dot_)net roam(_at_)FreeBSD(_dot_)org
pp(_at_)storpool(_dot_)com
PGP key: http://people.FreeBSD.org/~roam/roam.key.asc
Key fingerprint 2EE7 A7A5 17FC 124C F115 C354 651E EFB0 2527 DF13
signature.asc
Description: Digital signature
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp