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

Powered by blists - more mailing lists