Date: Fri, 05 Sep 2014 17:06:29 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.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 (x|n) = -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 (x|n) = -1, x cannot be equal to -y either. The consequence
> is that y-x is a multiple of p and not q, or of q and not p. A
> simple GCD computation between y-x 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 2048-bit RSA-like 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
> (p-1)/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 "p-1 method",
> which works for integers N = pq where p-1 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 "p-1 method" was not
> applicable.

I actually did mean that (p-1)/2 was prime when I said "safe" prime.

> However, this was overkill. The probability that p-1 was
> sufficiently smooth for a random prime p is extremely small, far
> into the "utterly negligible" area. For a 1000-bit random integer
> x, the average size of the largest prime factor of x is about 624
> bits (this is linked to the Golomb-Dickman constant). 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).
> 
> 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
> week-end), 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 bit-strength 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