System and method for increasing the security of encrypted secrets and authentication

In general, in one aspect, the invention relates to a method for accessing encrypted data by a client. The method includes receiving from the client by a server client information derived from a first secret wherein the client information is derived such that the server can not feasibly determine the first secret. The method also includes providing to the client by the server intermediate data, which is derived responsive to the received client information, a server secret, and possibly other information. The intermediate data is derived such that the client cannot feasibly determine the server secret. The method also includes authenticating the client by a device that stores encrypted secrets and is configured not to provide the encrypted secrets without authentication. After the authenticating step, the method also includes providing the encrypted secrets to the client. The encrypted secrets 5 are capable of being decrypted using a third secret that is derived from the intermediate data.

TECHNICAL FIELD

This invention relates generally to the field of cryptographic protocols and, more particularly, to a system and method for increasing the security of secrets used to decrypt encrypted secrets and secrets used to authenticate users to a server.

BACKGROUND

FIG. 1shows a prior art system100in which a user3stores secrets5on a remote server computer10, where the term secrets is used broadly to mean any data or information that the owner wishes to keep private. The user3accesses the secrets5using a client computer15that is connected to the server computer10via a data or telecommunications network20, such as the Internet. Storage of the secrets5on the server10allows the user3to access the secrets5from any client computer connected to the network20.

To help prevent the secrets5from being obtained by others, the secrets5are typically encrypted. Encrypting the secrets5, for example, by use of a key24, prevents someone who has access to the secrets5from learning the secrets5, for example, by compromise of the server or by observing the user's communications with the server10over the network20. The encryption of the secrets5can be performed according to various known techniques including symmetric encryption in which the same decryption key24is used for both encryption and decryption, and/or asymmetric encryption, in which different keys are used for encryption and decryption respectively.

As the number of possible values from which a key24might be chosen (the “key space”) is increased by changing the encryption implementation, it becomes increasingly more difficult for an attacker to try every possible decryption key24. At some point, the number of possible of keys is so great that an encrypted secret5cannot feasibly be decrypted by trying each possible key24. This is referred to as a strong encryption, because the large key space makes the encryption stronger. For example, a key that is chosen from the set of all known English words is much weaker than a key that is chosen from the set of all 1024-bit numbers. An encryption and/or decryption key24that is selected from a large key space is typically cumbersome for a user3to employ, however, because long sequences of characters are difficult for humans to remember. Users3may be inclined to write down such sequences, thereby making the key available to an attacker. To ease the memory burden on users3, shorter decryption keys24are frequently used, with the disadvantage that it may be feasible for a party that has access to the encrypted secrets5to decrypt the encrypted secrets5by trying every possible key.

SUMMARY

There exists a need, therefore, for a convenient and secure means for a user to access data that has been encrypted using strong secrets, and also to authenticate to servers using strong secrets.

In general, in one aspect, the invention relates to a method for accessing encrypted data by a client. The method includes receiving from the client by a server client information derived from a first secret wherein the client information is derived such that the server can not feasibly determine the first secret. The method also includes providing to the client by the server intermediate data that is derived responsive to the received client information, a server secret, and possibly other information. The intermediate data is derived such that the client cannot feasibly determine the server secret. The method also includes authenticating the client by a device that stores encrypted secrets and is configured not to provide the encrypted secrets without authentication. The method also includes, after the authenticating step, the step of providing the encrypted secrets to the client. The encrypted secrets are capable of being decrypted using a third secret that is derived from the intermediate data.

In one embodiment, the third secret is derived from the intermediate data by use of a key derivation function. In one embodiment, the third secret is the intermediate data. In one embodiment, the first secret includes one or more of a PIN, a password, and biometric information.

In another embodiment, the intermediate data is derived from at least the first secret and the server secret by the use of a blind function evaluation protocol. In one variation of this embodiment, the blind function evaluation protocol involves the use of the RSA cryptosystem. In another variation of this embodiment, the security of the blind function evaluation protocol is based on the principles of discrete logarithms. In another embodiment, the blind function evaluation protocol involves the use of a one-way function that is calculated using a multiparty secure computation technique.

In various embodiments, the authenticating step can include authenticating the client based on one or more of a PIN, a password, a token code, a time-dependent code, and biometric information, alone or in combination. In one embodiment, the authenticating step includes authenticating the client based on a secret other than the first secret. In another embodiment, the authenticating step includes using a secret derived from the intermediate data.

In another embodiment, the device includes at least one of a file server, a directory server, a key server, a PDA, a mobile telephone, a smart card, and a desktop computer. In one such embodiment, the device includes at least one secure data store, which requires authentication before allowing the client access to the data store.

In another embodiment, the encrypted secrets include a private key of a public/private key pair used for asymmetric cryptography. In one such embodiment, the private key is a signature key used for creating a digital signature. In one such embodiment, the authenticating step involves authenticating the client based on a secret other than the first secret, so that the user provides different information to access the device and to access the signature key. In such an embodiment, the user authenticates to a computer using one authentication mechanism, and uses a password different than the authentication mechanism to digitally sign a document. The password is used in a blind function evaluation protocol, the result of which is used to decrypt the signature key. This procedure can be used to satisfy digital signature requirements that a different password be used to digitally sign a document.

In still another embodiment, the encrypted secrets include a secret key used for symmetric cryptography. In another additional embodiment, the encrypted secrets include at least one unit of digital currency. In one such embodiment, the encrypted secrets function as an electronic wallet, containing digital currency and/or other information, such as keys and identification numbers. In still another embodiment, the encrypted secrets include one or more usernames and passwords that can be used to authenticate to one or more other servers. In this way the user can remotely access the collection of access codes, and use them to access other servers.

In another embodiment, the method also includes the step of verifying that the client has not exceeded a predetermined number of unsuccessful attempts to obtain the intermediate data. In one variation of this embodiment, the verifying step also includes the steps of transmitting a challenge code to the client and receiving the result of a cryptographic operation using the challenge code as an input and using a cryptographic key derived from at least one of the encrypted secrets. In another embodiment, the verification comprises showing knowledge of some item of information contained in the encrypted secrets.

In general, in another aspect, the invention relates to a system for accessing encrypted data by a client. The system includes a first server. The first server includes a first server receiver for receiving from a client client information derived from a first secret. The client information is derived such that the first server can not feasibly determine the first secret. The system includes a server secret. The system includes a first server output for providing to the client by the server intermediate data. The intermediate data is derived from at least the received client information and a server secret. The intermediate data is derived such that the client can not feasibly determine the server secret. The system also includes a second device. The second device includes a data store storing an encrypted secret. The encrypted secret is capable of being decrypted using a third secret that is derived from the intermediate data. The device includes an authentication subsystem for authenticating the client by the device. The device includes a device output for providing to the client by the device the encrypted secrets upon authentication.

In one embodiment, the third secret is derived from the intermediate data by use of a key derivation function. In another embodiment, the intermediate data is derived from at least the first secret and the server secret by use of a blind function evaluation protocol. In another embodiment, the intermediate data is derived from at least the first secret and the server secret and the security of the blind function evaluation protocol is based on the principles of the RSA cryptosystem, the problem of extracting roots modulo a composite. In another embodiment, the intermediate data is derived from at least the first secret and the server secret and the security of the blind function evaluation protocol is based on the principles of discrete logarithms.

In one embodiment, the authentication subsystem authenticates the client based on a secret other than the first secret. In one embodiment, the authentication subsystem authenticates the client using a secret derived from the intermediate data. In one embodiment, the second device comprises at least one of a file server, a directory server, a key server, a PDA, a mobile telephone, a smart card, and a desktop computer. In one embodiment, the encrypted secret is one of a private key of a public/private key pair used for asymmetric cryptography, a signature key used for creating a digital signature, a secret key used for symmetric cryptography, and at least one unit of digital currency. In one embodiment, the first server also includes a verifier for verifying that the client has not exceeded a predetermined number of unsuccessful attempts to obtain the intermediate data.

In general, in another aspect, the invention relates to a method for generating a password for a user to use for authenticating to a server. The method includes specifying a server secret, and receiving from a client a server identifier and client information derived from a first secret wherein the client information is derived such that the first server can not feasibly determine the first secret. The method includes generating a password derived from at least the server identifier, the client information, and the server secret wherein the password is derived such that the client can not feasibly determine the server secret from knowledge of the first secret, the web server identifier, and the generated password.

In one embodiment, the method also includes transmitting the generated password to the client. In another embodiment, the method also includes transmitting an attempt identifier to the client with the generated password. In another embodiment, the method also includes receiving from the server verification that the user has authenticated successfully to the server.

In general, in another aspect, the invention relates to a password for a user to use for accessing a web server. The system includes a server secret and a receiver for receiving from a client a web server identifier and client information derived from a first secret wherein the client information is derived such that the first server can not feasibly determine the first secret. The system also includes a password generator for generating a password derived from at least the web server identifier, the client information, and the server secret wherein the password is derived such that the client can not feasibly determine the server secret from knowledge of the first secret, the web server identifier, and the generated password.

DETAILED DESCRIPTION

Referring toFIG. 2, an embodiment of a system200according to the invention allows a user3to conveniently and securely gain access to encrypted secrets5, where the term secrets is used broadly to mean any data or information that the owner wishes to keep private. Here, for convenience, the encrypted secrets5are referred to in the plural, although there may be one or more secrets. The one or more secrets may include any data or information, as examples without limitation, such secrets as a private key8of a public/private key pair as used in asymmetric cryptography and/or for providing a digital signature, a secret key used for symmetric cryptography, one or more units of digital currency, or some combination. In this embodiment of the invention, the security of the encrypted secrets5is increased by storing the encrypted secrets5in one device that requires authentication for access to the secrets (the second device10′) and storing information used in the decryption process in another device (the first server30).

The system200includes a client15that may interact with a user3. The client can be implemented as any sort of device or machine capable of communicating with the second device10′ and the first server30. As examples of implementations of clients15not intended to be limiting, the client15may be one or more of a personal computer, a mobile telephone, a personal digital assistant (PDA), a network appliance, a smart card, a network terminal, and a workstation.

The client15is in communication with a first server30and a second device10′ over communications links, which may be the same, or different communications links for each of the first server30and the second device10′. For example, the client15may be a PDA that communicates via a wireless and wired internet protocol network with the first server30, and via a direct serial connection to the second device10′. As another example, the client15may be a personal computer in an airport that communicates with both the first server30and the second device10′ over a wired internet protocol network such as the Internet. Again, these examples of types of communications links are not intended to be limiting, and the invention may be used with any suitable wireless or wired communication links.

In an embodiment of the invention, a user3provides a first secret35to the client15. The first secret35can be something that is measured or something that the user enters, for example through a user interface17. Typically, the first secret35might be (as examples not intended to be limiting) one or more of a short numerical code such as a PIN, an alphanumeric code such as a password, a token code, a time-based code such as that provided by a RSA SECURID security token manufactured by RSA Security Inc. of Bedford, Mass., biometric information, and data derived from one or more of these.

The client derives client information38from the first secret35that is used to harden (i.e., strengthen) the first secret35. The derivation might be that the client15uses the first secret35directly as the client information38. The derivation might be that the client uses the first secret35as part of a blind function evaluation protocol to generate the client information38. The derivation can include use of one or more of a key derivation function, mask generation function, or another cryptographic function to derive the client information38from the first secret35. As described further below, the derivation may be for using the first secret35as part of a blind function evaluation protocol.

The first server30receives the client information38from the client. Preferably, the client information38is such that the first server30can not feasibly determine the first secret from the client information38, with feasibly being used here to mean not without an extraordinary amount of time and/or computational effort. In response to the client information38, the first server30provides the client15with intermediate data22, which is used by the client15(directly or indirectly) to decrypt the encrypted secrets5.

The first server30may derive the intermediate data22from a combination of information38that the client15provides to the first server30and a server secret, that is stored on or available to the first server30. The intermediate data22is preferably derived such that the client can not feasibly determine the server secret, meaning that an attacker posing as the client15, or observing the client's interactions with the first server30can not determine the server secret without an extraordinary amount of time and/or computational effort.

The first server30preferably is a server-class computer that is in communication with a network20, and that is capable of responding to many requests from clients15throughout the network20. In other embodiments, the first server30may be any type of computer or device. The first server may be, as examples not intended to be limiting, a personal computer, a mobile telephone, a personal digital assistant (PDA), a network appliance, a smart card, a network terminal, or a workstation.

The client15and the first server30interact such that the client15is provided with intermediate data22that the client15can use as part of the process to decrypt the encrypted secrets5. The client15may use the intermediate data22directly as a decryption key, for example, if the decryption key is communicated over a secure channel. Alternatively, the client15may derive (possibly in combination with other information) from the intermediate data22some portion or all of one or more decryption keys that are used to decrypt the encrypted secrets5. The client15and the first server30may participate in a blind function evaluation protocol, in which the client15has some secret information and the first server30has some secret information, and together the client15and the first server30provide their respective secrets as an input to a jointly calculated function, without either the client15or the first server30revealing their secrets to the other and with only the client15obtaining the output of the jointly calculated function. The specifics of the particular blind function evaluation protocol, what the first server30does with the client information38, and what the client15does with the intermediate data22, will vary depending upon the evaluated function and the blinded protocol selected.

The interaction between the client15and the first server30might include only a single data exchange or they might participate in more complicated protocols in which multiple data exchanges take place. For example, in a simple blind function evaluation protocol, there might be a single communication of client information38to the first server30, and a single response of the first server30back to the client15in which the intermediate data22is communicated. In more complex blind function evaluation protocols, portions of client information38are sent at different times to the first server30, and portions of intermediate data22are communicated to the client15at different times.

The use of a blind function evaluation protocol, or other embodiments in which the decryption key is derived from the client information, provides additional security benefits resulting from the fact that the first server30does not have the decryption key in an unblinded form. Even if the first server30is compromised, and a server secret obtained, it will still be necessary for an attacker to do more work to transform the server secret into the decryption key. Just as one example, in one such embodiment, the first server30and client15engage in a blind function evaluation protocol that results in the first server30providing to the client15a blinded key as the intermediate data22. The client15has information used to unblind the decryption key24, which is then used to decrypt the encrypted secrets5. Compromise of the first server30would still not directly reveal the decryption key25to an attacker.

In one embodiment, a verification is used to prevent attempts to gain access to the intermediate data22by repeated guessing of the first secret35or client information38. Without such a verification, an attacker that compromises the second device10′ and has access to the encrypted secrets5could determine the corresponding intermediate data22by sending the various possible values of the client information38to the first server30. By limiting the number of unsuccessful attempts allowed, the first server30prevents such an attack. For example, the verification can be made by demonstrating successful decryption of the encrypted secrets5. If the encrypted secrets5include an encryption key, the encryption key can be used to encrypt a challenge value provided by the first server30. If the encrypted secrets5include personal information of the user, such information can be provided to the first server30.

In one embodiment, biometric information is used for the first secret35, through the use of “fuzzy commitment” techniques such as those described in PCT Patent Application Serial No. PCT/US00/03522 entitled “A Fuzzy Commitment Scheme.” The transformation from initial biometric information to first secret35is accomplished with the use of codes that are akin to error correcting codes. Generally, the resulting first secret35has at least PIN-level security due to the limited amount of uncertainty available in typical biometrics and the accommodation for measurement errors. In one embodiment, code information used to correct differences in biometric information is stored on a code server (not shown) connected to the network20. The client15combines the code information with biometric data to generate the first secret35. In other embodiments, the code information is stored on the client15, the first server30, the second device10′, or some combination.

The second device10′ stores encrypted secrets5for the user3. The second device10′ can be implemented as any sort of device or machine capable of storing encrypted secrets and communicating the secrets upon authentication. As examples of implementations of devices10′ not intended to be limiting, the second device10′ can be one or more of a file server, a directory server, a key server, a personal computer, a mobile telephone, a personal digital assistant (PDA), a network appliance, a smart card, a network terminal, and a workstation. In one embodiment, the second device10′ is implemented in the client15in a cryptographically secure section of memory or on a dedicated cryptographically secure chip. The encrypted secrets5are stored in the second device10′ such that a client15authenticates to the second device10′ prior to the second device10′ providing the encrypted secrets5to the client15. The second device10′ may be an already-existing file server or other authenticated data store. The system and method of the invention can be used to provide additional security to secrets stored on such a data store.

In one embodiment, the second device10′ does not provide encrypted secrets5to the client15until the client15has authenticated to the second device10′. The authentication step can be based on information derived from the intermediate data22or the authentication can be based on independent authentication information, such as a PIN, a password, a token code, a time-based code, biometric information, or some combination. The second device10′ can be an already-existing, or standard, authenticating data store, for example, a directory server such as a file server accessed by MICROSOFT WINDOWS NT available from Microsoft Corporation of Redmond, Wash., clients, or a file system accessed by NIS clients, such as those available from Sun Microsystems of Mountain View, Calif. The second device10′ can also be a local device (implemented in hardware or software) on the user's3personal computer, or a portable memory device in communication with the client15by PCMCIA or serial connection. Because the encrypted secrets5can be stored in a conventional manner, the system of the current invention can be integrated with existing systems that provide authenticated access to encrypted secrets5to increase the security of the encryption.

In one example embodiment that enables digital signing of documents, a user has one mechanism for authenticating to a computer, and another for signing a document. In this embodiment, a computer stores an encrypted signature key and the user authenticates to that computer to obtain the encrypted signature key. When the user wishes to use the encrypted signature key to sign a document, the user provides a client (which may be the computer) with a password. The client engages in a blind function evaluation protocol with a first server. The result of the blind function evaluation protocol (or a key derived from the result) is used to decrypt the signature key, and the signature key is then used to digitally sign a document. In this way, a second mechanism, involving an independent server, is used to enable the digital signature of a document. Compromise of the computer does not enable an attacker to make use of the signature key.

Referring toFIG. 3, in one embodiment, a client15communicates with a first server30and a second device10″ as inFIG. 2. In this illustrative embodiment, the second device10″ is a second server that is accessed over a communications network such as the Internet. In this illustrative embodiment, the communication between the client15and the first server30takes place over a computer network20such as the Internet, and the communication between the client15and the second server10″ takes place over a computer network such as the Internet. Prior to the user3attempting to access the encrypted secrets5, the system300is initialized33for use by the user3. This initialization may include operations performed on both the client15and first server30and some initial exchange of data.

To access the encrypted secrets5, the user3first uses the client15and the first server30to convert a first secret35into a decryption key25, which preferably is a stronger key than the first secret35. In this example, the first secret35is a password, that is a sequence of symbols that can be conveniently remembered by the user3. As described above, in other embodiments, the first secret35might also be something else, or a combination of a password and something else.

In this embodiment, the client15participates in a blind function evaluation protocol40with the first server30. The blind function evaluation protocol40takes as input client information in the form of the client's secret input45, which may be the first secret35or information derived by the client15from the first secret35, and a server secret50to produce a hardened (i.e. stronger) secret25than the first secret35. The hardened secret is stronger at least partially because it is chosen from a much larger key space and so it is more difficult to guess. The blind function evaluation protocol is designed in such a way that the first secret35and the hardened secret25result are known to the client15but not the first server, and the first server secret50is known only to the first server30, yet both the client15and the server30participate in the protocol.

A blind function evaluation protocol40can be represented mathematically by the expression R=g(w, b) where, R is the result25of the blind function evaluation protocol, b is the first server's secret50, and w is the client's15secret input45. The function g is constructed such that the client15cannot determine the first server's secret50given the result25, yet the same inputs45,50consistently produce the same output25R. Preferably, the protocol is also designed such that a third party does not learn any of the three values b, w, and R.

Various blind function evaluation protocols have been developed that are based on different functions. These include, as examples not intended to be limiting, implementations based on discrete-logarithm cryptography and the RSA algorithm which is based on the problem of extracting roots modulo a composite. Blind function evaluation is an instance of multi-party secure computation, introduced by A. Yao in “Protocols for Secure Computations,” IEEE FOCS (1982), pp. 160-164. In multi-party secure computation, a function is computed in which the inputs are provided by two or more parties, and the output may be kept private from some parties as well. It has been shown that any polynomial-time-computable function g can be computed securely in polynomial time by representing the function as a logic circuit and evaluating it with what amounts to a gate-by-gate protocol (which tends to be complex).

In the embodiments described below, using discrete logarithm cryptography and the RSA cryptosystem, the function g has a special form and the protocol is more efficient, but it is also possible to use another one-way function, for example a hash function, or an encryption function, and apply the general methods. Generally, the function g(w, b) should be one-way with respect to b such that it is difficult to determine b, given a set of g(w, b) values for some inputs w. Otherwise, an attacker could participate in the protocol some number of times, each time providing different values of w, and then solve for b. Also, it should be difficult, given a set of g(w, b) values for some inputs w, to determine g(w, b) for other values of w. Otherwise, an attacker could use the results of some password guesses to get other password guesses. The second property implies the first.

Yao's construction enables two parties, such as the server and the client in this implementation, to compute the output y of any polynomial-computable function g on any pair of secret inputs b and w in the domain of g in such a way that the evaluator learns y, and neither party learns any additional information. Other variants are also possible.

We assume that the server behaves correctly, i.e., adheres to the protocol, but may try to learn additional information. In this case, the Yao construction involves two phases. In the first phase, the server decides on a polynomial-sized boolean circuit C. Input to this circuit is a secret v, while the output is g(v, b). (The input b is built into the circuit.) Let v1, v2, . . . , vnrepresent the individual bits of v. The circuit C is constructed in such a way that each bit viis expressed as one of two random “tags”, yi0and yi1, the first assigning a ‘0’ bit to viand the second assigning a ‘1’ bit to vi. The server sends C (in an appropriate representation) to the user. Further details are available in the Yao paper.

In order to evaluate C on the desired secret value w=w1, w2. . . wn, the user must obtain the correct set of tags {ywi}. On the other hand, to ensure in general that the user learns no information other than y, it is critical that the user learn only these tags, and furthermore that the server not learn which tags the user has obtained. This is accomplished by means of a protocol known as one-out-of-two oblivious transfer, abbreviated 1-2 OT. 1-2 OT is a cryptographic primitive involving two players, a sender and a receiver. The sender sends two values x0and x1to the receiver. The receiver selects a bit c and receives xc. The sender learns no information about c, while the receiver learns no information about x1-c. Yao proposed an RSA cryptosystem based 1-2 OT protocol in the paper referenced above, while Goldreich, Micali, and Wigderson extended the protocol to make use of any one-way permutation.

In the second phase, the server sends the set of tags yiwito the user using a 1-2 OT protocol as follows. For each value i, the server sets x0=yi0and x1=yi1and the user selects z=wi. Once the second phase is complete, the user has all of the necessary tags to compute g(w, b).

In one embodiment, the client15uses the result25R of the blind function evaluation protocol as a decryption key25to decrypt the encrypted secrets5. In another embodiment, the client15derives from the result R25intermediary strong secrets60that can include the decryption key (and possibly other data).

The client15also authenticates65to a second server10″. Typical authentication measures can include using something the user3knows, something the user3has, some measured characteristic of the user3, or some combination. The authentication65thus can take place in various ways, including without limitation by transmission of a PIN, a password, a biometric measurement, a token code, a time-based code (such as, from a SECURID token manufactured by RSA Security Inc.), use of an encryption key, use of a hash-chain approach, such as S/KEY, or some combination. If the authentication to the second device10″ is successful, then the second device10″ provides the client15access to, or a copy of, the encrypted secrets5.

In one embodiment, after successfully authenticating to the second device10″ and decrypting the encrypted secrets5, the client15verifies55the successful recovery of the encrypted secrets5to the first server30. The verification step55could be implemented in various ways including using asymmetric cryptography, symmetric cryptography, or a proof of knowledge protocol. An advantage of using asymmetric cryptography is that the initialization step33is more straight-forward.

Successful decryption of the encrypted secrets5implies that the user3provided the client15with the correct first secret35. In one embodiment, the first server30only allows a client15to engage in the blind function evaluation protocol40a limited number of times without demonstrating a successful verification55that the encrypted secrets5were successfully decrypted. The purpose of the verification55is to ensure that an attacker could not determine the correct hardened secret25through exhaustive searching of the possible client15first secret values35. The verification55can be implemented in various ways.

In one embodiment, the encrypted secrets5include a private key8, which the client15uses to sign an identifier70. The identifier70can be a nonce or other data selected by the first server30as representing to the first server30the particular instantiation of the recovery process. The identifier70can thus serve as a challenge, to which the client15responds by showing knowledge of the private key8.

One benefit of the invention is that an attacker has to compromise both the first server30and the second device10″ to obtain a decrypted form of the encrypted secrets5. Without compromise of both servers, an attacker's best attack on the secrets is on-line guessing of the user's password and other authentication factors, if any. On-line guessing in this context means the attacker attempts to guess by participating in the protocol and providing guessed values to either the first server30or the second device10″. In general, the success of on-line guessing can be severely limited by preventing the attacker from making more than a certain number of guesses, either by halting acceptance of guesses after more than a certain number have been made, or by increasing the delay time before the system responds to an on-line guess after a certain number have been made. In general, if such guess-prevention mechanisms are in place, limiting an attacker to on-line guessing is a sufficient level of security.

For example, in a simple implementation involving a first server30and a device10(as inFIG. 2), the user has a first PIN or password and the user has a token, such as a two-factor authentication token that produces a time-based token code in response to the current time, a token code, and a second PIN. In this implementation, the first server30merely stores the intermediate data22, and transmits it to the client upon receipt of the first PIN or password. Preferably, the communication takes place over an encrypted communications channel to ensure the security of the first PIN or password and the intermediate data22. The client uses the token code to authenticate to the device10and accesses the encrypted secrets5. The intermediate data22is used to decrypt the encrypted secrets5.

In this simple implementation, an attacker that has not compromised either the first server30or the device10needs to perform both on-line password guessing and on-line token-code guessing. If the device10is compromised (but not the first server30), the attacker can either try off-line guessing of the decryption key of the encrypted secrets5(the success of which is highly improbable) or the attacker still needs to undertake on-line guessing of the first PIN or password. If the first server30is compromised (but not the device10′), the attacker still has to undertake on-line token-code guessing. If both the first server30and the second device10″ are compromised, then the attacker has direct access to the encrypted secrets and to the intermediate data22and thus can immediately decrypt the encrypted secrets35.

As another example, another embodiment makes use of the blind function evaluation protocol and a two-factor token code. An example of such an embodiment is described in more detail with reference toFIG. 5below. In this embodiment, the user has a first PIN or password (the first secret35), and the user has a two-factor authentication token as in the previous example. The client participates in the blind function evaluation protocol (also referred to as a password hardening protocol) with the first server. The client provides the first secret35as input to the blind function evaluation protocol and obtains the strong secret R25. The client then derives one intermediary strong secret value from the strong secret R. The client uses the token to authenticate to the second device10″ to access the encrypted secrets5. The intermediary strong secret T2is used to decrypt the encrypted secrets5.

In this embodiment, an attacker that has not compromised either the first server30or the second device10″ needs to perform both on-line password guessing and on-line token-code guessing. If the second device10″ is compromised (but not the first server30), the attacker can either try off-line guessing of the decryption key of the encrypted secrets5(the success of which is highly improbable) or the attacker still needs to undertake on-line guessing of the password. If the first server30is compromised (but not the second device10″), the attacker has to undertake on-line token-code guessing and on-line first secret35guessing, because the blinding prevents the attacker from knowing the strong secret R25. It is only if the both the first server30and the second device10″ are compromised that the attacker can undertake off-line password guessing (but cannot immediately decrypt the encrypted secrets5).

Thus, the use of the blind function evaluation protocol provides benefits even to a system that uses a two-factor authentication token, because information is hidden from the first server30, which information the first server30cannot reveal even if the first server30is compromised. In the event that both the first server30and the second device10′ are compromised, the user's password still provides a degree of protection. This degree of protection can be increased by increasing the amount of time that an attacker (as well as the actual user) needs to spend to derive the intermediary strong secret value T2from the first secret35. Increasing the amount of time can be accomplished by increasing the complexity of the derivation of the strong secret R (which in the embodiments described herein is already relatively complex) and by increasing the complexity of the derivation of the intermediary strong secret value T2from the strong secret R. If each derivation of T2from a guess of the first secret35is sufficiently time consuming, even off-line guessing can be made unlikely to succeed.

In still another embodiment, described in more detail below with reference toFIG. 4, the user has only a single PIN or password. The client participates in the blind function evaluation protocol with the first server and obtains the strong secret R25. The client then derives two intermediary strong secret values T1and T2from the strong secret R. One intermediary strong secret T1is used to authenticate with the second device10″ and the other intermediary strong secret T2is used to decrypt the encrypted secrets5.

In this embodiment, an attacker that has not compromised either the first server30or the second device10″ can only perform on-line password guessing. If the second device10″ is compromised (but not the first server30), the attacker can either try off-line guessing of the decryption key of the encrypted secrets5(the success of which is highly improbable) or the attacker still needs to undertake on-line guessing of the password. If the first server30is compromised (but not the second device10″), the attacker is still limited to on-line password guessing, because the blinding prevents the attacker from knowing the strong secret R25. It is only if the both the first server30and the second device10″ are compromised that the attacker can undertake off-line password guessing. Thus, this embodiment provides security against the compromise of a single server, using only a single (possibly weak) PIN or password.

Referring toFIG. 4, an embodiment of the invention uses discrete logarithm cryptography in the blind function evaluation protocol40′. Prior to a user3attempting to access the encrypted secrets5, initialization is performed as in the initialization33ofFIG. 3. One step in this initialization process is that the first server30selects75a prime p such that p=2q+1 where q is a prime. The value of p is selected in this manner because it is useful to ensure that there is a large sub-group within the multiplicative group Zp* (where Zp* is the group of integers from 1 to (p−1) under the operation of multiplication modulo p) for straight forward cryptographic computation with minimal leakage of secret information in protocols, however other arrangements are possible. The first server30communicates80pto the client15.

The security of this discrete logarithm embodiment depends upon the parameters p and q being generated appropriately, which may be, as in the embodiment described here, that p and q are prime, and p=2q+1. In other embodiments, there may be more or less requirements on p and q, with the resulting tradeoffs in security benefits. In one embodiment, both p and q are published, or otherwise made available to the client. The client can then directly verify the properties of p and q.

The first server30also selects85a secret exponent b between 1 and q−1 for each user3i that can store encrypted secrets5ET2(K1, . . . , Kn) on the second device10′. The first server30also publishes a function/that maps weaker secrets35, such as passwords, to elements of the multiplicative group Zp*. For instance, given the first secret35FS, ƒ(FS) might be defined as MGF(FS) mod(p) or MGF2(FS) mod(p) where MGF is a mask-generation function. Various mask generation functions can be used. One suitable MGF is MGF1, described in PKCS #1: RSA Cryptography Specifications, Version 2.0 B. Kaliski and J. Staddon, available at http:/www.rsalabs.com/pkcs/pkcs-1/index.html. For security purposes, the mapping should be independent of other cryptographic operations performed and should map to sufficiently randomly distributed values mod p. The function ƒ might be different for different users or groups of users, so long as it is possible for the client to determine the appropriate function to use.

A final step in the initialization is that the first server30stores90a verification value vU. In the current embodiment, the verification value vu is the user's3public key. In an alternative embodiment, the verification value vUis one of the encrypted secret5Kiknown only to the user3and the first server30, or something derived from the encrypted secret5Ki.

Having initialized to the first server30, the user3can then use the first server30to access his or her encrypted secrets5. To initiate access to the encrypted secrets5, the user3provides95his or her first secret35to the client15. The client15then generates100a random exponent k that satisfies 1≦k≦q−1. The client15next computes105r=ƒ(FS)k=wkmod p and transmits110this value along to the first server30. The exponentiation105by k serves to hide the value of ƒ(FS) from the first server30and from parties observing communications between the client15and the first server30. In this way, even a party that compromises the first server30will not be able to determine the user's3underlying first secret35. Depending on the form of ƒ(FS), it may not ensure that all values of r are equally likely.

For example, if p=2q+1 and ƒ(FS)=MGF(FS)2mod p, where MGF(FS) is defined to map to a subset of the integers between 2 and p−2, then ƒ(FS) is an element in the multiplicative subgroup of Zp* of order q, and all values of r are equally likely. As another example, if p=2q+1 and ƒ(FS)=MGF(FS), with the same definition of MGF, then ƒ(FS) is an element in the multiplicative group Zp*, but not necessarily in the subgroup of order q. The value ƒ(FS) may either have order q or order 2q. If it has order q, then all values of r are equally likely, but if it has order 2q, only about half the elements of Zp* are possible, and information about ƒ(FS) is leaked, although it is not clear how to exploit this information. As a result, if ƒ(FS) is defined without squaring, k should range from 1 to 2q−1. A small amount of information may still be leaked (in particular, whether ƒ(FS) is in the subgroup of order q or not), but this is not significant.

In any implementation where p=2q+1, one bit of b may be leaked (specifically, whether it is even or odd) by an attacker who sends values not in the multiplicative group of order q, to determine whether they are mapped into the group or not when raised to the b power. This attack can be overcome by raising to the 2b power, or choosing an even value of b. In the more general situation, ƒ(FS)=MGF(FS)amod p, where p=aq+1, and a>2, and the greatest common divisor of a and q is 1. More bits of b may be leaked in this situation, specifically, the value b mod a. This can be overcome by raising to the a·times b power, or choosing a value of b that is divisible by a. This is described further in U.S. Pat. No. 5,933,502 to Vanstone et al. The general hardening function g(w, b) in the discrete logarithm embodiment is given by g(w, b,)=wbmod p. Upon receiving r, the first server computes115s=rbmod p. The term b is the first server's30secret input. Exponentiation by this factor transforms the first secret35into a recoverable hardened secret. Undoing the exponentiation is not mathematically feasible for sufficiently large valves of b due to the discrete logarithm problem. For the same reason, the term b remains unknown to the client15. That is, even with knowledge of r and s the client15can not feasibly determine b.

In addition, if this is the user's3first attempt to access the encrypted secrets5or first attempt since successfully accessing the encrypted secrets5, the first server30initializes120the access attempt variable nU. If this is not the user's3first attempt, then the first server30increments120the access attempt variable nU. The access attempt variable nUis used by the first server30as a mechanism to lock-out or throttle an attacker who is attempting to determine the hardened secret25by guessing the first secret35. In one embodiment, if the access attempt variable nUexceeds a predetermined number, then further attempts to harden the particular user's3first secret35are prohibited until either the first secret35is changed or a system administrator determines that the failed attempts do not represent a security threat. In another embodiment, the first server30increasingly delays its communication125of s and N (discussed below) as the access attempt variable nUincrements. This throttling mechanism makes it impractical for an attacker to determine the hardened secret25by searching all possible values of the first secret35.

If the allowed number of attempts has not been exceeded, the first server30returns125s and a unique index, or nonce N, for this instantiation of the attempted recovery process. In one embodiment, the nonce N is derived from the access attempt variable nUsuch that the derived value is unique for each instantiation. In another embodiment, the nonce N is chosen at random.

Upon receiving s and N, the client15computes1301/k, the multiplicative inverse of k mod q. The client15uses this value to generate135the hardened secret25R according to R=s1/kmod p. This step135reverses the blinding factor k that was used to hide communications between the client15and the first server30. In this embodiment, the client15uses R to compute140the intermediary strong secret values Tiand T2according to the relationship Ti=KDF(R, i) where KDF is a key derivation function. The key derivation function allows the system300to produce multiple intermediary strong secrets60from the hardened secret25R. The nature of the KDF is that knowledge of T1does not make it substantially easier to determine T2. Two example key derivation functions are PBKDF1 and PBKDF2, described in PKCS #5 by RSA Laboratories, a part of RSA Security Inc., available at http://www.rsalabs.com/pkcs/pkcs-5/index.html.

The client15then authenticates65the user3to a second device10′ by transmitting141T1and downloads142the encrypted secrets5T2(K1, . . . , Kn) that have been encrypted with T2. Next, the client15recovers145the secrets Knusing T2. The client3then uses K1to produce150verification data to verify55to the first server30that the current secret decryption attempt was successful. In the current embodiment, K1is the user's3private key8and the client15uses this value to sign150the nonce N. The first server30verifies the signature on the value N by applying155the user's3stored public key vU. If the signature verifies, then the first server30is assured that the client15successfully decrypted the secret value K1. In this case, the access attempt is considered successful and the value of the access attempt variable nUis reset160. If the decryption was unsuccessful, the value of nuwould remain unchanged to be incremented120by any subsequent attempts so that, as mentioned above, if an excessive number of unsuccessful attempts were made, hardening of the particular user's3first secret35would be prohibited or throttled.

To help ensure the security of the encrypted secrets5, the client15can be configured to store the encrypted secrets5only in active memory so that they will be lost whenever the client15is shut down. In addition, the client15can be configured to purge the encrypted secrets5whenever a particular user3signs off the client15or after a fixed period of time.

If the user's only secret is a PIN or password, as it is in this embodiment, the authentication protocol between the client15and the second device10′ should not provide enough information for an eavesdropper to verify a guess of T1and T2by examining messages exchanged between the client15and the second device10′. Otherwise, an attacker that compromises the first server30can verify guesses of the password by deriving R and T1and checking whether T1is correct. If the second device10′ is physically local to or integrated with the client15, this protection may be inherent in the architecture. If the client15and the second device10′ are separated by a computer network, however, one way to achieve this is to use a secure communication protocol, such as SSL, which encrypts and integrity-protects the data.

Likewise, the hardened secret25R should be obtained from the password in a manner such that the client can be assured that R has been computed by the first server30(and not an attacker) before the client15uses a key derived from R to authenticate to the device. Otherwise, an attacker that compromises the device may be able to manipulate the protocol to cause the client15to use a different key in a way that leaks information about the user's password. For instance, by manipulating the protocol so that the intermediate value s returned is the same as the value r provided by the client, the attacker can cause the hardened secret R to equal the value ƒ(FS). The keys T1and T2would then directly depend on the password. If T1is used to authenticate to the device in a typical challenge-response protocol, the attacker will be able to verify whether guesses of the password are correct. There is a similar attack if the encrypted secrets5are transmitted in the clear. Again, the use of a secure communication channel, such as SSL will provide the necessary security.

Alternatively, a “proof of correctness” can be used to so the client can determine whether the correct value of b has been applied. A proof of correctness is stronger than an SSL session as it does not require the client to trust the server to perform the computation correctly, and so provides more than is necessary to meet the protocol's design goal, which is for the client to know that the server was involved. In embodiments using the RSA cryptosystem (described further with regard toFIG. 5), the “proof” is built in. The client simply checks that R=ƒ(FS)e(mod n). A proof involves additional computations for the discrete logarithm approach described above. An illustrative example of the embodiment shown inFIG. 4is given by a cellular telephone that contains a dedicated cryptographic chip containing encrypted secrets5. In this example the cellular telephone is the client15and the cryptographic chip is the second device10′. As cellular telephones can be lost, it is advantageous to strongly encrypt the encrypted secrets5, such as a private key8used for digital signatures, on the cryptographic chip. As mentioned above, the decryption key25necessary to decrypt strongly encrypted secrets5can be difficult for users3to remember.

Given this, the cellular telephone can be configured to employ the embodiment shown inFIG. 4in which a first secret35, such as a PIN, can be used to access strongly encrypted secrets35. According to this embodiment, a user3would first enter95a numeric PIN as a first secret35into the cellular telephone key pad when he or she wanted to, for example, execute a digital signature. The cellular telephone would then modify and blind105the PIN and transmit110it to a first server35. The first server35would then apply115its secret b and transmit125the resulting value, as intermediate data22, back to the cellular telephone. The cellular telephone would then unblind the intermediate data thereby generating135the hardened secret25R. Using the hardened secret25R, the cellular telephone would generate140two intermediary strong secrets T1and T2. Next, the cellular telephone would transmit141T1to the cryptographic chip for authentication65′. Assuming that the authentication65′ was successful, the cryptographic chip would then download142into the cellular telephone's active memory the encrypted secrets5. The cellular telephone would then use T2to decrypt145the encrypted secrets5. Using the private key8, or employing one of the alternative methods discussed above, the cellular telephone would then verify55to the first server30that it had successfully accessed the encrypted secrets5. With access to the private key8, the cellular telephone could then use the private key8to form a digital signature to, for example, execute a digital transaction.

Referring toFIG. 5, in another embodiment, the blind function evaluation protocol40″ is based on the RSA cryptosystem, which is based on the problem of extracting roots modulo a composite, and which is described in R. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-key Cryptosystems,” Communications of the ACM, 21(2) pp. 120-126, February 1978 and “PKCS #1: RSA Cryptography Specifications,” Version 2.0, by B. Kaliski and J. Staddon, available at http://www.rsalabs.com/pkcs/pkcs-1/index.html. The use of the RSA cryptosystem to perform blind signatures in the context of anonymous digital cash is described in D. Chaum, “Security Without Identification: Transaction Systems to Make Big Brother Obsolete,” Communications of the ACM, 28 (1985), 1030-1044.

Also, in this embodiment, to show an example of this type of authentication, the authentication65″ operation employs a time-based token code. As before, the system includes a client15that receives a first secret35from a user3, a first server30, and a second device10′.

As part of initialization, the first server30generates170a product n that is the product of two primes, piand qifor each user3i. The values piand qiare large prime numbers, for example numbers larger than 512 bits in length, and n is the RSA modulus. The first server30also selects175a value eithat is a small integer that is relatively prime to LCM(pi−1, qi−1), where LCM stands for Least Common Multiple. The value of eiis the public exponent in the RSA cryptosystem. The public exponent eiis chosen to be relatively prime to LCM(pi−1, qi−1) so that it is assured that a multiplicative inverse b exists. The value of b is defined by b=ei−1mod LCM(pi−1, qi−1). The RSA cryptosystem makes use of the fact that Mbemod(n)=Mebmod(n)=M1mod n, where M is a message to be encrypted. That is, the exponentiation of M to eiand then to b or the exponentiation of M to b and then eireturns M to its original value mod(n).

The value b is the server secret input, which is either computed180by the first server or, in an alternative embodiment, stored on the first server30after being generated elsewhere, during initialization33(FIG. 3). An additional step in the initialization of the client15and the first server30is that both store185,185′ a secret seed SS that is used as part of the authentication65″ process. A further initialization step is that the first server30stores188a copy of the public exponent eiand the modulus nior publishes them so that they can be provided to the client, and initializes189the access attempt variable nU.

The hardening function R=g(w, b) in the RSA cryptosystem-based embodiment is defined by g(w, b)=wbmod n. The value w is generated 190 as above via a function ƒ applied to a user3supplied first secret35, such as a password P. That is, w=ƒ(FS) where the function ƒ may be based on a mask generation function and FS is the first secret35as previously. To blind the initial communication from the client15to the first server30, the client15generates195a random value aisuch that (1<ai<n−1) and gcd(ai, n)=1. The value aiis relatively prime to n so that an inverse of a1eiis guaranteed to exist. The client15then 200 computes Mi=aieiw mod n. Here, aieiis a random element of Zn*, regardless of ƒ(w). Provided that ƒ(w) is in Zn*, so that it does not contain a factor in common with n, the Miwill be a random element of Zn*, so all values of Miare equally likely. As all values of aiare equally likely, multiplication by the value aiserves to blind the value of w mod n with respect to the first server30and with respect to someone observing communications between the client15and the first server30. The value Miis transmitted205to the first server30by the client15.

The next step in the blind function evaluation protocol40″ is that the first server30computes210the value c=Mibmod n and returns215this value to the client15along with the nonce N. As described above, this operation reverses the exponentiation by eibecause eiand b are the multiplicative inverses of each other. Mathematically the value of c is given by h=mod n=aiwbmod n. If the space for b is sufficiently large, the exponentiation of Miby b serves to harden the user's3first secret35P. As mentioned above, the value of wbmod n is blinded from observers (including the first server30) by the multiplication by the random value of ai. In order to limit unauthorized attempts to harden a first secret35, the nonce N is returned is returned by the first server30to the client15to identify this instantiation of the encrypted secrets5recovery attempt for verification purposes.

The final stage in the blind function evaluation protocol40″ first involves the client15removing the blinding associated with the random value ai. The client15achieves this by multiplying220c mod n by ai−1mod n. The unblinding is represented mathematically by ai−1c=wbmod n. To provide additional security to the hardened secret R=wbmod n25″, the unblinded value is next entered225as the input to a hash function h so that the intermediary strong secret T365″ is given by T3=h(ai−1c mod n).

An advantage of the RSA cryptosystem-based blind function evaluation protocol40″ is that it only involves one short exponentiation, one multiplication, and one modular inversion per user3. The modulus may be the same for each user3i provided that the exponents eiare different, so that protocol runs are associated with a particular user3i and throttling of other account-specific countermeasures can be enabled. If the exponent eivaries for each user3i, the set of possible exponents should be pairwise relatively prime to LCM(p−1, q−1).

The security of the RSA cryptosystem-based blind function evaluation protocol40″ depends on the modulus n and the exponent e forming a valid RSA public exponent such that n is a product of two large primes, and e is relatively prime to Φ(n). If n is not a product of two large primes, it may be possible for an attacker to determine the value R from ƒ(w), and if e is not relatively prime to Φ(n), then information about ƒ(w) may be leaked from the client information aeƒ(w).

In one embodiment, the server provides the n and e values to the client in a certificate, where the certificate associates the n and e values with the particular user. The certificate authority can assure that the n and e values are valid before issuing the certificate. To do this the certificate authority may, for example, use the methods and apparatus described in co-pending U.S. Ser. No. 09/188,963, entitled “Methods and Apparatus for Verifying the Cryptographic Security of a Selected Private and Public Key Pair Without Knowing the Private Key,” by Liskov et al., incorporated herein by reference.

It should be noted that in the embodiment ofFIG. 5, proper selection of e may be more critical than selection of n. If a compromised first server selects n such that it does not have prime factors, that will help an attacker who compromises the device. But a improper selection of e will make it possible for someone else (who has not compromised the device10′), to attack the system.

As mentioned above, the authentication step65can be implemented in various ways. In the embodiment shown inFIG. 5, the authentication65″ shows the details of using a time-based token code. Under this method, the client15generates230a dynamic password L as a function of a secret seed SS and the current time CT (and optionally a user PIN PP) and sends235the dynamic password L to the second device10′. To authenticate65″ the client15, the second device10′ regenerates240a version L′ of the dynamic password L from its copy of the secret seed SS, the current time CT (and the user PIN PP, if appropriate). The second device10′ then compares245the dynamic password L it received from the client to the one L′ that it generated. If there is not an exact match, the second device10′ can be configured to recalculate the regenerated dynamic password L′ utilizing times nearby to its current time CT to synchronize its clock with the client's15clock. In an alternative embodiment, the second device10′ does not directly verify the dynamic password L but instead employs a third server to generate and verify the client's15dynamic password L.

In the current embodiment, the generation of the dynamic password L by the user is implemented as a physical token, such as a RSA SECURID token. In an additional alternative embodiment, the physical token is combined with a PIN to provide additional security through a two-factor authentication process. The use of the token is just one way that authentication could be implemented.

In another embodiment, biometric information is used for the authentication step65″. The use of biometric derived information for authentication65″ could be similar to the use of biometric derived information for the first secret35. The initial biometric information, such as a fingerprint or iris scan, is here converted into-authentication data. In one embodiment as in the first secret35case, the error correction codes are stored on error correction servers connected to the network20and can be signed by an independent server to ensure integrity. Before providing the authentication data, the client15obtains the error correcting information and verifies its integrity. The client15then combines the information with the initial biometric information to generate the authentication data that is used to authenticate65″ to the second device10′. In other embodiments, the error correction codes are stored in other locations including on the client15, on the first server30, or the second device10′.

In an additional embodiment also employing biometric-derived information for authentication65″ no error correction codes are utilized. In this embodiment, the authentication65″ process tolerates a range of biometric values. According to this embodiment, the client15transmits the biometric derived information to the second device10′, and if this information falls within the range that the second device10′ is configured to accept, then the second device10′ will consider that the client15has successfully been authenticated65″.

Once the client15has been authenticated65″ by the second device10′, the second device10′ provides250to the client15the encrypted secrets5. To decrypt the encrypted secrets5the client15uses the intermediary strong secret T3. Once the encrypted secrets5are decrypted255, the client15verifies55this to the first server30as before. That is, the client15signs260the nonce N with the user's3private key8and transmits265this valve to the first server30. The client15has access to the user's private key8because, as before, the user's private key8was one of the encrypted secrets5. The first server30then checks270the signature using the user's3public key Pubuand verifies275that the nonce N representing this instantiation of the access attempt is correct. Assuming the nonce N is verified, the value of the access attempt variable nuis reset280for further access attempts.

Referring toFIG. 6, in another embodiment, a user603uses commercially available web browser software running on a personal computer615(the client in this embodiment), to access a web server610over a computer network such as the Internet. In this interaction with the web server610, the user603provides certain personal information, such as the user's name and address, and possibly other information, such as personal preferences, demographic information, financial information (credit card or bank account numbers), and so on, to the web server610.

This personal information is useful for the interaction of the user603with the web server610using the client615, and the user603would typically prefer not to provide the same information to the web server610each time the user interacts with the web server610. The personal information could be stored on the client615, but this may not be practical, for example because the user would like to access the web server610from more than one location, or for example because the client615is not used by the user603exclusively.

It therefore is useful to store the personal information on the web server610, but in a manner that makes it difficult for an attacker to access the personal information. For performance reasons, web servers are frequently placed on an open network outside of firewalls and other security measures, and so they are vulnerable to attack. The user's personal information can be stored as encrypted secrets605. As described above, if a user-provided password (or other weak secret) is used as a key to encrypt the personal information, the password is likely to be a weak key, and so it will likely afford less than optimal protection to the encrypted secrets. In one embodiment, the encrypted secrets are stored such that they can be decrypted with a hardened password. In various embodiments, a user's password is used as the input to a blind function evaluation protocol in which either the client or the web server participates with a hardening server630. The result of the blind function evaluation protocol is used as or to derive a decryption key for the encrypted secrets.

In one embodiment, the user communicates651with the web server610, and the web server610directs the browser to communicate652with the hardening server630. If the web browser does not have the appropriate code to engage in the blind function evaluation protocol, either the web server610or the hardening server630can provide the browser with the necessary code, for example in the form of a Java applet, or in the form of a browser plug-in, or in the form of executable code for the computer.

The client615and the hardening server630engage in a blind function evaluation protocol, with the result that the client derives a hardened password. The hardened password is communicated to the web server, which then decrypts the user's personal information, and so can make the personal information available to the user as part of the user's interaction with the web server610. When the user has completed his interaction with the web server610(e.g. logs off), the web server deletes the unencrypted secrets, keeping only the encrypted secrets in its data store. If the data store of the web server610is compromised, the attacker has access only to the encrypted secrets, and cannot directly access to the user's personal information.

In one embodiment, the blind function evaluation protocol takes as input a web server610identifier, in addition to the client information and the first server secret. The web server identifier might be, for example, some portion of the URL or network address of the web server, or the web server identifier could be another identifier assigned to one or more web servers. The web server610identifier is used in the blind function evaluation protocol, for example as an input to the blind function, and/or as an input to the key derivation function that derives the decryption key from the result of the blind function. By including the web server identifier610as an input to the blind function evaluation protocol, the user need only have one password, yet the client would generate different decryption keys for different web servers.

In one such embodiment, the web server610communicates the verification information to the hardening server630. When the web server610decrypts the encrypted secrets, it uses some information in the encrypted secrets to prove to the hardening server that successful decryption has occurred. In this embodiment, the client communicates to the web server610, along with the decryption key, the nonce or other verification information provided by the hardening server.

In another embodiment, the client615provides the client information (derived from the user's password and/or other secret data) directly to the web server610, and the web server610engages652in the blind function evaluation protocol with the hardening server. The web server610then derives the decryption key from the hardened password (which may be the hardened password) to decrypt the encrypted secrets. In this way, the client615has to do less work, but the web server is able to store data that is only vulnerable to compromise when the user is communicating with the web server610.

Referring toFIG. 7, in a variation of the embodiment ofFIG. 6, the client715uses the password hardening server730to generate a hardened password that is used to authenticate the client715to the web server710. The client715receives a web server identifier WSID771. The web server identifier might be, for example, some portion of the URL or network address of the web server, or the web server identifier could be another identifier assigned to one or more web servers. Instead of receiving the WSID from the web server, the client could derive the WSID from such other information, store a list of WSID's locally, or request the WSID from a server on the network (such as the authentication server730).

The client provides772the client information (which is derived from the user's secret) to the authentication server730as part of the client's participation in a blind function evaluation protocol. The client may also provide the web server identifier WSID, and the client may also provide a user identifier to the authentication server730as part of the blind function evaluation protocol. The WSID can be used in the blind function evaluation protocol, for example as an additional input to the blind function, to select a server secret to use in the blind function evaluation protocol. This may be in addition to or instead of the use of the WSID as an input to the key derivation function that derives the decryption key from the result R of the blind function. The user identifier may be used to selected the appropriate server secret, or for other purposes.

The authentication server730returns the blinded result R to the client715, along with a nonce or other session identifier772. The client generates a hardened password for use in authenticating to the web site based on the result R of the blind function evaluation protocol and possibly the other information (i.e. user identifier, web site identifier). By including the web server identifier WSID as an input to the key derivation function (and/or as an input to the blind function evaluation protocol), the user need only have one password, yet the client can generate different passwords for authentication to different web servers.

The client communicates774the hardened password and the nonce to the web server710. For the verification, the web server710sends775a message to the authentication server730, indicating whether or not the authentication attempt associated with the nonce was successful. If the authentication was successful, the hardening server resets the attempt counter, if it was not successful, the account variable is increased. Preferably, the message is communicated such that the web server710cannot be impersonated. For example, the communication can include the digital signature of the web server on the nonce.