phc-discussions - Re: [PHC] A review per day

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: <540A2601.1030303@dei.uc.pt>
Date: Fri, 05 Sep 2014 22:07:13 +0100
From: Samuel Neves <sneves@....uc.pt>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - Makwa

On 05-09-2014 21:37, Thomas Pornin wrote:
> I am too lazy and rushed right now to
> compute the probability that, by generating random 1000-bit integers,
> you hit a value whose largest prime factor is less than 2^80, but it
> is negligible (less than 1 in 2^200).

Approximating Dickman's rho as u^-u, the probability that a randomly-selected 1000-bit integer is 2^80-smooth is
rho(log(2^1000)/log(2^80)), or roughly 2^-45.

That said, I agree that worrying about safe primes in unwarranted. By all measures, cycling and p+-1 attacks are a
terrible factorization method for general numbers; any serious attacker will be better served by trying ECM or the
number field sieve.

I recommend Rivest and Silverman's 1999 paper on this precise subject, specifically Section 9:
http://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf