Pass-sequences

• US 9,137,238 B1
• Filed: 02/11/2011
• Issued: 09/15/2015
• Est. Priority Date: 08/06/2010
• Status: Active Grant

• Current Assignee: Security Technology LLC (Bjorn Markus Jakobsson)
• Original Assignee: RightQuestions, LLC
• Inventors: Jakobsson, Bjorn Markus
• Primary Examiner(s): Nalven, Andrew
• Assistant Examiner(s): RUPRECHT, CHRISTOPHER S
• Application Number:
  US13/025,403
• Time in Patent Office: 1,677 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/44 Program or device authentication
• CPC Class Codes: G06F 21/45 Structures or tools for the administration of authentication
• CPC Class Codes: G06F 21/46 by designing passwords or checking the strength of passwords
• 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/008 involving homomorphic encryption
• 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/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04W 12/06 Authentication

Abstract

Authentication techniques, and in particular, authentication techniques which can be used in conjunction with input constrained devices are described herein. A plurality of words is received. The received words are parsed. A credential is authenticated by determining a match based on information associated with at least one of the received words in the plurality.

Claims

1. A system, comprising:

a set of one or more interfaces configured to receive, from a device operated by a user, input provided by the user comprising;

a user identifier;

and a credential comprising a plurality of separately parseable words;

a set of one or more processors configured to;

parse the credential into a set of constituent words;

perform one or more of the following checks on the set of constituent words;

that each of the constituent words in the set is present in a dictionary;

that none of the constituent words in the set is a proper noun;

that none of the constituent words in the set is present in a blacklist;

that the credential includes at least a threshold number of constituent words;

that each individual word in the set is of at least a first threshold length;

that the set of constituent words are collectively of at least a second threshold length;

that the set of constituent words have at least a threshold entropy; and

that a measure of strength determined for the set of constituent words meets a minimum threshold;

in response to determining that the set of constituent words satisfy the one or more checks, generate at least one of;

a normalized credential at least in part by normalizing one or more of the set of constituent words, wherein normalizing comprises mapping the one or more constituent words to one or more equivalence classes, and wherein equivalence classes are defined such that deviations from constituent words will also be considered acceptable in the event that the deviations are provided by the user in a subsequent authentication process; and

a set of acceptable variants of the normalized credential that will also be considered acceptable in the event that an acceptable variant in the set of acceptable variants is provided by the user in a subsequent authentication process, wherein generating the set of acceptable variants comprises determining a plurality of different combinations of subsets of the constituent words of the normalized credential; and

store, in a credential set associated with the user identifier, a set of representations corresponding to at least some of the normalized credential and the set acceptable variants as stored enrolled credentials; and

a memory coupled to the set of one or more processors and configured to provide the set of one or more processors with instructions.

2. The system of claim 1, wherein each combination omits a different one of the constituent words.

3. The system of claim 1, wherein determining a measure of strength for the constituent words comprises performing at least one of a word frequency analysis and an n-gram frequency analysis.

4. The system of claim 1, wherein the set of one more processors is further configured to cause to be displayed a credential quality indicator based on the performed one or more checks, including a score, a color indicator, or specific feedback for the user for improving the credential.

5. The system of claim 1, wherein a deviation comprises a deviation from a particular form of a constituent word, including a tense, conjugation, or part of speech.

6. The system of claim 1, wherein:

the one or more equivalence classes comprises one or more conceptual equivalence classes; and

a deviation comprises substituting a word having a meaning similar to the constituent word.

7. The system of claim 1, wherein normalizing one or more of the constituent words further comprises one or more of:

converting the constituent words to lower-case; and

sorting the constituent words.

8. The system of claim 1, wherein generating the set of acceptable variants of the normalized credential further comprises confirming that a measure of strength determined for each of the plurality of combinations of subsets of the constituent words also meets the minimum threshold.

9. The system of claim 1, wherein an order of the stored enrolled credentials of the credential set is deterministic, such that a representation corresponding to the normalized credential appears first, followed by representations corresponding to each acceptable variant in the set of acceptable variants of the normalized credential.

10. The system of claim 1, wherein:

the set of representations corresponding to at least some of the normalized credential and the set of acceptable variants of the normalized credential are generated by performing a salted cryptographic hash function on at least some of the normalized credential and the set of acceptable variants of the normalized credential; and

a set of resulting hash values are stored in the credential set associated with the user identifier as the set of representations, along with a set of corresponding random salt values.

11. A system, comprising:

a set of one or more interfaces configured to receive, from a device operated by a user, input provided by the user comprising;

a user identifier; and

a credential comprising a plurality of separately parseable words;

a set of one or more processors configured to;

parse the credential into a set of constituent words;

access a credential set associated with the user identifier, stored during a previous enrollment process, comprising a set of representations corresponding to a set of stored enrolled credentials including at least some of a normalized credential and a set of acceptable variants of the normalized credential, wherein the set of acceptable variants comprise different combinations of subsets of the constituent words in the normalized credential; and

authenticate the received credential by performing a match, wherein performing the match comprises;

normalizing one or more of the set of constituent words to generate a normalized received credential to be verified, wherein normalizing comprises mapping the one or more constituent words to one or more equivalence classes, and wherein equivalence classes are defined such that deviations from constituent words previously provided by the user during the previous enrollment process will also be considered acceptable;

comparing one or more representations corresponding to the normalized received credential to be verified to the set of representations corresponding to the set of stored enrolled credentials;

determining whether one of the one or more representations corresponding to the normalized received credential to be verified matches one of the set of representations corresponding to the set of stored enrolled credentials based on information associated with the constituent words; and

grant the user access to a resource in the event that the match is determined to be successful; and

a memory coupled to the set of one or more processors and configured to provide the set of one or more processors with instructions.

12. The system of claim 11, wherein each combination omits a different one of the constituent words.

13. The system of claim 11, wherein:

one or more of an auto-correct function and an auto-complete function is active on the user device during input of the credential;

the auto-correct function suggests valid words in order to avoid misspellings; and

the auto-complete function suggests likely words when sufficient parts have been input to make a predictable or near-predictable choice.

14. The system of claim 13, wherein:

receiving input provided by the user further comprises tracking a number of characters typed by the user in conjunction with entering the credential; and

authenticating the credential further comprises;

determining a number of key strokes required to input at least one of the constituent words; and

determining whether the user is pasting in the credential or whether the user device has undesirable auto-completion settings.

15. The system of claim 11, wherein:

the input provided by the user is spoken;

parsing the credential comprises mapping at least a portion of the spoken input to a constituent word;

the one or more equivalence classes comprises one or more homophonic equivalence classes; and

the one or more representations of the normalized credential to be verified comprise phonetic descriptions of the constituent words.

16. The system of claim 11, wherein a deviation comprises a deviation from a particular form of a constituent word, including a tense, conjugation, or part of speech.

17. The system of claim 11, wherein:

the one or more equivalence classes comprises one or more conceptual equivalence classes; and

a deviation comprises substituting a word having a meaning similar to a constituent word.

18. The system of claim 11, wherein normalizing one or more of the constituent words further comprises one or more of:

converting all of the constituent words to lower-case; and

sorting the constituent words.

19. The system of claim 11, wherein two constituent words are considered to match in the event that the two constituent words are related according to a metric or the two constituent words are both present in an equivalence class.

20. The system of claim 11, wherein:

a number of words included in the credential provided by the user during the authentication process is greater than a number of words included in the credential previously provided by the user during the enrollment process; and

performing a match further comprises;

removing a different one of the constituent words prior to comparing the representations; and

determining that a match exists for all but one of the constituent words.

21. The system of claim 11, wherein authenticating the credential further comprises displaying a success score indicator and suggestions for improving the success score in a subsequent authentication process, including suggesting that the user speak slower or avoid background noise in the event that the input provided by the user was spoken, suggesting that the user enter words more cautiously in the event that the input provided by the user was typed, or suggesting that the user replace or update the credential.

22. The system of claim 11, wherein:

the one or more representations corresponding to the normalized received credential to be verified are generated by performing one or more salted cryptographic hash functions on the normalized credential to be verified, wherein one or more random salt values, stored along with one or more corresponding hash values as the set of representations of the set of stored enrolled credentials, are extracted from the credential set; and

performing a match further comprises;

comparing one or more resulting hash values to the one or more hash values stored in the credential set; and

determining whether one of the one or more resulting hash values matches one of the stored hash values.

23. A method, comprising:

receiving, from a device operated by a user, input provided by the user comprising;

a user identifier;

and a credential comprising a plurality of separately parseable words;

parsing the credential into a set of constituent words;

performing one or more of the following checks on the set of constituent words;

that each of the constituent words in the set is present in a dictionary,

that none of the constituent words in the set is a proper noun;

that none of the constituent words in the set is present in a blacklist;

that the credential includes at least a threshold number of constituent words;

that each individual word in the set meets is of a first threshold length;

that the set of constituent words are collectively of a second threshold length;

that the set of constituent words have at least a threshold entropy; and

that a measure of strength determined for the constituent words meets a minimum threshold;

in response to determining that the set of constituent words satisfy the one or more checks, generating, using a set of one or more processors, at least one of;

a normalized credential at least in part by normalizing one or more of the set of constituent words, wherein normalizing comprises mapping the one or more constituent words to one or more equivalence classes, and wherein equivalence classes are defined such that deviations from constituent words will also be considered acceptable in the event that the deviations are provided by the user in a subsequent authentication process; and

a set of acceptable variants of the normalized credential that will also be considered acceptable in the event that an acceptable variant in the set of acceptable variants is provided by the user in a subsequent authentication process, wherein generating the set of acceptable variants comprises determining a plurality of different combinations of subsets of the constituent words of the normalized credential; and

storing, in a credential set associated with the user identifier, a set of representations corresponding to at least some of the normalized credential and the set acceptable variants as stored enrolled credentials.

24. A method, comprising:

receiving, from a device operated by a user, input provided by the user comprising;

a user identifier; and

a credential comprising a plurality of separately parseable words;

parsing the credential into a set of constituent words;

accessing a credential set associated with the user identifier, stored during a previous enrollment process, comprising a set of representations corresponding to a set of stored enrolled credentials including at least some of a normalized credential and a set of acceptable variants of the normalized credential, wherein the set of acceptable variants comprise different combinations of subsets of the constituent words in the normalized credential; and

authenticating, using a set of one or more processors, the received credential by performing a match, wherein performing the match comprises;

normalizing one or more of the set of constituent words to generate a normalized received credential to be verified, wherein normalizing comprises mapping the one or more constituent words to one or more equivalence classes, and wherein equivalence classes are defined such that deviations from constituent words previously provided by the user during the previous enrollment process will also be considered acceptable;

comparing one or more representations corresponding to the normalized received credential to be verified to the set of representations corresponding to the set of stored enrolled credentials;

and determining whether one of the one or more representations corresponding to the normalized received credential to be verified matches one of the set of representations corresponding to the set of stored enrolled credentials based on information associated with the constituent words; and

granting the user access to a resource in the event that the match is determined to be successful.