 # 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. where and . 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 . Then compute . Set . Then compute The signature is . 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 does not finish in constant time. If is small, then it completes measurably faster. Assume that we have an oracle for this and can obtain signatures with, say, of the leading bits of the secret nonce set to .

# 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 .

### 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 where the blanks are 0. The upper row with the entries exist to get the behavior of modulo reduction by . Here, and are defined as which gives us a relation for in terms of known and computable values. The value is a weighting factor, which effectively forces the coefficient for to be in the lattice reduction (whereas a randomly selected is typically in the order of ). Continuing our example, by setting , we can implement the attack as follows.

K = p
X = p * identity_matrix(QQ, ns)
Z = matrix(QQ,  * ns + [K/p] + ).transpose()
Z2 = matrix(QQ,  * (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]
print "Should be", ks

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

## The post TPM-fail TLDR is written by:

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