`Perlman et al.
`
`US006 17340OB1
`(10) Patent No.:
`US 6,173,400 B1
`(45) Date of Patent:
`Jan. 9, 2001
`
`(54) METHODS AND SYSTEMS FOR
`ESTABLISHING A SHARED SECRET USING
`AN AUTHENTICATION TOKEN
`
`(75) Inventors: Radia J. Perlman, Acton; Stephen R.
`Hanna, Bedford, both of MA (US)
`(73) Assignee: Sun Microsystems, Inc., Palo Alto, CA
`(US)
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(*) Notice:
`
`OTHER PUBLICATIONS
`
`Jablon, David P., “Strong Password-Only Authenticated
`Key Exchange,” Computers Communication Review, AM
`SIGCOMM, vol. 26, No. 5, pp. 5–26, Oct. 1996.
`Kaufman, Charlie, et al., Network Security, Private Com
`munication in a Public World, Prentice-Hall PTR, 1995.
`* cited by examiner
`
`Primary Examiner Thomas R. Peeso
`(74) Attorney, Agent, or Firm-Finnegan, Henderson,
`Farabow, Garrett & Dunner, L.L.P.
`(21) Appl. No.: 09/126,659
`(57)
`ABSTRACT
`(22) Filed:
`Jul. 31, 1998
`A method and System for establishing a shared Secret
`(51) Int. Cl." - G06F 1/26
`between a plurality of devices using an authentication token.
`(52) U.S. Cl. .......................... 713/172; 713/168; 713/171;
`An authentication token is used to establish a shared Secret
`713/182; 713/200; 380/255; 380/278; 380/283
`between a local device and a remote device to provide user
`authentication, data encryption, and integrity protection. The
`(58) Field of Search ..................................... 713/172, 168,
`authentication token may be used in a variety of ways to
`713/171, 182, 185, 200, 201; 380/255,
`authenticate a user. First, a time-synchronized authentication
`278, 283
`token can generate a first character String that is communi
`cated to a WorkStation. The WorkStation can manipulate the
`first character String to generate a Second character String
`and Send the Second character String to a Server. The Server
`then compares the Second character String with a plurality of
`possible matching character String values and determines the
`first character String. In another implementation, a challenge
`from a Server can be received and processed by a challenge
`response authentication token to generate a character String.
`The generated character String is then communicated to the
`WorkStation to establish a shared Secret. A Smart card may
`also be used to establish a shared Secret between a local
`device and a remote device using Similar techniques.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4.924,378 * 5/1990 Hershey et al. ..................... 713/201
`5,241,599
`8/1993 Bellovin et al. ....................... 380/21
`5,371,692 * 12/1994 Draeger et al. ...
`... 702/122
`5,416,842
`5/1995 Aziz ....................................... 380/30
`5,448,045 * 9/1995 Clark .....
`... 235/382
`5,455.953 * 10/1995 Russell ..............
`... 710/266
`5,491,752
`2/1996 Kaufman et al. ...................... 380/30
`5,602,918
`2/1997 Chen et al. ............................ 380/21
`5,892,902
`4/1999 Clark .................................... 395/187
`FOREIGN PATENT DOCUMENTS
`O 566 811 A1 10/1993 (EP).
`
`73 Claims, 15 Drawing Sheets
`
`
`
`
`
`AUTHENTCATION
`TOKEN
`
`serie
`WORKSTATION
`
`Ex. 2006, p. 1
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 1 of 15
`
`US 6,173,400 B1
`
`s
`
`
`
`Z
`O
`H.
`C
`9
`H
`Z
`LL
`He
`C)
`CC
`
`Ex. 2006, p. 2
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 2 of 15
`
`US 6,173,400 B1
`
`
`
`PROVIDING AN
`AUTHENTICATION
`TOKEN
`
`UTILIZING THE
`AUTHENTICATION
`TOKEN TO
`ESTABLISHA
`SHARED SECRET
`
`FIG. 2
`
`Ex. 2006, p. 3
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 3 of 15
`
`US 6,173,400 B1
`
`
`
`
`
`START
`
`DISPLAY
`300 CHARACTER STRING
`ON TIME
`SYNCHRONIZED
`TOKEN
`
`310 ENTER CHARACTER
`STRING INTO
`WORKSTATION
`
`
`
`
`
`320
`
`GENERATE HASH OF
`CHARACTER STRING
`
`
`
`330
`
`SEND HASH OF
`CHARACTER STRING
`TO SERVER
`
`SERVER COMPUTES
`HASH OF EACH OF A
`PLURALITY OF
`ACCEPTABLE
`CHARACTER STRING
`VALUES AND
`COMPARESTO
`RECEIVED HASH OF
`CHARACTER STRING
`
`350
`
`360
`
`NO
`
`FAILURE
`
`
`
`DOES
`RECEIVED HASH
`OF STRING
`MATCH HASH OF
`ONE ACCEPTABLE
`VALUE2
`
`Yes
`
`USE FUNCTION OF
`CHARACTER STRING 370
`VALUE AS SHARED
`SECRET BETWEEN
`WORKSTATION AND
`SERVER
`
`FIG. 3a
`
`Ex. 2006, p. 4
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 4 of 15
`
`US 6,173,400 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`345
`
`SERVER COMPUTES
`HASH OF EACH OF A
`PLURALITY OF
`ACCEPTABLE
`CHARACTER STRING
`VALUES AND
`COMPARESTO
`RECEIVED BITS OF
`HASH OF
`CHARACTER STRING
`
`355
`
`360
`
`No
`
`FAILURE
`
`365
`
`
`
`375
`
`SERVER SENDS
`Yes | INSTRUCTIONS
`TO
`WORKSTATION
`TO
`DISAMBIGUATE
`
`
`
`
`
`DOES
`RECEIVED BITS
`OF HASH OF
`STRING MATCH
`HASH OF AN
`ACCEPTABLE
`VALUEP
`
`Yes
`
`DOES
`RECEIVED BITS
`OF HASH OF
`STRING MATCH
`MORE THAN
`ONE HASH OF
`ACCEPTABLE
`VALUEP
`
`No
`
`370
`
`USE FUNCTION OF
`CHARACTER STRING
`VALUE AS SHARED
`SECRET BETWEEN
`WORKSTATION AND
`SERVER
`
`START
`
`
`
`DISPLAY
`300 CHARACTER STRING
`ON TIME
`SYNCHRONIZED
`TOKEN
`
`310 ENTER CHARACTER
`STRING INTO
`WORKSTATION
`
`320
`
`GENERATE HASH OF
`CHARACTER STRING
`
`335
`
`SEND LIMITED
`NUMBER OF BITS OF
`HASH OF
`CHARACTER STRING
`TO SERVER
`
`FIG. 3b
`
`Ex. 2006, p. 5
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 5 of 15
`
`US 6,173,400 B1
`
`START
`
`
`
`DISPLAY
`400 CHARACTER STRING
`ON TIME
`SYNCHRONIZED
`TOKEN
`
`410 ENTER CHARACTER
`STRING INTO
`WORKSTATION
`ALONG WITH PN
`
`
`
`420 SENERATEFASHOF
`CHARACTER STRING
`AND PN
`h(CHARACTER
`STRINGPIN)
`
`
`
`430 SEND h(CHARACTER
`STRINGPIN) TO
`SERVER
`
`SERVER COMPUTES 440
`HASH OF EACH OFA
`PLURALITY OF
`ACCEPTABLE
`CHARACTER STRING
`VALUES
`CONCATENATED WITH
`PIN AND COMPARES
`TO h(CHARACTER
`STRINGPIN)
`
`460
`
`No
`
`FAILURE
`
`450
`
`DOES
`h(CHARACTER
`STRINGPIN)
`MATCH HASH OF ONE
`ACCEPTABLE VALUE
`CONCATENATED
`WITH PIN?
`
`Yes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`USE FUNCTION OF
`CHARACTER STRING 470
`VALUE AND PNAS
`SHARED SECRET
`BETWEEN
`WORKSTATION AND
`SERVER
`
`FG. 4a
`
`Ex. 2006, p. 6
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 6 of 15
`
`US 6,173,400 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SERVER COMPUTES
`HASH OF EACH OFA
`PLURALITY OF
`ACCEPTABLE
`CHARACTER STRING
`VALUES CONCATENATED
`WITH PIN AND
`COMPARESTO
`RECEIVED BITS OF
`h(CHARACTER STRINGPIN)
`
`
`
`455
`
`DOES
`RECEIVED BITS
`OF h(CHARACTER STRING
`PIN) MATCH HASH OF
`ACCEPTABLEVALUE
`CONCATENATED
`WITH PIN?
`
`445
`
`460
`
`No
`
`FAILURE
`
`Yes
`
`465
`
`
`
`475
`
`DOES
`RECEIVED BITS
`OF h(CHARACTER
`STRINGPIN) MATCH
`MORE THAN
`ONE ACCEPTABLE
`VALUE
`
`Yes
`
`SERVER SENDS
`INSTRUCTIONS
`TO
`works.ATION
`DISAMBIGUATE
`
`NO
`
`
`
`USE FUNCTION OF
`CHARACTER STRING 470
`VALUE AND PNAS
`SHARED
`SECRET BETWEEN
`WORKSTATION AND
`SERVER
`
`START
`
`
`
`DISPLAY
`400 CHARACTER STRING
`ON TIME
`SYNCHRONIZED
`TOKEN
`
`
`
`410 ENTER CHARACTER
`STRING INTO
`WORKSTATION
`ALONG WITH PIN
`
`420 GENERATE HASH OF
`CHARACTER STRING
`AND PIN
`(h(CHARACTER
`STRINGPIN))
`
`435
`
`SEND LIMITED
`NUMBER OF BITS OF
`h(CHARACTER
`STRINGPIN)
`TO SERVER
`
`FIG. 4b
`
`Ex. 2006, p. 7
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 7 of 15
`
`US 6,173,400 B1
`
`DISPLAY CHARACTER 500
`STRING ON TIME
`SYNCHRONIZED
`TOKEN
`
`510
`
`ENTER CHARACTER
`STRING INTO A
`WORKSTATION
`
`
`
`
`
`
`
`DISAMBIGUATE FIRST 520
`SHARED SECRET
`BETWEEN THE
`WORKSTATION ANDA
`SERVER
`
`IMPLEMENT SHARED SECRET
`KEY EXCHANGE PROTOCOL.
`WITH CHARACTER STRING
`BETWEEN WORKSTATION AND
`SERVER
`
`530
`
`540
`
`
`
`STRONGER SHARED SECRET
`ESTABLISHED USING SHARED
`SECRE KEY EXCHANGE
`PROTOCOL BETWEEN
`WORKSTATION AND SERVER
`
`
`
`
`
`
`
`
`
`F.G. 5a
`
`Ex. 2006, p. 8
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 8 of 15
`
`US 6,173,400 B1
`
`START
`
`
`
`
`
`
`
`
`
`500
`
`510
`
`DISPLAY CHARACTER
`STRING ON TIME
`SYNCHRONIZED
`TOKEN
`
`ENTER CHARACTER
`STRING INTO A
`WORKSTATION
`
`IMPLEMENT SHARED SECRETKEY 527
`EXCHANGE PROTOCOL WITH
`CHARACTER STRING BETWEEN
`WORKSTATION ANDA SERVER
`WHILE DISAMBIGUATING FIRST
`SHARED SECRET
`
`540
`
`
`
`
`
`
`
`STRONGER SHARED SECRET
`ESTABLISHED USING SHARED
`SECRET KEY EXCHANGE
`PROTOCOL BETWEEN
`WORKSTATION AND SERVER
`
`
`
`
`
`
`
`
`
`F.G. 5b.
`
`Ex. 2006, p. 9
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 9 of 15
`
`US 6,173,400 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISPLAY CHARACTER 500
`STRING ON TIME
`SYNCHRONIZED
`OKEN
`
`
`
`
`
`510
`
`525
`
`ENTER CHARACTER
`STRING INTO A
`WORKSTATION
`
`IMPLEMENT SHARED
`SECRET KEY EXCHANGE
`PROTOCOL WITH
`CHARACTER STRING
`BETWEEN WORKSTATION
`AND A SERVER
`
`535
`
`540
`
`DISAMBIGUATE SHARED
`SECRET BETWEEN
`WORKSTATION AND SERVER
`
`STRONGER SHARED SECRET
`ESTABLISHED USNG SHARED
`SECRET KEY EXCHANGE
`PROTOCOL BETWEEN
`WORKSTATION AND SERVER
`
`FIG. 5C
`
`Ex. 2006, p. 10
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 10 Of 15
`
`US 6,173,400 B1
`
`
`
`
`
`
`
`600
`
`SEND CHALLENGE
`FROM SERVER TO
`USERWORKSTATION
`
`INPUT CHALLENGE
`NTO A CHALLENGE
`RESPONSE
`AUTHENTICATION
`TOKEN
`
`
`
`
`
`
`
`
`
`62O
`
`PROCESS CHALLENGE TO
`GENERATE ARESPONSE
`
`630
`
`640
`
`ENTER RESPONSE INTO USER
`WORKSTATION
`
`USE RESPONSE AS SHARED
`SECRET BETWEEN USER
`WORKSTATION AND SERVER
`
`FIG. 6
`
`Ex. 2006, p. 11
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 11 of 15
`
`US 6,173,400 B1
`
`
`
`SEND CHALLENGE
`FROM SERVERTO
`USERWORKSTATION
`
`
`
`
`
`
`
`
`
`INPUT CHALLENGE
`NTO A CHALLENGE
`RESPONSE
`AUTHENTCATION
`TOKEN
`
`700
`
`710
`
`720
`
`PROCESS CHALLENGE TO
`GENERATE ARESPONSE
`
`730
`
`740
`
`ENTER RESPONSE INTO USER
`WORKSTATIONALONG WITH PIN
`
`USE FUNCTION OF RESPONSE
`AND PNAS SHARED SECRET
`BETWEEN USERWORKSTATION
`AND SERVER
`
`
`
`
`
`
`
`FIG. 7
`
`Ex. 2006, p. 12
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 12 of 15
`
`US 6,173,400 B1
`
`
`
`SEND CHALLENGE
`FROM SERVERTO
`USERWORKSTATION
`
`INPUT CHALLENGE
`INTO AUTHENTICATION
`TOKEN
`
`PROCESS CHALLENGE
`TO GENERATE
`RESPONSE
`
`830
`
`ENTER RESPONSENTO
`WORKSTATION
`
`840
`
`850
`
`IMPLEMENT SHARED SECRET
`KEY EXCHANGE PROTOCOL
`WITH RESPONSE BETWEEN
`WORKSTATION AND SERVER
`
`SHARE SECRET DETERMINED
`USING SHARED SECRET KEY
`EXCHANGE PROTOCOL
`BETWEENUSERWORKSTATION
`AND SERVER
`
`FIG. 8
`
`Ex. 2006, p. 13
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 13 Of 15
`
`US 6,173,400 B1
`
`
`
`PROVIDING ASMART
`CARD
`
`COMMUNICATING
`DATA FROM THE
`SMART CARD TO A
`LOCAL DEVICE
`
`UTILIZING THE DATA
`TO ESTABLISHA
`SHARED SECRET
`BETWEEN THE LOCAL
`AND AREMOTE
`DEVICE
`
`FIG. 9a
`
`Ex. 2006, p. 14
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 14 of 15
`
`US 6,173,400 B1
`
`
`
`PROVIDING ASMART
`CARD
`
`ESTABLISHINGA
`SHARED SECRET
`BETWEEN THE SMART
`CARD AND AREMOTE
`DEVICE
`
`COMMUNICATING
`SHARED SECRET
`FROM THE SMART
`CARD TO ALOCAL
`DEVICE
`
`FIG. 9b
`
`Ex. 2006, p. 15
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`U.S. Patent
`
`Jan. 9, 2001
`
`Sheet 15 Of 15
`
`US 6,173,400 B1
`
`
`
`PROVIDING ASMART
`CARD
`
`ESTABLISHINGA
`SHARED SECRET
`BETWEEN THE SMART
`CARD AND AREMOTE
`DEVICE
`
`UTILIZING THE SMART
`CARD AND SHARED
`SECRET IN
`TRANSACTIONS
`BETWEEN THE
`REMOTE DEVICE AND
`A LOCAL DEVICE
`
`FIG. 9C
`
`Ex. 2006, p. 16
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`1
`METHODS AND SYSTEMS FOR
`ESTABLISHING A SHARED SECRET USING
`AN AUTHENTICATION TOKEN
`
`FIELD OF THE INVENTION
`The present invention relates generally to Secure
`communications, and more particularly, to methods and
`Systems for establishing a shared Secret between devices
`connected over a communication medium using an authen
`tication token to provide user authentication, data
`encryption, and integrity protection.
`
`RELATED ART
`Traditionally, network users Simply enter a user name and
`a password to gain access to network resources and other
`users of the network. After entering a user name and
`password to gain access to the network, a user usually Sends
`and receives data in the clear during the network Session
`without any protective measures. That is, the data is sent
`over a communication channel "as-is' without any level of
`Security protection. This traditional method of gaining
`access to and communicating over a network presents many
`problems with regard to the integrity of the network.
`First, a user name and password only provides a minimal
`level of user authentication to access the network. If the
`password is simple (e.g., the user's birth date) a hacker can
`easily determine the user's password and access the network
`with this information assuming the user's name. Second,
`Sending and receiving data in the clear makes the network
`Susceptible to eavesdroppers. An eavesdropper can intercept
`data Sent over a network communication channel and use it
`for improper purposes Such as hijacking the user's Session.
`Moreover, data Sent in the clear is Susceptible to malicious
`Software that can modify the data (e.g., delete or change bits)
`or copy the data to a hidden peripheral (e.g., copy data to a
`remote storage device unknown to the user).
`Many users currently rely on authentication tokens to
`provide an additional level of user authentication based on
`“Something you have” (versus “Something you know', like
`a password). Authentication tokens are physical devices that
`people carry while passwords are simply remembered.
`There are a variety of authentication tokens currently avail
`able in the marketplace. These authentication tokens include
`time-synchronized authentication tokens, challenge
`response authentication tokens, and Smart cards.
`A time-synchronized authentication token typically dis
`plays a different character String (i.e., password) at
`approximate, predetermined intervals of time (e.g., every
`minute). In this instance, for example, a server and token
`Synchronize (within a predetermined tolerance) using the
`time of day in minutes to produce a character String (e.g., the
`time of day in minutes encrypted with a Secret code known
`only to the token and the server). A user then enters the
`current character String displayed on the token into a work
`Station to authenticate the user to a Server. The WorkStation
`Sends the character String to the Server in the clear. The
`Server checks the character String against a list and then
`determines whether the character String could have been
`generated by the token in the last few minutes (to allow for
`delay in typing and transmission).
`A challenge-response token is a device with a keypad,
`Such as a card. Traditionally, when authenticating using this
`token, for example, the user first contacts a Server which
`generates a challenge (e.g., a character String) and sends it
`to the user via a local computer. The user then enters the
`challenge into the token which processes the challenge and
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,173,400 B1
`
`2
`displays a response (e.g., another character String). The user
`Sends the response to the Server which checks the response
`against a predetermined character String value. If there is a
`match, the Server grants the requested access.
`A Smart card is a device with a central processing unit
`(CPU) and memory. When inserted or positioned near a
`Smart card reader, the card communicates with the reader to
`transfer data or perform desired functions. The Smart card
`may have any shape. For instance, the Smart card may have
`the shape of a credit card or a pendant worn on an article of
`clothing.
`Any of the aforementioned authentication tokens may
`require an authentication code for operation. The activation
`code may be in the form of a personal identification number
`(PIN) or a biometric. For example, to operate a time
`Synchronized authentication token, a user may be required to
`enter in a character String or touch an area of the token with
`their thumb. With a challenge response token, an activation
`code may be required to activate the token before entering
`the challenge. Finally, certain Smart cards may require a user
`to enter an activation code to “unlock” information Stored
`therein (e.g., character String). Usually, after Some number
`of wrong guesses, the card “locks' itself and will not permit
`access to Stored information. If the information is accessible,
`the Smart card reader can communicate it to a WorkStation to
`use for authentication purposes.
`Typically, with time-synchronized authentication tokens,
`challenge-response authentication tokens, and Smart cards,
`the character String values generated therein are transferred
`between a user's WorkStation and a remote computer in the
`clear. As a result, all communications between the user and
`the remote terminal become Susceptible to hijackers and
`eavesdroppers who can easily decipher the unprotected code
`and intercept communicated information.
`In conventional use, the only purpose for authentication
`tokens is user authentication. No Session key-a quantity
`used to encrypt or decrypt information during a Session-is
`established and therefore no integrity protection or confi
`dentiality is provided for the Session. In addition, there is no
`way for the client to know that it is talking to the correct
`Server. The character String value generated by an authen
`tication token usually contains less than 32bits of significant
`information. This allows for an inexpensive display and
`avoids requiring users to enter long character Strings.
`However, it makes the System more Vulnerable to various
`attackS.
`Shared Secret key exchange protocols allow two comput
`erS with a shared Secret to establish a stronger shared Secret
`without risking attacks on the Shared Secret. The Stronger
`shared Secret may then be used to encrypt data exchanged
`between them. These protocols are commercially available
`and include the Bellovin-Merritt shared secret key exchange
`protocol and the Strong Password only Authentication Key
`Exchange (SPEKE). A description of several shared secret
`key exchange protocols is included in Kaufman, Perlman,
`and Speciner, Network Security. Private Communication in
`a Public World, Prentice Hall PTR (1995) (hereinafter
`“Network Security”). The Bellovin-Merritt protocol is dis
`cussed in Network Security, pp. 249-253 and described in
`U.S. Pat. No. 5,241,599. A discussion of SPEKE can be
`found in D. Jablon, “Strong Password only Authentication
`Key Exchange,” Computer Communication Review, ACM
`SIGCOMM, vol. 26, no. 5, pp. 5-26, October 1996. Shared
`Secret key exchange protocols Strengthen password-based
`Systems by avoiding Sending the password in the clear.
`Currently, shared Secret key exchange protocols are not used
`
`Ex. 2006, p. 17
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`3
`with authentication tokens to enhance Session Security.
`Therefore, there is a need for a solution that involves both
`authentication tokens and shared Secret key exchange pro
`tocols to provide adequate user authentication, data
`encryption, and integrity protection.
`
`SUMMARY OF THE INVENTION
`Based on the foregoing shortcomings, it is desirable to
`establish a shared Secret between parties communicating
`over a network using an authentication token to provide
`adequate user authentication, data encryption, and integrity
`protection.
`Methods and Systems consistent with the present inven
`tion meet the foregoing desires. Specifically, a method for
`establishing a shared Secret among a plurality of devices,
`comprises the Steps of providing an authentication token;
`and utilizing the authentication token to establish a shared
`Secret among the plurality of devices.
`A System for establishing a shared Secret among a plu
`rality of devices comprises an authentication token; a local
`device; and a remote device, wherein the authentication
`token is used to establish a shared Secret between the local
`device and the remote device.
`Additional desires, features and advantages of the inven
`tion are set forth in the following description, apparent from
`the description, or may be learned by practicing the inven
`tion.
`Both the foregoing general description and the following
`detailed description are exemplary and explanatory and are
`intended to provide further explanation of the invention as
`claimed.
`
`15
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The accompanying drawings, which are incorporated in
`and constitute a part of the Specification, illustrate presently
`preferred embodiments of the invention and, together with
`the preceding general description and the following detailed
`description, eXplain the principles of the invention.
`In the drawings:
`FIG. 1 illustrates a system for establishing a shared secret
`using an authentication token consistent with the present
`invention;
`FIG. 2 illustrates a method for establishing a shared secret
`using an authentication token consistent with the present
`invention;
`FIG. 3a illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token and a
`hash function consistent with the present invention;
`FIG. 3b illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token, a
`hash function, and a limited number of character String bits
`consistent with the present invention;
`FIG. 4a illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token, a
`hash function and a PIN consistent with the present inven
`tion;
`FIG. 4b illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token, a
`hash function, a PIN, and a limited number of character
`String bits consistent with the present invention;
`FIG. 5a illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token and a
`shared Secret key exchange protocol consistent with the
`present invention;
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,173,400 B1
`
`4
`FIG. 5b illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token and a
`shared Secret key exchange protocol consistent with an
`alternative implementation of the present invention;
`FIG. 5c illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token and a
`shared Secret key exchange protocol consistent with yet
`another alternative implementation of the present invention;
`FIG. 6 illustrates a method for establishing a shared secret
`using a challenge-response authentication token consistent
`with the present invention;
`FIG. 7 illustrates a method for establishing a shared secret
`using a challenge-response authentication token and a PIN
`consistent with the present invention;
`FIG. 8 illustrates a method for establishing a shared secret
`using a challenge-response authentication token and shared
`Secret key exchange protocol consistent with the present
`invention;
`FIG. 9a illustrates a method for establishing a shared
`Secret between a local device and a remote device using a
`Smart card consistent with the present invention;
`FIG. 9b illustrates a method for establishing a shared
`Secret between a Smart card and a remote device and Sharing
`the Secret with a local device; and
`FIG. 9c illustrates a method for establishing a shared
`Secret between a Smart card and a remote device and using
`the Smart card for transactions between the remote device
`and a local device.
`
`DETAILED DESCRIPTION
`
`Reference will now be made in detail to the construction
`and operation of preferred embodiments consistent with the
`present invention that are illustrated in the accompanying
`drawings. In those drawings, like elements and operations
`are designated with the same reference numbers.
`Methods and Systems consistent with the present inven
`tion establish a shared Secret between parties communicat
`ing over a network to provide adequate mutual
`authentication, data encryption, and integrity protection.
`This is accomplished in a variety of ways as explained in
`detail below. In one embodiment, for example, a shared
`Secret can be established using an authentication token that
`generates a character String and is approximately time
`Synchronized with a remote device (e.g., server). The char
`acter String, for example, is a password based on the time of
`day encrypted with a Secret code or a random number. The
`character String is communicated to a local device (e.g.,
`workstation) where it can be modified using a predetermined
`function to produce a result (i.e., a Second character String).
`The result is sent to the remote device. Once received, the
`remote device compares the result with a finite number of
`possible matching character String values relating to the
`initial character String generated by the authentication token.
`The remote device and the user's local device can then Share
`the matching value or a function of the matching value as a
`Secret to encrypt and enhance the integrity of information
`transferred therebetween, and/or perform mutual authenti
`cation. Alternatively, the remote and local devices may use
`their shared Secret to establish a larger (and thus more
`Secure) Secret, which may be used to encrypt data, enhance
`the integrity of information transferred therebetween, and/or
`perform mutual authentication.
`FIG. 1 illustrates a system 100 for establishing a shared
`Secret using an authentication token consistent with the
`present invention. System 100 includes a workstation 120,
`
`Ex. 2006, p. 18
`Amazon.com, Inc. v. Dynapass IP Holdings LLC, IPR2024-00283
`
`
`
`S
`servers 130, 140, and 150, a network 160, and an authenti
`cation token 170. One skilled in the art will appreciate that
`system 100 may include an unlimited amount of
`WorkStations, Servers, and other network components.
`Workstation 120 is a computer capable of sending data to
`and receiving data from network 160. Workstation 120
`includes a processor, memory, and input/output devices to
`facilitate human interaction (not shown). Workstation 120
`includes Software for implementing the authentication tech
`niques described herein, Such as encryption Software.
`Moreover, workstation 120 includes a modem (not shown)
`or other communications device to transfer data over net
`work 160. One skilled in the art will appreciate that work
`Station 120 may have any configuration consistent with the
`embodiments described herein. For example, WorkStation
`120 may rely on software stored in an external memory to
`implement the described authentication techniques.
`Servers 130, 140, and 150 are included in FIG. 1 to
`illustrate the ability of workstation 120 to communicate with
`a plurality of network devices for authentication purposes.
`Each Server is a computer capable of Sending data to and
`receiving data from network 160. Each server can be con
`figured for different applications and controlled by different
`entities. For example, a bank may operate server 130 to
`allow remote access to customer financial data and a Service
`oriented company may operate Server 140 to permit remote
`access to customer account information. In addition, a
`manufacturing company may operate Server 150 to facilitate
`customer access to order Status information. Each of these
`Servers can Store and control access to privileged informa
`tion. To this end, one or more authentication techniques as
`described herein are used to ensure that only intended parties
`receive the privileged information.
`Network 160 is a communication medium, Such as the
`Internet, that routes information between devices connected
`thereto. Although FIG. 1 shows computers connected to
`network 160, other components with communication capa
`bilities may be connected to network 160 as well. For
`simplicity, network 160 is often referred to herein as the
`Internet to illustrate how authentication tokens are used to
`authenticate users of the Internet. Nevertheless, authentica
`tion techniques consistent with the present invention may be
`used on other WANs as well as local area networks (LANs),
`network protocols, and other communication media.
`Authentication token 170 may include input (e.g., keypad,
`light pen, etc.) and output capabilities (e.g., LCD display,
`Speaker, etc.). The input capabilities allow information, Such
`as character Strings, to be communicated to authentication
`token 170. The output capabilities allow information to be
`communicated to a user or another device. Authentication
`token may be time-synchronized with a remote device (i.e.,
`time-synchronized token), configured to process character
`Strings entered on its keypad to produce a response (i.e.,
`challenge-response token), or designed to store information
`accessible only through an appropriate reader device (i.e.,
`Smart card). To facilitate these operations, authentication
`token 170 preferably includes a processor and a memory
`(not shown). In addition, authentication token 170 may be
`configured to require an activation code (e.g., PIN or
`biometric) for operation. Although authentication token 170
`may or may not be physically connected to WorkStation 120,
`it is included in system 100 to implement authentication
`techniques described in detail below.
`FIG. 2 illustrates a method for establishing a shared secret
`using an authentication token consistent with the present
`invention. The method begins with providing an authenti
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,173,400 B1
`
`6
`cation token (step 200). The authentication token can be a
`time-synchronized token, challenge response token, or any
`token configured to implement the authentication techniques
`described herein. The authentication token is then utilized to
`establish a shared secret (step 220). Authentication tech
`niques for establishing a shared Secret are described below
`with respect to FIGS. 3–8.
`FIG. 3a illustrates a method for establishing a shared
`Secret using a time-synchronized authentication token and a
`hash function consistent with the present invention.
`Traditionally, a user enters a character String into a work
`Station which transmits the character String to a Server in the
`clear. Implementations consistent with the present invention
`do not send the character String in the clear. Rather, these
`implementations use the character String displayed on the
`authentication token to generate a shared Secret between
`communicating parties to provide a reasonable level of
`authentication and a Secure Session.
`First, a character String is generated on a time
`synchronized token 170 (step 300). Preferably, the character
`String is the time of day in minutes encrypted with a Secret
`code known only to the token and the Server. The character
`string is then communicated to workstation 120 (step 310).
`For example, the user can read the character String and
`manually enter it into the WorkStation, or, if connected, the
`WorkStation can read the character String automatically from
`the authentication token. Upon receiving the character
`String, the WorkStation executes a commercially available
`hash program to generate a hash of the character String (i.e.,
`h(character String)) (Step 320). A hash is a cryptographic
`one-way function that takes an arbitrary-sized input and
`yields a fixed-sized output. The WorkStation then sends
`h(character string) to server 130 (step 330).
`To allow for clock skew and delays in typing and
`transmission, the Server will accept any one of Several
`character Strings, based on character Strings the token might
`have displayed in the last Seven minutes or the next three
`minutes (or other suitable values for the number of minutes).
`Because the number of acceptable character Strings is Small,
`it is easy for the Server to compute the hash of each
`acceptable character String and disambiguate a matching
`hash from the computed hashes by comparing each hash to
`the hash received, h(character string) (steps 340 and 350). If
`a match is not found, the authentication attempt fails (Step
`360). If a match is found, the server and workstation use a
`function of the character String (e.g., a hash of the character
`String, the character String itself, or othe