1641795 - (CVE-2020-12413) Raccoon Attack (TLS specification timing side-channel)

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Frederik Braun [:freddy]]

Attachment: mod_lengths.txt

This e-mail was sent to [e-mail] this morning (CEST):

Dear Mozilla Security Team,

We are writing to inform you about a new timing side-channel attack in
the TLS specification we call "raccoon attack".

Please forward this report to the person responsible for TLS (NSS) in
your company.

Please treat this report as confidential, since we are trying to
coordinate the disclosure of this finding.

Since the vulnerability is present in the standard, it may well be
applicable to most implementations, but we did not check whether your
implementation specifically is vulnerable to this attack. The best way
for you to determine whether it is vulnerable is to consult your
developers responsible for TLS.

Your implementation is probably affected if one of the following
applies:

• It supports TLS_DH_ cipher suites
• It supports TLS_DHE_ cipher suites and it is possible to reuse
  ephemeral public keys.
• It supports TLS_DHE_PSK cipher suites (a weaker form of the attack)

If none of these applies to your implementation, it is probably not
vulnerable and you can treat this report as a friendly heads up :).

Vulnerability Details

The core problem within the TLS specification is that for DH(E) the
computed PreMasterSecret (PMS) is supposed to be stripped from leading
zero bytes. This results in the PMS being sometimes longer, and
sometimes a little shorter. But since the PMS is then used to derive the
MasterSecret (MS), multiple potential side channels may arise that leak
the leading bits of the computed PMS. These leading bits can then be
used to compute the PMS if the same public Diffie-Hellman value is used
for multiple connections.

Potential side channel 1: Hash function block border

The PRF used to derive the MS is using HMAC internally with the PMS as
the key. If the PMS is longer than the block size of the hash function
within the HMAC (eg. 512 bit for SHA1, SHA256, or 1024 bit for SHA384),
the PMS has to be hashed before it is used as the HMAC key. Hashing of
inputs of different sizes is inherently not a constant time operation.
Whether the PMS reaches the block size obviously depends on the used
modulo. For standard size moduli (1024, 2048, 4096) it is not possible
to reach the block border of hash functions this way. We attached a list
of dangerous moduli sizes. If you are using a vulnerable moduli size, we
experimentally confirmed that the side channel is big enough such that
the attack can be executed over LAN. 

Potential side channel 2: Hash function padding

Initially, we thought that this just becomes an issue if the PMS is
close to the block size of the hash function (hashing one block vs
hashing two blocks), but experiments showed that a lot of
implementations are also not constant time within a single block. We
attribute this to internal copy operations or the adding of padding
within the hash function. We believe that this kind of side channel is
usually only exploitable in a co-located setup.

Potential side-channel 3: HMAC key padding

If the PMS is smaller than the block size of the hash function, the key
has to be padded to the hash function size. This can also create a
timing side channel. 

Potential side channel 4: DHE_PSK

For DHE_PSK the PMS is constructed differently. Instead of using the
PMS from the Diffie-Hellman computation directly, the PMS is constructed
as:

PMS* = Length | PMS | Length | PSK

This results in a change of the length of the PMS* which is fed into
the hash function. For some PSK lengths, this can leak the length of the
PSK, even if the public DH value of the server is not reused. More
dramatically, if the attacker is a legitimate user and can choose a PSK
for his own account, he can use this to guarantee that PMS* always gets
close to the critical block border.

Potential side channel 5: Direct answers

We saw that some implementations do not require a timing side channel
for exploitation at all since they behave differently if the PMS starts
with a zero byte (e.g., by sending an alert message). This is a bug in
itself, since this means that a fraction of the TLS connections fail
even if no attacker is present. With this bug, the vulnerability is
exploitable by simply observing server responses, without the need for
accurate timing measurements.

Remediation

This is an issue in the TLS specification. Without special care of the
handling of the PMS the side channel will be present. We recommend not
reusing the ephemeral public keys. This leaves the core of the
vulnerability open but makes it not exploitable. Last but not least we
recommend making sure the key derivation runs in constant time even if
the PMS has varying size. To do this, similar techniques as for Lucky13
mitigation can be applied.

Attack Explanation

A sophisticated attacker may be able to exploit this timing behavior as
follows: The attacker intercepts a (DH) CKE message (g^a mod p) for
which he wants to decrypt a session. The attacker then starts a lot of
connections on his own, where he sends his public key as g^a * g^s
mod p for arbitrary values of s, followed by a CCS and an invalid
finished message. The server then computes the PMS as g^ab * g^sb mod
p. The attacker measures the time it took for the implementation to
respond to the invalid finished message. He then tries to identify the
handshakes for which g^ab * g^sb resulted in a PMS with at least one
leading zero byte by looking at the execution time. The attacker can
construct and solve an instance of the Hidden Number Problem to recover
g^ab (for example using common techniques to find the shortest vector
in a lattice) and decrypt the targeted session.

Note that for some moduli this setup does not leak a single byte, but
might leak more than one byte. For example, for a 1036 bit modulus, we
can measure the block borders for SHA384 with a 12-bit leak. In this
specific case, the attacker needs to collect roughly 107 equations with
2^12 * 107 ~= 439000 connections (assuming perfect timing
measurements), and can then recover the shared secret of a past session
in under 20 minutes using lattice techniques.

For the important case of an 8-bit leak, the lattice techniques we used
were not successful with our modest computational power. It probably
requires a lot more measurements and intensive computational efforts.
However, an attacker can always continue measuring until he gets
equations that leak more than the top 8 bits. It is also possible that
other techniques to solve the hidden number problem (besides lattices)
can be applied to improve the result.

ECDH(E)

ECDH(E) is not directly affected by this issue, as in ECDH(E) the PMS is
always padded with zero bytes. Note that this padding might introduce
another side channel that will leak the top bits of the PMS again. We
have not yet investigated whether this potential leak can be exploited. 

FF-DHE TLS 1.3

TLS 1.3 preserves the leading zero bytes of the shared secret. If a
potential padding of the shared secret does not introduce a timing
side-channel, the attack is not applicable to TLS 1.3 directly. However,
if the public DH value of a TLS 1.3 session is shared with TLS 1.2
session the attack becomes possible again. 

Disclosure Timeline

As you can imagine, a lot of different people have to deal with this
issue currently. We want to coordinate the disclosure such that everyone
gets an appropriate time to respond to this issue. We plan to submit our
research to USENIX Security 2021 (in roughly 3 weeks), but we will
commit to not make our research publicly available before September 1st
2020. We would appreciate it if you would also keep this report
confidential until then.

Additional Information

If you need additional help with this report or require additional
clarification, feel free to contact us.

If you think this report applies to your library and you take measures
to mitigate it, we would appreciate hearing from you about the actions
you have taken.

Contact

Robert Merget ([e-mail]) 

Marcus Brinkmann
([e-mail]) 

Nimrod Aviram
([e-mail])

Juraj Somorovsky
([e-mail]) 

Kind Regards

Robert Merget, Marcus Brinkmann, Nimrod Aviram, Juraj Somorovsky

Comment 1

[Thyla van der Merwe]

Dear Robert, Marcus, Nimrod and Juraj,

Thank you so much for sending this through, we truly appreciate it. To confirm, the crux of the attack is to find, using one of the possible timing side channels, an attacker-constructed handshake that results in a PMS with a leading zero byte, and then solving for the HNP produces g^{ab}, the targeted PMS. Is this right?

As you've stated, with a single byte of leakage this attack is difficult to mount successfully from a modest computational power perspective. What do you mean by 'modest' here? Do you have estimates on how much computational power would be required for the single-byte-leakage case to succeed? Also, to use side channel 1, the hash function block border, it seems you need to be using a dangerous modulus size, i.e., non-standard, correct? And in the DHE case, ephemerals have to be reused.

From a Firefox perspective, support for DHE ciphersuites has, independent of your news, been marked for removal in the short-term. We will, however, discuss your findings within the team to determine what NSS components and consumers might be affected.

We appreciate that you've respected a 90-day public disclosure window. The disclosure to potential USENIX reviewers, however, is set to happen within a much tighter time frame. Typically, I imagine that reviewers will respect any disclosure boundaries but we will also discuss this further within the team.

Thank you again for reaching out to us, and for your very detailed report. We hope to be in touch soon.

Best wishes,
Thyla

Comment 2

[Nimrod Aviram]

Dear Thyla, thank you for the prompt response.

To confirm, the crux of the attack is to find, using one of the possible timing side channels, an attacker-constructed handshake that results in a PMS with a leading zero byte, and then solving for the HNP produces g^{ab}, the targeted PMS. Is this right?

Correct. We note the attacker will have to collect many handshakes (~100 handshakes) that result in a PMS with a leading zero byte, and then feed those as input to the HNP.

What do you mean by 'modest' here?

We used 64 cores.

Do you have estimates on how much computational power would be required for the single-byte-leakage case to succeed?

Unfortunately no. We used the above 64 cores for many hours, trying several settings for the HNP solver, but it seems we were not even close for 1024-bit modoli. However, 768-bit modulo with a single byte leakage is feasible with our computational power. For 1024 bit moduli, we also could not provide any estimates by extrapolating from cases we could solve.

Also, to use side channel 1, the hash function block border, it seems you need to be using a dangerous modulus size, i.e., non-standard, correct?

Correct.

And in the DHE case, ephemerals have to be reused.

Correct.

  The disclosure to potential USENIX reviewers, however, is set to happen within a much tighter time frame. Typically, I imagine that reviewers will respect any disclosure boundaries but we will also discuss this further within the team.

We imagine the concern is that reviewers might break the embargo, but we did not experience any problems with this in past projects. Please do let us know if this is a concern for you.

thank you again, best wishes,

Comment 3

[BugBot [:suhaib / :marco/ :calixte]]

The severity field is not set for this bug.
:jcj, could you have a look please?

For more information, please visit auto_nag documentation.

Comment 4

[Thyla van der Merwe]

Thanks for the clarification a while back, Nimrod, appreciated! Regarding your submission to USENIX, we don't see a problem with this. I imagine that you'll be stating in the paper, to reviewers, that you're observing responsible disclose and hence they will know that it's not public yet?

Comment 5

[Juraj Somorovsky]

Thank you Thyla...and yes, correct, we will make it explicitly clear that the result is in the responsible disclosure process.

Comment 6

[robert.merget]

Hey, we saw that you were moving the deprecation of DHE forward. Since we are writing a scientific paper, it would be good to know if this finding influenced the decision to deprecate DHE or if this is just a coincidence. Can you update us on that?

Comment 7

[Thyla van der Merwe]

This was already on our roadmap, and was going to be tackled by the team soon for Firefox, as stated in my first comment. So, the decision to deprecate DHE was already made and we would have moved forward with it regardless but perhaps now we're moving forward one or two Firefox cycles sooner. Again, we are very grateful for your responsible disclosure of what you've found, and the process that you have followed, we truly appreciate it.

Comment 8

[Daniel Veditz [:dveditz]]

We can use CVE-2020-12413 for this bug. NOTE: this CVE covers the Firefox/NSS action taken in our engine to address this attack and is not a generic CVE for the Raccoon attack. Our understanding as a CNA is that each implementation's fix (which could be different) needs a separate CVE.

Comment 9

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

Disabled in 79: https://hg.mozilla.org/mozilla-central/rev/ca83702c2741

Uplift to disable in 78 is pending.

Comment 10

[Nimrod Aviram]

Attachment: Raccoon paper

Comment 11

[Nimrod Aviram]

Hi Folks,

Following your earlier question about the single-byte-leakage case: We have now managed to solve this case.
For the RFC 5114 1024-bit modulo with a single byte leakage, we succeeded in solving the HNP in roughly 2.5 hours with a single CPU core.
We also attach a draft of our paper under submission; Table 3 (on page 12) summarizes the HNP instances we could solve.
(Times in the table are always using a single CPU core.)

best,

Comment 12

[Thyla van der Merwe]

Thanks you for the update, Nimrod, and for a copy of the paper - appreciated!

Comment 13

[Nimrod Aviram]

Hi Mozilla Folks,
Based on discussions with other vendors who are impacted more seriously by this issue, we have moved our own public disclosure date to September 9th.
Some vendors may release patches or disclose this issue on the original date we suggested, September 1st.
Obviously, it is fine with us if you'd like to do so. If you are planing to reference the attack, we would kindly ask you to postpone describing the full attack details to the 9th of September.