Closed Bug 1252035 (Cachebleed) Opened 5 years ago Closed 5 years ago

Investigate the Cachebleed attack, reported by Yuval Yarom


(NSS :: Libraries, defect)

Not set


(firefox47 affected)

Tracking Status
firefox47 --- affected


(Reporter: KaiE, Assigned: rbarnes)




(Keywords: sec-low)


(4 files, 1 obsolete file)

Investigate the Cachebleed attack, reported by Yuval Yarom
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.
Do they have an attack from JS?
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.)
Adding Hovav Shacham for his expertise on JS-based side channels
Attached file cachebleed.pdf
Group: crypto-core-security
Keywords: sec-moderatesec-low
Given that the degraded 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.
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.
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.
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'.
This appears to be the primary OpenSSL commit for this issue:;a=commitdiff;h=708dc2f1291e104fe4eef810bb8ffc1fae5b19c1
This patch just removes the MP_CHAR_STORE_SLOW preprocessor variable and the code that was gated on it.
Attachment #8727097 - Flags: review?(rrelyea)
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 on attachment 8727097 [details] [diff] [review]

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

Comment on attachment 8727098 [details] [diff] [review]

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.


::: 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+
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)
Also, I tested this patch manually with mpi-test.
Attachment #8728434 - Flags: review+
Attachment #8728434 - Flags: checked-in?
Attachment #8727097 - Flags: checked-in?
Yuval: I'm going ahead with this, but would still like your feedback on whether it addresses the problem.
Flags: needinfo?(zz-bugzilla-9297)
Assignee: nobody → rlb
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.24
We should probably get this ported to Firefox soon-ish.  Kai, can you advise?
Flags: needinfo?(kaie)
Attachment #8727097 - Flags: checked-in? → checked-in+
Attachment #8728434 - Flags: checked-in? → checked-in+
(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)
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)
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.
Flags: needinfo?(rlb)
Richard, will you check in an enhancement to address comment 24?
Flags: needinfo?(rlb)
Here you go.
Flags: needinfo?(rlb)
Attachment #8731267 - Flags: review?(kaie)
Comment on attachment 8731267 [details] [diff] [review]

r=kaie, because it matches the suggestion from comment 24
Attachment #8731267 - Flags: review?(kaie) → review+
Attachment #8731267 - Flags: checked-in+
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.