[Mono-bugs] [Bug 70171][Wis] New - 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 pieter@mentalis.org.

http://bugzilla.ximian.com/show_bug.cgi?id=70171

--- 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   
+Resolution: 
+Severity: 
+Priority: Wishlist
+Component: Mono.Security
+AssignedTo: mono-bugs@ximian.com                            
+ReportedBy: pieter@mentalis.org               
+QAContact: mono-bugs@ximian.com
+TargetMilestone: ---
+URL: 
+Cc: 
+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, 
+4].
+
+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,
+http://www.cryptography.com/resources/whitepapers/TimingAttacks.pdf
+
+[2] A Practical Implementation of the Timing Attack,
+F.-F. Dhem, et al.,
+http://users.belgacom.net/dhem/papers/CG1998_1.pdf
+
+[3] Montgomery Exponentiation Needs No Final Subtraction,
+Colin D. Walter,
+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