diff options
Diffstat (limited to 'pipermail/pycrypto/2009q4/000146.html')
| -rw-r--r-- | pipermail/pycrypto/2009q4/000146.html | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/pipermail/pycrypto/2009q4/000146.html b/pipermail/pycrypto/2009q4/000146.html new file mode 100644 index 0000000..d1d84ab --- /dev/null +++ b/pipermail/pycrypto/2009q4/000146.html @@ -0,0 +1,195 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> +<HTML> + <HEAD> + <TITLE> [pycrypto] getStrongPrime() implementation + </TITLE> + <LINK REL="Index" HREF="index.html" > + <LINK REL="made" HREF="mailto:pycrypto%40lists.dlitz.net?Subject=%5Bpycrypto%5D%20getStrongPrime%28%29%20implementation&In-Reply-To=52220e37ce0ac221cc93ca0579a55502%40localhost"> + <META NAME="robots" CONTENT="index,nofollow"> + <META http-equiv="Content-Type" content="text/html; charset=us-ascii"> + <LINK REL="Previous" HREF="000144.html"> + <LINK REL="Next" HREF="000148.html"> + </HEAD> + <BODY BGCOLOR="#ffffff"> + <H1>[pycrypto] getStrongPrime() implementation</H1> + <B>Dwayne C. Litzenberger</B> + <A HREF="mailto:pycrypto%40lists.dlitz.net?Subject=%5Bpycrypto%5D%20getStrongPrime%28%29%20implementation&In-Reply-To=52220e37ce0ac221cc93ca0579a55502%40localhost" + TITLE="[pycrypto] getStrongPrime() implementation">dlitz at dlitz.net + </A><BR> + <I>Mon Oct 26 20:56:21 CST 2009</I> + <P><UL> + <LI>Previous message: <A HREF="000144.html">[pycrypto] getStrongPrime() implementation +</A></li> + <LI>Next message: <A HREF="000148.html">[pycrypto] getStrongPrime() implementation +</A></li> + <LI> <B>Messages sorted by:</B> + <a href="date.html#146">[ date ]</a> + <a href="thread.html#146">[ thread ]</a> + <a href="subject.html#146">[ subject ]</a> + <a href="author.html#146">[ author ]</a> + </LI> + </UL> + <HR> +<!--beginarticle--> +<PRE>On Mon, Oct 26, 2009 at 10:21:36AM +0100, <A HREF="http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto">don at amberfisharts.com</A> wrote: +><i>On Sun, 25 Oct 2009 22:52:52 -0400, "Dwayne C. Litzenberger" <<A HREF="http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto">dlitz at dlitz.net</A>> wrote: +</I>>><i> - PyCrypto needs to work with *and* without _fastmath, since the GNU MP +</I>>><i> library is an *optional* dependency. We'll need a Python +</I>>><i> implementation +</I>>><i> for _slowmath.py before I can apply this patch. +</I>><i> +</I>><i>Yes, I understand and agree. I think I could do this. I just wanted to +</I>><i>wait for some feedback to see if I'm going in the right direction before I +</I>><i>invest more time. +</I> +Yes, that makes sense. + +>><i> If I applied the patch as it stands, it would introduce a security +</I>>><i> hole +</I>>><i> similar to CVE-2008-0166 (the Debian-specific openssl PRNG bug). +</I>><i>OK, I'm not sure I see the problem. Is it that one can guess a timerange +</I>><i>in which the program has been started and thus determine a small set of +</I>><i>possible seeds which then can be brute-forced? +</I> +Yes, exactly. + +>><i> To fix this, we're going to need Python and C implementations of the +</I>>><i> Miller-Rabin probabilistic primality test. These implementations will +</I>>><i> need to accept a callable Python "randfunc" parameter (like +</I>>><i> Crypto.Util.number.getRandomNumber does) so they can get random numbers +</I>>><i> from a cryptographically strong PRNG (i.e. Crypto.Random). +</I>><i>I'm confused. It sounds like this paragraph is in part referring to the next point. +</I>><i>I don't see what the primality testing has to do with the PRNG problem. +</I>><i>The second point (supporting a "randfunc" parameter) however I could +</I>><i>implement. +</I> +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. + +>><i> - PyCrypto's *current* isPrime() function needs improvement. It uses +</I>>><i> mpz_probab_prime_p, which is a *deterministic* variant of Miller-Rabin +</I>>><i> (see <A HREF="http://www.trnicely.net/misc/mpzspsp.html">http://www.trnicely.net/misc/mpzspsp.html</A>). That's fine for RSA +</I>>><i> key +</I>>><i> generation, but totally insecure if you want to validate negotiated +</I>>><i> Diffie-Hellman parameters, for example. Do you think you could make +</I>>><i> isPrime() take advantage of getStrongPrime()'s primality testing code? +</I>><i> +</I>><i>That won't do any good. The primality testing in getStrongPrime is also +</I>><i>deterministic. It uses a sieve (the base is the first 10000 primes) and +</I>><i>then some rounds (currently 25 as suggested in the paper) of +</I>><i>mpz_probab_prime_p(). +</I> +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.] + +><i>So I guess what you are suggesting is that we implement our own +</I>><i>non-deterministic Rabin-Miller test (again we would need a C and python +</I>><i>version). That might not be a bad idea because right now we have some +</I>><i>redundancy in that mpz_probab_prime_p also uses a sieve (with a smaller +</I>><i>base) before doing the Rabin-Miller tests. We could then avoid that +</I>><i>overhead. +</I> +Yes, exactly. + +><i>Maybe one could then later replace/extend it to a Baillie–PSW primality +</I>><i>test which has no pseudo-prime numbers up to at least 10^15. +</I> +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? + +>><i> - We'll need some unit tests to do some basic sanity checks on the output +</I>>><i> of this new function? +</I>><i>I agree. but what do you have in mind exactly? do you want to do an +</I>><i>*exact* primality test? +</I> +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). + +>><i> How much of the above are you comfortable with? I can probably pick up a +</I>>><i> lot of it if necessary, though in that case it's going to have to wait +</I>>><i> until after PyCrypto 2.1.0 is released. +</I>><i> +</I>><i>The python implementation of getStrongPrime() should be straight forward +</I>><i>so I can do that. +</I>><i> +</I>><i>Also taking the additional randfunc parameter shouldn't be to hard. +</I>><i>I'm not so sure about implementing a Rabin-Miller test. I don't know +</I>><i>exactly how it works and would need to make some research first. but from +</I>><i>what I read so far it shouldn't be to hard to implement. But you said that +</I>><i>for RSA the current deterministic approach is fine so this is for a future +</I>><i>version which includes a Diffie-Hellman keyexchange. +</I> +Yes, that sounds good. + +><i>Concerning the Unittests. I guess I could moc up some initial tests but I +</I>><i>don't know what exactly you have in mind. +</I> +Again, I'm not looking for a lot here. Just something that exercises all +of the code and does some basic checks. + +><i>further more I would like a comment on whether I got the thing with the +</I>><i>public exponent e right. +</I> +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. + +><i>P.S.: I'm not a national, citizen nor a resident of the USA. I gladly put +</I>><i>my current, past and future contributions to PyCrypto into the public +</I>><i>domain and I agree to the terms listed under the "PyCrypto Code Submission +</I>><i>Requirements - Rev. C". The code I write is not of USA origin. +</I>><i> +</I>><i>I think the paper the code was based on might be of USA origin but I don't +</I>><i>think that is a legal problem. +</I>><i> +</I>><i>I hope that takes care of the legal stuff. +</I> +Thanks for mentioning that. It helps me keep things straight. + +Cheers, +- Dwayne + +-- +Dwayne C. Litzenberger <<A HREF="http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto">dlitz at dlitz.net</A>> + 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 +</PRE> + + +<!--endarticle--> + <HR> + <P><UL> + <!--threads--> + <LI>Previous message: <A HREF="000144.html">[pycrypto] getStrongPrime() implementation +</A></li> + <LI>Next message: <A HREF="000148.html">[pycrypto] getStrongPrime() implementation +</A></li> + <LI> <B>Messages sorted by:</B> + <a href="date.html#146">[ date ]</a> + <a href="thread.html#146">[ thread ]</a> + <a href="subject.html#146">[ subject ]</a> + <a href="author.html#146">[ author ]</a> + </LI> + </UL> + +<hr> +<a href="http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto">More information about the pycrypto +mailing list</a><br> +</body></html> |