[Mono-bugs] [Bug 70171][Wis] Changed - Montgomery implementation inefficient and insecure

[bugzilla-daemon@bugzilla.ximian.com]

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.