An example of the TPM-fail vulnerability

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.