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, [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 . 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.