Method and apparatus for establishing an authenticated shared secret value between a pair of users

• US 5,953,420 A
• Filed: 10/25/1996
• Issued: 09/14/1999
• Est. Priority Date: 10/25/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Matyas, Stephen Michael Jr., Johnson, Donald Byron
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/736,774
• Time in Patent Office: 1,054 Days
• Field of Search: 380/9, 380/21, 380/30, 380/49, 380/50, 380/59, 380/23, 380/25, 380/44, 380/46
• US Class Current: 713/171
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys

Abstract

A method and apparatus for generating authenticated Diffie-Hellman keys. Each user first generates an authenticated first shared secret value from a first nonshared persistent secret value generated by that user and an authenticated first transformed value received from the other user over a trusted communications channel. Each user then dynamically generates a second shared secret value from a second nonshared secret value dynamically generated by that user and a dynamically generated second transformed value received from the other user. Each user thereafter generates one or more keys by concatenating the first and second shared secret values together with a count to form a concatenated value and passing the concatenated value through a one-way hash function to generate a hash value from which the keys are extracted. Since only the legitimate users possess the information necessary to construct the first shared secret value, a spoofer interacting with a user to generate a second shared secret value cannot generate the same key. Incrementing the count for successive hashes allows a multiplicity of keys to be generated from a given pair of shared secret values.

Claims

1. In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user'"'"'s own nonshared secret value and the transformed value received from the other user, a method of establishing for one of said users a new shared secret value with the other of said users, comprising the steps of:

generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value and being authenticated as having originated from said other of said users;

generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value and not being authenticated as having originated from said other of said users; and

generating said new shared secret value as a function of said first shared secret value and said second shared secret value.

2. The method of claim 1 wherein said users are located at nodes coupled by a communications channel.

3. The method of claim 1 wherein each of said users performs said steps.

4. The method of claim 1 wherein each of said steps of generating a shared secret value comprises the steps of:

generating a transformed value by transforming in a manner infeasible to invert, using said common transformation a nonshared secret value generated by said one of said users;

transmitting said transformed value to the other of said users;

receiving a transformed value generated by the other of said users using said common transformation; and

generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the transformed values exchanged between said users.

5. The method of claim 4 wherein said transformed value is generated by said one of said users as

6. The method of claim 5 wherein said shared secret value is generated by said one of said users as

7. The method of claim 1 wherein said step of generating said new shared secret value comprises the steps of:

combining said first and second shared secret values to generate a combined value; and

generating said new shared secret value as a one-way function of said combined value.

8. The method of claim 7 wherein said first and second values are also combined with a count to generate said combined value.

9. The method of claim 1 wherein said first shared secret value is a relatively long-term value and said second shared secret value is a relatively short-term value.

10. The method of claim 1 wherein said first transformed value is received from said other of said users over a trusted communications channel.

13. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 1, claim 11 or claim 12.

11. In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user'"'"'s own nonshared secret value and the transformed value received from the other user, a method of establishing for one of said users a new shared secret value with the other of said users, comprising the steps of:

generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value;

generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value;

concatenating said first and second shared secret values to generate a concatenated value; and

generating said new authenticated shared secret value as a one-way function of said concatenated value.

12. A method of establishing for one of a pair of users a cryptographic key that is shared with the other of said pair of users, comprising the steps of:

generating a transformed value by transforming in a manner infeasible to invert, using a common transformation, a nonshared secret value generated by said one of said users, each of said users having its own nonshared secret value;

transmitting said transformed value to the other of said users;

receiving a transformed value generated by the other of said users from its own nonshared secret value using said common transformation;

generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the first transformed values exchanged between said users;

concatenating said shared secret value and a value available to the other user to generate a concatenation value; and

generating said key as a one-way function of said concatenation value.

14. The method of claim 12 in which said value available to the other user is a successively incremented count.

15. The method of claim 12 wherein said step of generating said key comprises the step of generating each of a plurality of different keys as a one-way function of said shared secret value and a value available to the other user that is unique to that key.

16. The method of claim 12 wherein said users are located at nodes coupled by a communications channel.

17. The method of claim 12 wherein each of said users performs said steps.

18. In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user'"'"'s own nonshared secret value and the transformed value received from the other user, apparatus for establishing for one of said users a new shared secret value with the other of said users, comprising:

means for generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value and being authenticated as having originated from said other of said users;

means for generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value and not being authenticated as having originated from said other of said users; and

means for generating said new authenticated shared secret value as a function of said first shared secret value and said second shared secret value.

19. The apparatus of claim 18 wherein each of said means for generating a shared secret value comprises:

means for generating a transformed value by transforming in a manner infeasible to invert, using said common transformation, a nonshared secret value generated by said one of said users;

means for transmitting said transformed value to the other of said users;

means for receiving a transformed value generated by the other of said users using said common transformation; and

means for generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the transformed values exchanged between said users.

20. The apparatus of claim 18 wherein said means for generating said new shared secret value comprises:

means for combining said first and second shared secret values to generate a combined value; and

means for generating said new shared secret value as a one-way function of said combined value.

21. In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user'"'"'s own nonshared secret value and the transformed value received from the other user, apparatus for establishing for one of said users a new shared secret value with the other of said users, comprising:

means for generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value;

means for generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value;

means for concatenating said first and second shared secret values to generate a concatenated value; and

means for generating said new authenticated shared secret value as a one-way function of said concatenated value.

22. Apparatus for establishing for one of a pair of users a cryptographic key that is shared with the other of said pair of users, comprising:

means for generating a transformed value by transforming in a manner infeasible to invert, using a common transformation, a nonshared secret value generated by said one of said users, each of said users having its own nonshared secret value;

means for transmitting said transformed value to the other of said users;

means for receiving a transformed value generated by the other of said users from its own nonshared secret value using said common transformation;

means for generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the first transformed values exchanged between said users;

means for concatenating said shared secret value and a value available to the other user to generate a concatenation value; and

means for generating said key as a one-way function of said concatenation value.

23. The apparatus of claim 22 in which said value available to the other user is a successively incremented count.

24. The apparatus of claim 22, wherein said means for generating said key generates each of a plurality of different keys as a one-way function of said shared secret value and a value available to the other user that is unique to that key.