Derivative seeds

0001This application claims the benefit of <patcit id="pcit0001" dnum="US65410805P" dnum-type="L"><text>U.S. Provisional Application Nos. 60/654,108, filed February 18, 2005</text></patcit>, and <patcit id="pcit0002" dnum="US60668680B" dnum-type="L"><text>60/668,680, filed April 6, 2005</text></patcit>.

<u>Technical Field</u>

0002This invention relates to the field of computer-based security systems and, more particularly, to the distribution of authentication secrets.

<u>Background of the Invention</u>

0003In security systems, verifiers are used to authenticate, that is to verify the identity of, a person or other entity such as a computer. Typically an entity requesting authentication asserts their identity to the verifier, for example by entering a user ID. The entity then typically supplies some additional information which should only be knowable to the valid entity. The verifier determines if the information supplied by the entity matches the information that the valid entity would supply. When an entity has been authenticated, meaning that the verifier has confirmed that the identity of the entity is as the entity claims, the entity is allowed access, for example physical access to a physical location, in the case of a physical security system, or electronic access to a resource or information (e.g. financial records, computer data, network access, etc.), in data security systems.

0004There are many possible configurations for verifiers. Verifiers can receive input from keypads, keyboards, card readers, cameras, microphones, telephone and computer networks, and other such data input devices. As output, verifiers activate physical mechanisms, send electronic data signals, configure software, or take such other action to provide access. Verifiers can be implemented in various ways, for example as special purpose electronic and/or mechanical systems, or as general-purpose computers, possibly, but not necessarily, in electrical communication with special-purpose hardware.

0005Some verifiers use knowledge or possession of a shared secret to authenticate an entity. The secret is "shared" because it is held by both the verifier and the entity being authenticated. For example, knowledge or possession of a personal identification number, password, or pass phrase can be used to verify an entity. At the time that authentication takes place, the entity either reveals the secret or otherwise proves knowledge or possession of the secret. If the entity shows knowledge or possession of the secret as required by the particular authentication system, the entity is authenticated.

0006In some systems, an entity uses a physical or digital device, referred to as a token, that incorporates a secret. The secret, stored in some manner in the device, may or may not be known to the entity using the device.

0007To prove knowledge of a secret contained within the device, some devices provide an authentication code that is based upon, but different from, the secret code contained within the device. The use of such an authentication code allows the device to show knowledge of a secret without revealing it. In some systems, the authentication code is based on time-dependent information. The use of this sort of device has security benefits in that the secret is more difficult to determine by eavesdropping in the communications channel between the entity and the verifier, since the secret itself is not revealed.

0008One example of this sort of device used by a person to authenticate to a verifier is a token that includes an authentication code display. The person reads an authentication code from the display, and transmits the authentication code to the verifier. In such a system, the user may never know the shared secret. Some such tokens accept user input, such as a PIN, and provide a result in response to the user input as well as other information (such as time-dependent information). One disadvantage with these token devices is that only one user can use the token to authenticate to the verifier. Each user must have his or her own token.

0009One token of this type stores a secret code, referred to as a seed, and mathematically combines the secret code with a time-varying value and a personal identification code provided by the user to generate an authentication code. The mathematical combination takes place in such a way that the secret code stored in the token cannot be determined from the result--the secret code is combined cryptographically with the current time and other information. In another system that is a challenge-response system, meaning that the verifier transmits a challenge for the user to respond to, the secret code is cryptographically combined with the challenge to produce an output that is sent to the verifier as a response to the challenge.

0010To verify an entity using a shared secret, the verifier needs to have knowledge of the shared secret. In a security system that verifies a large number of entities, there is a tradeoff between security and verifier availability. If there are a large number of verifiers, there is more likely to be a verifier available when a particular entity requires authentication. However, as the number of verifiers that have knowledge of a secret increases, it becomes increasingly more difficult to maintain the security of the system.

0011The utility of a security system is limited by the number and variety of verifiers to which an entity can conveniently authenticate. If the entity interacts with a number of verifiers that share different secrets with that entity, the entity will have to manage a number of secrets (or devices containing secrets), where each secret is used to authenticate to one or small number of verifiers. Managing a large number of secrets adds complexity to a computer-based entity, and is inconvenient for a human entity. Even the process of securely sharing a different secret between an entity and each of a large number of verifiers can be inconvenient and cumbersome.

0012Public key cryptography can be used to avoid the need to securely share a secret between each two parties that wish to communicate or authenticate. However, public-key cryptography is impractical in many user and device authentication settings, at least partly because of the large computation power required to accomplish the calculations, and the complexity of managing certificates and revocation lists.

<u>Summary of the Invention</u>

0013In general, the invention is a system whereby a single shared secret can be used as the basis to derive a plurality of shared secrets to be used for authentication. The process of deriving the shared secrets can occur dynamically, in some cases at the time of authentication. One particular value of this derived secret model is that a single authentication device, containing the initial shared secret can be distributed without the need for pre-computing all possible derived secret values in advance. This significantly simplifies the process of distributing and using a single authentication device in multiple environments. Another value of this system is that the initial shared secret may never be used for authentication (only for secret derivation), increasing the security of the system. Yet another value of this system is to allow a single authenticator (i.e. token) to be used by multiple parties, or used by a single party to authenticate to multiple entities, or both used by multiple parties to authenticate to multiple entities, without using a common shared secret for these authentications. In this case, all authentications will occur using a shared secret unique to each situation; where each unique shared secret is derived from the initial shared secret.

0014In one aspect, the invention features a method for generating authentication secrets (e.g. "seeds") for a plurality of client-side entities. The method involves: based on a single master seed, generating a plurality of derivative seeds, each one for a corresponding different one of a plurality of client-side entities, wherein generating each one of the plurality of derivative seeds involves mathematically combining the master seed and a unique identifier identifying the corresponding client-side entity. In certain embodiments, the invention may also be used to generate authentication seeds for a plurality of server-side entities.

0015Other embodiments include one or more of the following features. The plurality of client-side entities is a plurality of users. The method also involves distributing the plurality of derivative seeds to a verifier for use in individually authenticating each of the plurality of client-side entities to that verifier. The following is an overview of one embodiment of the method of the present invention using a derivative seed to authenticate a user to an authentication server. First, a master seed generator creates the master seed. The master seed is loaded into the authenticator which may be used by multiple users to authenticate. The authenticator may be a token implemented as a hardware device or in software. The master seed is also loaded into the derived seed generator. At some later time, typically during a registration process to enable the authentication of a particular user using the authenticator, the following steps are performed: (1) the authentication server obtains the unique identifier (UID) for the user; (2) the authentication server contacts the derived seed generator supplying the user's UID and identifies which authenticator will be used by user (e.g. by supplying the authenticator serial number); (3) the derived seed generator uses the authenticator's serial number to locate the master seed which was loaded into authenticator, and then cryptographically combines the master seed and the user UID to create the derived Seed; and (4) the derived seed is sent back to the authentication server to be used as the shared secret for subsequent authentications. The master seed generator may be logically separate from the derived seed generator, or the two generators may be implemented as a single generator that performs both functions. At some yet later time, the user will decide to access some resource protected by the authentication server and the following steps will be performed: (1) the user UID will be passed to the authenticator at the time of the authentication; (2) internally, the authenticator will cryptographically combine the previously stored master seed, with the newly supplied user UID, and thereby dynamically create the derived seed; and (3) using the derived seed, the authenticator will execute one of a number of authentication algorithms using the derived seed as the shared secret, and release the appropriate authentication code. The authentication code will then be sent to the authentication server. Since the authentication server already has a stored copy of derived seed, it can validate the authentication code.

0016A number of different users, each with their own unique UID can use the same process which will derive a derived seed unique to that combination of user and authenticator. As a result, the resulting system has a number of unique properties. First, a single master seed is the only static secret which needs to be stored in the authenticator. Second, each user will have a unique user UID and therefore a unique derived seed. Each user's unique derived seed can be created dynamically at the time of authentication, and therefore there is no need it store the derived seed for a user in the authenticator. This is valuable from both a security and a memory utilization point of view. However, the derived seed may also be precomputed and stored in the authenticator. Each unique derived seed is used to authenticate each unique user, and as a result there is no sharing of a common authentication secret; and therefore no security vulnerability introduced by secret sharing. Finally, because derived seeds can be generated dynamically at the time of authentication and are not necessarily stored in the authenticator, there is no limit to the number of users who can share a common authenticator.

0017In general, in another aspect, the invention features a method of using a single master seed to authenticate any selectable one of a plurality of client-side entities to a verifier, wherein each of the plurality of client-side entities is identified by a different unique identifier. The method involves: mathematically combining the master seed with the unique identifier for the any selectable client-side entity to generate a derivative seed for the any selectable client-side entity; and using the derivative seed that was generated for the any selectable client-side entity to authenticate the any selectable client-side entity to the verifier.

0018Other embodiments include one or more of the following features. The plurality of client-side entities is a plurality of users. Using the derivative seed for the any selectable user involves sending to the verifier a value that is computed from the derivative seed for the any selectable user. Using the derivative seed that was generated for the any selectable client-side entity to authenticate that any selectable client-side entity to the verifier involves using an authentication algorithm selected from the group consisting of a time-based authentication algorithm, a challenge-response authentication algorithm, a counter-based authentication algorithm, and an event synchronous authentication algorithm. Mathematically combining the master seed with the unique identifier for the any selectable client-side entity involves using an authentication algorithm based on a shared secret. Examples of algorithms that utilize shared secretes include: a hash function, a block cipher function, a stream cipher function and a message authentication code function. These are just examples of algorithms that may be used. Any other algorithm that utilizes a shared secret may also be used. Mathematically combining may involve using a key derivation function. The key derivation function may include an iterative function. The key derivation function takes as inputs the master seed or a value previously derived from the master seed and one or more unique identifiers from a plurality of unique identifiers, one of which may include unique identifiers identifying the plurality of users.

0019In general, in still another aspect, the invention features a method of generating authentication seeds for one or more client-side entities to enable them to individually authenticate to one or more server-side entities. The method involves from a single master seed, generating a plurality of derivative seeds, wherein generating each one of the plurality of derivative seeds involves mathematically combining the master seed with a corresponding different plurality of unique identifiers, each unique identifier of the corresponding different plurality of unique identifiers identifying a different entity.

0020Other embodiments include one or more of the following features. The method also involves distributing the plurality of derivative seeds to the one or more server-side entities to enable a user to authenticate to those one or more server-side entities by using an appropriate one of the plurality of derivative seeds. That is, the derivative seeds may be based upon a combination of user unique identifiers and server unique identifiers, each user and server having a unique identifier value. The one or more server-side entities is a plurality of server-side entities, wherein at least one of the unique identifiers of each corresponding different plurality of identifiers identifies a corresponding different server-side entity user among the plurality of server-side entities. Mathematically combining involves using a key derivation function. The key derivation function includes an iterative function. The key derivation function takes as inputs the master seed or a value previously derived from the master seed and one or more unique identifiers from a plurality of unique identifiers, one of which may include unique identifiers identifying the plurality of users.

0021In general, in still yet another aspect the invention features a method implemented in a token for authenticating a plurality of different users to another entity. The method involves: storing a master seed in the token; when any one of the users seeks to authenticate to the other entity, (1) mathematically combining the master seed with a unique identifier supplied for that user to generate a derivative seed for that user; and (2) using the derivative seed for that user to authenticate to the other entity. While the method has been described for a plurality of users authenticating to another entity, it should be understood that the method may be used for any type of entity authenticating to another entity.

0022Other embodiments include one or more of the following features. Using the derivative seed for that user to authenticate to the other entity involves using an authentication algorithm which utilizes a shared secret. Examples of algorithms include: a time-based authentication algorithm, a challenge-response authentication algorithm, a counter-based authentication algorithm, and an event synchronous authentication algorithm. In other embodiments, the method also involves erasing the derivative seed for that user after authenticating that user to the other entity. However, this step is not required.

0023In still yet another aspect, the invention features a method for use in a network in which a user having a user device that stores a master seed authenticates through a client-side device to another entity on the network. The method involves: in a server connected to the network, receiving from the client-side device a unique identifier identifying the client-side device; in the server, mathematically combining a secret with the unique identifier for the client device to generate a derivative seed, wherein the secret is derived from the master seed or a previously generated derived seed; and sending the newly derived seed from the server to the client-side device.

0024Other embodiments include one or more of the following features. The method also involves, at the client-side device: receiving the derivative seed; and after receiving the derivative seed, disconnecting the client-side device from the network. And it also involves: in the user device: receiving the unique identifier for the client-side device; mathematically combining at least the unique identifier with the master seed to generate the derivative seed; and using the derivative seed to authenticate to the client-side device while the client-side device is disconnected from the network. The master seed is the shared secret. Alternatively, the secret is a seed previously derived from the master seed, that is, it is generated by mathematically combining the master seed with one or more other identifiers.

0025In general, in yet another aspect, the invention features a method implemented by a client-side device on a network in which a user authenticates through the client-side device to another entity on the network. The method involves: sending to the other entity of the network a unique identifier identifying the client-side device; receiving from the other entity a derivative seed, wherein the derivative seed was generated by mathematically combining a secret with the unique identifier for the client-side device, wherein the secret is based on the master seed; disconnecting from the network; to authenticate a user, sending the unique identifier for the client-side device to a user device; after sending the unique identifier for the client-side device to the user device, receiving information from the user device indicating that user device knows derivative seed, such as an authentication code computed from or based on the resulting derivative seed.

0026In general, in still yet another aspect, the invention features a method of authenticating a plurality of users at a server site. The method involves: storing a plurality of derived seeds that are all computed from a single master seed, wherein each one of the plurality of derived seeds is for a corresponding different one of the plurality of users, wherein each derived seed of the plurality of seeds is generated by mathematically combining the master seed with a unique identifier for the corresponding user; for any selected one of the plurality of users, receiving authentication information from that user that is mathematically generated from the derived seed for that user; and for that selected user, authenticating that user based on the authentication information received from that user. In other embodiments, the method can be used to authenticate any type of entity (not just users) to another entity.

0027The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.

<u>Brief Description of the Drawings</u>

0028<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a block diagram of a system that generates derivative seeds for a group of users.</li><li><figref idref="f0001">FIG. 2</figref> is a block diagram that illustrates another aspect of how derivative seeds are generated and used.</li><li><figref idref="f0001">FIG. 3</figref> is a block diagram used to described disconnected authentication.</li></ul>

<u>Detailed Description</u>

0029In an earlier patent application owned by the assignee of record (i.e., <patcit id="pcit0003" dnum="US09304775A" dnum-type="L"><text>U.S.S.N. 09/304,775 filed May 4, 1999</text></patcit>, now <patcit id="pcit0004" dnum="US6985583B"><text>US Patent No. 6,985,583</text></patcit> (RSA-038)), an approach was disclosed for using a single master seed or secret to generate multiple verifier or derivative seeds, each one for authenticating to a different site. This allows an entity to authenticate to many verifiers without having to manage a large number of secrets. With this technique only a single secret needs to be maintained and management becomes much simpler as compared to an approach that requires a different secret for each site. With one secret the user can authenticate to multiple sites or multiple verifiers without compromising the secret or having to share it with more than one entity. The process works as follows.

0030During a registration process, Site 1 asks the user to enter the serial number for the token. Site 1 then sends to a master seed generator both the serial number of the user's token and the unique identifier for Site 1, namely, UID₁.

0031The master seed generator mathematically combines the master seed and the unique identifier U_V1 to produce a derivative or verifier seed, S_D1, which is unique for that particular token being used at that particular site. The derivative seed S_D1 is generated by using a key derivation function to combine the master seed with other information. The key derivation function has the characteristic that a third party cannot feasibly determine the master seed by knowing the verifier seed and the other information. The other information is identifying information about the authentication server, in this case the unique identifier, UID₁.

0032The master seed generator sends the derivative seed to Site 1, where it is installed into an authentication server or verifier.

0033During an actual authentication, the authenticator at Site 1 sends its unique identifier U_ID1 to the token or the user in some other way (e.g. keypad entry) supplies the identifier. The token internally combines UID₁ and the master seed to produce another copy of the derivative seed S_D1. The derivative seed S_D1 is then used to authenticate to the authentication server. This is typically done by cryptographically combining it with some dynamic variable (e.g. time, a counter variable, a challenge, etc) to produce an authentication code, which is a function of at least the dynamic variable and the derivative seed. This authentication code is then sent to the authentication server for Site 1. Since the authentication server knows the derivative seed and the dynamic variable, it can validate the code, i.e., it can compute the code and compare it to the received authentication code to confirm that the user knows the shared secret.

0034The same process happens at Site 2, except with a different unique identifier UID₂ for that site. The result is a different derivative seed, S_D2. As a consequence, the resulting authentication codes will be different when using the same token to a different site.

0035UID₁ and UID₂ are intended to be unique identifiers associated with each site. These could be the hash of the site URL, for example, or some other unique value such as the public key associated with the site, or perhaps a unique identifier initially selected at random. Once assigned, however, the unique identifier must be knowable to both the master seed generator, and the token so that each can independently compute the same derived seed.

0036Notice that the master seed is known only by the master seed generator and is the token into which it is programmed. The token never reveals its master seed, and the master seed generator never releases the master seed to anyone. Thus, the master seed itself is never used for authentication.

Multiple people

0037It was recognized that a problem arises any time one wants to use a symmetric key or a seed based token for multiple different users. For example, assume that multiple family members want to log into the same site (e.g. MSN or AOL) with their own accounts. If each member of the family shared the same token, that generates a need to manage multiple keys, one for each user of the token for whom authentication is to be performed. But provisioning and administering multiple master seeds in a shared token can become very complex. Additionally, each master seed consumes storage memory in the token and some mechanism must be provided enabling the user to select the correct master seed when authenticating. Whereas, the alternative of issuing multiple individual tokens, a different one for each user, would be cumbersome.

0038It was further recognized that to solve the problem that presents itself under these circumstances, one could instead generate multiple derived seeds enabling multiple different users to authenticate to the same site, wherein each derived seed is used by a different user. In that way, the same master seed can be used to generate a corresponding different derived seed for each member of a group of multiple members. In this case, the master seed is shared between the key server and a token held by the user. Each member of the group of people who will use the token has a corresponding unique identifier which is shared with the key server. The unique identified is a value associated with that member, e.g. the hash of that person's name. The key server generates the corresponding derived seed for each member of the group by mathematically combining the master seed with that member's unique identifier and sends those derived seeds to the verifier site. When a person who is member of the group wishes to authenticate to the verifier site, that person passes his or her unique identifier to the token and the token generates the derived seed for that person by mathematically combining the master seed with a unique identifier for that person. In that way, each member of the group has his or her own key and can authenticate to the verifier site independently of the other members of the group; but only one master seed is required to support this.

0039In this case, the unique identifiers are associated with the user, as opposed to the sites to which the user is authenticating. The unique identifiers could be anything that uniquely identifies that user, e.g. the hash of ones ISP login name, or possibly the hash of ones Instant Messenger buddy name.

0040<figref idref="f0001">Fig. 1</figref> shows an example of a system in which the derivative seed concept is implemented. It includes a master seed generator 100 which generates and installs a master seed S_M into a token 102 that is used by a group of users. Token 102 is a hardware device implemented, for example, as a credit-card sized device that incorporates a microprocessor with memory and associated hardware logic and firmware, a battery, and an LCD display. In the described embodiment, token 102 accepts data input from, for example, buttons, a keypad, a pressure-sensitive display, through a connector interface or by wireless communication. Token 102 may also be implemented as a software application which runs on a computer, cell phone, personal digital assistant, or any other device capable of executing a software application.

0041Master seed generator 100 also provides the same master seed S_M for that group of users to a key server 104. Key server 104 may be exclusively a seed distribution server, or it may be a data server, such as a file server, web server, or authentication servers that incorporates seed distribution functionality.

0042The master seed S_M is a secret that is shared by token 102 and key server 104. Typically, the master seed is generated randomly, for example, by a pseudorandom number generator or by using a sensor observing a sufficiently random physical event. In any case, it is generated in a way that produces a secret number that is statistically difficult to predict.

0043There is also a client computer 108 that is used by the group of users to authenticate into a server site than includes a verifier or authentication server 110. The process of generating the derivative seeds works as follows.

0044Initially, master seed generator 100 distributes a master seed to token 102 and to key server 104.

0045A user at client computer 108 logs into the server site and seeks to register with the particular service provided by that site. As part of the registration request, client computer 108 supplies the serial number of the token being used as well as an identifier UID₁ that uniquely identifies the user (e.g. login name or screen name). The serial number of the token will enable key server 104 to find the relevant master seed S_M for that token among the seed records which it stores in a local database.

0046In response, authentication server 110 at the site sends a registration request to the key server. Accompanying the request is the serial number of the token and the unique identifier for that user. Key server 104, using the serial number, looks up the record for that token in its database and retrieves the corresponding master seed, S_M. It then mathematically combines the master seed with the unique identifier to generate a derivative seed, S_P1, which it sends back to authentication server 110 as part of a seed record. Authentication server 110 stores the received seed record along with its derivative seed S_P1 in its database for future use in authenticating the user.

0047In the described embodiment, key server 104 generates the derivative seed S_P1 by using a key derivation function "KDF." Key derivation functions are well known in the field of encryption. Key derivation functions are generally chosen for a capability to generate relatively distinct outputs for different inputs, and because they are hard to reverse, meaning that it is difficult, given a particular output, to determine the input. Various key derivation functions are based on hash functions, pseudorandom functions, and so on.

0048Key derivation functions typically combine the secret with other information. The secret may be a password. For the method of the invention, the secret is the seed, either the master seed or a previously generated derivative seed. An iterative function also may be included in a key derivation function. A number, referred to as an iteration count, can be used to indicate how many times to perform an underlying function by which the key is derived. The incorporation of the iteration count into the key derivation function increases the effort required to derive an encryption key from a password. A modest number of iterations, for example, 1000 is not likely to be a burden for legitimate parties when computing a key, but it will be a significant burden for attackers. If the password value is a large random value, a small iteration count may be used. Using a KDF and an iterative function is an example of how to derive the derivative seeds. Other techniques may be used.

0049It should be understood that other key derivation functions would be similarly useful, and various substitutions for the user information and other information are possible, as required by the particular key derivation function. Key derivation functions based on underlying hash functions, block ciphers, message authentication codes, and so on are among other alternatives.

0050In the described embodiment, which employs the key derivation function, the inputs to the key derivation function are thus the master seed, the user identifier (or a concatenated version thereof), and a time identifier. The user identifier U_1D includes information about the user, and also can include other information, such as a time value.

0051The key derivation function KDF takes as inputs the master seed S_M and identifying information UID₁ for user₁. The server 110 stores the master seed S_M. Token 102 also stores the master seed S_M and has access to the user identifier information UID₁. Token 102 is thus also able to use the same key derivation function to obtain the same derivative seed S_P1 from the master seed S_M and the user identifier information UID₁.

0052Each user sharing that token will have unique identifier information. The same procedure is followed to generate a corresponding derivative see S_Pi for each user, which is stored by authentication server 110.

0053Whenever any user within the group uses the token to authenticate to the site server, the client will pass the unique identifier for that user to the token. The token will internally combine that user's unique identifier with the previously stored master seed to generate a derived seed unique to that user. The client then uses the derived seed to authenticate the user to the authentication server at the site server site. In one embodiment, the token uses the derived seed to compute authentication code(s) unique to that user. The token passes the authentication code(s) back to the client, which then supplies them to the site server to authenticate the user.

0054Notice that the actual authentication uses the derivative seeds and never the master key, thereby protecting the security of the master seed. Authentication is typically accomplished by token 102 and/or client computer 108 transmitting a value that is mathematically derived from the derivative seed S_Pi to the verifier. Authentication can be accomplished by using a hash function, block cipher, message authentication code, or other techniques. Authentication can be accomplished by using a time-based algorithm according to which, the derivative seed S_Pi is, as part of the derivation, combined with time-dependent information. As another example, a challenge/response approach can be used. It would involve the verifier 108 transmitting a challenge value to the token 102. Token 102 then encrypts the challenge value with the derivative seed S_Pi, and transmits the result back to authentication server 110. Still other approaches include a counter-based authentication and an event synchronous authentication (e.g. HOTP).

0055Various authentication and communication systems and methods that can be utilized when a secret is shared by a device 102 and a verifier 108 can be extended to use the derivative seed. For example, see <patcit id="pcit0005" dnum="US4720860A"><text>U.S. 4,720,860</text></patcit>; <patcit id="pcit0006" dnum="US4885778A"><text>U.S. 4,885,778</text></patcit>; <patcit id="pcit0007" dnum="US4856062A"><text>U.S. 4,856,062</text></patcit>; <patcit id="pcit0008" dnum="US4998279A"><text>U.S. 4,998,279</text></patcit>; <patcit id="pcit0009" dnum="US5023908A"><text>U.S. 5,023,908</text></patcit>; <patcit id="pcit0010" dnum="US5058161A"><text>U.S. 5,058,161</text></patcit>; <patcit id="pcit0011" dnum="US5097505A"><text>U.S. 5,097,505</text></patcit>; <patcit id="pcit0012" dnum="US5237614A"><text>U.S. 5,237,614</text></patcit>; <patcit id="pcit0013" dnum="US5367572A"><text>U.S. 5,367,572</text></patcit>; <patcit id="pcit0014" dnum="US5361062A"><text>U.S. 5,361,062</text></patcit>; <patcit id="pcit0015" dnum="US5485519A"><text>U.S. 5,485,519</text></patcit>; and <patcit id="pcit0016" dnum="US5657388A"><text>U.S. 5,657,388</text></patcit>, which describe various systems and methods for authentication using shared secrets. Such systems can incorporate the system and methods described herein to use a derivative seed as the basis for authentication.

0056A common feature of the approaches just described is that there is only a single master seed in the token and the token uses that master seed to generate whatever derivative seeds are required. As indicated above, this has the great advantage of not requiring the user to manage multiple master seeds, which can be confusing and difficult to many users. Also note that the token typically neither receives nor even stores the derivative seed. However, in certain embodiments, the token may receive and/or store the derivative seed. It generates the derivative seed as needed from that single stored master seed and, when it is done using the derivative seed for authenticating to the desired site, it typically erases that derivative seed.

0057An alternative approach is, of course, to pre-compute and store the various derivative seeds in the token and simply supply the appropriate derivative seed when required.

0058A further extension of the idea presented above uses multiple unique identifiers to produce a derivative seed. For example, if multiple individuals in a group share a token and they want to use that same token to authenticate to different sites, then, derived seeds are generated for each meaningful combination (of person and site) that might be appropriate. To simplify the example, assume that there are two members in the group and also assume that each member of the group wants to use the token to authenticate to each of two sites, e.g. AOL and MSN. In that case, four derivative seeds are defined for the system, one for each combination of person and site. Thus, for person A at site 1 the corresponding derivative seed for that combination is generated by applying the unique identifier for person A (UID_A) to the master seed (S_M) to generate an intermediate result S_A and then applying the unique identifier for site 1 (SiteID₁) to the intermediate result to generate the derivative seed, S_A1. <maths id="math0001" num=""><math display="block"><msub><mi mathvariant="normal">S</mi><mi mathvariant="normal">A</mi></msub><mo>=</mo><mi>KDF</mi><mfenced separators=""><msub><mi mathvariant="normal">S</mi><mi mathvariant="normal">M</mi></msub><mo>,</mo><mspace width="1ex" /><msub><mi>UID</mi><mi mathvariant="normal">A</mi></msub></mfenced></math><img file="EP1849119B1_D0001.tif" /></maths><maths id="math0002" num=""><math display="block"><msub><mi mathvariant="normal">S</mi><mrow><mi mathvariant="normal">A</mi><mn>1</mn></mrow></msub><mo>=</mo><mi>KDF</mi><mfenced separators=""><msub><mi mathvariant="normal">S</mi><mi mathvariant="normal">A</mi></msub><mo>,</mo><mspace width="1ex" /><msub><mi>SiteID</mi><mi mathvariant="normal">1</mi></msub></mfenced></math><img file="EP1849119B1_D0002.tif" /></maths> The rest of the derivative seeds are generated in a similar fashion by using first the UID for the person and then the unique ID for the site. While the above example shows the derivation of S_A and S_A1 as serial computations (one after the other), this is an example only and is not required. In other embodiments, a single KDF may be performed using multiple unique identifiers.

0059This can be extended to any combination of entities. In other words, multiple unique identifiers can be combined when creating a derivative seed. For example, person A might want to authenticate to computer X and at site 1. Or, person A might want to authenticate to computer X at site 2. Or, person B might want to authenticate to computer Y at site 2, etc. There would be a different derivative seed for each of these combinations. And that derivative seed would be generated from the master seed by sequentially applying the unique identifier for person, the unique identifier for the computer, and the unique identifier for the site.

0060Any number of unique identifiers can be chained in this fashion to generate a corresponding derivative seed from a single master seed. Moreover, as in the simpler cases described above, the token would not need to store the derivative seeds so long as it was provided with the correct unique identifiers at the time of authentication to produce the required derivative seed. The token only needs to store the master seed and the function which is used to generate the derivative seed from the master seed.

0061In addition to sites and people, the unique identifiers can be virtually anything that identifies the entity wanting to be authenticated or the identity entity into which one wanted to authenticate. This includes, for example, a hardware unique ID; a unique domain ID; a group ID; an intermediary node ID; a newsgroup ID; a Kazza ID; a drivers license number; a passport number; a telephone number; the serial number of a cable box; etc. The intermediary node ID may be useful for antiphishing techniques (i.e. user_A at site_B coming from site_C).

0062Another example of a further extension of these ideas is illustrated in <figref idref="f0001">Fig. 2</figref>. This particular example shows how multiple unique identifiers can be used to enable local authentication within a network thereby avoiding having to go back to a root authentication server for every authentication.

0063In <figref idref="f0001">Fig. 2</figref> there are multiple authentication servers within a network arranged in a tree structure. The root authentication server is AS₁ and the remainder of the authentication servers, AS₂, AS₃, AS₄, AS₅, and AS₆ are connected to the root authentication server through the tree structure, as shown. Using the concepts described above, authentication is performed locally by the server to which the client connects and all of the authentications are based on the single master seed in the token held by the user.

0064A key server, KS, which stores the master seed, S_M, generates a derivative seed, DS₁, and sends that derivative seed to the root server, AS₁. The derivative seed is generated as previously described by mathematically combining the master seed S_M with a unique identifier for the root server AS₁ (i.e., UID₁) by using some appropriate key derivation function of a type known to persons of ordinary skill in the art. The user who possesses a token containing a copy of the master seed, S_M, can authenticate directly to the root server, AS₁. This is done by receiving from the root server AS₁ its unique identifier, UID₁, and applying that unique identifier to the master seed S_M to generate the corresponding derivative seed, DS₁. <maths id="math0003" num=""><math display="block"><msub><mi mathvariant="italic">DS</mi><mn>1</mn></msub><mo>=</mo><mi mathvariant="italic">KDF</mi><mfenced separators=""><msub><mi>S</mi><mi>M</mi></msub><mo>,</mo><mi mathvariant="italic">UI</mi><msub><mi>D</mi><mn>1</mn></msub></mfenced></math><img file="EP1849119B1_D0003.tif" /></maths> This operation can also be represented as follows: DS₁ = S_M + UID₁. The user then uses this derivate seed, DS₁, to authenticate directly to the root server in the manner described above.

0065In the described embodiment, a derivative seed DS₃ is generated for a next authentication server in the tree, AS₃, by applying its unique identifier to the derivative seed for AS₁. In other words, root server, AS₁, generates the derivative seed, DS₃, for authentication server, AS₃, by applying UID₃ to DS₁. That is, <maths id="math0004" num=""><math display="block"><msub><mi mathvariant="italic">DS</mi><mn>3</mn></msub><mo>=</mo><mi mathvariant="italic">KDF</mi><mfenced separators=""><msub><mi mathvariant="italic">DS</mi><mn>1</mn></msub><mo>,</mo><mi mathvariant="italic">UI</mi><msub><mi>D</mi><mn>3</mn></msub></mfenced></math><img file="EP1849119B1_D0004.tif" /></maths> Using the other form, this could be written as: DS₃ = DS₁ + UID₃.

0066Notice that if the appropriate key derivation function is chosen, DS₃ can also be generated from the master seed by applying the two unique identifiers in succession, i.e., <maths id="math0005" num=""><math display="block"><msub><mi>DS</mi><mn>3</mn></msub><mo>=</mo><mfenced separators=""><msub><mi mathvariant="normal">S</mi><mi mathvariant="normal">M</mi></msub><mo>+</mo><msub><mi>UID</mi><mn>1</mn></msub></mfenced><mo>+</mo><msub><mi>UID</mi><mn>3</mn></msub><mo>.</mo></math><img file="EP1849119B1_D0005.tif" /></maths> In other words, the derivative seed for AS₃ can be generated by two different entities. (It should be noted that not all key derivation functions allow separating the steps as just shown. An appropriate key derivation function must be used in order to take advantage of this particular characteristic.) The derivative seed can be generated by the key server, KS, based on the master seed, S_M, if the unique identifiers for the root server, AS₁, and for authentication server, AS₃, are made available to the key server. Or, if the unique identifier for authentication server, AS₃, is made available to authentication server, AS₁, it can be generated by authentication server, AS₁, based on its derivative seed DS₁.

0067This approach can be extended to the other authentication servers in the tree structure to generate derivative seeds for the other servers. Thus, each authentication server is able to generate derivative seeds for a neighboring child server in the network tree.

0068In the described embodiment, the neighboring authentication server which generates and supplies the derivative seed to the requesting server also sends along with the derivative seed its own unique identifier and the unique identifiers of all of the authentication servers in the path back to and including the root server. Thus, any authentication server that wants to authenticate a user is able to provide to that user (or the user's token) all of the unique identifiers that will enable the token to generate the derivative seed for that authentication server from the master seed, S_M, which it stores internally. This makes it unnecessary for the authentication server, regardless of where it is in the tree, to communicate with parent servers further up in the tree to perform authentication. Thus, for example, if the user wants to authenticate to server AS₆, it receives from server AS₆ the unique identifiers for AS₁, AS₃, AS₅, and AS₆. Then, by using the appropriate key derivation function which the user's token stores internally it applies those unique identifiers in succession to the master seed S_M to compute the derivative seed for server AS₆.

Disconnected Authentication:

0069Another advantage to the ideas described above is that the generation of the derivative seed can take place anytime and need not occur at the time the derivative seed is generated for other servers or entities in the system. The usefulness of this can be appreciated with the aid of a simple example illustrated by the network shown in <figref idref="f0001">Fig. 3</figref>. The network includes a key server KS, an authentication server AS at Site 1, a notebook computer NB connected to Site 1, and a user's token.

0070As described above, authentication server AS at Site 1 registers with the key server KS by providing its unique identifier, UID₁ to key server KS. Key server KS, in turn, uses a key derivation function to combine its master key, S_M, with the unique identifier, UID₁, to generate a derivative seed, DS₁, for Site 1. The user of the notebook computer authenticates to Site 1 by using a token which also holds a copy of the master seed S_M. To enable the user to authenticate to Site 1, the authentication server at Site S1 provides its unique id, UID₁, to the notebook computer, which, in turn, provides that unique id to the token. The token, which also knows the relevant key derivation function and the master seed S_M, then computes DS₁ in the same manner that key server KS generated it and uses that derivative seed to authenticate to authentication server AS.

0071At some later time, the user may want to disconnect the notebook from Site 1 so that it no longer is able to communicate with the authentication server AS₁ at Site 1. It may be desirable under those circumstances to require the user to authenticate to the notebook computer while it is disconnected and during the period when authentication to the authentication server at Site 1 is not possible. This is accomplished by using the ideas discussed above. More specifically, the user registers the notebook computer NB with the authentication server AS₁ at Site 1 for disconnected authentication. In response, the authentication server AS₁ at Site 1 performs another seed derivation by mathematically combining a unique id, UID_NB, from the notebook computer (e.g. its serial number) with the derivative seed that was previously provided to the authentication server, namely, DS₁. In other words, the authentication server AS₁ at Site 1 computes the following: DS₂ = DS₁ + UID_NB. Then, the authentication server sends derivative seed, DS₂, along with its unique identifier, UID₁, the notebook computer before the notebook is disconnected.

0072To enable the user to authenticate to the notebook computer while offline, the notebook computer sends to the user's token its own unique identifier, UID_NB, as well as unique identifier for Site 1, namely, UID₁. Internally, the token uses the key derivation function to mathematically combine the master seed S_M and the two identifiers, UID₁ and UID_NB, to generate DS₂ (i.e., DS₁ = S_M + UID₁; DS₂ = DS₁ + UID_NB). The user then uses DS₂ to authenticate to the notebook while it is disconnected from the network.

0073The above-described processes involving a network of authentication servers and disconnected authentication can be extended to many levels and to different levels by simply applying the principles that were also presented above.

0074Note that the unique identifier can be any value. While the unique identifier can be any value, for the highest level of security, the value is unique. Examples of unique identifiers include the public key of a site, a site URL, a username, a notebook serial number, etc. The combining of the unique identifier and the master seed can occur with a variety of different algorithms known in the art. Hashing them together is one example. Also, the authentication token can be any type of token based on a shared secret (symmetric key or seed). Examples include time-based, challenge-response, time and event, event synchronous, etc. Also, as is well known by persons skilled in the art, other information can be included in the derivation of the seed.

0075It should be understood that certain functionalities which are shown in this application as separate may be combined, and other functionalities that are shown as being combined may be split without impacting the underlying principles described herein. For example, master seed generator 100 and key Server 104 are shown in <figref idref="f0001">Fig. 1</figref> as being separate entities. These two functions could, however, be combined into a single entity. Also, server site 110 was shown as including the functionality of the verifier or authentication manager; but these two functions could be separated with the authentication manager being managed by a different entity from the one that manages the server site. Indeed, given that the authentication service is more likely to be provided by a third party server site rather than the site into which the user is trying to gain access, the functionality would be separated.

0076It should also be understood that the entity that is authenticating into a site was referred to herein as the user. In fact, this entity might be more generally referred to as the client-side entity since it could also be any hardware device, application or other software entity that seeks to authenticate into another site. Similarly, the servers into which the client-side entities seek to authenticate could be server sites, domains, regions or any other server-side entity into which a client-side entity might wish to authenticate.

0077In the above description, the user device that carries the master seed and is used to authenticate to a server was referred to herein as a token. This device is also sometimes referred to as an authenticator. It could take various forms including, for example, a hardware device which includes an internal processor element and memory or it could be code running on a PC (e.g. a soft token).

0078Also note that the user must have the ability to store the master see and must have key derivation capability, and must know the key derivation function. This capability can be contained with the token employed by the user in connection with the client computer or it can be contained within a combination of those devices.

0079Other embodiments are within the following claims.