TPM-fail: allows attackers to leak cryptographic keys

Most recently, four security researchers disclosed two vulnerabilities on TPM modules, named collectively under the umbrella name TPM-fail. Effectively, the attack allows an attacker to leak cryptographic keys stored inside the TPM modules. More specifically, the attack is targeted at a timing-information leakage within elliptic-curve computation.

Elliptic curve signatures

The private and public keys are generated as follows.

$\underbrace{d}_{\textnormal{private}} \cdot \underbrace{P}_{\textnormal{generator}} = \underbrace{Q}_{\textnormal{public}},$

where $d \in \mathbb{Z}_p$ and $P,Q \in E$ . Below is an (insecure) example of such a construction, in Sage.

p = random_prime(2**128)
R = GF(p)
E = EllipticCurve(R, [-3, 1])
 
# generate public/private key
d = ZZ(R.random_element())
P = E.random_element()
Q = ZZ(d) * P

The signature in DSA is computed in the following way. First pick a secret integer $k \in \mathbb{Z}_p$ . Then compute $k \cdot Q = (x,y)$ . Set $r = x$ . Then compute

$s = k^{-1} \cdot ( H(m) + d\cdot r)$

The signature is $(r,s)$ . Here is how to compute it.

# message to be signed
message = "sample message"
Hm = int(md5(message).hexdigest(), 16)
k = ZZ(R.random_element())
r,_,_ = k*Q
s = 1/R(k)*(Hm +d*r)
signature = (r, s)

Timing-information leaks

The attacks exploits the simple property that the computation of $k \cdot Q$ does not finish in constant time. If $k$ is small, then it completes measurably faster. Assume that we have an oracle for this and can obtain signatures with, say, $20$ of the leading bits of the secret nonce $k$ set to $0$ .

# samples obtained from the oracle
ns = 50
A = []
B = []
 
# real values for k
ks = []
 
# sign with small k
for i in range(0, ns):
    k = ZZ(R.random_element()) // 2^20
    ks += [k]
    r,_,_ = k*Q
    s = 1/R(k)*(Hm +d*r)
    A += [1/s * Hm]
    B += [1/s * r]

Running this code, gives us enough signatures to recover $k$ .

Lattice attack

The attack proceeds by using lattice-reduction techniques, which finds short vectors in a lattice. The researchers construct a lattice in the following way

$\begin{pmatrix}p & & & & & \\ & p & & & & \\ & &\ddots & & & \\ & & & p & & \\ B_1 & B_2 & \cdots & B_t & K/p & \\ A_1 & A_2 & \cdots & A_t & & K \end{pmatrix}$

where the blanks are 0. The upper row with the $p$ entries exist to get the behavior of modulo reduction by $p$ . Here, $A$ and $B$ are defined as

$k = \underbrace{s^{-1} \cdot H(m)}_{A} + \underbrace{s^{-1} \cdot r }_{B} \cdot d$

which gives us a relation for $k$ in terms of known and computable values. The value $K$ is a weighting factor, which effectively forces the coefficient for $A$ to be $1$ in the lattice reduction (whereas a randomly selected $d$ is typically in the order of $p$ ). Continuing our example, by setting $K=p$ , we can implement the attack as follows.

K = p
X = p * identity_matrix(QQ, ns)
Z = matrix(QQ, [0] * ns + [K/p] + [0]).transpose()
Z2 = matrix(QQ, [0] * (ns+1) + [K]).transpose()
 
Y = block_matrix([[X],[matrix(QQ, B)], [matrix(QQ, A)]])
Y = block_matrix([[Y, Z, Z2]])
Y = Y.LLL()
print "Found", Y[-1][0]
print "Should be", ks[0]

With high probability, this yields the secret $k$ . From this, it is trivial to obtain the private key $d$ .

The post TPM-fail TLDR is written by:

Carl Löndahl, Cyber Security Consultant at Truesec. Original post on grocid.net.

Elliptic curve signatures

Timing-information leaks

Lattice attack

The post TPM-fail TLDR is written by:

Reader Interactions