Two-phase cryptographic key recovery system

• US 5,937,066 A
• Filed: 10/02/1996
• Issued: 08/10/1999
• Est. Priority Date: 10/02/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zunic, Nevenko, Johnson, Donald Byron, Yung, Marcel Mordechay, Peyravian, Mohammad, Safford, David Robert, Matyas, Stephen Michael Jr., Karger, Paul Ashley, Gennaro, Rosario
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/725,102
• Time in Patent Office: 1,042 Days
• Field of Search: 380/21, 380/30
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB

Abstract

A cryptographic key recovery system that operates in two phases. In the first phase, the sender establishes a secret value with the receiver. For each key recovery agent, the sender generates a key-generating value as a one-way function of the secret value and encrypts the key-generating value with a public key of the key recovery agent. In the second phase, performed for a particular cryptographic session, the sender generates for each key recovery agent a key-encrypting key as a one-way function of the corresponding key-generating value and multiply encrypts the session key with the key-encrypting keys of the key recovery agents. The encrypted key-generating values and the multiply encrypted session key are transmitted together with other recovery information in a manner permitting their interception by a party seeking to recover the secret value. To recover the secret value, the party seeking recovery presents the encrypted key-generating values and public recovery information to the key recovery agents, who decrypt the key-generating values, regenerate the key-encrypting keys from the corresponding key-generating values, and provide the regenerated key-encrypting keys to the recovering party. The recovering party uses the key-encrypting keys to recover the secret value. Since the key-generating values cannot be derived from the key-encrypting keys, they may be used over a period spanning multiple cryptographic sessions without requiring new values or new public key encryptions.

Claims

1. A method of providing for the recovery of a secret value using a key recovery agent, comprising the steps of:

creating a generator value for said key recovery agent;

making said generator value available to said key recovery agent;

generating an encryption key as a one-way function of said generator value; and

encrypting said secret value with said encryption key to generate an encrypted secret value, said secret value being recoverable from said encrypted secret value by having said key recovery agent generate said encryption key as said one-way function of said generator value and decrypting said encrypted secret value with said encryption key.

2. The method of claim 1 in which said step of making said generator value available to said key recovery agent comprises the step of encrypting said generator value with a public key of said key recovery agent to generate an encrypted generator value.

3. The method of claim 1 wherein said step of creating said generator value comprises the steps of:

establishing a secret value; and

generating said generator value as a one-way function of said secret value.

4. The method of claim 1 wherein said encryption key is a first encryption key, said secret value being a second encryption key.

5. The method of claim 1, comprising the further step of encrypting data using said secret value as an encryption key to generate encrypted data.

6. The method of claim 5 wherein said encrypted data is transmitted from a sender to a receiver.

7. The method of claim 5 wherein said encrypted data is placed on a storage medium.

8. The method of claim 5 wherein said encrypted data is associated with a recovery field.

9. The method of claim 8 wherein said recovery field includes said encrypted secret value.

10. The method of claim 8 wherein said recovery field includes said generator value encrypted with a public key of said key recovery agent.

11. The method of claim 8 wherein said recovery field includes said encrypted secret value and said generator value encrypted with a public key of said key recovery agent.

12. The method of claim 1 wherein said encryption key is generated as a one-way function of said generator value and a dynamic value.

13. The method of claim 1 for providing for the recovery of a secret value using a plurality of key recovery agents, comprising the steps of:

creating a generator value for each of said key recovery agents;

making available to each of said key recovery agents the generator value created for that agent;

generating respective encryption keys as one-way functions of said generator values; and

encrypting said secret value with said encryption keys to generate an encrypted secret value, said secret value being recoverable from said encrypted secret value by having said key recovery agents generate said encryption keys as said one-way functions of said generator values and decrypting said encrypted secret value with said encryption keys.

14. The method of claim 13 in which said encrypting step comprises the step of successively encrypting said secret value with said encryption keys to generate said encrypted secret value.

15. The method of claim 13 wherein said step of creating said generator values comprises the steps of:

establishing a secret value; and

generating said generator values as respective one-way functions of said secret value, each of said one-way functions being different from one another.

16. The method of claim 15 wherein said step of generating said generator values comprises the steps of:

generating for each of said key recovery agents an intermediate value as a function of said secret value and a value unique to that agent; and

generating each of said generator values a generator value as a one-way function of the corresponding intermediate value.

17. A method comprising the steps of:

a) providing a secret value to a trustee; and

b) upon a predetermined request, having said trustee calculate a dependent value from at least said secret value and provide said calculated dependent value to a requesting party.

18. The method of claim 17 wherein said trustee calculates said dependent value from said secret value and additional information available to said trustee.

19. The method of claim 17 wherein said trustee calculates said dependent value from said secret value and additional information provided to said trustee.

20. The method of claim 17 wherein said secret value is a first secret value, said calculated dependent value being a second secret value.

21. The method of claim 17 wherein said secret value is a cryptographic key.

22. The method of claim 17 wherein said calculated dependent value is a cryptographic key.

23. The method of claim 17 wherein said calculated dependent value is calculated as a hash value calculated on said secret value.

24. The method of claim 17 wherein said calculated dependent value is calculated as a hash value calculated on said secret value and nonsecret data provided by said requesting party.

25. The method of claim 24 wherein said nonsecret data comprises key recovery information unique to a particular key.

26. The method of claim 17 wherein said secret value is encrypted under a public key of said trustee.

27. The method of claim 17 wherein said secret value is encrypted under a key entrusted to said trustee.

28. The method of claim 17 wherein said secret value provided to said trustee is used to calculate a plurality of dependent values.

29. The method of claim 28 wherein said dependent values are calculated for different requesting parties.

30. The method of claim 28 wherein said dependent values are calculated at different times.

31. A method of encrypting a plaintext block using an encryption key, comprising the steps of:

a) partitioning said plaintext block into first and second parts;

b) subjecting said plaintext block to a plurality of iterations in which said first and second parts are processed as input parts to produce first and second output parts, each of said iterations comprising the steps of;

(1) combining one of said input parts with said key to produce a composite part;

(2) generating a hash of said composite part;

(3) combining said hash of said composite part with the other of said input parts to produce one of said output parts; and

(4) producing the other of said output parts from the other of said input parts; and

c) combining the output parts produced by the last of said iterations to produce an encrypted plaintext block.

32. The method of claim 31 wherein said one of said input parts is combined with said key by concatenating said one of said input parts with said key.

33. The method of claim 31 wherein said one of said input parts is combined with said key by concatenating said one of said input parts with said key and a public header.

34. The method of claim 31 wherein said one of said input parts is combined with said key by prepending said key to said one of said input parts.

35. The method of claim 31 wherein said one of said input parts is combined with said key by appending said key to said one of said input parts.

36. The method of claim 31 wherein said one of said input parts is combined with said key by prepending a first part of said key to said one of said input parts and appending a second part of said key to said one of said input parts.

37. The method of claim 31 wherein said hash of said composite part is combined with the other of said input parts by modulo addition.

38. The method of claim 31 wherein said plaintext block is subjected to at least three of said iterations.

39. In a cryptographic recovery system in which a user encrypts a recovery value using a public recovery key and provides the encrypted recovery value to a recovery agent, said recovery agent being able to recover said recovery value from said encrypted recovery value using a private recovery key corresponding to said public recovery key, a method of establishing said public and private recovery keys for said user and said recovery agent, comprising the steps of:

generating for said user a recovery key pair comprising a public recovery key and a corresponding private recovery key;

transmitting said recovery key pair in a secure manner from said user to said recovery agent.

40. The method of claim 39 in which said user is an individual.

41. The method of claim 39 in which said user is an organization.

42. The method of claim 39 in which said user makes a plurality of recovery values available to respective recovery agents, said steps being performed for each of said recovery agents.

43. The method of claim 39 in which said recovery agent, upon receiving said recovery key pair, verifies that the public and private recovery keys are a valid key pair.

44. The method of claim 43 in which said recovery agent, upon verifying that the public and private recovery keys are a valid key pair, generates a signature on the public verification key using a private signature key and returns the public recovery key with the signature to the user.

45. The method of claim 44 in which said user, upon receiving the public recovery key with the signature, validates the signature using a public verification key corresponding to said signature key.

46. The method of claim 39 in which said recovery agent has a public encryption key, said transmitting step including the steps of:

encrypting the private key of said recovery key pair using said public encryption key of said recovery agent; and

transmitting the public key and encrypted private key of said recovery key pair to said recovery agent.

47. The method of claim 46 in which said recovery agent, upon receiving said recovery key pair, decrypts the private key of said recovery key pair using a private decryption key corresponding to said public encryption key.

48. The method of claim 46 in which said transmitting step includes the steps of:

embedding the private key of said recovery key pair in a device that is operable to encrypt values using said private key but inoperable to reveal said private key; and

providing the public key of said recovery key pair and the device containing the private key of said recovery key pair to said recovery agent.

49. A method for operating a cryptographic system so as to permit a recovery agent to selectively reveal secret information to an applicant, comprising the steps of:

deriving a second secret value from a first secret value;

combining said second secret value with authorization information and calculating a first hash value on the combination; and

providing said authorization information, said first hash value, and said first secret value to said recovery agent for use in recovering said secret information.

50. The method of claim 49 wherein said authorization information is provided to said recovery agent by encrypting it.

51. The method of claim 49 wherein said first secret value is provided to said recovery agent by encrypting it.

52. The method of claim 49 wherein said recovery agent, upon receiving a recovery request from an applicant, performs the steps of:

deriving a second secret value from said first secret value;

combining said second secret value with said authorization information and calculating a second hash value on the combination;

comparing said first and second hash values for equality; and

revealing said secret information if the credentials match with the authorization information and the first and second hash values are equal.

53. Apparatus for providing for the recovery of a secret value using a key recovery agent, comprising:

means for creating a generator value for said key recovery agent;

means for making said generator value available to said key recovery agent;

means for generating an encryption key as a one-way function of said generator value; and

means for encrypting said secret value with said encryption key to generate an encrypted secret value, said secret value being recoverable from said encrypted secret value by having said key recovery agent generate said encryption key as said one-way function of said generator value and decrypting said encrypted secret value with said encryption key.

54. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing for the recovery of a secret value using a key recovery agent, said method steps comprising:

creating a generator value for said key recovery agent;

making said generator value available to said key recovery agent;

generating an encryption key as a one-way function of said generator value; and

encrypting said secret value with said encryption key to generate an encrypted secret value, said secret value being recoverable from said encrypted secret value by having said key recovery agent generate said encryption key as said one-way function of said generator value and decrypting said encrypted secret value with said encryption key.