United States Patent (19)
`Kaufman et al.
`
`54) SYSTEM FOR INCREASING THE
`DFFICULTY OF PASSWORD GUESSING
`ATTACKS IN ADISTRIBUTED
`AUTHENTICATION SCHEME EMPLOYING
`AUTHENTICATION TOKENS
`
`(75) Inventors: Charles W. Kaufman, Northborough;
`Radia J. Pearlman, Acton; Morrie
`Gasser, Hopkinton, all of Mass.
`73) Assignee: Digital Equipment Corporation,
`Patent Law Group, Maynard, Mass.
`
`21 Appl. No.: 300,576
`22 Filed:
`Sep. 2, 1994
`Related U.S. Application Data
`63 Continuation of Ser. No. 34,225, Mar. 18, 1993, abandoned.
`(51) Int. Cl. ................................ H04K 1100
`52 U.S. Cl. ................................................ 380/30; 380/25
`58) Field of Search .................................. 380/23, 24, 25,
`380/30
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`3,798,605 3/1974 Feistel ....................................... 380/25
`3.996,449 12/1976 Attanasio et al. ..
`... 235/61.7 R
`4,218,738 8/1980 Matyas et al. ............................ 380/25
`(List continued on next page.)
`OTHER PUBLICATIONS
`1989, Mark, T., et al., "Reducing Risks from Poorly Chosen
`Keys,” University of Cambridge Computer Laboratory,
`from 12th Symposium On Operating System Principles.
`Security Dynamics, Inc., "Kerberos and SecurD,' approxi
`mately Apr. 1992, not published.
`Lomas et al., "Reducing Risks from Poorly Chosen Keys,”
`12th Symposium on Operating System Principles, 1989, pp.
`14-18, place of pub. unknown.
`Tardo et al., "SPX: Global Authentication Using Public Key
`Certificates.” Proceedings of IEEE Symposium Research in
`Security and Privacy, IEEE CS Press, 1991, pp. 232-244,
`
`US00549.1752A
`Patent Number:
`11
`45 Date of Patent:
`
`5,491,752
`Feb. 13, 1996
`
`place of publication unknown.
`Abadi et al., “Authentication and Delegation with
`Smart-Cards,” Oct. 22, 1990, pp. 1-24, place of publication
`unknown.
`Woo et al., "Authentication for Distributed Systems,' from
`Computer of IEEE Computer Society, Jan. 1992, pp. 49-51,
`place of pub. unknown.
`U.S. application Ser. No. 07/875,050, filed Apr. 28, 1992,
`Kaufman et al.
`Primary Examiner Tod R. Swann
`Attorney, Agent, or Firm-A. Sidney Johnston
`(57)
`ABSTRACT
`An improved security system inhibits eavesdropping, dic
`tionary attacks, and intrusion into stored password lists. In
`one implementation, the user provides a workstation with a
`"password', and a "token” obtained from a passive authen
`tication token generator. The workstation calculates a "trans
`mission code' by performing a first hashing algorithm upon
`the password and token. The workstation sends the trans
`mission code to the server. Then, the server attempts to
`reproduce the transmission code by combining passwords
`from a stored list with tokens generated by a second identical
`passive authentication token generatorjust prior to receipt of
`the transmission code. If any password/token combination
`yields the transmission code, the workstation is provided
`with a message useful in communicating with a desired
`computing system; the message is encrypted with a session
`code calculated by applying a different hashing algorithm to
`the password and token. In another embodiment, the work
`station transmits a user name to the authentication server.
`The server verifies the user name's validity, and uses an
`active authentication token generator to obtain a "response'
`to an arbitrarily selected challenge. The server generates a
`session code by performing a hashing algorithm upon the
`response and the password. The server sends the challenge
`and a message encrypted with the session code to the
`workstation. The workstation generates the session code by
`performing the hashing algorithm on the password and the
`received challenge, and uses the session code to decrypt the
`encrypted message. The message is useful in communicat
`ing with a desired computing system.
`
`37 Claims, 7 Drawing Sheets
`
`
`
`
`
`20
`
`WORKSION
`CALCUAESSESSION
`CODE
`
`WORKSTATION
`OECRYPTSESSAGE
`
`BASEDCOMBINATION (of
`RESONSESANt PASSWORE
`
`MESSAGENSBSEQUENT
`
`Amazon.com Exhibit 1008 - Page 1
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`5,491,752
`Page 2
`
`U.S. PATENT DOCUMENTS
`4,227,253 10/1980 Ehrsam et al............................... 375/2
`4,264,782 4/1981 Konheim ................................... 178/22
`4,288,659 9/1981 Atalla ........
`178/2.2.08
`4,386,266 5/1983 Chesarek
`... 235/380
`4,399,323 8/1983 Henry ................................... 178/2.2.14
`4,430,728 2/1984 Beitel et al. ................... 340/825.31 X
`4,626,845 12/1986 Ley ....................................... 380/23 X
`4,661,991 4/1987 Logemann
`340/825.31 X
`4,736,423 4/1988 Matyas ...................................... 380/23
`4.755,940 7/1988 Brachtl et al.
`... 364/408
`4,799,061
`1/1989 Abraham et al. .
`... 3401825.34
`4,815,031
`3/1989 Furukawa ......
`... 380/23 X
`4,868,877 9/1989 Fischer ...................................... 380/25
`4,881,264. 11/1989 Merkle ......
`... 380/25
`4,910,773 3/1990 Hazard et al.
`... 380/21
`4,919,545 4/1990 Yu .............
`380/25
`4,924,515 5/1990 Matyas et al.
`... 380/25
`4,932,056 6/1990 Shamir ...................................... 380/23
`4,965,568 10/1990 Atalla et al. ....................... 340/825.34
`
`4,974,193 11/1990 Beutelspacher ......................... 364/900
`4,993,068 2/1991 Piosenka et al. ......................... 380/23
`5,023,908 6/1991 Weiss ........................................ 380/2.3
`5,029,208 7/1991 Tanaka ....
`380/30 X
`5,050,212 9/1991 Dyson ....................................... 380/25
`5,068,894 11/1991 Hoppe ....................................... 380/23
`5,081,678
`1/1992 Kauf
`al
`380/21
`WWva.
`autman et al.
`5,109,152 4/1992 Takagi et al. ...
`235/380
`5,136,646 8/1992 Haber et al. ....
`... 380/49
`5,136,647 8/1992 Haber et al.
`... 380/49
`5,146,499 9/1992 Geffrotin
`... 380/23
`5,148,479 9/1992 Bird et al. ................................. 380/2.3
`5,163,096 11/1992 Clark et al. ................................. 380/4
`5,201,000 4/1993 Matyas et al. ......
`... 380/30
`5,204,966 4/1993 Wittenberg et al.
`380/25 X
`5,220,604 6/1993 Gasser et al. ..............
`... 380/23
`5,224,163
`6/1993 Gasser et al. ..............
`... 380/30
`5,235,644 8/1993 Gupta et al. ...
`... 380/48
`5,297,206 3/1994 Orton ..........
`... 380/30
`5,315,658 5/1994 Micali ....................................... 380/30
`
`
`
`Amazon.com Exhibit 1008 - Page 2
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 1 of 7
`
`5,491,752
`
`FIG. 1
`(Prior Art)
`
`
`
`PASSWORD
`
`WORK
`STATION
`
`USERNAME
`PASSWORD
`
`is a
`
`------
`
`
`
`USERNAME
`- PASSWORD
`TABLE
`
`
`
`
`
`
`
`--------
`
`EAVES
`DROPPER
`---------
`
`:
`
`SYSTEM
`RESOURCE
`
`Amazon.com Exhibit 1008 - Page 3
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 2 of 7
`
`5,491,752
`
`FG.2
`(Prior Art)
`
`
`
`RECIPIENTS
`PUBLIC
`KEY
`
`
`
`
`
`CPHERTEXT
`MESSAGE
`
`DECRYPTION
`
`Amazon.com Exhibit 1008 - Page 4
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 3 of 7
`
`5,491,752
`
`
`
`LOGEN
`
`
`
`FIG. 3
`(Prior Art)
`
`WORK
`STATION
`
`
`
`
`
`
`
`
`
`
`
`REQUEST FOR
`USER'S PRIVATE
`KEY
`
`
`
`
`
`(WORKSTATION)
`HASH
`
`RECIPIENTS
`PUBLIC
`KEY
`
`
`
`
`
`
`
`
`
`
`
`(WORKSTATION)
`DECRYPTION
`
`USERS
`PRIVATE
`KEY
`
`PRIVATE
`KEY
`(ENCRYPTED
`W/SECRET
`KEY)
`
`
`
`USERS PRIVATE
`KEY (ENCRYPTED
`WISECRET
`KEY
`
`Amazon.com Exhibit 1008 - Page 5
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 4 of 7
`
`5,491,752
`
`USER
`PASSWORD
`
`FG. 4
`(Prior Art)
`
`SHARED
`SECRET
`KEY
`
`
`
`
`
`
`
`
`
`
`
`(KERBEROS)
`TICKET
`GENERATOR
`
`(KERBEROS)
`TICKET
`ENCRYPTION
`
`
`
`
`
`(WORKSTATION)
`TICKET
`
`DECRYPTION
`
`PASSWORD
`
`(WORKSTATION)
`HASH
`
`(WORKSTATION)
`SHARED SECRET
`KEY
`
`
`
`
`
`
`
`Amazon.com Exhibit 1008 - Page 6
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 5 of 7
`
`5,491,752
`
`FGS
`
`SOO
`
`506 COMMUNICATION
`EQUIPMENT
`
`PRINTERS
`
`50
`
`SECONDARY
`COMPUTERS
`
`51
`
`58
`
`WORK-
`STATION
`
`
`
`516
`
`AUTHENTICATION
`SERVER
`
`WORK
`STATION
`
`AUTHENTCATION
`TOKEN
`GENERATOR
`
`503
`
`?
`t
`
`514
`
`522
`
`Amazon.com Exhibit 1008 - Page 7
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 6 of 7
`
`5,491,752
`F.G. 6
`
`
`
`
`
`
`
`
`
`
`
`604
`WORKSTATION RECEIVES
`USERNAME, PASSWORD,
`AND TOKEN
`
`606
`
`608
`
`610
`
`WORKSTATION
`CALCULATES
`TRANSMISSION CODE
`
`WORKSTATION SENDS
`TRANSMISSION CODE
`TO SERVER
`
`SERVER COMPUTES
`POSSIBLE TOKENS
`
`612
`
`
`
`
`
`
`
`
`
`
`
`
`
`SERVERENCRYPTS
`MESSAGE WITH
`SESSION CODE
`
`SERVER SENDS
`ENCRYPTED MESSAGE
`TO WORKSTATION
`
`WORKSTATION
`CALCULATESSESSION
`CODE
`
`WORKSTATION
`DECRYPTS
`MESSAGE
`
`622
`
`624
`
`626
`
`628
`
`630
`
`SERVER OBTANS
`PASSWORD
`
`WORKSTATIONUSES
`MESSAGE IN SUBSEQUENT
`COMMUNICATIONS
`
`614
`
`SERVER ATTEMPTS TO
`REPRODUCE
`TRANSMISSION CODE
`
`616
`
`
`
`620
`
`SERVER COMPUTES
`SESSION CODE
`
`618
`
`NO
`
`DENYACCESS
`
`632
`
`Amazon.com Exhibit 1008 - Page 8
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`U.S. Patent
`
`Feb. 13, 1996
`
`Sheet 7 of 7
`
`5,491,752
`
`702
`
`WORKSTATION
`RECEIVES
`USERNAME
`
`704
`
`706
`
`WORKSTATION SENDS
`USERNAME TO
`AUTHENTICATION SERVICE
`708
`
`SERVER SELECTs
`CHALLENGE
`
`SERVER OBTAINS
`RESPONSE
`
`SERVER OBTAINS
`PASSWORD
`
`710
`
`72
`
`714
`
`SERVER CALCULATES
`SESSION CODE WITH
`HASHED COMBINATION OF
`RESPONSES AND PASSWORD
`
`
`
`
`
`
`
`716
`
`SERVERENCRYPTS
`MESSAGE WITH SESSION
`CODE
`
`FIG. 7
`
`700
`
`1.
`
`WORKSTATION
`CALCULATESSESSION
`CODE
`
`WORKSTATION
`DECRYPTS MESSAGE
`
`720
`
`722
`
`724
`
`
`
`
`
`WORKSTATIONUSES
`MESSAGE IN SUBSEQUENT
`COMMUNICATIONS
`
`
`
`
`
`718
`
`726
`
`SERVER SENDS
`ENCRYPTED MESSAGE
`TO WORKSTATION
`
`
`
`719
`WORKSTATION DISPLAYS CHALLENGE
`TOUSER USERINPUTS CHALLENGE
`INTO TOKENGENERATOR AND
`RECEIVES RESPONSE; RESPONSE
`IS INPUT INTO WORKSTATION
`
`Amazon.com Exhibit 1008 - Page 9
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`5,491,752
`
`1.
`SYSTEM FOR INCREASING THE
`DFFCULTY OF PASSWORD GUESSING
`ATTACKS IN A DISTRIBUTED
`AUTHENTCATION SCHEME EMPLOYING
`AUTHENTICATION TOKENS
`
`This application is a file-wrapper continuation, of appli
`cation Ser. No. 08/034,225, filed Mar. 18, 1993, which is
`now abandoned.
`
`BACKGROUND OF INVENTION
`The present invention relates to an improved method by
`which a user or other principal in a computing system may
`authenticate to a computer system and establish a shared
`secret key for the protection of subsequent messages, with
`reduced risk that the information in question will be improp
`erly obtained or modified by a would-be intruder or
`imposter.
`In one aspect, the invention pertains to a method by which
`a server in a distributed computing system may authenticate
`a user, authorizing access by the user to specified system
`resources and establishing a shared secret key with which to
`protect subsequent messages. In a specific embodiment, the
`invention pertains to a method by which an authentication
`server in a distributed computing system may transmit an
`authentication "ticket' to a user, authorizing access by the
`user to specified system resources. In a related aspect, the
`invention pertains to a method of increasing the difficulty of
`password guessing attacks in a distributed authentication
`scheme that employs authentication tokens.
`
`10
`
`20
`
`25
`
`30
`
`2
`for that account. That is, the user name and password, taken
`together, serve to identify and "authenticate" the user at
`login time.
`
`DICTIONARY ATTACKS ON PASSWORD
`SECURITY
`An authentication system based solely on passwords and
`user names is open to attack by would-be intruders. User
`names often are not difficult for unauthorized persons to
`determine; for example, a user name may be the publicly
`known electronic mail address of the user. Furthermore,
`when users are allowed to select their own passwords, they
`tend to choose passwords that are easily remembered; often
`these can be easily guessed as well. Indeed one common
`threat to a password-based authentication system is an
`impostor that attempts to guess the password associated with
`a valid user name. Through the use of an automated system
`configured to generate character sequences at a high rate, the
`impostor can perform an "exhaustive search' by quickly
`'guessing' large numbers of character sequences. When
`guesses are limited to common names and words taken from
`a list called a "dictionary,' this type of search is sometimes
`called a "dictionary attack' on the password.
`A dictionary attack can be prevented fairly easily in a
`centralized computing system such as a timesharing system
`or a stand-alone computer, by authenticating users with the
`system's operating system software. Upon presentation of a
`user name and a password during a login procedure, the
`operating system software would verify the identity of the
`user by checking the presented user name and password
`against a list of valid user names and passwords. If too many
`wrong guesses occur, the operating system can intercede by
`disabling access to the account being attacked by, for
`example, disconnecting a dial-up telephone line or by dis
`abling the account itself.
`
`COUNTERMEASURES AGAINST
`PASSWORD-AUTHENTICATION DICTIONARY
`ATTACKS IN DISTRIBUTED SYSTEMS
`A dictionary attack can be more difficult to prevent in a
`distributed computing system. In such a system, several
`separate computer "subsystems' are typically linked
`together in a network to share various system resources.
`These systems generally lack a trusted central authority to
`implement a security policy for the system.
`Each system resource on the network may implement its
`own security policy, in which each system resource is
`responsible for determining the access rights of each
`requester and allowing or rejecting the requested access.
`When each resource must enforce its own security policy,
`complexities of a kind not encountered in centralized com
`puting environments are often seen. For example, if each
`system resource must maintain its own listing of all of the
`principals and their respective access rights and user names,
`then additional memory and maintenance is required for
`each resource. Further, if numerous system resources exist,
`then the addition ordeletion of one or more principals would
`require the modification of numerous lists.
`One known alternative is to utilize a central list that is
`accessible to all resources on the network. Because all
`system resources generally must have access to all of the
`principals and their names, a list of the principals and their
`names is often stored in a "global authentication service." A
`global authentication service is a system resource that con
`tains a list of all of the principals authorized to use the
`
`35
`
`PASSWORD-BASED CONTROL OF ACCESS TO
`COMPUTER SYSTEM RESOURCES
`Many large computing systems include "resources' such
`as one or more central processing units, main memories,
`disk and/or tape storage units, and printers. Such a system
`may also include user terminals such as workstations; in
`many implementations, each user terminal may have its own
`40
`local resources such as one or more central processing units,
`an associated main memory, a printer, and a disk or tape
`storage. In the present application, it is understood that
`"workstation' includes other user terminals that are not
`necessarily sold as "workstations,” such as personal com
`45
`puters.
`Different approaches have been used to maintain the
`security of system resources from unauthorized access.
`Quite commonly, a "principal' (e.g., a user) desiring access
`to a system resource must identify himself to a security
`management authority with a user name and a password.
`(The masculine gender is used throughout this specification
`solely for convenience.) The security management authority
`may be part of the operating system of a timesharing
`computing system, or it may be an authentication server in
`a distributed computing system. The user name and pass
`word typically are associated with an "account' on the
`computer system; each account normally has associated with
`it a set of access privileges to specified system resources.
`As illustrated in FIG. 1 in greatly simplified form, a user
`normally attempts to log in to the system by, for example,
`entering a user name and a password at a workstation. The
`security management authority checks whether the user
`name is associated with a valid account, and whether the
`password is the correct password for that account. If so, the
`security management authority presumes that the user is
`authorized to have access to system resources as specified
`
`50
`
`55
`
`60
`
`65
`
`Amazon.com Exhibit 1008 - Page 10
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`3
`system and their names. Unlike a timesharing environment,
`where the naming service is centrally controlled, in a dis
`tributed environment the naming service is merely one of
`many system resources.
`
`COUNTERMEASURES AGAINST PASSWORD
`EAVESDROPPING
`Another password-security problem, especially but not
`exclusively occurring in distributed computing systems, is
`that of the "eavesdropper." Because distributed systems
`generally have several workstations, it is desirable to allow
`a user to access the system resources regardless of which
`workstation he is logged into. However, all workstations on
`the network may not be equally trustworthy; for example,
`some workstations might be in secure and locked rooms
`while others might be publicly accessible. Moreover, many
`distributed systems require that a user who desires to use
`system resources located at various remote nodes must send
`his password to each node. In such an environment, unau
`thorized interception of the password by wiretapping the
`network may be possible, as illustrated in FIG. 1. If suc
`cessful, eavesdropping can result in the impersonation of the
`user by an imposter who has intercepted the user's pass
`word.
`To counter the eavesdropping threat, encryption using a
`secret encryption key shared by the workstation and the
`remote system resource is often used to preserve the confi
`dentiality of the transmitted password when authenticating
`the user to remote nodes. Although this type of protection is
`difficult to defeat with an exhaustive search, this method has
`practical logistical problems in that it is often difficult to
`establish the required keys between the workstation and the
`remote system resource. In another technique, the password
`is never passed between the workstation and the remote
`system resource; instead, the password is used as a key to
`encrypt information between the workstation and the remote
`system resource. However, this method is subject to dictio
`nary attacks using likely passwords to try and decrypt the
`messages.
`
`REMOTE AUTHENTICATION VIA
`PUBLIC/PRIVATE KEY ENCRYPTION
`A well-known cryptographic technique used to perform
`remote authentication is "public key' cryptography, illus
`trated in greatly simplified form in FIG. 2. In this method of
`secure communication, each principal has a public encryp
`tion key and a private encryption key. The private key is
`known only to the owner of the key, while the public key is
`known to other principals in the system. In effect, the public
`and private keys are mirror images of one another: messages
`encrypted with the public key can be decrypted only with the
`private key, and vice versa.
`To effect a secure transmission of information to a recipi
`ent, a sender encrypts the information with the recipient's
`public key. Because only the intended recipient has the
`complementary private key, only that recipient can decrypt
`it. Public key cryptography is also called "asymmetric'
`encryption because information encoded with one key of the
`pair may be decoded only by using the other key in the pair.
`One example of a public key technique is the well-known
`R.S.A. encryption scheme discussed in U.S. Pat. No. 4,405,
`829 to Rivest et al. In R.S.A. cryptography, a principal's
`public and private keys are selected such that the encryption
`and decryption transformations that they effect are mutual
`inverses of each other and the sequential application of both
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,491,752
`
`4
`transformations, in either order, will first encode the infor
`mation and then decode it to restore the information to its
`original form.
`Public key cryptography can be used in a login authen
`tication exchange between a workstation, acting on behalf of
`a user, and a remote server. In a hypothetical example,
`shown in FIG. 3, a user logs into the workstation by typing
`in the user's password. The workstation derives a secret,
`"symmetric' encryption key by applying a nonsecret (and
`indeed perhaps generally known) "hashing algorithm' to the
`password. The workstation then requests the user's private
`key from a directory service at the remote server. The user's
`private key has previously been encrypted under the same
`secret encryption key and stored as part of a "credential” in
`the directory. (A credential is a table entry comprising the
`user's name, as well as the user's private key encrypted with
`the hashed password; in other words, the credential is a
`representation of the user in the computer.) The remote
`server returns the encrypted private key to the workstation,
`which uses the secret key to decrypt and obtain the private
`key.
`A vulnerability of this password-based authentication is
`that the encrypted private key is transmitted over the net
`work from the remote server to the workstation. Because
`knowledge of the password is not needed to initiate the
`request, an impostor can easily request a copy of the
`encrypted message. Equipped with a copy of the encrypted
`message, the impostor can attempt to decrypt the message by
`guessing various passwords and hashing them with the
`known hashing algorithm to form the secret key. In other
`words, the impostor need only request the encrypted mes
`sage once and, thereafter, it can continuously attempt to
`decipher the message on its own computer without the risk
`of being audited or detected by the network. The impostor
`knows it has successfully derived the secret key and
`decrypted the message if the decrypted result yields an
`intelligible, valid private key. An impostor that can demon
`strate possession of the private key may thus access system
`resources, purportedly on behalf of the user.
`One known approach to solving this problem makes use
`of public key cryptography to enhance the security of a
`system that is primarily based on secret key authentication.
`Such an approach employs a method to ensure that the
`contents of messages exchanged over the network are unin
`telligible to an impostor, even if the impostor has correctly
`decrypted a captured message. According to the method, the
`workstation generates a random bit string to which is
`concatenated a hashed version of the user's password. This
`item of data is encrypted under the authentication server's
`public key and forwarded, together with the user name, as a
`message to the authentication server. The authentication
`server decrypts the message with its private key and checks
`that the workstation supplied the correct hash total for the
`user's password. If so, the server creates a ticket for the user
`and performs an exclusive-OR function on the ticket and the
`random bit string. The result of this latter operation is
`encrypted under the user's password hash value and returned
`as a message to the workstation. Because the impostor does
`not know the random bit string, it cannot distinguish
`between successful and unsuccessful decryptions of the
`message. This is because there is no information in a
`successfully decrypted message that would indicate that the
`decryption was successful. An example of this approach is
`discussed in Lomas et al., “Reducing Risks from Poorly
`Chosen Keys,' 12th Symposium on Operating System Prin
`ciples, 1989, pp. 14-18.
`The authentication server of the secret key system, then,
`must have knowledge of the user's password. If the authen
`
`Amazon.com Exhibit 1008 - Page 11
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`5
`tication server is compromised by an impostor, the impostor
`could use its knowledge of the password to impersonate the
`user. A significant advantage of a public key cryptography
`system lies in the fact that only the user has access to the
`user's private key. Yet, the lack of a trusted, on-line agent to
`oversee the login process makes the described form of
`public key distributed system particularly vulnerable to a
`dictionary attack.
`
`10
`
`15
`
`20
`
`25
`
`KERBEROS: USING ASHARED SECRET KEY
`FORTRANSMISSION OF AN
`AUTHENTICATION “TICKET'
`The well-known Kerberos network environment employs
`another variation on the basic password-authentication
`approach, which gives rise to a need to establish a shared
`secret key between the user's workstation and a remote
`authentication server. An example of such a system is
`illustrated in greatly simplified form in FIG. 4. In Kerberos,
`the authentication server uses this shared key to encrypt a
`"ticket' that, upon successful decryption by the workstation,
`gives the workstation the ability to access services in the
`network. If an eavesdropper can capture the encrypted ticket
`and decipher it, the eavesdropper can impersonate the user.
`In Kerberos, the shared key used to encrypt the ticket is
`based on the user's password; the authentication server
`knows the user's password because it is stored at the
`authentication server, and the workstation learns the pass
`word when the user types it in at login time. More specifi
`cally, a hash of the password is typically used to form the
`key since the password is an alphanumeric string and the key
`commonly must be a number. However, as discussed above,
`any user-selected password is vulnerable to dictionary
`attack.
`One technique to counter the dictionary attack on pass
`words in a network environment is entitled "Method and
`Apparatus for Protecting the Confidentiality of Passwords in
`a Distributed Data Processing System', filed on Apr. 28,
`1992 in the names of Charles W. Kaufman et al., and
`identified as U.S. Ser. No. 07/875,050; this technique
`requires the authentication server to receive proof that the
`user's workstation already knows the password before
`returning a ticket encrypted with the password as the key.
`
`6
`value supplied by the server and entered by the user into the
`keyboard of the authentication token generator. This type of
`token generator will be referred to as an "active' token
`generator, since it actively provides a particular token in
`response to a specific user input.
`To login at a workstation, a user first receives a token
`furnished by the authentication token generator, typically by
`reading the token from the token generator's display. Then
`the user types the token in at the workstation's keyboard,
`and the workstation sends the token to the authentication
`server. The authentication server, which knows the token
`generator's secret key, performs the same computations as
`the token generator to generate a token and compares it with
`the token typed by the user. If a match is not obtained, the
`authentication server rejects the login attempt. Often, an
`authentication token is used in addition to a user-chosen
`password.
`An authentication token generator reduces the vulnerabil
`ity of users who pick poor passwords that are easy to guess,
`but the device cannot be readily applied to a network
`environment such as Kerberos, where the workstation at
`which the user logs in also must securely receive a ticket
`from the authentication server. To use an authentication
`token generator with Kerberos, the user could type the token
`and password into a workstation, and the workstation could
`forward something based on the token and/or the password
`to Kerberos for purposes of authentication. A problem
`remains, in that a key must be established to encrypt the
`ticket that Kerberos sends to the workstation:
`(a) Both the workstation and the authentication server
`know the user's password. The password is unsuitable
`as a shared key, however, because it is potentially
`subject to a dictionary attack;
`(b) Both the workstation and the authentication server
`know, or can compute, the token. The token must be
`short enough for the user to enter reliably, however. The
`token cannot practically be more than about 8 or 9
`digits and thus is subject to attack via exhaustive
`search;
`(c) The secret key stored in the token generator would be
`a sufficiently secure shared key, but the workstation
`knows only the token that the user has typed in, not the
`secret key itself.
`
`5,491,752
`
`30
`
`35
`
`40
`
`45
`
`50
`
`HARDWARE-BASED AUTHENTICATION
`“TOKENS'''
`Another known authentication method makes use of a
`separate item of hardware referred to as an "authentication
`token generator.” Generally, authentication token generators
`provide some sort of authenticating code that a user or a
`workstation utilizes in accessing a computing system. One
`example of an authentication token generator is referred to
`colloquially as the "smart card.” In some applications, the
`authentication token generator is a "stand-alone' device that
`commonly resembles a credit card or calculator with a
`window that continuously displays a number that changes
`every few seconds. This number, which is called a "token,”
`is typically a function of (a) the date and time and (b) a secret
`key, unique to the particular token generator, that is stored in
`the token generator and also is known to the authentication
`server. This type of token generator will be referred to herein
`as a "passive' token generator, because it continuously
`provides tokens without requiring any user input.
`Another known type of authentication token generator
`provides a token that is a function of (1) a secret key unique
`to the authentication token generator, and (2) a "challenge'
`
`BRIEF SUMMARY OF THE INVENTION
`An illustrative system in accordance with the present
`invention is directed at the problems set forth above. Under
`this system, a workstation exchanges data with an authen
`tication server to obtain access to a desired computing
`system, which may include the authentication server. Com
`munications within this system are secure whether or not the
`connection between the workstation and the authentication
`server is subject to eavesdropping. An exemplary embodi
`ment of the invention is implemented in a computing
`network that includes an authentication server, as well as one
`or more workstations that may be connected to a number of
`resources, such as disk storage mechanisms, communica
`tions equipment, printers, and other computers. The work
`stations interact with one or more authentication token
`generators and one or more users.
`In one embodiment of the invention, each workstation
`additionally includes a passive token generator that provides
`a unique, ongoing sequence of "tokens' as a function of
`time. The user initiates communications with the authenti
`cation server by entering his "password' into the worksta
`
`55
`
`60
`
`65
`
`Amazon.com Exhibit 1008 - Page 12
`Amazon.com, Inc. v. DynaPass IP Holdings LLC
`IPR2024-00283 - U.S. Patent No. 6,993,658
`
`

`

`5,491,752
`
`7
`tion. The user additionally enters a token provided by the
`passive token generator. Then, the workstation calculates a
`"transmission code' by applying a first, cryptographically
`secure hashing algorithm to the password and the token, so
`that this information can be securely sent to the server.
`Upon receiving the transmission code, the server attempts
`to determine the token and the password upon which the
`transmission code was calculated. More particularly, the
`server utilizes another passive token generator that generates
`tokens substantially identical to those of the workstation's
`token generator to identify possible tokens that might have
`been generated just prior to the server's receipt of the
`transmission