Secure key exchange with mutual authentication

• US 20030229789A1
• Filed: 06/10/2002
• Published: 12/11/2003
• Est. Priority Date: 06/10/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Ling Tony, Danieli, Damon V., Morais, Dinarte R.
• Granted Patent: US 7,565,537 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/3213 using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

A secure key exchange with mutual authentication allows devices on a network to perform, in a single roundtrip over the network, the exchange. A key exchange initiator packet that does not include a key to be established is sent from an initiating device to another device via a network. The key exchange initiator packet is validated and the other device generates the key without requiring any additional packets to be received from the initiating device in order to generate the key. A key exchange response packet that does not include the key is returned to the initiating device, which validates the key exchange response packet and generates the key without requiring any additional packets to be sent to the other device or received from the other device.

Claims

1. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to:

perform, in a single roundtrip over a network, a key exchange with a device on the network achieving both mutual authentication with the device and perfect forward secrecy.

2. One or more computer readable media as recited in claim 1, wherein the mutual authentication is achieved based on a Kerberos authentication protocol.

3. One or more computer readable media as recited in claim 1, wherein the perfect forward secrecy is achieved based on Diffie-Hellman values included in the single roundtrip over the network.

4. One or more computer readable media as recited in claim 1, wherein the single roundtrip over the network includes a key exchange initiator message, and wherein the instructions, when executed by the one or more processors, cause the one or more processors to verify a digest of the key exchange initiator message to verify that the key exchange initiator message has not been tampered with.

5. One or more computer readable media as recited in claim 4, wherein the instructions, when executed by the one or more processors, further cause the one or more processors to generate the digest of the key exchange initiator message using a keyed hash.

6. One or more computer readable media as recited in claim 1, wherein the single roundtrip over the network includes a key exchange response message, and wherein the instructions, when executed by the one or more processors, cause the one or more processors to verify a digest of the key exchange response message to verify that the key exchange response message has not been tampered with.

7. One or more computer readable media as recited in claim 6, wherein the instructions, when executed by the one or more processors, further cause the one or more processors to generate the digest of the key exchange response message using a keyed hash.

8. One or more computer readable media as recited in claim 1, wherein the single roundtrip over the network includes a key exchange initiator message, and wherein the instructions, when executed by the one or more processors, cause the one or more processors to check whether a timestamp included in the key exchange initiator message is within a threshold amount of time of the current time, and respond to the key exchange initiator message only if the timestamp is within the threshold amount of time of the current time.

9. One or more computer readable media as recited in claim 1, wherein the single roundtrip over the network includes a key exchange initiator message, and wherein the instructions, when executed by the one or more processors, cause the one or more processors to check whether a timestamp included in the key exchange initiator message is newer than a last timestamp received from the device, and respond to the key exchange initiator message only if the timestamp is newer than the last timestamp received from the device.

10. One or more computer readable media as recited in claim 1, wherein the network comprises the Internet.

11. One or more computer readable media as recited in claim 1, wherein the one or more processors are implemented in a game console.

12. One or more computer readable media as recited in claim 1, wherein the plurality of instructions further causes the one or more processors to:

send, to the device, a key exchange initiator packet that does not include the key;

receive, from the device, a key exchange response packet that does not include the key;

validate the key exchange response packet; and

generate, based at least in part on data in the key exchange response packet, the key without requiring any additional packets to be sent to the device or received from the device in order to generate the key.

13. One or more computer readable media as recited in claim 1, wherein the plurality of instructions further causes the one or more processors to:

receive, from the device, a key exchange initiator packet that does not include the key;

validate the key exchange initiator packet;

generate, based at least in part on data in the key exchange initiator packet, the key without requiring any additional packets to be received from the device in order to generate the key; and

send, to the device, a key exchange response packet that does not include the key.

14. A method, implemented in a device, comprising:

communicating, with another device via a single roundtrip over a network, to securely exchange a security key and to mutually authenticate the devices as well as achieve perfect forward secrecy.

15. A method as recited in claim 14, wherein the method is implemented in a game console.

16. A method as recited in claim 14, wherein another device on the network is not able to deduce the key from the single roundtrip over the network.

17. A method, implemented in a game console, of establishing a mutual key for use in communications with a device, the method comprising:

sending, to the device via a network, a key exchange initiator packet that does not include the mutual key;

receiving, from the device via the network, a key exchange response packet that does not include the mutual key;

validating the key exchange response packet; and

generating, based at least in part on data in the key exchange response packet, the mutual key without requiring any additional packets to be sent to the device or received from the device in order to generate the mutual key.

18. A method as recited in claim 17, wherein the key exchange initiator packet allows the device that sends the key exchange response packet to generate the same mutual key without requiring any additional packets to be sent to the device in order to generate the key.

19. A method as recited in claim 17, further comprising generating the key exchange initiator packet by:

generating a key exchange initiator message;

computing a digest of the key exchange initiator message;

generating, based at least in part on the digest, an authenticator;

encrypting the authenticator; and

generating a key exchange initiator packet that includes the key exchange initiator message, the encrypted authenticator, and a security ticket.

20. A method as recited in claim 17, wherein validating the key exchange response packet comprises:

receiving, from the device, a key exchange response packet;

decrypting a reply message included in the key exchange response packet;

checking whether a timestamp in the reply message is the same as a timestamp previously sent to the device;

computing a digest value of a key exchange response message included in the key exchange response packet; and

determining that the key exchange response packet is valid only if the timestamp in the reply message is the same as the timestamp previously sent to the device, and if the computed digest value of the key exchange response packet is the same as a digest value included in the key exchange response packet.

21. A method as recited in claim 17, wherein generating the key comprises:

retrieving, from the key exchange response packet, a Diffie-Hellman value (g^Y mod N);

obtaining a value (X) that was randomly generated earlier;

calculating a Diffie-Hellman value (g^XY mod N); and

generating the key based at least in part on the Diffie-Hellman value (g^XY mod N).

22. A method as recited in claim 17, wherein the key exchange initiator packet and the key exchange response packet allow perfect forward secrecy to be achieved.

23. A method of establishing a key for use in communications with a game console, the method comprising:

receiving, from the game console via a network, a key exchange initiator packet that does not include the key;

validating the key exchange initiator packet;

generating, based at least in part on data in the key exchange initiator packet, the key without requiring any additional packets to be received from the game console in order to generate the key; and

sending, to the game console via the network, a key exchange response packet that does not include the key.

24. A method as recited in claim 23, wherein the key exchange response packet includes information that allows the game console to generate the key without requiring any additional packets to be sent to the game console in order to generate the key.

25. A method as recited in claim 23, wherein validating the key exchange initiator packet comprises:

decrypting a security ticket in the key exchange initiator packet;

decrypting an authenticator in the key exchange initiator packet;

computing a digest of a key exchange message in the key exchange initiator packet; and

determining that the key exchange initiator packet is valid only if all of the following conditions are satisfied;

the security ticket is not stale,

a timestamp in the authenticator is acceptable,

the computed digest of the key exchange message is equal to a digest value included as part of the authenticator, and

the authenticator has not been replayed.

26. A method as recited in claim 23, further comprising generating the key exchange response packet by:

generating a key exchange response message;

computing a digest of the key exchange response message;

generating a reply message;

encrypting the reply message; and

generating a key exchange response packet including both the key exchange response message and the encrypted reply message.

27. A method as recited in claim 23, wherein generating the key comprises:

retrieving, from the key exchange initiator packet, a Diffie-Hellman value (g^X mod N);

generating a random Diffie-Hellman value (Y);

including g^Y mod N as part of the key exchange response;

calculating a Diffie-Hellman value (g^XY mod N); and

generating the key based at least in part on the Diffie-Hellman value (g^XY mod N).

28. A method as recited in claim 23, wherein the key exchange initiator packet and the key exchange response packet allow perfect forward secrecy to be achieved.

29. A method, implemented in a game console to initiate establishing a key to be used in subsequent secure communications between the game console and a server device, the method comprising:

generating a key exchange initiator message;

computing a digest of the key exchange initiator message;

generating, based at least in part on the digest, an authenticator;

encrypting the authenticator;

generating a key exchange initiator packet that includes the key exchange initiator message, the encrypted authenticator, and a security ticket; and

sending the key exchange initiator packet to the server device.

30. A method as recited in claim 29, wherein generating the key exchange initiator message comprises:

generating a first value NonceInit;

generating a second value X;

using the second value X to generate a Diffie-Hellman value (g^X mod N); and

including, in the key exchange initiator message, the first value NonceInit and the Diffie-Hellman value (g^X mod N).

31. A method as recited in claim 29, wherein computing the digest of the key exchange initiator message comprises:

using a Kerberos session key K_CA, previously received from a key distribution center, and a hashing function to compute the digest.

32. A method as recited in claim 29, wherein generating the authenticator comprises:

generating a current timestamp; and

including, in the authenticator, the current timestamp and the digest of the key exchange initiator message.

33. A method as recited in claim 29, wherein encrypting the authenticator comprises encrypting the authenticator based at least in part on a Kerberos session key K_CA, previously received from a key distribution center.

34. A method as recited in claim 29, wherein generating the key exchange initiator packet comprises including, in the key exchange initiator packet, the following:

the key exchange initiator message;

a predetermined Security Parameters Index (SPI) value to indicate that establishment of a new security association is being initiated;

the encrypted authenticator; and

the security ticket.

35. A method as recited in claim 29, wherein the security ticket comprises a Kerberos ticket.

36. A method as recited in claim 29, wherein the key exchange initiator packet allows perfect forward secrecy to be achieved.

37. A method, implemented in a server device establishing a key to be used in subsequent secure communications between the server device and a game console, the method comprising:

receiving, from the game console, a key exchange initiator packet;

decrypting a security ticket in the key exchange initiator packet;

decrypting an authenticator in the key exchange initiator packet;

computing a digest of a key exchange message in the key exchange initiator packet; and

determining that the key exchange initiator packet is valid only if all of the following conditions are satisfied;

the security ticket is not stale,

a timestamp in the authenticator is acceptable,

the computed digest of the key exchange message is equal to a digest value included as part of the authenticator, and

the authenticator has not been replayed.

38. A method as recited in claim 37, wherein decrypting the security ticket comprises:

decrypting the security ticket using a key shared by the server device and a key distribution center that gave the security ticket to the game console.

39. A method as recited in claim 37, further comprising determining the security ticket is stale if a current time is not included in a range of times identified in the security ticket.

40. A method as recited in claim 37, further comprising determining the timestamp in the authenticator is acceptable if the timestamp is within a threshold amount of time of a current time.

41. A method as recited in claim 37, further comprising determining that the authenticator has been replayed if the timestamp is not newer than a last timestamp received by the server device from the game console.

42. A method as recited in claim 37, further comprising:

retrieving, from the key exchange initiator packet, a Diffie-Hellman value (g^X mod N);

generating a random value (Y);

sending a Diffie-Hellman value (g^Y mod N) in a response to the key exchange initiator packet;

calculating a Diffie-Hellman value (g^XY mod N); and

generating the key based at least in part on the Diffie-Hellman value (g^XY mod N).

43. A method as recited in claim 37, wherein the key exchange initiator packet allows perfect forward secrecy to be achieved.

44. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a server device in establishing a key to be used in subsequent secure communications between the server device and a game console, causes the one or more processors to:

receive a key exchange initiator packet;

decrypt a security ticket in the key exchange initiator packet;

check whether a current time is within a range of times identified in the security ticket, and indicate the key cannot be established if the current time is not within the range of times identified in the security ticket;

decrypt an authenticator in the key exchange initiator packet;

check whether a timestamp in the authenticator is within a threshold amount of time of the current time, and indicate the key cannot be established if the timestamp is not within the threshold amount of time of the current time;

compute a digest value of a key exchange message in the key exchange initiator packet; and

check whether the computed digest value is equal to a digest value included as part of the authenticator, and indicate that the key cannot be established if the computed digest value is not equal to the digest value included as part of the authenticator.

45. One or more computer readable media as recited in claim 44, wherein the instructions further cause the one or more processors to:

check whether the timestamp is newer than a last timestamp received by the server device from the game console, and indicate that the key cannot be established if the timestamp is not newer than the last timestamp.

46. One or more computer readable media as recited in claim 44, wherein the instructions further cause the one or more processors to:

retrieve, from the key exchange initiator packet, a Diffie-Hellman value (g^X mod N);

generate a random value (Y);

send a Diffie-Hellman value (g^Y mod N) as part of a response to the key exchange initiator packet;

calculate a Diffie-Hellman value (g^XY mod N); and

generate the key based at least in part on the Diffie-Hellman value (g^XY mod N).

47. One or more computer readable media as recited in claim 44, wherein the key exchange initiator packet allows perfect forward secrecy to be achieved.

48. A method, implemented in a server device establishing a key to be used in subsequent secure communications between the server device and a game console, the method comprising:

generating a key exchange response message;

computing a digest of the key exchange response message;

generating a reply message;

encrypting the reply message;

generating a key exchange response packet including both the key exchange response message and the encrypted reply message; and

sending the key exchange response packet to the game console.

49. A method as recited in claim 48, wherein generating the key exchange response message comprises:

generating a first value NonceResp;

generating a second value Y;

using the second value Y to generate a Diffie-Hellman value (g^Y mod N); and

including, in the key exchange response message, the following;

a NonceInit value previously received from the game console,

the first value NonceResp,

the Diffie-Hellman value (g^Y mod N), and

a timestamp value previously received from the game console.

50. A method as recited in claim 48, wherein computing the digest of the key exchange response message comprises:

using a Kerberos session key K_CA, previously received from the game console as part of a Kerberos ticket, and a hashing function to compute the digest.

51. A method as recited in claim 48, wherein generating the reply message comprises including, in the reply message, both a timestamp previously received from the game console and the digest of the key exchange response message.

52. A method as recited in claim 48, wherein encrypting the reply message comprises encrypting the reply message based at least in part on a Kerberos session key K_CA, previously received from the game console as part of a Kerberos ticket).

53. A method as recited in claim 48, wherein generating the key exchange response packet comprises including, in the key exchange response packet, the following:

the key exchange response message;

the encrypted reply message; and

a Security Parameters Index (SPI) value used to identify the subsequent secure communications from the server device to the game console.

54. A method as recited in claim 48, wherein the key exchange response packet allows perfect forward secrecy to be achieved.

55. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors in establishing a key to be used in subsequent secure communications between the server device and a game console, causes the one or more processors to:

generate a key exchange response message;

compute a digest of the key exchange response message;

generate a reply message that includes the digest and a timestamp previously received from the game console;

encrypt the reply message;

generate a key exchange response packet including both the key exchange response message and the encrypted reply message; and

send the key exchange response packet to the game console.

56. A method as recited in claim 55, wherein the instructions that cause the one or more processors to compute the digest of the key exchange response message include instructions that cause the one or more processors to compute, based at least in part on a Kerberos session key, the digest of the key exchange response message.

57. A method as recited in claim 55, wherein the instructions that cause the one or more processors to generate the key exchange response message comprise instructions that cause the one or more processors to:

generate a first value NonceResp;

generate a second value Y;

use the second value Y to generate a Diffie-Hellman value (g^Y mod N); and

include, in the key exchange response message, the following;

a NonceInit value previously received from the game console,

the first value NonceResp,

the Diffie-Hellman value (g^Y mod N), and

the timestamp value.

58. A method as recited in claim 55, wherein the instructions that cause the one or more processors to encrypt the reply message comprise instructions that cause the one or more processors to encrypt the reply message based at least in part on the Kerberos session key.

59. A method as recited in claim 55, wherein the instructions that cause the one or more processors to generate the key exchange response packet comprise instructions that cause the one or more processors to include, in the key exchange response packet, the following:

the key exchange response message;

the encrypted reply message; and

a Security Parameters Index (SPI) value used to identify the subsequent secure communications from the server device to the game console.

60. One or more computer readable media as recited in claim 55, wherein the key exchange response packet allows perfect forward secrecy to be achieved.

61. A method, implemented in a game console establishing a key to be used in subsequent secure communications between the game console and a server device, the method comprising:

receiving, from the server device, a key exchange response packet;

decrypting a reply message included in the key exchange response packet;

checking whether a timestamp in the reply message is the same as a timestamp previously sent by the game console to the server device;

computing a digest value of a key exchange response message included in the key exchange response packet; and

determining that the key exchange response packet is valid only if the timestamp in the reply message is the same as the timestamp previously sent by the game console to the server device, and if the computed digest value of the key exchange response packet is the same as a digest value included in the key exchange response packet.

62. A method as recited in claim 61, wherein decrypting the reply message comprises decrypting the reply message using a Kerberos session key previously obtained by the game console from a key distribution center.

63. A method as recited in claim 61, further comprising:

retrieving, from the key exchange response packet, a Diffie-Hellman value (g^Y mod N);

using a previously generated value (X), calculating a Diffie-Hellman value (g^XY mod N); and

generating the key based at least in part on the Diffie-Hellman value (g^XY mod N).

64. A method as recited in claim 61, wherein the key exchange response packet allows perfect forward secrecy to be achieved.

65. A system comprising:

a client device configured to obtain a session key from a key distribution center; and

a server device, coupled to the client device via a network, configured to communicate with the client device and, in a single roundtrip over the network, securely exchange a key and mutually authenticate one another as well as achieve perfect forward secrecy.

66. A system as recited in claim 65, wherein the client device comprises a game console.

67. A system as recited in claim 65, wherein the server device comprises a data center security gateway.

68. A system as recited in claim 65, wherein the client device is further configured to:

send, to the server device, a key exchange initiator packet that does not include the key;

receive, from the server device, a key exchange response packet that does not include the key;

validate the key exchange response packet; and

generate, based at least in part on data in the key exchange response packet, the key without requiring any additional packets to be sent to the server device or received from the server device in order to generate the key.

69. A system as recited in claim 65, wherein the server device is further configured to:

receive, from the client device, a key exchange initiator packet that does not include the key;

validate the key exchange initiator packet;

generate, based at least in part on data in the key exchange initiator packet, the key without requiring any additional packets to be received from the client device in order to generate the key; and

send, to the client device, a key exchange response packet that does not include the key.