1252035 - (Cachebleed) Investigate the Cachebleed attack, reported by Yuval Yarom

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Kai Engert (:KaiE:)]

Investigate the Cachebleed attack, reported by Yuval Yarom

Comment 1

[Richard Barnes [:rbarnes]]

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

[Eric Rescorla (:ekr)]

Do they have an attack from JS?

Comment 3

[Richard Barnes [:rbarnes]]

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

[Eric Rescorla (:ekr)]

Adding Hovav Shacham for his expertise on JS-based side channels

Comment 5

[Richard Barnes [:rbarnes]]

Details are now public at:

https://cachebleed.info/
https://ssrg.nicta.com.au/projects/TS/cachebleed//

Comment 6

[Richard Barnes [:rbarnes]]

Attachment: cachebleed.pdf

Comment 7

[Hovav Shacham]

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.

Comment 8

[Lars T Hansen [:lth]]

SharedArrayBuffer is going to ship.

Comment 9

[Hovav Shacham]

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.

Comment 10

[Richard Barnes [:rbarnes]]

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.

Comment 11

[Richard Barnes [:rbarnes]]

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'.
"""

Comment 12

[Richard Barnes [:rbarnes]]

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

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

Comment 13

[Richard Barnes [:rbarnes]]

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

Comment 14

[Richard Barnes [:rbarnes]]

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

Comment 15

[Robert Relyea]

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

Comment 16

[Robert Relyea]

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

[Robert Relyea]

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.

Comment 18

[Richard Barnes [:rbarnes]]

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

Comment 19

[Richard Barnes [:rbarnes]]

Also, I tested this patch manually with mpi-test.

Comment 20

[Richard Barnes [:rbarnes]]

Yuval: I'm going ahead with this, but would still like your feedback on whether it addresses the problem.

Comment 21

[Tim Taubert [:ttaubert] (inactive)]

https://hg.mozilla.org/projects/nss/rev/c02a3bc19832
https://hg.mozilla.org/projects/nss/rev/57f1c66f5b3a

Comment 22

[Richard Barnes [:rbarnes]]

We should probably get this ported to Firefox soon-ish.  Kai, can you advise?

Comment 23

[Kai Engert (:KaiE:)]

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

Comment 24

[zz-bugzilla-9297]

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.

Comment 25

[Richard Barnes [:rbarnes]]

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.

Comment 26

[Kai Engert (:KaiE:)]

Richard, will you check in an enhancement to address comment 24?

Comment 27

[Richard Barnes [:rbarnes]]

Attachment: 0001-Bug-1252035-Cachebleed-part-3-Fix-macro-definition.patch

Here you go.

Comment 28

[Kai Engert (:KaiE:)]

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

Comment 29

[Martin Thomson [:mt:]]

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

Comment 30

[Julien Pierre]

Will this fix be backported to any previous version, say, NSS 3.23.x ?