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.
