8
$\begingroup$

Trusted Platform Module (TPM) is designed as a hardware-based root of trust to protect cryptographic keys even against system based adversaries.

Although Intel's firmware based fTPM has FIPS 140-2 and STMicroelectronics hardware-based TPM has Common Criteria EAL 4+ certifications, recently in an attack TPM-FAIL: TPM meets Timing and Lattice Attacks by Moghimi et al., They demonstrated that an attacker can recover server's private authentication key even by remotely.

  • How do the attacks work?
  • What are the countermeasures?
$\endgroup$
  • 2
    $\begingroup$ Interestingly, delay countermeasures or anything about trying to add "jitter" to the computation are not really good usually. $\endgroup$ – Lery Nov 16 '19 at 1:13
8
$\begingroup$

In short, TPMFail attack is black-box timing analysis of TPM 2.0 devices deployed on computers. The TPMfail team is able to extract the private authentication key of TPMS's 256-bit private keys for ECDSA and ECSchnorr signatures, even over networks. This attack successful since there was secret dependent execution in TPMs that causes the timing attacks. To mitigate this attack, a firmware update needed for Intel fTPM and hardware replacement for STMicroelectronics TPM is needed.

How do the attacks work?

The attack is performed in three phases

  • Phase 1: The attacker generates signature pairs and timing information to profile of the given implementation fTPM or STM's. This is the pre-attack stage and the attackers know the secret keys and used nonces. This profile can be measured of-site. After the measurement, they have complete correlation information about the timing and secret nonce $k$ used in signatures. The bias is related to Leading Zero Bits (LZB).

  • Phase 2 With the timing on their hand the attackers target a system with the same TPM devices and collect signature pairs and timing information.

  • Phase 3 The attacker applies lattice-based cryptanalysis with filtered signatures to get biased nonces to recover the private key.

In more Details

  • The timing measurement Normally Intel fTPMs Linux kernel driver uses command response buffer in push mode. The driver checks the status after 20 milliseconds, if the calculation is not ready, the driver re-checks. It doubles the time for every check. This driver doesn't allow a perfect timing measurement, therefore, the TPMfail team developed their kernel driver to perfectly measure the timing. They collected 40000 ECDSA signature. They similarly build a driver for STM's hardware TPM.

  • Timing Analysis: They discovered that a bit-by-bit scalar point multiplication implementation that skips the computation for the most significant zero bits of the nonce. Therefore nonces with more leading zero bits are computed faster in TPMs.

On the below figure it is Intel fTPM's timing histogram. On the right a nonce depended software implementation. Comparing the figures leads to the information that Intel used a 4-bit fixed window during Fixed Window Scalar Multiplication.

enter image description here

In the left figure, there are 4 regions, the fastest one has nonces with 12 most significant windows are zero, next has 8, next has 4, and the slowest region has none.

The Lattice-based Cryptoanalysis

They used The Hidden Number problem lattice attacks. They used BKZ algorithm over the Sage. This attack recovers ECDSA nonces and private keys as long as the nonces are short. Since nonces are selected randomly half of them have zero in MSB, a quarter of them have two zeroes in MSB, etc. The side-channel will help to select the shorter nonces to apply the lattice-based attack.

The key recovery with attack models

  • System adversary a user with administrator privileges to extract the keys. The required signature for 12, 8, and 4 leading zeros for ECDSA

    \begin{array}{|c|c|c|c|}\hline \text{bias} & \text{need signatures} & \text{total sign operations} & \text{succes rate} \\\hline 4-bit & 78 & 1248 & 92\text{%}\\ \hline 8-bit & 34 & 8748 & 100\text{%}\\ \hline 12-bit & 23 & & 100\text{%} \\ \hline \end{array}

    The time for collecting signatures on i7-7700 is 385 signature/minute. Collecting the 8784 signatures took less than 23 minutes. Once the data is collected the Lattice attack took 2 to 3 seconds! for dimension 30.

    For Intel fTPM Schnorr signatures in 27 minutes 10,204 signature are collected with 8-bit leading zeroes. For 4-bit case 65 samples found from 1.040 signature in 1,5 minutes.

    STMicroelectronics TPM ECDSA Key Recovery

    They were able to recover the ECDSA key after 40,000 signature for 8-bit with 35 fastest signatures.

  • User level as before mentioned, in user-level the kernel driver checks the result, first in 20 micro seconds. This lead the below timing measure;

    enter image description here

    They collected 219,000 signatures that contain noisy 855 8-bit leading zeros. With filtering, they get 53 high-quality signatures with 100% recovery rate. They also look for the 4-bit case.

  • Remote adversary This is the weakest adversary in terms of capability. They set up a fast 1G network and requested 40,000 signatures to collect timing information. Although the timing histogram noisier, it still shows information about nonces with 4 and 8-bit leading zeroes. For the 4-bit case; 1,248 signatures are collected in less than 4 minutes and for the 8-bit case; the required signature is collected in 31 minutes.

enter image description here

They used this remote attack against StrongSwang, an open-source IPsec VPN implementation that is supported by modern OSes, including Linux and Microsoft Windows.

What are the countermeasures.

countermeasures

  • The kernel driver can increase the delay time so that this doesn't leak information. However, this may require different levels with different TPM devices. Therefore this is no bulletproof.
  • Constant time implementation. This is the key to the attack point. With data depending calculation the TPMfail team is able to distinguish the calculations. Once calculations are done in constant time, the side channel will be harder. They have testest the patches and couldn't execute the attack anymore.
  • Using double size nonce and setting the high bit to 1 *

Patches

  • CVE-2019-11090. Intel issued a firmware update for Intel Management Engine (ME) including patches to address this issue on November 12, 2019.
  • CVE-2019-16863. STMicroelectronics updated version of their TPM product for verification and sent to authors. They tested and see that it is resistant. Since it is hardware it requires replacement.

Note: From authors:

TPMs have previously suffered from vulnerabilities due to weak key generation. However, It is widely believed that the execution of cryptographic algorithms is secure even against system adversaries.

*Thanks to commentors. See :Why EdDSA held up better than ECDSA against Minerva. Minerva is also a smilar work on smart cards.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I hope, I've given some nice details of this nice attack. If something is not clear, please post a comment. $\endgroup$ – kelalaka Nov 15 '19 at 17:24
  • 3
    $\begingroup$ Is the setting of the nonce's MSB to 1 a recommendation from the TPM.fail team? This sounds like a potential source of bias. $\endgroup$ – SEJPM Nov 15 '19 at 17:26
  • 1
    $\begingroup$ Because then the nonce is no longer drawn uniformly from $[0,q)$? $\endgroup$ – SEJPM Nov 15 '19 at 17:28
  • 2
    $\begingroup$ According to ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf, a 1-bit bias doesn't lead to practical attacks with a 256-bit curve, at least with publicly known techniques as of 2017. A 2-bit bias approches practicality. So I would definitely not recommend forcing a bit to 1. $\endgroup$ – Gilles 'SO- stop being evil' Nov 15 '19 at 17:57
  • 1
    $\begingroup$ LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage. Revealing the high bit of the nonce can lead to a practical attack for small curves (sect163r1, secp192r1). We're getting really close to knowing how to exploit a 1-bit leak in the nonce for the curves used in practice. $\endgroup$ – Gilles 'SO- stop being evil' May 27 at 18:47
5
+100
$\begingroup$

TPM-Fail is a new demonstration of the well-known lattice-based attack of Howgrave-Graham and Smart on DLOG-based signature schemes such as Elgamal, Schnorr, and DSA that exploits partial information about per-signature secrets. TPM-Fail specifically applies the attack with timing side channels from the cryptogrpahy decelerators in TPMs. The attack had previously been applied to timing side channels in OpenSSL over the internet in 2011. A similar lattice-based attack called Minerva was just recently—days before TPM-Fail went public—reported on the same signature schemes in a collection of smart cards and cryptography libraries, apparently independently.

Here's a simplified presentation of how TPM-Fail works on Schnorr signatures, the simplest case.

Schnorr signatures. To make a Schnorr signature on a message $m$ with secret scalar $a$ in a group generated by a generator $G$ of order $n$, the signer picks a per-signature secret $k \in \mathbb Z/n\mathbb Z$ uniformly at random, computes

\begin{align*} R &= [k]G, \\ h &= H(R, m), \qquad \text{and} \\ s &= (k + h a) \bmod n, \end{align*}

and returns $(h, s)$ as the signature. (The verifier accepts it only if $h = H([s]G - [h]A, m)$, where $A = [a]G$ is the public key, but the verifier does not figure into this story.)

The crux of the attack is that the time taken by this computation on the target devices depends on the position of the most significant bit in the per-signature secret $k$—which turns out to be enough information to recover the long-term secret scalar $a$ after a modest number of signatures!

How does it work? We query the TPM for signatures on a series of messages, and use the timing attack to filter by the bit-length of the per-signature secret $k$—we keep only those signatures for which it is below $2^b$ for some $b$ that can be tuned. We gather $d$ different signatures $(h_1, s_1),$ $\dotsc,$ $(h_d, s_d)$ on messages $m_1, \dotsc, m_d$ with per-signature secrets $k_1, \dotsc, k_d$. As the adversary, we don't know $a$ or the $k_i$, but we do know that $k_i < 2^b$ and we do know a system of linear equations relating $k_i$ and $a$, by rearranging the construction of $s$:

\begin{equation*} k_i \equiv s_i - h_i a \pmod n, \qquad 1 \leq i \leq d. \end{equation*}

Using the equation $k_1 \equiv s_1 - h_1 a \pmod n$ to eliminate $a$, we can reduce this to

\begin{equation*} k_i \equiv k_1 u_i - v_i \pmod n, \qquad 2 \leq i \leq d, \end{equation*}

where the coefficients $0 \leq u_i, v_i < n$ can be computed from the $s_i$ and $h_i$—specifically, $u_i \equiv -h_i h_1^{-1}$ and $v_i \equiv h_i h_1^{-1} s_1 - s_i \pmod n$. This can equivalently be stated as a system of equations about integers

\begin{equation*} k_i = k_1 u_i + x_i n - v_i, \qquad 2 \leq i \leq d, \end{equation*}

for some $x_2, \dotsc, x_d$. We can then view the linear system as the matrix equation

\begin{equation*} k = x A - v, \end{equation*}

where $k = (k_1, k_2, \dotsc, k_d)$, $x = (k_1, x_2, \dotsc, x_d)$, $v = (0, v_2, \dotsc, v_d)$, and

\begin{equation*} A = \begin{bmatrix} 1 & u_2 & u_3 & \cdots & u_d \\ 0 & n & 0 & \cdots & 0 \\ 0 & 0 & n & & 0 \\ \vdots & \vdots & & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & n \end{bmatrix}. \end{equation*}

The matrix $A$ serves as a basis generating the lattice $\{x A \in \mathbb Z^d : x \in \mathbb Z^d\}$. Because we selected the $k_i$ to have shorter than usual bit-lengths by the timing side channel, we can conclude that the distance of the lattice vector $x A$ from the vector $v$ is bounded by what would be an improbably small bound for a uniform random system:

\begin{equation*} \lVert x A - v\rVert^2 = \lVert k\rVert^2 = \sum_i \lvert k_i\rvert^2 \leq \sum_i 2^{2b} \lll \sum_i n^2. \end{equation*}

With any of various lattice algorithms like Babai's to approximate solutions to the closest vector problem, we can use $A$ and $v$ find a candidate vector $w$ on the lattice but close to $v$. With any luck—because there are unlikely to be very many lattice vectors this close to $v$$w$ will be exactly the $x A$ we seek, so we can read off the $k_i$ from $w - t$ and recover $a \equiv h_1^{-1} (k_1 - s_1) \pmod n$.

The cost, of course, grows rapidly with $d$, and the success probability depends on $d$ and on how much smaller the bit-lengths $b$ are than $\lceil\lg n\rceil$; Howgrave-Graham and Smart originally applied it to any knowledge of the top 8 bits of 160-bit signatures with 30 signatures, but were unable to apply it to only the top 4 bits of any number of signatures they tried. TPMFail and Minerva extended the number of signatures into the thousands.


There are many more practical details worked out in the TPM-Fail and Minerva attacks:

  • Measuring the timing well enough to find the bit-lengths of the $k_i$.
  • Exploiting biases like the modulo bias in the $k_i$ rather than selecting the $k_i$ with short bit-lengths.
  • Filling out the details for ECDSA, Elgamal signatures, and EC-Schnorr alike.
  • Getting over how unfair it seems that black magic like lattice basis reduction algorithms exist and work as well as they do, and hoping you're not giving up a piece of your immortal soul by using them.

Lessons.

  • Use constant-time logic to avoid leaking the bit-lengths through timing side channels.

  • Either use rejection sampling to choose $k$ uniformly at random, or choose a $2\lceil\lg n\rceil$-bit string uniformly at random like EdDSA does before reducing modulo $n$, in order to keep any bias away from uniform small enough it is unlikely to be exploitable.

    DO NOT choose a $\lceil\lg n\rceil$-bit string uniformly at random and then reduce modulo $n$ to choose $k$; the bias is exploitable.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the complementary answer. $\endgroup$ – kelalaka Dec 29 '19 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.