[pycrypto] getStrongPrime() implementation
don at amberfisharts.com
don at amberfisharts.com
Mon Oct 26 03:21:36 CST 2009
On Sun, 25 Oct 2009 22:52:52 -0400, "Dwayne C. Litzenberger" <dlitz at dlitz.net> wrote:
> - PyCrypto needs to work with *and* without _fastmath, since the GNU MP
> library is an *optional* dependency. We'll need a Python
> for _slowmath.py before I can apply this patch.
Yes, I understand and agree. I think I could do this. I just wanted to wait for some feedback to see if I'm going in the right direction before I invest more time.
> - It looks like you're generating your random numbers using GMP's
> implementation of the Mersenne Twister algorithm, seeded by rand().
Yes that is true
> If I applied the patch as it stands, it would introduce a security hole
> similar to CVE-2008-0166 (the Debian-specific openssl PRNG bug).
OK, I'm not sure I see the problem. Is it that one can guess a timerange in which the program has been started and thus determine a small set of possible seeds which then can be brute-forced? Or is it something else?
> To fix this, we're going to need Python and C implementations of the
> Miller-Rabin probabilistic primality test. These implementations will
> need to accept a callable Python "randfunc" parameter (like
> Crypto.Util.number.getRandomNumber does) so they can get random numbers
> from a cryptographically strong PRNG (i.e. Crypto.Random).
I'm confused. It sounds like this paragraph is in part referring to the next point.
I don't see what the primality testing has to do with the PRNG problem.
The second point (supporting a "randfunc" parameter) however I could implement.
> - PyCrypto's *current* isPrime() function needs improvement. It uses
> mpz_probab_prime_p, which is a *deterministic* variant of Miller-Rabin
> (see http://www.trnicely.net/misc/mpzspsp.html). That's fine for RSA
> generation, but totally insecure if you want to validate negotiated
> Diffie-Hellman parameters, for example. Do you think you could make
> isPrime() take advantage of getStrongPrime()'s primality testing code?
That won't do any good. The primality testing in getStrongPrime is also deterministic. It uses a sieve (the base is the first 10000 primes) and then some rounds (currently 25 as suggested in the paper) of mpz_probab_prime_p().
So I guess what you are suggesting is that we implement our own non-deterministic Rabin-Miller test (again we would need a C and python version). That might not be a bad idea because right now we have some redundancy in that mpz_probab_prime_p also uses a sieve (with a smaller base) before doing the Rabin-Miller tests. We could then avoid that overhead.
Maybe one could then later replace/extend it to a Baillie–PSW primality test which has no pseudo-prime numbers up to at least 10^15.
> - We'll need some unit tests to do some basic sanity checks on the output
> of this new function?
I agree. but what do you have in mind exactly? do you want to do an *exact* primality test?
> How much of the above are you comfortable with? I can probably pick up a
> lot of it if necessary, though in that case it's going to have to wait
> until after PyCrypto 2.1.0 is released.
The python implementation of getStrongPrime() should be straight forward so I can do that.
Also taking the additional randfunc parameter shouldn't be to hard.
I'm not so sure about implementing a Rabin-Miller test. I don't know exactly how it works and would need to make some research first. but from what I read so far it shouldn't be to hard to implement. But you said that for RSA the current deterministic approach is fine so this is for a future version which includes a Diffie-Hellman keyexchange.
Concerning the Unittests. I guess I could moc up some initial tests but I don't know what exactly you have in mind.
further more I would like a comment on whether I got the thing with the public exponent e right.
P.S.: I'm not a national, citizen nor a resident of the USA. I gladly put my current, past and future contributions to PyCrypto into the public domain and I agree to the terms listed under the "PyCrypto Code Submission Requirements - Rev. C". The code I write is not of USA origin.
I think the paper the code was based on might be of USA origin but I don't think that is a legal problem.
I hope that takes care of the legal stuff.
More information about the pycrypto