Securely downloading and executing code from mutually suspicious authorities

• US 6,167,521 A
• Filed: 08/29/1997
• Issued: 12/26/2000
• Est. Priority Date: 08/29/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Smith, Sean William, Weingart, Steve Harris
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US08/920,814
• Time in Patent Office: 1,215 Days
• Field of Search: 713/200, 713/150, 713/168, 713/180, 395/652, 395/653, 395/712, 395/704, 395/186, 364/280, 380/4, 380/21, 380/286, 709/300, 709/303, 345/440, 705/64, 705/67, 705/71
• US Class Current: 726/21
• CPC Class Codes: G06F 21/33 using certificates
• CPC Class Codes: G06F 21/57 Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
• CPC Class Codes: G06F 2211/008 Public Key, Asymmetric Key, Asymmetric Encryption
• CPC Class Codes: G06F 2211/009 Trust
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: G06Q 20/382 insuring higher security of transaction
• CPC Class Codes: G06Q 20/3829 involving key management

Abstract

An apparatus, system and method for secure code-downloading and information exchange, in the full generality of complex code dependencies while considering the implications of mutual distrust and hot-swapping. Included are secure techniques wherein an authority signs code from another party upon which that authority depends in order to establish that a trusted execution environment, is being preserved. Trusted code is employed to ensure that proprietary data is destroyed, disabled, and/or made unreadable, when a change causes the trusted execution environment to cease holding to a certain security level. A carefully constructed key structure is employed to ensure that communications allegedly from particular code in a particular environment can be authenticated as such. Authenticity of code that decides the authenticity of public-key signatures, and/or the authenticity of other code is cared for. In particular, the loading code that performs these tasks may itself be reloadable. Authenticity is maintained in physically secure coprocessors with multiple levels of dependent software that is independently downloadable by mutually suspicious authorities, and in physically secure coprocessors whose software has sufficient richness and complexity so as to be certainly permeable. Recoverability is provided for physically secure coprocessors from code of arbitrary evil running at arbitrary privilege.

Claims

1. A method for a node'"'"'s authority to download new code into an existing node within a device, said method comprising:

said authority preparing a command message including the new code, load predicates and trust parameters, where the load predicates specify whether a current environment in said device is a secure environment for said code;

said authority communicating said command message to the device;

said device receiving said message;

said device verifying that said message originated from said authority, and verifying that the current environment is valid for said load predicates; and

downloading said code if said message is verified to have originated from said authority, and said current execution environment is valid for said load predicates.

2. A method as recited in claim 1, wherein said existing node has at least one descendent node, said method further comprising:

evaluating for each said descendent node a change in an environment of said existing node resulting from said step of loading by comparing said environment against stored trust parameters for said descendent node;

determining if said change is acceptable for said trust parameters and;

executing said code if said step of determining proves said change to be acceptable, or clearing sensitive data from said descendent node otherwise.

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

said device adjusting at least one of its outgoing authentication keys to reflect said change.

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

said device erasing an original outgoing authentication key of said descendent node;

said device generating and certifying a new outgoing authentication key for said descendent node.

5. A method as recited in claim 4, further comprising the steps of said device generating at least one receipt attesting to said change.

6. A method as recited in claim 5, further comprising authenticating said receipt using an outgoing authentication technique of the existing node.

7. A method as in claim 6, further comprising atomically completing said command and using a software environment that existed before said load was requested.

8. A method as in claim 1, further comprising:

maintaining said device in a safe state following a power failure.

9. A method as in claim 2, further comprising:

maintaining said device in a safe state following a power failure, and

sensing an untrusted download into said existing node triggering deletion of each of said descendent nodes even when recovering from a power failure.

10. A method as recited in claim 1, wherein said trust parameters include requirements which a subsequent change to an execution environment must satisfy in order for the code to continue to be able to run after said subsequent change.

11. A method as recited in claim 1, wherein said step of verifying includes having the device use a public key it has stored for said authority to verify a signature that said authority has produced and communicated along with said command message.

12. A method as recited in claim 1, wherein said device is a smart card.

13. A device as recited in claim 1 wherein said new code includes a new incoming authentication key for said node'"'"'s authority.

14. A method as recited in claim 1, wherein said load predicates include requirements which an execution environment must satisfy in order for the new code to be able to run.

15. A method as recited in claim 11, wherein the step of verifying that said message originated from said authority includes a method of incoming authentication using public key cryptography, and said step of preparing said requirements employs a method of identifying acceptable code, said method of identifying acceptable code including hashing, and wherein an inclusion of said requirements in the command constitute one authority signing code belonging to another.

16. A method as recited in claim 14, wherein said environment requirements which an execution environment must satisfy include:

for the existing node and each of its ancestors, an identification of a particular authority owning each node and an identification particular acceptable code in each node.

17. A method as recited in claim 16, wherein said environment requirements which an execution environment must satisfy further includes a specification of a particular family of devices deemed acceptable.

18. A method for an authority over a parent node in a device to create a child node of said parent node, said method comprising:

said parent authority preparing a create child command for said device,

said command including command predicates;

said authority sending said command to said device;

said device receiving said create child command;

said device verifying a source of said command;

said device creating said child if the predicates are satisfied and said source is said parent authority.

19. A method as recited in claim 18, further comprising making an initial state of said child to be unrunnable and to contain no code or authentication secrets.

20. A method as recited in claim 18, further comprising pre-loading said child with incoming authentication secrets sent in said command.

21. A method for a node authority to send a command to an existing node in a device, said method comprising:

said node authority preparing the command for the device, said command including command predicates;

said node authority sending the command to the device;

said device receiving the command;

said device verifying a source of said command;

said device verifying that the command predicates are valid for a current execution environment of said node; and

implementing said command if said source is verified to be said node authority and if the predicates are satisfied.

22. A method as recited in claim 21, wherein said command is a command to destroy the existing node.

23. A method as recited in claim 21, wherein said command predicates include requirements which the execution environment of said node must satisfy in order for said command to be carried out.

24. A method as recited in claim 23, wherein a method for incoming authentication is a public key method for the existing node, and a method for identifying acceptable code for the existing node includes hashing, said method further comprising allowing one authority to sign code belonging to another authority when the command includes such requirements.

25. A method as recited in claim 23, wherein said command is a command to destroy said existing node, and said existing node has at least one descendent, said method further comprising destroying each descendent of said node and erasing sensitive data in each said descendent.

26. A method as recited in claim 25, wherein said requirements which the execution environment of said node include, for the node being destroyed and each of its ancestors, an identification of a particular authority owning the node, and an identification particular acceptable code in the node, and a specification of a particular family of devices deemed acceptable.

27. A method for a device having a security dependency graph to regenerate an outgoing authentication key for a first node said first node having at least one ancestor having public-key ability, said method comprising:

said device generating a new keypair for said first node;

said device selecting said ancestor for its outgoing authentication technique;

said device composing a certificate for a new outgoing public key of said first node, said certificate includes the new outgoing public key of said first node, identifying an authority over each descendent node in said security dependency graph, and identifying code currently held in the descendent node;

signing said certificate with a current outgoing private key of the ancestor;

saving the new public key for the said first node and saving the certificate in an appropriate memory; and

making the new keypair the active pair for the first node while deleting the old private key.

28. A method for a device to ensure that a first message received from a first node before a change in an execution environment of said first node occurs, is distinguishable from a second message from said first node received after said change occurs, said method comprising:

selecting a pre-existing ancestor of said first node;

composing a second message whenever the first node needs outgoing authentication of the first message;

said second message including said first message;

said second message including a first identity of the authority over said first node, and a second identity of the authority over a second node;

said second message including a first identity of the code currently in said first node, and a second identity of the code currently in said second node;

for each node between said first node and said second node in a security dependency graph of said device, said second message includes a first identity of the authority over said third node, and a second identity of the code in said third node;

authenticating said second message with a current outgoing authentication technique of said second node.

29. A method for a device to respond to a first command, said device having a NODE-A and a NODE-B, said NODE-A under the control of a NODE-A authority, said NODE-B under the control of a NODE-B authority, wherein said NODE-A is an ancestor of said NODE-B, and said first command is a request made by said NODE-A authority, said method comprising:

said NODE-B authority;

selecting a command authentication technique, generating new incoming authentication secrets, and

communicating at least part of said secrets and/or keys to said NODE-A authority; and

said NODE-A authority;

authenticating that said step of communicating originated with NODE-B authority,

preparing an emergency certificate which includes a first identification of said NODE-B authority, the selected command authentication technique, and at least a part of said secrets, and

communicating said emergency certificate to the device to enable said device to respond to said first command.

30. A method as recited in claim 29, wherein said command authentication technique and said step of authenticating each employ a public key cryptology technique, said method further comprising:

sending said emergency certificate to said NODE-B authority; and

said NODE-B authority forwarding said emergency certificate to said device along with a second command to perform said first command.

31. A method as recited in claim 29, further comprising:

NODE-B authority

verifying said load command against information in said emergency certificate; and

verifying that the emergency certificate was indeed produces by said NODE-A authority; and

authorizing said device to perform said command.

32. A method as recited in claim 29, further comprising:

NODE-B authority

verifying said load command against information in said emergency certificate; and

verifying that the emergency certificate was indeed produces by said NODE-A authority; and

authorizing said device to perform a different action on the existing node and the descendent node, when the command uses emergency authentication.

33. A method for a device to create a child NODE-C of an existing NODE-B, by an authority over NODE-B;

said method comprising;

the NODE-B authority preparing and sending a create-child command to the device, said command includes a name of the new child, a name of the child'"'"'s authority; and

command predicates

said NODE-B authority sending the create-child command to the device;

said device receiving the create-child command, verifying that the command came from the NODE-B authority, and verifying that the command predicates are valid for a current execution environment of NODE-B;

creating said child if both steps of verifying are successful, otherwise not creating the child.

34. A method as in claim 33, wherein said child is pre-loaded with incoming authentication secrets sent in the create-child command.

35. A method for securely downloading dependent code from a loading device to a node, said loading device controlled by a first authority, said node controlled by a second authority, said method comprising:

said first authority providing an incoming authentication key of said second authority and an outgoing authentication key for said device;

said second authority allowing said downloading executed in a fashion trusted by said second authority; and

said second authority signing said dependent code.

36. A computer system comprising:

a processor;

a memory for storing instructions and data for the processor;

a communication channel for exchanging message signals between the processor and external devices;

an authenticator for determining whether incoming message signals to the processor are authorized by a trusted authority;

a loader for loading programs into the memory;

a security manager for authorizing the loader to load a new program into the memory only if the authenticator determines that the new program is authorized by a trusted authority;

an operating system or application program in the memory said operating system or application program being "dependent" on both the loader and the operating system or application program, and wherein said trusted authority includes a first influence of a first authority over the loader and a second influence of a second authority over the operating system or application program.

37. A computer system comprising:

a processor;

a port for exchanging message signals between the processor and external devices;

a first memory for storing a loader program executable by the processor, said loader program possessing a first cryptographic key for decoding incoming message signals from a first trusted authority over the loader program, and possessing a second cryptographic key for encoding outgoing message signals from the loader program;

a second memory for storing instructions and data for the processor, and for storing a first child program which calls one or more of the functions provided by the loader program, said first child program possessing a first child cryptographic key for decoding incoming message signals from a second trusted authority over the first child program, and possessing a second child cryptographic key for encoding outgoing message signals from the first child program.

38. A computer system as recited in claim 37, wherein said loader program includes code to verify an integrity level of said child and updated child secrets.

39. A computer system as recited in claim 37, wherein said first child program includes code for an interchange of sensitive data.

40. A computer system as recited in claim 37, wherein said loader program is a program including code to destroy sensitive data.

41. A computer system as recited in claim 37, wherein said first child program includes code for verifying an integrity level of the loader program.

42. A computer system comprising:

a processor;

a communication channel for exchanging message signals between the processor and external devices;

a first memory storing a loader program executable by the processor, said loader program possessing a first cryptographic key for authenticating incoming message signals from a first trusted authority over the loader program, and possessing a second cryptographic key for authenticating outgoing message signals from the loader program;

a second memory for storing instructions and data for the processor, said second memory storing a first child program which depends upon the loader program, said first child program possessing a first child cryptographic key for decoding incoming message signals from a second trusted authority over the first child program, and possessing a second child cryptographic key for encoding outgoing message signals from the first child program.

43. An apparatus for downloading new code into an existing node within a secure device, said apparatus comprising:

a receiver for receiving a download command message from an authority, said message including the new code, load predicates and trust parameters;

a verifying subdevice for verifying that the message is valid for said load predicates and for verifying that the message originated with the authority.

44. A secure device having an existing node and comprising:

a receiver for receiving a first command message from an outside source directed to the existing node, said message including first command actions, load predicates and trust parameters;

a verifying subdevice for verifying that the first command message is valid for said load predicates, and for verifying that the outside source is an authority over the existing node; and

a processor to implement the first command actions when the first command message is verified successfully.

45. A device as in claim 44, wherein the processor is capable of completing a command in progress following recovery from a power failure, and to maintain the device in a safe state following the power failure.

46. A device as recited in claim 44, further comprising a second subdevice to function to ensure that a change to a node and its descendants occur atomically.

47. A device as recited in claim 46 wherein said second subdevice performs said function despite interruptions and failures.

48. A device as recited in claim 44, wherein said existing node has at least one descendent node, said device further comprising:

a subdevice to sense a change in an environment of said existing node resulting from an implementation of the first command actions;

a descendent controller to control a reaction of each descendent node to the change in the environment.

49. A device as recited in claim 48, further comprising:

a key generator for generating keys, wherein the existing node and each descendent each have an outgoing authentication key, and wherein the device adjusts at least one outgoing authentication key to reflect the change in the environment.

50. A device as recited in claim 48, wherein at least one descendent has sensitive data, and wherein said sensor upon sensing an untrusted download into the existing node causes deletion of sensitive data in said at least one descendent.

51. A device as recited in claim 48, wherein said action is to generate a new keypair for the descendent node.

52. A device as recited in claim 48, further comprising:

a memory controller for erasing an original outgoing authentication key of the descendent node, and for certifying a new outgoing authentication key for the descendent node.

53. A device as recited in claim 52, further comprising:

a receipt generator to generate at least one receipt attesting to the change in the environment; and

an authenticator for authenticating the receipt using an outgoing authentication technique of the existing node.

54. A device as recited in claim 48, wherein said first command message is a command to create a child node of the existing node.

55. A device as recited in claim 54, wherein an initial state of the child makes the child unrunnable and to contain no code or authentication secrets.

56. A device comprising:

a NODE-A under the control of a NODE-A authority;

a NODE-B under the control of a NODE-B authority, wherein NODE-A is an ancestor of said NODE-B;

a NODE-B receiver for receiving a first command from the NODE-A authority, and for receiving an emergency certification from the NODE-A authority indicating the NODE-A authority authenticated that at least one of NODE-B secrets originated from the NODE-B authority;

a NODE-B responder for responding to the first command upon receiving permission from the NODE-B authority to prepare and send to the NODE-A authority a first response, where said first response includes at least part of NODE-B secrets, thereby enabling the NODE-A authority to generate and send to NODE-B the emergency certificate.

57. A device as recited in claim 56, wherein the emergency certificate includes a first identification of said NODE-B authority, a second authentication technique, and a shared key for said NODE-B authority.

58. A method for regenerating an outgoing authentication key for a NODE-B, if NODE-B or an ancestor of NODE-B has public-key ability, and if a previous version of the code at NODE-B was trusted, said method comprising the device:

generating a new keypair for NODE-B which includes a new outgoing public key of NODE-B;

composing a new certificate for the new outgoing public key of NODE-B;

signing the new certificate with a current outgoing private key of NODE-B;

saving both the new public key for NODE-B and the certificate in a memory;

making the new keypair to be an active pair for NODE-B; and

deleting an old private key.

59. A method as recited in claim 58, wherein an old version of NODE-B code is trusted and still available, said method being employed for downloads of updated code into B, and for simple renewal of NODE-B'"'"'s key.

60. A method as recited in claim 58, wherein the certificate includes the new public key for NODE-B, and identifying information for an authority over NODE-B and the code for both the previous and a new version of NODE-B.

61. A method for maintaining the security of a first node controlled by a first authority, said first node dependent on a second node controlled by a second authority, when said second authority issues a command for said second node, where said command changes an execution environment of said first node, said method comprising:

said first authority explicitly counter-authenticating said command from said second authority as acceptable for said first node;

destroying said first node and/or deleting its sensitive data when said command arrives without said counter-authentication.