| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Thu, 11 Sep 2014 17:36:51 +0200
From: pornin@...et.org
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Makwa parameter generation
> If you'd use a big modulus, you should be able to optimize it with CRT.
Thinking about it, this has serious implications. Suppose that there is
a big modulus N and that a (smallish) prime factor r of N is known
(even if the complete factorization of N is not known). Then, given
a Makwa output using N, one can compute modulo r to see whether a
given password matches or not -- and since r is prime, the "fast path"
is applicable. This yields an efficient, fast dictionary attack.
Thus, unless post-hashing is used, NONE of the factors of N must be
known by outsiders (post-hashing would save the day here, but it is
incompatible with offline work factor increase). An RSA-UFO would not
be appropriate for Makwa without post-hashing. With post-hashing, this
is still open (but this example demonstrates that it requires some more
thinking).
> Why does montgomery multiplication have larger asymptotic cost
> compared to multiplication modulo a power of two?
Montgomery multiplication is the combination of a "normal
multiplication" (which could be optimized with Karatsuba or FFT)
and a special reduction which works word-by-word, on the least
significant bits. That reduction is quadratic.
To get below quadratic cost, one must use other methods which are
more complex and are not worth the effort for "normal"-sized modulus,
but would be appropriate for a large modulus as we are envisioning
here.
--Thomas Pornin
Powered by blists - more mailing lists