Extended authenticated key exchange

• US 7,627,760 B2
• Filed: 07/21/2005
• Issued: 12/01/2009
• Est. Priority Date: 07/21/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mityagin, Anton, Lauter, Kristin E.
• Primary Examiner(s): Colin; Carl
• Assistant Examiner(s): SONG, HEE K
• Application Number:
  US11/186,251
• Publication Number:
  US 20070033403A1
• Time in Patent Office: 1,594 Days
• Field of Search: 713/171, 380/44
• US Class Current: 713/171
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes

Abstract

Extended authenticated key exchange is described. In one aspect, an identity (ID_A) of an initiator and an identity (ID_B) of a responder are determined. A first party (i.e., the initiator or the responder) computes a session key based at least on ID_A and ID_B. A second party (i.e., the initiator or the responder) that is not the first party, uses at least ID_A and ID_B to compute a corresponding session key. The initiator'"'"'s session key and the responder'"'"'s corresponding session key, if equal, provide for secure exchange of data between the initiator and the responder.

Claims

1. A computer-implemented method for extended authenticated key exchange using a mathematical group, via operations comprising:

initiating operations to execute extended authenticated key exchange between an initiator computing device and a responder computing device connected via a network;

generating setup parameters on a computing device, the setup parameters comprising;

a first fixed prime number,

a second fixed prime number that is a divisor of the first fixed prime number minus 1,

a key group from 1 to the second fixed prime number minus 1;

an element from the 1 to the first fixed prime number minus 1, which has order of the second fixed prime number,

an initiator long-term secret key selected from the key group,

an initiator public key, in the mathematical group based on the initiator long-term secret key, wherein the initiator public key is registered with a public certificate authority;

a responder long-term secret selected from the key group, and;

a responder public key, in the mathematical group based on the responder long-term secret, wherein the responder public key is registered with public certificate authority;

determining an initiator identity, wherein the initiator identity comprises a binary string based on context information of the initiator;

determining a responder identity, wherein the responder identity comprises a binary string based on context information of the responder;

the initiator generating an initiator ephemeral public key in the mathematical group based on an initiator ephemeral secret key, randomly selected from the key group, and sending the initiator ephemeral public key to the responder;

the responder generating a responder ephemeral public key in the mathematical group based on a responder ephemeral secret randomly selected from the key group, and sending the responder ephemeral public key to the initiator;

computing, a session key for the initiator and a corresponding session key for the responder, by hashing the concatenation of a first computed value, a second computed value, the initiator identity, and the responder identity such that;

by the initiator, for the session key the first value is computed in the mathematical group based on the responder ephemeral public key and the initiator long-term secret key, and the second value is computed in the mathematical group based on the responder public key and the initiator ephemeral secret key;

by the responder, for the corresponding session key the first value is computed in the mathematical group based on the initiator public key and the responder ephemeral secret key, and the second value is computed in the mathematical group based on the initiator ephemeral public key and the responder long-term secret key; and

the session key and the corresponding session key, if equal, providing for secure exchange of data between the initiator and the responder.

2. A method as recited in claim 1, wherein the mathematical group is a subgroup of a multiplicative group of natural numbers modulo the first fixed prime number.

3. A method as recited in claim 1, wherein the mathematical group is a subgroup of the group of points on an elliptic curve of prime order.

4. A method as recited in claim 1, wherein operations to compute the session key and the corresponding session key comprise modular exponentiation.

5. A method as recited in claim 1, wherein operations to compute the session key and the corresponding session key comprise scalar multiplication in elliptic curve groups.

6. A method as recited in claim 1, the operations further comprise:

verifying that the initiator ephemeral public key is valid, by raising the public key to the power of the second fixed prime number, and determining that result is the identity element of the group 1 modulo the first prime number.

7. A method as recited in claim 1, wherein computing the session key further comprises computing the session key based on a session identifier, and wherein the session identifier is for use by the responder to determine the corresponding session key.

8. A computer-implemented method for extended authenticated key exchange using a mathematical group via operations comprising:

registering, by an initiator computing device, an initiator identity (ID_A) with a certificate authority wherein ID_A comprises a binary string based on context information providing identification indicia of the initiator;

registering, by a responder computing device, an identity (ID_B) of the responder with the certificate authority, wherein ID_B comprises a binary string based on context information providing identification indicia of the responder;

computing, by the initiator computing device and the responder computing device, a respective session key based on hashing a concatenation of at least a first value in the mathematical group, a second value in the mathematical group, ID_A and ID_B, wherein;

by the initiator, the first value is determined based upon an ephemeral public key of the responder and a long-term secret key of the initiator, and the second value, is determined based upon a public key of the responder and an ephemeral secret key x of the initiator; and

by the responder, the first value is determined based upon an initiator public key and a responder ephemeral secret key, and the second value is determined based upon an initiator ephemeral public key, and a responder long-term secret key; and

wherein the respective session keys, if equal, provide for secure exchange of data between the initiator computing device and the responder computing device.

9. A method as recited in claim 8, wherein the mathematical group is a subgroup of a multiplicative group of natural numbers modulo a prime number.

10. A method as recited in claim 8, wherein the mathematical group is a subgroup of the group of points on an elliptic curve.

11. A method as recited in claim 8, wherein operations to compute the respective session keys comprise modular exponentiation.

12. A method as recited in claim 8, wherein operations to compute the respective session keys comprise scalar multiplication in an elliptic curve group.

13. A method as recited in claim 8, wherein computing the respective session keys further comprises computing the respective session key based on a session identifier.

14. A computing device for extended authenticated key exchange using a mathematical group, the computing device comprising:

communication means for communicating between an initiator and a responder;

generating means for generating setup parameters, the setup parameters comprising;

a first fixed prime number;

a second fixed prime number that is a divisor of the first prime number minus 1;

an initiator identity or a responder identity, wherein the respective identities are arbitrary binary strings based on context information of the respective initiator and responder;

an initiator long-term secret key or a responder long-term secret key, wherein the respective long-term secret keys are selected from the group 1 to the second fixed prime number minus 1,

an initiator public key in the mathematical group based on an initiator long-term secret key, or a responder public key in the mathematical group based on the responder long-term secret key;

an initiator ephemeral secret key or a responder ephemeral secret key, wherein the respective ephemeral secret keys are randomly selected from the group 1 to the second fixed prime number minus 1;

determining means for determining an initiator identity and a responder identity, wherein the initiator identity and the responder identity comprise a binary string based on context information of the respective initiator and responder;

generating means for generating an initiator ephemeral public key in the mathematical group based on the initiator ephemeral secret key and for generating a responder ephemeral public key in the mathematical group based on the responder ephemeral secret key;

sending means for sending the initiator ephemeral public key to the responder and the responder ephemeral public key to the initiator;

validating means for confirming the initiator ephemeral public key or the responder ephemeral public key is valid and terminating extended authenticated key exchange if either the initiator ephemeral public key or the responder ephemeral public key is invalid;

computing means for computing;

a session key or a corresponding session key based on hashing the concatenation of at least a first value in the mathematical group, a second value in the mathematical group, the initiator identity, and the responder identity wherein;

for the initiator the first value is determined based upon the responder'"'"'s ephemeral public key and the initiator'"'"'s long-term secret key, and the second value, is determined based upon the responder public key and the initiator ephemeral secret key; and

for the responder, the first value, is determined based upon the initiator public key and the responder ephemeral secret key, and the second value, is determined based upon the ephemeral public key of the initiator, and the long-term secret key of the responder; and

determining means to determine whether the session key and the corresponding session key are equal providing for secure exchange of data between the initiator and the responder.

15. A computing device as recited in claim 14, wherein the mathematical group is a subgroup of a multiplicative group of natural numbers modulo a prime number.

16. A computing device as recited in claim 14, wherein the mathematical group is a subgroup of the group of points on an elliptic curve.

17. A computing device as recited in claim 14, wherein means to compute the session key and the corresponding session key comprise modular exponentiation.

18. A computing device as recited in claim 14, wherein means to compute the session key and the corresponding session key comprise scalar multiplication in elliptic curve groups.

19. A computing device as recited in claim 14, wherein the computing means to compute the session key further comprises computing means to compute the session key based on a session identifier, and

wherein the session identifier is for use by the responder to determine the corresponding session key.

20. A computer-implemented method for extended authenticated key exchange between an initiator and a responder using a mathematical group, via operations comprising:

generating, via a computing device, setup parameters, the setup parameters comprising;

p, a fixed prime number;

q, a fixed prime number that is a divisor of p−

1;

g, an element from 1 . . . p−

1, which has order q;

a, an initiator long-term secret key selected from the group 1 . . . q−

1;

A, a registered public key of the initiator, wherein A=g^a;

b, a responder long-term secret selected from the group 1 . . . q−

1; and

B, a registered public key of the responder, wherein B=g^b;

determining, via the computing device, an initiator identity (ID_A) and an responder identity (ID_B), wherein ID_A comprises a binary string based on context information of the initiator, and ID_B comprises a binary string based on context information of the responder;

the initiator generating, via the computing device, an initiator ephemeral public key X in the mathematical group based on an initiator ephemeral secret key x, randomly

selected from 1 . . . p−

1, wherein X=g^x mod p, and sending the initiator ephemeral public key X to the responder;

the responder generating, via the computing device, a responder ephemeral public key Y in the mathematical group based on a responder ephemeral secret y, randomly selected from the multiplicative group [1 . . . q−

1], wherein Y=g^y mod p, and sending the responder ephemeral public key Y to the initiator;

computing, via the computing device, a session key and a corresponding session key, based at least on a first value Z₁, a second value Z₂, ID_A and ID_B, by hashing the concatenation of Z₁, Z₂, ID_A and ID_B, such that;

by the initiator, for the session key, the first value Z₁ is computed from the responder ephemeral public key Y and the initiator'"'"'s long-term secret key a;

wherein Z₁=Y^a mod p, and the second value Z₂ is computed from the responder'"'"'s public key B and the initiator ephemeral secret key x;

wherein Z₂=B^x mod p; and

by the responder, for the corresponding session key, the first value Z₁ is computed from the initiator public key and the responder ephemeral secret key y, wherein Z₁=A^y mod p, and the

second value Z₂ is computed from the initiator ephemeral public key X and the responder long-term secret key b, wherein Z₂₌X^b mod p; and

via the computing device, the session key and the corresponding session key, if equal, providing for secure exchange of data between the initiator and the responder.