Trusted hardware component for distributed systems

• US 9,455,992 B2
• Filed: 06/12/2009
• Issued: 09/27/2016
• Est. Priority Date: 06/12/2009
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Levin, David M, Douceur, John R., Lorch, Jacob R., Moscibroda, Thomas
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): FABBRI, ANTHONY E
• Application Number:
  US12/483,338
• Publication Number:
  US 20100318786A1
• Time in Patent Office: 2,664 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 2209/127 Trusted platform modules [TPM]
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Techniques for utilizing trusted hardware components for mitigating the effects of equivocation amongst participant computing devices of a distributed system are described herein. For instance, a distributed system employing a byzantine-fault-resilient protocol—that is, a protocol intended to mitigate (e.g., tolerate, detect, isolate, etc.) the effects of byzantine faults—may employ the techniques. To do so, the techniques may utilize a trusted hardware component comprising a non-decreasing counter and a key. This hardware component may be “trusted” in that the respective participant computing device cannot modify or observe the contents of the component in any manner other than according to the prescribed procedures, as described herein. Furthermore, the trusted hardware component may couple to the participant computing device in any suitable manner, such as via a universal serial bus (USB) connection or the like.

Claims

1. A method comprising:

receiving, by a hardware component and from a first computing device, a representation of a message, the message to be sent to a second computing device, the first computing device and the second computing device participating in a byzantine fault-tolerant protocol;

incrementing, by the hardware component, a monotonically non-decreasing counter from a first value to a second value that is greater than or equal to the first value based at least in part on receiving the representation of the message;

assigning the monotonically non-decreasing counter to a particular conversation between the first computing device and a second computing device, the particular conversation including the message;

binding, by the hardware component, the message to the second value of the monotonically non-decreasing counter;

creating, by the hardware component, a statement that includes the monotonically non-decreasing counter and includes the representation of the message, the statement attesting;

that the hardware component incremented the monotonically non-decreasing counter from the first value to the second value based at least in part on receiving the representation of the message; and

that no other message is to be bound to the second value of the monotonically non-decreasing counter;

signing, by the hardware component, the statement with a cryptographic key to create a signed statement;

sending the signed statement to the first computing device; and

storing the signed statement in a recent attestation queue used to store a predetermined number of most-recently signed statements, each of the most-recently signed statements attesting to a particular increment of the monotonically non-decreasing counter by the hardware component.

2. A method as recited in claim 1, wherein the cryptographic key comprises a symmetric key that is common to the hardware component of the first computing device and a second hardware component of the second computing device.

3. A method as recited in claim 1, further comprising:

maintaining, by the hardware component, a log comprising the signed statement and one or more previously-signed statements.

4. A method as recited in claim 1,

further comprising:

receiving, by the hardware component from the first computing device, a representation of a second message and an instruction to increment the monotonically non-decreasing counter to a specified value that is greater than the second value;

incrementing, by the hardware component, the monotonically non-decreasing counter from the second value to the specified value;

signing, by the hardware component, a statement with the cryptographic key attesting that the hardware component incremented the monotonically non-decreasing counter from the second value to the specified value based at least in part on receiving the representation of the second message; and

sending the signed statement associated with the representation of the second message to the first computing device.

5. A method as recited in claim 1, wherein the hardware component is free from a log other than the recent attestation queue (RAQ).

6. A method as recited in claim 1, wherein the hardware component further comprises:

a monotonically increasing meta-counter; and

multiple other monotonically non-decreasing counters;

and wherein the method further comprises;

receiving, by the hardware component, a request from the first computing device to create a new counter for a new protocol;

assigning, by the hardware component, one of the multiple other monotonically non-decreasing counters as the new counter;

assigning, by the hardware component, a current value of the monotonically increasing meta-counter as an identity of the new counter; and

incrementing, by the hardware component, the current value of the monotonically increasing meta-counter to a new, greater current value.

7. A method as recited in claim 1, wherein the hardware component comprises a third computing device participating in the byzantine fault-tolerant protocol.

8. A method as recited in claim 1, wherein:

multiple additional computing devices participate in the byzantine fault-tolerant protocol; and

each of multiple additional hardware components is associated with a respective one of the multiple additional computing devices.

9. A computer-readable memory device storing computer-executable instructions that, when executed, cause one or more processors to perform operations comprising:

sending a representation of a message, by a first computing device participating in a byzantine-fault-tolerant protocol, to a trusted hardware component associated with the first computing device;

receiving, by the first computing device and from the trusted hardware component, a signed statement that is signed by the trusted hardware component using a key, the signed statement attesting that the trusted hardware component incremented a monotonically non-decreasing counter from a first value to a second value that is greater than or equal to the first value based at least in part on receiving the representation of the message, attesting that the second value is bound to the message, and attesting that no other message will be bound to the second value of the monotonically non-decreasing counter, wherein the monotonically non-decreasing counter is assigned to a particular conversation between the first computing device and a second computing device, the particular conversation including the message;

determining that the signed statement includes the monotonically non-decreasing counter and includes the representation of the message;

storing the signed statement in a log associated with the byzantine-fault-tolerant protocol and maintained in untrusted memory located outside of the trusted hardware component;

sending the message and the signed statement to the second computing device; and

storing the signed statement in a recent attestation queue in untrusted memory.

10. The computer-readable memory device as recited in claim 9, the operations further comprising:

restarting the first computing device after a power failure;

requesting, by the first computing device, to view the signed statement in the recent attestation queue; and

writing, by the first computing device, the signed statement to a log in untrusted memory.

11. The computer-readable memory device as recited in claim 9, wherein the log comprises multiple other previously-signed statements received by the first computing device and from the trusted hardware component, and wherein the first computing device maintains the log in un-trusted memory of the first computing device.

12. The computer-readable memory device as recited in claim 9, the operations further comprising:

providing, by the first computing device and to the trusted hardware component;

(i) a nonce received by the first computing device from the second computing device, and (ii) a request to move in place the monotonically non-decreasing counter of the trusted hardware component in association with the nonce;

receiving a signed statement that is signed by the trusted hardware component attesting that the trusted hardware component moved in place the monotonically non-decreasing counter at least in part in response to receiving the nonce and the request; and

providing the signed statement to another computing device participating in the byzantine-fault-tolerant protocol.

13. The computer-readable memory device as recited in claim 9, wherein the monotonically non-decreasing counter comprises one of multiple monotonically non-decreasing counters of the trusted hardware component, and the operations further comprising:

receiving a request from the first computing device to create a new counter for a new protocol;

assigning an unused monotonically non-decreasing counter of the multiple monotonically non-decreasing counters as the new counter and assigning a current value of a monotonically increasing meta-counter as an identity of the new counter; and

incrementing the current value of the monotonically increasing meta-counter to a new, greater current value.

14. The computer-readable memory device as recited in claim 9, the operations further comprising:

receiving, by the first computing device and from a third computing device participating in the byzantine-fault-tolerant protocol, a message and an additional statement signed by a trusted hardware component of the third computing device and attesting that the trusted hardware component of the third computing device incremented a monotonically non-decreasing counter in association with message; and

verifying that the trusted hardware component of the third computing device signed the additional statement received from the third computing device.

15. The computer-readable memory device as recited in claim 14, wherein the signed statement is signed by a private key of the trusted hardware component of the third computing device, and wherein the verifying of the signed statement comprises verifying the signed statement by the first computing device with a public key of the trusted hardware component of the third computing device.

16. The computer-readable memory device as recited in claim 14, wherein the signed statement is signed by a symmetric key that is common to each trusted hardware component participating in the byzantine-fault-tolerant protocol, and wherein the verifying of the signed statement comprises providing, by the first computing device, the signed statement to the trusted hardware component of the first computing device for verifying the signed statement with the symmetric key by the trusted hardware component.

17. A computer-readable storage device storing computer-executable instructions that, when executed, cause one or more processors to perform operations comprising:

receiving, by a trusted hardware component, a key and a representation of a message from a first computing device, the representation of the message to be sent to a second computing device, the first computing device and the second computing device participating in a byzantine-fault-resilient protocol;

incrementing, by the trusted hardware component, a monotonically non-decreasing counter from a first value to a second value that is greater than the first value based at least in part on receiving the representation of the message;

associating the monotonically non-decreasing counter with a particular conversation, between the first computing device and the second computing device, that includes the message;

binding the second value of the monotonically non-decreasing counter to the message;

creating, by the trusted hardware component, a statement that includes the monotonically non-decreasing counter and includes the representation of the message, the statement attesting;

that the trusted hardware component incremented the monotonically non-decreasing counter from the first value to the second value based at least in part on receiving the representation of the message; and

that no other message is to be bound to the second value of the monotonically non-decreasing counter;

signing, by the trusted hardware component, the statement with the key to create a signed statement;

sending the signed statement to the first computing device; and

storing the signed statement in a recent attestation queue.

18. The computer-readable storage device as recited in claim 17, wherein the byzantine-fault-resilient protocol comprises a byzantine-fault-tolerant protocol, a byzantine-fault-detection protocol or a byzantine-fault-isolation protocol.

19. The computer-readable storage device as recited in claim 17, wherein the key comprises a symmetric key that is common to the trusted hardware component and a trusted hardware component of the second computing device.

20. The computer-readable storage device as recited in claim 19, further storing computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising:

before the signing of the statement;

receiving, from a trusted administrator and at the trusted hardware component, the symmetric key encrypted by a public key of the trusted hardware component;

decrypting the symmetric key using a private key of the trusted hardware component; and

storing the symmetric key within the trusted hardware component.