Method and apparatus for secure distribution of authentication credentials to roaming users

Background of the Invention

In networked computer deployments, users of client computers are required to authenticate themselves to server computers for applications such as electronic mail, accessing privileged or confidential information, purchasing goods or services, and many other electronic commerce transactions When the information involved is of relatively low value, it may be sufficient for the user to authenticate himself with a simple password. However, when the information is of high value, or when the data network is unsecured, simple passwords are insufficient to control access effectively For example, when computers are accessed across the Internet, passwords are easy to capture by filtering packets as they traverse the network. Alternatively, passwords can be guessed or “cracked” by intelligent trials, since passwords are often six or fewer characters. In brief, the convenience of passwords makes them easy to break — if they are sufficiently easy for the user to remember, they are sufficiently easy for the hacker to guess

To overcome the insecurity of the password, alternative technologies have been developed. One such technology is asymmetric key cryptography In this technology, each user has two keys, a private key and a public key The user performs a cryptographic operation (e.g., an encryption or a digital signature) on a digital quantity using his private key, such that the quantity may be authenticated by a verifier having access only to the user's public key. The private key therefore serves as the user’s authentication credential. That is, the verifier need not know the user's private key in order to authenticate the user. Because the public key may be widely disseminated while the private key remains confidential, strong authentication is provided with enhanced security. Private keys are generally too long and complex for the user to memorize, and are therefore usually stored in software or hardware tokens, and interfaced with computers prior to use.

One such software token is the so-called software wallet, m which the private key is encrypted with a password or other access-controlled datum In such software wallets, an intruder is not deterred from repeatedly trying passwords, in an exhaustive manner, until he

WO 00/30285

PCT/US99/27621 recovers the private key. This poses analogous security risks to the simple password schemes descnbed above. In addition, the software wallet is stored on a user's computer, which may be inconvenient if the user needs to freely roam from one location to another.

In contrast to software wallets, hardware tokens such as smart cards are more secure, and can be conveniently earned as the user roams. In a typical hardware smart card, the private key is stored in hardware, and protected by a watchdog chip that allows the user to access the pnvate key, should he enter the correct password that unlocks the smart card. The smart card can even be configured so that, if a hacker attempts to guess passwords, the card locks up after a small number of successive missed attempts. The disadvantages of hardware token are^- (1) roaming is restneted to locations where the appropnate token reader hardware is installed; (2) hardware tokens are expensive in contrast to software tokens; (3) hardware tokens must be physically earned wherever the user wishes to roam; and (4) hardware tokens are often lost, misplaced, or stolen

Thus, while hardware token systems offer increased secunty, they have several disadvantages compared to software based systems It would, therefore, be desirable to have a system that combines the best features of both hardware and software based systems.

Summary of the Invention

The present invention discloses a method and apparatus for the on-demand delivery of authentication credentials to roaming users Credentials are stored, delivered and transmitted in software, obviating the need for additional hardware. In a basic embodiment of the system, a user can demand his credential at will, upon providing proof of identity in the form of shared secret(s) that he has previously escrowed with the credential server. The shared secret may be chosen by the user, and could be easily remembered secrets such as: mother’s maiden name, third grade teacher, etc. The user will respond to challenges from the server via a challenge-response protocol, with the server demanding correct answers to such questions prior to releasing the user’s credentials. In another embodiment of the invention, a user's authentication credential can be stored on the server protected by a simple shared secret scheme such as a password, a biometric authentication scheme based on a fingerprint or retinal image, or a one-to-one hashed shared secret. In yet another embodiment of the invention, the user interacts with the server via a cryptographically camouflaged challengeresponse protocol. In particular, if the user responds correctly to the server’s challenges, the user will receive his authentication credentials. However, if the user responds incorrectly, such as might be the case with a hacker trying to break the system, the user will receive

WO 00/30285

PCT/US99/27621 plausible and well-formed but invalid credentials. Furthermore, the authentication credential itself could be encrypted or camouflaged with an additional secret that is known only to the user. An authentication credential is said to be in cryptographically camouflaged form when it is embedded among many pieces of similar (pseudo-valid) data. These data are sufficiently different that the user can locate the correct piece without any difficulty, using a shared secret that he can remember. However, the pieces of data are also sufficiently alike that an intruder will find all of them equally plausible. Such a cryptographically camouflaged authentication credential can be provided to the user in either camouflaged or decamouflaged form that is, the decamouflaging can be performed at either the credential server or at the user's computer. The various embodiments of the invention described above provide one or more or the following advantages:

No additional hardware is required for deployment. This is in contrast with hardware tokens such as smart cards where cards and card readers need to deployed in a widespread fashion.

(1) High user convenience. Roaming users need not carry tokens with them, but can demand them as required.

(2) Low administrative overhead. Users who have lost, misplaced or forgotten tokens do not require administrative intervention.

(3) Rapid deployment rate. Soft credentials with roaming access can be deployed rapidly, since they are intuitive to use and require little user/administrator training.

(4) Enhanced security over purely one-factor systems.

Brief Description of the Figures

Figure 1 illustrates an exemplary embodiment of the invention m which a user accesses a web server to conduct an electronic transaction with a transaction server protected by an access control server.

Figure 2 illustrates an exemplary embodiment of a wallet in which a private key is protected by a PIN.

Figure 3 illustrates an exemplary embodiment in which the wallet of Figure 2 is protected by a form of cryptographic camouflaging.

Detailed Description of the Invention

We now describe various exemplary embodiments of the invention using the exemplary context of a user operating a web browser to access one or more remote server, whereby the user can freely roam about the Internet while still maintaining access to his

WO 00/30285

PCT/US99/27621 authentication credential. Those skilled in the art will recognize that the invention is applicable to other client-server environments as well, including but not limited to databases, medical client stations, and financial trading stations. Furthermore, the network environment need not be the Internet, but could be an intranet or indeed any distributed computer network.

Referring now to Figure 1, a user at Browser 140 wishes to access a Web Server 110 to conduct an electronic transaction Web Server 110 is, in turn, safeguarded by Access Control Server 120, which prevents unauthorized access to Transaction Server 130. For example, Web Server 110 might be a company's home page, Access Control Server 120 might be a firewall, and Transaction Server 130 might contain proprietary company data that the user wishes to access. In yet another example, Access Control Server 120 might be a membership or credit/payment verification system, and Transaction Server 130 might be a back-end shipping/dehvery system. Those skilled m the art will appreciate that any or all of servers 110, 120 and 130 may be combined into a single server, that there may be more additional servers performing other specialized functions, that any of these servers may be co-located or widely distributed, and so forth. Similarly, the electronic transaction may be of virtually any type including, but not limited to, secure electronic mail, accessing privileged or confidential information, and purchasing electronic or physical goods or services.

Before accessing the Transaction Server 130 to perform the electronic transaction, the user first needs to authenticate himself to Access Control Server 120. As mentioned in the Background of the Invention, the user typically authenticates himself by using his private key to perform a cryptographic operation on a challenge sent by the Access Control Server 120. This cryptographic operation might be a simple encryption, a hash followed by encryption (commonly referred to as a digital signature), or still other protocols that are well known to those skilled in the art. Of course, in lower security applications, the authentication credential might be a simple password. Private key, password and other authentication credentials are well known to those skilled in the art, and need not be described m detail here. For examples thereof, the reader is referred to well-known, standard texts as Applied Cryptography (Bruce Schneier, Second Edition, 1996, pp. 101-112 & 548-549) for details.

No matter what the authentication credential or protocol, if the Access Control Server 120 authenticates the user, the user is subsequently allowed to access the Transaction Server 140. The present invention provides a method and apparatus for providing the authentication credential, on demand, to a user who wishes to be able to access servers 110, 120 and/or 130 from a variety of Browsers 140 (the so-called roaming user).

WO 00/30285

PCT/US99/27621

This on-demand roaming capability is provided by a Credential Server 160 that downloads the authentication credential (e.g., private key) to the user at Browser 140 via a software Wallet 150. As used herein, Wallet 150 need only serve as a basic container for the authentication credential. As such, it could be considered to be simply the data structure in which the authentication credential is embodied, or it could be a more sophisticated container having the capability to handle other user-owned items such as a digital certificate or digital currency (including, without limitation, electronic cash or scrip). In a basic embodiment of the invention, Credential Server 160 is embodied as a web server. The user points his Browser 140 to the Credential Server, which sends the user a challenge in the form of a shared secret that has previously been associated with the user during a set-up phase. This shared secret might be of the following exemplary forms^-

<td> Question^-</td><td> Mother’s maiden name⁹</td><td> Answer:</td><td> Jones</td>

<td> Question.</td><td> Dog’s name⁹</td><td> Answer</td><td> Lucky</td>

<td> Question:</td><td> Favorite sport⁹</td><td> Answer-</td><td> Football</td>

<td> Question.</td><td> PIN?</td><td> Answer^-</td><td> PIN</td>

The actual number of questions can vary from credential server to credential server, as dictated by their respective security policies If the user provides the correct answer(s), the Credential Server 160 obtains the user's wallet from a Wallet Database 170 (which may or may not be part of Credential Server 160) and provides the wallet to the user at Browser 140. In an alternative embodiment, the wallet, or a part thereof, could be provided directly to any of servers 110, 120 &amp; 130

In either of the foregoing, the wallet could be installed either^- 1) m the memory space of the software program, and/or subsequently 2) onto the hard drive or other physical memory of the computer If only the former, the authentication credential would be destroyed when the session is ended. If the latter, the authentication credential could be available for use across multiple sessions on that particular computer. In either event, as the user roams to another computer, the process can be repeated to provide on-demand access to the needed authentication credential without the requirement of a physical token (even though the invention could also be used in conjunction with a physical token, as desired).

The foregoing illustrates the use of so-called shared secrets, whereby the user and the server both share copies of information required to access the system. Of course, the invention is not limited to such simple protocols which, by their nature, are subject to abuse by a dishonest server. For example, zero knowledge proofs, whereby the user can prove to the server that he knows his mother’s maiden name (or other secret information) without

PCT/US99/27621

WO 00/30285 actually revealing the name to the server, can also be used. As a simple example, the user's private key itself could be used in this fashion, for a verifier need only know the corresponding public key to verify the pnvate key. The principles and implementations of zero knowledge proofs are well known to those skilled in the art and need not be described here. The reader is referred to well-known, standard texts such as Applied Cryptography, supra, for details.

In one embodiment of the invention, the wallet might itself be protected by a shared secret. For example, Figure 2 shows an exemplary embodiment of a wallet in which a pnvate key is protected by a PIN The PIN (more generally, a shared secret) might be the shared secret transmitted by the user to the Credential Server 160, as discussed previously, and the private key (more generally, the authentication credential) m the wallet might be decrypted by Credential Server 160 and provided in the clear to the user at Browser 140. Alternatively, the entire wallet (including the authentication credential in encrypted form) might be provided to the user, for the user to decrypt locally at Browser 140. With either approach, the process of decrypting the PIN-protected authentication credential as follows. The user enters a PIN 200 (more generally, an access code) to unlock the wallet, and the PIN is passed through a one-to-one hash function 210. The hash function may also include a salt value or other security-enhancing feature, as will be appreciated by persons skilled in the art. The hashed value 215 of the entered PIN is compared with a stored hash value 220, which is the hashed value of the correct PIN. If the two hash values agree, the PIN is passed to decryption module 240. The pnvate key which has been encrypted (with the correct PIN as the encryption key) and stored in field 230, is decrypted by decryption module 240, which is typically DES or some other cryptographic function such as, for example, tnple-DES, IDEA or BLOWFISH. Hence, the decrypted private key 250 is released for use.

The cryptographic operations of computing the hash(es) and decrypting the stored hash may be implemented using one or more cryptographic logic (e g., software or hardware) modules, and the correct hash value and private key may be stored m protected data fields or other forms of memory (e.g., read from ROM, from computer-readable media, etc.). A typical key wallet would also include input and output logic for receiving candidate PINs and outputting decrypted private keys, as well as logic for management, viewing, copying, and handling of keys and other data.

The one-to-one nature of the hash function ensures that the correct PIN and only the correct PIN will unlock the key wallet. Unfortunately, it also allows a malicious hacker to guess the complete PIN via a brute force search. For example, he might write a program that

PCT/US99/27621

WO 00/30285 simply checks all six-digit PIN codes on the key wallet. If he gets a copy of the key wallet, he can carry out this attack on his computer, completely undetected and in an automated fashion, in a matter of a few minutes.

To resist the PIN hash attack, another embodiment of the invention uses a technique called cryptographic camouflaging to provide even greater security in connection with the authentication credential Cryptographic camouflaging is descnbed is summary form below with respect to Figure 3; for full details, the reader may refer to co-pending U.S. patent application no. 08/996,758, which is incorporated herein by reference.

Referring now to Figure 3, the authentication credential (e.g., private key) is protected via an access code as in Figure 2. However, the one-to-one hash is replaced with a many-toone hash, i.e., a hash in which many inputs produce (i.e., regenerate) the same hashed output. In an exemplary implementation, the many-to-one hash function 310 might hash six-digit codes to two-digit hash values. As m the conventional key wallet, the hashed value 315 of the entered PIN 300 is compared with the stored hash value 320, which is the hashed value of the correct PIN. If the two hash values agree, the key wallet opens. The private key is again stored encrypted in field 330 of the key wallet, with the correct PIN as the encryption key. When the correct PIN is entered, the stored encrypted key is decrypted and the correct private key 350 is released for use. However, since the hash function is many-to-one, there will be many different entered PINs that will satisfy the hash challenge to open the key wallet. (PINs that hash to the same hash value as the correct PIN, including the correct PIN, are referred to herein as pseudo-valid PINs.) For example, if the hash function hashes six-digit codes to two-digit hash values, there will be 10,000 six-digit pseudo-valid PINs that will open the key wallet, out of a total of 1,000,000 possible six-digit codes Pseudo-valid PINs will all be passed to the decryption module 340 to decrypt the stored encrypted key to produce a candidate private key. However, all but one of these candidate private keys will be incorrect decryptions of the stored (correct) private key. Only when the entered PIN is the correct PIN will the correct private key be recovered.

Preferably, the many-to-one hash function above should be chosen to be a good hash. For example, and without limitation, MD5 and SHA are well-known good hash functions Good hash functions are one means to substantially uniformly distribute the pseudo-valid PINs in the space of all possible PINs For example, consider a hash function from six-digit codes to two-digit hash values. Of the 1,000,000 possible input values, 10,000 will be pseudo-valid PINs. If the hash function is a good hash, these values will be substantially uniformly distributed In particular, one in a hundred PINs will be pseudo-valid, and these

WO 00/30285

PCT/US99/27621 will be effectively randomly distributed. Specifically, the chances are 1/100 that if the user makes a typographical error in entering the correct PIN, then the resulting PIN will be a pseudo-valid PIN.

Another possible embodiment uses a weak hash, i e., one which results in clustering of pseudo-valid PINs, whereby an intruder who guesses one pseudo-valid PIN will more easily find others. A legitimate user making a series of 1-digit typographical errors would also get a sequence of pseudo-valid PINs and, if the system accepting the private key or messages encrypted thereby has an alarm-or-disable-upon-repeated-failure feature, this would inadvertently lock out the legitimate user. Thus a weak hash is typically disfavored over the good hash. Nevertheless, there may be some applications where a weak hash provides certain characteristics such as computational efficiency and ease of implementation that are advantageous for specialized applications.

The foregoing paragraphs describes techniques for further protecting the wallet, either with a one-to-one or many-to-one hash. It will be appreciated by those skilled in the art that the decryption processes 200-250 and 300-350 (e.g, cryptographic decamouflaging) may be performed at either the user's computer or at the Credential Server 160. In the former case, the wallet is downloaded to the user in decrypted form, while in the latter, the wallet is decrypted at the Credential Server 160 before downloading to the user.

More generally, it will also be appreciated that the various challenge-response protocols described to this point (e.g., the simple shared secret; the biometric method such as fingerprint recognition; the one-to-one hashed secret of Figure 2; and the many-to-one hashed secret of Figure 3) can be used at either the Credential Server 160 or at Browser 140, and that such use can occur m any combination or permutation. For example, with minimal secunty, the Credential Server 160 could be accessed by a simple shared secret, and the wallet could be downloaded to the user in the clear Alternatively, the wallet could be further protected by a one-to-one or many-to-one (i.e., cryptographically camouflaged) hashed shared secret and decrypted at the Credential Server m response to the user's responding to the appropriate challenge-response protocol. The decrypted (or, m the case of the many-to-one hash, the decamouflaged) wallet would then be downloaded to the user in the clear. For greater secunty, the wallet could be downloaded to the user in camouflaged form, with the decamouflaging occurring at the user's computer. For still greater secunty, a one-to-one or many-to-one hash process could replace the simple shared secret for the initial server access. In general, then, the one-to-one hash or many-to-one hash could be deployed at the initial server access stage, while any of the simple shared secret, one-to-one hash, many-to-one hash

WO 00/30285

PCT/US99/27621 techniques could be employed at the subsequent wallet downloading stage. Because of these and other variations that will be understood to those skilled m the art, it is therefore intended that the scope of the invention be not limited to the particular embodiments disclosed herein, but rather to the full breadth of the claims appended hereto.

<img file="NZ511397A_D0001.tif" />

WO 00/30285

PCT/US99/27621