USOO698,5583B1
`
`(12) United States Patent
`Brainard et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,985,583 B1
`Jan. 10, 2006
`
`(54) SYSTEM AND METHOD FOR
`AUTHENTICATION SEED DISTRIBUTION
`
`(75)
`
`(73)
`(*)
`
`(21)
`(22)
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`Inventors: John G. Brainard, Sudbury, MA (US);
`Burton S. Kaliski, Jr., Wellesley, MA
`(US); Magnus Nyström, Concord, MA
`(US); Ronald L. Rivest, Arlington, MA
`(US)
`Assignee: RSA Security Inc., Bedford, MA (US)
`Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`Appl. No.: 09/304,775
`Filed:
`May 4, 1999
`
`Int. Cl.
`(2006.01)
`H04L 9/00
`(2006.01)
`H04L 9/32
`U.S. Cl. ........................ 380/44; 380/277; 713/168;
`713/169; 713/171; 713/176; 713/200
`Field of Classification Search ........ 713/168-176;
`380/44, 277
`See application file for complete Search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`Hargrove
`4,104,694
`4,145,568
`Ehrat
`4,145,569
`Ehrat
`4,238.854
`EhrSam et al. .............. 713/165
`4,317,957
`Sendrow
`4,320,387
`Powell
`Campbell, Jr.
`4,369,332
`4,438,824
`Mueller-Schloer
`4,471,216
`Herve
`Stellberger
`4,509,093
`4,536,647
`Atalla et al.
`4,543,657
`Wilkinson
`4.575,621
`Dreifus
`4,578,530
`Zeidler
`Plangger et al.
`4,582,434
`
`8/1978
`3/1979
`3/1979
`* 12/1980
`3/1982
`3/1982
`1/1983
`3/1984
`9/1984
`4/1985
`8/1985
`9/1985
`3/1986
`3/1986
`4/1986
`
`4,599,489 A 7/1986 Cargile
`4,605,820 A 8/1986 Campbell, Jr.
`4,609.777 A
`9/1986 Cargile
`4,614,861 A 9/1986 Pavlov et al.
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`O140013 B1
`
`5/1985
`
`(Continued)
`OTHER PUBLICATIONS
`FIPS Publ. 190, “Guideline for the use of advanced authen
`tication technology alternatives”, Sep. 28, 1994, section 4;
`Section 4.4.2.1 particularly.*
`
`(Continued)
`Primary Examiner Ayaz Sheikh
`ASSistant Examiner-Ronald Baum
`(74) Attorney, Agent, or Firm-Wilmer Cutler Pickering
`Hale and Dorr LLP
`
`(57)
`
`ABSTRACT
`
`In one embodiment of a user authentication System and
`method according to the invention, a device shares a Secret,
`referred to as a master Seed, with a server. The device and
`the Server both derive one or more Secrets, referred to as
`Verifier Seeds, from the master Seed, using a key derivation
`function. The server shares a verifier seed with one or more
`Verifiers. The device, or an entity using the device, can
`authenticate with one of the verifiers using the appropriate
`verifier seed. In this way, the device and the verifier can
`share a secret, the verifier seed for that verifier, without that
`Verifier knowing the master Seed, or any other verifier Seeds.
`Thus, the device need only Store the one master Seed, have
`access to the information necessary to correctly derive the
`appropriate Seed, and have Seed derivation capability. A
`Verifier cannot compromise the master Seed, because the
`Verifier does not have access to the master Seed.
`
`35 Claims, 5 Drawing Sheets
`
`102
`
`DEVICE
`
`104
`
`
`
`SERVER
`
`AUTH
`USING
`
`VERFER
`
`108
`
`USR Exhibit No. 2025
`
`

`

`US 6,985,583 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`FR
`JP
`JP
`JP
`WO
`
`7/1985
`O148960 B1
`O566811 A1 10/1993
`O678836 B1
`10/1995
`26O7544
`6/1988
`59-11963O
`5/1991
`2835,433
`6/1997
`2884.338
`4/1999
`88/O6826
`9/1988
`
`4,720,860 A 1/1988 Weiss
`4,731.841 A 3/1988 Rosen et al.
`4,800,590 A
`1/1989 Vaughan
`4,819,267 A
`4/1989 Cargile et al.
`4,849,613 A 7/1989 Eisele
`2Y- - - 2
`4.856,062 A 8/1989 Weiss
`4.885,778 A 12/1989 Weiss
`4,890,323 A 12/1989 Beker et al.
`OTHER PUBLICATIONS
`4,928,098 A 5/1990 Dannhaeuser
`Chevassut, O., et al., “One-time Verifier based Encrypted
`4,933,971. A * 6/1990 Bestock et al. ............... 380/44
`Key Exchange”, Lawrence Berkeley National Lab.,
`4944008 A 7/1990 Piosenka et al.
`Springer-Verlag 2004-2005, entire document.*
`4,998.279 A 3/1991 Weiss
`Kim, Y., et al., “Secure authentication System that generates
`5,016,276 A 5/1991 Matumoto et al. ............ 380/45
`seed from biometric information’, Feb. 10, 2005, Optical
`5,023.908 A 6/1991 Weiss
`Society of America, Applied Optics, vol. 44, No. 5, entire
`5,046,125 A 9/1991 Takizawa
`article.*
`5,058,161 A 10/1991 Weiss
`American National Standard for Financial Services.
`5,097.505 A
`3/1992 Weiss
`“Financial Services Key Management Using the DEA,”
`5,101,430 A 3/1992 Periou
`American Bankers Association, copyright 1992, 1999, pp.
`5,168,520. A 12/1992 Weiss
`i-iii, 1-9, 34-52.
`5,180.902 A
`1/1993 Schick et al.
`RSA Laboratories, a division of RSA Data Security, Inc.
`A
`1. W. al.
`“PKCS is v2.0: Password-Based Cryptography Standard.”
`5280,527 A 1/1994 Gullman et al.
`Mar 25, 1999, copyright 1991-1999, pp. 1-30.
`5,347,580 A * 9/1994 Molva et al. ............... asso
`Standard Specifications for Public Key Cryptography, IEEE
`5,361,062. A 11/1994 Weiss et al.
`P 1363 / D 13 (Draft Version 13), Institute of Electrical and
`5,367,572 A 11/1994 Weiss
`Electronics Engineers, Inc., New York, NY, Nov. 12, 1999,
`5,479,512. A 12/1995 Weiss
`pp. 1, 4-6, 53-57, 71-73.
`5,485,519 A
`1/1996 Weiss
`Freier, et al. The SSL Protocol, Version 3.0, http://home.
`5,513.263 A * 4/1996 White et al. .................. 380/44
`netscape.com/eng/ssI3/3-SPEC.htm, Mar. 1996, pp. 1-26,
`5,539,824. A *
`7/1996 Bjorklund et al. .......... 380/249
`and Table of Contents, http://home.netscape.com/eng/SSl3/
`5,592,553 A
`1/1997 Guski et al.
`SSl-toc.html, pp. 1-3.
`5,655,077 A * 8/1997 Jones et al. ................. 713/201
`European Patent Office, European Search Report,
`5,657,388 A 8/1997 Weiss
`International Application EP 00303741, date of completion
`5,717,756 A
`2/1998 Coleman
`of Search Jan. 16, 2002, 2 pages.
`2. A 3. 1998 Mark
`5,748,734. A *
`5/1998 Mizikovsky ................ so, Ferreira, The SmartCard: A High Security Tool in EDP",
`5,802,176 A 9/1998 Audebert
`Philips Telecommunications and Data Systems Review,
`5.841,864 A * 11/1998 Klayman et al. ........... 713/171
`Philips Telecommunicatie Industrie N.V. Hilversum, NL,
`5,887,065 A 3/1999 Audebert
`Sep. 1989, vol. 47, No. 3, pp. 1.-19.
`5.937,068 A 8/1999 Audebert
`Shamir,"Identity-Based Cryptosystems and Signature
`6,078.888 A
`6/2000 Johnson, Jr. ................... 705/1
`Schemes', Lecture Notes in Computer Science, Springer
`6,141,760 A 10/2000 Abadi et al.
`Verlag, New York, NY, US, 1985, pp. 47-53.
`6,295,359 B1* 9/2001 Cordery et al. ............... 380/44
`6,338,140 B1
`1/2002 Owens et al. ............... 713/168
`* cited by examiner
`
`2 -
`
`f1998 Audebert
`
`- -
`
`66
`
`ss
`
`USR Exhibit No. 2025
`
`

`

`U.S. Patent
`
`Jan. 10, 2006
`
`Sheet 1 of 5
`
`US 6,985,583 B1
`
`H_LTV7
`
`SONIST
`
`
`
`USR Exhibit No. 2025
`
`

`

`U.S. Patent
`
`Jan. 10, 2006
`
`Sheet 2 of 5
`
`US 6,985,583 B1
`
`
`
`s
`
`USR Exhibit No. 2025
`
`

`

`U.S. Patent
`
`Jan. 10, 2006
`
`Sheet 3 of 5
`
`US 6,985,583 B1
`
`
`
`dELLS
`
`00?
`
`dELS
`
`ZOZ
`
`USR Exhibit No. 2025
`
`

`

`U.S. Patent
`
`Jan. 10, 2006
`
`Sheet 4 of 5
`
`US 6,985,583 B1
`
`
`
`S
`
`:
`
`1.
`
`9
`
`(Ot
`CD
`
`USR Exhibit No. 2025
`
`

`

`U.S. Patent
`
`Jan. 10, 2006
`
`Sheet 5 of 5
`
`US 6,985,583 B1
`
`
`
`
`
`- - - - - - - as as s - - - -
`
`USR Exhibit No. 2025
`
`

`

`1
`SYSTEMAND METHOD FOR
`AUTHENTICATION SEED DISTRIBUTION
`
`TECHNICAL FIELD
`
`This invention relates to the field of computer-based
`Security Systems and, more particularly, to the distribution of
`authentication Seeds.
`
`BACKGROUND INFORMATION
`
`In Security Systems, Verifiers are used to authenticate, that
`is to Verify the identity of, a perSon or other entity Such as
`a computer. When an entity has been authenticated, meaning
`that the identity of the entity has been determined by the
`Verifier, 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 information (e.g.
`financial records, computer data, network access, etc.), in
`data Security Systems.
`There 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, poS
`sibly, but not necessarily, in electrical communication with
`Special-purpose hardware.
`Some verifiers use knowledge of a shared secret to
`authenticate an entity. For example, knowledge of a personal
`identification number, password, or passphrase can be used
`to Verify an entity. At the time that authentication takes
`place, the entity either reveals the Secret or otherwise proves
`knowledge of the Secret. If the entity shows knowledge of
`the Secret, the entity is authenticated.
`In 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. A common door key
`is one simple mechanical example of Such a device. The
`shape of the key is a shared Secret. When a key is inserted
`into a lock, the lock Verifies that the key is of the correct
`shape. The door key shows knowledge of the Secret to the
`verifier (the lock), and allows entry. An attacker who learns
`the exact shape of the key can generate an appropriate token
`and authenticate to the lock.
`A bank card is a device that can contain a Secret identi
`fication number that is revealed when the card is accessed by
`an automatic teller machine ("ATM"). Some bank cards
`incorporate cryptography to make forging of bank cards
`more difficult. Also, to provide an added layer of Security,
`automatic teller machines require the user to possess the
`device (bank card) containing Secret information, and
`require the user to enter a Personal Identification Number
`(“PIN”), which is another secret shared between the bank’s
`Verifier and the account holder.
`Some devices, to prove knowledge of a Secret contained
`within the device, 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
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,985,583 B1
`
`2
`to determine by eavesdropping in the communications chan
`nel between the entity and the verifier, since the secret itself
`is not revealed.
`One example of this Sort of device used by a person to
`authenticate to a verifier is a token that includes an authen
`tication 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 informa
`tion).
`One 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 pro
`Vided 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 chal
`lenge to produce an output that is Sent to the verifier as a
`response to the challenge.
`To 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 is increasingly more difficult to main
`tain the Secrecy of the Secret. For example, as the number of
`Verifiers increases, So does the chance that one of the
`Verifiers can be compromised in Some fashion. Yet, if the
`number of verifiers is limited, it possible that a verifier will
`not be available to authenticate an entity when the entity
`requires authentication.
`In addition, a Single device presently cannot be used to
`acceSS multiple independent Services. For example, the same
`device cannot be used to access an enterprise's computer
`System and a financial institution's web page. Even if each
`independent Service trusts the user and the device, the
`Services do not trust each other. In the example just men
`tioned, a bank does not trust the user's employer. If each of
`the Services share the same Secret with the device, then each
`Service has information that can compromise the others. This
`prevents use of a single device from being used with
`Verifiers associated with independent Services.
`The 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.
`Similar issues arise in the area of Secure communications,
`where a Single shared Secret is used as an encryption key. To
`communicate Securely with many other entities, an entity
`either has to have a separate shared Secret with each other
`
`USR Exhibit No. 2025
`
`

`

`US 6,985,583 B1
`
`3
`entity, or has to share the same Secret with more than one
`entity, thereby reducing the Secrecy (and Security) of the
`shared Secret.
`Public 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 cryptog
`raphy 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.
`
`SUMMARY OF THE INVENTION
`
`4
`Verifier Seed using the master Seed and information associ
`ated with a Second Verifier, and transmitting the Second
`verifier seed to the second verifier. In another embodiment,
`the method includes, after the transmitting Step, generating
`an authentication code in response to the Verifier Seed.
`In one embodiment, the generating Step includes gener
`ating an authentication code in response to the verifier Seed
`and a time dependent value. In another embodiment, the
`method includes the Step of authenticating using the authen
`tication code. In another embodiment, the authenticating
`Step includes authenticating a user or a device by Verifying
`the authentication code. In another embodiment, the authen
`ticating Step includes transmitting the authentication code to
`the Verifier. In another embodiment, the generating Step
`includes randomly generating and/or pseudorandomly gen
`erating the master Seed.
`In one embodiment, the deriving Step includes deriving
`the Verifier Seed in response to a time identifier. In another
`embodiment, the deriving Step includes deriving a verifier
`Seed by using the master Seed and information associated
`with a verifier as inputs to a key derivation function. In
`another embodiment, the key derivation function is a hash
`function.
`In another aspect of the invention, a System for distrib
`uting authentication information associated with a device
`includes a Seed generator for generating a master Seed
`asSociated with a device, a Server for deriving a verifier Seed
`using the master Seed and information associated with a
`Verifier, and a transmitter for transmitting the Verifier Seed to
`the verifier. In one embodiment, the System includes a
`transmitter for transmitting the master Seed to the device. In
`another embodiment, the System includes a communication
`channel for Sharing the master Seed with the device and the
`Server. In another embodiment, the Server derives a Second
`Verifier Seed using the master Seed and information associ
`ated with a Second Verifier, and the transmitter transmits the
`Second Verifier Seed to the Second verifier. In another
`embodiment, the System includes an authentication code
`generator for generating an authentication code in response
`to the verifier seed. In another embodiment, the system
`includes an authentication code generator for generating an
`authentication code in response to the verifier Seed and a
`time dependent value. In another embodiment, the Seed
`generator is a random generator and/or a pseudorandom
`generator. In another embodiment, the Server includes a key
`derivation function.
`In another aspect of the invention, a method for authen
`tication includes Storing a master Seed associated with a
`device, deriving a verifier Seed using the master Seed and
`information associated with a verifier, and generating an
`authentication code in response to the verifier Seed. In one
`embodiment, the method includes authenticating a user with
`the authentication code. In another embodiment, the method
`includes transmitting the authentication code to a verifier. In
`another embodiment, the method includes receiving the
`authentication code by a verifier.
`In another aspect of the invention, an authentication
`System includes a memory for Storing a master Seed asso
`ciated with a device, a Server for deriving a verifier Seed
`using the master Seed and information associated with a
`Verifier, and an authentication code generator for generating
`an authentication code in response to the Verifier Seed.
`In another aspect of the invention, a verifier includes a
`data Store for Storing a verifier Seed associated with a device,
`an input for receiving an input authentication code, and an
`
`15
`
`25
`
`The System and method of the present invention allows an
`entity to authenticate to many verifiers without having to
`manage a large number of Secrets. An authentication System
`that is simple, and that allows the user to manage just one
`Secret, yet allows the user to authenticate with multiple
`Verifiers is a great improvement over the prior art. For
`example, a token-based System and method could allow
`authentication with Some or all of Such diverse Systems as
`(but not limited to) file servers inside and outside of one or
`more enterprises, remote acceSS Servers, Web Servers asso
`ciated with various Services (e.g. financial, business, utili
`ties, entertainment, etc.), other computers, a physical Secu
`rity System within a home or office, and a bank automatic
`teller machine. Such an authentication method and System
`avoids the complexity and cost of managing different Secrets
`or devices for different services.
`The benefit of associating a Single Secret with a user that
`is useful with multiple verifiers is beneficial even if the
`device is an electronic wallet stored on a personal computer,
`where the memory and processing limitations are much leSS
`restrictive than in a Smart card or other Small-sized token
`with limited memory and processing power. The Simplicity
`allows for Smaller, faster implementations, and also avoids
`the complexity of sharing each Secret.
`In an embodiment of a user authentication method and
`System according to the invention, a device Shares a Secret,
`referred to as a master Seed, with a server. The device and
`the Server both derive one or more Secrets, referred to as
`Verifier Seeds, from the master Seed, using a key derivation
`function. The server shares a verifier seed with one or more
`Verifiers. The device, or an entity using the device, can
`authenticate with one of the verifiers using the appropriate
`verifier seed. In this way, the device and the verifier can
`share a Secret, the Verifier Seed, without that Verifier having
`access to the master Seed, or any other verifier Seeds. Thus,
`the device need only Store the one master Seed, have acceSS
`to the information necessary to correctly derive the appro
`50
`priate verifier Seed, and have Seed derivation capability. An
`individual verifier cannot compromise the master Seed,
`because the verifier does not have access to the master Seed.
`In addition, if a particular verifier is compromised, only that
`Verifier Seed is affected, and other verifiers using other
`Verifier Seeds are not compromised.
`In one aspect of the invention, a method for distributing
`authentication information associated with a device includes
`generating a master Seed associated with the device, deriving
`a verifier Seed using the master Seed and information asso
`ciated with a verifier, and transmitting the Verifier Seed to the
`verifier. In one embodiment, the method includes, after the
`generating Step, the Step of transmitting the master Seed to
`the device. In another embodiment, the method includes,
`after the generating Step, Sharing the master Seed with the
`device and a Server. In another embodiment, the method
`includes, after the transmitting Step, deriving a Second
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`USR Exhibit No. 2025
`
`

`

`US 6,985,583 B1
`
`S
`authenticator for determining whether the input authentica
`tion code was correctly generated in response to the verifier
`Seed.
`In another aspect of the invention, a token includes a data
`Store for Storing a master Seed, a key derivation function for
`deriving a verifier Seed from a master Seed in response to
`information associated with a verifier, an authentication
`code generator for generating an authentication code in
`response to a verifier Seed, and an output for providing the
`authentication code to a verifier.
`In another aspect of the invention, an authentication
`method includes generating a master Seed, Sharing the
`master Seed between a token and a server, deriving a verifier
`Seed from the master Seed using a key derivation function,
`and transmitting an authentication code responsive to the
`verifier seed.
`
`15
`
`6
`The server 104 generates a verifier seed Sassociated with
`a verifier 108. The server 104 generates the verifier seed S.
`by using a key derivation function “KDF.” Key derivation
`functions are well known in the field of encryption relating
`to user-provided passwords. User-provided passwords are
`generally not directly useful as an encryption key in con
`ventional cryptosystems. Systems that use passwords as a
`basis for encryption generally derive an encryption key from
`the password using a key derivation function. Key deriva
`tion 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, pseudo
`random functions, and So on.
`Key derivation functions typically combine the password
`with other information, referred to as a salt. The Salt need not
`be a Secret value. 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 deri
`Vation 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.
`In one embodiment, a key derivation function called
`PBKDF2 is used to implement the invention. PBKDF2 uses
`the message authentication code HMAC-SHA-1, which is a
`message authentication code based on the SHA-1 hash
`function. HMAC-SHA-1 takes two arguments as input. The
`first argument is an encryption key, and the Second argument
`is text that is encrypted by the encryption key. HMAC
`SHA-1 has a variable encryption key length and produces a
`20-octet (160-bit) output value. When PBKDF2 uses the
`underlying function HMAC-SHA-1, it provides two inputs
`to HMAC-SHA-1, and FMAC-SHA-1 provides a 160-bit
`output in response.
`The key derivation function PBKDF2 has as inputs a
`password (P), a Salt (S), an iteration count (c), and a length
`(Len) in octets (8-bit bytes). PBKDF2 computes each block
`of derived output independently by applying the underlying
`function (HMAC-SHA-1) for (c) iterations. A block is the
`number of bits produced as output by the underlying func
`tion, which is 160 bits for HMAC-SHA-1. On the first
`iteration, the password (P) is the first argument to the
`underlying function, and the Salt (S) concatenated with the
`block number is the Second argument to the underlying
`function. The underlying function encrypts the Salt concat
`enated with the block number using the password as the
`encryption key. In Subsequent iterations, the result of the
`previous iteration is passed as the Second argument to the
`underlying function, with the password again used as the
`encryption key. The results of all the iterations are com
`bined, using the exclusive-or operation to produce the final
`result.
`In more formal notation, the PBKDF2 key derivation
`function can be described as:
`PBKDF2 (PS,c,i)=U(\xor U\xor . . . \xor U.
`where
`U=PRF(PSINT(i)),
`U=PRF(PU),
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`In the drawings, like reference characters generally refer
`to the Same parts throughout the different views. Also, the
`drawings are not necessarily to Scale, emphasis instead
`generally being placed upon illustrating the principles of the
`invention.
`FIG. 1 is a block diagram of an embodiment of a system
`according to the invention;
`FIG. 2 is a block diagram of an embodiment of a system
`with multiple verifiers according to the invention.
`FIG. 3 is a flowchart of an embodiment of an authenti
`cation method according to the invention;
`FIG. 4 is a block diagram of an embodiment of the
`invention using a token; and
`FIG. 5 is a flowchart of an authentication method accord
`ing to the invention.
`
`25
`
`35
`
`DESCRIPTION
`
`45
`
`50
`
`Referring to FIG. 1, in one embodiment, a master Seed S.
`100 is generated for a device 102. The master seed S. 100
`40
`is a secret that is shared by the device 102 and the server 104.
`In one embodiment, the server 104 may be exclusively a
`Seed distribution Server, and in other embodiments, the
`server 104 is a data server, Such as a file server, web server,
`or authentication Server, that incorporates Seed distribution
`functionality. In one embodiment, the master seed 100 is
`generated randomly, for example by using a Sensor observ
`ing a Sufficiently random physical event. In another embodi
`ment, the master Seed S. 100 is generated by a pseudoran
`dom number generator. In other embodiments the master
`SeedS 100 is generated in other ways that produce a Secret
`number that is statistically difficult to predict.
`The master seed S. 100 is, in various embodiments,
`generated by the device 102, the server 104, or by another
`entity used for seed generation. The master seed S. 100 is
`shared by the device 102 and the server 104, preferably in
`a private manner, for example over a Secure communications
`link. In one embodiment, the device 102 generates the
`master seed S. 100 and shares it with the server 104. In
`another embodiment, the server 104 generates the master
`seed S. 100 and shares it with the device 102. In yet another
`embodiment, another entity, a Seed generator (not shown in
`FIG. 1), generates the master Seed S. 100, and communi
`cates it to either the device 102 or the server 104 for sharing
`with the other. In still another embodiment, the seed gen
`erator communicates the master seed S100 directly to both
`the device 102 and the server 104.
`
`55
`
`60
`
`65
`
`USR Exhibit No. 2025
`
`

`

`US 6,985,583 B1
`
`15
`
`7
`Here, INT (i) is a four-octet encoding of the block number
`i, most Significant octet first, and PRF is the underlying
`function. In the embodiment just described, PRF is HMAC
`SHA-1. It should be clear that other key derivation functions
`would be similarly useful, and various substitutions for the
`Verifier 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
`intended to be within the scope of the invention.
`In one embodiment, the key derivation function PBKDF2
`is used to derive a verifier Seed from a master Seed by using
`the master Seed as the password P, and the concatenation of
`a verifier identifier and a time identifier as the Salt S. The
`inputs to the key derivation function are thus the master
`Seed, and the concatenated verifier identifier and time iden
`tifier. Of course, either the verifier identifier and/or the time
`identifier might not be included, and instead a default value
`used. Because this information Substitutes for the Salt, the
`verifier identifier and the time identifier do not have to be
`Secret, and can be public information. AS further described
`below, the verifier identifier V, includes information about
`the Verifier, and also can include other information, Such as
`a time value.
`In one embodiment, the key derivation function KDF
`25
`takes as inputs the master Seed S. 100 and identifying
`information V, about the verifier 108. The device 102, also
`stores the master seed 100, and has access to the verifier
`identifier information V. The device 102 is therefore able
`to use the same key derivation function KDF to obtain the
`same verifier seed S from the master seed S. 100 and the
`verifier identifier information V.
`To authenticate with the verifier 108, the device 102 uses
`the verifier seed S. that is shared by the device 102 and the
`verifier 108. In one embodiment, the authentication is
`accomplished by the device 102 transmitting the verifier
`seed S. directly to the verifier 108. In another embodiment,
`the authentication is accomplished by the device 102 trans
`mitting a value mathematically derived from the verifier
`seed S. to the verifier 108. The device 102 mathematically
`derives a value from the Verifier Seed St, and transmits the
`derived value from the verifier 108. The derivation, in
`various embodiments, is accomplished using a hash func
`tion, block cipher, message authentication code, or other
`techniques. In one embodiment, the verifier Seed S is, as
`part of the derivation, combined with other information,
`Such as time-dependent information. For example, in one
`embodiment, the device 102 transmits a hash of the verifier
`seed S. In another embodiment, the device 102 transmits a
`derived time-dependent value encrypted using the verifier
`Seed S. as the encryption key. Other 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 verifier seed. For example, U.S.
`Pat. No. 4,720,860, U.S. Pat. No. 4,885,778, U.S. Pat. No.
`4856,062, U.S. Pat. No. 4,998.279, U.S. Pat. No. 5,023,908,
`U.S. Pat. No. 5,058,161, U.S. Pat. No. 5,097.505, U.S. Pat.
`No. 5,237,614, U.S. Pat. No. 5,367,572, U.S. Pat. No.
`5,361,062, U.S. Pat. No. 5,485,519, and U.S. Pat. No.
`5,657,388 describe various systems and methods for authen
`tication using shared Secrets. Such Systems can incorporate
`the System and method of the invention to use a verifier Seed
`as the basis for authentication. AS another example, a
`challenge/response system includes the verifier 108 trans
`mitting a challenge value to the device 102, and the device
`102 encrypting the