1554336 - Potential Remote DoS in NSS due to bug in Modular Inverse

Status: VERIFIED FIXED

(NSS :: Libraries, defect, P1)

Description

[Greg Rubin (he/him)]

Attachment: slow_crypto.html

User Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101 Firefox/60.0

Steps to reproduce:

Due to a bug in how NSS implements the modular inverse (mp_invmod) it is possible to trigger an essentially infinite loop. As this method handles untrusted data via (EC)DSA signature verification and potentially other cryptographic algorithms, this DoS may be remotely exploited. The core bug is in how s_mp_almost_inverse() allows c to grow essentially without bound causing the loop on (approximately) line 2052 "while (MP_SIGN(c) != MP_ZPOS) {" to run for an exceedingly long time. For the examples below we estimate that this loop is executed approximately 2^34 times. If you use calculate the inverse of the following number rather than the number in the examples, the loop should execute approximately 2^82 times.
52dbe34571c0a3944e11a0de96b9bac7d03833d2e852447a9a4b0d02a39d265ecd69aa39c40b91c89dd0324808e77101

Repro 1:
Use mp_invmod to calculate the inverse of 3e10b9f4859fb9e8150cc0d94e83ef428d655702a0b6fb1e684f4755eb6be65ac6048cdfc533f73a9bad76125801051f modulo ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973.

Repro 2:
Embeds the prime and value in an ECDSA signature.

1. Load the attached file "slow_crypto.html" in Firefox
2. Click "Generate ECDSA key"
3. Click "Verify evil signature"
4. Click "OK"

Repro 3:
Embeds the prime and value in the ECDSA signature of an (invalid) certificate.

1. Extract bad_math_server.tgz to a directory on a standard Linux host
2. Install gunicorn (https://gunicorn.org/ just to serve as a simple HTTPS server)
3. Run ./bad_math_server.sh
4. Access https://SERVER-NAME-HERE:4433 in Firefox

Actual results:

Repro 1: Hangs for an excessively long time.

Repro 2: Signature verification will not complete and a background thread will consume CPU resources until the tab is closed.

Repro 3: Browser will not complete TLS handshake. Background thread will spin consuming excessive CPU resource and will not terminate even upon program exit. (Firefox crash reporter eventually detects that this thread does not terminate and kills it.)

Expected results:

Repro 1: Should return 12302214814361c15ab6c0f2131150af186099f8c22f6c9d6e77ad496b551c7c8039e61098bfe2af66474420659435c6

Repro 2: Should complete verification and reject the invalid signature

Repro 3: Should correctly fail the TLS handshake

Note: While the signatures and general TLS setup in these repros are invalid, it is possible to create valid signatures and TLS set-ups with these malicious numbers.

Comment 1

[Greg Rubin (he/him)]

Attachment: bad_math_server.tgz

Comment 2

[Greg Rubin (he/him)]

Attachment: nss_modinv.patch

The attached patch appears to correctly solve this bug.

Comment 3

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

Confirmed locally, marking P1. Marking sec-moderate per https://wiki.mozilla.org/Security_Severity_Ratings, subject to further review. And thank you for the patch!

Sorry I didn't triage this until today, but we're on it now.

Comment 4

[Greg Rubin (he/him)]

Thank you. FWIW, I agree on the impact.

Please be aware that the OpenJDK is also impacted and we are working with them. We don't want to discuss this publicly until they have also had the opportunity to fix it.

Comment 5

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

Kevin's going to take point initially.

Comment 6

[Kevin Jacobs [:kjacobs]]

Thanks for the report and patch!

I agree the patch correctly solves the issue in s_mp_almost_inverse(). However, in the case of an even modulus there's a similar loop: https://searchfox.org/mozilla-central/source/security/nss/lib/freebl/mpi/mpi.c#2238. I'll look into this one tomorrow more closely tomorrow, but I'm curious if you or the OpenJDK folks have already classified it as exploitable or not?

Comment 7

[Kevin Jacobs [:kjacobs]]

The other examples don't seem to be exploitable since they undergo similar modular reduction prior to the loop. This patch seems to be correct and complete.

Comment 8

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

We'll want to take this in 3.44 as well for ESR 68.

Greg: For sec-moderate-rated bugs like this, we typically will land fixes when they're ready, unless embargo requirements specify otherwise. Do you or OpenJDK have a preference on when to land this? (We can do so attempting to minimize disclosure).

Our next release process (feature freeze for 3.45) starts on 28 June. My preference would certainly be to land before then.

Comment 9

[Greg Rubin (he/him)]

J.C.,

I'll try to get an answer back to you shortly. Unfortunately both groups have their own ways to manage this bug so I'm relaying some things back and forth.

Comment 10

[Greg Rubin (he/him)]

Please be aware that Tavis' most recent project-zero bug in Windows modular inverse is not the same as the one we're looking at here. His bug is specifically related to when no modular inverse exists while ours is when one does.

SymCryptFdefModInvGeneric has an infinite loop on line 986 when no inverse exists.

Unfortunately, this may drive more attention to modular inverse implementations and makes it more challenging to release a silent patch.

I'm still trying to get date information for you from the OpenJDK Vulnerability Group. I'm sorry for the delay.

Comment 11

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

I am hoping to take this in NSS_3_44_1_RTM (Bug 1558549) for Firefox 68. In that case, I would prefer to land this by Monday next week, 17 June.

Comment 12

[Greg Rubin (he/him)]

By land do you mean "goes public"? Just clarifying

Comment 13

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

That would mean the patch would appear in public, but we would not call attention to it in the commit message, nor publish test cases.

If that's too soon, the drop-dead date would be 28 June, which would mean us landing/publishing the patch no later than 27 June.

I'm also working with a sec-high bug of much greater priority for NSS that I need to get out the door sooner rather than later, but I don't want to cause harm to OpenJDK/anyone else, either.

Comment 14

[Greg Rubin (he/him)]

Thank you. Forwarding this information (minus comment of related sec-high bug) to OpenJDK.

Comment 15

[Greg Rubin (he/him)]

Oracle has evaluated this as low risk and will fix this in their October release. While they would prefer that Mozilla wait, they do not appear to be worried about Mozilla doing a quiet patch before their release. We are attempting to get better clarification on this tomorrow, June 14th.

Comment 16

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

Thank you for the update, Greg. We'll wait to hear more.

Do you want this patch landed under your name, or for obfuscation purposes, should we use one of ours?

Comment 17

[Greg Rubin (he/him)]

Thank you for the choice. I think that I'd prefer to have it land under my name. I don't think that this would make the issue any more obvious.

(Not clearing the request for info until I can actually get clear info from Oracle.)

Comment 18

[Greg Rubin (he/him)]

(One more note, maybe this should be a Bugzilla bug?)

I do not have access to Bug 1558549 which this bug supposedly blocks. (I assume that I have no need to know for it and so not having access is appropriate.) When I try to view 1558549, I (correctly) get "Access Denied". When I try to view the dependency tree for this bug, it doesn't list any other bugs. However, when I view the dependency graph it displays that 1558549 is related to this one. What's more, if I change the display to show all bugs having any relationship with entered bugs I can see numerous bugs which I do not have access to including which of them have been resolved. I can not see descriptions or any information about them beyond their numbers and relationship though.

My view of the dependency graph

Comment 19

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

That's fascinating. I don't want to go into details about what that graph is showing at present, but if you do want to open a bug about the dependency graph being revealing, please mark it as a security bug and cc me.

Comment 20

[Greg Rubin (he/him)]

I've created 1559447 and given a redacted copy of the graph in that bug. (If you feel that the graph can be supplied in a raw form, please do so. I don't know what is being hinted at.)

As per some of the other bugs I found, I expect this to be closed as a duplicate.

Comment 21

[Greg Rubin (he/him)]

Most recent message from the OpenJDK Vulnerability group:

...
Our current plan is to fix this in the October security release of
OpenJDK (15 Oct). This issue came in late in our release cycle and
could not make an earlier release. If Mozilla is willing to wait until
then, that would be great.

My response to them is as follows:

...
I can absolutely forward on this message to them, However my understanding is that they want to patch NSS on Monday June 17th (ideally) or June 27th at the latest. Does OpenJDK have a position on Mozilla moving forward faster or specific requests for them?

Comment 22

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

I don't think it's appropriate to wait until October given the disclosure on Tuesday of a very similar bug out of Project Zero [0].

I understand their situation, though.

My current plan, pending other comments here, would be to land your patch (under your name) with a patch description of "Optimize away unneeded loop in mpi.c" and no additional tests. We'll open a follow-on bug to land the tests after OpenJDK discloses on their side.

[0] https://bugs.chromium.org/p/project-zero/issues/detail?id=1804

Comment 23

[Greg Rubin (he/him)]

I happen to agree with this. I will forward the following onto OpenJDK VG.

Mozilla does not feel it appropriate for them to wait until October given the disclosure on Tuesday of a very similar bug out of Project Zero [0].

Their current plan is to release the patch shortly with a patch description of "Optimize away unneeded loop in mpi.c" with no additional tests. Tests would be released and made public only after the OpenJDK discloses.

[0] https://bugs.chromium.org/p/project-zero/issues/detail?id=1804

Comment 24

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

Daiki, as far as I can tell, this DOS will affect all uses of NSS as a server, too, and be remotely exploitable.

Comment 25

[Greg Rubin (he/him)]

I think that this is the final relevant response from Oracle/OpenJDK VG:

Hi Greg,

Thank you for letting me know. I guessed they would want to go out
sooner and they need to do what's best for them.

Andrew

Comment 26

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

OK, thanks Greg.

We'll proceed later this week. I really appreciate you relaying here, even if the two groups eventually diverged.

Comment 27

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

https://hg.mozilla.org/projects/nss/rev/efd44c8a6c6330fd5752f57d8d8b627aa3b36b43

Comment 28

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

3.36 branch: https://hg.mozilla.org/projects/nss/rev/54f667fe074aca03840d875fae0f393ccf462083
3.44 branch: https://hg.mozilla.org/projects/nss/rev/1eac9016c021055018389a5cb117678ecc61782a

Comment 29

[Kevin Jacobs [:kjacobs]]

Dan, we'd like to make sure this isn't opened until OpenJDK applies their similar patch. Should we leave it assigned, or go ahead and mark it resolved (with leave-open set)? Thanks.

Comment 30

[Daniel Veditz [:dveditz]]

If we've fixed it the bug should be marked FIXED. "leave-open" is for bugs where we've landed a non-fix patch (tests, diagnostic code) and know we need to come back later and finish it, otherwise the sheriffs or other helpful people might reflexively resolve the bug if they notice a patch landed related to the bug. "leave-open" on a resolved (not open) bug makes no sense, and we might even have bug bots that clean up that kind of thing now.

The whiteboard marking you have is basically what we do, though for clarity in limited space I like to make sure it starts with "Embargo" or "Keep hidden until..." so it's clear right off the bat when skimming.

Comment 31

[Catalin Sasca, Desktop Test Engineering [:csasca]]

I successfully reproduced the issue on Firefox Nightly 69.0a1 (2019-05-24) under Ubuntu 18.04 (x64) using the STR from Comment 0 and some help from Kevin. I used both Repro 2 and Repro 3 for reproducing and verifying the issue.

The issue is no longer reproducible on Firefox Beta 68.0b14 and latest Nightly 69.0a1 (2019-07-02) under Ubuntu 18.04 (x64).

Comment 32

[Greg Rubin (he/him)]

As an update, it currently looks like the patch to the JDK (OpenJDK and others) will not happen before the April 2020 release. I will keep you all posted as I learn more.

Comment 33

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

Thanks the update, Greg.

Comment 34

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

Greg,

We've hit our 22 Oct date where we wanted to check in. Have there been any further updates for the JDK side - is it still looking like April 2020?

Thanks!

Comment 35

[Greg Rubin (he/him)]

There have been no status updates from Oracle or the Java Vulnerability Group (VG). Thus, we appear to still be tracking for April 2020.

Note: The JBS bug # is JDK-8225603

Comment 36

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

Looks like disclosure happened 6 days ago:
https://bodhi.fedoraproject.org/updates/FEDORA-2020-5386fe3bbb

Comment 37

[Greg Rubin (he/him)]

Reviewing the disclosure now

Comment 38

[Greg Rubin (he/him)]

Yes. We see that this is now public. Thank you very much for your patience.