Optimal Authentication Protocols
`Resistant to Password Guessing Attacks
`
`Li Gong
`
`SRI International
`Computer Science Laboratory
`Menlo Park, California 94025, U.S.A.
`(gong@csl.sri. com)
`
`Abstract
`
`Users are typically authenticated b y their pass-
`words. Because people are known to choose convenient
`passwords, which tend to be easy to guess, authenti-
`cation protocols have been developed that protect user
`passwords from guessing attacks. These proposed pro-
`tocols, however, use more messages and rounds than
`those protocols that are not resistant to guessing at-
`tacks. This paper gives new protocols that are resis-
`tant to guessing attacks and also optimal in both mes-
`sages and rounds, thus refuting the previous belief that
`protection against guessing attacks makes an authen-
`tication protocol inherently more expensive.
`
`1 Introduction
`
`Identifying users is an indispensable element of
`computer security and, because auxiliary devices such
`as smart-card are not likely to be ubiquitous in the
`foreseeable future, users have to be authenticated
`through their passwords. (We do not discuss authen-
`tication methods based on physical or biological tech-
`nologies.) People are known to use poorly chosen
`passwords that are vulnerable to dictionary attacks
`or guessing attacks [9], while all available evidence
`suggests that forcing people t o choose and remember
`good passwords - those that tend to be long charac-
`ter strings including both Roman letters and digits -
`is unworkable because such well-chosen passwords are
`also quite unmemorable [3, 71.
`Authentication protocols have been proposed that
`are resistant to password guessing attacks [8, 6, 1, 21,
`although they are more expensive in terms of the num-
`bers of messages and rounds than those authentication
`protocols without the additional requirement to pro-
`
`tect weak passwords [4, 51. For example, it is proven
`that the optimal mutual authentication (with hand-
`shake and using nonces for challenge and response)
`uses five messages [4], while the Nonce Protocol uses
`seven messages [6]. It was thought that such increased
`cost is inherent, and in particular, is because the server
`must decide if a client request is fresh before giving a
`reply - otherwise, guessing attack can materialize [6].
`In this paper, we show that this constraint is inci-
`dental to the techniques used in those protocols, and
`by a different design, we can develop authentication
`protocols that are resistant to password guessing at-
`tacks while at the same time being optimal both in
`the number of messages and in that of rounds.
`In the rest of this paper, we first review the tech-
`niques and protocols for protecting passwords from
`guessing attacks. Readers familiar with existing liter-
`ature on this subject can skip Section 2. Then we show
`how to design protocols that are optimal in messages
`and rounds. We also discuss extensions of the proto-
`cols to other scenarios, such as direct authentication.
`We finally conclude with a summary and a discussion
`as to why synchronized clocks may not help in further
`reducing the numbers of messages and rounds.
`
`2 Defeating Guessing Attacks
`
`We use the following notation throughout the pa-
`per. The notation {m}k denotes the result of en-
`crypting message m using key k , “,” denotes concate-
`nation ( m , n represents the concatenation of m and
`n ) , and
`denotes the bit-wise exclusive-or operation.
`“ A --.f B : m” represents A sending a message m to B .
`We now summarize the basic techniques for protect-
`ing passwords from guessing attacks. (More technical
`details can be found in an earlier paper [6].) Suppose
`
`1063-6900/95 $4.00 0 1995 IEEE
`
`24
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 13,2022 at 20:20:29 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1009
`Page 1 of 6
`
`

`

`A registers a password k2 at server S , and A knows
`the public key of S , k l . (The case of A not knowing
`S’s public key can be handled easily by a simple ex-
`tension [6].) Then, suppose that A asks S a question
`represented by the number n, and expects to get an
`answer in the form of f ( n ) , where f() can be a well
`known function. The protocol is shown in Table 1.
`
`tamps [6]. The modification is to let A (and also B )
`obtain al freshness identifier n s (a nonce in this case)
`from the server S (messages 1 and 2). After that, the
`protocol is the same as the Compact Protocol except
`that the timestamlp in messages 3 and 4 are substi-
`tuted by the nonce n s .
`
`1.
`2.
`
`A * S: { c l , ~ 2 , ~ 3 , n , k2}kl
`
`S * A: ( ~ 2 , ~3 @ f(n)}k;!
`
`Table 1: An illustration of basic techniques
`
`In step 1, A selects three sufficiently large random
`numbers c l , c2, and c3, encrypts them (together with
`the question n and the password k 2 ) under S’s public
`key k l , and sends the ciphertext to S. In step 2 , S de-
`crypts message l using his private key, checks the pass-
`word, uses c3 to mask the answer f(n), encrypts withi
`A’s password k2, and replies with message 2. Upon
`receiving message 2, A decrypts it using his password1
`and checks the result. If the first part of message f!
`is indeed c2, then the reply must be fresh (i.e., after
`receiving message 1) and has not been tampered eni
`route (assuming encryption also provides integrity).
`Now A can use c3 to unmask the second part of the
`reply and obtain the answer to his question.
`To mount a guessing attack, the attacker wlho has
`recorded all the exchanges over the network can guess
`k2 and try to decrypt message 2. But all he can see in
`the decrypted text is a random string, which gives no
`indication as to whether his guess of k2 is correct or
`not. Furthermore, k l is a public key and thus its cor-.
`responding private key is commonly assumed too long
`to guess in a computationally feasible way. Therefore,
`the attacker cannot decrypt message 1, and can only
`hope to reconstruct it in order to verify if a guess iri
`correct. This reconstruction is infeasible because he
`does not know c l . In other words, to attack password1
`k2 by guessing, the attacker effectively has to guess;
`both the password and c l (or S’s private key), but
`the latter is too long to guess. Therefore, the attacker
`cannot know whether a guess is correct or not, andl
`guessing attack is rendered impotent. If the attacker
`attempts to use a guessed password in an online trans-
`action, then a failed guess can be detected and logged.
`Based on these basic techniques, a protocol using
`nonces has been developed [6], as shown in Table 2.
`Here, K a and Kb are A’s and B’s passwords respec-
`tively. K s is server’s public key. This protocol irr
`adapted from the Compact Protocol that uses times-
`
`1. A - + S : A , B
`S -+ A : A , B , n s
`2.
`3.
`A -+ B : { A , 81, n u l , nu2, ca, { n s } K a } K s , n s , ru
`B --+ S: { A , B , n u l , na2, ca, { ~ s } K ~ } K ~ ,
`4.
`{ B , A , n b l , nb2, cb, {ns}Kb}Ks
`5.
`S -+ B : { n u l , k €8 n a 2 } g a , { n b l , k @ n b 2 ) ~ b
`6.
`B -+ A : { n u l , k @ na2}jya, {fl(ra), rb}k
`7. A --+ B : { f 2 ( ~ . b ) } k
`
`Table f!: The Nonce Protocol
`
`This protocol works as follows. A first obtains a
`nonce n s from the server, composes a fresh request
`message, and sends it to S via B (and at the same
`time passes along S’s nonce). B composes a simi-
`lar request message. The server checks, by examining
`that both parts of message 4 are
`
`{ n s } ~ ~ and { n s } ~ ~ ) ,
`fresh and they originate from A and B. S then se-
`lects a session key k and replies with message 5. B
`decrypts the second part of message 5 using his pass-
`word, finds n b l , and thus is satisfied that the message
`is from S, is fresh, and has not been tampered with
`during transmission. A does a similar check, before
`they complete a handshake. Here f l ( ) and f 2 ( ) are
`predefined functions.
`In this protocol, we protect the passwords not only
`from an outside attacker, but also from insiders, who
`can be either malicious or merely incompetent. For ex-
`ample, .4 cannot guess B’s password, and vice versa,
`even with the aid of the residue of a successful authen-
`tication. A safeguard that works under these circum-
`stances also ensures that neither party can cause the
`compromise of the other’s password by compromising
`their own.
`The reason for requiring the initial nonce acquisi-
`tion is that, if message 3 (or 4) is not fresh, then the
`attacker can reuse it and obtain two different versions
`of messa,ge 6: { n u l , k@na2}jya and { n u l , k ’ @ n ~ 2 } ~ a .
`The two session keys, k and k‘, are different because S
`chooses a new session key each time. However, because
`both messages contain the same value for n u l , the at-
`tacker ciin guess 1 - a and decrypt both messages to see
`if the same value nail emerges. A match indicates that
`the guess is correct with very high probability.
`
`25
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 13,2022 at 20:20:29 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1009
`Page 2 of 6
`
`

`

`It is this constraint - that the server must respond
`only to fresh requests - that makes the nonce-based
`protocol use two messages more than the optimal case.
`In the next section, we show how to remove this con-
`straint and thus to derive optimal protocols.
`
`3 An Optimal Protocol
`
`The central idea is to let A choose an additional
`random number nu3 that is to be used by S as the en-
`cryption key in the reply message. The idea of user-
`generated encryption key is not new, but the typi-
`cal objection is that the authentication server is much
`better at selecting high-quality keys. In our circum-
`stances, however, the alternative key is a user-chosen
`password, which is unlikely to be cryptographically
`stronger than the random number nu3. (Of course
`nu3 should not be weak keys specific to the cryptosys-
`tems used.) Moreover, nu3 is a one-time key such that
`cryptographically breaking its encryption does not en-
`danger the password and subsequent authentication
`sessions. The optimal protocol is shown in Table 3.
`
`is maintained, then it must have come from the server,
`and thus the key k must be the session key chosen
`by the server. Moreover, if the attacker attempts to
`mount a guessing attack on a password (say K u ) , then
`he needs to reconstruct message 1 because a guessed
`value of K u does not lead to any other information
`related to subsequent messages (i.e., no verifiable texts
`in later messages). However, to reconstruct message
`1, he must also guess the value of ca (the confounder
`[SI), which is assumed t o be chosen at random from a
`large space and thus infeasible to guess by exhaustive
`search.
`Although the attacker can replay an old message 1
`- because the server cannot decide its freshness - all
`the attacker can get is a pair (or more) messages in
`and { n u l , k’$ n ~ 2 } , , ~ .
`the form of { n u l , k $ nu2},,3
`These do not help him in compromising a future ses-
`sion key k” or in guessing the password K u .
`The optimality of the protocol is easier to see - it
`uses five messages, reaching the proven lower bound
`[4]. (More detailed definitions and terminologies re-
`lated to optimality can be found in our previous pub-
`lications [4, 51.) It is also simple to re-arrange the
`messages so that it uses four rounds, again a proven
`lower bound, as shown in Table 4.
`A -+ B : { A , B , n u l , nu2,cu, nu3, { n u 3 } ~ ~ } ~ ~ ,
`
`TU
`B -+ S: { A , B , n u l , nu2, cu, nu3, { n u 3 } ~ , } ~ ~ ,
`{ B , A, nbl, nb2, cb, nb3, { n b 3 } ~ b } ~ ,
`S --+ B : { n u l , k @ n ~ 2 } , , ~ , {nbl, k @ nb2},b3
`3 .
`B -+ A : { n u l , k @ n ~ 2 } , , ~ , { f l ( r u ) , r b } k
`4.
`5. A -+ B : { f 2 ( ~ b ) } k
`
`1.
`2.
`
`Table 3: An optimal, five-message nonce protocol
`
`This protocol works as follows. A selects ran-
`dom numbers ( n u l , nu2, cu, nu3, T U ) and composes
`and sends message 1. B does the same by sending
`message 2. The server S checks that the pair nu3
`and { n u 3 } ~ , matches with A’s password ICu, which
`proves that the original sender is A. S does the same
`check for B. Then the server selects a session key k
`for A and B to share and replies with message 3.
`In message 3, the inclusion of nul and n b l demon-
`strates that the reply is fresh, while n u l and nbl hide
`the value of the session key. The message is encrypted,
`in two parts, under keys nu3 and nb3. After that, A
`and B complete a handshake exchange, the same as is
`done in the earlier Nonce Protocol.
`The security of the protocol can be argued similarly
`as that of the Nonce Protocol. Basically, because ICs is
`the server’s public key, only the server can obtain nu3
`and nb3. Since message 3 is also fresh and its integrity
`
`1. A 3 B : { A , B , n u l , nu2, cu, nu3, { n u 3 } ~ , } ~ , ,
`TU
`
`2. B + S : { A , B , n u l , nu2, cu, nu3, { n u 3 } ~ , } ~ , ,
`{ B , A, nbl, nb2, cb, nb3, { n b 3 } ~ b } ~ , ,
`rb
`3. S + A : { n u l , IC
`n ~ 2 } , , ~ , rb
`4. s
`-f B : { n b l , k @ nb2},b3
`
`5.
`6 .
`
`A + B : { f 2 ( ~ b ) } k
`B + A : { f l ( ~ ~ ) } k
`
`Table 4: An optimal, four-round nonce protocol
`
`Here, messages 3 and 4, and 5 and 6, can be sent
`in the same round. Note that the server relays B’s
`nonce r b to A in message 3. An earlier proof (Case
`8, NB+AH+SO [5]) applies, which shows that it is
`impossible to design a protocol with five messages and
`four rounds.
`Note that a lot of replayed messages may overload
`the authentication server. This does not necessarily
`pose a security threat, unless we consider cryptanal-
`ysis (on the server’s responses) a significant problem.
`Techniques are available to make such attacks more
`difficult.
`
`26
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 13,2022 at 20:20:29 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1009
`Page 3 of 6
`
`

`

`4 Beware of Subtle Attacks
`
`5 Two-Party Direct Authentication
`
`As we have shown, it is not important if the server
`cannot decide the freshness of the request messages,
`which is the main reason why we have been aLble to
`develop optimal protocols. It is vital, however, that
`the server can identify the senders of those request
`messages because otherwise S may be cheated into
`telling B that A is at the other end of the connection
`when in fact it is an attacker C. In our protocol,
`identification is done through two pairs of texts, nu3
`
`and { n u 3 } ~ ~ , and nb3 and { n b 3 } ~ b , because only the
`holders of the passwords ( K u and Kb) can generate:
`such pairs.
`Such explicit identification may be necessary, as we
`now show how to break a variation of the protocoll
`where identification is inexplicit. Suppose we remove
`nu3 from the pair, as shown in Table 5 (the case for
`B is identical). Because { n u 3 } ~ , is still present, intu-
`itively only S knows Ku and can obtain nu3 to com-
`pose a reply message.
`
`1.
`2.
`
`3.
`4.
`5.
`
`A -+ B : { A , B , nul, nu2, cu, { ~ u ~ } K ~ } K ~ ,
`IW
`B --+ S : { A , B , nul, na2, cu, { ~ U ~ } K , } K ~ ,
`{ B , A , nbl, n b 2 , 4 { n b 3 } ~ b } ~ ~
`S 4 B : {nul, k
`1262}na3, {nbl, k CB nb2},nb3
`B -+ A : {nul, k CB n ~ 2 } ~ ~ 3 ,
`rb}k
`{ f l ( ~ ~ ) ,
`A -+ B : { f 2 ( ~ b ) } k
`
`
`
`Table 5: A variation that is insecure
`
`In this case, the attacker can take the following
`line of actions. He selects random numbers (nul,
`nu2, cu, and E ) and compose a message of the form
`{ A , B , n u l , n u 2 , c ~ , x } ~ ~ . He sends this in place of
`message 1, claiming that it originates from A . The
`server then treats x as { n u 3 } ~ , for some vatlue of
`nu3, and in due course the attacker receives y =:
`{nul, k @ n ~ 2 } , , ~ . Now the attacker guesses a. value
`of Ku, uses it to decrypt x to obtain nu3, and uses
`that to further decrypt y. If nul emerges from the de-.
`cryption, the attacker knows that he has guessled KGI
`correctly with very high probability.
`Note that even if message 3 is modified to be
`{ k n ~ 2 } , , ~ so that the evidence nul is rernoved,
`the same attack can still succeed. Now, the attacker
`himself also takes the role of B , through which he
`(quite legitimately) obtains the session key IC. After
`decrypting y, he only need to see if the plaintext is
`identical to k @ nu2 (he knows both k and na2). A,
`match indicates a successful guess of Ku.
`
`27
`
`A and B sometimes may already share a poorly cho-
`sen secret (say Kubf and wish to establish, in a secure
`way, a well-chosen session key. In the following direct
`authentication prot,ocol, k l is a public key chosen by
`A, and IC is the session key chosen by B.
`
`A -+ B : nu, { E ; l } K a b
`1.
`2. B -+ A : { B , A , nb, cb, kj { n a } l i a b } k l
`A --+ B : {nb}k
`3.
`
`Table 6: An optimal direct authentication protocol
`
`In this protocol, A selects public key k l , encrypts
`it with the shared password Kub, and sends it and a
`nonce n(z to B. B decrypts to get kl, selects three ran-
`dom numbers (nb, cb, k ) , and sends message 2. A then
`uses the private key corresponding to k l to decrypt
`this message and obtain the session key k . The pres-
`ence of (nu}Kab proves to A that the message is sent
`by B and is fresh. Finally, A completes the handshake
`by sending message 3.
`The security argument is similar to those for the
`three-pa.rty protocol in Section 3. This protocol is
`more efficient than those previously proposed that use
`five messages [l, 611. Our protocol is in fact optimal
`because three messages and three rounds are lower
`bounds proven for nonce-based protocols that carry
`out only handshakes [4].
`It is easy to modify the protocol so that both clients
`contribute to the selection of the session key. For ex-
`ample, .4 can propose another key k‘, and then they
`use h(k, k’) as the session key, where h ( ) is a one-way
`hash function, as follows.
`
`6 Using “Secret Public Keys”
`
`In th’e optimal protocol in Section 3, the clients A
`and B must know the server’s public key before pro-
`tocol invocation. If the clients cannot be assumed to
`have this knowledge, we can add an extra round of ini-
`tial exchange to obtain a “secret public key” protocol
`PI.
`1. A - + S : A , B
`2. S -+ A : {KS}Ka
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 13,2022 at 20:20:29 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1009
`Page 4 of 6
`
`

`

`Alternatively, if the clients can generate public keys
`in real time, then we can use the technique in Section 5
`to obtain a more efficient “secret public key” protocol,
`as shown in Table 7.
`
`Table 7: An optimal “secret public key” protocol
`
`In this protocol, k l and k 2 are public keys chosen
`by A and B , and nu and nb are their nonces. Numbers
`csl and cs2 are confounders chosen by S. They must
`be independently chosen because otherwise A and B
`may be able to guess each other’s password if a secret
`public key is later revealed.
`Rearranging the messages can yield a four-round
`protocol, as done in Section 3. These protocols are
`thus optimal because they meet the lower bounds of
`the numbers of messages and rounds [4].
`
`7 Do Timestamps Improve Protocol
`Efficiency?
`
`In this section, we discuss why the use of times-
`tamps may not help to make the protocols more ef-
`ficient.
`In general, the availability of synchronized
`clocks and the use of timestamps often can reduce the
`numbers of messages and rounds for authentication
`protocols. For example, an optimal mutual authenti-
`cation protocol assuming synchronized clocks uses four
`messages or three rounds, cheaper than nonce-based
`protocols [4]. Thus, a question remains as to whether
`the efficiency of the protocols in Sections 3 , 5, and 6
`can be further improved if timestamps are used.
`Clearly the use of timestamps will enable the server
`(or a client, in a situation of direct authentication) to
`check if an initial request message is fresh and thus to
`respond only to fresh requests. However, as we have
`shown, the security of the protocol does not depend
`on the server knowing whether the request messages
`are fresh, even with fhe additional requirement that
`protocols be resistan? to password guessing attacks.
`To use timestamps in later stages of the protocol does
`not increase protocol efficiency either, because by then
`all parties will have the chance to exchange nonces
`
`28
`
`(piggybacked on earlier messages).
`Moreover, current techniques for protecting pass-
`words [l, 61 all require that a client, before receiving
`the session key, must either generate and send a pub-
`lic key (to the other client) or send a message to the
`server encrypted with the server’s public key. This
`is equivalent, in terms of efficiency, to requiring that
`each client send a nonce before receiving the session
`key, which is in fact a security requirement for nonce-
`based protocols. Therefore, we conjecture that pro-
`tocols resistant to password guessing attacks cannot
`be more efficient than nonce-based protocols, even if
`synchronized clocks can be assumed.
`We can further argue for this conjecture from an-
`other angle. Suppose timestamps do help, and because
`the difference in lower bounds between timestamp-
`based and nonce-based protocols is only one message
`OF one round [4, 51, then we can deduce that three
`messages are sufficient for both A and B to receive the
`session key from the server. In this case, because A has
`to initiate the protocol, a little analysis will show that
`B must receive the key in his first contact with the
`server. We know of no technique that achieves this
`goal - note that guessing attacks must not become
`possible after the session key is later used for hand-
`shaking or for encrypting traffic - unless we assume
`that S knows about a trap-door function on B’s side
`(e.g., B’s public key). An impossibility proof along
`this line of reasoning will be very useful.
`Nevertheless, in the case with a trusted third party,
`if either (or both) client, instead of the server, chooses
`the session key, then it is not difficult to check that
`using timestamps can reduce the numbers of messages
`and rounds to the theoretical lower bounds [4].
`
`8 Related Work
`
`Gong et al. [6, 81 and Bellovin and Merritt [l, 21
`developed the first authentication protocols that are
`resistant t o password guessing attacks. Gong [4, 51
`and Yahalom [ll], among others, have investigated
`the design of optimal authentication protocols.
`Tsudik and Van Herreweghen suggested protocol
`modifications in order to reduce the amount of en-
`cryption [lo]. Their techniques, including their use of
`user-generated encryption keys, potentially can also
`reduce the number of messages. However, in their
`protocols, a client cannot know if the session key he
`receives from the server is correct (i.e., has not been
`tampered with) until he later uses it. This deficiency
`is nevertheless compensated by their use of extremely
`short messages. This trade-off appears to be intrinsic.
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 13,2022 at 20:20:29 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1009
`Page 5 of 6
`
`

`

`and Communications Security, pages 26-37, Fair-
`fax, Virginia, November 1993.
`[5] L. Gong. Efficient Network Authentication Pro-
`tocols: Lower Bounds and Optimal Implemen-
`tations. Technical Report SRI-CSL-94-15, Com-
`puter Science Laboratory, SRI International,
`Menlo Park, California, October 1994.
`[6] L. Gong, T.M.A. Lomas, R.M. Needham, and
`J.H. Saltzer. Protecting Poorly Chosen Secrets
`IEEE Journal on Se-
`froim Guessing Attacks.
`lected Areas in Communications, 11(5):648-656,
`June 1993.
`[7] D.V. Klein. Foiling the Cracker: A Survey of, and
`Improvements to Password Security. In Proceed-
`ings of the 2nd‘ USENIX Unix Security Workshop,
`pages 5-14, August 1990.
`[8] T.M.A. Lomas, L. Gong, J.H. Saltzer, and R.M.
`Needham. Reducing Risks from Poorly Chosen
`In Proceedings of the 12th ACM Sym-
`Ke:ys.
`posaum on Operating System Principles, volume
`23(5) of ACM Operating Systems Review, pages
`14-18, Litchfield Park, Arizona, December 1989.
`
`[9] R. Morris and K. Thompson. Password Security:
`A Case History. Communications of the ACM,
`22(11):594-597, November 1979.
`[lo] G. Tsudik and E. Van Herreweghen. Some Re-
`marks on Protecting Weak Keys and Poorly-
`Chosen Secrets from Guessing Attacks. In Pro-
`ceedings of the 12th IEEE Symposium on Reliable
`Distributed Systems, pages 136-141, Princeton,
`New Jersey, October 1993.
`
`[ll] R. Yahalom. Optimality of Multi-Domain Pro-
`tocols. In Proceedings of the 1st ACM Confer-
`ence on Computer and Communications Security,
`pages 38-48, Fairfax, Virginia, November 1993.
`
`9 Summary
`
`Users are typically authenticated to a computer sys-
`tem or to each other by the use of their passwords.
`Because people are known to prefer convenient pass-
`words, which are easy to guess, researchers have dlevel-
`oped authentication protocols that protect user pass-
`words from guessing attacks, even if the attacker can
`monitor and record all messages exchanged duriing au-
`thentication. These proposed protocols, however, use
`more messages and rounds than those protocols that
`are not resistant to guessing attacks.
`In this paper, we have described new protocols that
`are resistant to guessing attacks and are also opti-
`mal in both messages and rounds, thus refuting the
`previously held belief that the additional requirement
`of protecting passwords from guessing attacks makes
`an authentication protocol inherently more expensive.
`Our protocols use the simple idea of letting the user
`choose a temporary key that is used by the seirver to
`encrypt its response message. We also show why some
`naive variations of the protocols are not secure, how
`to extend the basic idea to direct authentication and
`to the use of “secret” public keys, and why the use of
`timestamps may not make the protocols more efhcient.
`
`References
`
`S. Bellovin and M. Merritt. Encrypted Key
`Exchange:
`Password-Based Protocols Secure
`In Proceedrings of
`Against Dictionary Attacks.
`the IEEE Symposium on Research in Security and
`Privacy, pages 72-84, Oakland, California, May
`1992.
`
`[2] S. Bellovin and M. Merritt. Augmented En-
`crypted Key Exchange: A Password-Based Pro-
`tocol Secure Against Dictionary Attacks and
`Password File Compromise. In Proceedings cif thle
`1st ACM Conference on Computer and Cfmmu-
`nzcations Security, pages 244-250, Fairfax, Vir-
`ginia, November 1993.
`
`[3] D.C. Feldmeier and P.R. Karn. UNIX Pass-
`word Security - Ten Years Later.
`In Proceed-
`ings of Crypto’89, volume 435 of Lecture Notes in
`Computer Science, pages 44-63. Springer-’Verlag ,
`1989.
`
`[4] L. Gong. Lower Bounds on Messages and FLoundis
`for Network Authentication Protocols. In Pro-
`ceedings of the 1st ACM Conference on Computer
`
`29
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 13,2022 at 20:20:29 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1009
`Page 6 of 6
`
`