[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)
David Leon Gil
coruus at gmail.com
Wed Jul 23 19:46:00 PDT 2014
> If the system uses RSA, the cheapest approach is usually to vary the public exponent.
Actually done that. (64-bit OpenPGP key collisions, see https://github.com/cooperpair). But fingerprints that include the RSA exponent are a design mistake. (It isn't a part of the 'hard problem'; and > 99% of normal users' keys use the top three exponents, IIRC.)[*]
And thanks for the exceedingly helpful suggestions on EC keys; I may play around with figuring out a more precise cost estimate
Joseph: Attacker's hardware is much more parallel than users' hardware... See, e.g., djb's current microcluster[**]: http://blog.cr.yp.to/20140602-saber.html
(Background on the zero-prefix cost issue: Experimentally verified when I was looking at OpenPGP key collisions. Did a slightly larger plain collision search than is reflected by results in my repo; selecting targets with a zero byte needed to hide memory latency on target architecture. At some point I'll clean up the source...)
[*] Adam Langley has pointed out that protocols which allow arbitrary exponents are subject to DoS attacks. https://www.imperialviolet.org/2012/03/17/rsados.html So perhaps not requiring e fixed was the design mistake.
[**] Why can't cryptographers get funding for real clusters? I know plenty of physicists with as much compute power in their office. And cluster-builders who have wasted more real cluster time running Linpack than, well...alas.
—
Sent using alpine: an Alternatively Licensed Program for Internet News and Email
On Wed, Jul 23, 2014 at 11:56 AM, Robert Ransom<rransom.8774 at gmail.com>, wrote:
On 7/23/14, David Leon Gil <coruus at gmail.com> wrote:
> (I suspect perhaps Joseph was thinking about prime-based-crypto in his
> comment. Or is there a good way of cheaply generating (strong) RSA keys? The
> obvious approach is to just pick two strong primes and then just multiply
> by, say, all primes less than 2^w, where w is the word length, which is a
> factor of N/w cheaper for schoolbook, at least.)
I would reserve the term “prime-based crypto” for
discrete-logarithm-based cryptosystems in prime-field multiplicative
groups. You seem to be talking about factorization-based
cryptosystems.
If the system uses RSA, the cheapest approach is usually to vary the
public exponent. (This search can be performed on untrusted hardware,
e.g. botnet nodes, so it poses a greater threat than one that exposes
the secret key to the device which finds the winning public key. All
reasonable discrete-logarithm public key search procedures can also
use untrusted hardware.)
If the system uses RSA with a fixed public exponent, what you describe
may work if no one tries to actively detect and prevent that attack.
(This search can also be performed on untrusted hardware.)
If the system uses RSA with a fixed public exponent and you must
ensure that no prime factor of the modulus is ever found, the cheapest
approach is to generate a bunch of secret primes and multiply together
each pair of distinct primes. (This search requires trusted
hardware.)
> In general, the speedup of just doing adds or doubles is very roughly the
> bit length of the EC key, right? (I have a factor of 515 for
> Ed448-Goldilocks based on benchmarks, which seems in accord with my
> intuition.)
For Ed448-Goldilocks, I'm not sure. The earlier versions used Mike
Hamburg's 1/sqrt(u) point format (where u is the Montgomery-form x
coordinate), and I don't think that can be batch-scaled.
For ECC with the more common point formats, at the very least, you can
batch the inversions together using ‘Montgomery's trick’ (on a serial
or mostly-serial computer), at least until your working storage
reaches the processor's cache size. On top of that speedup,
short-Weierstrass batched affine addition uses a batched inversion
within the formula, and is considerably faster than projective
addition followed by scaling.
Robert Ransom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140723/740eddba/attachment.html>
More information about the Messaging
mailing list