1568061 - side-channel leakage in ECDSA signature generation

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Daniel Veditz [:dveditz]]

Our security alias received the following from Ján Jančár:

I am a security researcher at Masaryk University in Brno, Czech Republic.

During our research into security of elliptic curve cryptography implementations
on smart-cards and in software libraries [1], we have discovered side-channel
leakage (cache) in the ECDSA signature generation in the Mozilla nss library.

The side-channel is present in the scalar multiplication algorithm in
(lib/freebl/ecl/ecp_jm.c) ec_GFp_pt_mul_jm_wNAF. A local attacker that is able
to observe the order of double and add calls in the loop on lines 265-275 during
ECDSA signing, either through a cache side channel [2,3] or port contention [4]
or a similar microarchitectural side-channel, will be able to recover the
private key, after observing a few tens of signatures. This method is described
in almost the exact scenario as is present in nss, in [2,3,4].

The side channel exists because the addition formulas used by nss are incomplete
and cannot handle the point addition of point at infinity in a side-channel
indistinguishable way. The scalar multiplication loop then has to check whether
the current wNAF digit is a zero, and only add if it isn't.

I do not know what the intended deployment modes and considered attacker models
in nss are, as to whether local/cache attackers are considered. If so, one way
to mitigate this issue would be to replace the addition formulas by complete
ones (those that can handle the point at infinity, as it has a projective
representation) and make the scalar multiplication loop regular, by adding the
point at infinity if the wNAF digit is zero. That point might even be added to
the wNAF precomputed table.

[1] ECTester: https://crocs-muni.github.io/ECTester/

[2] Naomi Benger, Joop van de Pol, Nigel P. Smart, Yuval Yarom: “Ooh Aah... Just
a Little Bit” : A small amount of side channel can go a long way
https://eprint.iacr.org/2014/161.pdf

[3] Joop van de Pol, Nigel P. Smart, Yuval Yarom: Just a Little Bit More
https://eprint.iacr.org/2014/434.pdf

[4] Alejandro C. Aldaya, Billy B. Brumley, Sohaib ul Hassan, Cesar P. Garcia,
Nicola Tuveri: Port Contention for Fun and Profit
https://eprint.iacr.org/2018/1060.pdf

Comment 2

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

This might be a duplicate of - or perhaps very related to - Bug 1387108 (CVE-2017-10118) which was new to me this morning. I'm asking Kevin to investigate both and make a recommendation of criticality and analysis here. I'm also adding in our RedHat folks: This looks to my eyes mostly to be exploitable for NSS used in servers.

Comment 3

[Kevin Jacobs [:kjacobs]]

Yes - it's the same issue. P384 and P521 are impacted, P256 is not (it does not use ec_GFp_pt_mul_jm_wNAF/wNAF).

The above linked papers explore microarchitectural side-channels. It doesn't appear that the timing is remotely distinguishable ([2] notes this type of side channel (on the weight of a scalar) is less easily exploited than one on the length, and [3] concludes that such attacks are not practical to exploit remotely). I think this is sec-medium at most for Firefox, due to very little use of P384/521 and the local attack vector, but this may be higher for RedHat.

The OpenJDK patch [3] gives some improvement, but ideally wNAF is limited to non-secret multiplication, or cases where montgomery ladder or other constant-time approaches aren't usable (or have undue performance impact).

Cherry-picking the OpenJDK patch is the minimum we can do here, but replacing wNAF would likely give better results. Using the former as a temporary mitigation seems reasonable, but given that there's little impact for Firefox, it would be helpful to hear RedHat's analysis and preferred next steps.

[1] https://eprint.iacr.org/2011/232.pdf
[2] https://eprint.iacr.org/2015/839.pdf
[3] http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/rev/996632997de8

Comment 4

[Daniel Veditz [:dveditz]]

CC'ing reporter.

Comment 5

[Ján Jančár]

(In reply to Kevin Jacobs [:kjacobs] from comment #3)

The above linked papers explore microarchitectural side-channels. It doesn't appear that the timing is remotely distinguishable ([2] notes this type of side channel (on the weight of a scalar) is less easily exploited than one on the length, and [3] concludes that such attacks are not practical to exploit remotely). I think this is sec-medium at most for Firefox, due to very little use of P384/521 and the local attack vector, but this may be higher for RedHat.

I only really considered this to be explotiable locally and by a cache or a similar microarchitectural side-channel that gives you the order of doubles and adds as they are executed, [3] in my original report is exactly the case of this. Sure, the timing gives you something, but the DSA lattice attacks on just Hamming Weight (of the NAF representation) will not work. So, as I said in my original report, I don't really know where nss is used and whether this microarchitectural side-channel is an issue in those cases, but as you say, it seems like a minor issue for Firefox. NSS doesn't leak the bit-length due to a mitigation from the "Remote Timing Attacks are Still Practical" paper that is applied on lines 742-744 in lib/freebl/ec.c.

The OpenJDK patch [3] gives some improvement, but ideally wNAF is limited to non-secret multiplication, or cases where montgomery ladder or other constant-time approaches aren't usable (or have undue performance impact).

wNAF could still be used, even with secrets, if complete addition formulas are used. That way, the precomputed table would contain the point at infinity, which the complete addition formulas could handle, and there would not be a need for the conditional add on a non-zero wNAF digit, just an add. -> No timing leakage, no cache leakage (if the array access into the precomputed table is performed properly).

Cherry-picking the OpenJDK patch is the minimum we can do here, but replacing wNAF would likely give better results. Using the former as a temporary mitigation seems reasonable, but given that there's little impact for Firefox, it would be helpful to hear RedHat's analysis and preferred next steps.

I would advise against using that patch, it only really mitigates this as a timing side-channel, which is almost non-existent as it is, but leaves the microarchitectural side-channel open.

See:

• Joost Renes, Craig Costello, Lejla Batina: Complete addition formulas for
  prime order elliptic curves https://eprint.iacr.org/2015/1060.pdf
• Tanja Lange, Daniel J. Bernstein: Explicit Formulas Database
  https://www.hyperelliptic.org/EFD/

for examples of complete addition formulas that could be used.

Comment 6

[Kevin Jacobs [:kjacobs]]

Thanks, Ján. I mentioned the OpenJDK patch because the rating on CVE-2017-10118 seems to suggest remote exploitability, though from your report and what I've found, that doesn't seem to be the case.

Comment 7

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

The priority flag is not set for this bug.
:jcj, could you have a look please?

For more information, please visit auto_nag documentation.

Comment 9

[Kevin Jacobs [:kjacobs]]

NSS 3.55 replaced both P384 and P521 with verifiable implementations from Fiat-Crypto and ECCKiila. I'm closing this bug as code in question is no longer used in NSS, and to the best of our knowledge no such issues are present in the new code.