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