Method and apparatus for providing interoperability between key recovery and non-key recovery systems

• US 6,535,607 B1
• Filed: 11/02/1998
• Issued: 03/18/2003
• Est. Priority Date: 11/02/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Safford, David R., Gennaro, Rosario, Chandersekaran, Coimbatore S., Gupta, Sarbari, Zunic, Nevenko, Matyas, Stephen M. Jr.
• Primary Examiner(s): Barrón, Gilberto
• Assistant Examiner(s): Zand, Kambiz
• Application Number:
  US09/184,002
• Time in Patent Office: 1,597 Days
• Field of Search: 380/286, 380/273, 380/150, 713/168, 713/169, 713/171
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method and apparatus for ensuring that a key recovery-enabled (KR-enabled) system communicating with a non-KR-enabled system in a cryptographic communication system transmits the information necessary to permit key recovery by a key recovery entity. In a first embodiment, data is encrypted under a second key K that is generated as a one-way function of a first key K′ and a key recovery block KRB generated on the first key K′. The key recovery block KRB and the encrypted data e(K, data) are transmitted to the receiver, who cannot decrypt the data without regenerating the second key K from the first key K′ and the key recovery block KRB. In a second embodiment, data is encrypted under a second key K that is generated independently of the first key K′. A third key X, generated as a one-way function of the first key K′ and a key recovery block KRB generated on the second key K, is used to encrypt the XOR product Y of the first and second keys K′, K. The key recovery block KRB, the encrypted XOR product e(X, Y) and the encrypted data e(K, data) are transmitted to the receiver, who cannot decrypt the data without regenerating the third key X from the first key K′ and the key recovery block KRB, decrypting the XOR product Y using the regenerated third key X, and recombining the XOR product Y with the first key K″ to regenerate the second key K. In a third embodiment, an integrity value is computed on a key K and its key recovery block KRB. The integrity value and the key K are encrypted to form an encrypted portion of a key exchange block KEB, while the key recovery block KRB is put in an unencrypted portion of the key exchange block KEB, which is sent along with the encrypted data e(K, data) to the receiver. The receiver decrypts the encrypted portion, recomputes the integrity value and compares it with the received integrity value. Only if the two integrity values compare is the key K extracted and used to decrypt the data.

Claims

1. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, a method for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising the steps of:

generating a key recovery block from which a first key is recoverable by a key recovery entity;

generating a second key as a one-way function of the first key and the key recovery block; and

encrypting the data under the second key to generate encrypted data, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block and regenerating the second key from the first and the key recovery block.

2. The method of claim 1, further comprising the step of:

transmitting the key recovery block and the encrypted data from the sender to the receiver.

3. The method of claim 2 in which the receiver performs the steps of:

regenerating the second key from the first key and the key recovery block; and

decrypting the encrypted data using the second key.

4. The method of claim 1 in which the generating steps and the encrypting step are performed by a trusted component of the sender.

5. The method of claim 4 in which the second key is not made available outside of the trusted component of the sender.

6. The method of claim 1 further comprising the step of:

generating a key exchange block from which the first key is recoverable by the receiver.

7. The method of claim 6 further comprising the step of:

transmitting the key exchange block from the sender to the receiver.

8. The method of claim 7 in which the receiver performs the step of:

extracting the first key from the key exchange block.

9. The method of claim 1 in which the step of generating a second key comprises the steps of:

encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

generating the second key as a one-way function of the encrypted key recovery block.

10. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, a method for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising the steps of:

generating a key recovery block from which a first key is recoverable by a key recovery entity;

generating a second key independently of the first key;

generating a third key as a one-way function of the first key and the key recovery block;

combining the first and second keys to obtain a result that can be recombined with the first key to regenerate the second key;

encrypting the result under the third key; and

encrypting the data under the second key to generate encrypted data, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block, regenerating the third key from the first key and the key recovery block, decrypting the encrypted result using the regenerated third key, and recombining the result with the first key to regenerate the second key.

11. The method of claim 10, further comprising the step of:

transmitting the key recovery block, the encrypted result and the encrypted data from the sender to the receiver.

12. The method of claim 11 in which the receiver performs the steps of:

regenerating the third key from the first key and the key recovery block;

decrypting the encrypted result using the regenerated third key;

recombining the decrypted result with the first key to regenerate the second key; and

decrypting the encrypted data using the regenerated second key.

13. The method of claim 10 in which the generating steps, the combining step and the encrypting steps are performed by a trusted component of the sender.

14. The method of claim 13 in which the second and third keys are not made available outside of the trusted component of the sender.

15. The method of claim 10, further comprising the step of:

generating a key exchange block from which the first key is recoverable by the receiver.

16. The method of claim 15, further comprising the step of:

transmitting the key exchange block from the sender to the receiver.

17. The method of claim 16 in which the receiver performs the step of:

extracting the first key from the key exchange block.

18. The method of claim 10 in which the step of generating the third key comprises the steps of:

encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

generating the third key as a one-way function of the encrypted key recovery block.

19. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, a method for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising the steps of:

generating a key recovery block from which the encryption key is recoverable by a key recovery entity; and

encrypting the data under an encryption procedure having a corresponding decryption procedure requiring the use of the key recovery block, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block and using the key recovery block in the decryption procedure; and

transmitting the key recovery block and the encrypted data from the sender to the receiver;

the receiver performing the steps of;

receiving the key recovery block and the encrypted data; and

decrypting the encrypted data by using the key recovery block in the decryption procedure.

20. In a cryptographic communication system in which a sender generates a key recovery block from which a first key is recoverable by a key recovery entity, encrypts data under a second key generated as a one-way function of the first key and the key recovery block, and transmits the key recovery block and the encrypted data to a receiver, a method for decrypting the encrypted data, comprising the steps of:

receiving the key recovery block and the encrypted data;

regenerating the second key from the first key and the key recovery block; and

decrypting the encrypted data using the second key.

21. The method of claim 20 in which the step of regenerating the second key comprises the steps of:

encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

generating the second key as a one-way function of the encrypted key recovery block.

22. The method of claim 20 further comprising the step of:

extracting the first key from a key exchange block from which the key is recoverable by the receiver.

23. In a cryptographic communication system in which a sender generates a key recovery block from which a first key is recoverable by a key recovery entity, encrypts data under a second key generated independently of the first key, and transmits the key recovery block and the encrypted data to a receiver, along with a result of combining the first key with the second key that is encrypted under a third key generated as a one-way function of the first key and the key recovery block, a method for decrypting the encrypted data, comprising the steps of:

receiving the key recovery block and the encrypted data;

regenerating the third key from the first key and the key recovery block;

decrypting the encrypted result using the regenerated third key;

recombining the decrypted result with the first key to regenerate the second key; and

decrypting the encrypted data using the regenerated second key.

24. The method of claim 23 in which the step of regenerating the third key comprises the steps of:

encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

generating the third key as a one-way function of the encrypted key recovery block.

25. The method of claim 23, further comprising the step of:

extracting the first key from a key exchange block from which the key is recoverable by the receiver.

26. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, a method for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, the method comprising the steps of:

generating a key recovery block from which a key is recoverable by a key recovery entity; and

generating an integrity value as a one-way function of the key and the key recovery block, whereby a receiver of the key recovery block and the integrity value may verify the key recovery block without regenerating it by regenerating the integrity value as a one-way function of the key and the key recovery block and comparing the regenerated integrity value with the received integrity value.

27. The method of claim 26, comprising the further step of:

transmitting the key recovery block and the integrity value to the receiver.

28. The method of claim 26, further comprising the steps of:

encrypting the integrity value and the key to generate an encrypted portion of a key exchange block having an unencrypted portion containing the key recovery block; and

encrypting the data under the key to generate encrypted data, whereby a receiver of the key exchange block may verify the key recovery block without regenerating it by decrypting the integrity value and the key, regenerating the integrity value as a one-way function of the key and the key recovery block, and comparing the regenerated integrity value with the decrypted integrity value.

29. The method of claim 28 in which the receiver performs the steps of:

decrypting the integrity value and the key;

regenerating the integrity value as a one-way function of the key and the key recovery block;

comparing the regenerated integrity value with the decrypted integrity value; and

decrypting the encrypted data with the key only if the regenerated integrity value compares with the decrypted integrity value.

30. The method of claim 26 in which the receiver performs the steps of:

regenerating the integrity value as a one-way function of the key and the key recovery block;

comparing the regenerated integrity value with the received integrity value; and

decrypting the encrypted data only if the regenerated integrity value compares with the received integrity value.

31. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, along with a key recovery block from which the key is recoverable by a key recovery entity and an integrity value generated as a one-way function of the key and the key recovery block, a method for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising the steps of:

regenerating the integrity value as a one-way function of the key and the key recovery block;

comparing the regenerated integrity value with the received integrity value; and

decrypting the encrypted data only if the regenerated integrity value compares with the received integrity value.

32. The method of claim 31 in which the sender sends the receiver a key exchange block containing an encrypted portion and an unencrypted portion, the encrypted portion containing the key and the integrity value, the unencrypted portion containing the key recovery block, the method further comprising the step of:

decrypting the integrity value and the key in the encrypted portion of the key exchange block.

33. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, apparatus for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising:

means for generating a key recovery block from which a first key is recoverable by a key recovery entity;

means for generating a second key as a one-way function of the first key and the key recovery block; and

means for encrypting the data under the second key to generate encrypted data, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block and regenerating the second key from the first key and the key recovery block.

34. The apparatus of claim 33 further comprising:

means for transmitting the key recovery block and the encrypted data from the sender to the receiver.

35. The apparatus of claim 34 in which the receiver comprises:

means for regenerating the second key from the first key and the key recovery block; and

means for decrypting the encrypted data using the second key.

36. The apparatus of claim 33 in which the means for generating a second key comprises:

means for encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

means for generating the second key as a one-way function of the encrypted key recovery block.

37. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, apparatus for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising:

means for generating a key recovery block from which a first key is recoverable by a key recovery entity;

means for generating a second key independently of the first key;

means for generating a third key as a one-way function of the first key and the key recovery block;

means for combining the first and second keys to obtain a result that can be recombined with the first key to regenerate the second key;

means for encrypting the result under the third key; and

means for encrypting the data under the second key to generate encrypted data, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block, regenerating the third key from the first key and the key recovery block, decrypting the encrypted result using the regenerated third key, and recombining the result with the first key to regenerate the second key.

38. The apparatus of claim 37, further comprising:

means for transmitting the key recovery block, the encrypted result and the encrypted data from the sender to the receiver.

39. The apparatus of claim 38 in which the receiver comprises:

means for regenerating the third key from the first key and the key recovery block;

means for decrypting the encrypted result using the regenerated third key;

means for recombining the decrypted result with the first key to regenerate the second key; and

means for decrypting the encrypted data using the regenerated second key.

40. The apparatus of claim 37 in which the means for generating the third key comprises:

means for encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

means for generating the third key as a one-way function of the encrypted key recovery block.

41. In a cryptographic communication system in which a sender generates a key recovery block from which a first key is recoverable by a key recovery entity, encrypts data under a second key generated as a one-way function of the first key and the key recovery block, and transmits the key recovery block and the encrypted data to a receiver, apparatus for decrypting the encrypted data, comprising:

means for receiving the key recovery block and the encrypted data;

means for regenerating the second key from the first key and the key recovery block; and

means for decrypting the encrypted data using the second key.

42. The apparatus of claim 41 in which the means for regenerating the second key comprises:

means for encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

means for generating the second key as a one-way function of the encrypted key recovery block.

43. In a cryptographic communication system in which a sender generates a key recovery block from which an encryption key is recoverable by a key recovery entity, encrypts data under a second key generated independently of the first key, and transmits the key recovery block and the encrypted data to a receiver, along with a result of combining the first key with the second key that is encrypted under a third key generated as a one-way function of the first key and the key recovery block, apparatus for decrypting the encrypted data, comprising:

means for receiving the key recovery block and the encrypted data;

means for regenerating the third key from the first key and the key recovery block;

means for decrypting the encrypted result using the regenerated third key;

means for recombining the decrypted result with the first key to regenerate the second key; and

means for decrypting the encrypted data using the regenerated second key.

44. The apparatus of claim 43 in which the means for regenerating the third key comprises:

means for encrypting the key recovery block under the first key to generate an encrypted key recovery block; and

means for generating the third key as a one-way function of the encrypted key recovery block.

45. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, apparatus for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, the apparatus comprising:

means for generating a key recovery block from which a key is recoverable by a key recovery entity; and

means for generating an integrity value as a one-way function of the key and the key recovery block, whereby a receiver of the key recovery block and the integrity value may verify the key recovery block without regenerating it by regenerating the integrity value as a one-way function of the key and the key recovery block and comparing the regenerated integrity value with the received integrity value.

46. The apparatus of claim 45, further comprising:

means for encrypting the integrity value and the key to generate an encrypted portion of a key exchange block having an unencrypted portion containing the key recovery block; and

means for encrypting the data under the key to generate encrypted data, whereby a receiver of the key exchange block may verify the key recovery block without regenerating it by decrypting the integrity value and the key, regenerating the integrity value as a one-way function of the key and the key recovery block, and comparing the regenerated integrity value with the decrypted integrity value.

47. The apparatus of claim 46 in which the receiver comprises:

means for decrypting the integrity value and the key;

means for regenerating the integrity value as a one-way function of the key and the key recovery block;

means for comparing the regenerated integrity value with the decrypted integrity value; and

means for decrypting the encrypted data with the key only if the regenerated integrity value compares with the decrypted integrity value.

48. The apparatus of claim 45 in which the receiver comprises:

means for regenerating the integrity value as a one-way function of the key and the key recovery block;

means for comparing the regenerated integrity value with the received integrity value; and

means for decrypting the encrypted data only if the regenerated integrity value compares with the received integrity value.

49. In a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, along with a key recovery block from which the key is recoverable by a key recovery entity and an integrity value generated as a one-way function of the key and the key recovery block, apparatus for ensuring the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity, comprising:

means for regenerating the integrity value as a one-way function of the key and the key recovery block;

means for comparing the regenerated integrity value with the received integrity value; and

means for decrypting the encrypted data only if the regenerated integrity value compares with the received integrity value.

50. The apparatus of claim 49 in which the sender sends the receiver a key exchange block containing an encrypted portion and an unencrypted portion, the encrypted portion containing the key and the integrity value, the unencrypted portion containing the key recovery block, the apparatus further comprising:

means for decrypting the integrity value and the key in the encrypted portion of the key exchange block.

51. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for ensuring the concomitant transmission of data sufficient to permit recovery of an encryption key by a key recovery entity in a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, the method steps comprising:

generating a key recovery block from which a key is recoverable by a key recovery entity; and

generating an integrity value as a one-way function of the key and the key recovery block, whereby a receiver of the key recovery block and the integrity value may verify the key recovery block without regenerating it by regenerating the integrity value as a one-way function of the key and the key recovery block and comparing the regenerated integrity value with the received integrity value.

52. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for ensuring the concomitant transmission of data sufficient to permit recovery of an encryption key by a key recovery entity in a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, along with a key recovery block from which the key is recoverable by a key recovery entity and an integrity value generated as a one-way function of the key and the key recovery block, the method steps comprising:

regenerating the integrity value as a one-way function of the key and the key recovery block;

comparing the regenerated integrity value with the received integrity value; and

decrypting the encrypted data only if the regenerated integrity value compares with the received integrity value.

53. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for ensuring the concomitant transmission of data sufficient to permit recovery of an encryption key by a key recovery entity in a cryptographic communication system in which a sender transmits data encrypted under the encryption key to a receiver, the method steps comprising:

generating a key recovery block from which a first key is recoverable by a key recovery entity;

generating a second key as a one-way function of the first key and the key recovery block; and

encrypting the data under the second key to generate encrypted data, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block and regenerating the second key from the first key and the key recovery block.

54. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for ensuring the concomitant transmission of data sufficient to permit recovery of an encryption key by a key recovery entity in a cryptographic communication system in which a sender transmits data encrypted under the encryption key to a receiver, the method steps comprising:

generating a key recovery block from which a first key is recoverable by a key recovery entity;

generating a second key independently of the first key;

generating a third key as a one-way function of the first key and the key recovery block;

combining the first and second keys to obtain a result that can be recombined with the first key to regenerate the second key;

encrypting the result under the third key; and

encrypting the data under the second key to generate encrypted data, whereby the receiver cannot decrypt the encrypted data without receiving the key recovery block, regenerating the third key from the first key and the key recovery block, decrypting the encrypted result using the regenerated third key, and recombining the result with the first key to regenerate the second key.

55. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for decrypting encrypted data in a cryptographic communication system in which a sender generates a key recovery block from which a first key is recoverable by a key recovery entity, encrypts data under a second key generated as a one-way function of the first key and the key recovery block, and transmits the key recovery block and the encrypted data to a receiver, the method steps comprising:

receiving the key recovery block and the encrypted data;

regenerating the second key from the first key and the key recovery block; and

decrypting the encrypted data using the second key.

56. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for decrypting encrypted data in a cryptographic communication system in which a sender generates a key recovery block from which a first key is recoverable by a key recovery entity, encrypts data under a second key generated independently of the first key, and transmits the key recovery block and the encrypted data to a receiver, along with a result of combining the first key with the second key that is encrypted under a third key generated as a one-way function of the first key and the key recovery block, the method steps comprising:

receiving the key recovery block and the encrypted data;

regenerating the third key from the first key and the key recovery block;

decrypting the encrypted result using the regenerated third key;

recombining the decrypted result with the first key to regenerate the second key; and

decrypting the encrypted data using the regenerated second key.