phc-discussions - Re: [PHC] Pleco and Plectron - two provably secure password hashing algorithms

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

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <53FBCCE3.6040804@dei.uc.pt>
Date: Tue, 26 Aug 2014 00:55:15 +0100
From: Samuel Neves <sneves@....uc.pt>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Pleco and Plectron - two provably secure password hashing
 algorithms

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.

[1] https://eprint.iacr.org/2007/205
[2] http://link.springer.com/chapter/10.1007/978-3-540-47942-0_21
[3] http://link.springer.com/chapter/10.1007%2F978-3-642-38980-1_35