Device authentication

• US 20050243619A1
• Filed: 04/30/2004
• Published: 11/03/2005
• 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.
• Granted Patent: US 7,647,498 B2
• Time in Patent Office: Days
• US Class Current: 365/202
• 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 and the second device communicating a set of values to each other using the third device, such that the first device is able to calculate a first expression with a value equivalent to the product hP and the second device is able to calculate a second expression with a value equal to the product hP, the third device retaining copies of the values being communicated between the first and the second device, the method further comprising the step of the third device calculating and comparing the values of the first expression and of the second expression to authenticate the first and the second devices.

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 and second devices.

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 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 is 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 value R_D=r_DP,

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

d) the third device retaining a copy of the value R_D and forwarding the value 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 value 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 the values r_D and R_B to the third device,

f) the third device retaining copies of the values R_B and r_D forwarding the said values 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 step of 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 the value e_D is not zero and/or that 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 the value R_B is not equal to the point at infinity and/or that the value 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 value R_B is not equal to the value 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 established includes the third device as part of the channel and the third device having retained the values 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, the step of closing the said channel comprising the steps of:

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

r_C<

p−

1, and calculating a value 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 value 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.

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 value 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 value R_C is not equal to the value R_B and is not equal to the value 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 code being operative to cause communication of a set of values between the first device and the second device using the third device,

the program code being operative to cause the first device to calculate a first expression with a value equivalent to the product hP and the second device to calculate a second expression with a value equal to the product hP,

the program code being operative to cause the third device to retain copies of the values being communicated between the first and the second device, and

the program code being operative to cause the third device to calculate and compare the values of the first expression and of the second expression to authenticate the first and the second devices.

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 opertative to cause the third device to authenticae the first and second devices comprises program code operative to establish a communications channel between the first and second devices.

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

a) the program code being operative to 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) the program code being operative to cause the first device to obtain a random value r_D such that 1<

r_D<

p−

1, and to calculate a value R_D=r_DP,

c) the program code being operative to cause the first device to communicate the value R_D to the third device,

d) the program code being operative to cause the third device to retain a copy of the value R_D and to forward the value R_D to the second device,

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

r_B<

p−

1, and to calculate a value 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 the values r_D and R_B to the third device,

f) the program code being operative to cause the third device to retain copies of the values R_B and r_D and to forward the said values to the first device,

g) the program code being operative to 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) the program code being operative to 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) the program code being operative to 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) the program code being operative to 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 comprises program code operative to establish a communications channel between the first and second devices.