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] [day] [month] [year] [list]

Date: Mon, 25 Aug 2014 20:13:41 -0400
From: Bo Zhu <bo.zhu@...terloo.ca>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Pleco and Plectron - two provably secure password hashing algorithms

Hi Samuel,

Thank you for pointing out these alternative methods!
They are very interesting and useful. I didn't know them before.

Best,
Bo


On Mon, Aug 25, 2014 at 7:55 PM, Samuel Neves <sneves@....uc.pt> wrote:

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

Content of type "text/html" skipped