[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)

[Robert Ransom]

On 7/22/14, Joseph Bonneau <jbonneau at gmail.com> wrote:

> It's never possible to precisely compare brute-force but we should try to
> steer it around basic symmetric-key crypto block operations as a standard.
> On which note, steering back to public key search, the cost of generating a
> new public key when trying to come up with colliding fingerprints is far
> more costly than the hash, so setting 80 bits is probably at least 1000x
> more expensive than doing 2^80 SHA-256 ops.

No -- start each search node with Q = n*P for n secret and random, and
optionally Q' = n'*P for n' random; in each search step, replace Q
with either 2*Q or Q + Q', depending on which operation is faster for
your group.  (In multiplicative groups or curves represented in
Edwards form, doubling is faster; if you're doing a search for a
short-Weierstrass form point, ‘batched affine addition’ is faster (as
the SafeCurves page on ‘rho’ security says).  I don't know which
operation is faster in Montgomery form, since the conversion between
Montgomery and short-Weierstrass consists of adding/subtracting a
constant.)


Robert Ransom