Device authentication

• US 7,647,498 B2
• Filed: 04/30/2004
• Issued: 01/12/2010
• Est. Priority Date: 04/30/2004
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Davis, Dinah L. M., Brown, Michael K., Little, Herbert A.
• Primary Examiner(s): Orgad; Edan
• Assistant Examiner(s): Baum; Ronald
• Application Number:
  US10/836,107
• Publication Number:
  US 20050243619A1
• Time in Patent Office: 2,083 Days
• Field of Search: 713/168
• US Class Current: 713/168
• CPC Class Codes: G11C 7/24 Memory cell safety or protection circuits, e.g. arrangements for preventing inadvertent reading or writing; Status cells; Test cells

Abstract

Authentication of two devices in communication with a third device is achieved where the first and second devices each possess a shared secret value. The authentication includes communication of authentication values from the first device to the second device using the third device. Similarly, there is communication of values from the second device to the first device using the third device. The third device retains the communicated values. The values are calculated to permit the third device to authenticate the first and second devices without the third device receiving the shared secret value. The authentication may be used to establish a communications channel between the first and the second devices.

Claims

1. A method for the authentication of a first and a second device by a third device, the first and the second devices each possessing a shared secret key value h, each of the devices having available to it a public key P selected such that the operation of deriving the secret key value h from the product hP is a computationally difficult operation, the method comprising the steps of:

the first device communicating a product R_D of a random value r_D and P to the second device using the third device, the third device retaining a copy of the product R_D;

the second device communicating a product R_B of a random value r_B and P, and a challenge value e_D to the first device using the third device, the third device retaining a copy of the product R_B and the challenge value e_D;

the first device calculating a value y_D defined by a first expression with a value equivalent to the product hP using the random value r_D and the challenge value e_D, and communicating the value y_D and a challenge value e_B to the second device using the third device, the third device retaining a copy of the value y_D and a challenge value e_B;

the second device calculating a value y_B defined by a second expression with a value equivalent to the product hP using the challenge value e_B and the random value r_B and communicating the value y_B to the third device; and

the third device authenticating the first device and the second device by comparing values of the first expression, the random value r_D, the challenge value e_D and the value y_D, with values of the second expression, the random value r_B, the challenge value e_B and the value y_B.

2. The method of claim 1 in which the first device is a wireless handheld device, the second device is an enterprise server, and the third device is a router and in which the step of the third device authenticating the first and second devices comprises the step of establishing a communications channel between the first device and the second device.

3. The method of claim 2 in which the communications channel established includes the third device as part of the channel and the third device having retained the values communicated between the first device and the second device, the method further comprising the step of closing the communication channel between the second device and the third device, the step of closing the said channel comprising the steps of the second device and the third device exchanges sets of closing authentication values to permit the third device to carry out a computation of an expression based on the retained values and the closing authentication values to authenticate the closing the communication channel.

20. A program product comprising a medium having executable program code embodied in said medium, the executable program code being variously executable on a first device, a second device and a third device, the executable program code being operative to cause the method of claim 1 to be carried out.

4. A method for the authentication of a first device and a second device by a third device, the first and second devices each possessing a shared secret key value h, each of the devices being operative to carry out mathematical operations on defined groups E(F_q) and Z_p, where F_q is a finite field of prime order q, including scalar multiplication defined with reference to the group, the method comprising the steps of:

a) obtaining a public key P, such that P generates a prime subgroup of the group E(F_q) of order p, and making available to each of the devices the public key P,

b) the first device obtaining a random value r_D such that 1<

r_D<

p−

1, and calculating a product R_D=r_DP,

c) the first device communicating the product R_D to the third device,

d) the third device retaining a copy of the product R_D and forwarding the product R_D to the second device,

e) the second device obtaining a random value r_B such that 1<

r_B<

p−

1, and calculating a product R_B=r_BP, where R_B is determined such that it is not equal to R_D, the second device obtaining a random value e_D such that 1<

e_D<

p−

1, the second device communicating e_D and R_B to the third device,

f) the third device retaining copies of R_B and e_D forwarding R_B and e_D to the first device,

g) the first device calculating a value y_D=h−

e_Dr_D mod p, the first device obtaining a random value e_B such that 1<

e_B<

p−

1, the first device communicating values y_D and e_B to the third device,

h) the third device retaining copies of the values y_D and e_B forwarding the said values to the second device,

i) the second device calculating a value y_B=h−

e_Br_B mod p, the second device communicating the value y_B to the third device, and

j) the third device authenticating the first and second devices when the condition y_BP+e_BR_B=y_DP+e_DR_D is satisfied.

5. The method of claim 4, further comprising the steps of the third device communicating the value y_B to the first device and the first device authenticating the second device when the condition y_BP+e_BR_B=hP is satisfied.

6. The method of claim 4, further comprising the step of the second device authenticating the first device when the condition y_DP+e_DR_D=hP is satisfied.

7. The method of claim 4, in which the first device is identified by a non-authenticating identifier and in which the second device retains a set of key values which set includes a key value shared with the secret key value of the first device, the method comprising the step of the first device communicating the non-authenticating identifier to the second device whereby the second device may select the key value shared with the secret key value of the first device from the set of key values.

8. The method of claim 4, further comprising the step of deriving the value h from a shared secret value s.

9. The method of claim 8, in which the step of deriving the value h comprises the step of carrying out a one-way hash function on the shared secret value s.

10. The method of claim 4, further comprising the steps of one or more of the first, second and third devices checking that at least one of the value e_D and the value e_B is not zero.

11. The method of claim 4, further comprising the steps of one or more of the first, second and third devices checking that at least one of the product R_B and the product R_D is not equal to the point at infinity.

12. The method of claim 4, further comprising the steps of one or more of the first, second and third devices checking that the product R_B is not equal to the product R_D.

13. The method of claim 4 in which the first device is a wireless handheld device, the second device is an enterprise server, and the third device is a router, and in which the step of the third device authenticating the first and second devices comprises the step of establishing a communications channel between the first and second devices.

14. The method of claim 13 in which the communications channel is defined by the assignment of an Internet Protocol address to the first device.

15. The method of claim 13 in which the communications channel is established through the third device, the third device having retained y_D, P, e_D, and R_D, the method further comprising the step of closing the communication channel between the second device and the third device by:

a) the second device obtaining a random value r_C such that 1<

r_C<

p−

1, and calculating a product R_C=r_CP, whereby R_C is constrained to have a different value than both R_B and R_D,

b) the second device communicating the product R_C to the third device,

c) the third device obtaining a random value e_C such that 1<

e_C<

p−

1, the third device communicating the value e_C to the second device,

d) the second device authenticating the close operation when the condition y_CP+e_CR_C=y_DP+e_DR_D is satisfied by the second device calculating a value y_C=h−

e_Cr_C mod p, the second device communicating the value y_C to the third device, and the third device closing the channel if the value y_C received by the third device satisfies the condition y_CP+e_CR_C=y_DP+e_DR_D.

16. The method of claim 15, further comprising the steps of the second device checking that the value e_C is not zero.

17. The method of claim 15, further comprising the steps of the third device checking that the product R_C is not equal to the point at infinity.

18. The method of claim 15, further comprising the steps of one or both of the second and third devices checking that the product R_C is not equal to the product R_B and is not equal to the product R_D.

19. The method of claim 15, further comprising the steps of one or both of the second and third devices checking that the value e_C is not equal to the value e_D and is not equal to the value e_B.

21. A program product comprising a medium having executable program code embodied in said medium, the executable program code being variously executable on a first device, a second device and a third device, the executable program code being operative to cause the method of claim 4 to be carried out.

22. A system comprising a first device, a second device, and a third device, the first and the second devices each possessing a shared secret key value h, each of the devices having available to it a public key P, selected such that the operation of deriving the secret key value h from the product hP is a computationally difficult operation, the first device, the second device and the third device each comprising memory units and processors for storing and executing program code, the program code being operative to:

the first device to communicate a product R_D of a random value r_D and P to the second device using the third device;

cause the second device to communicate a product R_B of a random value r_B and P, and a challenge value e_D, to the first device using the third device;

cause the first device to calculate a value y_D defined by a first expression with a value equivalent to the product hP using the random value r_D and the challenge value e_D, and to communicate the value y_D and a challenge value e_B to the second device using the third device;

cause the second device to calculate a value y_B defined by a second expression with a value equivalent to the product hP using the challenge value e_B and the random value r_B and to communicate the value y_B to the third device;

cause the third device to retain copies of the values being communicated between the first and the second device using the third device; and

cause the third device to authenticate the first device and the second device by comparing values of the first expression, the random value r_D, the challenge value e_D and the value y_D, with values of the second expression, the random value r_B, the challenge value e_B and the value y_B.

23. The system of claim 22 in which the first device is a wireless handheld device, the second device is an enterprise server, and the third device is a router and in which the program code operative to cause the third device to authenticate the first device and the second device comprises program code operative to establish a communications channel between the first device and the second device.

24. The system of claim 23 in which the communications channel established includes the third device as part of the channel and the third device comprises memory to retain the values communicated between the first device and the second device, the program code further comprising the program code operative to close the communication channel between the second device and the third device, the said code comprising program code operative to exchange sets of closing authentication values between the second device and the third device to permit the third device to carry out a computation of an expression based on the retained values and the closing authentication values to authenticate the closing the communication channel.

25. A system comprising a first device, a second device, and a third device, the first and second devices each possessing a shared secret key value h, each of the devices being operative to carry out mathematical operations on defined groups E(F_q) and Z_p, where F_q is a finite field of prime order q, including scalar multiplication defined with reference to the group, the first device, the second device and the third device each comprising memory units and processors for storing and executing program code, the program code being operative to:

a) obtain a public key P, such that P generates a prime subgroup of the group E(F_q) of order p, and to make available to each of the devices the public key P,

b) cause the first device to obtain a random value r_D such that 1<

r_D<

p−

1, and to calculate a product R_D=r_DP,

c) cause the first device to communicate the product R_D to the third device,

d) cause the third device to retain a copy of the product R_D and to forward the product R_D to the second device,

e) cause the second device to obtain a random value r_B such that 1<

r_B<

p−

1, and to calculate a product R_B=r_BP, where R_B is determined such that it is not equal to R_D, and to cause the second device to obtain a random value e_D such that 1<

e_D<

p−

1, and to communicate e_D and R_B to the third device,

f) cause the third device to retain copies of the R_B and e_D and to forward R_B and e_D to the first device,

g) cause the first device to calculate a value y_D=h−

e_Dr_D mod p, to cause the first device to obtain a random value e_B such that 1<

e_B<

p−

1, and to cause the first device to communicate values y_D and e_B to the third device,

h) cause the third device to retain copies of the values y_D and e_B and to forward the said values to the second device,

i) cause the second device to calculate a value y_B=h−

e_Br_B, mod p, and to cause the second device to communicate the value y_B to the third device, and

j) cause the third device to authenticate the first and second devices when the condition y_BP+e_BR_B=y_DP+e_DR_D is satisfied.

26. The system of claim 25 in which the first device is a wireless handheld device, the second device is an enterprise server, and the third device is a router and in which the program code operative to cause the third device to authenticate the first and second devices comprises program code operative to establish a communications channel between the first and second devices.