A New Two-Server Approach for Authentication with Short Secrets
`(To appear in USENIX Security ’03)
`
`John Brainard, Ari Juels, Burt Kaliski, and Michael Szydlo
`RSA Laboratories
`Bedford, MA 01730, USA
`E-mail: fjbrainard,ajuels,bkaliski,mszydlog@rsasecurity.com
`
`April 9, 2003
`
`Abstract
`
`1
`
`Introduction
`
`Passwords and PINs continue to remain the most
`widespread forms of user authentication, despite
`growing awareness of their security limitations. This
`is because short secrets are convenient, particularly
`for an increasingly mobile user population. Many
`users are interested in employing a variety of com-
`puting devices with di(cid:11)erent forms of connectivity
`and di(cid:11)erent software platforms. Such users often
`(cid:12)nd it convenient to authenticate by means of pass-
`words and short secrets, to recover lost passwords by
`answering personal or \life" questions, and to make
`similar use of relatively weak secrets.
`
`In typical authentication methods based on short
`secrets, the secrets (or related values) are stored in
`a central database. Often overlooked is the vulner-
`ability of the secrets to theft en bloc in the event
`of server compromise. With this in mind, Ford and
`Kaliski and others have proposed various password
`\hardening" schemes involving multiple servers, with
`password privacy assured provided that some servers
`remain uncompromised.
`
`In this paper, we describe a new, two-server se-
`cure roaming system that bene(cid:12)ts from an especially
`lightweight new set of protocols. In contrast to pre-
`vious ideas, ours can be implemented so as to require
`essentially no intensive cryptographic computation by
`clients. This and other design features render the sys-
`tem, in our view, the most practical proposal to date
`in this area. We describe in this paper the protocol
`and implementation challenges and the design choices
`underlying the system.
`
`In this paper, we consider a basic, pandemic security
`problem: How is it possible to provide secure services
`to users who can authenticate using only short secrets
`or weak passwords?
`This problem is of growing importance as Internet-
`enabled computing devices become ever more preva-
`lent and versatile. These devices now include among
`their ranks an abundant variety of mobile phones,
`personal digital assistants (PDAs), and game con-
`soles, as well as laptop and desktop PCs. The avail-
`ability of networks of computers to highly mobile user
`populations, as in corporate environments, means
`that a single user may regularly employ many di(cid:11)er-
`ent points of remote access. The roaming user may
`additionally employ any of a number of di(cid:11)erent de-
`vices, not all of which necessarily possess the same
`software or con(cid:12)guration.
`While smartcards and similar key-storage devices
`o(cid:11)er a secured, harmonized approach to authentica-
`tion for the roaming user, they lack an adequately de-
`veloped supporting infrastructure in many computing
`environments. At present, for example, very few com-
`puting devices contain smartcard readers { particu-
`larly in the United States. Furthermore, many users
`(cid:12)nd physical authentication tokens inconvenient. An-
`other point militating against a critical reliance on
`hardware tokens is the common need to authenticate
`roaming users who have lost or forgotten their to-
`kens, or whose tokens have malfunctioned. Today,
`this is usually achieved by asking users to provide
`answers to a set of \life" questions, i.e., questions
`regarding personal and private information. These
`
`1
`
`USR Exhibit 2116, Page 1
`
`

`

`observations stress that roaming users must be able
`to employ passwords or other short pieces of mem-
`orable information as a form of authentication. In-
`deed, short secrets like passwords and answers to life
`questions are the predominant form of authentication
`for most users today. They are the focus of our work
`here.
`To ensure usability by a large user population, it is
`important that passwords be memorable. As a result,
`those used in practice are often highly vulnerable to
`brute-force guessing attacks [18]. Good credential-
`server designs must therefore permit secure authen-
`tication assuming a weak key (password) on the part
`of the user.
`
`1.1 SPAKA protocols
`
`A basic tool for mutual authentication via pass-
`words, and one well developed in the litera-
`ture, is secure password-authenticated key agreement
`(SPAKA). Most SPAKA protocols are descendants
`of Bellovin and Merrit’s EKE protocol [3, 4], and are
`predicated on either Di(cid:14)e-Hellman key agreement or
`key agreement using RSA. The client and server share
`a password, which is used to achieve mutual assur-
`ance that a cryptographically strong session key is
`established privately by the two parties. To address
`the problem of weak passwords, SPAKA protocols are
`constructed so as to leak no password information,
`even in the presence of an active attacker. When used
`as a means of authentication to obtain credentials
`from a trusted server, a SPAKA protocol is typically
`supplemented with a throttling or lockout mechanism
`to prevent on-line guessing attacks. Many roaming-
`credentials proposals involve use of a SPAKA proto-
`col as a leverage point for obtaining credentials, or
`as a freestanding authentication protocol. A com-
`prehensive, current bibliography of research papers
`on the topic of SPAKA protocols (of which there are
`dozens) is maintained by David Jablon, and may be
`found at [15].
`The design of most SPAKA protocols overlooks a
`fundamental problem: The server itself represents a
`serious vulnerability. As SPAKA protocols require
`the verifying server to have cleartext access to user
`passwords (or to derivative material), compromise of
`
`the server leads potentially to exposure of the full
`database of passwords. While many SPAKA proto-
`cols store passwords in combination with salt or in
`some exponentiated form, an attacker who compro-
`mises the server still has the possibility of mounting
`o(cid:11)-line dictionary attacks. Additionally, these sys-
`tems o(cid:11)er no resistance to server corruption. An at-
`tacker that gains control of the authenticating server
`can spoof successful login attempts.
`To address this problem, Ford and Kaliski [11] in-
`troduced a system in which passwords are e(cid:11)ectively
`protected through distribution of trust across mul-
`tiple servers. Mackenzie, Shrimpton, and Jakobsson
`[21] extended this system, leading to more complex
`protocols, but with rigorous security reductions in a
`broadly inclusive attack model. Our work in this pa-
`per may be regarded as a complement, rather than a
`successor to the work of these authors. We propose a
`rather di(cid:11)erent technical approach, and also achieve
`some special bene(cid:12)ts in our constructions, such as
`a substantially reduced computational load on the
`client. At the same time, we consider a di(cid:11)erent, and
`in our view more pragmatic security model than that
`of other distributed SPAKA protocols.
`
`1.2 Previous work
`
`The scheme of Ford and Kaliski reduces server vulner-
`ability to password leakage by means of a mechanism
`called password hardening. In their system, a client
`parlays a weak password into a strong one through
`interaction with one or multiple hardening servers,
`each one of which blindly transforms the password
`using a server secret. Ford and Kaliski describe sev-
`eral ways of doing this. Roughly speaking, the client
`in their protocol obtains what may be regarded as a
`blind function evaluation (cid:27)i of its password P from
`(The function in ques-
`each hardening server Si.
`tion is based on a secret unique to each server and
`user account.) The client combines the set of shares
`f(cid:27)ig into a single secret (cid:27), a strong key that the
`user may then use to decrypt credentials, authen-
`ticate herself, etc. Given an appropriate choice of
`blind function evaluation scheme, servers in this pro-
`tocol may learn no information, in an information-
`theoretic sense, about the password P . An additional
`
`2
`
`USR Exhibit 2116, Page 2
`
`

`

`element of the protocol involves the user authenticat-
`ing by means of (cid:27) (or a key derived from it) to each
`of the servers, thereby proving successful hardening.
`The harderened password (cid:27) is then employed to de-
`crypt downloaded credentials or authenticate to other
`servers.
`Mackenzie et al. extend the system of Ford and
`Kaliski to a threshold setting.
`In particular, they
`demonstrate a protocol such that a client commu-
`nicating with any k out of n servers can establish
`session keys with each by means of password-based
`authentication; even if k (cid:0) 1 servers conspire, the
`password of the client remains private. Their system
`can be straightforwardly leveraged to achieve secure
`downloadable credentials. The Mackenzie et al. sys-
`tem, however, imposes considerable overhead of sev-
`eral types. First, servers must possess a shared global
`key and local keys as well (for a total of 4n + 1 public
`keys). The client, additionally, must store n + 1 (cer-
`ti(cid:12)ed) public keys. The client must perform several
`modular exponentiations per server for each session,
`while the computational load on the servers is high
`as well. Finally, the Mackenzie et al. protocol is
`somewhat complex, both conceptually and in terms
`of implementation. On the other hand, the protocol
`is the (cid:12)rst such provided with a rigorous proof of se-
`curity under the Decision Di(cid:14)e-Hellman assumption
`[7] in the random oracle model [2].
`Frykholm and Juels [13] adopt a rather di(cid:11)erent
`approach,
`in which encrypted user credentials are
`stored on a single server.
`In this system, no trust
`in the server is required to assure user privacy un-
`der appropriate cryptographic assumptions. Roughly
`stated, user credentials are encrypted under a collec-
`tion of short passwords or keys. Typically, these are
`answers to life questions. While the Frykholm-Juels
`system provides error tolerance, allowing the user to
`answer some questions incorrectly, it is somewhat im-
`practical for a general population of users, as it re-
`quires use of a large number of questions.
`Indeed,
`the authors recommend a suite of as many as (cid:12)fteen
`such questions to achieve strong security. The work
`of Frykholm and Juels is an improvement on that of
`Ellison et al.
`[10], which was found to have a seri-
`ous security vulnerability [5]. This approach may be
`thought of as an extension to that of protecting cre-
`
`dentials with password-based encryption. The most
`common basis for this in practice is the PKCS #5
`standard [1].
`
`1.3 Our work: a new, lightweight sys-
`tem
`
`It is our view that most SPAKA protocols are over-
`engineered for real-world security environments. In
`particular, we take the position that that mutual au-
`thentication is often not a requirement for roaming
`security protocols per se. Internet security is already
`heavily dependent upon a trust model involving ex-
`isting forms of server-side authentication, particu-
`larly the well studied Secure Sockets Layer protocol
`(SSL) [12]. SSL is present in nearly all existing Web
`browsers. Provided that a browser veri(cid:12)es correct
`binding between URLs and server-side certi(cid:12)cates, as
`most browsers do, the user achieves a high degree of
`assurance of the identity of the server with which she
`has initiated a given session. In other words, server
`authentication is certainly important, but need not
`be provided by the same secret as user authentica-
`tion. Thus many SPAKA protocols may be viewed
`as replicating functionality already provided in an ad-
`equately strong form by SSL, rather than building on
`such functionality.
`Moreover, it may be argued that SPAKA proto-
`cols carry a hidden assumption of trust in SSL or
`similar mechanisms to begin with. SPAKA protocols
`require the availability of special-purpose software on
`the client side. Given that a mobile user cannot be
`certain of the (correct) installation of such software
`on her device, and that out-of-band distribution of
`special-purpose software is rare, it is likely that a user
`will need to download the SPAKA software itself from
`a trusted source. This argues an a priori requirement
`for user trust in the identity of a security server via
`SSL or a related mechanism. In this paper, we as-
`sume that the client has a pre-existing mechanism
`for establishing private channels with server-side au-
`thentication, such as SSL.
`Our system represents an alternative to SPAKAs
`in addressing \hardening" problem; it is a two-server
`solution that is especially simple and practical. The
`idea is roughly as follows. The client splits a user’s
`
`3
`
`USR Exhibit 2116, Page 3
`
`

`

`password (or other short key) P into shares for the
`two servers. On presenting a password P 0 for au-
`thentication, the client provides the two servers with
`a new, random sharing of P 0. The servers then com-
`pare the two sharings of P and P 0 in such a way that
`they learn whether P = P 0, but no additional infor-
`mation. The client machine of the user need have no
`involvement in this comparison process.
`As we explain, it is bene(cid:12)cial to con(cid:12)gure our sys-
`tem such that users interact with only one server
`on the front-end, and pass messages to a second,
`back-end server via a protected tunnel. This per-
`mits the second server to reference accounts by way
`of pseudonyms, and thereby furnishes users with an
`extra level of privacy. Such privacy is particularly
`valuable in the case where the back-end server is ex-
`ternally administered, as by a security-services or-
`ganization. Much of our protocol design centers on
`the management of pseudonyms and on protection
`against the attacks that na(cid:127)(cid:16)ve use of pseudonyms
`might give rise to.
`
`1.4 Organization
`
`In section 2, we describe the core cryptographic pro-
`tocol our system for two-server comparison of secret-
`shared values. We provide an overview of our ar-
`chitecture in section 3, discussing the security mo-
`tivations behind our choices.
`In section 4, we de-
`scribe two specialized protocols in our system; these
`are aimed at preventing false-identi(cid:12)er and replay at-
`tacks. We provide some implementation details for
`our system in section 5. We conclude in section 6
`with a brief discussion of some future directions.
`
`2 An Equality-Testing Proto-
`col
`
`Let us (cid:12)rst reiterate and expand on the intuition be-
`hind the core cryptographic algorithm in our system,
`which we refer to as equality testing. The basic idea is
`for the user to register her password P by providing
`random shares to the two servers. On presenting her
`password during login, she splits her password into
`shares in a di(cid:11)erent, random way. The two servers
`
`compare the two sharings using a protocol that de-
`termines whether the new sharing speci(cid:12)es the same
`password as the original sharing, without leaking any
`additional information (even if one server tries to
`cheat). For convenience, we label the two servers
`\Blue" and \Red". Where appropriate in subscripts,
`we use the lower-case labels \blue" and \red".
`
`Registration: Let H be a large group (of, say, 160-
`bit order), and + be the group operator. Let f be
`a collision-free hash function f : f0; 1g(cid:3) ! H. To
`share her password at registration, the user selects a
`random group element R 2U H. She computes the
`share Pblue for Blue as Pblue = f (P ) + R, while the
`share Pred of Red is simply R. Observe that the share
`of either server individually provides no information
`about P .
`
`Authentication: When the user furnishes pass-
`word P 0 to authenticate herself, she computes a shar-
`ing based on a new random group element R0 2U H.
`
`In this sharing, the values P 0blue = f (P 0) + R0 and
`
`P 0red = R0 are sent to Blue and Red respectively.
`The servers combine the shares provided during
`registration with those for authentication very sim-
`ply as follows. Blue computes Qblue = Pblue (cid:0)P 0
`blue =
`(f (P ) (cid:0) f (P 0)) + (R (cid:0) R0), while Red similarly com-
`
`putes Qred = Pred (cid:0) P 0red = R (cid:0) R0. Observe
`that if P = P 0, i.e., if the user has provided the
`correct password, then f (P ) and f (P 0) cancel, so
`that Qblue = Qred. Otherwise, if the user provides
`P 6= P 0, the result is that Qblue 6= Qred (barring
`a collision in f ). Thus, to test the user password
`submitted for authentication, the two servers need
`merely test whether Qblue = Qred, preferably with-
`out revealing any additional information.
`For this task of equality testing, we require a sec-
`ond, large group G of order q, for which we let mul-
`tiplication denote the group operation. The group G
`should be one over which the discrete logarithm prob-
`lem is hard. We assume that the two servers have
`agreed upon this group in advance, and also have
`agreed upon (and veri(cid:12)ed) a generator g for G. We
`also require a collision-free mapping w : H ! G. For
`equality testing of the values Qred and Qblue, the idea
`
`4
`
`USR Exhibit 2116, Page 4
`
`

`

`ular multiplications.) Moreover, once the client has
`submitted a sharing, it need have no further involve-
`ment in the authentication process. Red and Blue
`together decide on the correctness of the password
`submitted for authentication. Given a successful au-
`thentication, they can then perform any of a range
`of functions providing privileges for the user: Each
`server can send a share of a key for decrypting the
`user’s downloadable credentials, or two servers can
`jointly issue a signed assertion that the user has au-
`thenticated, etc.
`
`2.1 Protocol details
`
`As we have already described the simple sharing pro-
`tocols employed by the client in our system for regis-
`tration and authentication, we present in detail only
`the protocol used by the servers to test the equality
`Qred = Qblue. We assume a private, mutually au-
`thenticated channel between the two servers. Should
`the initiating server (Blue) try to establish multiple,
`concurrent authentication sessions for a given user
`account, the other server (Red) will refuse. (In par-
`ticular, in Figure 1, Red will reject the initiation of
`a session in which the (cid:12)rst (cid:13)ow speci(cid:12)es the same
`user account as for a previously established, active
`authentication session.) Alternative approaches per-
`mitting concurrent login requests for a single account
`are possible, but more complicated. If Blue initiates
`an authentication request with Red for a user U for
`which Red has received no corresponding authenti-
`cation request from the user, then Red, after some
`appropriate delay, will reject the authentication.
`Let Qblue;U denote the current share combination
`that Blue wishes to test for user U , and Qred;U the
`analogous Red-server share combination for user U .
`In this and any subsequently described protocols in
`this paper, if a server fails to validate any mathemat-
`?
`ical relation denoted by ?=,
`, it determines
`, or
`6=,
`that a protocol failure has taken place; in this case,
`the authentication session is terminated and the cor-
`responding authentication request rejected.
`We let 2R denote uniform random selection from
`a set. We indicate by square brackets those com-
`putations that Red may perform prior to protocol
`
`?>
`
`?2
`
`is for the two servers to perform a variant of Di(cid:14)e-
`Hellman key exchange. In this variant, however, the
`values Qred and Qblue are \masked" by the Di(cid:14)e-
`Hellman keys. The resulting protocol is inspired by
`and may be thought of as a technical simpli(cid:12)cation of
`the PET protocol in [16]. Our protocol uses only one
`component of an El Gamal ciphertext [14], instead
`of the usual pair of components as in PET. Our pro-
`tocol also shares similarities with SPAKA protocols
`such as EKE. Indeed, one may think of the equal-
`ity Qred = Qblue as resulting in a shared secret key,
`and inequality as yielding di(cid:11)erent keys for the two
`servers.
`There are two basic di(cid:11)erences, however, between
`the goal of a SPAKA protocol and the equality-
`testing protocol in our system. A SPAKA protocol,
`as already noted, is designed for security over a po-
`tentially unauthenticated channel.
`In contrast, our
`intention is to operate over a private, mutually au-
`thenticated channel between the two servers. More-
`over, we do not seek to derive a shared key from the
`protocol execution, but merely to test equality of two
`secret values with a minimum of information leakage.
`Our desired task of equality testing in our system is
`known to cryptographers as the socialist millionaires’
`problem. (The name derives from the idea that two
`millionaires wish to know whether they enjoy equal (cid:12)-
`nancial standing, but do not wish to reveal additional
`information to one another.) Several approaches to
`the socialist millionaires’ problem are described in
`the literature. Often, researchers are also concerned
`in addressing the problem to ensure the property of
`fairness, namely that both parties should learn the
`answer or neither. We do not treat this issue here,
`as it does not have a major impact on the overall
`system design.
`(A protocol unfairly terminated by
`one server in our system is no worse than a password
`guess initiated by an adversary, and will be immedi-
`ately detected by the other server.)
`Note that in this protocol, the client need perform
`no cryptographic computation, but just a single (ad-
`dition) operation in H.
`(The client performs some
`cryptographic computation to establish secure con-
`nections with Blue and Red in our system, but this
`may occur via low-exponent RSA encryption { as in
`SSL { and thus involves just a small number of mod-
`
`5
`
`USR Exhibit 2116, Page 5
`
`

`

`initiation by Blue, if desired. Our password-equality
`testing protocol is depicted in Figure 1. We use sub-
`scripts red or 1 to denote values computed or received
`by Red and blue or 0 for those of Blue. We alternate
`between these forms of notation for visual clarity. We
`let h denote a one-way hash function (modeled in our
`security analysis by a random oracle).
`In the case
`where a system may include multiple Blue and/or
`Red servers, the hash input should include the server
`identities as well. We let k denote string concatena-
`tion.
`For the sake of simplicity, we (cid:12)x a particular group
`G for our protocol description here.
`In particular,
`we consider G to be the prime subgroup of order q
`in Zp, for prime p = 2q + 1. Use of this particular
`group is re(cid:13)ected in our protocol by: (1) Use of even
`exponents e0 and e1 to ensure group membership in
`manipulation of transmitted values, and (2) Mem-
`bership checks over f2; : : : ; p (cid:0) 2g. For other choices
`of group, group membership of manipulated values
`may be ensured by other means. All arithmetic here
`is performed mod p.
`
`Implementation choices: A typical choice for p,
`and that adopted in our system, is a 1024-bit prime.
`Recall that we select G to be a subgroup of prime
`order q for p = 2q + 1.1 For H, we simply select the
`group consisting of, e.g., 160-bit strings, with XOR
`as the group operator. We note that a wide variety
`of other choices is possible.
`
`In brief, security in our model states that
`Security:
`an adversary with active control of one of the two
`servers and an arbitrary set of users can do essen-
`tially no better in attacking the accounts of honest
`
`1One may achieve greater e(cid:14)ciency by selecting shorter ex-
`ponents e0 and e1, e.g., 160 bits. This yields a system that
`we hypothesize may be proven secure in the generic model for
`G, but whose security has not been analyzed in the literature.
`One might also use smaller subgroups, in which case group-
`membership testing involves fair computational expense. Al-
`ternatively, other choices of group G may yield higher e(cid:14)ciency.
`One possibility, for example, is selection of G as an appropriate
`group over an elliptic curve. This yields much better e(cid:14)ciency
`for the exponentiation operations, and also has an e(cid:14)cient test
`of group membership.
`
`users than random, on-line guessing. Attacks in-
`volving such guessing may be contained by means of
`standard throttling mechanisms, e.g., shutting down
`a given account after three incorrect guesses. Of
`course, our scheme does not o(cid:11)er any robustness
`against simple server failures. This may be achieved
`straightforwardly through duplication of the Red and
`Blue servers. We also assume fully private server-
`authenticated channels between the client and the
`two servers.
`In this model, and with the random-
`oracle assumption [2] on the hash function, we claim
`that the security of our core cryptographic algorithm
`for equality testing may be reduced to the computa-
`tional Di(cid:14)e-Hellman assumption on the group G.
`
`3 Architectural Motivation and
`Overview
`
`The security of our equality-testing protocol in our
`system depends upon the inability of an attacker to
`compromise both Red and Blue. Heterogeneity in
`server con(cid:12)gurations is thus an important practical
`security consideration here. At the simplest level,
`the Red and Blue servers may run di(cid:11)erent operat-
`ing systems, thereby broadening the range of tech-
`nical obstacles confronting the would-be attacker. A
`further possible step in this direction would be to
`situate Red and Blue within di(cid:11)erent organizations,
`with the hope of minimizing the risk of insider or
`social-engineering attacks.
`The distribution of security across organizations
`also provides an appealing model of risk management
`in which legal and (cid:12)nancial responsibility for compro-
`mise can be (cid:13)exibly allocated. We can view this as a
`form of privacy outsourcing, in which one server (say,
`Blue) is operated by a service provider and the other
`(say, Red) is operated by what we may refer to as a
`privacy provider. The privacy provider might be an
`organization with specialized expertise that is will-
`ing to assume the primary burden of security main-
`tenance and likewise to assume a large portion of the
`legal and (cid:12)nancial liability associated with privacy
`breaches.
`For a service provider to adopt this approach in a
`
`6
`
`USR Exhibit 2116, Page 6
`
`

`

`RED server
`
`[e1 2R f2; 4; : : : ; q (cid:0) 1g]
`
`[Y 01 = ge1 ]
`
`B = w(Qred;U )
`Y1 = BY 0
`1
`Zred = (Y0=B)e1
`
`?2
`
`Zred
`f2; : : : ; p (cid:0) 2g
`Hred = h(Zred k Y0 k Y1 k U )
`
`Y0;U
`(cid:0)!
`
`Y1;Hred (cid:0)
`
`Hblue(cid:0)!
`
`BLUE server
`
`e0 2R f2; 4; : : : ; q (cid:0) 1g
`A = w(Qblue;U )
`Y0 = Age0
`
`Zblue = (Y1=A)e0
`
`?2
`
`f2; : : : ; p (cid:0) 2g
`Zblue
`Hblue = h(Zblue k Hred)
`
`Hred
`
`?= h(Zblue k Y0 k Y1 k U )
`
`Hblue
`
`?= h(Zred k Hred)
`
`Figure 1: Password-equality testing protocol
`
`way appealing to a large and potentially mobile user
`population, there are two salient requirements:
`
`(cid:15) Universality: There should be no need for
`clients to install special-purpose software.
`In
`particular, clients should be able to interface
`with the system by way of standard browser
`components such as Java and HTML.
`
`(cid:15) Pseudonymity: Red, i.e., the privacy provider,
`should be unable to gain explicit access to the
`user names associated with accounts. At a mini-
`mum, clients should be able to interact with this
`server pseudonymously, i.e., by way of identi(cid:12)ers
`unlinkable with true account names or IP ad-
`dresses. This provides a technical obstacle to
`abuse of account information on the part of the
`operator of Red.
`It is also useful to employ
`pseudonyms in this way so as to limit exposure
`of account identi(cid:12)ers in case of compromise of
`Red.
`
`The requirement of universality in the service-
`provider model argues that the software in our sys-
`tem, while perhaps installed on some clients as a
`browser plug-in or standalone executable, should also
`be available in the form of a Java applet. This ap-
`plet is dispensed by Blue in our system (although it
`could be dispensed elsewhere). The applet contains
`the software to execute our basic two-server proto-
`col, and also contains a public key for Red. This
`public key serves to establish a private channel from
`the client to Red via Blue.
`
`Distribution of such applets by Blue raises an im-
`mediate concern: Blue might serve bad applets. In
`particular, an attacker that has compromised Blue in
`an active fashion can cause that server to distribute
`applets that contain a false public key for Red { or
`indeed that do not even run the intended protocol.
`As we have already explained, the problem of trusted
`software is present even for SPAKA protocols, given
`the need of roaming clients to install such software
`on the (cid:13)y. Applets or other software may be digitally
`
`7
`
`USR Exhibit 2116, Page 7
`
`

`

`signed, but most users are unlikely to understand
`how to employ browser-provided veri(cid:12)cation tools to
`check the correctness of the associated code-signing
`certi(cid:12)cate. Rather, we make two observations on
`this score. First, active compromise of core compo-
`nents of Blue is likely to be much harder than passive
`compromise. Some hope may be placed in so-called
`\tripwire" tools that are designed speci(cid:12)cally to de-
`tect hostile code modi(cid:12)cation. Additionally, the task
`of an attacker in compromising Blue in this way is
`harder than active compromise in traditional crypto-
`graphic settings, in the following sense: Any observer
`can in principle detect the compromise by inspecting
`applets. Thus, the privacy provider might period-
`ically initiate authentication requests with Blue to
`monitor its integrity. Another complementary ap-
`proach is for Red to distribute to interested clients a
`piece of software that veri(cid:12)es the hash of code served
`by Blue.
`The pseudonymity requirement, particularly the
`notion that Red should not learn the IP addresses
`of clients, suggests that the privacy provider should
`operate Red as a back-end server, i.e., a server that
`only interacts with other servers, not clients. This is
`the server-con(cid:12)guration that we adopt in our system.
`In particular, the client in our system communicates
`with the Red server via an encrypted tunnel estab-
`lished using the public key for Red. There are in fact
`several other compelling reasons to operate Red as a
`back-end server:
`
`(cid:15) Engineering simplicity: Deployment of Red
`as a back-end server permits the client to estab-
`lish a direct connection with only a single server,
`the normal mode of use for most services on the
`Internet. A service provider may maintain a sin-
`gle front-end server and treat Red as an external,
`supporting Web service.
`
`(cid:15) System isolation: In the outsourcing model,
`the major burden of liability and security is on
`Red, and the privacy provider is the primary
`source of security expertise. Hence it is desirable
`to isolate Red from open communication on the
`Internet, restricting its interaction instead to one
`or more Blue servers exclusively via the proto-
`cols in our system, e(cid:11)ectively creating a kind of
`
`strong, application-layer (cid:12)rewall. This imparts
`to the system as a whole a higher level of secu-
`rity than if both servers were directly exposed.
`
`(cid:15) Mitigation of denial-of-service attacks: Iso-
`lation of Red as a back-end server is also helpful
`in minimizing the exposure of Red to denial-of-
`service attacks, which the operator of Blue, hav-
`ing better familiarity with its own user base, is
`better equipped to handle.
`
`A serious concern does arise in conjunction with
`the pseudonymity requirement. Blue must identify
`a given user name U to Red according to a (cid:12)xed
`pseudonym V . One possible attack, then, is for Red
`to pose as a client authenticating under identi(cid:12)er U ,
`and then see which associated pseudonym V Blue
`asserts. Red thereby learns the linkage between U
`and V . There is e(cid:11)ectively no good (and practical)
`way to defend against this type of attack. Instead, we
`rely on social factors to forestall this such behavior on
`the part of Red, namely: (1) As the service provider,
`it is Blue that will hold the list of account names, so
`that these may be di(cid:14)cult for Red to accumulate en
`bloc; and (2) Given the risk of damaged reputation,
`Red should be averse to mounting an attack against
`pseudonyms. Of course, use of pseudonyms is still
`bene(cid:12)cial in that passive compromise of Red will not
`reveal true account identi(cid:12)ers.
`
`4 False Pseudonym and Replay
`Attacks
`
`Our equality-testing protocol is designed to provide
`security against corruption of one of the two servers
`in a single session. Other security problems arise,
`however, as a result of the use of pseudonyms in our
`system and also from the need for multiple invoca-
`tions of the equality-testing protocol. In particular,
`additional protocols are needed in our system to de-
`fend against what we refer to as false-pseudonym and
`replay attacks.
`
`8
`
`USR Exhibit 2116, Page 8
`
`

`

`4.1 The false-pseudonym problem
`
`The possibility of a massive on-line false-pseudonym
`attack by a