Method of bilateral identity authentication

• US 6,769,060 B1
• Filed: 10/25/2000
• Issued: 07/27/2004
• Est. Priority Date: 10/25/2000
• Status: Expired due to Term

• Current Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Dent, Paul W., Rydbeck, Nils
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/695,964
• Time in Patent Office: 1,371 Days
• Field of Search: 713/182-186, 713/200-202, 716/8-1-4
• US Class Current: 713/168
• 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
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method for bilateral identity authentication over a communication channel provides a secure method for authenticating the identity of the communicating parties and establishing a secret key. Each party computes an authentication challenge based on an exchanged value used in a key generation procedure. The authentication challenge is encrypted to the other party'"'"'s public key. After receiving an encrypted authentication channel from the other party, each party deciphers the authentication challenge and generates an authentication response based on the authentication challenge. The authentication response includes bits that the challenging party cannot predict in advance to prevent fraudulent use of the authentication response by the challenging party or some other third party. After receiving an authentication response from the other party, each party verifies that the expected authentication response was received.

Claims

1. A method for authenticating two parties and establishing a session key for enciphering communications between said two parties, said method comprising:

generating a first authentication challenge by said first party based on a first exchanged value;

enciphering said first authentication challenge by said first party to obtain a first enciphered authentication challenge;

transmitting said first enciphered authentication challenge from said first party to said second party;

deciphering said first enciphered authentication challenge by said second party and recovering said first exchanged value;

generating a second authentication challenge by said second party based on a second exchanged value;

computing a session key by said second party based on said first and second exchanged values;

re-enciphering said first authentication challenge with said session key by said second party to obtain a first authentication response;

forming a first authentication response message by said second party, said first authentication response message comprising at least said first authentication response and said second authentication challenge;

enciphering said first authentication response message by said second party such that only said first party can decipher said first authentication response message;

transmitting said first authentication response message from said second party to said first party;

deciphering said enciphered authentication response message by said first party to obtain said first authentication response and said second authentication challenge;

determining said second exchange value by said first party;

computing said session key by said first party using said first and second exchanged values; and

deciphering said first authentication response by said first party using said session key to authenticate said second party to said first party.

2. The method of claim 1 wherein generating said first authentication challenge by said first party based on a first exchanged value comprises raising a first prime number to a first random power and reducing the result modulo a second prime number to generate said first exchanged value.

3. The method of claim 2 wherein generating said first authentication challenge by said first party based on a first exchanged value comprises generating said first authentication challenge comprising at least said first exchanged value.

4. The method of claim 2 wherein generating said second authentication challenge by said second party based on said second exchanged value comprises raising said first prime number to a second random power and reducing the result modulo said second prime number to generate said second exchanged value.

5. The method of claim 4 wherein generating said second authentication challenge by said second party based on a second exchanged value comprises generating said second authentication challenge comprising at least said second exchanged value.

6. The method of claim 4 wherein computing said session key by said first party based on said first and second exchanged values comprises raising said second exchanged value to said first random power and reducing the result modulo said second prime number, and wherein computing said session key by said second party based on said first and second exchanged values comprises raising said first exchanged value to said second random power and reducing the result modulo said second prime number.

7. The method of claim 1 wherein enciphering said first authentication challenge by said first party to obtain a first enciphered authentication challenge comprises enciphering said first authentication challenge using a public key ciphering algorithm and a public key of said second party.

8. The method of claim 1 wherein enciphering said first authentication response message by said second party comprises enciphering said first authentication response message using a public key ciphering algorithm and a public key of said first party.

9. The method of claim 1 further comprising:

enciphering said second authentication challenge by said first party using said session key to form a second authentication response;

transmitting said second authentication response from said first party to said second party;

deciphering said second authentication response by said second party using said session key to authenticate said first party.

10. The method of claim 9 further comprising enciphering said second authentication response by said first party to obtain an enciphered second authentication response.

11. The method of claim 10 wherein enciphering said second authentication response by said first party to obtain an enciphered second authentication response comprises enciphering said second authentication response using a public key cipher algorithm and a public key of said second party.

12. The method of claim 11 further comprising deciphering by said second party said enciphered second authentication response using said public key.

13. The method of claim 1 wherein computing a session key by said first party and by said second party based on said first and second exchanged values comprises:

computing a first value;

computing a second key value using a symmetric function; and

combining said first and second key values.

14. The method of claim 13 wherein combining said first and second key values comprises adding said first and second key values.

15. A method of establishing a session key used to encipher communications between a first party and a second party, said method comprising:

generating a first exchanged value by said first party;

generating a first message containing said first exchanged value by said first party;

enciphering said first message by said first party;

transmitting said enciphered first message from said first party to said second party;

deciphering said first message by said second party to recover said first exchanged value;

generating a second exchanged value by a second party;

generating a second message containing said second exchanged value by said second party;

enciphering said second message by said second party;

transmitting said enciphered second message from said second party to said first party;

deciphering said enciphered second message by said first party to recover said second exchanged value;

computing a first key value by said first and second parties;

computing a second key value by said first and second parties using a symmetrical function with interchangeable arguments, wherein said first and second exchanged values are used as said arguments to compute said second key value; and

combining said first and second key values by said first and second parties to obtain said session key.

16. The method of claim 15 wherein computing a second key value by said first and second parties comprises computing a product of said first and second exchanged values.

17. The method of claim 16 wherein computing a second key value by said first and second parties further comprises reducing said product modulo a prime number to obtain said second key value.

18. The method of claim 15 wherein computing a second key value by said first and second parties comprises computing the sum of the first exchanged value raised to the power of the second exchanged value and the second exchanged value raised to the power of the first exchanged value reduced modulo a prime number.

19. The method of claim 18 wherein generating a first exchanged value by said first party comprises raising a first prime number to a first random power modulo a second prime number, and wherein generating a second exchanged value by said second party comprises raising said first prime number to a second random power modulo said second prime number.

20. The method of claim 19 wherein computing a first key value by said first and second parties comprises raising said first and second exchanged values respectively to the power of a first prime number and reducing the result modulo a second prime number.

21. The method of claim 20 wherein combining said first and second key values by said first and second parties to obtain said session key comprises adding said first and second key values.

22. A method of establishing a session key used for enciphering communications between a first party and a second party and for authenticating the identities of said first and second parties, said method comprising:

generating a first authentication challenge by said first party based on a first exchanged value;

enciphering said first authentication challenge by said first party to a secret key used by said second party;

transmitting said enciphered first authentication challenge from said first party to said second party;

deciphering said enciphered first authentication challenge by said second party;

determining said first exchanged value by said second party;

generating a second authentication challenge by said second party based on a second exchanged value;

computing said session key by said second party based on said first and second exchanged value;

generating a first authentication response by said second party based on said first authentication challenge, wherein said first authentication response contains one or more unpredictable bits;

transmitting said first authentication response to said first party;

enciphering said second authentication challenge by said second party to a secret key used by said first party;

transmitting said enciphered authentication challenge from said second party to said first party;

receiving said first authentication response and said enciphered second authentication challenge by said first party;

deciphering said enciphered second authentication challenge by said first party using said secret key;

determining said second exchanged value by said first party;

computing said session key by said first party based on said first and second exchanged values; and

authenticating said second party by said first party based on said first authentication response.

23. The method of claim 22 wherein generating said first authentication challenge by said first party based on a first exchanged value comprises raising a first prime number to a first random power and reducing the result modulo a second prime number to generate said first exchanged value.

24. The method of claim 23 wherein generating said first authentication challenge by said first party based on a first exchanged value comprises generating a first authentication challenge containing at least said first exchanged value.

25. The method of claim 23 wherein generating said second authentication challenge by said second party based on said second exchanged value comprises raising said first prime number to a second random power and reducing the result modulo said second prime number to generate said second exchanged value.

26. The method of claim 25 wherein generating said second authentication challenge by said second party based on a second exchanged value comprises generating a second authentication challenge containing at least said second exchanged value.

27. The method of claim 25 wherein computing said session key by said first and second parties based on said first and second exchanged values comprises raising said second and first exchanged values to said first and second random powers respectively and reducing the result modulo said second prime number.

28. The method of claim 22 wherein enciphering said first authentication challenge by said first party to a secret key used by said second party comprises enciphering said first authentication challenge using a public key ciphering algorithm and a public key of said second party.

29. The method of claim 22 wherein enciphering said second authentication challenge by said second party to a secret key used by said first party comprises enciphering said second authentication challenge using a public key ciphering algorithm and a public key of said first party.

30. The method of claim 22 further comprising

generating a second authentication response by said first party based on said second authentication challenge;

transmitting said second authentication response from said first party to said second party;

receiving said second authentication response by said second party; and

authenticating said first party by said second party based on said second authentication response.

31. The method of claim 30 wherein transmitting said second authentication response from said first party to said second party comprises enciphering said second authentication response by said first party to obtain an enciphered second authentication response and wherein receiving said second authentication response by said second party comprises deciphering the enciphered second authentication response by said second party.

32. The method of claim 30 wherein authenticating said first party by said second party based on said second authentication response comprises:

computing an expected authentication response by said second party; and

comparing said second authentication response with said expected authentication response to authenticate said first party.

33. The method of claim 22 wherein generating a first authentication response by said second party based on said first authentication challenge comprises enciphering said first authentication challenge to obtain said first authentication response.

34. The method of claim 22 wherein generating a first authentication response by said second party based on said first authentication challenge comprises combining bits of said first authentication challenge with unexpected bits.

35. The method of claim 34 wherein combining bits of said first authentication challenge with unexpected bits comprises combining bits of said first authentication challenge with bits of said second authentication challenge.

36. The method of claim 35 wherein combining bits of said first authentication challenge with unexpected bits comprises combining said first authentication challenge with said session key.

37. The method of claim 36 wherein combining said first authentication challenge with said session key further comprises generating a hash code based on a combination of said first authentication challenge and said session key.

38. The method of claim 37 wherein authenticating said second party by said first party based on said first authentication response comprises hashing a combination of said first authentication challenge and said second key to obtain an expected authentication response and comparing said expected authentication response with said first authentication response received from said second party.

39. A cryptographic communication apparatus used by a first party to communicate with a second party, said apparatus comprising:

a communications interface for communicating with said second party over a communication channel;

a processor coupled to said communication interface to perform cryptographic calculations, said processor programmed to;

generate a first authentication challenge based on a first exchanged value;

encipher said first authentication challenge to a key used by said second party;

compute a session key based on said first exchanged value and a second exchanged value received from said second party; and

verify the identity of said second party based on a first authentication response received from said second party.

40. An apparatus of claim 39 wherein said processor is further programmed to compute a second authentication response based on a second authentication challenge received from said second party and said session key.

41. The apparatus of claim 40 wherein said processor is further programmed to encipher said second authentication response to a key used by said second party.

42. The apparatus of claim 41 wherein computing a second authentication response by said processor comprises enciphering said second authentication challenge with said session key.

43. The apparatus of claim 41 wherein computing a second authentication response by said processor comprises combining bits of said second authentication challenge with one or more bits unknown to said second party.

44. The apparatus of claim 43 wherein combining bits of said second authentication challenge with bits unknown to said second party comprises combining said second authentication response with said session key.

45. The apparatus of claim 44 wherein combining said authentication challenge with said session key further comprises generating a hash code based on a combination of said second authentication challenge and said session key.

46. A cryptographic communication system used for communications between first and second parties, said communication system comprising:

a first communication terminal connected to a communications channel, said first communications terminal comprising a processor programmed to;

generate a first authentication challenge containing at least a first exchanged value;

encipher said first authentication challenge to a key used by said second party;

decipher a second authentication challenge received from said second party to obtain a second exchanged value;

compute a session key based on said first exchanged value and said second exchanged value;

verify the identity of said second party based on a first authentication response received from said second party; and

compute a second authentication response based on said second authentication challenge;

a second communications terminal connected to said communications channel, said second communications terminal comprising a processor programmed to;

generate said second authentication challenge containing at least said second exchanged value;

decipher said first authentication challenge received from said first party to obtain said first exchanged value;

compute a first authentication response based on said first authentication challenge;

encipher said second authentication challenge to a key used by said first party;

compute a session key based on said first exchanged value and said second exchanged value; and

verify the identity of said first party based on a second authentication response received from said first party.

47. The system of claim 46 wherein said first authentication response is computed by said processor in said second communication terminal by enciphering said first authentication challenge with said session key.

48. The system of claim 46 wherein said second authentication response is computed by said processor in said first communication terminal by enciphering said second authentication challenge with said session key.

49. The system of claim 46 wherein said first authentication response is computed by said processor in said second communication terminal by combining bits of said first authentication challenge with one or more bits unknown to said first party.

50. The system of claim 49 wherein combining bits of said first authentication challenge with bits unknown to said first party comprises combining said first authentication challenge with said session key.

51. The system of claim 49 wherein combining said first authentication challenge with said session key further comprises generating a hash code based on a combination of said second authentication challenge and said session key.

52. The system of claim 46 wherein said second authentication response is computed by said processor in said first communication terminal by combining bits of said second authentication challenge with one or more bits unknown to said second party.

53. The system of claim 52 wherein combining bits of said second authentication challenge with bits unknown to said second party comprises combining said second authentication challenge with said session key.

54. The system of claim 53 wherein combining said second authentication challenge with said session key further comprises generating a hash code based on a combination of said second authentication challenge and said session key.