1464971 - (CVE-2018-0495) Side Channel Based (EC)DSA Key Extraction in Mozilla NSS

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement)

Description

[Keegan Ryan]

Summary:
--------
An attacker capable of triggering signatures and mounting a side channel
attack against a victim can extract an ECDSA or DSA key in a practical amount
of time. The full attack takes only a few minutes on a modern system, and there
is room for further optimization. We also suggest countermeasures that can be
applied to ECDSA signature generation and DSA signature generation to protect
against this attack.

Other cryptographic libraries are similarly affected, so eventual public
disclosure of this issue and release of a corresponding paper should be
coordinated with these parties as well.

Due to the number of affected libraries, we have not developed a working proof
of concept for NSS, but we have developed a working proof of concept for
a library with a similar code pattern.

Location:
---------
When computing a DSA or ECDSA signature, the signer calculates
    r = x[kG]
    s = k^-1(m + rx)
over a finite field. Our attack targets non-constant time operations in
the addition step
    m + (rx)

Impact:
-------
An attacker can use this attack to extract an ECDSA or DSA private key from a
victim, and the requirements for the attacker are realistic. Consider a HTTPS
server running in a VM in a cloud environment. An unprivileged running in a
colocated VM can initiate a connection to the server to trigger a signature
and use a side channel to leak the desired information about the signature.

Details:
--------
This attack applies a known cryptanalytic technique in a new and unique way and
shows that the needed information can be exposed by NSS via well-known side
channel techniques.

In particular, we use the leaked information to construct an instance of the
Hidden Number Problem (HNP). The HNP has been used before in cryptanalytic
side channel attacks, but typically these attacks seek to leak bits of k during
the exponentiation step of computing r. Various methods exist to solve the HNP
efficiently, including a method based on highly efficient lattice reduction
algorithms.

The HNP problem can be stated as follows:
Given finite field of prime order q, unknown x \in F_q, and a series of multipliers
t_i and approximations u_i to x*t_i, recover the value of x. Approximations can be
written as
    |(t_i * x mod q) - u_i| < q * 2 ^ -l.
That is, when u_i is close to x*t_i, the absolute value on the left hand side is
small. If we can formulate our cryptanalytic attack in this way, we can use
HNP solvers to recover the value of x.

We are targeting the step of adding m to the product rx. In NSS's ECDSA and DSA
signing code, rx has been reduced modulo q. We wish for our side channel to leak
whether m + (rx mod q) is less than q or not (here we are referring to addition within
Z, not within Fq).

This is possible because of the non-constant finite field arithmetic used at
ec.c:822 and dsa.c:406. Both locations use mp_addmod to add m to the reduced product
rx. This can be seen in the following code from ec.c:

    SECITEM_TO_MPINT(t2, &t);                /* t <-$ Zq */
    CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
    CHECK_MPI_OK(mp_invmod(&k, &q, &k));     /* k = k**-1 mod q */
    CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
    SECITEM_TO_MPINT(localDigest, &s);       /* s = HASH(M)     */
    CHECK_MPI_OK(mp_mulmod(&x, &r, &q, &x)); /* x = x * r mod q */
    CHECK_MPI_OK(mp_addmod(&s, &x, &q, &s)); /* s = s + x mod q */
    CHECK_MPI_OK(mp_mulmod(&s, &k, &q, &s)); /* s = s * k mod q */

mp_addmod references mp_mod to reduce the final sum, which has nonconstant time code.
Observe the following snippet of code from mpi.c in the mp_mod function, which calculates
a % m:

  /* ... */
  if ((mag = s_mp_cmp(a, m)) > 0) {
      if ((res = mp_div(a, m, NULL, c)) != MP_OKAY)
          return res;
  /* ... */

If a > m, then a call to mp_div happens that would not happen if a < m. We could perform
a Flush+Reload attack or similar on this code to distinguish which branch is taken and
learn if m + (rx mod q) < q

Assume that the side channel indicates that the above inequality is true. Thus we know:
    m + (rx mod q) < q
	(rx mod q) < q - m
	|(rx mod q) - (q - m) / 2| < (q - m) / 2
The relationship to the HNP is obvious. Under our assumptions, the attacker knows
the value of m and the signature (r, s), so the attacker knows the HNP multiplier
r, approximation (q-m)/2, and bound (q-m)/2. After collecting several approximations
of this type, the attacker can use an HNP solver to calculate x, the private key.

This is a simplified view of the attack. In reality, there are limitations to the
bounds that HNP solvers can tolerate, the side channel may have errors, and it is
possible that the attacker can observe m but not control it. These obstacles can be
overcome with slight modifications to the procedure, but the fundamental idea is
the same.

The cryptanalysis has been implemented in a separate proof of concept and another
similar library has been successfully targeted using Flush+Reload to leak the desired
side-channel information. In that PoC, we demonstrate an unprivileged attacker recovering
a 256 bit ECDSA private key from a colocated process. Due to the number of libraries
with the same leaky code pattern, we have not developed a proof of concept for all
libraries, but we believe it would be straightforward to adapt the attack to compromise
this library.

Recommendation:
---------------
There are two approaches to mitigating this issue, and using both will help defend
against this sort of issue. Though both address slightly different risks, we believe
the first countermeasure is effective against a greater range of threats and its
implementation should be prioritized.

The first approach is to make modular arithmetic for computing the final value of s
branchless. Thus by ensuring there is no difference in code executed when
m + (rx mod q) < q, many side channels will be useless for recovering this data.
This will protect against currently known variations of Prime+Probe, Flush+Reload,
Spectre v1, and more. Since the time needed to compute s is dwarfed by the exponentiation
step in computing r, we believe that making such code constant time is unlikely to
incur a significant performance penalty. Additionally, although this work only
targets the modular addition, it is possible that the same information could be leaked
through modular multiplication, and making all operations involved in computing s
constant time would give greater assurance that the needed information is not being leaked.

The second approach is to use a blinding value for the sum. Even with constant time code
in place, it is theoretically possible that a side channel (such as power analysis under
a Hamming distance model) could distinguish between constant time code subtracting 0 from
the sum and subtracting q. To address this possibility, we recommend introducing a random
blinding multiplier b \in [1, q-1]. Instead of computing the reduced sum:

    (m + (r * x mod q) mod q)    and revealing if    m + (r * x mod q) < q
    
we propose computing:

    (b^-1 * ((b * m mod q) + (b * r * x mod q)) mod q)    and revealing if    (bm mod q) + (brx mod q) < q.

Under these assumptions, the countermeasure is provably secure (although it does not
address if the side channel reveals different information).

Comment 1

[Franziskus Kiefer [:franziskus]]

Thanks for reporting this issue Keegan.
This is mostly an issue on servers. The impact on Firefox is only on WebCrypto using DSA and ECDSA.

Having a constant-time modulo operation would be great but that's nothing we can easily with mpi.
Blinding the value is the obvious quick fix. I'll make a patch.

Comment 2

[Phabricator Automation]

Attachment: Bug 1464971 - making ecdsa and dsa better

Comment 3

[Keegan Ryan]

I have taken a look at the patch, and the newly introduced operations implement the blinding step as intended.

Reminder that as other libraries are similarly affected, this patch should remain private until those libraries are ready to patch as well, which we expect to be in the near future.

Comment 4

[Keegan Ryan]

Other libraries were also able to prepare patches quickly, so we are anticipating a 6/13 release date, at which point it will be okay to make this patch public.

Comment 5

[Franziskus Kiefer [:franziskus]]

This patch probably won't get into an NSS or Firefox release before June 26th.

Comment 6

[Phabricator Automation]

Comment on attachment 8981403 [details]
Bug 1464971 - making ecdsa and dsa better

Martin Thomson [:mt:] has approved the revision.

https://phabricator.services.mozilla.com/D1441

Comment 7

[Franziskus Kiefer [:franziskus]]

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

Comment 8

[Kai Engert (:KaiE:)]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #5)
> This patch probably won't get into an NSS or Firefox release before June
> 26th.

Currently, the patch has been applied to NSS trunk only, for NSS 3.38, which targets Firefox 62, which is scheduled for final release 2 months later than that.

Do you intend any backporting to any older branches for Firefox branches?

If not, should we backport it anyway, to help those who use NSS for servers?