One TPM to Bind Them All: Fixing TPM 2.0 for Provably Secure Anonymous Attestation

The Trusted Platform Module (TPM) is an international standard for a security chip that can be used for the management of cryptographic keys and for remote attestation. The specification of the most recent TPM 2.0 interfaces for direct anonymous attestation unfortunately has a number of severe shortcomings. First of all, they do not allow for security proofs (indeed, the published proofs are incorrect). Second, they provide a Diffie-Hellman oracle w.r.t. the secret key of the TPM, weakening the security and preventing forward anonymity of attestations. Fixes to these problems have been proposed, but they create new issues: they enable a fraudulent TPM to encode information into an attestation signature, which could be used to break anonymity or to leak the secret key. Furthermore, all proposed ways to remove the Diffie-Hellman oracle either strongly limit the functionality of the TPM or would require significant changes to the TPM 2.0 interfaces. In this paper we provide a better specification of the TPM 2.0 interfaces that addresses these problems and requires only minimal changes to the current TPM 2.0 commands. We then show how to use the revised interfaces to build q-SDH-and LRSW-based anonymous attestation schemes, and prove their security. We finally discuss how to obtain other schemes addressing different use cases such as key-binding for U-Prove and e-cash. No PPT adversary has Adv(A) non-negligible in τ . Assumption 2 (LRSW). Let X = g x 2 and Y = g y 2 , and let O X,Y (•) be an oracle that, on input a value m ∈ Z p , outputs a triple (a, a y , a x+xym ) for a randomly chosen a. Define the advantage of A as follows: No PPT adversary has Adv(A) non-negligible in τ . We introduce a generalized version of the LRSW assumption where we split the oracle O X,Y into one that first gives the values a and b, the two elements that do not depend on the message, and one that later provides c upon input of m. That is, after receiving a, b, the adversary may specify a message m to receive c = a x+xym . Assumption 3 (Generalized LRSW). Let X = g x 2 and Y = g y 2 , and let O a,b X (•) return (a, b) with a ← $ G 1 and b ← a y . Let O c X,Y (•) on input (a, b, m), with (a, b) generated by O a,b X,Y , output c = a x+xym . It ignores queries with input (a, b) not generated by O a,b X,Y or inputs (a, b) that were queried before. Define the advantage of A as follows. Adv(A) = Pr (G 1 , G 2 , G T , e, q) ← G(1 τ ), (x, y) No PPT adversary has Adv(A) non-negligible in τ .