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

bugzilla-daemon@bugzilla.ximian.com bugzilla-daemon@bugzilla.ximian.com
Fri, 3 Dec 2004 01:11:27 -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 pieter@mentalis.org.


--- shadow/70171	2004-12-03 01:11:27.000000000 -0500
+++ shadow/70171.tmp.6421	2004-12-03 01:11:27.000000000 -0500
@@ -0,0 +1,48 @@
+Bug#: 70171
+Product: Mono: Class Libraries
+Version: unspecified
+OS: All
+OS Details: 
+Status: NEW   
+Priority: Wishlist
+Component: Mono.Security
+AssignedTo: mono-bugs@ximian.com                            
+ReportedBy: pieter@mentalis.org               
+QAContact: mono-bugs@ximian.com
+TargetMilestone: ---
+Summary: Montgomery implementation inefficient and insecure
+The current RSAManaged implementation is vulnerable to the timing attacks 
+described in [1, 2], due to the fact that the mono Montgomery 
+implementation isn't a constant-time implementation. Making the 
+Montgomery reductions constant-time would require getting rid of the 
+conditional subtraction at the end of the algorithm, as described in [3, 
+Note that this isn't a theoretical or infeasible attack; I already have a 
+program that performs the timing attack on the mono code. It can guess a 
+128-bit key in only a matter of minutes.
+[1] Timing Attacks on Implementations of Diffe-Hellman, RSA, DSS, and 
+Other Systems,
+Paul C. Kocher,
+[2] A Practical Implementation of the Timing Attack,
+F.-F. Dhem, et al.,
+[3] Montgomery Exponentiation Needs No Final Subtraction,
+Colin D. Walter,
+[4] Precise Bounds for Montgomery Modular Multiplication and Some 
+Potentially Insecure RSA Moduli,
+Colin D. Walter,