SYSTEM AND METHOD FOR PROTECTING A PASSWORD AGAINST BRUTE FORCE ATTACKS

• US 20080120504A1
• Filed: 10/31/2006
• Published: 05/22/2008
• Est. Priority Date: 10/31/2006
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Adams, Neil P., Kirkup, Michael G., Little, Herbert A.
• Granted Patent: US 8,838,975 B2
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• 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/3247 involving digital signatures

Abstract

In a system and method for authenticating a client device by an authentication device, the client device user is assigned a PIN generated by the authentication device. The user provides the PIN and a password to the client device, from which the client device generates a symmetric key and further generates a public/private key pair. The private key is encrypted using the symmetric key and stored in encrypted form only. The public key and a message authentication code generated from the PIN are provided to the authentication device, which stores the public key. Subsequently, when the user seeks to be authenticated, the user enters a password at the client device, which is used to generate a symmetric key to decrypt the encrypted private key. A message to the authentication device is signed using the resultant value. The authentication device uses the public key to verify the signature of the message.

Claims

1. A method for providing authentication information from a client device to an authentication device, the authenticating device being provided with a public key K_pub paired to a private key K_priv associated with the client device, wherein K_pub and K_priv are generated at the client device, and K_priv is stored at the client device in encrypted form E_Kpriv, wherein K_priv is encrypted by a key K(P) derived from a password P to provide E_Kpriv, the method comprising the steps of:

receiving an input password P′

at the client device;

deriving, using the input password P′

, a key K(P′

), wherein the key K(P′

) is derived from the input password P′

using the same method used to derive the key K(P) from the password P;

decrypting, using the key K(P′

), the encrypted private key E_Kpriv to provide a signing value;

digitally signing a message using the signing value; and

transmitting the message to the authentication device, the authentication device being configured to verify the digitally signed message using the paired public key K_pub.

2. The method of claim 1, wherein the authentication device, upon verifying the digitally signed message, is configured to deliver a digital certificate associated with the provider of the input password P′

to the client device.

3. The method of claim 1, wherein the key K(P) is a symmetric key derived from the password P and the key K(P′

) is a symmetric key derived from the password P′

.

4. The method of claim 1, wherein the client device is a communication device.

5. The method of claim 4, wherein the client device is a mobile communication device.

6. The method of claim 3, wherein the client device is a communication device.

7. The method of claim 6, wherein the client device is a mobile communication device.

8. The method of claim 1, wherein the public key K_pub is associated with the user of a client device by means of authentication data associated with the user of the client device,

the authentication data having been generated and stored by the authentication device and provided to the user of the client device prior to provision of the public key K_pub to the authentication device, the method further comprising the step of transmitting, to the authentication device, a message comprising K_pub and information derived from the authentication data, such that the authentication device can verify the message using the information derived from the authentication data and, if said information is verified, store K_pub in association with the user of the client device.

9. The method of claim 8, wherein the information derived from the authentication data comprises a message authentication code generated at the client device from the authentication data.

10. The method of claim 8, wherein the key K(P) is a symmetric key derived from the password P and the key K(P′

) is a symmetric key derived from the password P′

.

11. The method of claim 8, wherein the client device is a communication device.

12. The method of claim 11, wherein the client device is a mobile communication device.

13. The method of claim 10, wherein the client device is a communication device.

14. The method of claim 13, wherein the client device is a mobile communication device.

15. A method for authenticating a client device by an authentication device, comprising the steps of claim 2, and further comprising the step of receiving, at the client device, the digital certificate upon verification of the digitally signed message by the authentication device.

16. The method of claim 15, wherein the authentication device is a certificate authority.

28. The method of claim 1, wherein the step of digitally signing a message comprises the step of generating a message comprising a nonce or randomly generated value.

29. The method of claim 8, wherein the step of digitally signing a message comprises the step of generating a message comprising a nonce or randomly generated value.

30. The method of claim 14, wherein the step of digitally signing a message comprises the step of generating a message comprising a nonce or randomly generated value.

37. A computer program product comprising program code operative to carry out the method of claim 1.

38. A computer program product comprising program code operative to carry out the method of claim 16.

17. A method for providing authentication information to a client device and an authentication device for authenticating the client device by the authentication device, comprising the steps of:

receiving an input password P at the client device;

deriving, using the input password P, a key K(P);

generating a private key K_priv and a paired public key K_pub;

encrypting, using the key K(P), the private key K_priv to derive E_Kpriv, wherein E_Kpriv is stored at the client device; and

transmitting the public key K_pub to the authentication device for storage.

18. The method of claim 17, further comprising the step of receiving, at the client device, authentication data associated with a user of the client device;

and wherein the step of transmitting the public key K_pub to the authentication device for storage comprises the steps of composing a message comprising information derived from the authentication data and the public key K_pub and transmitting the message to the authentication device.

19. The method of claim 18, further comprising the step of providing the authentication data to the user of the client device and at the authentication device before the step of transmitting the public key K_pub to the authentication device.

20. The method of claim 19, wherein the step of providing the authentication data to the user of the client device and at the authentication device comprises the step of generating the authentication data at the authentication device.

21. The method of claim 20, wherein the step of providing the authentication data to the user of the client device and at the authentication device further comprises the step of communicating the authentication data after verifying the identity of the user.

22. The method of claim 17, wherein the step of transmitting the public key K_pub to the authentication device for storage comprises the steps of generating a hash of the public key K_pub;

signing a message comprising the public key K_pub with the hash; and

transmitting the signed message to the authentication device.

23. The method of claim 22, wherein the step of transmitting the public key K_pub to the authentication device for storage comprises the steps of generating a hash of the public key K_pub;

generating a message authentication code from the authentication data;

signing a message comprising the public key K_pub and the message authentication code with the hash; and

transmitting the signed message to the authentication device.

24. A method for authenticating a client device, comprising the steps of:

receiving, at an authentication device, a message from a client device comprising a public key K_pub;

storing the public key K_pub at the authentication device;

receiving, at the authentication device, a message comprising a request for authentication and a digital signature;

verifying, at the authentication device, the digital signature of the message, such that if the digital signature is verified further data requiring prior authentication may be delivered to the client device;

wherein the digital signature is derived from a first value stored at the client device processed in accordance with a decryption algorithm using a key K(P′

), the key K(P′

) in turn derived using a key derivation algorithm from a user-entered password P′

, wherein the first value was previously derived at the client device as a private key K_priv paired with the public key K_pub and encrypted using an encryption algorithm corresponding to the decryption algorithm and using a key K(P), the key K(P) in turn derived from the key derivation algorithm from a password P, such that the digital signature is verified if the user-entered password P′

matches the password P.

25. The method of claim 24, further comprising the steps of:

providing, at the authentication device, first authentication data associated with a user of the client device;

storing, at the authentication device, the first authentication data, the first authentication data being provided to the user of the client device;

wherein the message received from the client device comprising the public key K_pub further comprises information derived from the first authentication data, the first authentication data being received by the client device from the user of the client device, and the step of storing the public key K_pub at the authentication device comprises the step of correlating the message received from the client device with the first authentication data stored at the authentication device and storing K_pub in association with an identifier associated with the user of the client device.

26. The method of claim 25, further comprising, prior to the step of receiving, at an authentication device, a message from a client device comprising a public key K_pub, the steps of:

generating, at the client device, the public key K_pub and the private key K_priv;

encrypting the private key K_priv with a key K(P) derived from a password P to provide E_Kpriv;

storing, at the client device, E_Kpriv.

27. The method of claim 25, wherein the key K(P) and the key K(P′

) are symmetric keys.

39. A computer program product comprising program code operative to carry out the method of claim 24.

40. A computer program product comprising program code operative to carry out the method of claim 25.

31. A client device for a system for authenticating the client device using an authentication device, the client device comprising:

an input for receiving an input password and authentication data;

a processor and memory for;

generating symmetric keys and paired public and private keys,

encrypting and decrypting data and digitally signing messages using keys, and

generating and transmitting messages;

wherein the client device is further adapted to;

generate a symmetric key from a first password P,

generate a public and private key pair K_pub, K_priv,

generate and transmit a message to the authentication device comprising the public key K_pub and received authentication data,

encrypt the private key K_priv using the symmetric key and store the encrypted private key K_priv,

generate and transmit a message to the authentication device comprising a request for authentication digitally signed with a value derived from decrypting the stored encrypted private key K_priv using a symmetric key generated from an input password P′

, for verification by the authentication device using the public key K_pub.

33. A system comprising the client device of claim 31 and the authentication device of claim 32.

34. The client device of claim 31, wherein the client device is a communication device.

35. The client device of claim 34, wherein the client device is a mobile communication device.

36. The system of claim 33, wherein the client device is a mobile communication device.

32. An authentication device for a system for authenticating a client device using the authentication device, the authentication device comprising:

a processor and memory for;

generating and providing authentication data;

storing data;

verifying digitally signed messages using public keys;

generating and transmitting messages;

wherein the authentication device is further adapted to;

receive a message comprising a public key K_pub generated by the client device and information derived from the authentication data generated by the authentication device and provided to a user of the client device and subsequently received by the client device, the public key K_pub corresponding to a paired private key K_pub encrypted using a first password P and stored at the client device in encrypted form,

store the public key K_pub,

receive a message from the client device comprising a request for authentication provided with a digital signature generated by the client device using a value derived from decrypting the encrypted private key K_priv stored at the client device using a symmetric key generated from an input password P′

received at the client device, and

verify the digital signature using the public key K_pub,

wherein the authentication device is adapted to authenticate a user of the client device if the digital signature is verified using the public key K_pub.