Authentication protocol using a multi-factor asymmetric key pair Number:7,386,720 from the United States Patent and Trademark Office (PTO) owispatent Techniques for user authentication based upon an asymmetric key pair having a public key and a split private key are provided. A first portion of the split private key is generated based upon multiple factors under control of the user. The factors include a password. A challenge is cryptographically combined with a first one of the multiple factors, but not the user password, to form a first message. The first message is transformed with the generated first portion to form a second message, which is then sent to an authentication entity. The sent second message is transformed to authenticate the user by proving direct verification of user control of the first factor.<H Authentication, asymmetric, Authentication, , 7386720.html, Patent, pto, 7386720

Title: Authentication protocol using a multi-factor asymmetric key pair

Abstract: Techniques for user authentication based upon an asymmetric key pair having a public key and a split private key are provided. A first portion of the split private key is generated based upon multiple factors under control of the user. The factors include a password. A challenge is cryptographically combined with a first one of the multiple factors, but not the user password, to form a first message. The first message is transformed with the generated first portion to form a second message, which is then sent to an authentication entity. The sent second message is transformed to authenticate the user by proving direct verification of user control of the first factor.

Patent Number: 7,386,720 Issued on 06/10/2008 to Sandhu, et al.

Inventors: Sandhu; Ravinderpal Singh (Oak Hill, VA), Schoppert; Brett Jason (Leesburg, VA), Ganesan; Ravi (Half Moon Bay, CA), Bellare; Mihir (San Diego, CA), Desa; Colin Joseph (Herndon, VA)
Assignee: TriCipher, Inc. (San Mateo, CA)

Appl. No.: 11/055,988

Filed: February 14, 2005

Current U.S. Class: 713/155 ; 380/277; 380/282; 380/44; 380/45; 713/168; 713/170; 713/171; 726/6

Field of Search: 713/155

References Cited [Referenced By]

U.S. Patent Documents


5623546	April 1997	Hardy et al.
5768388	June 1998	Goldwasser et al.
5956407	September 1999	Slavin
6026163	February 2000	Micali
6072876	June 2000	Obata et al.
6542608	April 2003	Scheidt et al.
6662299	December 2003	Price, III
6845160	January 2005	Aoki
7095851	August 2006	Scheidt
7260552	August 2007	Riera Jorba et al.
2002/0078345	June 2002	Sandhu et al.
2005/0002532	January 2005	Zhou et al.

Other References

Basney, J., et al, `Credential Wallets: A Classification of Credential Repositories Highlighting MyProxy`, NCSA , Univ. of Illinois, 2003, entire document, http://www.ncsa.uiuc.edu/.about.jbasney/credentialwalletTPRC.pdf. cited by examiner .
RSA Laboratories, "PKCS #5 v2.0: Password-Based Cryptography Standard", Dec. 10, 1998, pp. 1-25. cited by other.

Primary Examiner: Baum; Ronald

Claims

What is claimed is:

1. A method for user authentication based upon an asymmetric key pair having a public key and a split private key, comprising: generating a first portion of the split private key based upon multiple factors under control of the user, the multiple factors including a user password; cryptographically combining a challenge with a first one of the multiple factors other than the user password to form a first message; transforming the first message with the generated first portion to form a second message; transmitting the second message to an authentication entity; and transforming the transmitted second message to authenticate the user, the transformation of the transmitted second message providing direct verification of user control of the first factor.

2. The method of claim 1, wherein the transformation of the transmitted second message provides direct verification of user control of the first factor and indirect verification of user control of the password.

3. The method of claim 2, wherein: transforming the transmitted second message includes applying a second portion of the split private key and the public key of the asymmetric key pair to the transmitted second message to recover the first message; and recovery of the first message provides the indirect verification of user control of the password.

4. The method of claim 1, wherein: forming the first message includes cryptographically combining the challenge with each of the multiple factors other than the user password; and the transformation of the transmitted second message provides direct verification of user control of each of the multiple factors combined with the challenge.

5. The method of claim 4, wherein the asymmetric key pair having a public key and a split private key is a first asymmetric key pair, the multiple factors are the password, a first entire private key associated with a second asymmetric key pair, and a second entire private key associated with a third asymmetric key pair, and further comprising: cryptographically signing a first hash of the challenge with the first entire private key, cryptographically signing a second hash of the challenge with the second entire private key, and combining the cryptographically signed first and second hashes with the challenge to cryptographically combine the challenge with each of the multiple factors other than the user password to form a first message.

6. The method of claim 5, further comprising: applying a first public key associated with the second asymmetric key pair to the signed first hash to recover the challenge to provide direct verification of user control of the first entire private key; and applying a second public key associated with the third asymmetric key pair to the signed second hash to recover the challenge to provide direct verification of user control of the second entire private key.

7. The method of claim 1, further comprising: receiving the challenge from the authentication entity prior to cryptographically combining the challenge with the first factor.

8. The method of claim 1, further comprising: destroying the generated first portion after transforming the first message.

9. The method of claim 1, further comprising: performing multiple cryptographic operations to produce a result, at least one of the multiple cryptographic operations based upon less than all the multiple factors, and a final performed one of the multiple cryptographic operations based upon all the multiple factors, and performing a cryptographic operation based upon the produced result to generate the first portion of the split private key.

10. The method of claim 1, wherein the password is not stored in a persistent state.

11. A system for user authentication based upon an asymmetric key pair having a public key and a split private key, comprising: a first network station configured to i) generate a first portion of the split private key based upon multiple factors under control of the user, the multiple factors including a user password, ii) cryptographically combine a challenge with a first one of the multiple factors other than the user password to form a first message, iii) transform the first message with the generated first portion to form a second message, and iv) transmitting the second message; and a second network station configured to i) receive the transmitted second message, and ii) transform the transmitted second message to authenticate the user; wherein the transformation of the transmitted second message provides direct verification of user control of the first factor.

12. The system of claim 11, wherein the transformation of the transmitted second message provides direct verification of user control of the first factor and indirect verification of user control of the password.

13. The system of claim 12, wherein: transforming the transmitted second message includes applying a second portion of the split private key and the public key of the asymmetric key pair to the transmitted second message to recover the first message; and recovery of the first message provides the indirect verification of user control of the password.

14. The system of claim 11, wherein: the first network station is further configured to cryptographically combine the challenge with each of the multiple factors other than the user password to form the first message; and the transformation of the transmitted second message provides direct verification of user control of each of the multiple factors combined with the challenge.

15. The system of claim 14, wherein: the asymmetric key pair having a public key and a split private key is a first asymmetric key pair; the multiple factors are the password, a first entire private key associated with a second asymmetric key pair, and a second entire private key associated with a third asymmetric key pair; the first network station is further configured to form the first message by i) cryptographically signing a first hash of the challenge with the first entire private key, cryptographically signing a second hash of the challenge with the second entire private key, and combining the cryptographically singed first and second hashes with the challenge.

16. The system of claim 15, wherein the second network station is further configured to i) apply a first public key associated with the second asymmetric key pair to the signed first hash to recover the challenge to provide direct verification of user control of the first entire private key, and ii) apply a second public key associated with the third asymmetric key pair to the signed second hash to recover the challenge to provide direct verification of user control of the second entire private key.

17. The system of claim 11, wherein: the second network station is further configured to transmit the challenge to the first network station; and the first network station is further configured to receive the transmitted challenge prior to cryptographically combining the challenge with the first factor.

18. The system of claim 11, wherein the first network station is further configured to destroy the generated first portion after transforming the first message.

19. The system of claim 11, wherein the first network station is further configure to i) perform multiple cryptographic operations to produce a result, at least one of the multiple cryptographic operations based upon less than all the multiple factors, and a final performed one of the multiple cryptographic operations based upon all the multiple factors, and ii) perform a cryptographic operation based upon the produced result to generate the first portion of the split private key.

20. The system of claim 11, wherein the password is not stored in a persistent state.

21. An apparatus for user authentication based upon an asymmetric key pair having a first key and a second key, with the first key split into multiple portions, with a first of the multiple portions of the split first key being based on multiple factors, including a user password, the apparatus comprising: a communications port configured to receive a message transformed with the first portion of the split first key, wherein the message includes a challenge and a first of the multiple factors, other than the user password, cryptographically combined; and a processor configured with logic that is executable to further transform the received transformed message to authenticate the user and directly verify user control of the first factor.

22. The apparatus of claim 21, wherein: the further transforming is performed by applying a second portion of the split first key and the second key of the asymmetric key pair to the received transformed message to recover the message; and recovery of the message also indirectly verifies user control of the password.

Description

RELATED APPLICATIONS

This application is related to U.S. application Ser. No. 11/055,987, filed concurrently herewith, and entitled "ARCHITECTURE FOR ASYMMETRIC CRYPTO-KEY STORAGE", U.S. application Ser. No. 11/055,986, filed concurrently herewith, and entitled "TECHNIQUE FOR ASYMMERIC CRYPTO-KEY GENERATION", U.S. application Ser. No. 11/056,120, filed concurrently herewith, and entitled "MULTIPLE FACTOR PRIVATE PORTION OF AN ASYMMETRIC KEY", U.S. application Ser. No. 11/056,116, filed concurrently herewith, and entitled "ROAMING UTILIZING AN ASYMMETRIC KEY PAIR", U.S. application Ser. No. 11/056,114, filed concurrently herewith, and entitled "ASYMMETRIC KEY PAIR HAVING A KIOSK MODE", and U.S. application Ser. No. 11/056,115, filed concurrently herewith, and entitled "TECHNIQUE FOR PROVIDING MULTIPLE LEVELS OF SECURITY". This application is also related to U.S. application Ser. No. 09/739,260, filed Dec. 19, 2000, and entitled "SYSTEM AND METHOD FOR CRYPTO-KEY GENERATION AND USE IN CRYPTOSYSTEM", U.S. application Ser. No. 10/849,818, filed May 21, 2004, and entitled "ONE TIME PASSWORD ENTRY TO ACCESS MULTIPLE NETWORK SITES", which is a continuation of U.S. application Ser. No. 09/739,114, filed Dec. 19, 2000, (now abandoned) and U.S. application Ser. No. 09/739,260, filed Dec. 19, 2000, U.S. application Ser. No. 09/739,112, filed Dec. 19, 2000, and entitled "HIGH SECURITY CRYPTO SYSTEM", U.S. application Ser. No. 09/739,113, filed Dec. 19, 2000, and entitled "SECURE COMMUNICATIONS NETWORK WITH USER CONTROL OF AUTHENTICATED PERSONAL INFORMATION PROVIDED TO NETWORK ENTITIES", U.S. application Ser. No. 09/739,119, filed Dec. 19, 2000, and entitled "METHOD AND SYSTEM FOR AUTHORIZING GENERATION OF ASYMMETRIC CRYPTO KEYS", U.S. application Ser. No. 09/739,118, filed Dec. 19, 2000, and entitled "SYSTEM AND METHOD FOR AUTHENTICATION IN A CRYPTO SYSTEM UTILIZING SYMMETRIC AND ASYMMETRIC CRYPTO KEYS", and U.S. application Ser. No. 09/739,111, filed Dec. 19, 2000, and entitled "SYSTEM AND METHOD FOR GENERATION AND USE OF ASYMMETRIC CRYPTO KEYS EACH HAVING A PUBLIC PORTION AND MULTIPLE PRIVATE PORTIONS". This application claims priority based upon Provisional U.S. application Ser. No. 60/644,028, filed Jan. 18, 2005, and entitled "THE TRICIPHER ARMORED CREDENTIAL SYSTEM", the contents of which are incorporated herein in their entirety by reference.

TECHNICAL FIELD

This invention relates to cryptosystems. More particularly, the present invention relates to split key cryptosystem having multiple levels of security.

BACKGROUND ART

Today, computing devices are almost always interconnected via networks. These networks can be large closed networks, as within a corporation, or truly public networks, as with the Internet. A network itself might have hundreds, thousands or even millions of potential users. Consequently it is often required to restrict access to any given networked computer or service, or a part of a networked computer or service, to a subset of the users on the public or closed network. For instance, a brokerage might have a public website accessible to all, but would like to only give Ms. Alice Smith access to Ms. Alice Smith's brokerage account.

Access control is an old problem, tracing its roots to the earliest days of computers. Passwords were among the first techniques used, and to this day remain the most widely used, for protecting resources on a computer or service.

In its simplest form, known as single factor authentication, every user has a unique password and the computer has knowledge of the user password. When attempting to log on Alice would enter her userid, say alice, and password, say apple23, the computer would compare the pair, i.e. alice, apple23, with the pair it had stored for Alice, and if there is a match would establish a session and give Alice access.

This simple scheme suffers from two problems. First, the table containing the passwords is stored on the computer, and thus represents a single point of compromise. If Eve could somehow steal this table, she would be able to access every user's account. A second problem with this approach is that when Alice enters her password it travels from her terminal to the computer in the clear, and Eve could potentially eavesdrop. Such eavesdropping is known as a Man-In-The-Middle attack. For instance the "terminal" could be Alice's PC at home, and the computer could be a server on the Internet, in which case her password travels in the clear on the Internet. It will be recognized by those with ordinary skill in the art that a Man-in-The-Middle attack can go beyond eavesdropping to modify the contents of the communication.

Various solutions have been proposed and implemented to solve these two issues. For instance, to solve the first problem of storing the password on the computer, the computer could instead store a one way function of the password. E.g. F(apple23)=XD45DTY, and the pair {alice, XD45DTY}. In this example as F( ) is a one way function, computing XD45DTY from apple23 is easy, but as it is a "one way function", the reverse is believed to be computationally difficult or close to impossible. So when Alice logs on and sends the computer {alice, apple23}, the computer can compute F(apple23) and compare the result with XD45DTY. The UNIX operating system was among the first to implement such a system in the 1970's. However, this approach, while solving the problems due to the storage of the password on the computer, does not solve the problem of the password traveling in the clear.

Multiple factor authentication also exists as a solution to the problems inherent with single factor authentication. In multiple factor authentication, at least knowledge of, if not actual possession of, at least two factors must be shown for authentication to be complete. It should be understood that in multiple factor authentication, each factor remains separate. That is, the factors are not combined. Further, the factors are not even concatenated. Several multiple factor authentication techniques exist, including one time password token techniques, encrypted storage techniques, smart card techniques, and split key techniques.

In one time password token techniques, two passwords are utilized, one being a permanent password associated with the user, and the other being a temporary, one-time use, password generated by a password generator. The permanent password may be optional. The temporary password has a finite usable life, such as sixty seconds. At the end of the useable life, another temporary password is generated. An authentication server knows each usable password as well as its useable life, based upon algorithms well known to one of ordinary skill in the art. A user transmits both the permanent password (first factor) and a temporary password (second factor) to the authentication server which then verifies both passwords. The passwords are transmitted in the clear, thus token techniques are subject to man-in-the-middle attacks.

Encrypted storage techniques utilize a cryptographic key, to be discussed further below, stored on either removable media or a hard drive. The cryptographic key is encrypted with a user's password. After decryption with the user's password, the key is then stored, at least temporarily, in memory of the user's computer system where it is used to either encrypt or decrypt information. As will be recognized by one of ordinary skill, this particular approach is undesirable due to it being susceptible to a dictionary attack, to be discussed in detail further below.

In smart card techniques, a private portion of an asymmetric cryptographic key, to be discussed further below, is stored on a smart card, which is portable. A specialized reader attached to a computer system is used to access the smart card. More particularly, the user enters a PIN (the first factor) to `unlock` the smart card. Once unlocked, the smart card encrypts or decrypts information using the key stored thereon. It should be stressed that in smart card techniques the key never leaves the smart card, unlike in the encrypted storage techniques discussed above. Rather, electronics within the smart card itself perform the encrypting and/or decrypting. Smart card techniques are associated with certain problems. These problems include the fact that the technique is costly to implement, due to hardware costs. Further, a lack of readers makes use of a user's smart card difficult, and smart cards themselves are subject to loss.

Before discussing in detail the more sophisticated conventional techniques for authentication, which are based upon split key technology, let us briefly describe symmetric and asymmetric key cryptography.

In symmetric key cryptography, the two parties who want to communicate in private share a common secret key, say K. The sender encrypts messages with K, to generate a cipher, i.e. C=Encrypt(M,K). The receiver decrypts the cipher to retrieve the message, i.e. D=Decrypt(C,K). An attacker who does not know K, and sees C, cannot successfully decrypt the message, if the underlying algorithms are strong. Examples of such systems are DES3 and RC4. Encryption and decryption with symmetric keys provide a confidentiality, or privacy service.

Symmetric keys can also be used to provide integrity and authentication of messages in a network. Integrity and authentication means that the receiver knows who sent a message and that the message has not been modified so it is received as it was sent. Integrity and authentication is achieved by attaching a Message Authentication Code (MAC) to a message M. E.g., the sender computes S=MAC(M,K) and attaches S to the message M. When the message M reaches the destination, the receiver also computes S'=MAC(M,K) and compares S' with the transmitted value S. If S'=S the verification is successful, otherwise verification fails and the message should be rejected. Early MACs were based on symmetric encryption algorithms such as DES whereas more recently MACs are constructed from message digest functions, or "hash" functions, such as MD5 and SHA-1. The current Internet standard for this purpose is known as hash-based MAC (HMAC).

By combining confidentiality with integrity and authentication, it is possible to achieve both services with symmetric key cryptography. It is generally accepted that different keys should be used for these two services and different keys should be used in different directions between the same two entities for the same service. Thus if Alice encrypts messages to Bob with a shared key K, Bob should use a different shared key K' to encrypt messages from Bob to Alice. Likewise Alice should use yet another key K'' for MACs from Alice to Bob and Bob should use K''' for MACs from Bob to Alice. Since this is well understood by those skilled in the art, we will follow the usual custom of talking about a single shared symmetric key between Alice and Bob, with the understanding that strong security requires the use of four different keys.

Symmetric key systems have always suffered from a major problem--namely how to perform key distribution. How do Bob and Alice agree on K? Asymmetric key cryptography was invented to solve this problem. Here every user is associated with two keys, which are related by special mathematical properties. These properties result in the following functionality: a message encrypted with one of the two keys can then only be decrypted with the other.

One of these keys for each user is made public and the other is kept private. Let us denote the former by E, and the latter by D. So Alice knows D.sub.alice, and everyone knows E.sub.alice. To send Alice the symmetric key K, Bob simply sends C=Encrypt(K,E.sub.alice). Alice, and only Alice (since no one else knows D.sub.alice), can decrypt the ciphertext C to recover the message, i.e. Decrypt(C,D.sub.alice)=K. Now both Alice and Bob know K and can use it for encrypting subsequent messages using a symmetric key system. Why not simply encrypt the message itself with the asymmetric system? This is simply because in practice all known asymmetric systems are fairly inefficient, and while they are perfectly useful for encrypting short strings such as K, they are inefficient for large messages.

The above illustrates how asymmetric cryptography can solve the key distribution problem. Asymmetric cryptography can also be used to solve another important problem, that of digital signatures. To sign a message M, Alice encrypts it with her own private key to create S=Encrypt(M,D.sub.alice). She can then send (M,S) to the recipient who can then decrypt S with Alice's public key to generate M', i.e. M'=Decrypt(S,E.sub.alice). If M'=M then the recipient has a valid signature as only someone who has D.sub.alice, by definition only Alice, can generate S, which can be decrypted with E.sub.alice to produce M. To convey the meaning of these cryptographic operations more clearly they are often written as S=Sign(M,D.sub.alice) and M'=Verify(M,S,E.sub.alice). It is worth noting that asymmetric key digital signatures provide non-repudiation in addition to the integrity and authentication achieved by symmetric key MACs. With MACs the verifier can compute the MAC for any message M of his choice since the computation is based on a shared secret key. With digital signatures this is not possible since only the sender has knowledge of the sender's private key required to compute the signature. The verifier can only verify the signature but not generate it. It will be recognized by those with ordinary skill in this art that there are numerous variations and elaborations of these basic cryptographic operations of symmetric key encryption, symmetric key MAC, asymmetric key encryption and asymmetric key signatures.

The RSA cryptosystem is one system that implements asymmetric cryptography as described above. In particular the RSA cryptosystem allows the same public-private key pair to be used for encryption and for digital signatures. It should be noted there are other asymmetric cryptosystems which implement encryption only e.g., ElGamal or digital signature only, e.g., DSA. Technically the public key in RSA is a pair of numbers E, N and the private key is the pair of numbers D, N. When N is not relevant to the discussion it is commonplace to refer to the public key as E and the private key as D.

Finally, the above description does not answer the important question of how Bob gets Alice's public key E.sub.alice. The process for getting and storing the binding [Alice, E.sub.alice] which binds E.sub.alice to Alice is tricky. The most practical method appears to be to have the binding signed by a common trusted authority. So such a "certificate authority" (CA) can create CERT.sub.alice=Sign([Alice, E.sub.alice], Dca). Now CERTalice can be verified by anyone who knows the CA's public key Eca. So in essence, instead of everyone having to know everyone else's public key, everyone only need know a single public key, that of the CA. More elaborate schemes with multiple Certificate Authorities, sometimes having a hierarchical relationship, have also been proposed.

Asymmetric key cryptosystems have been around for a long time, but have found limited use. The primary reasons are twofold: (a) the private key D in most systems is long, which means that users cannot remember them, and they have to either be stored on every computer they use, or carried around on smart cards or other media; and (b) the infrastructure for ensuring a certificate is valid, which is critical, is cumbersome to build, operate, and use. The first technique proposed to validate certificates was to send every recipient a list of all certificates that had been revoked. This clearly does not scale well to an environment with millions of users. The second method proposed was to require that one inquire about the validity of a certificate on-line, which has its own associated problems.

A system based on split private key cryptography has been developed to solve these two issues, among others. In this system the private key for Alice, i.e. D.sub.alice, is further split into two parts, D.sub.aa which Alice knows, and a part D.sub.as which is stored at a security server. To sign a message, Alice could perform a partial encryption to generate a partial signature, i.e. PS=Sign(M,Das). Alice then sends the server PS which `completes` the signature by performing S=Sign(PS,Dss). This completed signature S is indistinguishable from one generated by the original private key, so the rest of the process works as previously described. However, D.sub.aa can be made short, which allows the user to remember it as a password, so this system is consumer friendly. Further, if the server is informed that a particular ID has been revoked, then it will cease to perform its part of the operation for that user, and consequently no further signatures can ever be performed. This provides for instant revocation in a simple highly effective fashion. It will be recognized by those with ordinary skill in the art that use of a split private key for decryption purposes can be similarly accomplished, and that the partial signatures (or decryptions) may be generated in the opposite sequence, that is first on the security server and subsequently by the user's computer, or even be computed concurrently in both places and then combined.

Let us return now to password based systems. Challenge-response systems solve the issue of having to send passwords in the clear across a network. If the computer and Alice share a secret password, P, then the computer can send her a new random challenge, R, at the time of login. Alice computes C=Encrypt(R,P) and sends back C. The computer decrypts Decrypt(C,P)=C'. If C=C', then the computer can trust that it is Alice at the other end. Note however that the computer had to store P. A more elegant solution can be created using asymmetric cryptography. Now Alice has a private key D.sub.alice, or in a split private key system she has D.sub.aa. The computer challenges her to sign a new random challenge R. She signs the challenge, or in the split private key system she interacts with the security server to create the signature, and sends it back to the computer which uses her public key, retrieved from a certificate, to verify the signature. Observe that the computer does not have to know her private key, and that an eavesdropper observing the signature on R gains no knowledge of her private key.

The SSL system, which is widely used on the Internet, in effect implements a more elaborate method of exactly this protocol. SSL has two components, `server side SSL` in which a server proves its identity by correctly decrypting a particular message during connection set-up. As browsers such as Netscape and Microsoft Internet Explorer come loaded with the public keys of various CAs, the browser can verify the certificate of the server and use the public key therein for encryption This authenticates the server to the client, and also allows for the set-up of a session key K, which is used to encrypt and MAC all further communications. Server side SSL is widely used, as the complexity of managing certificates rests with system administrators of web sites who have the technical knowledge to perform this function. The converse function in SSL, client side SSL, which lets a client authenticate herself to a server by means of a digital signature is rarely used, because although the technical mechanism is much the same, it now requires users to manage certificates and long private keys which has proven to be difficult, unless they use the split private key system. So in practice, most Internet web sites use server side SSL to authenticate themselves to the client, and to obtain a secure channel, and from then on use Userid, Password pairs to authenticate the client.

So far from disappearing, the use of passwords has increased dramatically. Passwords themselves are often dubbed as inherently "weak" which is inaccurate, because if they are used carefully passwords can actually achieve "strong" security. As discussed earlier passwords should not be sent over networks, and if possible should not be stored on the receiving computer. Instead, in a "strong" system, the user can be asked to prove knowledge of the password without actually revealing the password. And perhaps most critically passwords should not be vulnerable to dictionary attacks.

Introduced above, dictionary attacks can be classified into three types. In all three types the starting point is a `dictionary` of likely passwords. Unless the system incorporates checks to prevent it, users tend to pick poor passwords, and compilations of lists of widely used poor passwords are widely available.

On line dictionary attack: Here the attacker types in a guess at the password from the dictionary. If the attacker is granted access to the computer they know the guess was correct. These attacks are normally prevented by locking the user account if there are an excessive number of wrong tries. Note that this very commonly used defense prevented one problem, but just created another one. An attacker can systematically go through and lock out the accounts of hundreds or thousands users. Although the attacker did not gain access, now legitimate users cannot access their own accounts either, creating a denial of service problem.

Encrypt dictionary attacks: If somewhere in the operation of the system a ciphertext C=Encrypt(M,P) was created, and the attacker has access to both C and M, then the attacker can compute off-line C1=Encrypt(M,G1), C2=Encrypt(M,G2), . . . where G1, G2, . . . etc. are the guesses at the password P from the dictionary. The attacker stops when he finds a Cn=C, and knows that Gn=P. Observe that the UNIX file system, which uses a one way function F( ) instead of an encryption function E( ), is vulnerable to this attack.

Decrypt dictionary attacks: Here the attacker, does not know M, and only sees the ciphertext C (where C=Encrypt(M,P)). The system is only vulnerable to this attack if it is true that M has some predictable structure. So the attacker tries M1=Decrypt(C,G1), M2=Decrypt(C,G2) . . . , and stops when the Mi has the structure he is looking for. For instance Mi could be known to be a timestamp, English text, or a number with special properties such as a prime, or a composite number with no small factors. Those with ordinary skill in the art will recognize there are numerous variations of the encrypt and decrypt dictionary attacks.

In split private key systems the user portion of the private key, referred to as D.sub.aa above, may come from the user's password only. Thus, a compromise of the password, i.e, another person learning a user's password, results in a compromise of the split private key system. Also, there still remains the possibility of a dictionary attack on the server portion of the private key, referred to as D.sub.as above, because the user portion of the private key comes from the user's password only. Thereby knowledge of D.sub.as enables a dictionary attack on Daa. Further, and as discussed above, existing multiple factor systems that overcome these problems rely upon expensive hardware. Because of this and other reasons, such systems have failed to gain support. Thus, there remains a need for a multifactor cryptographic system which overcomes the problems of the prior art.

OBJECTIVES OF THE INVENTION

It is an object of the present invention to provide a cryptosystem which overcomes the deficiencies of existing cryptosystems. Additional objects, advantages, novel features of the present invention will become apparent to those skilled in the art from this disclosure, including the following detailed description, as well as by practice of the invention. While the invention is described below with reference to preferred embodiment(s), it should be understood that the invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional implementations, modifications, and embodiments, as well as other fields of use, which are within the scope of the invention as disclosed and claimed herein and with respect to which the invention could be of significant utility.

SUMMARY DISCLOSURE OF THE INVENTION

In accordance with the present invention, a method and a system for user authentication based upon an asymmetric key pair having a public key and split private key are provided. The split private key includes at least a first private portion and another private portion. As desired, the asymmetric crypto-key may include even more private portions. Each of the private portions are applied to an original message to form a transformed message, and the public portion is applied to the transformed message to verify authenticity of the message preferably by recovering the original message, which authenticates the user. The use of asymmetric crypto-keys is well understood by those skilled in the art.

The system includes a first network station and a second network station. A network station can be any type computing device capable of functioning as described herein, including, but not limited to, a personal computer, a mainframe computer, a server computer, a PDA, a mobile phone, or a set top box.

A first portion of the split private key is generated based upon multiple factors. Each of these multiple factors are under control of a user associated with the asymmetric key pair. One of the multiple factors is a user's password. Thus, the user has possession of, or free access to, each of the multiple factors. A factor could be as simple as a readily available number string, such as a serial number of a user's computer, or could be a sophisticated algorithm, such as a cryptographic key. These factors are used to generate this first portion.

A challenge is then cryptographically combined with a first one of the multiple factors, forming a first message. This first factor is a factor other than the user's password. Typically, a challenge is a text string, though it could be more sophisticated, as desired. A cryptographic combination can include one or more cryptographic operations. As will be recognized by one of ordinary skill in the art, a cryptographic combination is more than a simple concatenation of the challenge and the first factor. Rather, one, or both, of the challenge and the first factor are transformed due to the cryptographic combination.

This first message is then transformed with the generated first portion of the split private key to form a second message. Thus, the first portion is applied to the first message to cause the first message to change form. This second message is then transmitted to an authentication entity, which could be any type entity seeking to authenticate the user.

The transmitted second message is then transformed to authenticate the user. This transformation provides a direct verification of user control of the first factor. That is, this transformation verifies that the user actually performed a transformation utilizing the first factor. Because of the direct verification, the user's authenticity can be relied upon.

In another aspect of the present invention, the transformation of the transmitted second message provides not only direct verification of user control of the first factor, but indirect verification of user control of the password. An indirect verification means that while the transformation does not prove that the user performed a transformation using the password, it does prove that the user performed a transformation using an element that is based at least in part upon the password.

In a further aspect, the transformation of the second message includes applying a second portion of the split private key and the public key of the asymmetric key pair to the second message. This results in the first message being recovered. This recovery is what provides the indirect verification of use control of the password.

In yet another aspect of the present invention, forming the first message includes cryptographically combining the challenge with each of the multiple factors other than the user password. Because of the multiple combinations, the transformation of the second message provides direct verification of user control of each of the multiple factors that are combined with the challenge.

In a further aspect, there are only three multiple factors, the password, and two private keys. It will be apparent that the private keys are different than the split private key being generated. Thus, a private portion of one asymmetric key is generated based at least in part upon the private keys of two other asymmetric crypto-keys. In this further aspect, the first message is formed using a hash function, such as, but not limited to, the well known SHA-1 hash function, and the well known process of cryptographically signing with an entire private key of an asymmetric key pair. More particularly, this aspect includes cryptographically signing a first hash of the challenge with the first entire private key, cryptographically singing a second hash of the challenge with the second entire private key, and combining the cryptographically signed first and second hashes with the challenge.

In an even further aspect, a first public key associated with the second asymmetric key pair is applied to the signed first hash to recover the challenge to provide direct verification of user control of the first entire private key, and a second public key associated with the third asymmetric key pair is applied to the signed second hash to recover the challenge to provide direct verification of user control of the second entire private key.

According to one aspect of the present invention, the challenge is received from the authentication entity. The cryptographic combination with the first factor is performed after the challenge is received. In another aspect, the generated first portion is destroyed after it is used in transforming the first message. Thus, in order to use the first portion to transform another message, it must be generated again. And, in yet another aspect of the present invention, the password is not stored in a persistent state. Thus, each time the password is needed, it must be supplied by the user.

BRIEF DESCRIPTION OF DRAWINGS

FIG. 1 depicts an exemplary network of the present invention, including networked devices associated with a user, a sponsor, a merchant, and an optional distinguished server.

FIG. 2 depicts a computer suitable for use by a user to access a network in accordance with the invention.

FIG. 3 is an exemplary block diagram of components of the computer depicted in FIG. 2.

FIG. 4 depicts a server suitable for use by the sponsor station, optional distinguished entities, and merchants in accordance with the present invention.

FIG. 5 is an exemplary block diagram of components of the server depicted in FIG. 4.

FIGS. 6a-6c is a flow chart showing operations which are performed by a user a optional distinguished server and sponsor station in associating a multifactor asymmetric key pair with the user in accordance with certain aspects of the present invention.

FIGS. 7a-7b is a flow chart showing operations which are performed by a user device and merchant server for a user to authenticate himself or herself to a server in accordance with certain aspects of the present invention.

FIGS. 8a-8c is a flow chart showing operations which are performed by a user device and the sponsor station for a user to log himself or herself onto a server in accordance with certain other aspects of the present invention.

FIGS. 9a-9b is a flow chart showing operations which are performed by a user device and the sponsor station for a user to authenticate himself or herself subsequent to logging on in accordance with certain aspects of the present invention.

BEST MODE FOR CARRYING OUT THE INVENTION

FIG. 1 illustrates a network 10, which could be the Internet. As shown, the network 10 is an interconnection of networked devices in communication with each other. These networked devices include networked devices 30-33 associated with individual network users, networked devices 40-41 associated with merchant network users, a sponsor station 50 associated with a sponsor, and optional networked devices 60-62 associated with entities known to and trusted by the sponsor.

Networked devices 30-33 will be referred to as user devices. These network devices are typically personal computers, but could be other type network devices. Networked devices 40-41 will be referred to as merchant servers. It should be understood that merchant servers 40-41 could be associated with any type entity having a presence on network 10. Optional networked devices 60-62 will be referred to as distinguished servers. It will be understood that a network may consist of more networked devices than depicted in FIG. 1.

FIGS. 2 and 3 depict an exemplary personal computer (PC) suitable for use by an individual user as a user device 30-33 to access the network 10. The PC is preferably a commercially available personal computer. It will be recognized that the PC configuration is exemplary in that other components (not shown) could be added or substituted for those depicted, and certain of the depicted components could be eliminated if desired. Further, a user device 30-33 could be another type device other than a `computer`, such as, but not limited to, a PDA or a mobile phone.

The computer functions in accordance with stored programming instructions which drive its operation. Preferably, the computer stores its programming instructions on an EPROM, or hard disk. It will be recognized that only routine programming is required to implement the instructions required to drive the computer to operate in accordance with the invention, as described below. Further, since the computer components and configuration are conventional, routine operations performed by depicted components will generally not be described, such operations being well understood in the art.

Referring to FIG. 2, the computer 1000 includes a main unit 1010 with slots 1011,1012, and 1013, respectively provided for loading programming or data from floppy disk, compact disk (CD), or other removable media, onto the computer 1000. The computer 1000 also includes a keyboard 1030 and mouse 1040 which serve as user input devices. A display monitor 1020 is also provided to visually communicate information to the user.

As depicted in FIG. 3, the computer 1000 has a main processor 1100 which is interconnected via bus 1110 with various remote or local storage devices which may include, but are not limited to, EPROM 1122, RAM 1123, hard drive 1124, which has an associated hard disk 1125, CD drive 1126, which has an associated CD 1127, floppy drive 1128, which has an associated floppy disk 1129, USB port 1195 for connecting a USB drive 1196 (often called a flash drive), smart card reader 1197 for communicating with a smart card 1198. Also shown in FIG. 3 is a trusted processing module (TPM) 1199 for securely storing cryptographic keys. Taken together, the remote and local storage will be referred to collectively as 1170. A drive controller 1150 controls the hard drive 1124, CD drive 1126 and floppy drive 1128. Also depicted in FIG. 3 is a display controller 1120 interconnected to display interface 1121, a keyboard controller 1130 interconnected to keyboard interface 1131, a mouse controller 1140 interconnected to mouse interface 1141 and a modem 1160 interconnected to I/O port 1165, all of which are connected to the bus 1110. The modem 1160 and interconnected I/O port 1165 are used to transmit and receive signals via the network 10 as described below. It will be understood that other components may be connected if desired to the bus 1110, or that less than all the components shown in FIG. 3 May be connected to the bus 1110. By accessing the stored computer programming, the processor 1100 is driven to operate in accordance with the present invention.

The sponsor station 50, the merchant users and the optional distinguished entities are preferably represented on network 10 by an Internet server of the applicable type shown in FIGS. 4 and 5, as will be described further below. However, here again, any network compatible device which is capable of functioning in the described manner could be substituted for the servers shown in FIGS. 4 and 5.

FIGS. 4 and 5 depict an exemplary network server suitable for use by the sponsor, merchants, and optional distinguished entities to access the network 10 in the below-described invention. The server is preferably a commercially available high power, mini-computer or mainframe computer. Here again, it will be recognized that the server configuration is exemplary in that other components (not shown) could be added or substituted for those depicted and certain of the depicted components could be eliminated if desired.

The server functions as described below in accordance with stored programming instructions which drive its operation. Preferably, the server stores its unique programming instructions on an EPROM or hard disk. It will be recognized that only routine programming is required to implement the instructions required to drive the server to operate in accordance with the invention, as described below. Further, since the server components and configuration are conventional, routine operations performed by depicted components will generally not be described, such operations being well understood in the art.

Referring to FIG. 4, the server 1000' includes a main unit 1010' with slots 1011', 1012', 1013' and 1014', respectively provided for loading programming or data from a floppy disk, CD and/or hard disk onto the server 1000'. The server 1000' also includes a keyboard 1030' and mouse 1040', which serve as user input devices. A display monitor 1020' is also provided to visually communicate information to the user.

As depicted in FIG. 5, the server 1000' has a main processor 1100' which is interconnected via bus 1110' with various storage devices including EPROM 1122', RAM 1123', hard drive 1124', which has an associated hard disk 1125', CD drive 1126', which has an associated CD 1127', and floppy drive 1128', which has an associated floppy disk 1129'. The memories, disks and CD all serve as storage media on which computer programming or data can be stored for access by the processor 1100'. The stored data includes one or more databases containing information associated with network users. The memories associated with a server hereafter will be collectively referred to as memory 1170'. A drive controller 1150' controls the hard drive 1124', CD drive 1126' and floppy drive 1128'. Also depicted in FIG. 11B is a display controller 1120' interconnected to display interface 1121', a keyboard controller 1130' interconnected to keyboard interface 1130', a mouse controller 1140' interconnected to mouse interface 1141' and a modem 1160' interconnected to I/O port 1165', all of which are connected to the bus 1110'. The modem 1160' and interconnected I/O port 1165' are used to transmit and receive signals via the network 10 as described above. It will be understood that other components may be connected if desired to the bus 1110'. By accessing the stored computer programming, the processor 1100' is driven to operate in accordance with the present invention.

Multifactor Asymmetric Crypto-Key

A multifactor asymmetric crypto-key is associated with at least each individual network user, and, if present, each optional distinguished server 60-62. If desired, a multifactor asymmetric crypto-key can also be associated with each merchant user. Each multifactor asymmetric crypto-key consists of two portions, a public portion and a private portion. The public portion is referred to as E, and the private portion is referred to as D. The public portion of each multifactor asymmetric crypto-key is known to at least each merchant user. If desired, the public portion of each multifactor asymmetric crypto-key can also be known to each individual user. Each of these public portions can be stored on each merchant server, or on each merchant server and each individual device, in association with a user id. Additionally, each E, or less than each E, can be stored at sponsor station 50. The private portion of each asymmetric crypto-key consists of at least a first private portion having multiple factors and a second private portion. The second private portion of each multifactor asymmetric crypto-key is retained by the sponsor station 50 and will be referred to as D.sub.2. The first private portion of each multifactor asymmetric crypto-key will be referred to as D.sub.1 and will be further discussed below.

The multifactor asymmetric crypto-keys are used in transforming information. Preferably, the multifactor asymmetric crypto-keys are used in providing trusted authentication of an individual user to a merchant user. Also, the multifactor asymmetric crypto-keys can be used in providing trusted authentication of an individual user to another individual user, or of a merchant user to another merchant user. Further the multifactor asymmetric crypto-keys can be used to decrypt data encrypted with the public key. More generally, some subset of the multifactor asymmetric crypto-keys can be used to sign (or likewise decrypt) a message and the signature verified (likewise message encrypted) by the remaining crypto-keys.

In accordance with the present invention D.sub.1 is made up of at least two, and perhaps additional, factors. One factor which is preferably always present is a user's password. Another factor will be either a private key stored on a user device 30-33, or a private key stored elsewhere. Of course, both, instead of one, of the other factors could be utilized with the user password, as will be discussed in detail below. Sometimes a private key stored on a user device 30-33 will be referred to as D.sub.tether or a tether key, and a private key stored elsewhere will be referred to as D.sub.USB.

Typically, the password will not be stored in any form, as preferably a password is short, and thus relatively easy for a user to memorize. However, as desired, a password could be stored on a user device 30-33, or even elsewhere. Introduced above, D.sub.tether, when present, is stored on the user's device. In the most common implementation, D.sub.tether is stored securely on the hard disk 1125 using the protection capabilities provided by the PC's operating system, preferably as a non-exportable private key in a Windows Operating System key-store. Of course, as desired, D.sub.tether could be stored in a Windows Operating System registry. Alternatively, D.sub.tether can be, as desired, stored on the trusted processing module (TPM) 1199. No matter where or how on the user device 30-33 D.sub.tether is stored, in the most basic configuration, D.sub.tether can only be used from the user device 30-33 upon which it is stored. That is, D.sub.tether is a non-exportable private key stored on the user device upon which it will be used. However, as will be discussed in detail further below, D.sub.tether may be ported to other devices and used thereon.

Introduced above, D.sub.USB is not stored on the user device. D.sub.USB is stored on removable media such as, but not limited to, a USB drive (flash drive), a floppy disk, or a CD. Preferably D.sub.USB is stored on a USB flash drive. As desired D.sub.USB may be encrypted. Preferably, such an encryption is not performed with the user's password. However, D.sub.USB could be, as desired, encrypted with D.sub.tether. In addition to the removable media described above, D.sub.USB can be, as desired, stored on a smart card, which is a more sophisticated form of removable memory which typically includes separate processing electronics.

Key Generation

In one preferred implementation of key generation the sponsor station 50 drives the association between users and multifactor asymmetric crypto-keys. Preferably, for a user to obtain an association with a multifactor asymmetric crypto-key, the user must have a relationship with an entity associated with an optional distinguished server 60-62 and only those users referred to the sponsor 50 by an optional distinguished server 60-62 are eligible to participate in network 10. However, as desired, distinguished servers 60-62 may not be included in the network 10. In such a case, some or all of the functions performed by an optional distinguished server 60-62, including those described herein, could be performed by sponsor 50, and/or some or all of the functions performed by an optional distinguished server 60-62 might not be performed.

For the sake of discussion below, it is assumed that one or more optional distinguished servers 60-62 are included in network 10. If an individual user associated with user device 31 wishes to obtain an association with a multifactor asymmetric crypto-key, yet does not have a preexisting relationship with any distinguished server 60-62, that user may choose to contact distinguished server 60 via the network 10 and provide identity information to the distinguished server 60. In this case, the distinguished server 60 has the capabilities to verify identity information. This capability may be any well known method of verifying identify information, such as a database of credit information, a database of telephone account information, or a database of address information. If the distinguished server 60 verifies the provided information, the distinguished server 60 can refer the user to the sponsor station 50.

If an individual user associated with user device 33 wishes to obtain an association with a multifactor asymmetric crypto-key and has a relationship with the distinguished server 61, the individual user must request that the distinguished server 61 initiate the process of associating an asymmetric crypto-key with the individual user. Operations as described below and depicted in FIGS. 6a-6c will be performed.

As shown in step 601 of FIG. 6a, a distinguished server 60-62, in this instance distinguished server 62, logs in with the sponsor station 50. Then, the distinguished server 62 transmits to the sponsor station 50 information identifying a new user with whom a multifactor asymmetric crypto-key will be associated, in this instance the individual user associated with user device 33, step 605. The sponsor 50 then generates a symmetric key pair and a user ID which will be associated with the new user, step 610. This symmetric key pair will serve as a one time activation code. Preferably, the symmetric key/one time activation code is a short pronounceable word. This symmetric key/one time activation code and user ID is stored in the memory 1170' and is also transmitted to the distinguished server 62, step 615. The distinguished server 62 then causes the symmetric key/one time activation code and user ID to be delivered to the new user. This delivery may be via traditional postal delivery, via e-mail, or via other electronic delivery, such as via a web-page, step 617. Preferably electronic or hard-copy delivery will be secured using techniques familiar to those skilled in the art.

The new user, after receiving the user ID and symmetric key/one time activation code, establishes a communication session with the sponsor 50 via network 10, step 620. The new user enters the user ID into his or her user device and transmits the same to the sponsor station 50 via the network 10, step 625. The sponsor 50 matches the received user ID with the user ID and symmetric key stored in memory 1170', step 630.

If the received user ID has a match stored in memory 1170', the sponsor 50 generates a challenge and encrypts the challenge with the symmetric key/one time activation code, step 635. The sponsor 50 transmits the encrypted challenge to the user device 33, step 638. The user device 33 decrypts the challenge using the new user's symmetric key/one time activation code, step 640. At step 645, the user device 33 transmits either the decrypted challenge, or proof of possession thereof, to sponsor 50 to authenticate the user to the sponsor. At this point, the user is eligible to be associated with a multifactor asymmetric crypto-key.

In an alternative embodiment, the sponsor station 50 and an optional distinguished server 60-62 do not participate in key generation. Rather, key generation is between a user device 30-33