1623116 - (CVE-2020-12400) P-384 and P-521 implementation uses a side-channel vulnerable modular inversion function

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Daniel Veditz [:dveditz]]

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.

Comment 1

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

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

Comment 2

[Alejandro Cabrera Aldaya]

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.

Comment 3

[Daniel Veditz [:dveditz]]

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.

Comment 4

[Alejandro Cabrera Aldaya]

it is a local side-channel

Comment 5

[Robert Relyea]

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.

Comment 6

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

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.

Comment 7

[Alejandro Cabrera Aldaya]

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.

Comment 8

[Hubert Kario]

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

Comment 9

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

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.

Comment 10

[Alejandro Cabrera Aldaya]

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.

Comment 11

[Kevin Jacobs [:kjacobs]]

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

Comment 12

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

Leaving untriaged for next week's triage

Comment 13

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

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

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

Comment 15

[Alejandro Cabrera Aldaya]

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.

Comment 16

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

(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.

Comment 17

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

Requesting CVE assignment.

Comment 18

[Daniel Veditz [:dveditz]]

Assigned CVE-2020-12400

Comment 19

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

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!

Comment 20

[Alejandro Cabrera Aldaya]

Hi JC, could you add [e-mail] to this thread?

thanks!

Comment 21

[Julien Cristau [:jcristau]]

cc:ed

Comment 22

[Billy Brumley]

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.

Comment 23

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

Thank you very much, bbrumley!

Comment 24

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

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

Comment 25

[Billy Brumley]

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

Comment 26

[Ryan VanderMeulen [:RyanVM]]

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 27

[Kevin Jacobs [:kjacobs]]

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

Comment 28

[Tom Ritter [:tjr] (OOTO until 4/30 at least)]

Attachment: 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.

Comment 29

[Billy Brumley]

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.