1631573 - (CVE-2020-12401) ECDSA Timing Countermeasure Bypass

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Daniel Veditz [:dveditz]]

[filed from mail to security@ from Alejandro Cabrera Aldaya]

Hello

We are a research group from Tampere University, Finland.

We have been analyzing NSS regarding side-channel vulnerabilities.

We have found that current NSS ECDSA code bypasses one countermeasure used
to prevent a timing attack during signature generation.

Please, find the details of our findings in the attached report.

Best regards,
Alejandro

[timing_bypass_ecdsa_report.md attachment]

---

ECDSA timing vulnerability.

A timing attacker against ECDSA signature generation is able to obtain information from the secret nonce measuring the time an ECDSA signature generation takes.

Description

Current NSS code path has a countermeasure to prevent this know attack since 2011 [1] (actually cited in the code).
However, we have found that said countermeasure is currently completely bypassed.

The countermeasure is in ``lib/freebl/ec.c` :

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));
}

Thus when this code snipped is executed during an ECDSA signature generation,
the nonce is padded such that its bit-length reveals nothing about it.

However, subsequent function calls during scalar multiplication, ECPoints_mul and ECPoint_mul,
removes this padding, thus making the countermeasure useless.
(actually, only one removes the padding, but reporting both as fixing one will not fix the issue)

Fix

Remove the unpadding from ECPoints_mul and ECPoint_mul.
We don't know if there is a correctness rationale to reduce this nonce, you know better.

Disclosure

We are planning for a public disclosure on May 18. But this embargo date
is also up for discussion.

Links

[1] - http://eprint.iacr.org/2011/232

Comment 1

[Daniel Veditz [:dveditz]]

RedHat is tracking this as INC1266620 if we need to talk to their incident folks about it (as opposed to the NSS dev we know).

Comment 2

[J.C. Jones [:jcj] (he/they)]

Thank you and your whole research group for this collection of reports. This comment is being added to each.

I’m assigning each of these to a team member for more detailed analysis beyond our initial triage. As all of these affect RHEL, I am also requesting impact analysis from our RedHat peers as well, as even if a side-channel is local, that might indicate higher-severity for server software than for Firefox. The analysis will also determine how to allocate CVE numbers, as needed.

I would like to advise that the embargo period your team has initially indicated is quite short, and in this case conflicts with both RedHat and Firefox release cycles. For a bug being actively exploited, we can do what is necessary; in the general case, our Release Calendar [0] indicates that to meet a 18 May disclosure date, we would need to make and uplift a point release of NSS from Nightly to Firefox Beta 76 within 8 days, which, given the complexity involved, seems unrealistic - and moreso for all four bugs at once. We’ll have a better idea as we complete our analysis of each bug.

Again, thank you for bringing these issues to our attention. Research such as yours makes the whole world safer!

[0] https://wiki.mozilla.org/Release_Management/Calendar

Comment 3

[J.C. Jones [:jcj] (he/they)]

Requesting CVE assignment.

Comment 4

[Daniel Veditz [:dveditz]]

assigned CVE-2020-12401

Comment 5

[J.C. Jones [:jcj] (he/they)]

Re-targeting to 30 June per https://bugzilla.mozilla.org/show_bug.cgi?id=1631597#c14 - thanks bbrumley and team!

Comment 6

[J.C. Jones [:jcj] (he/they)]

Re-targetting to 2020-07-28 (Firefox 79) per https://bugzilla.mozilla.org/show_bug.cgi?id=1631583#c30

Comment 7

[Billy Brumley]

Attachment: Bug 1631573: Remove unnecessary scalar padding in ec.c

Subsequent calls to ECPoints_mul and ECPoint_mul remove this padding,
making the countermeasure ineffective since 2011.

Timing attack countermeasures are now applied more generally deeper in
the call stack.

Comment 8

[Billy Brumley]

This can go in once Bug 1631583 fixes are merged.

Comment 9

[Ryan VanderMeulen [:RyanVM][PTO June 24-28]]

Per JC, we're going to let these fixes ride the regular NSS trains without uplifting since the severity to Firefox is significantly lower.

Comment 10

[J.C. Jones [:jcj] (he/they)]

Hey Bob, do you want to review this countermeasure fix?

Comment 11

[J.C. Jones [:jcj] (he/they)]

Comment on attachment 9160924 [details]
Bug 1631573: Remove unnecessary scalar padding in ec.c

Security Approval Request

• How easily could an exploit be constructed based on the patch?: Moderate. It's much like Bug 1631583.
• Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?: Yes
• Which older supported branches are affected by this flaw?: all
• If not all supported branches, which bug introduced the flaw?: None
• Do you have backports for the affected branches?: Yes
• If not, how different, hard to create, and risky will they be?: We can only backport this with Bug 1631583, which we decided not to backport.
• How likely is this patch to cause regressions; how much testing does it need?: This should ride the trains, not uplift.

Comment 12

[Daniel Veditz [:dveditz]]

Comment on attachment 9160924 [details]
Bug 1631573: Remove unnecessary scalar padding in ec.c

sec-approval+

Comment 13

[Kevin Jacobs [:kjacobs]]

https://hg.mozilla.org/projects/nss/rev/aeb2e583ee957a699d949009c7ba37af76515c20

Comment 14

[J.C. Jones [:jcj] (he/they)]

I'm planning to uplift this bug's patches to the 3.53 branch for whenever we make our next build of NSS destined for ESR 78.

Comment 15

[BugBot [:suhaib / :marco/ :calixte]]

As part of a security bug pattern analysis, we are requesting your help with a high level analysis of this bug. It is our hope to develop static analysis (or potentially runtime/dynamic analysis) in the future to identify classes of bugs.

Please visit this google form to reply.

Comment 16

[J.C. Jones [:jcj] (he/they)]

NSS_3_53_BRANCH
https://hg.mozilla.org/projects/nss/rev/89733253df83ef7fe8dd0d49f6370b857e93d325

Comment 17

[Tom Ritter [:tjr] (OOTO until mid-August)]

Attachment: advisory.txt

Advisory attached, LMK if corrections are needed.

Comment 18

[Billy Brumley]

It's good from my behalf. Thanks Tom.