SECURING PASSWORDS AGAINST DICTIONARY ATTACKS

• US 20110252229A1
• Filed: 04/07/2010
• Published: 10/13/2011
• Est. Priority Date: 04/07/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Belenkiy, Mira, Kupcu, Alptekin, Jerez Morales, Henry Nelson, Acar, Tolga
• Granted Patent: US 9,015,489 B2
• Time in Patent Office: Days
• US Class Current: 713/155
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• 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 63/0853 using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• 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/3271 using challenge-response

Abstract

Described herein are various technologies pertaining to constructions of a password-based authentication protocol that are configured to allow a user to register with and authenticate to an online service without the online service receiving a password or a deterministic function of the password of the user. When registering with an online service, a client computing device establishes a cryptographically strong random secret and stores an encryption of such secret with a data storage device. The storage device also never receives the password or a deterministic function of the password. When the user wishes to authenticate to the online service, the user employs her password to retrieve the encrypted secret from the storage device, decrypts such secret, and utilizes the decrypted secret to answer a cryptographically strong challenge provided to the user by the online service upon the online service receiving a username pertaining to such user.

Claims

1. A method that facilitates protecting a password of an individual from dictionary attacks, the method comprising the following computer-executable acts:

authenticating a user to an online service, comprising;

at a client computing device, receiving a username and password from the user that wishes to authenticate to the online service, wherein the username is configured to identify the user to the online service hosted by a server that is accessible to the client computing device by way of a network connection, wherein the client computing device refrains from transmitting the password or a deterministic function of the password to the server or a storage provider that is separate from the client computing device and the server;

transmitting the username from the client computing device to the server;

receiving at the client computing device from the server a challenge to authenticate the user;

receiving, from a storage device, first data that is processible by the client computing device to reply to the challenge from the server;

processing the first data to obtain a signature, wherein the password is unidentifiable from the signature; and

transmitting the signature to the server responsive to receipt of the challenge.

2. The method of claim 1, wherein the client computing device is one of a mobile telephone or a portable media player.

3. The method of claim 1, wherein the storage device is a mobile telephone.

4. The method of claim 1, further comprising:

registering the user with the online service, comprising;

executing a blind signature key generation algorithm to generate a blind signature key pair, wherein the blind signature key pair comprises a randomly generated blind signature key;

executing a digital signature key generation algorithm to generate a signature key pair, wherein the signature key pair comprises a randomly generated signature verification key and a randomly generated signing key;

executing a first hashing algorithm to generate a cryptographic hash of the password;

executing a blind signature on the cryptographic hash of the password using the blind signature key to generate a first blind signature;

hashing the first blind signature to generate a first key;

executing an encryption algorithm to encrypt the signing key utilizing the first key to generate ciphertext;

generating an identity that identifies the user, wherein the identity is based at least in part upon the username;

transmitting the identity, the ciphertext, and the blind signature key to the storage device; and

transmitting the username and the signature verification key to the server.

5. The method of claim 4, wherein authenticating the user to the online service further comprises:

generating the identity responsive to receiving the username and password from the user;

re-executing the first hashing function to regenerate the cryptographic hash of the password;

transmitting the identity to the storage device to cause the storage device to retrieve the blind signature key and the ciphertext that are indexed by the identity, and further causing the storage device to execute a blind signature algorithm to apply a blind signature to the cryptographic hash of the password using the blind signature key;

receiving the blind signature and the ciphertext from the storage device;

executing a hashing algorithm on the blind signature to regenerate the first key; and

executing a decryption algorithm of the ciphertext utilizing the cryptographic key to generate the signing key.

6. The method of claim 1, further comprising:

registering the user with the online service, comprising;

executing a blind signature key generation algorithm to generate a blind signature key pair, wherein the blind signature key pair comprises a randomly generated blind signature key;

executing a signature key generation algorithm to generate a signature key pair, wherein the signature key pair comprises a signature verification key and a signing key;

executing a first hashing algorithm to generate a cryptographic hash of the password;

executing a blind signature on the cryptographic hash of the password using the blind signature key to generate an identity;

executing an encryption algorithm to encrypt the signing key utilizing the cryptographic hash of the password to generate ciphertext, wherein the first data comprises the ciphertext;

transmitting the identity and the ciphertext to the storage device; and

transmitting the username, the signature verification key, and the blind signature key and to the server.

7. The method of claim 6, wherein authenticating the user to the online service further comprises:

re-executing the first hashing function to regenerate the cryptographic hash of the password;

causing the server to generate a blind signature for the cryptographic hash of the password utilizing the blind signature key;

receiving the blind signature from the server;

executing a cryptographic hashing algorithm on the blind signature to generate the identity;

transmitting the identity to the storage device to cause the storage device to retrieve the ciphertext that is indexed by the identity;

receiving the ciphertext from storage device;

executing a decryption algorithm on the ciphertext utilizing the cryptographic hash of the password to generate the signing key; and

signing the challenge provided by the server utilizing the signing key to generate the signature.

8. The method of claim 6, wherein authenticating the user to the online service further comprises:

re-executing the first hashing function to regenerate the cryptographic hash of the password;

causing the server to generate a blind signature for the cryptographic hash of the password utilizing the blind signature key;

receiving the blind signature from the server;

computing a cryptographic hash on the blind signature to generate the identity;

transmitting the identity to the storage device to cause the storage device to retrieve the ciphertext that is indexed by the identity, wherein a Private Information Retrieval protocol is utilized to locate the ciphertext;

receiving the ciphertext from storage device;

executing a decryption algorithm on the ciphertext utilizing a cryptographic hash of the password to generate the signing key; and

signing the challenge provided by the server utilizing the signing key to generate the signature.

9. The method of claim 1, further comprising:

registering the user with the online service, comprising;

executing a signature key generation algorithm to generate a signing key;

generating an identity;

executing a first hashing algorithm to generate a cryptographic hash of the password;

executing an encryption algorithm to encrypt the signing key utilizing the cryptographic hash of the password to generate ciphertext;

transmitting the identifier and the ciphertext to the storage device, wherein the storage device is a local storage device; and

transmitting the username, the signing key, and the identifier to the server.

10. The method of claim 1 configured for execution in an Internet browser executing on the client computing device.

11. The method of claim 1, wherein the storage device is a mobile computing device that is configured with cryptographic algorithms.

12. A system that facilitates executing a protocol that facilitates securing a user password from dictionary attacks, the system comprising the following computer-executable components:

a receiver component that receives an indication that a user wishes to authenticate with an online service hosted by a server, wherein the indication comprises a username and password of the user;

a transmitter component that transmits the username to the server;

a challenge receiver component that receives a challenge from the server, wherein the challenge requests a signature from a client computing device;

a transform component that executes a first cryptographic function on the password to retrieve a data packet from a storage device responsive to receipt of the challenge; and

a challenge answerer component that executes a second cryptographic function on the data packet to generate a signature, wherein the signature is secure against dictionary attacks by the online service, wherein the transmitter component transmits the signature to the server responsive to receipt of the challenge.

13. The system of claim 12, wherein the transform component resides on a client computing device, and wherein the first cryptographic algorithm is a cryptographic hash function.

14. The system of claim 12, wherein the storage device is a mobile telephone.

15. The system of claim 12, wherein the storage device is accessible by way of the Internet.

16. The system of claim 12 comprised by a personal computer.

17. The system of claim 12, further comprising an identity generator component that generates an identity that identifies the user and the online service, wherein the data packet is retrieved from the storage device through utilization of the identity.

18. The system of claim 12, further comprising a blind signature generator component that is configured to generate a blind signature key pair during a registration phase, wherein the blind signature key pair comprises a blind signature key and a blind verification key, and wherein the challenge answerer component executes the second cryptographic function through utilization of at least one of the blind signature key or the blind verification key.

19. The system of claim 12, wherein the challenge answerer component receives a cryptographic key, ciphertext, and a blind signature of a hash of the password, and utilizes the hash of the password to decrypt the ciphertext and retrieve a signing key to answer the challenge.

20. A computer-readable medium resident upon a mobile computing device comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a challenge from an online service with which a user wishes to authenticate, wherein the challenge is issued by the online service responsive to receipt of a username corresponding to the user;

receiving a password from the user that the user employs to authenticate to the online service;

executing a hash algorithm on the password to generate a cryptographic hash of the password;

decrypting ciphertext utilizing the hash of the password to generate a key, wherein the key is a randomly or pseudo-randomly generate key that is generated during a registration phase with the online service and the ciphertext is an encryption of the key utilizing the hash of the password;

signing the challenge using the key to generate a signature; and

responding to the challenge based at least in part upon the signature.