US20150172272A1 - Distributed storage of password data - Google Patents

Abstract

To better protect passwords used for authentication or for generating cryptographic keys, methods and apparatuses may store password data on multiple storage devices. For each password, each subset of multiple distinct subsets of a data set may be sufficient to authenticate a trial password or generate a cryptographic key. A first subset enables a quick method for authenticating the trial password or generating the cryptographic key. The first subset may be stored in a distributed manner to make it more difficult to steal. If the first subset is unavailable, then a second subset, which is stored centrally, may be used to authenticate the trial password or generate the cryptographic key, but with a method that is an order of magnitude slower than the quick method. Brute force and dictionary attacks based on the second subset may take much longer than such attacks based on the quick method.

Description

BACKGROUND
• A host computer system used by multiple entities (people or other devices) usually maintains accounts for the entities. To access data owned by, and services provided to, an account, an entity must first prove his/her/its identity. The entity, also called the “user,” may be a person, a physical device, or a collection of software. A process by which the user proves his/her/its identity is called “authentication.”
• One of the most common methods of authentication is password authentication: verifying that the user has provided a correct password. When the user sets up his/her/its account, he/she/it specifies a new password—usually a string of characters that may include letters, digits, symbols and control characters. The host computer system stores information about the password sufficient to verify whether or not a trial password, provided by the user at a later time, is correct (is identical to the password). The information stored about the password that is used to verify whether or not the trial password is correct is called a “password verification data set.”
• In the early days of computing, the password verification data set was the password itself. To authenticate the user, the computer system obtained the trial password from the user and compared it to the password stored in the password verification data set. This password authentication method is simple but has a major flaw: a person who can view the password stored in the password verification data set can use the password to impersonate the user.
• An early improvement to the password verification data set was storing an encrypted version of the user's password instead of the password itself. When creating the user's account, the host computer system applied a “one-way function” to the new password, and an output of the one-way function was stored. The one-way function modifies its input in a way that is very difficult to reverse; from an output of the one-way function, it is hard to determine what its input was. The output of the one-way function is called a “hash.” Looking at the hash derived from the user's password, it is not easy to determine what user's the password is.
• As host computer systems were entrusted with more important data and services, the rewards for determining the password of another user grew. A method for determining another user's password from a password verification data set became known as “cracking” or an “attack.” Today, a password attack generally starts when an attacker gains access to (steals) a password verification data set of a targeted user. The attacker then programs his/her own computers to perform a same password authentication method that the host computer system uses, and the attacker attempts to authenticate many trial passwords until the correct password is found. Three common password attacks are dictionary attacks, brute force attacks and rainbow table attacks. A dictionary attack tries to authenticate all passwords in a list of likely passwords. A brute force attack tries to authenticate all possible passwords less than a certain length (possibly with other restrictions). A rainbow table attack uses a large, pre-computed table of passwords and hashes to speed up the process of finding the correct password.
• A cryptographic key can be used, in conjunction with an encryption method, to encrypt and decrypt a data set. If the cryptographic key is generated from a password, the cryptographic key may be vulnerable to some of the attacks described above.
• To make password attacks more difficult, computer scientists invented the concept of “salt.” A salt is a string of characters or bits that varies from user to user and is mixed with the user's new password and trial password before applying the one-way function. The password verification data set was expanded to include both the hash and the salt. The salt is usually randomly generated when the user's account is created or when the user changes his/her/its password.
• Other techniques for resisting password attacks have been suggested but are not widely used. For example, “password strengthening” adds random bits to the user's password before applying the one-way function to create the hash that is stored in the password verification data set. The random bits are not stored in the password verification data set or in any data storage device. If 20 random bits are added, then an attacker has to perform one million (two raised to the power of 20) times as many computations, on average, to determine the correct password. A disadvantage of password strengthening is that authenticating a legitimate user's password also takes longer. Another technique, “password stretching,” makes the one-way function more time-consuming to compute, for example by applying the one-way function repeatedly in a loop. Password stretching also slows down both password attacks and the authentication of a legitimate user's password.
• An important weakness of most password authentication methods is that they store password verification data sets of many users in one place, typically in a single file or database. Numerous times, hackers have broken into host computer systems and stolen the data in these files or databases. The password verification data sets stored in a central location may be considered vulnerable.
• Another proposed technique for resisting password attacks is distributing the password verification data set among a set of cooperating computers. To successfully attack a host computer system that uses this technique, the attacker must gain access to multiple cooperating computers, a more difficult task than gaining access to a single host computer. Implementation of the proposed technique is complex and may not protect the host computer system against an attacker who gains root access to one or more of the cooperating servers.
• Other authentication methods may achieve greater security by obtaining other types of information from the user besides, or in addition to, the password. For example, bio-metric authentication verifies the user's identity from a unique attribute of the user such as a fingerprint. Authentication can also be based on verifying that the user has an object, such as a smart card or a security token. Multi-factor authentication obtains several types of information from the user, such as a password and data from a smart card, or a password and a fingerprint. Multi-factor authentication may offer greater security than password authentication but has several disadvantages: 1) the additional factor(s) usually require additional hardware, such as a fingerprint reader or a smart card, that has a cost, 2) presenting the additional information may inconvenience the user every time he/she/it logs in, and 3) if the user loses the smart card, or if the fingerprint reader breaks, then the user cannot log in at all.
• The other techniques for resisting password attacks may be used in conjunction with password verification data sets and password authentication methods described in this disclosure. The password verification data sets and password authentication methods described herein may also be used with multi-factor authentication as long as one of the authentication factors is a password.
• A different approach to authentication is to challenge the user with security questions in addition to the password. Before or after the user enters his/her/its password, the host computer system may ask the user one or more security questions that only the user (hopefully) can answer correctly. Incorrect answers to one or more security questions may cause authentication to fail. In some implementations, the security questions are asked only if the user does not have an expected data element, such as a cookie written on the user's hard drive during a previous session. Requesting answers to security questions may also be used as an alternative to password authentication if the user claims to have forgotten his/her/its password.
• Multi-factor authentication and requesting answers to security questions may be used in addition to password authentication, but are not password authentication methods as defined herein.
SUMMARY
• This Summary is provided to introduce a selection of concepts in a simplified form that is further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.
• In various embodiments, a method implemented by a processing device is provided for generating password verification data sets. Using the method, password verification data sets may be generated based, at least partly, on a password. In these embodiments, the password verification data set may contain two or more distinct subsets, each of which may be sufficient for performing password authentication. In some embodiments, when a first subset of the password verification data set is available, a first password authentication process may be performed with respect to a provided trial password. When the first subset of the password verification data set is not available, a second password authentication process may be performed based on a second subset of the password verification data set and the provided trial password. The first password authentication process using the first subset may be much faster than the second password authentication process using the second subset.
• In other embodiments, a method is provided for authenticating a password. A trial password may be obtained from a user. Some elements of a password verification data set may be obtained from a first storage device. Other elements of the password verification data set, if available, may be obtained from a second storage device. When the other elements are available, a processing device performs a first calculation based on the trial password, the some elements and the other elements to authenticate the trial password. When the other elements are not available, a second calculation is performed based on the trial password and the some elements to authenticate the trial password. The first calculation may be different from the second calculation and the first calculation is performed in at most half an amount of time used to perform the second calculation.
• In other embodiments, a method implemented by a processing device is provided for generating cryptographic keys. Using the method, cryptographic key data sets may be generated based, at least partly, on a password. In these embodiments, the cryptographic key data set may contain two or more distinct subsets, each of which may be sufficient to generate the cryptographic key based on a trial password that is identical to the password. In some embodiments, when a first subset of the cryptographic key data set is available, a first cryptographic key generation process may be performed with respect to a provided trial password. When the first subset of the cryptographic key data set is not available, a second cryptographic key generation process may be performed based on a second subset of the cryptographic key data set and the provided trial password. The first cryptographic key generation process using the first subset may be much faster than the second cryptographic key generation process using the second subset.
• In other embodiments, a method is provided for generating a cryptographic key. A trial password may be obtained from a user. Some elements of a cryptographic key data set may be obtained from a first storage device. Other elements of the cryptographic key data set, if available, may be obtained from a second storage device. When the other elements are available, a processing device performs a first calculation based on the trial password, the some elements and the other elements to generate the cryptographic key. When the other elements are not available, a second calculation is performed based on the trial password and the some elements to generate the cryptographic key. The first calculation may be different from the second calculation and the first calculation is performed in at most half an amount of time used to perform the second calculation.
• In additional embodiments, at least one processing device is provided. The at least one processing device may include one or more processors and one or more memories connected to the one or more processors. The one or more memories may have instructions stored therein for the one or more processors to perform a method. The method may include generating and storing a password verification data set, which may be used during a password authentication process based, at least partly, on a password. The password verification data set may include at least two distinct subsets, each of which may be sufficient to perform the password authentication process. In other embodiments, the method may include generating and storing a cryptographic key data set, which may be used during a cryptographic key generation process based, at least partly, on the password. The cryptographic key data set may include at least two distinct subsets, each of which may be sufficient to perform the cryptographic key generation process.
• Various embodiments disclose numerous ways to generate and store password verification data sets and cryptographic key data sets that make cracking passwords more difficult but, in most cases, do not slow down the password authentication process and the cryptographic key generation process for legitimate users or make the processes inconvenient.
• Unlike multi-factor authentication, the password authentication processes used in various embodiments do not require special hardware devices. For example, in one embodiment, a user who creates a web site account may have some data elements of his/her password verification data set stored as cookies on his/her own hard disk drive. (In this embodiment, the user's hard disk drive serves as the second storage device.) The user may not perform any additional steps besides providing a user name and trial password to log in; the cookies containing the password verification data set elements are transmitted to a processing device that hosts the web site in a manner that is transparent to the user. The user may not notice any difference between conventional password authentication methods and the password authentication methods of the various embodiments. Furthermore, if the user's cookies are not available, he/she can still log in. The only difference is that a password authentication process employed takes longer than if the cookies were available. In some embodiments, when the user logs in without the cookies, the cookies are reconstructed and stored anew on the user's hard disk drive so that, on subsequent login attempts, the cookies will again be available and an employed password authentication process will be quicker than the password authentication process employed when the cookies were not available. Depending on the embodiment, the reconstruction of the missing password verification data set elements (cookies) and their re-storage on the user's hard disk drive may occur without any effort by the user.
DRAWINGS
• In order to describe the manner in which the above-recited and other advantages and features can be obtained, a more particular description is described below and will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understand that these drawings depict only typical embodiments and are not therefore to be considered to be limiting of its scope. Implementations will be described and explained with additional specificity and detail through the use of the accompanying drawings.
• FIGS. 1-5 illustrate five exemplary operating environments consistent with the subject matter of this disclosure.
• FIG. 6 is a functional block diagram of an exemplary processing device that that may be used to implement apersonal processing device104 ofFIG. 1, ahost processing device204 ofFIG. 2, aclient processing device402 ofFIG. 4, the processing devices comprising an attackerprocessing device array502 ofFIG. 5, or all of these processing devices.
• FIGS. 7-10 constitute a storyboard illustrating an exemplary process for generating a password verification data set in astandalone operating environment100 ofFIG. 1.
• FIGS. 11-14 constitute a storyboard illustrating an exemplary successful password authentication process in thestandalone operating environment100 ofFIG. 1 when a remote password verification data subset954 (RPVDS) depicted inFIGS. 9-10 is available.
• FIGS. 15-18 constitute a storyboard illustrating an exemplary successful password authentication process in thestandalone operating environment100 ofFIG. 1 when the remote password verification data subset954 (RPVDS) depicted inFIGS. 9-10 is not available.
• FIGS. 19-22 constitute a storyboard illustrating an exemplary process for generating a password verification data set in anetwork operating environment200 ofFIG. 2.
• FIGS. 23-26 constitute a storyboard illustrating a successful password authentication process in thenetwork operating environment200 ofFIG. 2 when the remote password verification data subset954 (RPVDS) depicted inFIGS. 17-18 is available.
• FIGS. 27-30 constitute a storyboard illustrating a successful password authentication process in thenetwork operating environment200 ofFIG. 2 when the remote password verification data subset954 (RPVDS) depicted inFIGS. 17-18 is not available.
• FIG. 31 illustrates a first exemplary passwordverification data set3150.
• FIG. 32 is a flowchart that illustrates amethod3290 for generating the passwordverification data set3150 ofFIG. 31.
• FIG. 33 is a flowchart that illustrates an exemplary quickpassword authentication method3390 using the passwordverification data set3150 ofFIG. 31.
• FIG. 34 is a flowchart that illustrates an exemplary slowpassword authentication method3490 using the passwordverification data set3150 ofFIG. 31.
• FIG. 35 illustrates a second exemplary passwordverification data set3550.
• FIG. 36 is a flowchart that illustrates amethod3690 for generating the passwordverification data set3550 ofFIG. 35.
• FIG. 37 is a flowchart that illustrates an exemplary quickpassword authentication method3790 using the passwordverification data set3550 ofFIG. 35.
• FIG. 38 is a flowchart that illustrates an exemplary slowpassword authentication method3890 using the passwordverification data set3550 ofFIG. 35.
• FIG. 39 illustrates a third exemplary passwordverification data set3950.
• FIG. 40 is a flowchart that illustrates amethod4090 for generating the passwordverification data set3950 ofFIG. 39.
• FIG. 41 is a flowchart that illustrates an exemplary quick password authentication method4190 using the passwordverification data set3950 ofFIG. 39.
• FIG. 42 is a flowchart that illustrates an exemplary slowpassword authentication method4290 using the passwordverification data set3950 ofFIG. 39.
• FIG. 43 illustrates a fourth exemplary passwordverification data set4350.
• FIG. 44 is a flowchart that illustrates amethod4490 for generating the passwordverification data set4350 ofFIG. 43.
• FIG. 45 is a flowchart that illustrates an exemplary quickpassword authentication method4590 using the passwordverification data set4350 ofFIG. 43.
• FIG. 46 is a flowchart that illustrates an exemplary slowpassword authentication method4690 using the passwordverification data set4350 ofFIG. 43.
• FIG. 47 illustrates a fifth exemplary passwordverification data set4750.
• FIG. 48 is a flowchart that illustrates amethod4890 for generating the passwordverification data set4750 ofFIG. 47.
• FIG. 49 is a flowchart that illustrates an exemplary quickpassword authentication method4990 using the passwordverification data set4750 ofFIG. 47.
• FIG. 50 is a flowchart that illustrates an exemplary slowpassword authentication method5090 using the passwordverification data set4750 ofFIG. 47.
• FIG. 51 illustrates a sixth exemplary passwordverification data set5150.
• FIG. 52 is a flowchart that illustrates amethod5290 for generating the passwordverification data set5150 ofFIG. 51.
• FIG. 53 is a flowchart that illustrates an exemplary quickpassword authentication method5390 using the passwordverification data set5150 ofFIG. 51.
• FIG. 54 is a flowchart that illustrates an exemplary slowpassword authentication method5490 using the passwordverification data set5150 ofFIG. 51.
• FIG. 55 illustrates an exemplary cryptographickey data set5550.
• FIG. 56 is a flowchart that illustrates amethod5690 for generating the cryptographic key data set5550 ofFIG. 55.
• FIG. 57 is a flowchart that illustrates an exemplary quick cryptographickey generation method5790 using the cryptographic key data set5550 ofFIG. 55.
• FIG. 58 is a flowchart that illustrates an exemplary slow cryptographickey generation method5890 using the cryptographic key data set5550 ofFIG. 55.
• FIG. 59 is a flowchart that illustrates an exemplary dictionary/bruteforce attack method5990 using the passwordverification data set4350 ofFIG. 43.
DETAILED DESCRIPTION
• The following terms are used in the Detailed Description consistent with their usual meanings.
• • user name: A name provided by a user to identify an account belonging to him/her/it.
  • new password: A password provided by a user when the user creates an account, when the user changes a password of his/her/its existing account, or when the user creates a cryptographic key.
  • trial password: A password provided by a user when the user attempts to log in to an account or when the user regenerates a cryptographic key.
  • correct password: A password identical to a most recent new password that a user provided when creating his/her/its account, when changing the password of his/her/its account, or when creating a cryptographic key.
  • host processing device: A processing device, or a collection of processing devices, that creates and provides access to accounts for one or more users, and/or encrypts and decrypts data sets.
  • password authentication data set: A set of data elements, including either a user name and a new password, or a user name and a trial password, provided by a user to establish or confirm his/her/its identity.
  • password authentication: A processing device implemented process performed by a host processing device that determines whether or not to grant a user access to an account based on the user name and the trial password provided by the user.
  • password verification data set: A set of data elements that enables a host processing device to determine whether or not a trial password provided by a user is identical to the user's correct password.
  • one-way function: A method that converts an input into an output in such a way that reversing the method's action (determining the input from the output) is very difficult.
  • hash: An output of a one-way function.
  • salt: A string of characters or bits, that may differ from user to user, and that may be combined with other data elements before applying a one-way function. (In some embodiments, the salt is combined with a new password or a trial password before applying the one-way function.)
  • temp value: A data element generated during a computation that is not stored permanently.
  • cryptographic key: A string of characters or bits that may be used, in conjunction with an encryption method, to encrypt or decrypt a data set.
• The following terms, although not in common usage, make it easier to describe the invention:
• • password verification data set generation method: A processing device implemented method that generates a password verification data set from a password.
  • quick password authentication method: A processing device implemented method that accepts a trial password and a first subset of a password verification data set as inputs, and may return a success indicator if the trial password is identical to a correct password, and may return a failure indicator if the trial password is not identical to the correct password.
  • slow password authentication method: A processing device implemented method that accepts a trial password and a second subset of the password verification data set as inputs, may return a success indicator if the trial password is identical to a correct password, may return a failure indicator if the trial password is not identical to the correct password, and uses at least twice as much time to return the success indicator or the failure indicator as an amount of time that a quick password authentication method uses.
  • quick password verification data subset: A subset of a password verification data set that may be provided as an input to a quick password authentication method.
  • slow password verification data subset: A subset of a password verification data set that may be provided as an input to a slow password authentication method.
  • central storage device: A storage device that is permanently connected to a processing device is considered to be a central storage device from a perspective of the processing device.
  • central password verification data subset: A proper subset of a password verification data set that is stored in a central storage device.
  • remote storage device: A storage device that is not permanently connected to a processing device is considered to be a remote storage device from a perspective of the processing device.
  • remote password verification data subset: A proper subset of a password verification data set that is stored in a remote storage device.
  • perturb function: A method that is performed within a loop, that accepts a data element as an input, and produces an output that depends on the data element and on a number of iterations of a loop that have already been performed.
  • cryptographic key data set: A set of data elements that, together with a trial password, may enable a host processing device to generate a cryptographic key.
  • cryptographic key data set generation method: A processing device implemented method that may generate a cryptographic key data set and a cryptographic key from a password.
  • quick cryptographic key generation method: A processing device implemented method that accepts a trial password from a user and a subset of a cryptographic key data set, intended for use with the quick cryptographic key generation method, as inputs, determines whether the trial password is identical to a password that the user provided to a cryptographic key data set generation method when the cryptographic key data set was generated, and if the trial password is identical to the password, may generate a cryptographic key identical to a cryptographic key generated by the cryptographic key data set generation method.
  • slow cryptographic key generation method: A processing device implemented method that accepts a trial password from a user and a subset of a cryptographic key data set, intended for use with the slow cryptographic key generation method, as inputs, determines whether the trial password is identical to a password that the user provided to a cryptographic key data set generation method when the cryptographic key data set was generated, and, if the trial password is identical to the new password, may generate a cryptographic key identical to a cryptographic key generated by the cryptographic key data set generation method, and uses at least twice as much time to generate the identical cryptographic key as an amount of time a quick cryptographic key method uses.
  • quick cryptographic key data subset: A subset of a cryptographic key data set that may be provided as an input to a quick cryptographic key generation method.
  • slow cryptographic key data subset: A subset of a cryptographic key data set that may be provided as an input to a slow cryptographic key generation method.
  • central cryptographic key data subset: A proper subset of a cryptographic key data set that is stored in a central storage device.
  • remote cryptographic key data subset: A proper subset of a cryptographic key data set that is stored in a remote storage device.
• The terms “set”, “subset”, “proper subset” and “function” have the usual meanings assigned to them by a branch of mathematics known as set theory.
• Some of the above definitions use the phrase “permanently connected” in relation to processing devices and storage devices. For the purposes of this disclosure, a processing device is considered to be permanently connected to a storage device if the processing device is able to read data from the storage device under all normal circumstances. Unplugging a removable storage device from the processing device is considered to be a normal circumstance. A personal processing device failing to respond to a query for data stored on an attached storage device, the query originating from a host processing device, is considered to be another normal circumstance. An equipment malfunction is not considered to be a normal circumstance. Configuration changes, such as removing an internal storage device from a processing device, or disconnecting a file server from a processing device, are not considered to be normal circumstances.
Exemplary Operating Environments
• FIGS. 1-5 illustrate five exemplary operating environments in which embodiments can be implemented. This is not an exhaustive list of operating environments; embodiments can be built using other configurations.
• The operating environments share some common elements:
• • Apersonal processing device104 may be a desktop computer, a laptop computer, a handheld computer such as a tablet or a smartphone, a wearable computer, or any other device that performs computations and interacts with human beings.
  • Anoutput device110 may be a computer monitor, a screen built into a desktop computer, a television, a projector, a screen of a laptop or smartphone, an eye-mounted display, a printer, or any other device that displays images generated by thepersonal processing device104.
  • A fixedstorage device108 may be an internal hard drive, an external hard drive, or any other non-transitory, non-removable storage device.
  • Aremovable storage device106 may be a flash drive, an external disk drive, a CD-ROM, a floppy disk, a smartphone or any other removable storage device having a non-transitory storage medium.
  • Anetwork202 may be a wired or wireless network, or a mixture of wired and wireless networks. Thenetwork202 may be a local-area network that connects devices in a room, office, building or campus, it may be a wide-area network that spans a larger geographic area, or it may be a network of networks.
  • Ahost processing device204 may be a single computer with an interface to thenetwork202, or a collection of cooperating computers at least one of which has the interface to thenetwork202.
  • Ahost storage device206 may be an internal hard drive, an external hard drive, a drive consisting of memory chips, a file server, or any other non-transitory storage device that is always accessible to thehost processing device204.
  • Aclient processing device402 may be a single computer, a collection of cooperating computers, or any device that may interact with thehost processing device204, which creates and maintains one or more user accounts at the request of the client processing device.
  • A client storage device404 may be an internal hard drive, an external hard drive, a drive consisting of memory chips, a file server, or any other storage device having a non-transitory storage medium.
  • An attackerprocessing device array502 may be a single computer or a collection of cooperating computers.
  • An attacker storage device array504 may be an internal hard drive, an external hard drive, a file server, or any other non-transitory storage device, or a collection of such devices.
• FIG. 1 illustrates an exemplarystandalone operating environment100 that may include thepersonal processing device104, theoutput device110, the fixedstorage device108, and theremovable storage device106. Ahuman user102 interacts with thepersonal processing device104. Thehuman user102 may at times remove theremovable storage device106 from thepersonal processing device104. Thepersonal processing device104 may not be connected to anetwork202 and may not have acommunication interface680 as depicted inFIG. 6.
• Thepersonal processing device104 plays a dual role in the standalone operating environment100: it interacts with thehuman user102, and it hosts the user's account. In operatingenvironments200,300 and400, the two roles are played by different processing devices.
• Theremovable storage device106 is not permanently connected to thepersonal processing device104 because thehuman user102 may unplug theremovable storage device106 from thepersonal processing device104. In this disclosure, unplugging theremovable storage device106 is not considered to be a configuration change.
• In contrast, the fixedstorage device108 is permanently connected to thepersonal processing device104. The only circumstances in which thepersonal processing device104 would not be able to read data from the fixedstorage device108 are if thepersonal processing device104 and/or the fixedstorage device108 malfunction, or if thepersonal processing device104 is opened up and the fixedstorage device108 is disconnected from it. In this disclosure, disconnecting the fixedstorage device108 is considered to be a configuration change.
• FIG. 2 illustrates an exemplarynetwork operating environment200 that may include thepersonal processing device104, theoutput device110, the fixedstorage device108, thenetwork202, thehost processing device204, and thehost storage device206. Thehuman user102 interacts with thepersonal processing device104. Thepersonal processing device104 and thehost processing device204 are both connected to thenetwork202 and can exchange information with each other via thenetwork202.
• The fixedstorage device108 is not permanently connected to thehost processing device204 because the fixedstorage device108 and thehost processing device204 communicate via thenetwork202 and thepersonal processing device104. There are several normal circumstances in which thehost processing device204 may not be able to read data from the fixedstorage device108 including, but not limited to, thepersonal processing device104 being off-line or thepersonal processing device104 failing to respond to a query from thehost processing device204.
• In contrast, thehost storage device206 is permanently connected to thehost processing device204. The only circumstances in which thehost processing device204 would not be able to read data from thehost storage device206 are if thehost processing device204 and/or thehost storage device206 either malfunction or are reconfigured. Even if thehost storage device206 is a file server, thehost storage device206 is considered to be permanently connected to thehost processing device204 for the purposes of this disclosure.
• Disconnecting thehost storage device206 from thehost processing device204 is considered to be a configuration change.
• FIG. 3 illustrates an exemplary network plus removable storagedevice operating environment300 that is very similar to thenetwork operating environment200 ofFIG. 2 with one addition: theremovable storage device106 is attached to thepersonal processing device104. As in thestandalone operating environment100 ofFIG. 1, thehuman user102 may at times remove theremovable storage device106 from thepersonal processing device104.
• Theremovable storage device106 is not permanently connected to thehost processing device204 because thehuman user102 may unplug theremovable storage device106 from thepersonal processing device104.
• FIG. 4 illustrates an exemplary machine-to-machine operating environment400 that may include theclient processing device402, the client storage device404, thenetwork202, thehost processing device204, and thehost storage device206. Theclient processing device402 and thehost processing device204 are both connected to thenetwork202 and can exchange information with each other via thenetwork202.
• The client storage device404 is not permanently connected to thehost processing device204 because the client storage device404 and thehost processing device204 communicate via thenetwork202 and theclient processing device402. There are several normal circumstances in which thehost processing device204 may not be able to read data from the client storage device404 including, but not limited to, theclient processing device402 being off-line or theclient processing device402 failing to respond to a query from thehost processing device204.
• FIG. 5 illustrates an exemplaryattack operating environment500 that may include the attackerprocessing device array502 and the attacker storage device array504.
• FIG. 6 is a functional block diagram that illustratesexemplary processing device600, which may be used to implement thepersonal processing device104, thehost processing device204, theclient processing device402, a processing device that is a component of the attackerprocessing device array502, or any combination of these devices. Theprocessing device600 may include abus610, aprocessor620, amemory630, a read-only memory (ROM)640, astorage device650, aninput device660, anoutput device670, and acommunication interface680. Thebus610 may permit communication among components of theprocessing device600.
• Theprocessor620 may include at least one conventional processor or microprocessor that interprets and executes instructions. Thememory630 may be a random access memory (RAM) or another type of dynamic storage device that stores information and instructions for execution by theprocessor620. Thememory630 may also store temporary variables or other intermediate information used during execution of instructions by theprocessor620. TheROM640 may include a conventional ROM device or another type of static storage device that stores static information and instructions for theprocessor620. Thestorage device650 may include any type of non-transitory computer-readable medium for storing data and/or instructions.
• Theinput device660 may include one or more conventional mechanisms that permit a user to input information to theprocessing device600, such as, for example, a keyboard, a mouse, a touch screen, an electronic pen, a microphone or other input device. Theoutput device670 may include one or more conventional mechanisms that output information to the user, including a display, a printer, or other output device. Thecommunication interface680 may include any transceiver-like mechanism that enable theprocessing device600 to communicate with other devices or networks. Thecommunication interface680 may include an interface to thenetwork202.
• Theprocessing device600 may perform such functions in response to theprocessor620 executing sequences of instructions contained in a non-transitory computer-readable medium, such as, for example,memory630, or other non-transitory computer-readable medium. Such instructions may be read into thememory630 from another computer-readable non-transitory medium, such as thestorage device650, or from a separate device via thecommunication interface680.
Overview
• A host processing device, which may include, but not be limited to, a personal computer or a web server, may host accounts for one or more users. When a user attempts to log in to his/her/its account, he/she/it provides a user name and a trial password to the host processing device. The host processing device then obtains a password verification data set for the user and provides the password verification data set and the trial password to a password authentication method. If the password authentication method returns a success indicator, the user is granted access to his/her/its account. If the password authentication method returns a failure indicator, the user is not granted access to his/her/its account.
• An attacker who breaks into the host processing device may steal the user's password verification data set (or password verification data sets for all users). The attacker may also learn methods by which the host processing device authenticates passwords. The attacker may then use the stolen password verification data sets and the learned methods on his/her own processing devices to try to crack the user's password.
• To make the cracking of the user's password more difficult, embodiments of the invention divide the user's password verification data set into a central password verification data subset and a remote password verification data subset. The central password verification data subset is stored in a central storage device that is permanently connected to the host processing device, and the remote password verification data subset is stored in a remote storage device that is not permanently connected to the host processing device. For example, the remote password verification data subset may be stored in a user's storage device, such as a fixed or removable storage device, or on a remote file server that is not permanently connected to the host processing device. The host processing device may not be able to obtain the user's remote password verification data subset unless the remote password verification data subset is provided to the host processing device when the user attempts to log in to his/her/its account.
• If the host processing device is able to obtain the user's remote password verification data subset, then the processing device may construct a first data set from the remote password verification data subset and the user's central password verification data subset. The first data set and the trial password may be provided to a first password authentication method that yields a result quickly, typically in less than a second. If the host processing device cannot obtain the user's remote password verification data subset, then the processing device may construct a second data set including only data elements from the user's central password verification data subset. The second data set and the trial password may be provided to a second password authentication method that takes longer to produce a result than the first password authentication method, typically seconds or tens of seconds.
• Because the password verification data set is distributed on multiple storage devices, the attacker who breaks into the host processing device may only be able to obtain the user's central password verification data subset, but not the user's remote password verification data subset. Without the remote password verification data subset, the attacker uses the second password authentication method on a series of millions or billions of trial passwords. If authenticating each trial password in the series takes seconds rather than fractions of a second, then cracking the user's password may take months or years rather than minutes or hours.
• The first password authentication method is referred to herein as a quick password authentication method, and the first data set is referred to herein as a quick password verification data subset. At least one data element of the quick password verification data subset may belong to the central password verification data subset, and at least one other data element may belong to the remote password verification data subset. The quick password verification data subset may be the same as, or may be a proper subset of, the password verification data set.
• The second password authentication method is referred to herein as a slow password authentication method, and the second data set is referred to herein as a slow password verification data subset. The slow password verification data subset is a subset of the central password verification data subset. The slow password verification data subset may be the same as, or may be a proper subset of, the central password verification data subset.
• The central password verification data subset may include at least one data element that may be used to verify the authenticity of the remote password verification data subset. The at least one data element may be a hash of a combination of data elements from the remote password verification data subset. If the central password verification data subset does not include the at least one data element, then the attacker may be able to provide a spoofed remote password verification data subset to the processing device that the processing device accepts as valid.
• There are many ways to design the password verification data set that is divisible into the central password verification data subset and the remote password verification data subset, and that allow multiple password authentication methods to be used. The exemplary methods include examples of password verification data sets and password authentication methods meeting these criteria.
• In some embodiments, a speed ratio of the quick password authentication method with respect to the slow password authentication method may be easy to adjust. An implementer may choose a value of the ratio depending on a speed of the host processing device and an anticipated speed of an attacker's processing device. If the host processing device is fast, then the ratio can be made larger than a ratio suitable for a slower processing device without inconveniencing the user, and thereby making the password verification data set more secure.
• Some embodiments define a cryptographic key data set that is used, in conjunction with a password, to generate a cryptographic key. The cryptographic key data set may be based on, and may include same data elements as, the password verification data set. The cryptographic key data set may be divided into a central cryptographic key data subset and a remote cryptographic key data subset wherein the central cryptographic key data subset is stored on a central storage device and the remote cryptographic key data subset is stored on a remote storage device. Some embodiments define a quick cryptographic key data subset that includes data elements from both the central cryptographic key data subset and the remote cryptographic key data subset, a slow cryptographic key data subset that includes data elements from only the central cryptographic key data subset, a quick cryptographic key generation method that accepts a trial password and the quick cryptographic key data subset as inputs, and may generate the cryptographic key more quickly than a slow cryptographic key generation method, typically in less than a second, and the slow cryptographic key generation method that accepts the trial password and the slow cryptographic key data subset as inputs, and may generate the cryptographic key more slowly than the quick cryptographic key generation method, typically in seconds or tens of seconds. The cryptographic key data set may resist attacks that attempt to recover the cryptographic key.
Exemplary Methods
• In some embodiments of this disclosure, processes that generate a password verification data set and store data elements of the password verification data set in various storage devices, and processes that use the password verification data set to authenticate a password, operate differently depending on an operating environment of the embodiment.FIGS. 7-30 illustrate how the password verification data set is generated and stored, and how password authentication is performed, in various operating environments.
• FIGS. 7-30 refer to ageneric method890, ageneric method1290 and ageneric method1690.
• Thegeneric method890 may generate the password verification data set. Detailed descriptions of exemplary implementations of thegeneric method890 are presented inFIGS. 32,36,40,44,48 and52.
• Thegeneric method1290 is a generic quick password authentication method. Detailed descriptions of exemplary implementations of thegeneric method1290 are presented inFIGS. 33,37,41,45,49 and53.
• Thegeneric method1690 is a generic slow password authentication method. Detailed descriptions of exemplary implementations of thegeneric method1290 are presented inFIGS. 34,38,42,46,50 and54.
FIGS. 7-10
• FIGS. 7-10 constitute a storyboard illustrating an exemplary process for generating and storing the password verification data set in thestandalone operating environment100 ofFIG. 1. Thestandalone operating environment100 differs from the other exemplary operating environments in that thestandalone operating environment100 may include a single processing device, thepersonal processing device104. Thepersonal processing device104 performs two roles in the standalone operating environment100: thepersonal processing device104 accepts some authentication data, that may include auser name750, anew password752, and atrial password1150, from thehuman user102, and thepersonal processing device104 hosts an account for thehuman user102.
• InFIGS. 7-10, thehuman user102 operates thepersonal processing device104 which is connected to theoutput device110, the fixedstorage device108, and theremovable storage device106.
• FIG. 7 depicts a first panel of the storyboard showing that thehuman user102 has entered theuser name750 and thenew password752 into a form displayed on theoutput device110. In other embodiments, theuser name750 and thenew password752 may be entered via other input means including, but not limited to, a microphone, a touch screen, a keyboard, etc.
• FIG. 8 depicts a second panel of the storyboard that shows thepersonal processing device104 starting to perform thegeneric method890 that may generate the password verification data set. Thepersonal processing device104 provides thenew password752 to themethod890 as input.
• FIG. 9 depicts a third panel of the storyboard that shows themethod890 finishing and providing two output data sets to the personal processing device104: a central password verification data subset956 (CPVDS) and a remote password verification data subset954 (RPVDS).
• FIG. 10 depicts a fourth panel of the storyboard that shows thepersonal processing device104 storing the central password verification data subset956 (CPVDS) in the fixedstorage device108, and storing the remote password verification data subset954 (RPVDS) in theremovable storage device106. Thepersonal processing device104 also stores theuser name750 in the fixedstorage device108, and may confirm that the user has successfully created the account by displaying a message on theoutput device110.
• Thestandalone operating environment100 may use at least two storage devices such as the fixedstorage device108 and theremovable storage device106. Without the at least two storage devices, only one storage device, typically the fixedstorage device108, would be available to store both the central password verification data subset956 (CPVDS) and the remote password verification data subset954 (RPVDS). Storing both subsets in a same storage device may enable an attacker to steal the user's entire password verification data set. The attacker may then overcome the defenses provided by the various embodiments by using a quick password authentication method in an attack.
FIGS. 11-14
• FIGS. 11-14 constitute a storyboard illustrating an exemplary process for using a quick password verification data subset1250 (QPVDS) to authenticate atrial password1150 of thehuman user102 in thestandalone operating environment100 ofFIG. 1. InFIGS. 11-14, thehuman user102 operates thepersonal processing device104, which is connected to theoutput device110 and the fixedstorage device108. The fixedstorage device108 contains the central password verification data subset956 (CPVDS) belonging to thehuman user102, and theremovable storage device106 contains the remote password verification data subset954 (RPVDS) belonging to thehuman user102.
• FIG. 11 depicts a first panel of the storyboard showing that thehuman user102 has entered theuser name750 and the trial password1150 (that is identical to thenew password752 that thehuman user102 entered inFIG. 7) into a form displayed on theoutput device110. In other embodiments, theuser name750 and thetrial password1150 may be entered via other input means including, but not limited to, a microphone, a touch screen, a keyboard, etc.
• FIG. 12 depicts a second panel of the storyboard that shows thepersonal processing device104 starting to perform the generic quickpassword authentication method1290. Themethod1290 is designed to authenticate a password based on the quick password verification data subset1250 (QPVDS). Thepersonal processing device104 reads the remote password verification data subset954 (RPVDS) from theremovable storage device106, the central password verification data subset956 (CPVDS) from the fixedstorage device108. Then, thepersonal processing device104 constructs the quick password verification data subset1250 (QPVDS) that combines some data elements from the remote password verification data subset954 (RPVDS) with some other data elements from the central password verification data subset956 (CPVDS). Lastly, thepersonal processing device104 provides thetrial password1150 and the quick password verification data subset1250 (QPVDS) as inputs to themethod1290.
• FIG. 13 depicts a third panel of the storyboard that shows themethod1290 finishing and providing a success indicator to thepersonal processing device104. If, inFIG. 11, thehuman user102 enters thetrial password1150 that is not identical to thenew password752, then themethod1290 may instead provide a failure indicator to thepersonal processing device104.
• FIG. 14 depicts a fourth panel of the storyboard that shows thepersonal processing device104 providing an indication of success to thehuman user102. In this exemplary embodiment, the indication of success is provided by displaying a message on theoutput device110 confirming that thehuman user102 has logged in successfully. If themethod1290 provides the failure indicator to thepersonal processing device104, then thepersonal processing device104 may provide an indication of failure to thehuman user102. In this exemplary embodiment, the indication of failure may be provided to thehuman user102 by displaying a login failure message on theoutput device110.
FIGS. 15-18
• FIGS. 15-18 constitute a storyboard illustrating an exemplary process for using a slow password verification data subset1650 (SPVDS) to authenticate thetrial password1150 of thehuman user102 in thestandalone operating environment100 ofFIG. 1. InFIGS. 15-18, thehuman user102 operates thepersonal processing device104 which is connected to theoutput device110, and the fixedstorage device108. The fixedstorage device108 has stored therein the central password verification data subset956 (CPVDS) belonging to thehuman user102. InFIGS. 15-17, theremovable storage device106 does not contain the remote password verification data subset954 (RPVDS) belonging to thehuman user102.
• FIG. 15 depicts a first panel of the storyboard showing that thehuman user102 has entered theuser name750 and the trial password1150 (that is identical to thenew password752 that thehuman user102 entered inFIG. 7) into a form displayed on theoutput device110. In other embodiments, theuser name750 and thetrial password1150 may be entered via other input means including, but not limited to, a microphone, a touch screen, a keyboard, etc.
• FIG. 16 depicts a second panel of the storyboard that shows thepersonal processing device104 starting to perform the generic slowpassword authentication method1690. Themethod1690 is designed to authenticate a password based on the slow password verification data subset1650 (SPVDS). Thepersonal processing device104 reads the central password verification data subset956 (CPVDS) from the fixedstorage device108, and constructs the slow password verification data subset1650 (SPVDS) using some or all data elements from the central password verification data subset956 (CPVDS). Lastly, thepersonal processing device104 provides thetrial password1150 and the slow password verification data subset1650 (SPVDS) as inputs to themethod1690.
• FIG. 17 depicts the third panel of the storyboard that shows themethod1690 finishing and providing two outputs to the personal processing device104: the success indicator, and a fresh copy of the remote password verification data subset954 (RPVDS). If, inFIG. 15, thehuman user102 provides thetrial password1150 that is not identical to thenew password752, then themethod1690 may instead provide the failure indicator to thepersonal processing device104.
• FIG. 18 depicts the fourth panel of the storyboard that shows thepersonal processing device104 providing an indication of success to thehuman user102. In this exemplary embodiment, the indication of success is provided by displaying a message on theoutput device110 confirming that thehuman user102 has logged in successfully. Thepersonal processing device104 also stores the fresh copy of the remote password verification data subset954 (RPVDS) in theremovable storage device106. If themethod1690 provides the failure indicator to thepersonal processing device104, then thepersonal processing device104 may provide an indication of failure to thehuman user102. In this exemplary embodiment, the indication of failure may be provided to thehuman user102 by displaying a login failure message on theoutput device110.
• Although not shown inFIG. 18, in some embodiments, thepersonal processing device104 may also update some data elements of the central password verification data subset956 (CPVDS) on the fixedstorage device108.
• If thehuman user102 had removed theremovable storage device106 from thepersonal processing device104, then thepersonal processing device104 would not have been able to store the fresh copy of the remote password verification data subset954 (RPVDS) inFIG. 18.
FIGS. 19-22
• FIGS. 19-22 constitute a storyboard illustrating an exemplary process for generating and storing the password verification data set in thenetwork operating environment200 ofFIG. 2.
• Thenetwork operating environment200 includes at least two processing devices: thepersonal processing device104 with which thehuman user102 interacts directly, and thehost processing device204 that hosts the human user's account.
• InFIGS. 19-22, thehuman user102 operates thepersonal processing device104, which is connected to theoutput device110, the fixedstorage device108, and thenetwork202. Thehost processing device204 is connected to thenetwork202. Thehost storage device206 is permanently connected to thehost processing device204. Thepersonal processing device104 and thehost processing device204 can exchange information via thenetwork202.
• FIG. 19 depicts a first panel of the storyboard showing that thehuman user102 has entered theuser name750 and thenew password752 into a form displayed on theoutput device110. In other embodiments, theuser name750 and thenew password752 may be entered via other input means including, but not limited to, a microphone, a touch screen, a keyboard, etc. Thepersonal processing device104 transmits theuser name750 and thenew password752 via thenetwork202 to thehost processing device204.
• FIG. 20 depicts a second panel of the storyboard that shows thehost processing device204 starting to perform thegeneric method890 that may generate the password verification data set. Thehost processing device204 provides thenew password752 to themethod890 as input, and stores theuser name750 in thehost storage device206.
• FIG. 21 depicts a third panel of the storyboard that shows themethod890 finishing and providing two data sets to the host processing device204: the central password verification data subset956 (CPVDS) and the remote password verification data subset954 (RPVDS).
• FIG. 22 depicts a fourth panel of the storyboard that shows thehost processing device204 storing the central password verification data subset956 (CPVDS) in thehost storage device206, and transmitting the remote password verification data subset954 (RPVDS) via thenetwork202 to thepersonal processing device104. Thepersonal processing device104 stores the remote password verification data subset954 (RPVDS) in the fixedstorage device108, and confirms that thehuman user102 has successfully created the account by displaying a message on theoutput device110.
• In a first similar embodiment, an exemplary process for generating and storing the password verification data set in the network plus removable storagedevice operating environment300 ofFIG. 3 differs in only one respect from the process illustrated inFIGS. 19-22: thepersonal processing device104 stores the remote passwordverification data subset954 in theremovable storage device106 instead of in the fixedstorage device108.
• In a second similar embodiment, an exemplary process for generating and storing a password verification data set in the machine-to-machine environment400 ofFIG. 4 differs from the process illustrated inFIGS. 19-22 in two respects:
• theuser name750 and thenew password752 are sent from theclient processing device402 instead of from thepersonal processing device104; and
• theclient processing device402 stores the remote password verification data subset954 (RPVDS) in the client storage device404 instead of thepersonal processing device104 storing the remote password verification data subset954 (RPVDS) in the fixedstorage device108.
FIGS. 23-26
• FIGS. 23-26 constitute a storyboard illustrating an exemplary process for using the quick password verification data subset1250 (QPVDS) to authenticate thetrial password1150 of thehuman user102 in thenetwork operating environment200 ofFIG. 2. InFIGS. 23-26, thehuman user102 operates thepersonal processing device104, which is connected to theoutput device110, the fixedstorage device108, and thenetwork202. Thehost processing device204 is connected to thenetwork202. Thehost storage device206 is permanently connected to thehost processing device204. Thepersonal processing device104 and thehost processing device204 can exchange information via thenetwork202. Thehost storage device206 has stored therein the central password verification data subset956 (CPVDS) belonging to thehuman user102, and the fixedstorage device108 has stored therein the remote password verification data subset954 (RPVDS) belonging to thehuman user102.
• FIG. 23 depicts a first panel of the storyboard showing that thehuman user102 has entered theuser name750 and the trial password1150 (that is identical to thenew password752 that thehuman user102 entered inFIG. 19) into a form displayed on theoutput device110. In other embodiments, theuser name750 and thetrial password1150 may be entered via other input means including, but not limited to, a microphone, a touch screen, a keyboard, etc. Thepersonal processing device104 transmits theuser name750 and thetrial password1150 via thenetwork202 to thehost processing device204.
• FIG. 24 depicts a second panel of the storyboard that shows thehost processing device204 starting to perform the generic quickpassword authentication method1290. The personal processing device reads the remote password verification data subset954 (RPVDS) from the fixedstorage device108, and transmits the remote password verification data subset954 (RPVDS) via thenetwork202 to thehost processing device204. Thehost processing device204 receives the remote password verification data subset954 (RPVDS) sent by the personal processing device, reads the central password verification data subset956 (CPVDS) from thehost storage device206, and constructs the quick password verification data subset1250 (QPVDS) using some data elements from the remote password verification data subset954 (RPVDS) and some other data elements from the central password verification data subset956 (CPVDS). Lastly, thehost processing device204 provides thetrial password1150 and the quick password verification data subset1250 (QPVDS) as inputs to themethod1290.
• FIG. 25 depicts a third panel of the storyboard that shows themethod1290 finishing and providing the success indicator to thehost processing device204. If, inFIG. 23, thehuman user102 provides thetrial password1150 that is not identical to thenew password752, then themethod1290 may instead provide the failure indicator to thehost processing device204.
• FIG. 26 depicts a fourth panel of the storyboard that shows thehost processing device204 transmitting the success indicator via thenetwork202 to thepersonal processing device104. Thepersonal processing device104 may then provide an indication of success to thehuman user102. In this exemplary embodiment, the indication of success is provided by displaying a message on theoutput device110 confirming that thehuman user102 has logged in successfully. If thehost processing device204 transmits the failure indicator via thenetwork202 to thepersonal processing device104, then thepersonal processing device104 may provide an indication of failure to thehuman user102. In this embodiment, the indication of failure may be provided by displaying a login failure message on theoutput device110.
• In the first similar embodiment, an exemplary process for using the quick password verification data subset1250 (QPVDS) to authenticate thetrial password1150 of thehuman user102 in the network plus removable storagedevice operating environment300 ofFIG. 3 differs in only one respect from the process illustrated inFIGS. 23-26: thepersonal processing device104 reads the remote password verification data subset954 (RPVDS) from theremovable storage device106.
• In the second similar embodiment, an exemplary process for using the quick password verification data subset1250 (QPVDS) to authenticate thetrial password1150 of theclient processing device402 in the machine-to-machine environment400 ofFIG. 4 differs from the process illustrated inFIGS. 23-26 in two respects:
• theuser name750 and thetrial password1150 are sent from theclient processing device402 instead of from thepersonal processing device104; and
• theclient processing device402 obtains the remote password verification data subset954 (RPVDS) from the client storage device404 instead of thepersonal processing device104 obtaining the remote password verification data subset954 (RPVDS) from the fixedstorage device108.
FIGS. 27-30
• FIGS. 27-30 constitute a storyboard illustrating an exemplary process for using the slow passwordverification data subset1650 to authenticate thetrial password1150 of thehuman user102 in thenetwork operating environment200 ofFIG. 2. InFIGS. 27-30, thehuman user102 operates thepersonal processing device104, which is connected to theoutput device110, the fixedstorage device108, and thenetwork202. Thehost processing device204 is connected to thenetwork202. Thehost storage device206 is permanently connected to thehost processing device204. Thepersonal processing device104 and thehost processing device204 can exchange information via thenetwork202. Thehost storage device206 has stored therein the central password verification data subset956 (CPVDS) belonging to thehuman user102. The fixedstorage device108 does not contain the remote password verification data subset954 (RPVDS) belonging to thehuman user102 inFIGS. 27-29.
• FIG. 27 depicts a first panel of the storyboard showing that thehuman user102 has entered theuser name750 and the trial password1150 (that is identical to thenew password752 that thehuman user102 entered inFIG. 19) into a form displayed on theoutput device110. In other embodiments, theuser name750 and thetrial password1150 may be entered via other input means including, but not limited to, a microphone, a touch screen, a keyboard, etc. Thepersonal processing device104 transmits theuser name750 and thetrial password1150 via thenetwork202 to thehost processing device204.
• FIG. 28 depicts a second panel of the storyboard that shows thehost processing device204 starting to perform the generic slowpassword authentication method1690. Thehost processing device204 reads the central password verification data subset956 (CPVDS) from thehost storage device206 and constructs the slow password verification data subset1650 (SPVDS) using some (possibly all) of the data elements from the central password verification data subset956 (CPVDS). Lastly, thehost processing device204 provides thetrial password1150 and the slow password verification data subset1650 (SPVDS) as inputs to themethod1690.
• FIG. 29 depicts a third panel of the storyboard that shows themethod1690 finishing and providing the success indicator and a fresh copy of the remote password verification data subset954 (RPVDS) to thehost processing device204. If, inFIG. 27, thehuman user102 provides thetrial password1150 that is not identical to thenew password752, then themethod1690 may instead provide the failure indicator to thehost processing device204.
• FIG. 30 depicts a fourth panel of the storyboard that shows thehost processing device204 transmitting the success indicator and the fresh copy of the remote password verification data subset954 (RPVDS) via thenetwork202 to thepersonal processing device104. Thepersonal processing device104 stores the fresh copy of the remote password verification data subset954 (RPVDS) on the fixedstorage device108 and may then provide an indication of success to thehuman user102. In this exemplary embodiment, the indication of success is provided by displaying a message on theoutput device110 confirming that thehuman user102 has logged in successfully. If thehost processing device204 transmits the failure indicator via thenetwork202 to thepersonal processing device104, then thepersonal processing device104 may provide an indication of failure to thehuman user102. In this exemplary embodiment, the indication of failure may be provided to thehuman user102 by displaying a login failure message on theoutput device110.
• Although not shown inFIG. 30, in some embodiments, thehost processing device204 may also update some data elements of the central password verification data subset956 (CPVDS) that are stored on thecentral storage device206.
• In the first similar embodiment, an exemplary process for using the slow password verification data subset1650 (SPVDS) to authenticate thetrial password1150 of thehuman user102 in the network plus removable storagedevice operating environment300 ofFIG. 3 differs in only one respect from the process illustrated inFIGS. 27-30: thepersonal processing device104 stores the fresh copy of the remote password verification data subset954 (RPVDS) in theremovable storage device106, instead of storing the fresh copy of the remote password verification data subset954 (RPVDS) in the fixedstorage device108.
• In the second similar embodiment, an exemplary process for using the slow password verification data subset1650 (SPVDS) to authenticate thetrial password1150 of theclient processing device402 in the machine-to-machine environment400 ofFIG. 4 differs from the process illustrated inFIGS. 27-30 in three respects:
• • theuser name750 and thetrial password1150 are sent from theclient processing device402 instead of from thepersonal processing device104;
  • the client storage device404 (instead of the fixed storage device108) lacks the remote password verification data subset954 (RPVDS); and
  • theclient processing device402 stores the fresh copy of the remote password verification data subset954 (RPVDS) in the client storage device404 instead of thepersonal processing device104 storing it in the fixedstorage device108.
• The six storyboards ofFIGS. 7-10,FIGS. 11-14,FIGS. 15-18,FIGS. 19-22,FIGS. 23-26, andFIGS. 27-30, refer to the password verification data set, thegeneric method890 that may generate a password verification data set, the generic quickpassword authentication method1290, and the generic slowpassword authentication method1690.FIGS. 31-53 illustrate exemplary password verification data sets, exemplary methods that generate a password verification data set, exemplary quick password authentication methods, and exemplary slow password authentication methods. TheFIGS. 31-53 are a series of four related figures:FIGS. 31-34,FIGS. 35-38,FIGS. 39-42,FIGS. 43-46,FIGS. 47-50, andFIGS. 51-54. In each set of four related figures, the first figure illustrates a specific password verification data set, the second figure illustrates a specific method that may generate the specific password verification data set, the third figure illustrates a specific quick password authentication method using the specific password verification data set, and the fourth figure illustrates a specific slow password authentication method using the specific password verification data set. The specific password verification data set, the specific method that may generate the specific password verification data set, the specific quick password authentication method, and the specific slow password authentication method from any one set of the sets of four related figures can be substituted for the password verification data set, thegeneric method890, thegeneric method1290, and thegeneric method1690 in the six storyboards.
Common Features of FIGS. 31-59
• Some of the exemplary data sets and methods illustrated inFIGS. 31-59 share common features described in the following paragraphs.
• Various exemplary methods for generating password verification data sets and for authenticating passwords may be invoked through an interaction between a user, who/that is either creating an account or is seeking to access an existing account, and a processing device that hosts the user's account. In thestandalone operating environment100 ofFIG. 1, thenetwork operating environment200 ofFIG. 2, and the network plus removable storagedevice operating environment300 ofFIG. 3, the user may be thehuman user102. In the machine-to-machine operating environment400 ofFIG. 4, the user may be theclient processing device402. In thestandalone operating environment100 ofFIG. 1, the processing device that hosts the user's account may be thepersonal processing device104. In thenetwork operating environment200 ofFIG. 2, the network plus removable storagedevice operating environment300 ofFIG. 3, and the machine-to-machine operating environment400 ofFIG. 4, the processing device that hosts the user's account may be thehost processing device204.
• Some exemplary password verification data sets include one or more salts. The one or more salts are strings of bits or characters. In some embodiments, the one or more salts may have a same length (number of characters or bits) for every user, and in other embodiments, the one or more salts may have a different length for some users. In some embodiments, a password verification data set may include two or more salts. The salts may each have a same length or different lengths. A longer one or more salts, as opposed to a shorter one or more salts, may make a password verification data set, to which the one or more salts belongs, more resistant to attacks. With modern processing devices available to an attacker, a salt having two 8-bit characters is too short to provide much protection from the attacker. An eight-character salt provides some protection from the attacker, and a 16- or more character salt provides adequate protection from the attacker. For a processing device that hosts the user's accounts, a longer one or more salts requires a small amount of additional storage space than a shorter one or more salts, and some methods that generate the longer one or more salts, and other methods that use the longer one or more salts to authenticate passwords, execute somewhat more slowly than some similar methods that generate the shorter one or more salts, and other similar methods that use the shorter one or more salts to authenticate passwords.
• In some embodiments, the one or more salts may be generated by a random number generator in such a way that either no two users have a same salt value, or that a probability that two users have the same salt value is exceedingly low.
• Some exemplary password verification data sets include one or more hashes. A hash of the one or more hashes may be generated by calculating a result of a one-way function, which may include, but not be limited to, a standard one-way function such as MD5, SHA-1, SHA-256 or SHA-512. In some embodiments, the one-way function is called repeatedly in a loop and the hash is generated from a final output of the one-way function during a last iteration of the loop. Generating a hash by calling the one-way function repeatedly makes a password verification data set to which the hash belongs more resistant to attacks by causing an attacker to perform more computations when attempting to crack a password.
• In some figures, exemplary password verification data sets are depicted with exemplary values of salts and hashes. The exemplary values of salts and hashes in some of the figures are base64-encoded character strings. Although, in some embodiments, other encoding methods may be employed.
• Some exemplary methods for generating password verification data sets and some exemplary methods for authenticating passwords may combine two or more data elements. For example, a salt and a trial password may be combined in the process of authenticating a trial password. There are many ways to combine two or more data elements, including, but not limited to, concatenating the two or more data elements, interleaving the characters of the two or more data elements, or performing an arithmetic operation such as multiplication or a logical operation such as exclusive or on the two or more data elements. If a method for combining two or more data elements is used to generate a password verification data set, then a same method is used when using the password verification data set to authenticate a trial password.
• An exemplary password verification data set may include aRPVDS hash3156. The RPVDS hash is based on one or more data elements from the remote passwordverification data subset954. The one or more data elements are called herein RPVDS hash constituent data elements. When the password verification data set is generated, a value for theRPVDS hash3156 may be obtained from a result of the one-way function applied to a combination of the RPVDS hash constituent data elements. The value of theRPVDS hash3156 may be stored in the central passwordverification data subset956. When a processing device performs the quick password verification method and obtains the RPVDS hash constituent data elements from the remote passwordverification data subset954, the processing device may verify the authenticity of the obtained RPVDS hash constituent data elements by calculating a result of the one-way function applied to a combination of the obtained RPVDS hash constituent data elements and comparing the calculated result to the value of theRPVDS hash3156 stored in the central passwordverification data subset956. If the processing device determines that the calculated result is different than the stored value of theRPVDS hash3156, then the quick password authentication process may return the failure indicator. If an attacker attempts to log in and makes up values for (spoofs) the remote passwordverification data subset956, then a result of the one-way function applied to a combination of the attacker's spoofed RPVDS hash constituent data elements will almost certainly be different than the stored value of theRPVDS hash3156 causing password authentication to fail.
• Some exemplary methods for generating and storing the password verification data set and authenticating thetrial password1150 may transmit sensitive data via a network. The sensitive data may include thenew password752, thetrial password1150, and the remote passwordverification data subset954. To prevent an attacker from intercepting the sensitive data, the sensitive data may be encrypted before being transmitted by using a well-known protocol such as secure-sockets layer (SSL). Other secure communications protocols may be used to encrypt the sensitive data in other embodiments.
• When a processing device finishes executing an exemplary method for generating the password verification data set, the processing device may store the central passwordverification data subset956 in the central storage device, and the processing device may store the remote passwordverification data subset954 in the remote storage device. In thenetwork operating environment200 ofFIG. 2, the network plus removable storagedevice operating environment300 ofFIG. 3, and the machine-to-machine operating environment400 ofFIG. 4, the processing device may transmit the remote passwordverification data subset954 via thenetwork202 to thepersonal processing device104 or theclient processing device402. Thepersonal processing device104 or theclient processing device402 may then store the remote passwordverification data subset954 in an appropriate storage device.
• An instance of the password verification data set, an instance of the central passwordverification data subset956, and an instance of the remote passwordverification data subset954, may each be associated with theuser name750. When the user attempts to log in, he/she/it provides theuser name750 and thetrial password1150. A processing device that performs the password authentication process may look up the central passwordverification data subset956 and the remote passwordverification data subset954 employing theuser name750 as a key during the two lookups. Depending on an operating environment in which the password authentication process takes place, the processing device may look up the remote passwordverification data subset954 in a storage device, the processing device may receive the remote passwordverification data subset954 via thenetwork202 together with theuser name750 and thetrial password1150, or the processing device may request the remote passwordverification data subset954 via thenetwork202 and may receive the remote passwordverification data subset954 separately from theuser name750 and thetrial password1150. The lookup of the remote passwordverification data subset954 may succeed or fail.
• The implementer of some exemplary methods for generating and storing password verification data sets and for authenticating passwords may determine values of some parameters and functions to be used within the methods. A choice of values for some of the parameters and functions may cause the methods to take longer to execute and may make the resulting password verification data sets more resistant to attack. The choice of values for some of the parameters and functions may depend on processing speed of a processing device that hosts the user's account, severity of a threat of attack, and computational resources that attackers are expected to possess.
• The sets of figuresFIGS. 31-34,FIGS. 35-38,FIGS. 39-42,FIGS. 43-46,FIGS. 47-50 andFIGS. 51-54 are all closely related. In each set, a first figure depicts a specific password verification data set and four of its subsets: the remote passwordverification data subset954, the central passwordverification data subset956, the quick passwordverification data subset1250 and the slow passwordverification data subset1650. A second figure depicts a method that may generate the password verification data set. A third figure depicts a method that may authenticate thetrial password1150 based on the quick passwordverification data subset1250. A fourth figure depicts a method that may authenticate thetrial password1150 based on the slow passwordverification data subset1650.
• In the embodiments depicted in each set of four figures, a same processing device may perform the three methods depicted in the second, third and fourth figures. In other embodiments, different processing devices may perform the three methods.
FIG. 31
• FIG. 31 illustrates an exemplary passwordverification data set3150 that may be used by a processing device when performing a password authentication method consistent with the subject matter of this disclosure. The passwordverification data set3150 includes five elements: afirst salt3152, afirst hash3154, asecond salt3158, asecond hash3160 and aRPVDS hash3156.
• FIG. 31 shows an exemplary value for thefirst salt3152, “uZOvDw8nd0eNsb6DhzRS”, an exemplary value for thefirst hash3154, “IpG3UenVLDTTqZtzb9YVPDQWeVw”, an exemplary value for thesecond salt3158, “bxKcYwie0v0ZH6GvcVZ+”, an exemplary value for thesecond hash3160, “lkZ+OIAbEh3jTI8L+G0KP40oZtQ”, and an exemplary value for theRPVDS hash3156, “7BReNC0wnwuZ1DrSVuzeOzK5l8g”. The five exemplary values shown inFIG. 31 are all base64-encoded strings. Although, other encoding methods may be employed in other implementations.
• The passwordverification data set3150 may be divided into the central passwordverification data subset956 and the remote passwordverification data subset954. The central passwordverification data subset956 may include thefirst hash3154, thesecond salt3158, thesecond hash3160 and theRPVDS hash3156. The remote passwordverification data subset954 may include thefirst salt3152. When a user attempts to log in and the remote passwordverification data subset954 is available, the processing device may construct the quick passwordverification data subset1250 including thefirst salt3152, thefirst hash3154 and theRPVDS hash3156, and executes a quickpassword authentication method3390 depicted inFIG. 33. When the user attempts to log in and the remote passwordverification data subset954 is not available, the processing device may construct the slow passwordverification data subset1650 including thesecond salt3158 and thesecond hash3160, and may execute a slowpassword authentication method3490 depicted inFIG. 34.
FIG. 32
• FIG. 32 illustrates anexemplary method3290 that may be used by the processing device to generate the passwordverification data set3150 for the user.
• The processing device may start performing themethod3290 by obtaining theuser name750 and thenew password752 from the user (act3200). Then, the processing device may generate thefirst salt3152 and the second salt3158 (act3202). Then, the processing device may set thefirst hash3154 to a result of a one-way function3292 applied to a combination of thenew password752 and the first salt3152 (act3204). Then, the processing device may set thesecond hash3160 to a result of the one-way function3292 applied to a combination of thenew password752 and the second salt3158 (act3206). Then, the processing device may set acounter3250 to one (act3208). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set thesecond hash3160 to a result of the one-way function3292 applied to the combination of thenew password752 and the second hash3160 (act3210). Then, the processing device may increment the counter3250 (act3212). Then, the processing device may determine whether thecounter3250 is greater than a counter maximum3252 (act3214). If thecounter3250 is not greater than the counter maximum3252, then the processing device may remain in the loop and return toact3210. If thecounter3250 is greater than the counter maximum3252, then the processing device may leave the loop and proceed to act3216. Atact3216, the processing device may set theRPVDS hash3156 to a result of the one-way function3292 applied to thefirst salt3152. Then, the processing device may store the password verification data set3150 (PVDS) as described in the section of this disclosure titled COMMON FEATURES OFFIGS. 31-59 (act3218), and themethod3290 may terminate.
• Before implementing themethod3290, an implementer may make some determinations:
• • a one-way function to use for the one-way function3292;
  • a number of characters or bits that thefirst salt3152 and thesecond salt3158 include, and a method for generating the salts;
  • a method for combining some data elements, including thenew password752 with thefirst salt3152, thenew password752 with thesecond salt3158, and thenew password752 with thesecond hash3160; and
  • a value for thecounter maximum3252.
• Some factors influencing the determinations 1-3 were discussed in the section of this disclosure titled “COMMON FEATURES OF FIGS.31-59.”
• Regarding determination 4, choosing a larger value for the counter maximum3252, as opposed to choosing a smaller value for the counter maximum3252, may have the following effects:
• • a) themethod3290 may take longer to execute;
  • b) the passwordverification data set3150 generated by themethod3290 may be more resistant to attacks; and
  • c) themethod3490 depicted inFIG. 34, that authenticates thetrial password1150 when the remote passwordverification data subset954 is not available, may take longer to execute.
• With modern processing devices, some values for thecounter maximum3252 of one hundred thousand to one billion may be considered.
FIG. 33
• FIG. 33 illustrates the exemplary quickpassword authentication method3390 that may be used by the processing device to authenticate thetrial password1150 of the user. Themethod3390 may be used if the remote passwordverification data subset954, depicted inFIG. 31, is available. If the remote passwordverification data subset954 is not available, then the processing device may use themethod3490, depicted inFIG. 34, instead.
• Themethod3390 may use the quick passwordverification data subset1250 of the passwordverification data set3150, depicted inFIG. 31.
• The processing device may start performing themethod3390 by obtaining theuser name750 and thetrial password1150 from the user, and the quick passwordverification data subset1250, including thefirst salt3152, thefirst hash3154 and the RPVDS hash3156 (act3300). Thefirst salt3152 may be obtained from the remote passwordverification data subset954, and thefirst hash3154 and theRPVDS hash3156 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value3350 to a result of the one-way function3292 applied to the first salt3152 (act3302). Then, the processing device may determine whether thetemp value3350 is equal to the RPVDS hash3156 (act3304). If thetemp value3350 does not equal theRPVDS hash3156, then themethod3390 may terminate and password authentication fails (act3312). If thetemp value3350 equals theRPVDS hash3156, then the processing device may proceed to act3306. Atact3306, the processing device sets thetemp value3350 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thefirst salt3152. Then, the processing device may determine whether thetemp value3350 is equal to the first hash3154 (act3308). If thetemp value3350 equals thefirst hash3154, then themethod3390 may terminate and password authentication succeeds (act3310). If thetemp value3350 does not equal thefirst hash3154, then themethod3390 may terminate and password authentication fails (act3312).
• An implementer of themethod3390 uses a same one-way function3292 as he/she determined to use for themethod3290. In addition, the implementer uses a same method to combine thetrial password1150 with thefirst salt3152 as the method he/she determined to use to combine some data elements within themethod3290. Themethod3290 is depicted inFIG. 32.
FIG. 34
• FIG. 34 illustrates the exemplary slowpassword authentication method3490 that may be used by the processing device to authenticate thetrial password1150. Themethod3490 may use the slow passwordverification data subset1650 of the passwordverification data set3150, depicted inFIG. 31.
• The processing device may start performing themethod3490 by obtaining theuser name750 and thetrial password1150 from the user, and the slow passwordverification data subset1650, including thesecond salt3158 and the second hash3160 (act3400). Thesecond salt3158 and thesecond hash3160 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value3450 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the second salt3158 (act3402). Then, the processing device may set acounter3452 to one (act3404). At this point, the processing device may execute a loop. As its first action in the loop, the processing device may set thetemp value3450 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the temp value3450 (act3406). Next, the processing device may determine whether thecounter3452 is greater than the counter maximum3252 (act3408). If thecounter3452 is less than or equal to thecounter maximum3252, then the processing device may continue executing the loop and may increment the counter3452 (act3410). Next, the processing device may return to the first action of the loop,act3406. If, atact3408, thecounter3452 is greater than the counter maximum3252, then the loop may terminate and the processing device may determine whether thetemp value3450 is equal to the second hash3160 (act3412). If thetemp value3450 does not equal thesecond hash3160, then themethod3490 may terminate and password authentication fails (act3426). If thetemp value3450 equals thesecond hash3160, then the processing device may proceed to act3414. Atact3414, the processing device may generate a new value for thefirst salt3152. Next, atact3416, the processing device may attempt to store a fresh copy of the remote password verification data subset954 (RPVDS). (How the storage operation is performed depends on an operating environment in which themethod3490 is executing.) Then, the processing device may setRPVDS hash3156 to a result of the one-way function3292 applied to the fresh value of the first salt3152 (act3418). Then, the processing device may set thefirst hash3154 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the new value of the first salt3152 (act3420). Then, the processing device may store the new values of thefirst hash3154 and theRPVDS hash3156 in the central password verification data subset956 (act3422) Then, themethod3490 may terminate and password authentication succeeds (act3424).
• An implementer of themethod3490 uses the same one-way function3292 as he/she determined to use for themethod3290. The implementer uses the same method to combine some data elements, including thetrial password1150 with thesecond salt3158 and thetrial password1150 with thetemp value3450, as the method he/she determined to use to combine some data elements within themethod3290. In addition, the implementer uses a same value of the counter maximum3252 as the value that he/she determined to use for themethod3290. Themethod3290 is depicted inFIG. 32.
FIG. 35
• FIG. 35 illustrates an exemplary passwordverification data set3550 that may be used by a processing device when performing a password authentication method consistent with the subject matter of this disclosure. The passwordverification data set3550 may include four elements: asalt3552, thefirst hash3154, thesecond hash3160 and theRPVDS hash3156.
• FIG. 35 shows an exemplary value for thesalt3552, “eCQ8jeIIA9RwEMay0ffH”, an exemplary value for thefirst hash3154, “/bbhHZdNFiwJl1M7oZlY27y9z4E”, an exemplary value for thesecond hash3160, “1OuGoyHPhXCbDQ/6JXhkySYdB8c”, and an exemplary value for theRPVDS hash3156, “oipnAYpUL+NtRyZWJPXdcfGww3w”. The four exemplary values are all base64-encoded strings. Although, in other embodiments other encoding methods may be employed.
• The passwordverification data set3550 may be divided into the central passwordverification data subset956 and the remote passwordverification data subset954. The central passwordverification data subset956 includes thesalt3552, thesecond hash3160 and theRPVDS hash3156. The remote passwordverification data subset954 includes thefirst hash3154. When a user attempts to log in and the remote passwordverification data subset954 is available, the processing device may construct the quick passwordverification data subset1250 including thesalt3552, thefirst hash3154 and theRPVDS hash3156, and may execute a quickpassword authentication method3790 depicted inFIG. 37. When the user attempts to log in and the remote passwordverification data subset954 is not available, the processing device may construct the slow passwordverification data subset1650 including thesalt3552 and thesecond hash3160, and may execute a slowpassword authentication method3890 depicted inFIG. 38.
FIG. 36
• FIG. 36 illustrates anexemplary method3690 that may be used by the processing device to generate the passwordverification data set3550 for the user.
• The processing device may start performing themethod3690 by obtaining theuser name750 and thenew password752 from the user (act3600). Then, the processing device may generate the salt3552 (act3602). Then, the processing device may set thefirst hash3154 to a result of the one-way function3292 applied to a combination of thenew password752 and the salt3552 (act3604). Then, the processing device may set acounter3650 to one (act3606). Then, the processing device may set thesecond hash3160 equal to the first hash3154 (act3608). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set thesecond hash3160 to a result of the one-way function3292 applied to a combination of thenew password752 and the second hash3160 (act3610). Then, the processing device may increment the counter3650 (act3612). Then, the processing device may determine whether thecounter3650 is greater than a counter maximum3652 (act3614). If thecounter3650 is not greater than the counter maximum3652, then the processing device may continue to execute the loop and may return toact3610. If thecounter3650 is greater than the counter maximum3652, then the processing device may stop executing the loop and may proceed to act3616. Atact3616, the processing device sets theRPVDS hash3156 to a result of the one-way function3292 applied to thefirst hash3154. Then, the processing device may store the passwordverification data set3550 as described in the section of this disclosure titled COMMON FEATURES OFFIGS. 31-59 (act3618), and themethod3690 may terminate.
• Before implementing themethod3690, an implementer may make some determinations:
• • a one-way function to use for the one-way function3292;
  • a number of characters or bits that thesalt3552 includes, and a method for generating thesalt3552;
  • a method for combining some data elements, including thenew password752 with thesalt3552, and thenew password752 with thesecond hash3160; and
  • a value of thecounter maximum3652.
• Some factors influencing the determinations 1-3 were discussed in the section of this disclosure titled “COMMON FEATURES OF FIGS.31-59.” Some factors influencing the determination 4 are identical to the factors influencing the determination 4 of themethod3290 depicted inFIG. 32.
FIG. 37
• FIG. 37 illustrates the exemplary quickpassword authentication method3790 that may be used by the processing device to authenticate thetrial password1150. Themethod3790 may be used if the remote passwordverification data subset954, depicted inFIG. 35, is available. If the remote passwordverification data subset954 is not available, then the processing device may use themethod3890, depicted inFIG. 38, instead.
• Themethod3790 may use the quick passwordverification data subset1250 of the passwordverification data set3550, depicted inFIG. 35.
• The processing device may start performing themethod3790 by obtaining theuser name750 and thetrial password1150 from the user, and the quick passwordverification data subset1250, including thesalt3552, thefirst hash3154 and the RPVDS hash3156 (act3700). Thefirst hash3154 may be obtained from the remote passwordverification data subset954, and thesalt3552 and theRPVDS hash3156 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value3750 equal to a result of the one-way function3292 applied to the first hash3154 (act3702). Then, the processing device may determine whether thetemp value3750 is equal to the RPVDS hash3156 (act3704). If thetemp value3750 does not equal theRPVDS hash3156, then themethod3790 may terminate and password authentication fails (act3712). If thetemp value3750 equals theRPVDS hash3156, then the processing device may proceed to act3706. Atact3706, the processing device may set thetemp value3750 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesalt3552. Then, the processing device may determine whether thetemp value3750 is equal to the first hash3154 (act3708). If thetemp value3750 equals thefirst hash3154, then themethod3790 may terminate and password authentication succeeds (act3710). If thetemp value3750 does not equal thefirst hash3154, then themethod3790 may terminate and password authentication fails (act3712).
• An implementer of themethod3790 uses a same one-way function3292 as he/she determined to use for themethod3690. In addition, the implementer uses a same method to combine thetrial password1150 with thesalt3552 as the method he/she determined to use to combine some data elements within themethod3690. Themethod3690 is depicted inFIG. 36.
FIG. 38
• FIG. 38 illustrates the exemplary slowpassword authentication method3890 that may be used by the processing device to authenticate thetrial password1150.
• Themethod3890 may use the slow passwordverification data subset1650 of the passwordverification data set3550, depicted inFIG. 35.
• The processing device may start performing themethod3890 by obtaining theuser name750 and thetrial password1150 from the user, and the slow passwordverification data subset1650, including thesalt3552 and the second hash3160 (act3800). Thesalt3552 and thesecond hash3160 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value3850 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the salt3552 (act3802). Then, the processing device may set acounter3852 to one (act3804). At this point, the processing device may execute a loop. As its first action in the loop, the processing device may set thetemp value3850 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the temp value3850 (act3806). Next, the processing device may determine whether thecounter3852 is greater than a counter maximum3652 (act3808). If thecounter3852 is less than or equal to thecounter maximum3652, then the processing device may continue executing the loop and may increment the counter3852 (act3810). Next, the processing device may return to the first action of the loop,act3806. If, atact3808, thecounter3852 is greater than the counter maximum3652, then the loop may terminate and the processing device may determine whether thetemp value3850 is equal to the second hash3160 (act3812). If thetemp value3850 does not equal thesecond hash3160, then themethod3890 may terminate and password authentication fails (act3820). If thetemp value3850 equals thesecond hash3160, then the processing device may proceed to act3814. Atact3814, set thefirst hash3154 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesalt3552. Then, the processing device may attempt to store a fresh copy of the remote password verification data subset954 (act3816). (How the storage operation is performed depends on an operating environment in which themethod3890 is executing.) Then, themethod3890 may terminate and password authentication succeeds (act3818).
• An implementer of themethod3890 may use the same one-way function3292 as he/she determined to use for themethod3690. The implementer uses the same method to combine some data elements, including thetrial password1150 with thesalt3552 and thetrial password1150 with thetemp value3850, as the method he/she determined to use to combine some data elements within themethod3690. In addition, the implementer uses a same value of the counter maximum3652 as the value that he/she determined to use for themethod3690. Themethod3690 is depicted inFIG. 36.
FIG. 39
• FIG. 39 illustrates an exemplary passwordverification data set3950 that may be used by a processing device when performing a password authentication method consistent with the subject matter of this disclosure. The passwordverification data set3950 may include four elements: thefirst salt3152, thesecond salt3158, ahash3952, and theRPVDS hash3156.
• FIG. 39 shows an exemplary value for thefirst salt3152, “KyIE1HvA/GcBwxEydT9d”, an exemplary value for thesecond salt3158, “k2Zy402tSv21pAmRtKM0”, an exemplary value for thehash3952, “r5lJvIladh3Dt+TOW4AH7Qql12k”, and an exemplary value for theRPVDS hash3156, “HT3woq6OdWzwypd4c5Fie1QmMlY”. The four exemplary values are all base64-encoded strings. Although, in other embodiments, other encoding methods may be employed.
• The passwordverification data set3950 may be divided into the central passwordverification data subset956 and the remote passwordverification data subset954. The central passwordverification data subset956 includes thefirst salt3152, thehash3952 and theRPVDS hash3156. The remote passwordverification data subset954 includes thesecond salt3158. When a user attempts to log in and the remote passwordverification data subset954 is available, the processing device may construct the quick passwordverification data subset1250 including thesecond salt3158, thehash3952 and theRPVDS hash3156, and may execute a quick password authentication method4190 depicted inFIG. 41. When the user attempts to log in and the remote passwordverification data subset954 is not available, the processing device may construct the slow passwordverification data subset1650 including thefirst salt3152 and thehash3952, and may execute a slowpassword authentication method4290 depicted inFIG. 42.
FIG. 40
• FIG. 40 illustrates anexemplary method4090 that may be used by the processing device to generate the passwordverification data set3950 for the user.
• The processing device may start performing themethod4090 by obtaining theuser name750 and thenew password752 from the user (act4000). Then, the processing device may generate the first salt3152 (act4002). Then, the processing device may set thehash3952 to a result of the one-way function3292 applied to a combination of thenew password752 and the first salt3152 (act4004). Then, the processing device may set acounter4050 to one (act4006). Then, the processing device may execute a loop. As its first action in the loop, the processing device may determine whether thecounter4050 is greater than a counter maximum4052 (act4008). If thecounter4050 is not greater than the counter maximum4052, then the processing device may continue to execute the loop and may proceed to act4010. Atact4010, the processing device may set thesecond salt3158 equal to thehash3952. Then, the processing device may truncate thesecond salt3158 so that it is a proper length for a salt (act4012). Then, the processing device may set thehash3952 to a result of the one-way function3292 applied to a combination of thenew password752 and the second salt3158 (act4014). Then, the processing device may increment the counter4050 (act4016). Then, the processing device may return toact4008. If, atact4008, the processing device determines that thecounter4050 is greater than the counter maximum4052, then the processing device may stop executing the loop and may proceed to act4018. Atact4018, the processing device may set theRPVDS hash3156 to a result of the one-way function3292 applied to thesecond salt3158. Then, the processing device may store the passwordverification data set3950 as described in the section of this disclosure titled COMMON FEATURES OFFIGS. 31-59 (act4020), and themethod4090 may terminate.
• Before implementing themethod4090, an implementer may make some determinations:
• • a one-way function to use for the one-way function3292;
  • a number of characters or bits that thefirst salt3152 and thesecond salt3158 include, and a method for generating the salts;
  • a method for combining some data elements, including thenew password752 with thefirst salt3152, and thenew password752 with thesecond salt3158; and
  • a value for thecounter maximum4052.
• Some factors influencing the determinations 1-3 were discussed in the section of this disclosure titled “COMMON FEATURES OF FIGS.31-59.” Some factors influencing the determination 4 are identical to the factors influencing the determination 4 of themethod3290 depicted inFIG. 32.
FIG. 41
• FIG. 41 illustrates the exemplary quick password authentication method4190 that may be used by the processing device to authenticate thetrial password1150. The method4190 may be used if the remote passwordverification data subset954, depicted inFIG. 39, is available. If the remote passwordverification data subset954 is not available, then the processing device may use themethod4290, depicted inFIG. 42, instead.
• The method4190 may use the quick passwordverification data subset1250 of the passwordverification data set3950, depicted inFIG. 39.
• The processing device may start performing the method4190 by obtaining theuser name750 and thetrial password1150 from the user, and the quick passwordverification data subset1250, including thesecond salt3158, thehash3952 and the RPVDS hash3156 (act4100). Thesecond salt3158 may be obtained from the remote passwordverification data subset954, and thehash3952 and theRPVDS hash3156 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value4150 to a result of the one-way function3292 applied to the second salt3158 (act4102). Then, the processing device may determine whether thetemp value4150 is equal to the RPVDS hash3156 (act4104). If thetemp value4150 does not equal theRPVDS hash3156, then the method4190 may terminate and password authentication fails (act4112). If thetemp value4150 equals theRPVDS hash3156, then the processing device may proceed to act4106. Atact4106, the processing device may set thetemp value4150 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesecond salt3158. Then, the processing device may determine whether thetemp value4150 is equal to the hash3952 (act4108). If thetemp value4150 equals thehash3952, then the method4190 may terminate and password authentication succeeds (act4110). If thetemp value4150 does not equal thehash3952, then the method4190 may terminate and password authentication fails (act4112).
• An implementer of the method4190 uses a same one-way function3292 as he/she determined to use for themethod4090. In addition, the implementer uses a same method to combine thetrial password1150 and thesecond salt3158 as the method he/she determined to use to combine some data elements within themethod4090. Themethod4090 is depicted inFIG. 40.
FIG. 42
• FIG. 42 illustrates the exemplary slowpassword authentication method4290 that may be used by the processing device to authenticate thetrial password1150. Themethod4290 uses the slow passwordverification data subset1650 of the passwordverification data set3950, depicted inFIG. 39.
• The processing device may start performing themethod4290 by obtaining theuser name750 and thetrial password1150 from the user, and thefirst salt3152 and thehash3952 from the central password verification data subset956 (act4200). Then, the processing device may set acounter4250 to one (act4202). Then, the processing device may set thesecond salt3158 equal to the first salt3152 (act4204). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set thesecond salt3158 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the second salt3158 (act4206). Next, the processing device may truncate thesecond salt3158 to a proper length for a salt (act4208). Next, the processing device may increment the counter4250 (act4210). Next, the processing device may determine whether thecounter4250 is greater than a counter maximum4052 (act4212). If thecounter4250 is less than or equal to thecounter maximum4052, then the execution of the loop may continue and the processing device may return to the top of the loop,act4206. If thecounter4250 is greater than the counter maximum4052, then the the loop may terminate and the processing device may proceed to act4214. Atact4214, the processing device may set atemp value4252 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesecond salt3158. Then, the processing device may determine whether thetemp value4252 is equal to the hash3952 (act4216). If thetemp value4252 does not equal thehash3952, then themethod4290 may terminate and password authentication fails (act4222). If thetemp value4252 equals thehash3952, then the processing device may proceed to act4218. Atact4218, the processing device may attempt to store a fresh copy of the remote passwordverification data subset954. (How the storage operation is performed depends on an operating environment in which themethod4290 is executing.) Then, themethod4290 may terminate and password authentication succeeds (act4220).
• An implementer of themethod4290 uses the same one-way function3292 as he/she determined to use for themethod4090. The implementer uses the same method to combine thetrial password1150 with thefirst salt3152 as the method he/she determined to use to combine some data elements within themethod4090. In addition, the implementer uses a same value of the counter maximum4052 as the value that he/she determined to use for themethod4090. Themethod4090 is depicted inFIG. 40.
FIG. 43
• FIG. 43 illustrates an exemplary passwordverification data set4350 that may be used by a processing device when performing a password authentication method consistent with the subject matter of this disclosure. The passwordverification data set4350 may include four elements: thefirst salt3152, thesecond salt3158, thehash3952 and theRPVDS hash3156.
• The passwordverification data set4350 includes a same set of data elements as the passwordverification data set3950 ofFIG. 39, but a method used to calculate thesecond salt3158 of the passwordverification data set4350 is different than the method used to calculate thesecond salt3158 of the passwordverification data set3950 within themethod4090 ofFIG. 40.
• FIG. 43 shows an exemplary value for thefirst salt3152, “IAHzcdGFij3lggSCVXzW”, an exemplary value for thesecond salt3158, “SsN4Z2impP2P3HMrtyL3”, an exemplary value for thehash3952, “RHIFHZ+MxwoAqO2IX43RHe/pwiU”, and an exemplary value for theRPVDS hash3156, “n1OgA7jIA99tP/BMJHuTmk4Z3l4”. The four exemplary values are all base64-encoded strings. Although, in other embodiments other encoding methods may be employed.
• The passwordverification data set4350 may be divided into the central passwordverification data subset956 and the remote passwordverification data subset954. The central passwordverification data subset956 may include thefirst salt3152, thehash3952 and theRPVDS hash3156. The remote passwordverification data subset954 may include thesecond salt3158. When a user attempts to log in and the remote passwordverification data subset954 is available, the processing device may construct the quick passwordverification data subset1250 including thesecond salt3158, thehash3952, and theRPVDS hash3156, and may execute a quickpassword authentication method4590 depicted inFIG. 45. When the user attempts to log in and the remote passwordverification data subset954 is not available, the processing device may construct the slow passwordverification data subset1650 including thefirst salt3152 and thehash3952, and may execute a slowpassword authentication method4690 depicted inFIG. 46.
FIG. 44
• FIG. 44 illustrates anexemplary method4490 that may be used by the processing device to generate a passwordverification data set4350 for the user.
• The processing device may start performing themethod4490 by obtaining theuser name750 and thenew password752 from the user (act4400). Then, the processing device may generate a randomreal number4450 between 0 and 1 (act4402). Then, the processing device may generate the first salt3152 (act4404). Then, the processing device may set thesecond salt3158 equal to the first salt3152 (act4406). Then, the processing device may determine whether the randomreal number4450 is less than a minimum real number4452 (act4408). If the randomreal number4450 is not less than the minimumreal number4452, then the processing device may execute a loop. If the randomreal number4450 is less than the minimumreal number4452, then the processing device may stop executing the loop. (It is highly likely that the processing device will enter the loop if the minimumreal number4452 is close to zero.) At the beginning of the loop (act4410), the processing device may set thesecond salt3158 to a result of the one-way function3292 applied to a combination of thenew password752 and thesecond salt3158. Then, the processing device may truncate thesecond salt3158 so that it is a proper length for a salt (act4412). Then, the processing device may set thesecond salt3158 to a result of aperturb function4492 applied to the second salt3158 (act4414). Then, the processing device may generate another randomreal number4450 between 0 and 1 (act4416). Then, the processing device may return to act4408 where it again may determine whether the randomreal number4450 is less than the minimumreal number4452. If the randomreal number4450 is not less than the minimumreal number4452, then the processing device may continue executing the loop. If the randomreal number4450 is less than the minimumreal number4452, then the processing device may stop executing the loop and may proceed to act4418. Atact4418, the processing device may set thehash3952 to a result of the one-way function3292 applied to a combination of thenew password752 and thesecond salt3158. Then, the processing device may set theRPVDS hash3156 to a result of the one-way function3292 applied to the second salt3158 (act4420). Then, the processing device may store the passwordverification data set4350 as described in the section of this disclosure titled COMMON FEATURES OFFIGS. 31-59 (act4422), and themethod4490 may terminate.
• Before implementing themethod4490, an implementer may make some determinations:
• • a one-way function to use for the one-way function3292;
  • a number of characters or bits that thefirst salt3152 and thesecond salt3158 include, and a method for generating the salts;
  • a method for combining thenew password752 with thesecond salt3158;
  • a value of the minimumreal number4452; and
  • a perturb function to use for theperturb function4492 within the loop of themethod4490.
• Some factors influencing the determinations 1-3 were discussed in the section of this disclosure titled “COMMON FEATURES OF FIGS.31-59.”
• Regarding the determination 4, the implementer may choose the value of the minimumreal number4452 to be a positive real number close to zero. Choosing a smaller value of the minimumreal number4452, as opposed to choosing a larger value of the minimumreal number4452, may have the following effects:
• • themethod4490 may cycle through the loop more times (on average);
  • themethod4490 may take more time to execute;
  • a slowpassword authentication method4690, depicted inFIG. 46, may take more time to execute; and
  • the passwordverification data set4350 generated by themethod4490 may be more resistant to attacks.
• Regarding the determination 5, the implementer may choose theperturb function4492 so that it modifies its input in a way that depends on a number of iterations of the loop that have already been performed. Theperturb function4492 may also be chosen so that its output has at least as much entropy as its input. Many perturb functions meet the two criteria, including, but not limited to, adding the number of iterations that have already been performed to the input and bitwise exclusive or-ing the number of iterations that have already been performed to the input. A purpose of theperturb function4492 is to make it more difficult for an attacker to build a rainbow table.
• The implementer may make some modifications to the method4490:
• • add an action that causes the loop of themethod4490 to execute a minimum number of times before exiting the loop;
  • add an action that causes the loop of themethod4490 to execute no more than a maximum number of times; and
  • omit theact4414, thereby not using theperturb function4492.
FIG. 45
• FIG. 45 illustrates the exemplary quickpassword authentication method4590 that may be used by the processing device to authenticate thetrial password1150. Themethod4590 may be used if the remote passwordverification data subset954, depicted inFIG. 43, is available. If the remote passwordverification data subset954 is not available, then the processing device may use themethod4690, depicted inFIG. 46, instead.
• Themethod4590 uses the quick passwordverification data subset1250 of the passwordverification data set4350, depicted inFIG. 43.
• The processing device may start performing themethod4590 by obtaining theuser name750 and thetrial password1150 from the user, and the quick passwordverification data subset1250, including thesecond salt3158, thehash3952 and the RPVDS hash3156 (act4500). Thesecond salt3158 may be obtained from the remote passwordverification data subset954, and thehash3952 and theRPVDS hash3156 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value4550 to a result of the one-way function3292 applied to the second salt3158 (act4502). Then, the processing device may determine whether thetemp value4550 is equal to the RPVDS hash3156 (act4504). If thetemp value4550 does not equal theRPVDS hash3156, then themethod4590 may terminate and password authentication fails (act4512). If thetemp value4550 equals theRPVDS hash3156, then the processing device may proceed to act4506. Atact4506, the processing device may set thetemp value4550 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesecond salt3158. Then, the processing device may determine whether thetemp value4550 is equal to the hash3952 (act4508). If thetemp value4550 equals thehash3952, then themethod4590 may terminate and password authentication succeeds (act4510). If thetemp value4550 does not equal thehash3952, then themethod4590 may terminate and password authentication fails (act4512).
• An implementer of themethod4590 uses a same one-way function3292 as he/she determined to use for themethod4490. In addition, the implementer uses a same method to combine thetrial password1150 and thesecond salt3158 as the method he/she determined to use to combine some data elements within themethod4490. Themethod4490 is depicted inFIG. 44.
FIG. 46
• FIG. 46 illustrates the exemplary slowpassword authentication method4690 that may be used by the processing device to authenticate thetrial password1150. Themethod4690 uses the slow passwordverification data subset1650 of the passwordverification data set4350, depicted inFIG. 43.
• The processing device may start performing themethod4690 by obtaining theuser name750 and thetrial password1150 from the user, and thefirst salt3152 and thehash3952 from the central password verification data subset956 (act4600). Then, the processing device may set thesecond salt3158 equal to the first salt3152 (act4602). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set atemp value4650 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the second salt3158 (act4604). Then, the processing device may determine whether thetemp value4650 equals the hash3952 (act4606). If thetemp value4650 equals thehash3952, then the processing device may stop executing the loop and may proceed to act4614. Atact4614, the processing device may attempt to store a fresh copy of the remote password verification data subset954 (RPVDS). (How the storage operation is performed depends on an operating environment in which themethod4690 is executing.) Then, themethod4690 may terminate and password authentication succeeds (act4616). If, atact4606, thetemp value4650 does not equal thehash3952, then the processing device may continue executing the loop and may proceed to act4608. Atact4608, the processing device may set thesecond salt3158 equal to thetemp value4650. Then, the processing device may truncate thesecond salt3158 to a proper length for a salt (act4610). Then, the processing device may set thesecond salt3158 to a result of theperturb function4492 applied to the second salt3158 (act4612). Then, the processing device may return to the top of the loop (act4604).
• An implementer of themethod4690 uses the same one-way function3292 as he/she determined to use for themethod4490. The implementer uses asame perturb function4492 as he/she determined to use for themethod4490. In addition, the implementer uses the same method to combine thetrial password1150 and thesecond salt3158 as the method he/she determined to use to combine some data elements within themethod4490. Themethod4490 is depicted inFIG. 44.
• Themethod4690 lacks an action in which the method terminates with a password authentication failure. If thetrial password1150 is not a correct password, then the loop of themethod4690 may continue indefinitely. The lack of a password authentication failure action makes the passwordverification data set4350 more resistant to attacks. An attacker's processing device may attempt to authenticate many trial passwords using themethod4690, but the attacker will probably modify themethod4690 to exit the loop based on some criteria. A difficulty confronting the attacker is that, depending on the loop exit criteria that the attacker chooses, the attacker's processing device may spend a very long time trying to authenticate eachtrial password1150, or the attacker's processing device may fail to authenticate acorrect trial password1150, or both. To better understand the difficulty confronting the attacker, seeFIG. 59 that illustrates anexemplary method5990 that may be used to perform a dictionary attack or a brute force attack on the passwordverification data set4350.
FIG. 47
• FIG. 47 illustrates an exemplary passwordverification data set4750 that may be used by a processing device when performing a password authentication method consistent with the subject matter of this disclosure. The passwordverification data set4750 includes five elements: thesalt3552, apartial salt4754, thehash3952, asalt salt4752 and theRPVDS hash3156.
• Thepartial salt4754 is a truncated copy of thesalt3552. Thesalt salt4752 is a salt that is combined with thesalt3552 before an application of the one-way function3292 to create theRPVDS hash3156. Thesalt salt4752 is combined with thesalt3552 to give theRPVDS hash3156 more entropy.
• FIG. 47 shows an exemplary value for thesalt3552, “bWQsmqDGPa9gBSme2zLX”, an exemplary value for thepartial salt4754, “bWQsmqDGPa9gBSme”, an exemplary value for thehash3952, “/u3VVuQuutw1ECS17Q3rGZfjKXU”, an exemplary value for thesalt salt4752, “jfu3cco8FYrmKhDUlfYl”, and an exemplary value for theRPVDS hash3156, “ynsV0ih7liuusjng3Ej5L2a3+kM”. The five exemplary values are all base64-encoded strings. Although, in other embodiments other encoding methods may be employed.
• The passwordverification data set4750 may be divided into the central passwordverification data subset956 and the remote passwordverification data subset954. The central passwordverification data subset956 includes thepartial salt4754, thehash3952, and theRPVDS hash3156. The remote passwordverification data subset954 includes thesalt3552 and thesalt salt4752. When a user attempts to log in and the remote passwordverification data subset954 is available, the processing device may construct the quick passwordverification data subset1250 including thesalt3552, thesalt salt4752, thehash3952, and theRPVDS hash3156, and may execute a quickpassword authentication method4990 depicted inFIG. 49. When the user attempts to log in and the remote passwordverification data subset954 is not available, the processing device may construct the slow passwordverification data subset1650 including thepartial salt4754 and thehash3952, and may execute a slowpassword authentication method5090 depicted inFIG. 50.
FIG. 48
• FIG. 48 illustrates anexemplary method4890 that may be used by the processing device to generate the passwordverification data set4750 for a user.
• The processing device may start performing themethod4890 by obtaining theuser name750 and thenew password752 from the user (act4800). Then, the processing device may generate the salt3552 (act4802). Then, the processing device may set thepartial salt4754 equal to the salt3552 (act4804). Then, the processing device may truncate thepartial salt4754 to a proper length for the partial salt (act4806). Then, the processing device may set thehash3952 to a result of the one-way function3292 applied to a combination of thenew password752 and the salt3552 (act4808). Then, the processing device may generate the salt salt4752 (act4810). Then, the processing device may set theRPVDS hash3156 to a result of the one-way function3292 applied to a combination of thesalt3552 and the salt salt4752 (act4812). Then, the processing device may store the password verification data set4750 (PVDS) as described in the section of this disclosure titled COMMON FEATURES OFFIGS. 31-59 (act4814), and themethod4890 may terminate.
• Before implementing themethod4890, an implementer may make some determinations:
• • a one-way function to use for the one-way function3292;
  • a number of characters or bits that thesalt3552 and thesalt salt4752 include, and a method for generating the salts;
  • a method for combining some data elements, such as thenew password752 with thesalt3552, and thesalt3552 with thesalt salt4752; and
  • a number of bits to remove from thesalt3552 when generating thepartial salt4754.
• Some factors influencing the determinations 1-3 were discussed in the section of this disclosure titled “COMMON FEATURES OF FIGS.31-59.”
• Regarding the determination 4, removing a larger number characters or bits from thesalt3552 when generating thepartial salt4754, as opposed to removing a smaller number of characters or bits from thesalt3552 when generating thepartial salt4754, may have the following effects:
• • the slowpassword authentication method5090, depicted inFIG. 50, may take more time to execute; and
  • the passwordverification data set4750 generated by themethod4890 may be more resistant to attacks.
• With modern processing devices, some reasonable values to consider for the number of bits to remove from thesalt3552 when generating thepartial salt4754 may be in a range from 20 to 36. In the exemplary data depicted inFIG. 47,24 bits (four 6-bit base64 characters) have been removed from thesalt3552 to generate thepartial salt4754.
FIG. 49
• FIG. 49 illustrates the exemplary quickpassword authentication method4990 that may be used by the processing device to authenticate thetrial password1150. Themethod4990 may be used if the remote passwordverification data subset954, depicted inFIG. 47, is available. If the remote passwordverification data subset954 is not available, then the processing device may use themethod5090, illustrated inFIG. 50, instead.
• Themethod4990 uses the quick passwordverification data subset1250 of the passwordverification data set4750, depicted inFIG. 47.
• The processing device may start performing themethod4990 by obtaining theuser name750 and thetrial password1150 from the user, and the quick passwordverification data subset1250, including thesalt3552, thesalt salt4752, thehash3952, and the RPVDS hash3156 (act4900). Thesalt3552 and thesalt salt4752 may be obtained from the remote passwordverification data subset954, and thehash3952 and theRPVDS hash3156 may be obtained from the central passwordverification data subset956. Then, the processing device may set atemp value4950 to a result of the one-way function3292 applied to a combination of thesalt3552 and the salt salt4752 (act4902). Then, the processing device may determine whether thetemp value4950 is equal to the RPVDS hash3156 (act4904). If thetemp value4950 does not equal theRPVDS hash3156, then themethod4990 may terminate and password authentication fails (act4912). If thetemp value4950 equals theRPVDS hash3156, then the processing device may proceed to act4906. Atact4906, the processing device may set thetemp value4950 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesalt3552. Then, the processing device may determine whether thetemp value4950 is equal to the hash3952 (act4908). If thetemp value4950 equals thehash3952, then themethod4990 may terminate and password authentication succeeds (act4910). If thetemp value4950 does not equal thehash3952, then themethod4990 may terminate and password authentication fails (act4912).
• An implementer of themethod4990 uses a same one-way function3292 as he/she determined to use for themethod4890. In addition, the implementer uses a same method to combine some data elements, such as thesalt3552 with thesalt salt4752 and thetrial password1150 with thesalt3552, as the method he/she determined to use to combine some data elements within themethod4890. Themethod4890 is depicted inFIG. 48.
FIG. 50
• FIG. 50 illustrates the exemplary slowpassword authentication method5090 that may be used by the processing device to authenticate thetrial password1150. Themethod5090 uses the slow passwordverification data subset1650 of the passwordverification data set4750, depicted inFIG. 47.
• To authenticate thetrial password1150, themethod5090 appends all possible values to thepartial salt4754 that extend thepartial salt4754 to a proper length for thesalt3552. A data element that extends thepartial salt4754 to the proper length for thesalt3552 is referred to herein as asalt completion5050.
• The processing device may start performing themethod5090 by obtaining theuser name750 and thetrial password1150 from the user, and thepartial salt4754 and thehash3952 from the central password verification data subset956 (act5000). Then, the processing device may set thesalt completion5050 equal to a first possible salt completion value (act5002). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set thesalt3552 to a combination of thepartial salt4754 and the salt completion5050 (act5004). Then, the processing device may set atemp value5052 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the salt3552 (act5006). Then, the processing device may determine whether thetemp value5052 equals the hash3952 (act5008). If thetemp value5052 equals thehash3952, then the processing device may stop executing the loop and may proceed to act5014. Atact5014, the processing device may attempt to store a fresh copy of the remote password verification data subset954 (RPVDS). (How the storage operation is performed depends on an operating environment in which themethod5090 is executing.) Then, themethod5090 may terminate and password authentication succeeds (act5016). If, atact5008, thetemp value5052 does not equal thehash3952, then the processing device may continue executing the loop and may proceed to act5010. Atact5010, the processing device may determine whether there are more values of thesalt completion5050 left to try. If there are no more values of thesalt completion5050 left to try, then themethod5090 may terminate and password authentication fails (act5018). If there are more values of thesalt completion5050 left to try, then the processing device may continue executing the loop and may proceed to act5012. Atact5012, the processing device may set thesalt completion5050 equal to a next possible salt completion value that has not yet been tried. Then, the processing device may return to the top of the loop atact5004.
• An implementer of themethod5090 uses the same one-way function3292 as he/she determined to use for themethod4890. In addition, the implementer uses the same method to combine some data elements, such as thepartial salt4754 with thesalt completion5050 and thetrial password1150 with thesalt3552, as the method he/she determined to use to combine some data elements within themethod4890. Themethod4890 is depicted inFIG. 48.
FIG. 51
• FIG. 51 illustrates an exemplary passwordverification data set5150 that may be used by a processing device when performing a password authentication method consistent with the subject matter of this disclosure. All the previously described exemplary password verification data sets included salts and hashes. However, some embodiments of password verification data sets, such as the passwordverification data set5150, include neither salts nor hashes.
• The passwordverification data set5150 represents a part of a polynomial equation of one variable. Another part of the polynomial equation may be derived from thetrial password1150. A process of authenticating thetrial password1150 includes finding a numerical solution to the polynomial equation.
• The passwordverification data set5150 includes the following data elements: asolution5151 that is a solution to the polynomial equation of one variable; a coefficient5152 (C12), a coefficient5153 (C13), a coefficient5154 (C14), . . . , a coefficient5163 (C23) of the polynomial equation, where the coefficient5152 (C12) is a coefficient of the x̂12 term, where the coefficient5153 (C13) is a coefficient of the x̂13 term, etc.; and aconstant term5164 that is a constant term of the polynomial equation.
• Coefficient5260 (CO) through coefficient5261 (C11) are derived from thetrial password1150 and are not part of the passwordverification data set5150.
• The polynomial equation may be expressed as a mathematical formula as follows:
• 
  C0+C1×x+C2×x²+C3×x³+ . . . +C23×X²³=CT
• In the formula, C0 to C23 are the coefficients, x is the variable, and CT is the constant term. The left side of the equation, to the left of the equals sign (=), is referred to herein as a polynomial expression.
• To create exemplary data forFIG. 51, the coefficient5152 (C12) through the coefficient5163 (C23) were generated randomly. If a different number of randomly generated coefficients are included in the passwordverification data set5150, then a number of terms of the polynomial equation may be more than, or less than, 24.
• FIG. 51 depicts exemplary values for the data elements of the passwordverification data set5150.
• • the solution5151: 5697328
  • the coefficient5152 (C12): 83
  • the coefficient5153 (C13): 85
  • the coefficient5154 (C14): 9
  • the coefficient5155 (C15): 144
  • the coefficient5156 (C16): 227
  • the coefficient5157 (C17): 45
  • the coefficient5158 (C18): 155
  • the coefficient5159 (C19): 215
  • the coefficient5160 (C20): 194
  • the coefficient5161 (C21): 71
  • the coefficient5162 (C22): 214
  • the coefficient5163 (C23): 139
  • the constant term5164: 3337744153087612374360770407796907519861176298636950 360031677000393191563090385368815180624513159813319514779483891715806424 7024198006479887559249385769336753
• The exemplary values are all decimal numbers. Although, in other embodiments other encoding methods may be employed. All the numbers are less than ten million except for theconstant term5164, a decimal representation of which includes 158 digits.
• The passwordverification data set5150 may be divided into the central passwordverification data subset956 and the remote passwordverification data subset954. The central passwordverification data subset956 includes the coefficient5152 (C12), the coefficient5153 (C13), . . . , the coefficient5163 (C23), and theconstant term5164. The remote passwordverification data subset954 includes thesolution5151. When a user attempts to log in and the remote passwordverification data subset954 is available, the processing device may construct the quick passwordverification data subset1250 that includes a same set of data elements as belong to the passwordverification data set5150, and may execute a quickpassword authentication method5390 depicted inFIG. 53. When the user attempts to log in and the remote passwordverification data subset954 is not available, the processing device may construct the slow passwordverification data subset1650 that includes a same set of data elements as belong to the central passwordverification data subset956, and may execute a slowpassword authentication method5490 depicted inFIG. 54.
FIG. 52
• FIG. 52 illustrates anexemplary method5290 that may be used by the processing device to generate the passwordverification data set5150 for the user.
• The processing device may start performing themethod5290 by obtaining theuser name750 and thenew password752 from the user (act5200). Then, the processing device may randomly generate the coefficient5152 (C12), the coefficient5153 (C13), the coefficient5154 (C14), the coefficient5155 (C15), the coefficient5156 (C16), the coefficient5157 (C17), the coefficient5158 (C18), the coefficient5159 (C19), the coefficient5160 (C20), the coefficient5161 (C21), the coefficient5162 (C22), and the coefficient5163 (C23) (act5202). Then, the processing device may derive the coefficient5250 (C0), the coefficient5251 (C1), the coefficient5252 (C2), the coefficient5253 (C3), the coefficient5254 (C4), the coefficient5255 (C5), the coefficient5256 (C6), the coefficient5257 (C7), the coefficient5258 (C8), the coefficient5259 (C9), the coefficient5260 (C10), and the coefficient5261 (C11) from the new password752 (act5204). (The coefficient5250 (C0) through the coefficient5261 (C11) are lower-order coefficients of a polynomial expression of one variable and the coefficient5152 (C12) through the coefficient5163 (C23) are higher-order coefficients of the polynomial expression.) Then, the processing device may set thesolution5151 equal to a randomly generated integer that is greater than zero and less than or equal to a maximum solution5262 (act5206). Then, the processing device may set theconstant term5164 equal to a numerical result of substituting thesolution5151 for the one variable of the polynomial expression (act5208). Then, the processing device may store the passwordverification data set5150 as described in the section of this disclosure titled COMMON FEATURES OFFIGS. 31-59 (act5210), and themethod5290 may terminate.
• Before implementing themethod5290, an implementer may make some determinations:
• • a number of coefficients of the polynomial expression to generate randomly. If the number of randomly generated coefficients is eight or more, then the polynomial equation will be difficult for an attacker to solve. In the exemplary data ofFIG. 51, the number of randomly generated coefficients is 12;
  • a range of numbers from which each randomly generated coefficient is selected. The range of numbers for the exemplary data ofFIG. 51 is 0 through 255;
  • a method for deriving the lower-order coefficients of the polynomial expression from thenew password752. To generate the exemplary data ofFIG. 51, numerical ASCII values of each character of thenew password752 were obtained; and
  • a value of themaximum solution5262 that is a largest number that the randomly generatedsolution5151 can attain. To generate the exemplary data ofFIG. 51, themaximum solution5262 was set equal to 16777216 (two raised to a power of 24).
• Increasing the number of coefficients of the polynomial expression that are generated randomly, as opposed to decreasing the number of coefficients of the polynomial expression that are generated randomly, widening the range of numbers from which each randomly generated coefficient is selected, as opposed to narrowing the range of numbers from which each randomly generated coefficient is selected, and increasing the value of themaximum solution5262, as opposed to decreasing the value of themaximum solution5262, may have the following effects:
• • solving the polynomial equation may become more time-consuming, making attacks more difficult; and
  • themethod5290 that generates the passwordverification data set5150, and themethod5390 and themethod5490 that use the passwordverification data set5150 to authenticate thetrial password1150, may take more time to execute.
FIG. 53
• FIG. 53 illustrates the exemplary quickpassword authentication method5390 that may be used by the processing device to authenticate thetrial password1150. Themethod5390 may be used if the remote passwordverification data subset954, depicted inFIG. 51, is available. If the remote passwordverification data subset954 is not available, then the processing device may use themethod5490, illustrated inFIG. 54, instead.
• Themethod5390 uses the quick passwordverification data subset1250 of the passwordverification data set5150, depicted inFIG. 51.
• The processing device may start performing themethod5390 by obtaining theuser name750 and thetrial password1150 from the user, and the quick passwordverification data subset1250, including thesolution5151, the coefficient5152 (C12), the coefficient5153 (C13), . . . , the coefficient5163 (C23), and the constant term5164 (act5300). Thesolution5151 may be obtained from the remote passwordverification data subset954, and the coefficient5152 (C12), the coefficient5153 (C13), . . . , the coefficient5163 (C23), and theconstant term5164 may be obtained from the central passwordverification data subset956. Then, the processing device may derive the coefficient5250 (C0) through the coefficient5261 (C11) from the trial password1150 (act5302). (The coefficient5260 (C0) through the coefficient5261 (C11) and the coefficient5152 (C12) through the coefficient5163 (C23) are the coefficients of the polynomial expression.) Then, the processing device may set atemp value5350 to a numerical result of substituting thesolution5151 for the one variable of the polynomial expression (act5304). Then, the processing device may determine whether thetemp value5350 is equal to the constant term5164 (act5306). If thetemp value5350 equals theconstant term5164, then themethod5390 may terminate and password authentication succeeds (act5308). If thetemp value5350 does not equal theconstant term5164, then themethod5390 may terminate and password authentication fails (act5310).
FIG. 54
• FIG. 54 illustrates the exemplary slowpassword authentication method5490 that may be used by the processing device to authenticate thetrial password1150. Themethod5490 uses the slow passwordverification data subset1650 of the passwordverification data set5150, depicted inFIG. 51.
• The processing device may start performing themethod5490 by obtaining theuser name750 and thetrial password1150 from the user, and the slow passwordverification data subset1650, including the coefficient5152 (C12), the coefficient5153 (C13), . . . , the coefficient5163 (C23), and the constant term5164 (act5400). The coefficient5152 (C12), the coefficient5153 (C13), . . . , the coefficient5163 (C23), and theconstant term5164 may be obtained from the central passwordverification data subset956. Then, the processing device may derive the coefficient5250 (C0) through the coefficient5261 (C11) from the trial password1150 (act5402). (The coefficient5250 (C0) through the coefficient5261 (C11) and the coefficient5152 (C12) through the coefficient5163 (C23) are the coefficients of the polynomial expression.) Then, the processing device may set thesolution5151 to one (act5404). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set atemp value5450 to the numerical result of substituting thesolution5151 for the one variable in the polynomial expression (act5406). Then, the processing device may determine whether thetemp value5450 equals the constant term5164 (act5408). If thetemp value5450 equals theconstant term5164, then the processing device may proceed to act5410. Atact5410, the processing device may attempt to store a fresh copy of the remote passwordverification data subset954. Then themethod5490 may terminate and password authentication succeeds (act5412). If, atact5408, thetemp value5450 does not equal theconstant term5164, then the processing device may continue executing the loop and may proceed to act5414. Atact5414, the processing device may increment thesolution5151. Then, the processing device may determine whether thesolution5151 is greater than a maximum solution5262 (act5416). If thesolution5151 is greater than themaximum solution5250, then themethod5490 may terminate and password authentication fails (act5418). If thesolution5151 is not greater than themaximum solution5250, then the processing device may continue executing the loop and may return toact5406.
Cryptographic Keys
• Acryptographic key5656 ofFIG. 56, in conjunction with an encryption method, including, but not limited to, Data Encryption Standard (DES), triple-DES, Advanced Encryption Standard (AES) or Blowfish, may be used by a processing device to encrypt or decrypt a sensitive data set.
• The storage of the cryptographic key5656 raises many of the same concerns as the storage of a password. For example, if the cryptographic key5656 is stored unencrypted, then it may be stolen or misused. If the cryptographic key5656 is generated from a password, then an attacker may attempt to crack the password to reconstruct thecryptographic key5656.
• Some password verification data sets presented previously may be used, in conjunction with the password, to generate thecryptographic key5656.
• A set of data elements used to generate the cryptographic key5656 is referred to herein as a cryptographickey data set5550. The cryptographickey data set5550 is stored in one or more storage devices. The cryptographic key5656 is not stored but is instead generated as needed. The cryptographickey data set5550 is analogous to the password verification data set.
• A subset of the cryptographic key data set that is stored in a central storage device is referred to herein as a central cryptographickey data subset5554. The central cryptographickey data subset5554 is analogous to the central passwordverification data subset956.
• A subset of the cryptographic key data set that is stored in a remote storage device is referred to herein as a remote cryptographickey data subset5552. The remote cryptographickey data subset5552 is analogous to the remote passwordverification data subset954.
• A subset of the cryptographic key data set5050 that is provided as input to a quick method for generating a cryptographic key is referred to herein as a quick cryptographickey data subset5558. The quick cryptographickey data subset5558 is analogous to the quick passwordverification data subset1250.
• A subset of the cryptographic key data set that is provided as input to a slow method for generating a cryptographic key is referred to herein as a slow cryptographickey data subset5560. The slow cryptographickey data subset5560 is analogous to the slow passwordverification data subset1650.
• A sensitive data set may be identified by adata set name5650. The processing device uses thedata set name5650 to look up the cryptographic key data set for the sensitive data set. Thedata set name5650 plays a role for the sensitive data set that is analogous to a role of theuser name750 for a user.
• However, there is a significant difference between the use of thedata set name5650 and the use of theuser name750. Theuser name750 is associated with the password verification data set that is not shared with any other user. Thedata set name5650 may be associated with the cryptographic key data set that may be shared with a different sensitive data set that uses a different data set name. If multiple sensitive data sets share a same cryptographic key data set, then the multiple sensitive data sets may each be encrypted and decrypted with a same cryptographic key, and the user may use a same password to encrypt or decrypt any of the multiple sensitive data sets.
• Some exemplary cryptographic key data sets may include aRCKDS hash5556 that serves a similar function as theRPVDS hash3156 in some password verification data sets. TheRCKDS hash5556 is set equal to a result of a one-way function applied to a combination of at least one data element from the remote cryptographic key data subset. TheRCKDS hash5556 belongs to the central cryptographic key data subset. When the processing device performs the quick cryptographic key generation method, and obtains the at least one data element from the remote password verification data subset, the processing device may verify the authenticity of the at least one data element by calculating a result of the one-way function applied to a combination of the at least one data element and comparing the result to theRCKDS hash5556. If an attacker spoofs the at least one data element, then a result of the one-way function applied to a combination of the attacker's spoofed at least one data element will almost certainly be different than theRCKDS hash5556 stored in the central cryptographic key data subset, and the attacker's attempt to generate the cryptographic key5656 will be rejected.
• FIGS. 55-58 are closely related.FIG. 55 depicts a specific cryptographickey data set5550 and four of its subsets: a remote cryptographickey data subset5552, a central cryptographickey data subset5554, a quick cryptographickey data subset5558 and a slow cryptographickey data subset5560.FIG. 56 depicts amethod5690 that may generate the cryptographickey data set5550 and thecryptographic key5656.FIG. 57 depicts amethod5790 that may generate the cryptographic key5656 based on the quick cryptographickey data subset5558.FIG. 58 depicts amethod5890 that may generate the cryptographic key5656 based on the slow cryptographickey data subset5560.
• In the embodiment depicted inFIGS. 55-58, a same processing device may perform the three methods depicted inFIGS. 56-58. In other embodiments, different processing devices may perform the three methods.
FIG. 55
• FIG. 55 illustrates the exemplary cryptographic key data set5550 that may be used by a processing device when performing a cryptographic key generation method consistent with the subject matter of this disclosure. The cryptographickey data set5550 is based on the passwordverification data set3950 depicted inFIG. 39. Theexemplary method5690, depicted inFIG. 56, may generate the cryptographickey data set5550 and is based on theexemplary method4090, depicted inFIG. 40. Theexemplary method5790, depicted inFIG. 57, may quickly generate the cryptographic key5656, and is based on the exemplary method4190, depicted inFIG. 41. Theexemplary method5890, depicted inFIG. 58, may slowly generate the cryptographic key5656, and is based on theexemplary method4290, depicted inFIG. 42.
• The cryptographickey data set5550 includes four elements: thefirst salt3152, thesecond salt3158, thehash3952, and theRCKDS hash5556.
• FIG. 55 shows an exemplary value for thefirst salt3152, “KyIE1HvA/GcBwxEydT9d”, an exemplary value for thesecond salt3158, “k2Zy402tSv21pAmRtKM0”, an exemplary value for thehash3952, “r5lJvIladh3Dt+TOW4AH7Qq1l2k”, and an exemplary value for theRCKDS hash5556, “HT3woq6OdWzwypd4c5Fie1QmMlY”. The four exemplary values are all base64-encoded strings. Although, in other embodiments other encoding methods may be employed.
• The cryptographickey data set5550 may be divided into the central cryptographickey data subset5554 that may be stored in a central storage device, and the remote cryptographickey data subset5552 that may be stored in a remote storage device. The central cryptographickey data subset5554 includes thefirst salt3152, thehash3952 and theRCKDS hash5556. The remote cryptographickey data subset5552 includes thesecond salt3158. When a user attempts to decrypt the sensitive data set and the remote cryptographickey data subset5552 is available, the processing device may construct a quick cryptographickey data subset5558 including thesecond salt3158, thehash3952, and theRCKDS hash5556, and may execute the quick cryptographickey generation method5790 depicted inFIG. 57. When the user attempts to decrypt the sensitive data set and the remote cryptographickey data subset5552 is not available, the processing device may construct the slow cryptographickey data subset5560 including thefirst salt3152 and thehash3952, and may execute the slow cryptographickey generation method5890 depicted inFIG. 58.
• In an alternative embodiment, an exemplary cryptographic key data set may be based on the passwordverification data set4350 depicted inFIG. 43.
FIG. 56
• FIG. 56 illustrates theexemplary method5690 that may be used by the processing device to generate the cryptographickey data set5550 and the cryptographic key5656 from thenew password752 provided by the user. The processing device may then use the cryptographic key5656 to encrypt the sensitive data set.
• The processing device may start performing themethod5690 by obtaining thedata set name5650 and thenew password752 from the user (act5600). The user may indicate a desire for a cryptographic key and may provide thedata set name5650 and thenew password752 in a manner similar to the manner previously described with respect to the user providing a user name and password.
• The processing device may then generate the first salt3152 (act5602). Then, the processing device may set thehash3952 to a result of the one-way function3292 applied to a combination of thenew password752 and the first salt3152 (act5604). Then, the processing device may set acounter5652 to one (act5606). Then, the processing device may execute a loop. As its first action in the loop, the processing device may determine whether thecounter5652 is greater than a counter maximum5654 (act5608). If thecounter5652 is not greater than the counter maximum5654, then the processing device may continue to execute the loop and may proceed to act5610. Atact5610, the processing device may set thesecond salt3158 equal to thehash3952. Then, the processing device may truncate thesecond salt3158 so that it is a proper length for a salt (act5612). Then, the processing device may set thehash3952 to a result of the one-way function3292 applied to a combination of thenew password752 and the second salt3158 (act5614). Then, the processing device may increment the counter5652 (act5616). Then, the processing device may return toact5608. If, atact5608, the processing device determines that thecounter5652 is greater than the counter maximum5654, then the processing device may stop executing the loop and may proceed to act5618. Atact5618, the processing device may set theRCKDS hash5556 to a result of the one-way function3292 applied to thesecond salt3158. Then, the processing device may set the cryptographic key5656 to a result of the one-way function3292 applied to a combination of thenew password752, thesecond salt3158, and the hash3952 (act5620). Then, the processing device may store the cryptographic key data set5550 (act5622) as follows: the central cryptographickey data subset5554 may be stored in the central storage device; and the remote cryptographickey data subset5552 may be stored in the remote storage device. Then, the processing device may encrypt the sensitive data set, having the data setname5650, using the cryptographic key5656, and themethod5690 may terminate (act5624).
• Before implementing themethod5690, an implementer may make some determinations:
• • a one-way function to use for the one-way function3292;
  • a number of characters or bits that thefirst salt3152 and thesecond salt3158 include, and a method for generating the salts;
  • a method for combining some data elements, such as thenew password752 with thefirst salt3152, thenew password752 with thesecond salt3158, and thenew password752 with thesecond salt3158 and thehash3952; and
  • a value of thecounter maximum5654.
• Some factors influencing the determinations 1-3 were discussed in the section of this disclosure titled “COMMON FEATURES OF FIGS.31-59.” Regarding the determination 4, choosing a larger value of the counter maximum5654, as opposed to choosing a smaller value of the counter maximum5654, may have the following effects:
• • themethod5690 may take longer to execute;
  • the cryptographickey data set5550 generated by themethod5690 may be more resistant to attacks; and
  • themethod5890, depicted inFIG. 58, that generates the cryptographic key5656 when the remote cryptographickey data subset5552 is not available, may take longer.
• With modern processing devices, some values for thecounter maximum3252 of one hundred thousand to one billion may be considered.
FIG. 57
• FIG. 57 illustrates the exemplary quick cryptographickey generation method5790 that may be used to generate the cryptographic key5656 from the cryptographic key data set5550 depicted inFIG. 55. The cryptographic key5656 may then be used to decrypt the sensitive data set. Themethod5790 may be used if the remote cryptographickey data subset5552, depicted inFIG. 55, is available. If the remote cryptographickey data subset5552 is not available, then the processing device may use themethod5890, depicted inFIG. 58, instead.
• Themethod5790 uses the quick cryptographickey data subset5558 of the cryptographickey data set5550, depicted inFIG. 55.
• The processing device may start performing themethod5790 by obtaining thedata set name5650 and thetrial password1150 from the user, and the quick cryptographickey data subset5558, including thesecond salt3158, thehash3952 and the RCKDS hash5556 (act5700). Thesecond salt3158 may be obtained from the remote cryptographickey data subset5552, and thehash3952 and theRCKDS hash5556 may be obtained from the central cryptographickey data subset5554. Then, the processing device may set atemp value5750 to a result of the one-way function3292 applied to the second salt3158 (act5702). Then, the processing device may determine whether thetemp value5750 is equal to the RCKDS hash5556 (act5704). If thetemp value5750 does not equal theRCKDS hash5556, then themethod5790 may terminate and fail to generate the cryptographic key5656 (act5710). If thetemp value5750 equals theRCKDS hash5556, then the processing device may proceed to act5706. Atact5706, the processing device may set thetemp value5750 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesecond salt3158. Then, the processing device may determine whether thetemp value5750 is equal to the hash3952 (act5708). If thetemp value5750 does not equal thehash3952, then themethod5790 may terminate and fail to generate the cryptographic key5656 (act5710). If thetemp value5750 equals thehash3952, then the processing device may proceed to act5712. Atact5712, the processing device may set the cryptographic key5656 to a result of the one-way function3292 applied to a combination of thetrial password1150, thesecond salt3158 and thehash3952. Then, the processing device may decrypt the sensitive data set with thedata set name5650 using the cryptographic key5656, and themethod5790 may terminate (act5714).
• An implementer of themethod5790 uses a same one-way function3292 as he/she determined to use for themethod5690. In addition, the implementer uses a same method to combine some data elements, such as thetrial password1150 with thesecond salt3158 and thetrial password1150 with thesecond salt3158 and thehash3952, as the method he/she determined to use to combine some data elements within themethod5690. Themethod5690 is depicted inFIG. 56.
• In other embodiments, the cryptographic key5656 may be used for other purposes, including, but not limited to, re-encrypting the sensitive data set with thedata set name5650 using the cryptographic key5656 and encrypting a different data set using thecryptographic key5656.
FIG. 58
• FIG. 58 illustrates the exemplary slow cryptographickey generation method5890 that may be used to generate the cryptographic key5656 from the cryptographic key data set5550 depicted inFIG. 55. The cryptographic key5656 may then be used to decrypt the sensitive data set.
• Themethod5890 uses the slow cryptographickey data subset5560 of the cryptographickey data set5550, also depicted inFIG. 55.
• The processing device may start performing themethod5890 by obtaining thedata set name5650 and thetrial password1150 from the user, and thefirst salt3152 and thehash3952 from the central cryptographic key data subset5554 (act5800). Then, the processing device may set thesecond salt3158 equal to the first salt3152 (act5802). Then, the processing device may set acounter5850 to one (act5804). Then, the processing device may execute a loop. As its first action in the loop, the processing device may set thesecond salt3158 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the second salt3158 (act5806). Next, the processing device may truncate thesecond salt3158 to a proper length for a salt (act5808). Next, the processing device may increment the counter5850 (act5810). Next, the processing device may determine whether thecounter5850 is greater than a counter maximum5654 (act5812). If thecounter5850 is less than or equal to thecounter maximum5654, then the processing device may continue executing the loop and may return to the top of the loop,act5806. If thecounter5850 is greater than the counter maximum5654, then the processing device may stop executing the loop and may proceed to act5814. Atact5814, the processing device may set atemp value5852 to a result of the one-way function3292 applied to a combination of thetrial password1150 and thesecond salt3158. Then, the processing device may determine whether thetemp value5852 is equal to the hash3952 (act5816). If thetemp value5852 does not equal thehash3952, then themethod5890 may terminate and fail to generate the cryptographic key5656 (act5824). If thetemp value5852 equals thehash3952, then the method may proceed to act5818. Atact5818, the processing device may attempt to store a fresh copy of the remote cryptographickey data subset5552. (How the storage operation is performed depends on an operating environment in which themethod5890 is executing.) Then, the processing device may set a cryptographic key5656 to a result of the one-way function3292 applied to a combination of thetrial password1150, thesecond salt3158 and the hash3952 (act5820). Then, the processing device may decrypt the sensitive data set with thedata set name5650 using the cryptographic key5656, and themethod5890 may terminate (act5822).
• An implementer of themethod5890 uses the same one-way function3292 as he/she determined to use for themethod5690. The implementer uses the same method to combine some data elements, including thetrial password1150 with thesecond salt3158 and thetrial password1150 with thesecond salt3158 and thehash3952, as the method that was used to combine some data elements within themethod5690. In addition, the implementer uses a same value of the counter maximum5654 as the value that was used for themethod5690. Themethod5690 is depicted inFIG. 56.
• In other embodiments, the cryptographic key5656 may be used for other purposes, including, but not limited to, re-encrypting the sensitive data set with thedata set name5650 using the cryptographic key5656, and encrypting a different data set using thecryptographic key5656.
Other Cryptographic Key Data Sets
• A cryptographic key data set may include the same data elements as the passwordverification data set3150, with one exception: theRPVDS hash3156 in passwordverification data set3150 is replaced by theRCKDS hash5556 in the cryptographic key data set. The cryptographic key data set may be used to generate thecryptographic key5656. The cryptographic key5656 may then be used to encrypt or decrypt the sensitive data set.
• The following changes may be applied to theexemplary method3290, depicted inFIG. 32, to generate the cryptographic key data set and thecryptographic key5656. Inact3200, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact3216, set theRCKDS hash5556 to a result of the one-way function3292 applied to thefirst salt3152 instead of setting theRPVDS hash3156 to the result of the one-way function3292 applied to thefirst salt3152. Inact3218, store the cryptographic key data set instead of the passwordverification data set3150. Add two acts afteract3218. In the first new act, generate the cryptographic key5656 by applying the one-way function3292 to a combination of thenew password752, thesecond salt3158 and thesecond hash3160. In the second new act, encrypt the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method3390, depicted inFIG. 33, to generate thecryptographic key5656. Inact3300, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact3304, determine whether thetemp value3350 equals theRCKDS hash5556 instead of determining whether thetemp value3350 equals theRPVDS hash3156. Inact3312, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact3310, generate the cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thesecond salt3158 and thesecond hash3160 instead of successfully authenticating thetrial password1150. Afteract3310, add one act that decrypts the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method3490, depicted inFIG. 34, to generate thecryptographic key5656. Inact3400, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact3426, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact3416, store a fresh copy of the remote cryptographic key data subset of the cryptographic key data set instead of storing a fresh copy of the remote passwordverification data subset954. Inact3424, generate cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thesecond salt3158 and thesecond hash3160 instead of successfully authenticating thetrial password1150. Afteract3424, add one act that decrypts the sensitive data set with thecryptographic key5656.
• A cryptographic key data set may include the same data elements as the passwordverification data set3550, with one exception: theRPVDS hash3156 in passwordverification data set3550 is replaced by theRCKDS hash5556 in the cryptographic key data set. The cryptographic key data set may be used to generate thecryptographic key5656. The cryptographic key5656 may then be used to encrypt or decrypt the sensitive data set.
• The following changes may be applied to theexemplary method3690, depicted inFIG. 36, to generate the cryptographic key data set and thecryptographic key5656. Inact3600, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact3616, set theRCKDS hash5556 to a result of the one-way function3292 applied to thefirst hash3154 instead of setting theRPVDS hash3156 to the result of the one-way function3292 applied to thefirst hash3154. Inact3618, store the cryptographic key data set instead of the passwordverification data set3550. Add two acts afteract3618. In the first new act, generate the cryptographic key5656 by applying the one-way function3292 to a combination of thenew password752, thesalt3552 and thesecond hash3160. In the second new act, encrypt the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method3790, depicted inFIG. 37, to generate thecryptographic key5656. Inact3700, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact3704, determine whether thetemp value3750 equals theRCKDS hash5556 instead of determining whether thetemp value3750 equals theRPVDS hash3156. Inact3712, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact3710, generate the cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thesalt3552 and thesecond hash3160 instead of successfully authenticating thetrial password1150. Afteract3710, add one act that decrypts the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method3890, depicted inFIG. 38, to generate thecryptographic key5656. Inact3800, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact3820, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact3816, store a fresh copy of the remote cryptographic key data subset of the cryptographic key data set instead of storing a fresh copy of the remote passwordverification data subset954. Inact3818, generate cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thesalt3552 and thesecond hash3160 instead of successfully authenticating thetrial password1150. Afteract3818, add one act that decrypts the sensitive data set with thecryptographic key5656.
• FIGS. 55-58 show how to modify the passwordverification data set3950 and themethods4090,4190 and4290 to generate thecryptographic key5656.
• A cryptographic key data set may include the same data elements as the passwordverification data set4350, with one exception: theRPVDS hash3156 in passwordverification data set4350 is replaced by theRCKDS hash5556 in the cryptographic key data set. The cryptographic key data set may be used to generate thecryptographic key5656. The cryptographic key5656 may then be used to encrypt or decrypt the sensitive data set.
• The following changes may be applied to theexemplary method4490, depicted inFIG. 44, to generate the cryptographic key data set and thecryptographic key5656. Inact4400, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact4420, set theRCKDS hash5556 to a result of the one-way function3292 applied to thesecond salt3158 instead of setting theRPVDS hash3156 to the result of the one-way function3292 applied to thesecond salt3158. Inact4422, store the cryptographic key data set instead of the passwordverification data set4350. Add two acts afteract4422. In the first new act, generate the cryptographic key5656 by applying the one-way function3292 to a combination of thenew password752, thehash3952 and thesecond salt3158. In the second new act, encrypt the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method4590, depicted inFIG. 45, to generate thecryptographic key5656. Inact4500, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact4504, determine whether thetemp value4550 equals theRCKDS hash5556 instead of determining whether thetemp value4550 equals theRPVDS hash3156. Inact4512, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact4510, generate the cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thehash3952 and thesecond salt3158 instead of successfully authenticating thetrial password1150. Afteract4510, add one act that decrypts the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method4690, depicted inFIG. 46, to generate thecryptographic key5656. Inact4600, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact4614, store a fresh copy of the remote cryptographic key data subset of the cryptographic key data set instead of storing a fresh copy of the remote passwordverification data subset954. Inact4616, generate cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thehash3952 and thesecond salt3158 instead of successfully authenticating thetrial password1150. Afteract4616, add one act that decrypts the sensitive data set with thecryptographic key5656.
• A cryptographic key data set may include the same data elements as the passwordverification data set4750, with one exception: theRPVDS hash3156 in passwordverification data set4750 is replaced by theRCKDS hash5556 in the cryptographic key data set. The cryptographic key data set may be used to generate thecryptographic key5656. The cryptographic key5656 may then be used to encrypt or decrypt the sensitive data set.
• The following changes may be applied to theexemplary method4890, depicted inFIG. 48, to generate the cryptographic key data set and thecryptographic key5656. Inact4800, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact4812, set theRCKDS hash5556 to a result of the one-way function3292 applied to a combination of thesalt3552 and thesalt salt4752 instead of setting theRPVDS hash3156 to the result of the one-way function3292 applied to the combination of thesalt3552 and thesalt salt4752. Inact4814, store the cryptographic key data set instead of the passwordverification data set4750. Add two acts afteract4814. In the first new act, generate the cryptographic key5656 by applying the one-way function3292 to a combination of thenew password752, thehash3952 and thesalt3552. In the second new act, encrypt the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method4990, depicted inFIG. 49, to generate thecryptographic key5656. Inact4900, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact4904, determine whether thetemp value4950 equals theRCKDS hash5556 instead of determining whether thetemp value4950 equals theRPVDS hash3156. Inact4912, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact4910, generate the cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thehash3952 and thesalt3552 instead of successfully authenticating thetrial password1150. Afteract4910, add one act that decrypts the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method5090, depicted inFIG. 50, to generate thecryptographic key5656. Inact5000, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact5018, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact5014, store a fresh copy of the remote cryptographic key data subset of the cryptographic key data set instead of storing a fresh copy of the remote passwordverification data subset954. Inact5016, generate cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, thehash3952 and thesalt3552 instead of successfully authenticating thetrial password1150. Afteract5016, add one act that decrypts the sensitive data set with thecryptographic key5656.
• A cryptographic key data set may include the same data elements as the passwordverification data set5150, and may be used to generate thecryptographic key5656. The cryptographic key5656 may then be used to encrypt or decrypt the sensitive data set.
• The following changes may be applied to theexemplary method5290, depicted inFIG. 52, to generate the cryptographic key data set and thecryptographic key5656. Inact5200, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact5210, store the cryptographic key data set instead of the passwordverification data set5150. Add two acts afteract5210. In the first new act, generate the cryptographic key5656 by applying the one-way function3292 to a combination of thenew password752, theconstant term5164, and thesolution5151. In the second new act, encrypt the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method5390, depicted inFIG. 53, to generate thecryptographic key5656. Inact5300, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact5310, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. In act5312, generate the cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, theconstant term5164, and thesolution5151 instead of successfully authenticating thetrial password1150. After act5312, add one act that decrypts the sensitive data set with thecryptographic key5656.
• The following changes may be applied to theexemplary method5490, depicted inFIG. 54, to generate thecryptographic key5656. Inact5400, obtain thedata set name5650 and thetrial password1150 instead of obtaining theuser name750 and thetrial password1150. Inact5418, fail to generate the cryptographic key5656 instead of failing to authenticate thetrial password1150. Inact5410, store a fresh copy of the remote cryptographic key data subset of the cryptographic key data set instead of storing a fresh copy of the remote passwordverification data subset954. Inact5412, generate cryptographic key5656 by applying the one-way function3292 to the combination of thetrial password1150, theconstant term5164, and thesolution5151 instead of successfully authenticating thetrial password1150. Afteract5412, add one act that decrypts the sensitive data set with thecryptographic key5656.
• In each of the embodiments described in this section, an implementer may generate the cryptographic key5656 based on a different combination of data elements than the combination of data elements specified herein. To make the cryptographic key data set more secure against attacks, the different combination may include at least one data element from the central cryptographickey data subset5554 and at least one data element from the remote cryptographickey data subset5552 that can be regenerated from the central cryptographickey data subset5554 and thetrial password1150. The implementer may avoid using data elements from the remote cryptographickey data subset5552 that cannot be regenerated from the central cryptographickey data subset5554 and thetrial password1150.
Brute Force and Dictionary Attacks
• Attackers who seek to crack passwords are often criminals. However, there are legitimate reasons to crack passwords including, but not limited to, the following:
• an individual may want to recover his/her own forgotten password;
• an organization may want to recover a password of a former employee to regain access to data stored in the former employee's account; or
• law enforcement personnel may want to access an account and/or read an encrypted data set of a criminal suspect.
• For most of the exemplary password verification data sets presented previously, methods for performing dictionary and brute force attacks are straightforward. However, the passwordverification data set4350, depicted inFIG. 43, presents a greater challenge to an attacker because of a role that random numbers play in generating the passwordverification data set4350.
FIG. 59
• FIG. 59 illustrates anexemplary method5990 that may be used by a processing device to perform a dictionary or brute force attack seeking to recover a password from the passwordverification data set4350, depicted inFIG. 43. Themethod5990 is performed in the exemplaryattack operating environment500 depicted inFIG. 5.
• In the dictionary or brute force attack, the processing device attempts to authenticate a series of trial passwords. In the dictionary attack, the processing device tries to authenticatetrial passwords1150 from a list of likely passwords. In the brute force attack, the processing device tries to authenticate allpossible trial passwords1150 meeting some criteria, such as, for example, thetrial password1150 being shorter than nine characters. Both dictionary attacks and brute force attacks may use a trialpassword iteration function5992 that may generate adifferent trial password1150 each time the function is called. For dictionary attacks, the trialpassword iteration function5992 may look up and return anext trial password1150 from the list of likely passwords. For a brute force attack, the trialpassword iteration function5992 may return anext trial password1150 that meets the criteria for trial passwords. The trialpassword iteration function5992 may also return a code indicating that all trial passwords have already been returned.
• Before performing the dictionary attack or the brute force attack, the attacker obtains the central passwordverification data subset956 of the passwordverification data set4350 for a password that he/she is trying to recover. The attacker also learns how the passwordverification data set4350 was generated (by themethod4490, depicted inFIG. 44), and all the determinations that the implementer of themethod4490 made when he/she implemented themethod4490.
• To perform themethod5990, the processing device may start by obtaining thefirst salt3152 and thehash3952 from the central password verification data subset956 (act5900). Then, the processing device may set thesecond salt3158 equal to the first salt3152 (act5902). Then, the processing device may execute an outer loop. As its first action in the outer loop, the processing device may determine whether apassword iteration function5992 can generate another trial password1150 (act5904). If thepassword iteration function5992 cannot generate anothertrial password1150, then the processing device may stop executing the outer loop, themethod5990 may terminate, and the attack may fail to recover the password (act5906). If thepassword iteration function5992 is able to generate anothertrial password1150, then the processing device may continue executing the outer loop and may proceed to act5908. Atact5908, the processing device may obtain thenext trial password1150 from thepassword iteration function5992. Then, the processing device may set acounter5950 to zero (act5910). Then, the processing device may execute an inner loop. As its first action in the inner loop, the processing device may set atrial hash5952 to a result of the one-way function3292 applied to a combination of thetrial password1150 and the second salt3158 (act5912). Then, the processing device may determine whether thetrial hash5952 equals the hash3952 (act5914). If thetrial hash5952 equals thehash3952, then the processing device may stop executing both the inner and the outer loops and themethod5990 may terminate successfully with thetrial password1150 as a recovered password (act5916). If thetrial hash5952 does not equal thehash3952, then the processing device may proceed to act5918. Atact5918, the processing device may increment thecounter5950. Then, the processing device may determine whether thecounter5950 is less than a counter maximum5954 (act5920). If thecounter5950 is not less than the counter maximum5954, then the processing device may stop executing the inner loop and may return toact5904. If thecounter5950 is less than the counter maximum5954, then the processing device may proceed to act5922. Atact5922, the processing device may set thesecond salt3158 equal to thetrial hash5952. Then, the processing device may truncate thesecond salt3158 to a proper length for a salt (act5924). Then, the processing device may set thesecond salt3158 to a result of theperturb function4492 applied to the second salt3158 (act5926). Then, the processing device may continue executing the inner loop and may return toact5912.
• Before implementing themethod5990, an implementer may determine a value of thecounter maximum5954. Choosing a larger value of the counter maximum5954, as opposed to choosing a smaller value of the counter maximum5954, may have the following effects:
• • the inner loop of themethod5990 may take longer to execute; and
  • the inner loop may be more likely to recognize acorrect trial password1150, although there is no value of the counter maximum5954 that guarantees that thecorrect trial password1150 will be recognized.
• In theattack operating environment500, multiple processing devices may cooperate to perform themethod5990. In some embodiments, some processing devices from the array ofprocessing devices502 may each perform the inner loop of themethod5990 simultaneously, with each of the some processing devices testing adifferent trial password1150. Each of the some processing devices may report the results of its inner loop to another processing device in thearray502 that performs the outer loop of themethod5990.
• If the passwordverification data set4350 is used to generate the cryptographic key5656, then themethod5990, with slight modifications, may be able to recover a password that enables a slow cryptographic key generation method to generate thecryptographic key5656.
CONCLUSION
• Embodiments consistent with the subject matter of this disclosure generate password verification data sets based, at least in part, on a password. In some embodiments, password authentication may be performed based on a subset of the password verification data set and a provided trial password. In other embodiments consistent with the subject matter of this disclosure, a cryptographic key may be generated based, at least partly, on a provided password, and the cryptographic key may be regenerated based on a provided trial password, when the trial password is identical to the password.
• Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms for implementing the claims.
• Accordingly, the appended claims and their legal equivalents define embodiments, rather than any specific examples given.

Claims (16)

I claim as my invention:

1. A processing device implemented method for generating and storing a data set for a password, and for either authenticating a trial password, or for attempting to generate a cryptographic key, the method comprising:

performing a first method; and

performing either a second method or a third method, wherein:

the first method comprises:

generating the data set, based at least partly, on the password, the data set including at least two distinct subsets, each of the two distinct subsets being sufficient either to perform a password authentication process or to generate a cryptographic key, storing a plurality of data elements of the data set on a first storage device, at least one of the plurality of data elements stored on the first storage device is included in a first subset of the data set, and

storing at least one other data element of the data set on a second storage device, at least one of the at least one other data element is included in the first subset of the data set;

the second method comprises:

either

authenticating the trial password, based on the first subset, when the first subset is available,

or

attempting to generate the cryptographic key, based, at least partly, on the first subset and the trial password, when the first subset is available; and

the third method comprises:

either

authenticating the trial password, based on a second subset of the data set, when the second subset is available,

or

attempting to generate the cryptographic key, based, at least partly, on a second subset of the cryptographic key data set and the trial password, when the second subset is available;

wherein:

each of the first method, the second method and the third method are performed by at least one respective processing device,

the first subset is different from the second subset,

the second method is different from the third method, and

the second method is at least twice as fast as the third method.

2. The processing device implemented method ofclaim 1, wherein:

the second storage device is not permanently connected to any of the at least one processing device that performs the second method.

3. The processing device implemented method ofclaim 1, wherein the second storage device is a removable storage device.

4. The processing device implemented method ofclaim 1, wherein:

the first method further comprises:

applying a one-way function to a combination, based on one or more of the at least one other data element that belongs to the first subset of the data set, to produce a first hash which is included in the data set, and

storing the first hash on the first storage device;

the second method further comprises:

providing the first hash and the one or more of the at least one other data element to one or more processing devices of the at least one processing device that performs the second method,

applying the one-way function to the combination to produce a second hash, and

either failing to authenticate the trial password, or failing to generate the cryptographic key, when the first hash is different from the second hash.

5. The processing device implemented method ofclaim 2, wherein:

the data set comprises a first salt, a second salt, a first hash and a second hash,

the first subset comprises the first hash and the first salt,

the second subset comprises the second hash and the second salt,

the first hash, the second hash and the second salt are stored on the first storage device,

the first salt is stored on the second storage device, and

the processing device implemented method further comprises:

obtaining, by the any of the at least one processing device that performs the second method, the first salt, if available;

obtaining the trial password by the any of the at least one processing device that performs the second method or any of the at least one processing device that performs the third method;

when the first salt is available, obtaining the first hash and performing the second method; and

when the first salt is unavailable, obtaining the second hash and the second salt and performing the third method.

6. The processing device implemented method ofclaim 2, wherein:

the data set comprises a salt, a first hash and a second hash,

the first subset comprises the salt and the first hash,

the second subset comprises the salt and the second hash,

the salt and the second hash are stored on the first storage device,

the first hash is stored on the second storage device, and

the processing device implemented method further comprises:

obtaining, by the any of the at least one processing device that performs the second method, the first hash, if available;

obtaining the trial password by the any of the at least one processing device that performs the second method or any of the at least one processing device that performs the third method;

when the first hash is available, obtaining the salt and performing the second method; and

when the first hash is unavailable, obtaining the salt and the second hash and performing the third method.

7. The processing device implemented method ofclaim 2, wherein:

the data set comprises a first salt, a second salt and a hash,

the first subset comprises the second salt and the hash,

the second subset comprises the first salt and the hash,

the first salt and the hash are stored on the first storage device,

the second salt is stored on the second storage device, and

the processing device implemented method further comprises:

obtaining, by the any of the at least one processing device that performs the second method, the second salt, if available;

obtaining the trial password by the any of the at least one processing device that performs the second method or any of the at least one processing device that performs the third method;

when the second salt is available, obtaining the hash and performing the second method; and

when the second salt is unavailable, obtaining the second salt and the hash and performing the third method.

8. The processing device implemented method ofclaim 2, wherein:

the data set comprises a complete salt, a partial salt and a hash,

the partial salt includes only some of the bits that represent a value of the complete salt,

the first subset comprises the complete salt and the hash,

the second subset comprises the partial salt and the hash,

the partial salt and the hash are stored on the first storage device,

the complete salt is stored on the second storage device, and

the processing device implemented method further comprises:

obtaining, by the any of the at least one processing device that performs the second method, the complete salt, if available;

obtaining the trial password by the any of the at least one processing device that performs the second method or any of the at least one processing device that performs the third method;

when the complete salt is available, obtaining the hash and performing the second method; and

when the complete salt is unavailable, obtaining the partial salt and the hash and performing the third method.

9. The processing device implemented method ofclaim 7, further comprising:

generating the second salt by an iterative process; and

terminating the iterative process based, at least partly, on at least one randomly generated number.

10. The processing device implemented method ofclaim 2, wherein:

the data set comprises a first set of coefficients of a polynomial equation and a numerical solution to the polynomial equation,

a second set of coefficients of the polynomial equation are derivable from the password,

the first set of coefficients and the second set of coefficients are disjoint and the union of the two sets contains all coefficients of the polynomial equation,

the first subset comprises the first set of coefficients and the numerical solution,

the second subset comprises the first set of coefficients,

the first set of coefficients of the polynomial equation are stored on the first storage device,

the numerical solution to the polynomial equation is stored on the second storage device, and

the processing device implemented method further comprises:

obtaining, by the any of the at least one processing device that performs the second method, the numerical solution, if available;

obtaining the trial password by the any of the at least one processing device that performs the second method or any of the at least one processing device that performs the third method;

deriving the second set of coefficients from the trial password by the any of the at least one processing device that performs either the second method or the third method;

obtaining the first set of coefficients by the any of the at least one processing device that performs either the second method or the third method;

when the numerical solution is available, performing the second method; and

when the numerical solution is unavailable, performing the third method.

11. The processing device implemented method ofclaim 2, further comprising:

generating the cryptographic key from a combination including at least one data element of the plurality of data elements of the data set stored on the first storage device and one or more data elements of the at least one other data element of the data set stored on the second storage device.

12. The processing device implemented method ofclaim 11 wherein the combination further includes the trial password.

13. A processing device implemented method for either authenticating a password or generating a cryptographic key, the method comprising:

obtaining a trial password;

obtaining a subset of a data set wherein at least one data element of the data set was generated by a first iterative process, termination of the first iterative process being based, at least partly, on at least one randomly generated number; and

performing a calculation, based, at least partly, on the trial password, the calculation comprising a second iterative process that, during each iteration, performs calculations which are mathematically equivalent to calculations performed by the first iterative process, during a respective iteration of the first iterative process; wherein:

either

the second iterative process terminates successfully, indicating successful authentication of the password or successful generation of the cryptographic key, if at least one data element, that the second iterative process generates during an iteration, matches the at least one data element of the data set that was generated by the first iterative process;

or

the second iterative process terminates without success, indicating either unsuccessful authentication of the password or a failure to generate the cryptographic key, based on a calculation that includes at least one item from a group of items consisting of a number of iterations already performed, a time elapsed from a start of the second iterative process, and at least one random number, and

the method is performed by at least one processing device.

14. At least one processing device, each of the at least one processing device comprising:

at least one processor; and

at least one memory connected to one or more respective processors of the at least one processor, the at least one memory having instructions stored therein for the one or more respective processors of the at least one processor to perform a method for generating and storing a data set for a password, and either the data set is for authenticating a trial password or the data set is for generating a cryptographic key, the method comprising:

performing a first method; and

performing either a second method or a third method; wherein:

the first method comprises:

generating the data set, based at least partly, on the password, the data set including at least two distinct subsets that are each sufficient to perform either a password authentication process or a cryptographic key generation process;

storing a plurality of data elements of the data set on a first storage device, at least one of the plurality of data elements stored on the first storage device is included in a first subset of the data set; and

storing at least one other data element of the data set on a second storage device, at least one of the at least one other data element is included in the first subset of the data set;

the second method comprises:

either authenticating the trial password, or generating the cryptographic key, based on the first subset, when the first subset is available; and

the third method comprises:

either authenticating the trial password, or generating the cryptographic key, based on a second subset of the data set, when the second subset is available; wherein:

the first subset is different from the second subset,

the second method is different from the third method, and

the second method is at least twice as fast as the third method.

15. The at least one processing device ofclaim 14, wherein

the second storage device is not permanently connected to the at least one processing device.

16. The at least one processing device ofclaim 14, wherein

the second storage device is a removable storage device.

Images