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  PHC 
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 26 Aug 2014 00:55:15 +0100
From: Samuel Neves <>
Subject: Re: [PHC] Pleco and Plectron - two provably secure password hashing

On 08/25/2014 04:27 PM, Bo Zhu wrote:
>    - Can use unfactored Mersenne composite numbers rather than RSA moduli
>    in Rabin in order to
>       - speed up internal time-consuming steps
>       - use the password hashing algorithms in cryptocurrencies for
>       proof-of-work/space.

Using unfactored Mersenne numbers, as described in the paper, does not seem to be optimal:

 - Mersenne numbers factor much faster than randomly-selected numbers, using the special number field sieve (e.g.,
2^1039-1 was factored, in 2007, at a much lower cost than RSA-768 [1]); a reasonable rule of thumb is that using such
special numbers requires doubling the modulus bitsize to maintain comparable security.

 - We don't know how many nor how unbalanced the factors of, e.g., 2^1277 - 1 are, since its factorization is unknown.
It may well be that one of the factors is significantly smaller than the others, which makes ECM the prime choice to
factor this modulus. This means that we don't actually know how hard it is to actually factor this number. Note that the
factorizations of Mersenne numbers are mostly a hobby project with a small number of contributors; it's hard to estimate
how much computational power has been put into factoring these numbers. This does not seem to be a good basis for the
security of a scheme.

There are alternative methods to generate (much larger) moduli without a known factorization [2, 3]. Using some seeding
material derived from the user and salt (or some nothing-up-my-sleeve constant if generation is a bottleneck), for
example, one can use a pseudorandom bitstream (e.g., Keccak's output) to generate a number which is very likely to be
hard to factor by either ECM or NFS.


Powered by blists - more mailing lists