[Mono-bugs] [Bug 70171][Wis] Changed - Montgomery implementation inefficient and insecure
bugzilla-daemon@bugzilla.ximian.com
bugzilla-daemon@bugzilla.ximian.com
Fri, 3 Dec 2004 12:21:19 -0500 (EST)
Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.
Changed by sebastien@ximian.com.
http://bugzilla.ximian.com/show_bug.cgi?id=70171
--- shadow/70171 2004-12-03 09:04:16.000000000 -0500
+++ shadow/70171.tmp.18072 2004-12-03 12:21:19.000000000 -0500
@@ -1,12 +1,12 @@
Bug#: 70171
Product: Mono: Class Libraries
Version: unspecified
OS: All
OS Details:
-Status: NEW
+Status: NEEDINFO
Resolution:
Severity: Unknown
Priority: Wishlist
Component: Mono.Security
AssignedTo: sebastien@ximian.com
ReportedBy: pieter@mentalis.org
@@ -43,6 +43,91 @@
http://www.comodogroup.com/research/crypto/CDW_ELL_99.ps
[4] Precise Bounds for Montgomery Modular Multiplication and Some
Potentially Insecure RSA Moduli,
Colin D. Walter,
http://www.springerlink.com/index/3P1QW48B1VU84GYA.pdf
+
+------- Additional Comments From sebastien@ximian.com 2004-12-03 12:21 -------
+There are 2 important points here:
+
+1 - Fixing the problem
+
+* Thanks for the links. I will compare them with Mono implementation
+of BigInteger. I know the implementation could be more efficient (not
+just for the Montgomery implementation) and probably more secure.
+
+BTW paper [4] is also freely available from
+http://www.comodogroup.com/research/crypto/CDW_RSA_2002_Monty.ps
+
+
+2 - Finding out how it affects Mono
+
+* This part is harder as I don't have enough informations with the bug
+report (it's the reason I changed the bug status to NEEDINFO).
+
+- Is this a 128 bits key pair ? or
+- Are you able to find the 128 bits secret key of a key exchange ?
+- If so (secret) what was the size of the public key involved ?
+
+If it's a 128 bits key pair, then I can factor such a key in less than
+a minute (like 5 seconds) on my computer (P4 @ 2.8 Hgz).
+
+$ time ./factor 122014424615055279531969978322750663391
+first trying brute force division by small primes
+now trying 1000 iterations of brent's method
+now trying william's (p+1) method
+phase 1 - trying all primes less than 10000
+phase 2 - trying last prime less than 1000000
+now trying pollard's (p-1) method
+phase 1 - trying all primes less than 100000
+phase 2 - trying last prime less than 5000000
+now trying lenstra's method using 10 curves
+curve 1 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 2 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 3 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 4 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 5 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 6 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 7 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 8 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 9 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+curve 10 phase 1 - trying all primes less than 20000
+ phase 2 - trying last prime less than 2000000
+finally - the multiple polynomial quadratic sieve - with large prime (*)
+using multiplier k= 11 and 564 small primes as factor base
+working...* 547
+trying...
+working... 547
+trying...
+working...* 551
+trying...
+working... 551
+trying...
+working... 551
+trying...
+working... 551
+trying...
+PRIME FACTOR 12548059430501651957
+PRIME FACTOR 9723768467215279363
+
+real 0m5.103s
+user 0m0.015s
+sys 0m0.000s
+
+However I'm curious about how your program scales with bigger key size
+(i.e. at what point, if any, it is able to guess faster than I can
+factor). Plotting a graph with different key size would be useful.
+Let's start small, say 128, 130, 132, ... up to one hour computation,
+as I don't think we'll get very high in bits count very soon ;-).
+
+There are also other requirements for a timing attack (e.g. having
+several measurements) that aren't required when factoring.