692694 - Timing attack on ECDSA

Status: RESOLVED WONTFIX

(NSS :: Libraries, defect, P1)

Description

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

This bug is to track any work that may be necessary to fix the Montgomery multiplication code used by NSS's ECDSA implementation, that may be needed in addition to the work that was done in bug 660394. If no additional work is needed, please explain why and we can WONTFIX this.

+++ This bug was initially created as a clone of Bug #660394 +++

Brumley and Tuveri recently described a timing attack on the implementation of Montgomery multiplication for binary elliptic curve arithmetic in OpenSSL. They describe how to use this vulnerability to recover the long-term ECDSA private key of a TLS server both locally and over a local network (http://eprint.iacr.org/2011/232)

The ECC code in NSS has a similar vulnerability.

The paper above proposes a patch to the ECDSA code in OpenSSL, which has already been adopted by OpenSSL.  However, I believe it may be more appropriate to patch the Montgomery multiplication code, not the ECDSA code, and I have emailed the authors to determine if that's the case.  I will post a patch here when I know more.

Comment 1

[Wan-Teh Chang]

Brian: I am confused by this bug report.  You copied Douglas'
original description in bug 660394 verbatim.  It seems that
the purpose of this bug is to ask Douglas the same question
I asked in bug 660394 comment 9.  Why don't we just have
Douglas answer that question in bug 660394?

Comment 2

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Sorry I wasn't clear. Your understanding is correct; we just need to find out whether we need to change the Montgomery multiplication. I think we should have an open bug on it until we are satisfied that it either isn't necessary or that we have a fix. Otherwise, I will forget about it. But, bug 660394 should be closed because the fix has been checked in.

Comment 3

[Douglas Stebila]

Here's what I asked the paper's authors:

> > First, your proposed fix (which I see has been adopted by OpenSSL already) is in ecs_ossl.c, the ECDSA code.  But the vulnerability itself is in ec2_mult.c in the core EC library, and which would be used by other parts of OpenSSL (e.g., ECDH) and potentially by other applications who might directly called into the EC library.  While placing the fix in ecs_ossl.c will fix the vulnerability you observed in TLS, would it not be better to place this fix right in the ec_GF2m_montgomery_point_multiply function in ec2_mult.c?

Here's their response:

> We discussed on this point while preparing the proposed fix, as both approaches have pros and cons, but in the end we felt that fixing it at the cryptosystem level was a reasonable approach. We considered that the problem was not in the ladder implementation itself but in using the ladder without considering the inherent timing leakage; in addition to that we also weighted the fact that a similar approach was also used in the regular DSA implementation.

One would have to go through and consider all the places where Montgomery ladder EC point multiplication code might be used.  In the context of SSL, EC point multiplication would be used in ECDSA and ECDH cipher suites.  In ephemeral ECDH, everything would be fine, as each ephemeral public key would be used only once, and unlike the ECDSA case is not used in any other computation.  In static ECDH, the timing leak does reveal information about the number of zeros in the high order bits.  Although the static ECDH private key is reused in many key agreements, there's no additional information dependent on the secret key leaked in a modular equation like in the ECDSA case, which I think means that that direct lattice attack does not apply.

So to summarize: I don't think that ECDH -- either static or ephemeral -- is affected by this lattice attack.  Some timing information is leaked, to be sure, but I don't think that the information leaked can be used by this attack.

Comment 4

[Wan-Teh Chang]

Douglas: thank you for the reply.  I marked the bug WONTFIX.

The paper's authors said:
> ... a similar approach was also used in the regular DSA
> implementation.

Do you recommend that we do the same in the regular DSA
implementation in NSS?  See dsa.c, function dsa_SignDigest:
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/freebl/dsa.c&rev=1.21&mark=383,385,387#376

Comment 5

[Douglas Stebila]

I don't think so.  The attack relies on the use of the Montgomery ladder for ECC binary point multiplication.

Comment 6

[Daniel Veditz [:dveditz]]

Isn't this more of a DUPLICATE than a WONTFIX?

Comment 7

[Wan-Teh Chang]

This is an intentional duplicate (or rather, clone) to make sure
a question in the original bug report get answered.