1853908 - (CVE-2023-6135) Minerva attack on P-256 and P-384 in NSS

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[gpantela]

Attachment: In this zip file there are 2 png images. One is called conf_interval_plot_median_before_K_generation and the other conf_interval_plot_median_K_generation

Steps to reproduce:

My team and I have tested NSS and we found that it is vulnerable to the Minerva attack and we have now identified the first piece of code that contributes to the side channel.

The test scenario is that we are signing random messages using the SEC_SignData API and then using the private key to extract the K value from the signatures. Then based on the bit size of the extracted nonce we compare full-sized nonces to smaller ones and use the statistical tests to compare the signature times.

Actual results:

Now we have executed the test to verify that all the code from SEC_SignData up to line https://github.com/nss-dev/nss/blob/master/lib/freebl/ec.c#L978 is not leaky and then we have verified that the code in lines https://github.com/nss-dev/nss/blob/master/lib/freebl/ec.c#L979-L986 does leak. We suspect that the side channel is caused by the fact that K is an MPI object, and thus subject to normalization (automatic memory management based on bit size). You can see the results of the analysis below.

For testing, we built nss statically from hg and used the master checkout from 2023-09-14 for both nss and nspr.

The result in the attachment namedconf_interval_plot_median_before_K_generation.png represents code from SEC_SignData up to line 978 of file lib/freebl/ec.c and as you can see in this code there is no leak found. The sample tested has 102,723,896 observations.

The result in the attachment named conf_interval_plot_median_K_generation.png represents code from line 979 to line 986 in file lib/freebl/ec.c and we can clearly see that there is a leak: there is a clear dependency between the bit size of K and the size of the side channel. The sample tested has 129,438,263 observations.

Because we have identified this piece of code as leaky we won't be able to exclude the possibility of a side-channel in the subsequent code. We will need to run the test again after the leaking piece of code is fixed to be able to verify that NSS is not valuable to Minerva anymore (overall we have found a side-channel of ~50 ns and in the k-generating piece of code is only ~45 ns, although the extra 5 ns could be the effect of this piece of code not being side-channel free on the subsequent signature code).

Expected results:

The code should have no side-channels.

Comment 1

[John Schanck [:jschanck]]

Thanks for this report. We're working on a fix.

Comment 2

[Daniel Veditz [:dveditz]]

John: how bad is this attack for Firefox users in practice? sec-high? sec-moderate?

Comment 3

[John Schanck [:jschanck]]

This code is accessible from WebCrypto and ipcclientcerts, so Firefox is affected. A 50ns difference is going to be difficult to observe over the network. However, reliable observation leads to the disclosure of signing keys, so I think it's a sec-high.

Comment 4

[John Schanck [:jschanck]]

Our partners at Cryspen are going to fix this. I'm self-assigning as they don't have access to sec bugs, and the patch will not be attached to this bug.

Comment 5

[John Schanck [:jschanck]]

This is being handled as part of ongoing work on integrating formally verified implementations of the NIST P-curves into NSS (Bug 1615555, Bug 1854438, Bug 1854439), which will be finished soon.

Comment 6

[Alicja Kario]

@John, but we've tested the P-256 code after https://hg.mozilla.org/projects/nss/rev/88262a8e60126b5168d0b96306ed5fd2de4867bb was merged...

Comment 7

[John Schanck [:jschanck]]

It's being done as part of that line of work. The fix is not part of that patch.

Comment 8

[John Schanck [:jschanck]]

Hubert, the fix for P-256 has been merged to NSS trunk https://hg.mozilla.org/projects/nss/rev/e68b42b773657000078d104aaccbe26e71a1e0be.

Comment 9

[Robert Relyea]

re comment 8: That looks like the code that we thought was the issue.

Comment 10

[John Schanck [:jschanck]]

It seems likely that Cryspen won't have the other curves ready in time for the next NSS release. So I'll write patches for those.

@gpantela, I'd like to confirm our fix for P-256 and also evaluate the size of the side channel for the other curves. Could you share your timing code?

Comment 11

[gpantela]

Attachment: Minerva_timing.zip

Hello, I am attaching Minerva_timing.zip which includes result graphs from the fix on NIST256p and the requested scripts.

For the scripts, there is a readme.md file that explains how to use them.

To elaborate more on the fix. Unfortunately, we do not have enough data yet to say with absolute certainty that the side channel was eliminated completely but the side channel was reduced after the fix to single-digit ns. This means that the fix is improving the situation. We will continue to collect the data and will provide you with additional information later. When you do have the patches for NIST384p and NIST521p feel free to send them to us so we can test them.

Comment 12

[John Schanck [:jschanck]]

Thanks! I've attached a patch for P-384 and P-521 to Bug 1863605.

Comment 13

[John Schanck [:jschanck]]

The patch for P-384 and P-521 has landed in NSS trunk. I'm confident, from inspection of the code and from the timing tests, that there's no longer a network observable timing side-channel here.

Comment 14

[Alicja Kario]

1. testing for P-256 is not finished
2. This is a security issue, we need a CVE assigned
3. We even haven't started testing P-384 or P-521

So, no, I don't think we can consider Minerva to be done and finished as a topic.

Comment 15

[gpantela]

Attachment: conf_interval_plot_all_k_sizes_median_0-10.png

Hello,

We have tested the fixed version on P-521 and we found out that the fix did NOT work fully. It has definitely helped the side channel's size but the side channel is still there. Also in the P-521 curve, there is a "step" from 513 to 512 that needs a bit more attention.
I am attaching a graph with the first 10 nonce sizes that show the side channels and the "step".
Thank you very much for all your time and efforts!

For reference, the p-values of the first 10 nonce sizes are:
K size of 521: n=25992110, pvalue=0.1773705822345769
K size of 520: n=118800233, pvalue=1.1532642817636213e-06
K size of 519: n=69254593, pvalue=0.0006259390728389119
K size of 518: n=37681393, pvalue=7.724653206901568e-09
K size of 517: n=19696178, pvalue=5.492816419730179e-06
K size of 516: n=10082674, pvalue=7.63628467844954e-08
K size of 515: n=5092416, pvalue=0.6586284140275034
K size of 514: n=2561652, pvalue=0.9357608648292923
K size of 513: n=1284527, pvalue=0.04931945934013337
K size of 512: n=642243, pvalue=8.043381228577995e-05
K size of 511: n=322084, pvalue=0.07956264294715022

For any questions feel free to contact us!

Sincerely,
George and Hubert

Comment 16

[gpantela]

As a follow-up to the previous comment:
The version we tested was the head of mercurial on 15/11/2023. It seems to us that the patches for P-384 and P-521 are not integrated completely. There are some changes but the code from bugs 1854438, and 1854439 is not there yet. We tried to apply the patches but they were not applied cleanly. Perhaps a rebase if needed to apply the patches. When you do rebase, we can retest it to verify that the side channels are eliminated before it is merged.

Comment 17

[Alicja Kario]

Attachment: P-521.diff

Since we're most worried about P-521 (as the non multiple of 64 size makes implementation tricky), I've done a quick rebase of the patch from bug 1854439. We'll start testing it.

Comment 18

[John Schanck [:jschanck]]

Thanks for the update. We are aware of timing side-channels in the existing P-384 and P-521 code, and we're also aware of timing side-channels in the work-in-progress replacements from Bug 1854438 and Bug 1854439. The Cryspen team is working on resolving the known issues and plans to have those patches ready early next year.

Given the very low prevalence of P-521 in deployment, and the fact that the timing side-channel is visible in only 1 in 512 nonces, I would not rank the remaining defect as a sec-high. It's important to track that there was a sec-high for P-256 here, so I'm going to split the remaining P-521 defect off into a new bug (Bug 1866848). Feel free to split P-384 off into a new bug if you find that you are still able to detect a side-channel.

Comment 19

[gpantela]

Attachment: Plot of the amount of time need for nss to sign data with ecdsa. No side channel detected.

Hello, my team and I have gathered 701,794,739 samples of singing with NSS ECDSA keys and we can verify that the fix for the NIST256p curve eliminated the side channel in x86_64 architecture.
Also, attaching a plot that shows that there is no visible side channel.

Comment 20

[gpantela]

Follow up on Comment 19:
The version of NSS tested was commit 3e25d69ba6b2 for nspr and 46a7d596d718 for nss. Default branch. The gatherer run on 28-11-2023.

Comment 21

[Jason Kratzer [:jkratzer]]

Attachment: advisory.txt

Comment 22

[Mike Hommey [:glandium]]

This CVE is not listed on https://www.mozilla.org/en-US/security/known-vulnerabilities/nss/

Comment 23

[Daniel Veditz [:dveditz]]

Bulk-unhiding security bugs fixed in Firefox 119-121 (Fall 2023). Use "moo-doctrine-subsidy" to filter

Comment 24

[Daniel Veditz [:dveditz]]

Sorry for the burst of bugspam: filter on tinkling-glitter-filtrate
Adding reporter-external keyword to security bugs found by non-employees for accounting reasons