1631576 - (CVE-2020-12399) Timing attack on DSA on NSS library

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Daniel Veditz [:dveditz]]

Attachment: timings.pdf

[filed from mail to security@ from Cesar Pereida Garcia]
Dear NSS and Red Hat folks,

We are a team of security researchers in Finland and we would like to report a vulnerability affecting the DSA signature generation path in NSS.
The vulnerability leaks enough information to recover DSA private keys via a timing attack and a lattice calculation.

Timing attack strikes once more

Affecting NSS latests branch.
This attack draws inspiration from the attacks presented in [1] and [2].
During DSA signature generation in the function dsa_SignDigest, the nonce value k is not padded, exposing the bit length of k,
i.e. the most significant bits (MSBs) of the nonce.
Similar to [1], the regularity of the modular exponentiation function mp_exptmod_safe_i processing the nonce, amplifies and improves the
timing resolution, allowing to clearly distinguish the time it takes to generate a signature, and therefore leaking the MSBs.
Moreover, due to the windowed approach used by the modular exponentiation algorithm, nonce bits are processed in windows of 4 bits,
thus the leakage occurs in multiples of 4 bits.
An attacker can measure the time it takes to compute a DSA signature and then based on the time, catalog in buckets.
The attacker can label each bucket with length n - (4 * i) bits, where n is the length of the DSA private key, and i is the amount
of windows skipped by the algorithm due to smaller nonce length.
The attached figure shows experimental results with a DSA key generated with default parameters using the certutil tool, i.e. 2048-bit DSA with
a 224-bit private key length. As can be appreciated, the timing difference is clearly marked, allowing to easily categorize signatures in each bucket
to then proceed with the lattice calculation to finally recover the private key.

Vulnerable applications

This vulnerability can be exploited by any application performing DSA signatures and using NSS as the cryptography library.
We include Red Hat folks in the loop as they very likely have several tools and applications linking to NSS to perform DSA operations.

Countermeasure

We recommend padding the nonce k value to be of fixed length, similar to the work by [1], resulting in no leakage by the modular exponentiation
function.

We can help develop and/or test the patch, according to your needs, please let us know how would you like to proceed.

Disclosure

We aim a public disclosure of our findings on May 18 (~1 month from today). We appreciate if you could take a look at this issue at your earliest
convenience.

References

[1] Billy Bob Brumley and Nicola Tuveri. “Remote Timing Attacks Are Still Practical”. In Computer Security - ESORICS 2011.
[2] Cesar Pereida, Billy Bob Brumley, and Yuval Yarom. "Make sure DSA signing exponentiations really are constant-time". In 23rd CCS, 2016.

Thanks for your time reviewing this vulnerability.

Regards,

Cesar Pereida Garcia
Doctoral Researcher
Network and Information Security Group (NISEC)
Tampere University

Comment 1

[Daniel Veditz [:dveditz]]

RedHat has tagged this one INC1266622 if we need to talk to them about it.

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

[Robert Relyea]

Attachment: Bug 1631576 - Force a fixed length for DSA exponentiation

Add blinding to k before calculation g^k mod p

Depends on D59652

Comment 4

[Robert Relyea]

I'd like to get the actual reporters to review the proposed patch, is there anyway to do this? The patch adds blinding at the cost of doubling the cost of the DSA operation. I think that's fine since DSA is not our high volume protocol. This is much simpler that trying to come up with a CT version of mod_expt.

Comment 5

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

Billy and team,

Can you follow the review link to Phabricator? Until you've logged in there once, we can't tag you for review, yet your review we'd appreciate. Thank you!

Comment 6

[Billy Brumley]

I .... think I'm registered in Phabricator now (bbrumley)

Comment 7

[Billy Brumley]

Thanks I took a look.

Let's wait for Cesar (it's 5am here in Tampere!) and we'll compare notes together later today.

Comment 8

[cesar.pereida]

(In reply to J.C. Jones [:jcj] (he/him) [increased latency due to COVID-19] from comment #5)

Billy and team,

Can you follow the review link to Phabricator? Until you've logged in there once, we can't tag you for review, yet your review we'd appreciate. Thank you!

I should be registered now as pereida

Comment 9

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

Matt,

Does FxA / nsIIdentityCryptoService still have any need for DSA? It's used there via jwcrypto.jsm, and it use would be potentially subject to this vulnerability.

Comment 10

[Matthew N. [:MattN]]

I was involved in that code for Persona/BrowserID (long dead) but as you noticed it's now used by FxA code so redirecting this to Ryan Kelly.

It does look like it's used: https://searchfox.org/mozilla-central/rev/41c3ea3ee8eab9ce7b82932257cb80b703cbba67/services/fxaccounts/FxAccounts.jsm#1297

Comment 11

[Ryan Kelly [:rfkelly]]

Yeah, we're definitely still using it, although we have finally kicked off a project to remove browserid from the FxA and Sync ecosystem so hopefully it won't be with us for much longer.

In broad strokes: If you're signed in to Firefox with your Firefox Account, then every 12 hours it will generate a fresh DSA keypair. It asks the FxA server to sign the public key to tie it to your account, and then it uses the private key to sign an assertion that's used to authenticate to the Sync servers.

If an attacker was able to intercept one of these assertions, and to learn the corresponding DSA private key, then they would be able to impersonate the victim to all other FxA relying services (because you can use a BrowserID assertion to generate FxA OAuth tokens). As one example, a malicious or compromised Sync Tokenserver might be able to exploit this to hijack the user's credentials and use them on other services, since it's in a position to force the client to generate lots of signatures from the same key.

We know how to stop using DSA here (switch from BrowserID assertions to OAuth tokens, which don't involve any client-side crypto) but we're not in a position to make that change in a hurry.

Comment 12

[Robert Relyea]

JC, we have an approved patch. what's the process from here (I don't want to leak embargoed information before had).

Comment 13

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

Thanks, Bob. At this point, I think it's in my hands, I'll handle the releases.

We're late in the cycle for Firefox 76, since RCs start tomorrow. Since per https://bugzilla.mozilla.org/show_bug.cgi?id=1631583#c8 embargo date is now Firefox 77's release on 2 June, we have a little breathing room. We need to do the sec-approval analysis now and see if we want to land this into NSS trunk now or make a point release at the end of May.

RedHat: If you have input as to how early to make the release of NSS beyond Firefox's timing, let me know.

Comment 14

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

Comment on attachment 9142475 [details]
Bug 1631576 - Force a fixed length for DSA exponentiation

Security Approval Request

• How easily could an exploit be constructed based on the patch?: Medium difficulty
• 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 branches
• 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?:
• How likely is this patch to cause regressions; how much testing does it need?: We have moderate coverage of DSA with automated tests, and it's unlikely we'll encounter correctness regressions from this due to the nature of the change. This change does cause a performance regression, deliberately, but it shouldn't be noticeable.

This will need to be back-ported to ESR 68, which will be tracked and get esr68-approval in uplift Bug 1632908. I propose landing this into Beta 77 and ESR 68.9 at the same time.

Comment 15

[Robert Relyea]

Thanks JC. Our current plan is to pick this up in our next rebase (which is in the next month).

Comment 16

[Daniel Veditz [:dveditz]]

Comment on attachment 9142475 [details]
Bug 1631576 - Force a fixed length for DSA exponentiation

sec-approval for Firefox 77. It's too late for Firefox 76.

Comment 17

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

Requesting CVE assignment.

Comment 18

[Daniel Veditz [:dveditz]]

assigned CVE-2020-12399

Comment 19

[Daniel Veditz [:dveditz]]

more than sec-moderate for Firefox per comment 11

Comment 20

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

default: https://hg.mozilla.org/projects/nss/rev/daa823a4a29bcef0fec33a379ec83857429aea2e
NSS_3_52_BRANCH: https://hg.mozilla.org/projects/nss/rev/a5a9937948c8e3dba3a8065781f0ade74be1259e
NSS_3_44_BRANCH: https://hg.mozilla.org/projects/nss/rev/48612468b52fe730e54c785adac68b6972c95277

Uplifts to Firefox and releases are in progress.

Comment 21

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

beta: https://hg.mozilla.org/releases/mozilla-beta/rev/d64b298d08bc3847778e99a510cc341a7f4dac09

Comment 22

[Julien Cristau [:jcristau]]

https://hg.mozilla.org/mozilla-central/rev/80ded95f5d33

Comment 23

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

https://groups.google.com/d/msg/mozilla.dev.tech.crypto/LL7uY4wvzUs/mp1B7Wd0AQAJ

Comment 24

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

esr68: https://hg.mozilla.org/releases/mozilla-esr68/rev/555ae5322bbb

Comment 25

[Frederik Braun [:freddy]]

Attachment: advisory.txt

Comment 26

[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 27

[Robert Relyea]

response filled in, such as it is.