Device authentication in a PKI

• US 20030065918A1
• Filed: 04/08/2002
• Published: 04/03/2003
• Est. Priority Date: 04/06/2001
• Status: Active Grant

• Current Assignee: Blackberry Limited
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Willey, William Daniel
• Granted Patent: US 7,516,325 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 63/0492 by using a location-limited connection, e.g. near-field communication or limited proximity of entities
• CPC Class Codes: H04L 63/14 for detecting or protecting against malicious traffic
• CPC Class Codes: H04L 63/1466 Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/3273 for mutual authentication network architectures or network communication protocols for achieving mutual authentication in a packet data network H04L63/0869
• CPC Class Codes: H04W 12/06 Authentication
• CPC Class Codes: H04W 12/50 Secure pairing of devices
• CPC Class Codes: H04W 12/64 using geofenced areas

Abstract

A method for establishing a link key between correspondents in a public key cryptographic scheme, one of the correspondents being an authenticating device and the other being an authenticated device. The method also provides a means for mutual authentication of the devices. The authenticating device may be a personalized device, such as a mobile phone, and the authenticated device may be a headset. The method for establishing the link key includes the step of introducing the first correspondent and the second correspondent within a predetermined distance, establishing a key agreement and implementing challenge-response routine for authentication. Advantageously, man-in-the middle attacks are minimized.

Claims

1. A method of establishing a key between a first device and a second device, said method comprising the steps of:

establishing a shared secret in said first device and in said second device;

calculating an antispoof variable based at least in part upon said shared secret in said first device and in said second device, said antispoof variable being represented by a plurality of digits;

indicating said digits of said antispoof variable from said first device to a user using a first stimulus;

indicating said digits of said antispoof variable from said second device to said user, using a second stimulus;

verifying that said digits of said antispoof variable from said first device and said second device are the same; and

establishing said key based upon said result of said verifying step.

2. The method of claim 1 wherein said digits of said antispoof variable are divided into a plurality of groups of at least one digit and a timing of said indication of a group of digits of said antispoof variable from said first device is time synchronized with a timing of said indication of a same group of digits of said antispoof variable from said second device.

3. The method of claim 2 wherein said synchronization is based on a timing of messages used to perform said key agreement.

4. The method of claim 1 wherein said first stimulus is an audible stimulus and said second stimulus is a visual stimulus.

5. The method of claim 1 wherein said first stimulus is an audible stimulus and said second stimulus is an audible stimulus time delayed from said first stimulus.

6. The method of claim 1 wherein said user to which digits of said antispoof variable are indicated from said first device is a different user than said user to which digits of said antispoof variable are indicated from said second device.

7. A method for establishing a link key between a pair of correspondents in a public key cryptographic scheme in which one of said correspondents is an authenticating device and another of said correspondents is an authenticated device, said devices being interoperable over a first normal operating range to exchange information, said method comprising the steps of locating said devices at a relative spacing less than said normal operating range, determining said relative spacing between said devices, comparing said spacing with a predetermined maximum distance and initiating a key agreement protocol between said devices if relative spacing is less than predetermined maximum distance.

8. The method of claim 7 further including a step of determining at said first correspondent if said second correspondent has a particular piece of information.

9. The method of claim 8 wherein the step of determining at said first correspondent if said second correspondent has a particular piece of information further includes of the following steps of:

determining a challenge at said first correspondent;

dividing said challenge into a plurality of portions;

performing the following sub-steps for each portion of said challenge;

transmitting said portion of said challenge from said first correspondent to said second correspondent,

receiving said portion of said challenge from said first correspondent in said second correspondent,

in said second correspondent generating a response that is an output of a function whose input is said received portion of said challenge and said particular piece of information,

transmitting said response from said second correspondent to said first correspondent, and receiving said response in said first correspondent;

and performing a verify function in said first correspondent, said verify function verifying that said response is a function of said corresponding portions of said challenge and said response is a function of said particular piece of information.

10. The method of claim 9 wherein an acceptable time between said reception of a portion of said challenge by said second correspondent and said transmission of said response by said second correspondent is determined, said acceptable time being related to a time it takes for the response to travel said maximum distance being a function of a tolerable error in measurement.

11. The method of claim 9 wherein said time to transmit a portion of said challenge is related to a time it takes for said challenge to travel a distance that is a function of a tolerable error in measurement.

12. The method of claim 9 wherein said measurement of said distance between said first correspondent and said second correspondent is determined based on a time difference between a time of reception of the response to the portion of a challenge and a time of transmission of said portion of said challenge.

13. The method of claim 9 wherein said portions of said challenge are transmitted between said first correspondent and said second correspondent using a radio frequency (RF) signal.

14. The method of claim 9 wherein said portions of said challenge are transmitted between said first correspondent and said second correspondent using an ultra-wideband signal.

15. The method of claim 9 wherein said portions of said challenge are transmitted between said first correspondent and said second correspondent using a sound signal.

16. A method for establishing a key between a first correspondent and a second correspondent device, the method including the steps of:

establishing a shared secret in said first correspondent and said second correspondent;

calculating an antispoof variable in said first correspondent and said second correspondent, based at least in part upon said shared secret;

generating a random challenge in said first correspondent, said challenge having a plurality of bits;

performing the following substeps for each of said bits of said random challenge;

transmitting said bit of said random challenge from said first correspondent to said second correspondent,

receiving said bit of said random challenge from said first correspondent in said second correspondent,

in said second correspondent, performing an exclusive OR (XOR) of said bit of said random challenge with a bit of said antispoof variable to determine a response bit,

after receiving said bit of said random challenge transmitting said response bit from said second correspondent to said second correspondent,

receiving at said first correspondent said response bit, and

in said first correspondent performing an XOR of said response bit with a

corresponding bit of said antispoof variable and determining if said result bit matches said bit of said random challenge that was transmitted from said first correspondent to said second correspondent;

at said first correspondent determining a time difference between a time said response bit is received and a time said corresponding bit of said random challenge was sent;

at said first correspondent verifying that a sufficiently large number of result bits match said corresponding bit of said transmitted random challenge; and

whereby said key is established when said time difference is substantially small to determine that said second correspondent is within a predetermined distance of the first correspondent and a substantially large number of response bits match said corresponding bits of said transmitted random challenge.

17. The method of claim 16 wherein said time between said reception of a bit of said random challenge by said second correspondent and said transmission of said response bit by said second correspondent is related to a time it takes for said response bit to travel a distance that is a function of a tolerable error in measurement.

18. The method of claim 16 wherein said time to transmit a bit of said random challenge is related to a time it takes for said challenge to travel a distance that is a function of a tolerable error in measurement.

19. The method of claim 16 wherein bits are transmitted between said first correspondent and said second correspondent using a radio frequency (RF) signal.

20. The method of claim 16 wherein bits are transmitted between said first correspondent and said second correspondent using an ultra-wideband signal.

21. The method of claim 16 wherein bits are transmitted between said first correspondent and said second correspondent using a sound signal.

22. A method for securely determining a distance between a first device and a second device, said method including the steps of:

determining at said first device if said second device has a particular piece of information, including the further steps of;

determining a challenge at said first device dividing said challenge into a plurality of portions;

performing the following substeps for each portion of said challenge;

transmitting a portion of said challenge from said first device to said second device, receiving said portion of said challenge from said first device in said second device,

in said second device generating a response that is an output of a function whose input in said received portion of said challenge and said particular piece of information,

transmitting said response from said second device to said first device, and receiving said response in said first device;

performing a verify function in said first device, said verify function verifying that said responses are a function of corresponding portions of said challenge and are function of said particular piece of information; and

determining said distance between said first device and said second device based on a time difference between a time of reception of said response to a portion of a challenge and a time of transmission of the portion of said challenge.

23. The method of claim 22 wherein said time between said reception of said portion of said challenge by said second device is related to a time it takes for said portion of said challenge to travel a distance that is a function of a tolerable error in measurement.

24. The method of claim 22 wherein said time to transmit said portion of said challenge is related to the amount of time it takes for said portion of said challenge to travel a distance that is a function of a tolerable error in measurement.

25. The method of claim 22 wherein said portion of said challenge and said response are transmitted between the first device and said second device using a radio frequency (RF) signal.

26. The method of claim 22 wherein said portion of said challenge and said response are transmitted between said first device and said second device using an ultra-wideband signal.

27. The method of claim 22 wherein said portion of said challenge and said response are transmitted between said first device and said second device using a sound signal.

28. A method for establishing a key between a first device and a second device, said method including the steps of:

establishing a shared secret in said first device and in said second device, wherein said messages used to perform said key agreement are sent using a first form of communication;

calculating an antispoof variable based at least in part upon said shared secret in said first device and in said second device, said antispoof variable being represented by a plurality of digits;

transmitting said digits of said antispoof variable from said first device to said second device using a second form of communication;

verifying in said second device that said digits of said antispoof variable received from said first device are said same as said digits of said antispoof variable calculated by said second device;

and establishing said key based upon said result of said verifying step.

29. The method of claim 28 wherein the range of a signal transmitted using the second form of communication is less than the range of a signal transmitted using the first form of communication.

30. The method of claim 28 wherein said first form of communication and second form of communication include a radio frequency signal, an infrared signal or a sound signal.

31. A method of establishing a key between a first device and a second device, the method including the steps of:

performing a key agreement to establish in said first device and in said second device a shared secret;

calculating an antispoof variable in said first device and in said second device based at least in part upon said shared secret, said antispoof variable having a plurality of digits;

indicating said digits of said antispoof variable from said first device to a user using an audible stimulus;

indicating said digits of said antispoof variable from a user to said second device;

verifying in said second device that said digits of said antispoof indicated by said user are the same as said digits of said antispoof variable calculated by said second device; and

establishing said key based upon said result of said verifying step.

32. A method for establishing secure communications between a first correspondent and a second correspondent, said method including the steps of:

said first correspondent initializing communication with said second correspondent;

said first correspondent and said second correspondent performing said key agreement;

said first correspondent generating a first public signal associated with said first correspondent

and said second correspondent generating a second signal associated with second correspondent;

said first correspondent sending said first public signal to said second correspondent and said second correspondent sending said second public signal to said first correspondent;

said first correspondent performing a first mathematical operation on said second public signal to generate a shared secret signal and said second correspondent performing a corresponding first mathematical operation on first public signal to generate a corresponding shared secret signal;

performing a second mathematical operation to said shared signal and corresponding shared signal to generate an authenticating signal;

said first correspondent and said second correspondent performing mutual authentication of one another, said step of mutual authentication further including a step of;

said first correspondent and said second correspondent performing a third mathematical operation on said authenticating signal to obtain a private verification signal;

whereby said first correspondent and said second correspondent further synchronizing one another to exchange of said private verification signal and compare received verification signal with said private verification signal; and

performing said exchange sequentially as determined by a predefined time period;

establishing a link key for use in authentication between said first correspondent and said second correspondent subsequent to said verification;

performing a fourth mathematical operation on said link key to generate an encryption key.