[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 12:21:19.000000000 -0500
+++ shadow/70171.tmp.25747	2004-12-06 09:24:08.000000000 -0500
@@ -128,6 +128,57 @@
 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.
+
+------- Additional Comments From sebastien@ximian.com  2004-12-06 09:24 -------
+I read (or re-read some) thru references [1] to [4]. I've worked years
+with smartcards so I well aware of the problem - but never much
+considered it a major problem on personal computers (at least wrt
+Montgomery) in large parts due to the fact that much easier attacks
+exists on PC and because the attack scenarios can be quite different. 
+
+The references didn't help much to convince me otherwise, e.g.
+RSAManaged generally use the Chinese Remainder Theorem (CRT) which
+papers (talking about CRT) seems to think it safe from timing. But you
+said you had results and I'm interested in the subject so I continued
+looking...
+
+And found out the document, "Remote Timing Attacks are Practical" [5],
+which is both more recent (2003) and it's attacks are far more
+realistic (i.e. real-life) and related to Mono than the previous
+documents. Indeed very interesting...
+
+[5] Remote Timing Attacks are Practical
+http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf
+
+So I'll assume that even a noisy target, like a PC, on a noisy
+environment, like a network, is not safe from this attack with
+*enough* samples.
+
+However modifying BigInteger (as suggested) to avoid timing attacks
+doesn't seems a good idea to me. The two main reasons are:
+
+- it's not a math problem it's a security problem. E.g. someone
+re-using BigInteger for other purpose wouldn't require (nor want) the
+compromises.
+
+- making the algorithms (not just modpow or montgomery as other timing
+issues could exists) executing constant-time is a *very hard* problem.
+It's doable on a small CPU like "some" smartcards but very difficult
+on PC. Paper [5] talks about how the different architectures and
+compiler optimizations affects the timing results. Running in
+constant-time on multiple JITs (e.g. Mono and MS), with different
+optimizations and different architecture would be a BIG problem (and a
+testing nightmare).
+
+So right now I'm inclined to fix problem #1 (fixing the problem) using
+the key blinding technique, as suggested in [5], which means that
+RSAManaged (and DHManaged) will need to be fixed (and not BigInteger).
+
+As for problem #2 (finding out how it affects Mono) I still hope to
+get more informations about your tests (i.e. how they were conducted,
+number of samples required, retrieval time versus key length, ...) and
+how key blinding would affect the results.
+