Bug 1252035 (Cachebleed)

Investigate the Cachebleed attack, reported by Yuval Yarom

RESOLVED FIXED in 3.24

Status

NSS
Libraries
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: kaie, Assigned: rbarnes)

Tracking

({sec-low})

trunk
3.24
sec-low

Firefox Tracking Flags

(firefox47 affected)

Details

(URL)

Attachments

(4 attachments, 1 obsolete attachment)

(Reporter)

Description

2 years ago
Investigate the Cachebleed attack, reported by Yuval Yarom
(Assignee)

Comment 1

2 years ago
I will refrain from discussing details until the paper is released, but try to capture the high-level situation here.

Cachebleed is a timing attack on RSA private-key operations.  This means that NSS is only affected when it is used as a TLS server, e.g., in mod_nss or WebRTC.  (Or for signing / decryption more generally.)  

There are a couple of mitigating factors:
* "The victim and the attacker share the L1 data cache"
* The researchers' current approach requires ~16,000 decryption operations

Firefox and Thunderbird are mostly not affected.  The only case where they act as TLS servers is in the case of WebRTC, and WebRTC always uses ECDSA keys (dtlsidentity.cpp:69).  Firefox and Thunderbird do signing in some other cases (client certificates; S/MIME), but not normally with enough frequency to generate the required signal.

Comment 2

2 years ago
Do they have an attack from JS?
(Assignee)

Comment 3

2 years ago
They do not present an attack from JS in the paper.

It seems like this would be difficult to implement in pure JS.  The attack they describe requires the attacker to run a specific set of instructions to prime the L1 cache, which it's not obvious you can do from JS.  It also requires the attacker to make precise timing measurements, which is difficult from JS.

It may be possible, however, to stimulate signatures from JS to generate a signal that could be picked up by local code.  For example, JS could generate a bunch of requests to a site that requires a client certificate. (Assuming the client certificate UX doesn't make this impractical.)

Comment 4

2 years ago
Adding Hovav Shacham for his expertise on JS-based side channels
(Assignee)

Comment 6

2 years ago
Created attachment 8725269 [details]
cachebleed.pdf
Keywords: sec-moderate
Group: crypto-core-security
Keywords: sec-moderate → sec-low

Comment 7

2 years ago
Given that the degraded performance.now() gives a clock on the order of 1 us, and the attack seems to require a clock with substantially higher resolution, I suspect that it's not currently possible to mount from JavaScript.  Provided, of course, that you never ship SharedArrayBuffers.
SharedArrayBuffer is going to ship.

Comment 9

2 years ago
That is a terrible idea.  It will make it impossible to secure browsers against timing attacks, by providing a timer fine enough even for distinguishing microarchitectural events.
(Assignee)

Comment 10

2 years ago
If SharedArrayBuffer creates a timer with greater precision than we allow in other contexts, that seems like a problem, but probably not one for this bug.
(Assignee)

Comment 11

2 years ago
From the authors:
"""
The issue is the creation of what you call "weave" around line 550 in nss/lib/freebl/mpi/mpmontg.c.

If I understand the code and comments correctly, what you call "weave" is a table of multipliers organised using what we call 'scatter-gather'.
"""
(Assignee)

Comment 12

2 years ago
This appears to be the primary OpenSSL commit for this issue:

https://git.openssl.org/?p=openssl.git;a=commitdiff;h=708dc2f1291e104fe4eef810bb8ffc1fae5b19c1
(Assignee)

Comment 13

2 years ago
Created attachment 8727097 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-1-Remove-duplicate-weave.patch

This patch just removes the MP_CHAR_STORE_SLOW preprocessor variable and the code that was gated on it.
Attachment #8727097 - Flags: review?(rrelyea)
(Assignee)

Comment 14

2 years ago
Created attachment 8727098 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-2-Make-table-access-cons.patch

This patch updates the weave_to_mpi function so that it is constant in terms of time and the pattern of memory accesses.

Bob: This does not update mpi_to_weave, because it did not seem necessary to this patch and because the change we discussed (adding an index) would have required some significant refactoring in the callers. 

Yuval: Does this look sufficient to address the problem, or is there something I've missed here?
Attachment #8727098 - Flags: review?(zz-bugzilla-9297)
Attachment #8727098 - Flags: review?(rrelyea)

Comment 15

2 years ago
Comment on attachment 8727097 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-1-Remove-duplicate-weave.patch

r+ rrelyea.

Please check in only after you have your next patch ready.

OK to check in as a separate patch, though (actually preferred).
Attachment #8727097 - Flags: review?(rrelyea) → review+

Comment 16

2 years ago
so this works, but it's the inefficient way of doing this.

The efficient way is to no longer weave and store the entries as mp_digits. This makes our table search shorter. (the outer loop only loops the number of mp_digits rather than the number of bytes).

Let's get this in as it solves the problem, but then we should update it with something with a little better performance.

bob

Comment 17

2 years ago
Comment on attachment 8727098 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-2-Make-table-access-cons.patch

Review of attachment 8727098 [details] [diff] [review]:
-----------------------------------------------------------------

r+ for the overall correctness.

There is a simple performance improvement we can make by using mp_digits.

bob

::: lib/freebl/mpi/mpmontg.c
@@ +601,5 @@
> +  /* Fetch the proper column in constant time, indexing over the whole array */
> +  for (i=0; i<nRows; ++i) {
> +    unsigned char b = 0;
> +    for (j=0; j<nBignums; ++j) {
> +      b |= weaved[i*nBignums + j] & CONST_TIME_EQ(j, index);

We should be storing weaved as mp_digits. grabing them as chars are less efficient.
Attachment #8727098 - Flags: review?(rrelyea) → review+
(Assignee)

Comment 18

2 years ago
Created attachment 8728434 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-2-Make-table-access-cons.patch r=rrelyea

This patch changes the weave from being in units of bytes to being in units of mp_digits.  It follows the same pattern for constant-time access.

FWIW, I did a quick performance comparison using mpi/timetest, and it looks like the difference is small enough that it's washed out by noise.
Attachment #8727098 - Attachment is obsolete: true
Attachment #8727098 - Flags: review?(zz-bugzilla-9297)
(Assignee)

Comment 19

2 years ago
Also, I tested this patch manually with mpi-test.
(Assignee)

Updated

2 years ago
Attachment #8728434 - Flags: review+
Attachment #8728434 - Flags: checked-in?
(Assignee)

Updated

2 years ago
Attachment #8727097 - Flags: checked-in?
(Assignee)

Comment 20

2 years ago
Yuval: I'm going ahead with this, but would still like your feedback on whether it addresses the problem.
Flags: needinfo?(zz-bugzilla-9297)
https://hg.mozilla.org/projects/nss/rev/c02a3bc19832
https://hg.mozilla.org/projects/nss/rev/57f1c66f5b3a
Assignee: nobody → rlb
Status: NEW → RESOLVED
Last Resolved: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.24
(Assignee)

Comment 22

2 years ago
We should probably get this ported to Firefox soon-ish.  Kai, can you advise?
Flags: needinfo?(kaie)
(Assignee)

Updated

2 years ago
Attachment #8727097 - Flags: checked-in? → checked-in+
(Assignee)

Updated

2 years ago
Attachment #8728434 - Flags: checked-in? → checked-in+
(Reporter)

Comment 23

2 years ago
(In reply to Richard Barnes [:rbarnes] from comment #22)
> We should probably get this ported to Firefox soon-ish.  Kai, can you advise?

Before I make plans about NSS releases, I need to know what Mozilla wants.

On which branches of Firefox would you like this to land, and using what schedule?
Flags: needinfo?(kaie) → needinfo?(rlb)

Comment 24

2 years ago
Looks good.  You may want to change line 572 to:
#define CONST_TIME_EQ(a, b) CONST_TIME_EQ_Z((a) ^ (b))
This does not affect the code as is now, but is a bot more future-proof.
Flags: needinfo?(zz-bugzilla-9297)
(Assignee)

Comment 25

2 years ago
Kai: I think this will be OK to ride the trains, so as long as it makes it in before the next Firefox uplift (18 April), that will be fine.  I expect we'll have an NSS release before then anyway.
(Assignee)

Updated

2 years ago
Flags: needinfo?(rlb)
(Reporter)

Comment 26

2 years ago
Richard, will you check in an enhancement to address comment 24?
Flags: needinfo?(rlb)
(Assignee)

Comment 27

2 years ago
Created attachment 8731267 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-3-Fix-macro-definition.patch

Here you go.
Flags: needinfo?(rlb)
Attachment #8731267 - Flags: review?(kaie)
(Reporter)

Comment 28

2 years ago
Comment on attachment 8731267 [details] [diff] [review]
0001-Bug-1252035-Cachebleed-part-3-Fix-macro-definition.patch

r=kaie, because it matches the suggestion from comment 24
Attachment #8731267 - Flags: review?(kaie) → review+
(Assignee)

Updated

2 years ago
Attachment #8731267 - Flags: checked-in+

Comment 30

2 years ago
Will this fix be backported to any previous version, say, NSS 3.23.x ?
You need to log in before you can comment on or make changes to this bug.