lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening linuxcveannounce PHC  
Open Source and information security mailing list archives
 

Date: Fri, 05 Sep 2014 17:06:29 0400 From: Bill Cox <waywardgeek@...hershed.org> To: discussions@...swordhashing.net Subject: Re: [PHC] A review per day  Makwa BEGIN PGP SIGNED MESSAGE Hash: SHA1 On 09/05/2014 04:37 PM, Thomas Pornin wrote: > On Fri, Sep 05, 2014 at 01:40:45PM 0400, Bill Cox wrote: >> The concern I am working through right now is trying to convince >> myself that Makwa will have good long cycle lengths when squaring >> over and over, with effectively zero chance of getting a weak >> cycle where finding the square root is many times easier. > > If you can find small cycles then you can factor the modulus. > > Indeed, choose a random x modulo N. Probability that x is a > quadratic residue modulo p is about 1/2. Probability that x is a > quadratic residue modulo q is also about 1/2. You can compute the > Jacobi symbol of x relatively to n, which will be 1 or 1; the > computation is easy (see the Wikipedia page: > http://en.wikipedia.org/wiki/Jacobi_symbol ). We are here > interested in values x such that the Jacobi symbol (xn) = 1: > these are exactly the values which are a square modulo p but not > modulo q, or are a square modulo q but not modulo p. Probability of > a random x to be such a value is about 1/2, so finding one is > easy. > > Suppose that such a x generates a small cycle. You can them > compute x^2, x^4, x^8... and so on, until you complete the cycle: > you end up with a value y which is such that y^2 = x^2 modulo N. > However, y is a quadratic residue, but x is not, so y != x; and > since (xn) = 1, x cannot be equal to y either. The consequence > is that yx is a multiple of p and not q, or of q and not p. A > simple GCD computation between yx and N reveals p or q, and N is > factored. > > Therefore, if the probability of hitting a small cycle is not > negligible, then you have an efficient factoring algorithm. Since > integer factorization is hard for 2048bit RSAlike moduli, small > cycles will not be reachable in practice, even if you try hard. > > > > The notion of "safe prime" has been coined at various times, not > always for the same values. Usually, a prime p is called "safe" if > (p1)/2 is also prime (note that it is not exactly the same meaning > as the one you use). That specific notion of safe prime was about > resistance to a factorization algorithm known as the "p1 method", > which works for integers N = pq where p1 is the product of only > small integers (this is called a "smooth integer"); in that sense, > selecting your prime factors (for RSA key pair generation) to be > "safe" (in that sense) guaranteed that the "p1 method" was not > applicable. I actually did mean that (p1)/2 was prime when I said "safe" prime. > However, this was overkill. The probability that p1 was > sufficiently smooth for a random prime p is extremely small, far > into the "utterly negligible" area. For a 1000bit random integer > x, the average size of the largest prime factor of x is about 624 > bits (this is linked to the GolombDickman constant). I am too lazy > and rushed right now to compute the probability that, by generating > random 1000bit integers, you hit a value whose largest prime > factor is less than 2^80, but it is negligible (less than 1 in > 2^200). > > In the case of short cycles for Makwa, similar results hold. I > don't have time right now to quantify it (I'll try later this > weekend), but probability of finding a small cycle will be > negligible (which explains why it does not work in practice as a > factorization algorithm). > > > Yet another way to see it is the following: if you hit a short > cycle, short enough to be walked extensively, then you are breaking > Rabin encryption. > > > > To sum up, trying to generate p and q factors with special > properties ot ensure a lack of short cycles is mostly wasted CPU, > since purely random primes will already ensure it with overwhelming > probability. You _can_ apply extra checks or insist on "safe prime" > for some notion of "safe", but the benefits will be only > psychological, not cryptographic: this won't improve security in > any tangible way, but it may help you sleep at night. > > Since I personally don't have qualms with regards to short cycles, > I did not enforced any such "safe primes" in the modulus generation > tool provided with the Makwa reference code. > > > Thomas Pornin Thanks for that explanation! I am nearly convinced that we can increase the bitstrength against a cycle measuring attack to just a few bits short of n's length. However, given that attacking factoring n with the simplest possible attack has strength sqrt(n), there's no point. Knowing that the cycle length being less than 2^1024 happens with negligible probability is enough. However, I did have a *lot* of fun with that analysis :) Bill BEGIN PGP SIGNATURE Version: GnuPG v1 iQIcBAEBAgAGBQJUCiXRAAoJEAcQZQdOpZUZ2nkQAKPk0u/ap/0wLM3CR9Qcm7H3 OWOebxrxqYNY4TsDwQ2Ku9Ra2tEZGPCQLJxAAxnn11w0wSGWul5+428cl5xWgBgD y5jx7LeCG8iDYzH16DrGY/ug7z2mQPFYgddl6BbQgW7jqDH3shLTd5mtNlBu1NTC WE0rrnkGn6kk52GiQt5xNq6DvCTEFfO0lhzEuINKhbdGAFPnXshpmrlxtnobYCqa qRzOJKcYk9kciwAXJpTRdny3wYPqDgQa4jcctPPh+db1d9kTIHt9LF7lGdA4cNsu S7KU4UZB5S5E3SNnFA3d1DrQ6vWU4fWv2EL4ef+1jjvkqV96AESHNqspKvtMcFgf mg4EA3LSN/FgUmI/zjI+Ut5o8NMRU8aZbb7XSKPGO20XkkOgpP+pAxhDQ1obz586 +J5aloxtkvnhn2kEPFZxpdoSIsUYX6KaVzwYJDYoiNQkJk2og2mf6UDoU5IMoe+x QWDrPUX4Kzx0QwsynAt13DWtY7KD0md3h0l8dGUQ8hf9TxTdpzJLH1tT0JzS0CmA Et9uPQ/WEgQNA17bdKL/eRaoLbnQB4vwgXp8duY4c9FsMn/gGmdhrzouPAcJd+To tt+CxU/CnMjInrVBHrufRfh5gblBY0IrXl1+kG2CuEQwWCyQQhAG8KJjckWrJYIp 8bnbi41UZ5bERqEcdUe4 =cl6r END PGP SIGNATURE
Powered by blists  more mailing lists