Granted Patent B1

US 8,254,571 · App. 11/963,726 · Granted Aug 28, 2012

Abstract

Claims (87)

1. A method for deriving a cryptographic key using a computer-implemented halting key derivation function that has a state, comprising:

obtaining a password from a user;

obtaining a random string, wherein the password and random string form inputs to the computer-implemented halting key derivation function;

in a loop, iteratively modifying the state of the halting key derivation function using a scrambling function;

receiving user input to halt the loop;

in response to the user input to halt the loop, halting the loop and generating verification information based on the state of the halting key derivation function when the loop is halted; and

generating a cryptographic key based on the state of the halting key derivation function when the loop is halted.

2. The method defined in claim 1 further comprising initializing the state of the halting key derivation function using the password obtained from the user and the random string.

3. The method defined in claim 1 further comprising initializing a running hash value by applying a hash function to the password and the random string.

4. The method defined in claim 1 wherein modifying the state of the halting key derivation function using the scrambling function comprises generating an element in an array of values.

5. The method defined in claim 1 wherein modifying the state of the halting key derivation function using the scrambling function comprises generating an element in an array of values using a hash function.

6. The method defined in claim 1 further comprising:

initializing a running hash value by applying a hash function to the password and the random string; and

initializing an array of running hash values using the running hash value that was initialized by applying the hash function to the password and the random string, wherein modifying the state of the halting key derivation function using the scrambling function comprises generating an element in the array of running hash values.

7. A method for deriving and using a cryptographic key on a computer having a user interface, a processor, and storage, wherein the cryptographic key is derived using a halting key derivation function setup process having a state, comprising:

obtaining a password from a user through the user interface;

obtaining a random string, wherein the password and the random string form inputs to the halting key derivation function;

in a loop, iteratively modifying the state of the halting key derivation function setup process by using the processor to apply a hash function;

with the user interface, receiving user input from the user to halt the loop; and

in response to the user input to halt the loop, halting the loop and generating a cryptographic key based on the state of the halting key derivation function when the loop is halted.

8. The method defined in claim 7 further comprising:

when the loop is halted by the user, generating verification information with the processor that is based on the state of the halting key derivation function when the loop is halted.

9. The method defined in claim 7 wherein the processor contains a plurality of cores, the method further comprising:

instantiating a separate instance of the halting key derivation function on each of the plurality of cores, wherein each instance has a respective running hash value that is generated using a hash function.

10. The method defined in claim 7 wherein the processor contains a plurality of cores, the method further comprising:

instantiating a separate instance of the halting key derivation function on each of the plurality of cores, wherein each instance has a respective running hash value that is generated using a hash function; and

updating the state of the halting key derivation function setup process by applying a hash function to each of the respective running hash values.

11. The method defined in claim 7 further comprising initializing a running hash value by applying the hash function to the password and the random string.

12. The method defined in claim 7 further comprising:

initializing a running hash value by applying the hash function to the password and the random string, wherein iteratively modifying the state of the halting key derivation function setup process comprises applying the hash function to at least the running hash value.

13. A computer-implemented method for deriving a cryptographic key using a halting key derivation function that has a state, comprising:

obtaining a trial password from a user through a computer user interface;

obtaining verification information that is indicative of a final halting key derivation function state associated with a halting key derivation function setup process and that is indicative of a random string obtained by the halting key derivation function setup process;

in a loop, iteratively modifying the state of the halting key derivation function using a scrambling function;

while in the loop, determining whether the current iteratively modified state of the halting key derivation function matches the final halting key derivation function state produced by the halting key derivation function setup process;

if there is no match between the current iteratively modified state and the final halting key derivation function state, continuing in the loop; and

if there is a match between the current iteratively modified state and the final halting key derivation function state, generating the cryptographic key.

14. The method defined in claim 13 further comprising initializing a running hash value by scrambling the trial password and the random string.

15. The method defined in claim 13 further comprising:

initializing a running hash value by scrambling the trial password and the random string, wherein iteratively modifying the state of the halting key derivation function comprises updating the running hash value.

16. The method defined in claim 13 further comprising:

initializing a running hash value from the trial password and the random string, wherein iteratively modifying the state of the halting key derivation function comprises updating the running hash value by scrambling the running hash value and an element from an array of intermediate hash values.

17. The method defined in claim 13 further comprising:

while in the loop, using the computer user interface to provide the user with a retry opportunity in which the loop is exited and a new trial password is obtained from the user.

18. The method defined in claim 13 further comprising:

while in the loop, using the computer user interface to provide the user with an opportunity to abort the loop.

19. A method for deriving and using a cryptographic key on a computer having a user interface and a processor having a plurality of cores, comprising:

obtaining a password from a user through the user interface;

obtaining a random string;

instantiating a separate instance of a key derivation function on each of the plurality of cores, wherein the password and the random string form inputs to each instance of the key derivation function and wherein each instance of the key derivation function has a respective running hash value that is generated using a hash function;

in a loop, iteratively updating the running hash value of each instance of the key derivation function;

with the user interface, receiving user input from the user to halt the loop; and

in response to the user input to halt the loop, halting the loop and generating a cryptographic key based on the updated running hash value of each instance of the key derivation function.

20. The method defined in claim 19 , wherein the separate instances of the key derivation function collectively define an associated common state, the method further comprising:

updating the common state of the key derivation function by applying the hash function to the running hash values; and

in response to the user input to halt the loop, generating verification information from updated common state of the key derivation function and the random string.

21. A method for deriving and using a cryptographic key on a computer having a user interface and a processor having a plurality of cores, comprising:

obtaining a password from a user through the user interface;

obtaining verification information that is indicative of a final halting key derivation function state associated with a halting key derivation function setup process and that is indicative of a random string obtained by the halting key derivation function setup process;

instantiating a separate instance of a key derivation function on each of the plurality of cores, wherein the password and the random string form inputs to each instance of the key derivation function and wherein each instance of the key derivation function has a respective running hash value that is generated using a hash function;

in a loop, iteratively updating the running hash value of each instance of the key derivation function;

while in the loop, determining whether a common state of the key derivation function matches the final halting key derivation function state produced by the halting key derivation function setup process, wherein the common state of the key derivation function is based on the running hash values;

if there is no match between the common state and the final halting key derivation function state, continuing in the loop; and

if there is a match between the common state and the final halting key derivation function state, generating the cryptographic key.

22. A method for deriving a cryptographic key using a computer-implemented halting key derivation function that has a state, comprising:

obtaining a password from a user;

obtaining a complexity parameter;

obtaining a random string, wherein the password, the complexity parameter, and random string form inputs to the computer-implemented halting key derivation function; and

generating from the password and the random string a cryptographic key and verification information, wherein:

the verification information alone is not indicative of either the complexity parameter or the cryptographic key; and

the cryptographic key is reproducible from the verification information and the password using a computation of complexity indicated by the complexity parameter.

23. The method defined in claim 22 , wherein obtaining the complexity parameter comprises obtaining the complexity parameter from the user before generating the cryptographic key.

24. The method defined in claim 22 , wherein obtaining the complexity parameter comprises obtaining a time limit for the computer-implemented halting key derivation function.

25. The method defined in claim 22 , wherein obtaining the complexity parameter comprises obtaining the complexity parameter from the user through a user interface while generating the cryptographic key.

26. A computer-implemented method for deriving a cryptographic key using a halting key derivation function that has a state, comprising:

obtaining a trial password from a user through a computer user interface;

obtaining verification information that is indicative of a final halting key derivation function state associated with a halting key derivation function setup process and that is indicative of a random string obtained by the halting key derivation function setup process;

in a loop, performing a password verification computation of iteratively increasing complexity, wherein the verification computation takes the trial password and the verification information as inputs, and has a computational state;

while in the loop, using the state of the password verification computation to determine whether the trial password is valid with respect to the verification information produced by the halting key derivation function setup process;

continuing in the loop until the trial password is determined to be valid while performing the password verification computation; and

when it is determined that the trial password is valid, generating the cryptographic key based on the computational state of the password verification process.

27. The method defined in claim 26 further comprising:

while in the loop, using the computer user interface to provide the user with a retry opportunity in which the loop is exited and a new trial password is obtained from the user.

28. The method defined in claim 26 further comprising:

while in the loop, using the computer user interface to provide the user with an opportunity to abort the loop.

29. The method defined in claim 26 further comprising:

stopping the loop when a limit specified by a complexity parameter is reached.

Assignments (11)