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

[David Leon Gil]

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