System and Method for Performing Device Authentication Using Key Agreement

• US 20120011362A1
• Filed: 07/06/2011
• Published: 01/12/2012
• Est. Priority Date: 07/08/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Lambert, Robert John
• Granted Patent: US 8,990,564 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• CPC Class Codes: G06F 21/34 involving the use of external additional devices, e.g. dongles or smart cards
• CPC Class Codes: G06F 21/44 Program or device authentication
• 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/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A system and method are provided which employs a key agreement scheme, wherein the agreed-upon-shared key is used in a protocol message in the authentication rather than being employed as a session key.

Claims

1. A method of performing device authentication, the method comprising:

a verification device participating in a key agreement protocol with an authentication device;

the verification device obtaining a first value from the authentication device, the first value having been generated by applying a deterministic function to a first result from a first operation performed in the key agreement protocol; and

the verification device using the first value to authenticate the authentication device by performing a comparison of the first value with a second value, the second value generated by applying the deterministic function to a second result from a second operation performed in the key agreement protocol.

2. The method according to claim 1, wherein the first and second results correspond to an agreed-upon-key.

3. The method according to claim 1, wherein the deterministic function uses information known to the verification device and the authentication device.

4. The method according to claim 1, wherein the deterministic function uses identity information of the authentication device.

5. The method according to claim 1, wherein the deterministic function generates an output based on one or more inputs, the output having a number of bits, each input having a respective number of bits, the number of bits of the output being less than the respective number of bits of one or more inputs.

6. The method according to claim 1, wherein the key agreement protocol comprises an elliptic curve key agreement protocol, and wherein the participating comprises the verification device choosing a challenge point on an elliptic curve and providing the challenge point to the authentication device, wherein the first value received from the authentication device has been computed using the challenge point.

7. The method according to claim 6, wherein the challenge point is computed by performing scalar multiplication using a private key and a generating point.

8. The method according to claim 1, further comprising the verification device obtaining a public key of the authentication device.

9. The method according to claim 1, further comprising the verification device validating a signature obtained from the authentication device.

10. The method according to claim 1, further comprising the verification device accepting or rejecting the authentication device according to the comparison.

11. The method according to claim 1, wherein the key agreement protocol comprises any one of a Diffie-Hellman protocol, an MQV protocol, and a STS protocol.

12. The method according to claim 1, wherein a cofactor is utilized in computing the first and second values.

13. The method according to claim 12, wherein the cofactor has been included in a private key of the authentication device.

14. A computer readable medium comprising computer executable instructions for performing device authentication, the computer readable medium comprising instructions for:

a verification device participating in a key agreement protocol with an authentication device;

the verification device obtaining a first value from the authentication device, the first value having been generated by applying a deterministic function to a first result from a first operation performed in the key agreement protocol; and

the verification device using the first value to authenticate the device by performing a comparison of the first value with a second value, the second value generated by applying the deterministic function to a second result from a second operation performed in the key agreement protocol.

15. A verification device comprising a processor and memory, the processor configured for performing device authentication, the memory storing computer executable instructions for:

participating in a key agreement protocol with an authentication device;

obtaining a first value from the authentication device, the first value having been generated by applying a deterministic function to a first result from a first operation performed in the key agreement protocol; and

using the first value to authenticate the device by performing a comparison of the first value with a second value, the second value generated by applying the deterministic function to a second result from a second operation performed in the key agreement protocol.

16. A method of enabling device authentication, the method comprising:

an authentication device participating in a key agreement protocol with a verification device;

the authentication device generating a first value by applying a deterministic function to a first result from a first operation performed in the key agreement protocol; and

the authentication device providing the first value to the verification device, wherein the first value enables the verification device to perform device authentication by performing a comparison of the first value with a second value, the second value generated by applying the deterministic function to a second result from a second operation performed in the key agreement protocol.

17. The method according to claim 16, wherein the first and second results correspond to an agreed-upon-key.

18. The method according to claim 16, wherein the deterministic function uses information known to the verification device and the authentication device.

19. The method according to claim 16, wherein the deterministic function uses identity information of the authentication device.

20. The method according to claim 16, wherein the deterministic function generates an output based on one or more inputs, the output having a number of bits, each input having a respective number of bits, the number of bits of the output being less than the respective number of bits of one or more inputs.

21. The method according to claim 16, wherein the key agreement protocol comprises an elliptic curve key agreement protocol, and wherein the participating comprises the authentication device obtaining a challenge point on an elliptic curve from the verification device, and the authentication device computing the first value using the challenge point.

22. The method according to claim 21, wherein the challenge point has been computed by performing scalar multiplication using a private key and a generating point.

23. The method according to claim 16, further comprising the authentication device providing a public key to the verification device.

24. The method according to claim 16, further comprising the authentication device providing a signature to be obtained by the verification device.

25. The method according to claim 16, wherein the key agreement protocol comprises any one of a Diffie-Hellman protocol, an MQV protocol, and a STS protocol.

26. The method according to claim 16, wherein a cofactor is utilized in computing the first and second values.

27. The method according to claim 26, wherein the cofactor has been included in a private key of the authentication device.

28. The method according to claim 21, further comprising the authentication device applying one or more tests to the challenge point.

29. The method according to claim 28, wherein the one or more tests comprise any one or more of checking the challenge point is on an elliptic curve being used in the key agreement protocol, and checking that the challenge point is in a large prime sub-order group on the elliptic curve.

30. A computer readable medium comprising computer executable instructions for performing device authentication, the computer readable medium comprising instructions for:

an authentication device participating in a key agreement protocol with a verification device;

the authentication device generating a first value by applying a deterministic function to a first result from a first operation performed in the key agreement protocol; and

the authentication device providing the first value to the verification device, wherein the first value enables the verification device to perform device authentication by performing a comparison of the first value with a second value, the second value generated by applying the deterministic function to a second result from a second operation performed in the key agreement protocol.

31. An authentication device comprising a processor and memory, the processor configured for enabling device authentication, the memory storing computer executable instructions for:

participating in a key agreement protocol with a verification device;

generating a first value by applying a deterministic function to a first result from a first operation performed in the key agreement protocol; and

providing the first value to the verification device, wherein the first value enables the verification device to perform device authentication by performing a comparison of the first value with a second value, the second value generated by applying the deterministic function to a second result from a second operation performed in the key agreement protocol.