Mitigating dictionary attacks on password-protected local storage

• US 8,108,683 B2
• Filed: 08/10/2006
• Issued: 01/31/2012
• Est. Priority Date: 08/10/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Canetti, Ran, Halevi, Shai, Steiner, Michael
• Primary Examiner(s): Zee, Edward
• Application Number:
  US11/501,831
• Publication Number:
  US 20080049939A1
• Time in Patent Office: 2,000 Days
• Field of Search: 726/2, 726/27, 726/28, 713/182, 713/183, 380 44- 47
• US Class Current: 713/182
• 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/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• 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

Abstract

The invention includes a method for key creation and recovery based on solutions to puzzles solvable by humans and not computers. In some exemplary embodiments, the key is created and recovered based on the solution(s) in conjunction with the password entered by the user. The puzzle(s) is selected based on the password used by the user from a puzzle database containing multiple puzzles that is greater in number to the number of puzzles used in conjunction with a particular password.

Claims

1. A method comprising:

receiving on a computer a password from a user;

selecting at least one puzzle from a puzzle database based on the received password;

for each selected puzzle

providing the puzzle to the user on a computer, and

receiving a solution for the puzzle from the user on a computer; and

generating a key on a computer based at least on the entirety of at least one solution, wherein said key is a cryptographic key.

2. The method according to claim 1, further comprising using the key for encryption of data.

3. The method according to claim 2, further comprising using the key to authenticate the data being encrypted.

4. The method according to claim 1, further comprising using the key for decryption of data encrypted with the key.

5. The method according to claim 1, wherein creating a key is based on the entirety of at least one solution and the received password.

6. The method according to claim 1, wherein at least eight puzzles are selected from the puzzle database.

7. The method according to claim 1, wherein selecting at least one puzzle includes expanding the received password into a predetermined number of indices corresponding to particular puzzles within the puzzle database.

8. The method according to claim 1, further comprising:

receiving information other than the password from the user, and

wherein selecting at least one puzzle is based on the received password and information provided by the user.

9. The method according to claim 1, wherein at least one of selecting and generating uses a salt.

10. The method according to claim 1, further comprising generating puzzles for the puzzle database.

11. The method according to claim 10, further comprising:

receiving information other than the password from the user, and

wherein generating puzzles is based on information received from the user.

12. The method according to claim 1, further comprising generating human-only solvable puzzles for the puzzle database.

13. The method according to claim 1, wherein generating includes using a fuzzy extractor.

14. A method comprising:

receiving on a computer a password from a user;

selecting on a computer at least four puzzles indexed with the password from a puzzle database having puzzles solvable by a human and not solvable by a non-human entity;

for each selected puzzle

providing the puzzle to the user, and

receiving on a computer a solution for the puzzle from the user;

generating on a computer a key based on at least the received solutions; and

using the key to encrypt files on a computer, wherein retrieving includes expanding the received password into indices to provide the index to puzzles in the puzzle database.

15. The method according to claim 14, wherein retrieving includes expanding the received password into indices to provide the index to puzzles corresponding to particular puzzles within the puzzle database.

16. A computer program product comprising a non-transitory computer useable medium, including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

generate a key including

receive a password from a user,

compute indices based on the received password,

select at least one puzzle from a puzzle database based on the computed indices,

for each selected puzzle, query the user for a solution,

compute a cryptographic key based on the received at least one solution and the received password, and

discard the solutions.

17. A method comprising:

receiving on a computer information including a password from a user;

generating one or more puzzles on a computer based on at least some of the received information;

for each generated puzzle

providing the puzzle to the user on a computer, and

receiving on a computer a solution for the puzzle from the user; and

generating on a computer a cryptographic key based at least on the entirety of at least one solution.

18. The method according to claim 17, wherein generating one or more puzzles uses a salt.

19. The method according to claim 17, further comprising selecting one or more puzzles from at least one of a puzzle database and generated puzzles.