[pycrypto] getStrongPrime() implementation

[Dwayne C. Litzenberger]

On Mon, Oct 26, 2009 at 10:21:36AM +0100, don at amberfisharts.com wrote:
>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
>> implementation
>>    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. 

Yes, that makes sense.

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

Yes, exactly.

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

Ok, ignore what I wrote there.  I can't think of a good way of explaining 
what I mean right now.  There are a few concepts that are intertwined.

>> - 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
>> key
>>    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(). 

Yes, I agree.  This would only be useful once getStrongPrime() is modified 
to use a proper random number source.

[I should correct the terminology I used in my previous email: 
mpz_probab_prime_p doesn't implement a deterministic test (as I suggested); 
it implements the probabilistic Rabin-Miller test deterministically.  As a 
result, the theoretical guarantee normally provided by the Rabin-Miller 
probabilistic test (at most a 25% false positive probability per iteration) 
is void.]

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

Yes, exactly.

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

Yes.  Of course, for crypto, we really only need to worry about primes 
larger than 2^2047 (10^616).   Does Baillie-PSW offer a theoretical maximum 
probability of error like Rabin-Miller does?

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

No. :)

Basically, I just want to test for obvious coding errors.  For example, we 
could check for "primes" that are even, or wrong sized primes (e.g if you 
ask for a 2048-bit prime and get a 2047-bit number instead).  We could also 
test a new isPrime() by including some pseudoprimes that currently fool 
isPrime (Thomas R. Nicely has generated some).

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

Yes, that sounds good.

>Concerning the Unittests. I guess I could moc up some initial tests but I 
>don't know what exactly you have in mind.

Again, I'm not looking for a lot here.  Just something that exercises all 
of the code and does some basic checks.

>further more I would like a comment on whether I got the thing with the 
>public exponent e right.

That's the part I don't understand, and why I asked for help with this in 
the first place.  I unfortunately don't know very much about the math 
behind RSA. :-/

I'll look at it again this weekend if I have time and I remember.

Also, thanks for posting your earlier test results.

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

Thanks for mentioning that.  It helps me keep things straight.

Cheers,
- Dwayne

-- 
Dwayne C. Litzenberger <dlitz at dlitz.net>
  Key-signing key   - 19E1 1FE8 B3CF F273 ED17  4A24 928C EC13 39C2 5CF7
  Annual key (2009) - C805 1746 397B 0202 2758  2821 58E0 894B 81D2 582E