Closed Bug 1623116 (CVE-2020-12400) Opened 2 years ago Closed 2 years ago

P-384 and P-521 implementation uses a side-channel vulnerable modular inversion function

Categories

(NSS :: Libraries, defect, P1)

Tracking

(firefox-esr68- wontfix, firefox-esr78- wontfix, firefox76 wontfix, firefox77 wontfix, firefox78 wontfix, firefox79- wontfix, firefox80- fixed)

RESOLVED FIXED
Tracking Status
firefox-esr68 - wontfix
firefox-esr78 - wontfix
firefox76 --- wontfix
firefox77 --- wontfix
firefox78 --- wontfix
firefox79 - wontfix
firefox80 - fixed

People

(Reporter: dveditz, Assigned: beurdouche)

References

()

Details

(Keywords: csectype-disclosure, sec-moderate, Whiteboard: [disclosure date 2020-07-28][adv-main80+])

Attachments

(1 file)

Mail to security@ from Alejandro Cabrera Aldaya:


We recently dig into how the EC projective coordinates attack proposed in [1] could affect NSS.

The attack in [1] aims at recover some bits of the scalar starting from the projective representation
of an scalar multiplication output point.
Schemes like ECDSA are very sensitive to scalar leaks, therefore the attack in [1] can thwarts the security of an implementation if the attacker knows the projective representation of the product kG in ECDSA.

The success rate of the attack proposed in [1] depends on several factors such as:

  • Elliptic curve form (Weierstrass, Montogmery, etc.)
  • The finite field over the curve is defined
  • Projective coordinates (Jacobian, Mxy, etc.)
  • Scalar multiplication algorithm

making a high-demand time-consuming task to assess the real threat of this attack on implementation.

During our analysis to several cryptographic libraries we focused on NIST curve P-256 code paths and have found that your library is potentially vulnerable because the projective to affine coordinates conversion uses a side-channel vulnerable modular inversion function.

Considering the number of freedom degrees and potential threats we recommend to use one of the following countermeasures to prevent an already existing vulnerability or a future introduced one if one of the listed factors changes.

Countermeasures:

  • Coordinates randomization after scalar multiplication but just before coordinates conversion takes place.
  • Using FLT to invert Z instead of binary GCD based algorithms during coordinates conversion.

[1] - Naccache et al. - "Projective coordinates leak" - https://eprint.iacr.org/2003/191

The results of our research is going to be published at CHES.
If you wan't to assign a CVE, please let us know to include it a reference in the paper.

Hmm; how quickly can we get the HACL* p256 implementation, I wonder?

I made a copy-and-paste error in the report. Sorry for the noise!

P-256 code path is secure against this attack in NSS.
It uses FLT to compute the modular inversion of Z during the projective to affine coordinates conversion.

The issues relies in P-384 and P-521.
Where a side-channel insecure modular inversion algorithm is used.

JC: is this just a local side-channel, or something that could be detected over the internet somehow? Not sure how to rate the severity here.

Flags: needinfo?(jjones)
Summary: P-256 implementation uses a side-channel vulnerable modular inversion function → P-384 and P-521 implementation uses a side-channel vulnerable modular inversion function

it is a local side-channel

I think the 256 bit curve on 64 bit is vulnerable as well. Only the 32 bit platforms have a special implementation. The quick and fix for this is to change ec_GFp_div() to use Fermat's Little Therom rather than or GCD invert function. The former is significantly slower (you calculate 1/x mod p = x^(p-1) mod p. Blinding is probably the better way to go. That would happend in jac code.

This is a duplicate of Bug 1568061 and also related to Bug 1387108 (CVE-2017-10118).

The short of it is this is mostly a vulnerability for the server-side, and for an uncommon configuration (<1% of Firefox handshakes).

I'm resolving this as a duplicate, and we can continue the server-side discussions in the other two bugs.

Status: NEW → RESOLVED
Closed: 2 years ago
Flags: needinfo?(jjones)
Resolution: --- → FIXED
See Also: → 1387108

Sorry, could you check the CVE? CVE-2017-10118 is related to Java SE.

I don't have access to the mentioned bug tracks, may I get access to them?

It would be nice for our research to know about previous works on this, thanks!

Regarding mostly server-side, take into account NSS is used by other projects as crypto backend (eg. libreswan VPN), where client auth are in place.

jcj: The Resolution doesn't match what you said...

Ugh, sorry about that Hubert. Fixed.

Alejandro - interesting, perhaps they redefined the CVE. It was never ours to begin with, but reported against Java and we got the notice that NSS had the same vulnerability. I'll add you to the other bugs in a moment.

Resolution: FIXED → DUPLICATE
Duplicate of bug: 1568061

jcj: thanks!

I read the descriptions and they are not the same.

We didn't exploit the non-constant time nature of wNAF nor Weierstrass incomplete formulae.

The potential threat resides in the coordinates conversion from projective to affine, that involves a side-channel insecure modular inversion function.

P-384 and P-521 code paths use a modular inversion algorithm based on the binary GCD algorithm.

while P-256 code path use an exponentiation with a non secret exponent (FLT) to compute the inverse.

This code path difference is what makes the P-384 and P-521 potentially exploitable while P-256 doesn't.

Thank you for the clarification - I'm reopening this one.

Status: RESOLVED → REOPENED
Resolution: DUPLICATE → ---
Keywords: sec-moderate

Leaving untriaged for next week's triage

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

For more information, please visit auto_nag documentation.

Flags: needinfo?(jjones)

Replacement of the P384/P521 implementations in Bug 1631583 is going to be the best resolution for this bug, too.

Only if you replace the insecure modular inversion function used to convert from projective coordinates.

Changing the scalar mult to a constant-time variant doesn't help.

(In reply to Alejandro Cabrera Aldaya from comment #15)

Only if you replace the insecure modular inversion function used to convert from projective coordinates.

Indeed.

Ben is currently keeping track of the EC replacements. Assigning to him for tracking.

Assignee: nobody → bbeurdouche
Status: REOPENED → ASSIGNED
Flags: needinfo?(jjones)
Priority: -- → P1

Requesting CVE assignment.

Flags: needinfo?(dveditz)

Assigned CVE-2020-12400

Alias: CVE-2020-12400
Flags: needinfo?(dveditz)

Alejandro and team,

After some more digging here, I'd like to revise my earlier comments and request whether your team would be able to help us rewrite this modular inversion function. I had mistakenly believed that there was one constructed already by the HACL* project, but there is not. As with the other patches, we are happy to and standing by to assist in review and test.

Thank you!

Flags: needinfo?(aldaya)

Hi JC, could you add bbrumley@gmail.com to this thread?

thanks!

Flags: needinfo?(aldaya)

After some more digging here, I'd like to revise my earlier comments and request whether your team would be able to help us rewrite this modular inversion function

Absolutely. When we have the fix for Bug 1631583 (finally) ready, it will remove mp_invmod from this call stack anyway. But the Bug 1631597 fix should make mp_invmod CT so everybody wins :)

Stay tuned and yea we'll appreciate the testing help when my team gets there.

Thank you very much, bbrumley!

Whiteboard: [disclosure date 2020-06-30]
Severity: normal → S3

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

Whiteboard: [disclosure date 2020-06-30] → [disclosure date 2020-07-28]

Our tooling ECCKiila is now public.

We stripped out the NSS rigging and instructions for now, to respect the embargo. (It's questionable if that was necessary, but I acted conservatively.)

The code you are seeing in these revisions is exactly the output from that tooling, just post-processed with unifdef like the instructions say. I used this oneliner

export CURVES="secp256r1 secp384r1 secp521r1"
for c in $CURVES; do unifdef ecp/$c/ecp_$c.c -URIG_GOST -DRIG_NSS -UOPENSSL_BUILDING_OPENSSL -ULIB_TEST > /path/to/libnss/nss/lib/freebl/ecl/ecp_$c.c; done

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

As stated in comment 22, this issue has been remedied in the related and mentioned bugs. Closing.

Status: ASSIGNED → RESOLVED
Closed: 2 years ago2 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.55
Group: crypto-core-security → core-security-release
Flags: qe-verify-
Whiteboard: [disclosure date 2020-07-28] → [disclosure date 2020-07-28][adv-main80+]
Attached file advisory.txt

It's not clear to me from this bug what type of side channel this was - I'm guessing timing? If it's a power analysis attack or something, or you think the advisory can be improved or the credit is incorrect please let me know.

Hey Tom,

A few suggestions below, if it's not too late. It was a page fault attack (although def power analysis would've been an option for us), but without getting too technical for a high level advisory, maybe stressing it's a local attack vector like below is sufficient.

BBB

Byline

Alejandro Cabrera Aldaya, Cesar Pereida García, and Billy Bob Brumley, Network and Information Security (NISEC) Group, Tampere University, Finland

Channel

When converting coordinates from projective to affine, the modular inversion was not performed in constant time, resulting in a possible local microarchitecture attack.

Group: core-security-release
You need to log in before you can comment on or make changes to this bug.