1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
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>
|
