Challenge response-based device authentication system and method

• US 7,603,556 B2
• Filed: 11/26/2004
• Issued: 10/13/2009
• Est. Priority Date: 05/04/2004
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: Brown, Michael S., Brown, Michael K., Kirkup, Michael G., Little, Herbert A.
• Primary Examiner(s): Pich; Ponnoreay
• Application Number:
  US10/996,369
• Publication Number:
  US 20050250473A1
• Time in Patent Office: 1,782 Days
• Field of Search: 713/168, 713/169
• US Class Current: 713/169
• CPC Class Codes: H04L 2209/80 Wireless
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A challenge response scheme authenticates a requesting device by an authenticating device. The authenticating device generates and issues a challenge to the requesting device. The requesting device combines the challenge with a hash of a password provided by a user, and the combination is further hashed in order to generate a requesting encryption key used to encrypt the user supplied password. The encrypted user supplied password is sent to the authenticating device as a response to the issued challenge. The authenticating device generates an authenticating encryption key by generating the hash of a combination of the challenge and a stored hash of an authenticating device password. The authenticating encryption key is used to decrypt the response in order to retrieve the user-supplied password. If the user-supplied password hash matches the stored authenticating device password hash, the requesting device is authenticated and the authenticating device is in possession of the password.

Claims

1. A method for authentication of a requesting device by an authenticating device, the requesting device and the authenticating device each being operative to carry out a one-way hash operation and to carry out a key-based encryption operation, the authenticating device storing a hash of a defined password generated by applying the one-way hash operation to the defined password, the authenticating device being further operative to carry out a key-based decryption operation for decrypting values obtained from the key-based encryption operation, the method comprising the steps of:

the requesting device receiving a user password and carrying out the one-way hash operation on the user password to obtain a hash of the user password,

the authenticating device determining and transmitting a challenge to the requesting device;

the requesting device receiving the challenge and defining a requesting encryption key by carrying out the one-way hash operation on a combination of the challenge and the hash of the user password,

the requesting device carrying out the key-based encryption operation using the requesting encryption key to encrypt the user password,

the requesting device transmitting a response comprising the encrypted user password to the authenticating device,

the authenticating device receiving the response and defining an authenticating encryption key by carrying out the one-way hash operation on a combination of the challenge and the hash of the defined password;

the authenticating device using the authenticating encryption key in the key-based decryption operation to decrypt the response to obtain a decrypted user password and carrying out the one-way hash operation on the decrypted user password;

the authenticating device comparing the hash of the decrypted user password with the hash of the defined password to authenticate the requesting device when the comparison indicates a match.

2. The method of claim 1 further comprising:

the authenticating device using the decrypted user password to carry out operations on the authenticating device.

3. The method of claim 1 in which the authenticating device comprises a wireless handheld device and the requesting device comprises a desktop computer and in which the authentication of the requesting device is required to establish a connection between the wireless handheld device and the requesting device, the method further comprising:

the requesting device sending a connection request to the authenticating device prior to the authenticating device determining a challenge, and

refusing to establish a connection when the one-way hash of the decrypted user password does not match the hash of the defined password.

4. The method of claim 1, in which the step of the authenticating device determining and transmitting a challenge comprises generating a random number to be used as the challenge.

5. The method of claim 1, further comprising an initial step of the requesting device transmitting a connection request to the authenticating device and comprising the step of the authentication device receiving the connection request and carrying out the authentication of the requesting device if a defined flag is set on the authenticating device to indicate that the authenticating device has been secured with the defined password.

6. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing system, to perform the method of claim 1.

7. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing system, to perform the method of claim 2.

8. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing system, to perform the method of claim 3.

9. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing system, to perform the method of claim 4.

10. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing system, to perform the method of claim 5.

11. A system for an authentication device to authenticate a requesting device, comprising:

a challenge generator for generating a challenge,

a communications link for transmitting the challenge to the requesting device and receiving a response to the challenge from the requesting device, the response comprising a requesting password encrypted using a requesting encryption key, the requesting encryption key comprising a hash of a combination of the challenge and a hash of the requesting password;

a hash generator for generating an authenticating encryption key by hashing a combination of the challenge and a hash of a predetermined password;

a decryptor for decrypting the encrypted requesting password using the authenticating encryption key to obtain a decrypted response; and

a comparator for comparing a hash of the decrypted response with the hash of the predetermined password, whereby if the hash of the decrypted requesting password matches the hash of the predetermined password, the requesting device is authenticated.

12. The system of claim 11, wherein the challenge generated by the challenge generator is a random or pseudo-random number.

13. The system of claim 11, wherein the communications link is further configured to receive an authentication request from the requesting device.

14. The system of claim 11, further comprising an authentication flag for indicating whether the authentication device has been secured with the predetermined password.

15. A method for securely transmitting a password to a receiving device, the receiving device being provided with a hash of a predetermined password, a random number, and a receiving encryption key comprising a hash of the random number and the hash of the predetermined password, comprising the steps of:

receiving a random number from the receiving device;

encoding the password to produce a hash of the password;

combining the random number with the hash of the password;

hashing the combined random number and hash of the password to produce a transmitting encryption key;

encrypting the password using the transmitting encryption key;

transmitting the encrypted password to the receiving device for decryption by the receiving device using the receiving encryption key.

16. A computing device program product comprising code embodied on a computer-readable medium operative, when implemented on a computing device, to perform the method of claim 15.

17. A method for authentication of a requesting device by an authenticating device, the requesting device and the authenticating device each being operative to carry out a one-way hash operation and to carry out a key-based encryption operation, the authenticating device storing a hash of a defined password generated by applying the one-way hash operation to the defined password, the authenticating device being further operative to carry out a key-based decryption operation for decrypting values obtained from the encryption operation, the method comprising the authenticating device:

determining and transmitting a challenge to the requesting device;

receiving a response from the requesting device, the response comprising a requesting encryption key determined by carrying out the hash operation on a combination of the challenge and a hash of a received user password, the hash being defined by carrying out the hash operation on the received user password,

defining an authenticating encryption key by carrying out the hash operation on a combination of the challenge and the hash of the defined password;

using the authenticating encryption key in the decryption operation to decrypt the response to obtain a decrypted user password and carrying out the one-way hash operation on the decrypted user password;

comparing the hash of the decrypted user password with the hash of the defined password to authenticate the requesting device when the comparison indicates a match.

18. The method of claim 17 further comprising:

the authenticating device using the decrypted user password to carry out operations on the authenticating device.

19. The method of claim 17 in which the authenticating device comprises a wireless handheld device and the requesting device comprises a desktop computer and in which the authentication of the requesting device is required to establish a connection between the wireless handheld device and the requesting device, the method further comprising:

the authenticating device receiving a connection request prior to the authenticating device determining a challenge, and

refusing to establish a connection when the hash of the decrypted user password does not match the hash of the defined password.

20. The method of claim 17, in which the authenticating device determining and transmitting the challenge to the requesting device comprises generating a random number to be used as the challenge.

21. The method of claim 17, further comprising an initial step of the authentication device receiving from the requesting device a connection request and carrying out the authentication of the requesting device if a defined flag is set on the authenticating device to indicate that the authenticating device has been secured with the defined password.

22. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing device, to perform the method of claim 17.

23. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing device, to perform the method of claim 19.

24. A computing device program product comprising a computer-readable medium embodying code operative, when implemented on a computing device, to perform the method of claim 18.