660394 - Timing attack on ECDSA (especially over binary curves)

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Douglas Stebila]

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

[Douglas Stebila]

Attachment: Proposed patch

This patch is equivalent to the patch used in OpenSSL.  I have not been able to confirm that all ECC code still runs correctly because running nss/tests/all.sh on my system (Mac OS X 10.6.7, x86_64) with NSS_ENABLE_ECC=1 results in a bunch of failures, even before this patch is applied.

Comment 2

[Wan-Teh Chang]

Comment on attachment 536810 [details] [diff] [review]
Proposed patch


>+    /*
>+    ** We do not want timing information to leak the length of k,
>+    ** so we compute k*G using an equivalent scalar of fixed
>+    ** bit-length.
>+    ** Fix based on patch for ECDSA timing attack in the paper
>+    ** by Billy Bob Brumley and Nicola Tuveri at
>+    **   http://eprint.iacr.org/2011/232
>+    */
>+    CHECK_MPI_OK( mp_add(&k, &n, &k) );
>+    if (mpl_significant_bits(&k) <= mpl_significant_bits(&n)) {
>+        CHECK_MPI_OK( mp_add(&k, &n, &k) );
>+    }

In pseudo code, the above is:
    k += n;
    if (k is shorter or the same length as n) {
        k += n;
    }

I understand adding n (the group order) results in an equivalent
scalar, but I don't understand how your code makes it fixed bit
length.  Could you explain?  Thanks.

Comment 3

[Johnathan Nightingale [:johnath]]

Minusing this for tracking against current releases since it's not release-specific BUT BUT BUT we would very much like to see approval requests on a reviewed patch, for inclusion in FF8, 9, and 10.

Comment 4

[Douglas Stebila]

(In reply to Wan-Teh Chang from comment #2)
> >+    CHECK_MPI_OK( mp_add(&k, &n, &k) );
> >+    if (mpl_significant_bits(&k) <= mpl_significant_bits(&n)) {
> >+        CHECK_MPI_OK( mp_add(&k, &n, &k) );
> >+    }
> 
> In pseudo code, the above is:
>     k += n;
>     if (k is shorter or the same length as n) {
>         k += n;
>     }
> 
> I understand adding n (the group order) results in an equivalent
> scalar, but I don't understand how your code makes it fixed bit
> length.  Could you explain?  Thanks.

k starts off as integer satisfying 0 <= k < n.  Hence, n <= k+n < 2n.  Now, it could be that k+n has either the same number of bits as n or one more bit than n.  If k+n has the same number of bits as n, the second addition ensures that the final value has exactly one more bit than n.  Thus, we always end up with a value that exactly one more bit than n.

Comment 5

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

The patch is to a function that isn't specific to binary elliptic curves. Does this mean it applies to elliptic curves over primes too?

This code is in the ECDSA signing code path. AFAICT, currently no Mozilla products can even use ECDSA signatures, because we build NSS without ECDSA signing support enabled. We even have an open bug about that: bug 367577. And, even if we were to have ECDSA signing support, we (Mozilla products) only support ECC using non-binary curves.

Comment 6

[Wan-Teh Chang]

Attachment: Proposed patch v2, by Douglas Stebila

Douglas: I added your proof as a comment.  Please review.  Thanks.

I tested your patch with all.sh.  All tests passed.  (To run all.sh
with ECC, you also need to set NSS_ECC_MORE_THAN_SUITE_B=1.)

Comment 7

[Douglas Stebila]

(In reply to Brian Smith (:bsmith) from comment #5)
> The patch is to a function that isn't specific to binary elliptic curves.
> Does this mean it applies to elliptic curves over primes too?

Yes. The academic paper describing this attack implemented it against binary curves because their multiplication routine (Montgomery ladder) is most susceptible to this. They note that certain other types of point multiplication routines could be susceptible. I don't think the prime field ones used in NSS satisfy their constraint. But in ECDSA overall, one should avoid leaking any information about the scalar k, so having the patch affect the prime curve code path potentially eliminates an undiscovered vulnerability and is certainly no detriment.

> This code is in the ECDSA signing code path. AFAICT, currently no Mozilla
> products can even use ECDSA signatures, because we build NSS without ECDSA
> signing support enabled. We even have an open bug about that: bug 367577.
> And, even if we were to have ECDSA signing support, we (Mozilla products)
> only support ECC using non-binary curves.

When I go into about:config in my Firefox 6.0, 10 cipher suites are present that match the string ECDSA, 8 of which are enabled by default.

Comment 8

[Wan-Teh Chang]

Douglas, a TLS client does not need to generate ECDSA signatures
when using an ECDSA cipher suite.  But NSS supports the ecdsa_sign
client authentication method, so Mozilla products can still generate
ECDSA signatures.

Patch checked in on the NSS trunk (NSS 3.13).

Checking in ec.c;
/cvsroot/mozilla/security/nss/lib/freebl/ec.c,v  <--  ec.c
new revision: 1.22; previous revision: 1.21
done

Comment 9

[Wan-Teh Chang]

(In reply to Douglas Stebila from comment #0)
>
> 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.

Have the authors of the paper answered your question?

Comment 11

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

Thanks Wan-Teh for correcting my misunderstanding.

Comment 12

[Daniel Veditz [:dveditz]]

We have a plan to land NSS 3.13 for Firefox soon, not sure if it's Fx8 or 9.

Comment 13

[Daniel Veditz [:dveditz]]

Is there a bug tracking the NSS 3.13 landing described in comment 12? if not I'll file one.

Comment 14

[Wan-Teh Chang]

dveditz: you can use bug 669061 to track the NSS 3.13 landing.

Comment 15

[LegNeato]

---------------------------------[ Triage Comment ]---------------------------------

Dan, this will just land when NSS 3.13 lands? Are you not trying to take this patch on top of the NSS we have?

Comment 16

[u279076]

Is there something QA can do to verify this fix?

Comment 17

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

(In reply to Anthony Hughes, Mozilla QA (irc: ashughes) from comment #16)
> Is there something QA can do to verify this fix?

Not that I can think of, other than ensuring we are shipping NSS 3.13 or later.

Comment 18

[Watson Ladd]

Our fix is completely bogus.

https://dxr.mozilla.org/mozilla-central/source/security/nss/lib/freebl/ec.c?q=ec.c&redirect_type=direct#692
computes the scalar by adding a random multiple of the order, then calls
https://dxr.mozilla.org/mozilla-central/source/security/nss/lib/freebl/ec.c?q=%2Bfunction%3A%22ec_points_mul
which is a small wrapper around
https://dxr.mozilla.org/mozilla-central/source/security/nss/lib/freebl/ecl/ecl_mult.c?q=%2Bfunction%3A%22ECPoints_mul%28const+ECGroup+%2A%2C+const+mp_int+%2A%2C+const+mp_int+%2A%2C+const+mp_int+%2A%2C+const+mp_int+%2A%2C+mp_int+%2A%2C+mp_int+%2A%29%22&redirect_type=single#275

The first thing this function does is reduce the scalar modulo the group order, then passes the scalar to the multiplication routine.

Comment 19

[Watson Ladd]

Attachment: A patch that removes modular reductions, uses total multiplication, fixes optimised routine for P256 to deal

Possible that some multiplication routines expect reduced input and will fail.

Comment 20

[Wan-Teh Chang]

Hi Watson: Thank you for the patch. In the future, it would be
better to open a new bug. Re-opening a very old bug that was
marked as fixed in an NSS release can make it hard to determine
which versions of NSS have the (incorrect) fix.

Comment 21

[Daniel Veditz [:dveditz]]

What's the next step for this bug? Did this patch get moved to a different bug and handled there, or is this a patch we still need to get reviewed and landed?

Comment 22

[Franziskus Kiefer [:franziskus]]

I'm currently investigating. I'll leave the ni here as a reminder until I take action.

Comment 23

[Franziskus Kiefer [:franziskus]]

I'll close this one as fixed again as the original problem was solved. The proposed patch doesn't work and most systems are currently covered and I don't think that the information we're leaking is significant enough to use for anything.