c ACM, 2006. This is the author’s version of the work. It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in Proceedings of the 2006 ACM Symposium on Information,
Computer and Communications Security (ASIACCS’06), http://doi.acm.org/10.1145/1128817.1128827
Appears in Shiuhpyng Shieh, Sushil Jajodia (Eds.):
Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security (ASIACCS’06),
ACM, pp. 35–45, ISBN 1-59593-272-0, 2006.

Provably Secure Password-Based Authentication in TLS[Extended Abstract]
Michel Abdalla

Emmanuel Bresson

Olivier Chevassut

Departement d’InformatiqueÉcole normale supérieure
45 Rue d’Ulm
75230 Paris Cedex 05, France
http://www.di.ens.fr/˜mabdalla

Cryptology department
CELAR Technology Center
35174 Bruz Cedex, France
http://www.di.ens.fr/˜bresson

Lawrence Berkeley National
Laboratory
Berkeley, CA 94720, USA
http://www.dsd.lbl.gov/˜chevassu

Emmanuel.Bresson@m4x.org

OChevassut@lbl.gov

Michel.Abdalla@ens.fr
Bodo Möller

David Pointcheval

Dept. of Math. and Statistics
University of Calgary
Calgary, AB T2N 1N4, Canada
http://www.bmoeller.de/

Departement d’InformatiqueÉcole normale supérieure
45 Rue d’Ulm
75230 Paris Cedex 05, France
http://www.di.ens.fr/˜pointche

bmoeller@acm.org

David.Pointcheval@ens.fr
ABSTRACT

Categories and Subject Descriptors

In this paper, we show how to design an efficient, provably
secure password-based authenticated key exchange mechanism specifically for the TLS (Transport Layer Security)
protocol. The goal is to provide a technique that allows
users to employ (short) passwords to securely identify themselves to servers. As our main contribution, we describe
a new password-based technique for user authentication in
TLS, called Simple Open Key Exchange (SOKE). Loosely
speaking, the SOKE ciphersuites are unauthenticated DiffieHellman ciphersuites in which the client’s Diffie-Hellman
ephemeral public value is encrypted using a simple mask
generation function. The mask is simply a constant value
raised to the power of (a hash of) the password.

C.2.2 [Computer-Communication Networks]: Network
Protocols; E.3 [Data Encryption]: Public key cryptosystems, standards

The SOKE ciphersuites, in advantage over previous password-based authentication ciphersuites for TLS, combine
the following features. First, SOKE has formal security arguments; the proof of security based on the computational
Diffie-Hellman assumption is in the random oracle model,
and holds for concurrent executions and for arbitrarily large
password dictionaries. Second, SOKE is computationally efficient; in particular, it only needs operations in a sufficiently
large prime-order subgroup for its Diffie-Hellman computations (no safe primes). Third, SOKE provides good protocol
flexibility because the user identity and password are only
required once a SOKE ciphersuite has actually been negotiated, and after the server has sent a server identity.

An increasing number of Internet systems all around theworld are using open-source products. For examples, in the
categories of operating systems, browsers, webservers, andcryptographic engines, open-source software products suchas Linux, Mozilla, Apache, and OpenSSL are widely fielded.
For building Grid systems and applications, the referenceis the Globus toolkit1 . This toolkit unlocks the computing
power of the Internet by enabling users to tap a global network of computer systems to access information and large
distributed processing power [16]. Grid security is basedon the recognition that individual sites have their own local security policies and methods to enforce it [17]. Joining
a grid does not force a site to radically change its security
policies already in place, but rather to make them interoperable with the general grid policy. This requirement led
to the implementation in the Globus Toolkit of a security
infrastructure based on the OpenSSL software and X.509
identity certificates. Recent security compromises of userand server machines, however, have resulted in site security
policy changes. Many sites are changing their security policies to prohibit long-term private keys associated with X.509
certificates from being stored on a user’s machine. The keys

General Terms
Security

Keywords
Encrypted Key Exchange, Password Authentication, TLS

1. INTRODUCTION
1.1 Motivation

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
ASIACCS’06, March 21–24, 2006, Taipei, Taiwan.
Copyright 2006 ACM 1-59593-272-0/06/0003 ...$5.00

1

1

http://www.globus.org/

3. SOKE does not require conveying the user identity
in the very first TLS handshake messages (known as
ClientHello). This feature (also present in [23], but
not in [24]) provides additional protocol flexibility: theuser does not have to specify a user identity and password before a SOKE ciphersuite has actually been negotiated, so these values can be chosen depending on
the server identity transmitted by the server.

will instead be stored on servers in data centers where they
can be protected better.
The immediate need for Grids is a cryptographic technology that allows users to securely identify themselves to data
centers using passwords (short enough to be memorized)
and be issued short-lived public/private keys [15]. The simplest approach is to use the OpenSSL implementation of the
TLS protocol’s unilateral-authentication mode [13] and add
a straightfoward password check: the (credential repository)
server sends its X.509 certificate for explicit verification,then the user sends his password through the TLS securechannel. This is what typically happens in the MyProxy(open-source) software for managing grid security credentials2 , and generally in most of today’s “secure” WWW applications. This approach, however, provides a false senseof security because the privacy of the user’s password is lost
if the server is actually not authentic (“phishing” attacks),
and, hence, anything protected through the password could
get compromised. The password can be exposed when a user
accepts a bogus server certificate, which usually takes just asingle mouse click. And this is not all—security is in fact totally dependent on the X.509 public-key infrastructure used
for server authentication: any party with a certificate apparently issued to the legitimate server can potentially obtain
the password from the client. A single trusted Certification
Authority (CA) that is malicious or careless would do lotof harm! Sending a one-time password in place of the fixed
password would not help either since the bogus server could
turn around and use this one-time password to impersonate
the user.

1.2

SOKE ciphersuites for TLS (SOKE-TLS in short) are essentially unauthenticated Diffie-Hellman ciphersuites where
the client’s Diffie-Hellman ephemeral public value is encrypted under the password shared with the server; the encryption primitive is a mask generation function computed as
the product of the message with a constant value raised
to the power of the password. Full TLS handshakes negotiating a SOKE ciphersuite require modifications to theusual TLS handshake message flow to achieve security: theusual Finished messages of the TLS protocol, which aresent under the newly negotiated cryptographic parameters(after ChangeCipherSpec), are replaced by Authenticatormessages, which are similar in meaning to the Finished messages but must be sent under the old cryptographic parameters (namely, before ChangeCipherSpec)—that is, typically(in the case of an initial handshake) unencrypted. Also,
while usually the client sends its Finished message first,
here the server has to send its Authenticator message first.
The client can only send its Authenticator message after having verified the server’s Authenticator message (toavoid dictionary attacks since otherwise a rogue server could
try a brute force attack on the client’s password [23]).

Contributions

1.3

This paper alleviates the above problem by presenting atechnique that ties the user’s authentication to the TLS secure channel. We present a high-level description of thistechnique in TLS and a security analysis in the tradition ofprovable security. The technique goes under the name of
Simple Open Key Exchange (SOKE). Using SOKE for TLS
combines the following three features, in advantage overprevious password-based authentication ciphersuites in TLS[23, 24]:
1. SOKE has formal security arguments (in the random
oracle model under the computational Diffie-Hellman(CDH) assumption, based on Abdalla et al.’s security
definitions for password-based authenticated key exchange [3]).
2. SOKE is computationally efficient because it can workin an appropriate subgroup of the multiplicative groupof a prime field without requiring a “safe prime”; similarly, it could be used with elliptic curves or othergroups. Thus, the computations for SOKE can use
smaller exponents than those required for [23] or [24].
(The protocol described in [23] does not need safe
primes, but it does not solely work in the subgroup.
Rather, it involves an exponentiation to map arbitrary
elements of Z∗p to subgroup elements: the smaller the
subgroup, the larger the exponent for this exponentiation. SOKE, in contrast, uses only the subgroup.)2

Related Work

A Password-based Authenticated Key Exchange (PAKE) isa key exchange [14, 22] with one [19] or two flows [8, 9]
encrypted using the password as a common symmetric key.
Bellare et al. [5, 7], Boyko et al. [10], and MacKenzie [10, 20]
proposed and proved secure various PAKE structures. These
structures were later proved forward-secure under various
computational assumptions [2, 11, 12, 18]. Instantiations
for the encryption primitive were either a password-keyedsymmetric cipher or a mask generation function computed
as the product of the message with the hash of a password,
until Abdalla et al. proposed the Simple PAKE (SPAKE-)
structure with a new mask generation function computed
as the product of the message with a constant value raised
to the power of the password [4]. Whereas earlier mask
generation functions need a full-domain hash function into
the group, SPAKE provides high flexibility in the choice ofgroups (e.g., this makes it easy to work with elliptic curves).
The SOKE structure, described in the present paper, is the
SPAKE structure with only one flow encrypted.

1.4

Organization

The paper is organized as follows. In Section 2, we define
the formal security model that we use through the rest of
the paper. In Section 3, we present the algorithmic assumptions upon which the security of the SOKE scheme and, thus,
SOKE-TLS is based. In Section 4, we describe SOKE-TLS
itself, and in Section 5 we prove that it is secure via a reduction from SOKE-TLS to the computational Diffie-Hellman
problem. We finally conclude the paper by presenting our

http://grid.ncsa.uiuc.edu/myproxy/22.3

long-term objective and by describing the steps we have undertaken to achieve it.

2.

FORMAL MODEL FOR PASSWORD AUTHENTICATIONIn this section, we recall the security model of Abdalla etal. [3] for password-based authenticated key exchange protocol, which in turn implies that of Bellare et al. [5].

2.1

2.3.1

Using Weak Passwords

AKE Security

In order to model the privacy (semantic security) of thesession key, we consider the game Gameake (A, P ), in which
an additional oracle is made available to the adversary: theTest(U i ) oracle.

A password-based authenticated key exchange protocol P
is a protocol between two parties, a client C ∈ client anda server S ∈ server. Each participant in a protocol may
have several instances, called oracles, involved in distinct,
possibly concurrent, executions of P . We let U i denote theinstance i of a participant U , which is either a client or aserver.

• Test(U i ): This query tries to capture the adversary’s
ability to distinguish real keys from random ones. In
order to answer it, we need a private random coin b(unique for the whole game) and then forward to theadversary either the session key sk held by U i if b = 1
or a random key of the same size if b = 0.

Each client C ∈ client holds a password pw C . (Actually, inpractice a client implementation will typically work on behalf of a user, where a single user may be using the same
password with different client implementations, and wheremultiple users may be employing the same client implementation that queries the current user for the respective password. Also, a single user may be acting as multiple virtual users by using different passwords in different contexts.
However, in the abstract view of the security model, we
neglect these fine points and consider only abstract clients
instead, which combine the knowledge of a single password
with the computational capabilities of a client implementation.)

The Test-oracle can be queried as many times as the adversary A wants, but is available only if the queried instance U iholds a key, i.e. has accepted the key exchange session. The
simple restriction is that in the random case the same random answer will be obtained when querying two partners.
(Two player instances are said to be partners if they haveexchanged the same set of messages, and are thus expected
to hold the same session key.) When playing this game, thegoal of the adversary is to guess the hidden bit b involved in
the Test-queries, by outputting a guess b0 . Let Succ denotethe event in which the adversary is successful and correctly
guesses the value of b. The AKE advantage of an adversary A is then defined as Advake
P (A) = 2 Pr[Succ] − 1. The
protocol P is said to be (t, ε)-AKE-secure if A’s advantage
is smaller than ε for any adversary A running with time t.
Note that the advantage of an adversary that simply guesses
the bit b is 0 in the above definition due to the rescaling of
the probabilities.

If a server S ∈ server has been set up for key exchange witha given client C, this means that the respective server was
handed a value pw S [C] for said client. The value pw S [C] isdenoted a derived password [5]. Schemes where pw S [C] =pw C are called symmetric; in general, pw S [C] may differ
from pw C .
pw C and pw S [C] are also referred to as the long-lived keys ofclient C and server S. Each password pw C is considered to
be a low-entropy string, drawn from the dictionary Passwordof size N , according to the uniform distribution.

2.2

Security Notions

In order to define a notion of security for the key exchange
protocol, we consider a game in which the protocol P is
executed in the presence of the adversary A. In this game,we first draw a password pw from Password, provide cointosses and oracles to A, and then run the adversary, letting
it ask any number of queries as described above, in any
order.

It is worth pointing out that, as proven in [3], any schemethat is proven secure in the above model is also secure in
the model of Bellare et al. [5]. The converse, however, is
not necessarily true due to the non-tightness of the security
reduction (see [3] for more details).

Security Model

The interaction between an adversary A and the protocol
participants occurs only via oracle queries, which model theadversary capabilities in a real attack (see literature for moredetails [5, 12, 3].) The types of oracles available to theadversary are as follows:

2.3.2

Mutual Authentication

The above property essentially means that only the legitimate participants can obtain the secret session key, and thatan outside adversary should not be able to learn information about the key. This is also known as implicit authentication. In addition to that property, a protocol is said toachieve mutual authentication if each party can be ensured
that it has established a key with the players it intended
to. In the context of password-based protocols, authentication between the players is often done through authenticators. Intuitively, an authenticator is a value that can only be
computed (except with small probability) with the knowledge of a secret. The idea is that if a party has sent datain the clear, it must subsequently provide an authenticator• Execute(C i , S j ): The output of this query consists ofthe messages exchanged during the honest executionof the protocol. This models passive attacks.
• Send(U i , m): The output of this query is the message
that the instance U i would generate upon receipt of
message m. A query Send(U i , “start”) initializes the
key exchange protocol, and thus the adversary receives
the initial flow that the initiator would send to thereceiver. This models active attacks.
3relative to these data. We denote by SuccauthS (A) the success probability of an adversary trying to impersonate theserver (i.e., the probability that a client will finish the key
exchange protocol accepting the adversary as an authenticated server).

2.3.3

injective map P from {1, . . . , n} into G. Now let us consider
an adversary that runs in two stages. In the first stage, theadversary is given as input two random elements U and X
in G as well as the public injective map P and it outputs avalue Y in G (the chosen-basis). Next, we choose a random
password k ∈ {1, . . . , n} and give it to the adversary. We
also compute the mapping r = P(k) of the password k. The
goal of the adversary in this second stage is to output thevalue K = CDHg,G (X, Y /U r ).

Forward-Secrecy

One additional security property to consider is that offorward-secrecy. A key exchange protocol is called forwardsecure if the security of a session key between two participants is preserved even if one of these participants later iscompromised. In order to consider forward-secrecy, one has
to account for a new type of query, the Corrupt-query, whichmodels the compromise of a participant by the adversary.
This query is defined as follows:

Note that an adversary that correctly guesses the password
k in its first stage can easily solve this problem by computingr = P(k) and making, for instance, Y = g · U r so that K =X. Since we assume k to be chosen uniformly at random
from the dictionary {1, . . . , n}, an adversary that chooses
to guess the password and follow this strategy can succeed
with probability 1/n.

• Corrupt(U ): This query returns to the adversary thelong-lived key pw U for participant U . As in [5], we assume the weak corruption model in which the internal
states of all instances of that user are not returned tothe adversary.

The idea behind the password-based chosen-basis computational Diffie-Hellman assumption is that no adversary can
do much better than the adversary described above: that is,
Succpccdh (t, n) cannot be significantly larger than 1/n, where
n is the size of the dictionary.

In order to define the AKE success probability in the presence of this new type of query, one should extend the restriction in the random case: all the executions completed
after the Corrupt-query are answered with the real session
key.

3.1.3

SPCCDHg,G :Set Password-Based ChosenBasis Computational Diffie-Hellman

This is a generalization of the above problem, in which theadversary, in the second stage, outputs a set of candidates
for K. It wins if the set indeed contains K: Succspccdh (t, s, n)
is the maximal probability to output a valid set of size s,
within time t. The SPCCDHg,G problem is equivalent to theCDHg,G problem as shown in Appendix A.

Let Succ denote the event in which the adversary successfully guesses the hidden bit b used by Test oracle. The
FS-AKE advantage of an adversary A is then defined as
Advake−fs(A) = 2 Pr[Succ] − 1. The protocol P is said to beP(t, ε)-FS-AKE-secure if A’s advantage is smaller than εfor any adversary A running with time t.

3.2

Pseudo-Random Functions

A pseudo-random function family (PRF) is a family of functions F = (fk )k in Fm,n , the set of the functions from{0, 1}m into {0, 1}n , indexed by a key k ∈ {0, 1}` , so thatfor a randomly chosen `-bit key k, no adversary can distinguish the function fk from a truly random function inFm,n : we define the advantage Advprf
F (D, q) = | Prk [1 ←Dfk ] − Prf [1 ← Df ]|, where D is a distinguisher, with anoracle access to either a random instance fk in the given
family F or a truly random function f in Fm,n , and must
distinguish the two cases with at most q queries to the function oracle. We say that such a family is a (q, ε, t)-PRF if forany distinguisher asking at most q queries to the oracle, its
advantage is less than ε, after a running time bounded by t.

3. INTRACTABILITY ASSUMPTIONS
3.1 Diffie-Hellman Problems
The arithmetic is in a finite cyclic group G = hgi of order a `-bit prime number q, where the operation is denoted
multiplicatively.

3.1.1 CDHg,G : Computational Diffie-Hellman
A (t, ε)-CDHg,G attacker, in a finite cyclic group G ofprime order q with g as a generator, is a probabilistic machine ∆ running in time t such that its success probabilityxyxy
Succcdh,g,G (∆), given random elements g and g to output gis greater than ε:

3.3

x
y
xy
Succcdh] ≥ ε.
g,G (∆) = Pr[∆(g , g ) = g

Message Authentication Codes

A Message Authentication Code, say MAC = (MAC.Sign,
MAC.Verify), is made of the two following algorithms, witha secret key sk uniformly distributed in {0, 1}` :We denote by Succcdh
g,G (t) the maximal success probability
over every adversaries running within time t. The CDHAssumption states that Succcdh
g,G (t) ≤ ε for any t/ε not toolarge.

• The MAC generation algorithm MAC.Sign. Given a
message m and secret key sk ∈ {0, 1}` , MAC.Sign produces an authenticator µ. This algorithm might beprobabilistic.

3.1.2 PCCDHg,G : Password-Based Chosen-Basis
Computational Diffie-Hellman
The so-called password-based chosen-basis computational
Diffie-Hellman problem is a variation of the computational
Diffie-Hellman that is more appropriate to the passwordbased setting: Let D = {1, . . . , n} be a dictionary containing n equally likely password values and let P be a public• The MAC verification algorithm MAC.Verify. Givenan authenticator µ, a message m and a secret key sk,
MAC.Verify tests whether µ has been produced using
MAC.Sign on inputs m and sk.
4

The classical security level for MAC is to prevent existential forgeries, even for an adversary which has access to
the generation and the verification oracles. We denote by
Succmac (t, q) the maximum success probability of a forger
running within time t and making at most q queries to the
MAC.Sign oracle.

4.

(b) If the server holds a private key and certificate
suitable for signing, then in specific SOKE ciphersuites the server additionally sends the certificate to the client via a Certificate message.
In this case the ServerKeyExchange message additionally contains a signature on the ephemeral
Diffie-Hellman public key made with the server’s
long-term key—similar to non-anonymous standard Diffie-Hellman ciphersuites in TLS (cf. [13]).

A SIMPLE OPEN KEY EXCHANGE FOR
TLS (SOKE-TLS)(c) The server then sends an empty message in theform of a ServerHelloDone to indicate that the“hello” phase is completed.

In this section, we describe the Diffie-Hellman Simple
Open Key Exchange (SOKE), an efficient, provably secure
password-based authenticated key exchange for TLS ciphersuites. The proof of security is based on the computational
Diffie-Hellman assumption and holds in the random oracle
model. The use of the random oracles, however, is very
limited. More precisely, we only model a hash function as arandom oracle during the extraction of the pre-master secretfrom the Diffie-Hellman result.

(d) If the server has sent a Certificate message, theclient verifies the signature.
(e) The client generates its random private exponent
x and computes the second Diffie-Hellman public
key as X = g x . That latter key is encrypted(using a password) as the product of the key withthe password-based mask: X ? = g x × U pw . The
client encapsulated its name and the encrypted
value in the ClientKeyExchange message which
is sent out.

As described below, the protocol does use the password in
the key derivation process. As it will become clear in thenext section, this simple enhancement plays a major role inthe security of SOKE and enables us to prove its forwardsecurity under concurrent executions without imposing any
restrictions on the size of the dictionary.

4.1(f) The client and the server can now compute thecommon Diffie-Hellman secret Z = g xy from thevalues they received in the ServerKeyExchange
and ClientKeyExchange messages, respectively.

The Handshake

Figure 1 illustrates the full TLS handshake for the case of
SOKE-TLS ciphersuites. Since the abbreviated handshakefor resuming a previously negotiated session is performed
exactly as in other TLS ciphersuites, we only discuss thedetails of the full handshake.

Note. In the protocol description, C and S are strings
giving the client identity and server identity, respectively (i.e., a user name and a server or “realm” name).
The password for the user denoted by C is a string pw.
Observe that the client identity C and the password pw
are not used within the protocol before the server has
chosen a SOKE ciphersuite and transmitted the server
identity S. This means that a user only needs to provide C and pw after seeing that a SOKE handshakewith S is going on. For example, HTTP servers might
required password-based ciphersuites only for specificsubtrees of their URL space by requesting a TLS renegotiation if necessary, and the server identity might
depend on the specific URL.

1. Choose Ciphersuite. The client and the server negotiate the ciphersuite to use and exchange nonces.
(a) The client sends its list of supported ciphersuites,
including SOKE-TLS ciphersuites, in the TLS initial ClientHello message. It includes a nonce Nc
as well. (In the TLS specification, this nonce is
known as ClientHello.random.)(b) The server specifies the ciphersuite to be used,
selected from the client’s list, by using a TLS
ServerHello message. It also includes a nonce
Ns (known as ServerHello.random).

A detail not shown in the figure is that the server, with
its ServerKeyExchange message, will also send an index into the list of standardized groups for SOKE (suchas 0, 1, 2, . . . for standardized 1024-bit, 1536-bit, 2048bit, . . . prime moduli with appropriate subgroups).
The client should display the server’s choice of groupto the client, and the user should provide his password
only if he agrees with the group.

Note. Each SOKE ciphersuite specifies a symmetric encryption algorithm (AES-CBC with either 128-bit or
256-bit keys) as well as an integrity algorithm (HMACSHA1) to use once the handshake has completed. Also,
appriorate prime-order groups are standardized in the
ciphersuite specification; they are equipped with twogenerators g and U that have been generated verifiably pseudo-randomly to provide assurance that noone knows logg U (see [1]).

Note that when the client receives Y from the server
and when the server receives X ? from the client, it is
implicit that the respective recipient performs a groupmembership test: it is a fatal TLS handshake failure
if Y or X ? is not a group member.

2. Compute Diffie-Hellman Secret.
3. Compute Pre-Master Secret and Authentication Key.

(a) First, the server generates the random private exponent y and computes the Diffie-Hellman publickey Y = g y . The public key is sent to the clientin the form of a ServerKeyExchange message, together with the server’s identity.

(a) The parties extract the randomness in the DiffieHellman result to form the pre-master secret as:
PreMasterSecret = Hash(C, S, pw , X ? kY kZ).
5

Client C(password pw )Server S(password pw )accept ← false

accept ← false
Choose ciphersuite:Rchoose Nc ← {0, 1}∗

ClientHello : (Nc , . . .)−−−−−−−−−−−−−−−−−→
ServerHello : (Ns , . . .)←−−−−−−−−−−−−−−−−−

R

choose Ns ← {0, 1}∗

Compute Diffie-Hellman secret:ServerKeyExchange : (S, Y )ServerHelloDone←−−−−−−−−−−−−−−−−−−−−

R

choose y ← Z?q , compute Y ← g y

Rchoose x ← Zq , compute X ← g x
encrypt X ? ← X × U pw

ClientKeyExchange : (C, X ? )−−−−−−−−−−−−−−−−−−−−−−→Z = Y x = Xy

decrypt X ← X ? /U pw

Compute pre-master secret and authentication key:
PreMasterSecret = Hash(C, S, pw , X ? kY kZ)
AuthKey = PRF1 (PreMasterSecret, Nc kNs )Compute authenticators:
AuthC = MAC.SignAuthKey (“client finished”, . . .)Abort if verification fails. Else:accept ← true

AuthS = MAC.SignAuthKey (“server finished”, . . .)Authenticator : AuthS←−−−−−−−−−−−−−−−−−
Authenticator : AuthC[ChangeCipherSpec]−−−−−−−−−−−−−−−−−→[ChangeCipherSpec]←−−−−−−−−−−−−−−

Abort if verification fails. Else:accept ← true

Compute master secret and key material as in standard TLS:
MasterSecret = PRF2 (PreMasterSecret, Nc kNs )KeyBlock = PRF3 (MasterSecret, Ns kNc )←−−−−−−−−−− Secure Channel −−−−−−−−−−→
Figure 1: The full handshake for SOKE-TLS ciphersuites.
(b) The pre-master secret is used as a means to derive
the authentication key AuthKey used by the parties to perform the mutual authentication; we define AuthKey = PRF1 (PreMasterSecret, Nc kNs ).
This key derivation is performed based on thestandard TLS pseudo-random function PRF (see[13, Sec. 5]). The function PRF1 (PreMasterSecret,z) used here is specific to SOKE ciphersuites; itsvalue is obtained as PRF(PreMasterSecret, “authentication key”, z).

ways to instantiate Hash1 are discussed in [6].
4. Compute Authenticators.
(a) Both parties use AuthKey to produce the authenticators AuthC and AuthS . More precisely, theauthenticator is set as a MAC on “finished label khash of handshake”, in which finished label is thestring “client finished” or “server finished”, depending on which party is sending the respective
message, and where hash of handshake denotes
the hash of the concatenation of all the handshakemessages sent so far in both directions exactly as
would be used for the Finished message in other
TLS ciphersuites (i.e., the MD5 hash concatenated with the SHA-1 hash). The server sends
its Authenticator message first.

Note. Here the randomness extractor function Hash(z1,z2 , z3 , z4 ) is defined as a function with multiple inputs.
The reason for this is that while we assume that groupelements can be represented as fixed-length strings,
the same does not hold for the strings C, S, and pw .
A function Hash1 (z) in a single input can be used
to implement
Hash by defining Hash(z1 ,´z2 , z3 , z4 ) =`Hash1 SHA1(z1 )kSHA1(z2 )kSHA1(z3 )kz4 . The function Hash1 (z), in turn, can be instantiated by using
SHA1(constanth0ikz)kSHA1(constanth1ikz)k. . . Other(b) The client first checks the server’s authenticator,
and, if correct, sends its own Authenticator, andthen proceeds to the ChangeCipherSpec message.
6

(c) The server then checks the client’s authenticator, and, if correct, replies with the
ChangeCipherSpec message as well.

the protocol reduces to finding pw . In other words, at the
protocol level, pw is the password needed for authenticationand password is just a way to remember it.

Note. Usual TLS ciphersuites send Finished messages for authentication after switching to the newly
negotiated key material (KeyBlock) in the TLS record
layer (which event is indicated by a ChangeCipherSpec
message). This approach, however, would violate thesecurity notion that SOKE ciphersuites are designed
to achieve. Instead, SOKE ciphersuites make use ofAuthenticator messages; the client does not send its
Authenticator and ChangeCipherSpec before it hasverified the server’s Authenticator, and the serverdelays its ChangeCipherSpec until it has verified theclient’s Authenticator. Note that the Authenticatormessage does not undergo any processing using the
KeyBlock, since it precedes the ChangeCipherSpec;
this is different from the handshake in other TLS ciphersuites where Finished is sent in an TLS record
processed under key material KeyBlock (see [13]).

4.2.2

pw i = hash(i k password) mod qi .

4.2.3

5.

SECURITY ANALYSIS OF SOKE-TLS

Theorem 5.1. [FS-AKE Security] Let us consider theabove protocol, over a group of prime order q, where
Password is a dictionary of size N , equipped with the uniform distribution. Let A be an adversary running withina time bound t that makes less than qactive active sessions
with the parties and qpassive passive eavesdropping queries,
and asks qhash hash queries. Then we have(a) Both parties compute a common MasterSecret,using a function PRF2 (PreMasterSecret, z) that isdefined as PRF (PreMasterSecret, “mastersecret”,z).
(b) The MasterSecret is then used to obtain KeyBlockas a function PRF3 (MasterSecret, z), which is defined as PRF(MasterSecret, “key expansion”, z).
This two-stage derivation process is used by TLS
session resumption: a new connection with newclient and server nonces Nc and Ns can continue
to use a previously negotiated MasterSecret andderive a new KeyBlock.

S
Succauth
SOKE (A) ≤2qactiveN+qhash (qactive qhash + qactive + 1) × Succcdh (t + 2τe )qhash 2qhash 2+ 2qhash 2 × Succmac (t, 0) + `+1`
m2
2
qpassive 2
qactive 2
prf++2qsession × Adv (t, 2) +
2q
2q 2

+2

Note. Another change from the standard TLS handshake message flow, besides having Authenticator
sent before ChangeCipherSpec, is that for SOKE theserver and not the client provides its authentication
message first. This is necessary to protect clients
against dictionary attacks: if the client was to makethe start, its Authenticator message could be used bya malicious server that does not know pw to try out
different passwords in an offline attack, looking which
one results in the Authenticator message as observed.

4.2.1

Using the Password with Several Servers

The password string password should be hashed before being used as an exponent pw . If the protocol is changed again
to use (C, S, pw ) instead of just password to derive the exponent, we obtain a security improvement in practice in thata client can use the same password (string) with multiple
servers and yet the respective secrets (effective passwords)
will be different. (However, every server could run a dictionary attack to recover the common underlying password.)

5. Compute Master Secret and Key Material. The
material KeyBlock is the bit string assigned to the Initialization Vectors (IVs), MAC secrets, and encryption
keys which will protect the application sensitive messages. KeyBlock, exactly as in other TLS ciphersuites,
is obtained indirectly, in two steps:

4.2

Password Derivation for Different Groups

Remember that the protocol should allow using one out ofa set of different groups (the client likely wants to see thegroup being used before typing his password). So for group i,
the effective password pw may be defined in the form

Advake−fs
SOKE (A) ≤6qactiveN+2qhash (3qactive qhash + qactive + 1) × Succcdh (t + 2τe )qhash 2qhash 2
+ 8qhash 2 × Succmac (t, 0) +
`
2m
2`
2
qactive
qpassive 2+8qsession × Advprf (t, 2) +
+
q
q2
+8

where τe denotes the computational time for an exponentiation in G.

Additional Remarks
How the Password Becomes an Exponent

Since the password pw appears as an exponent in the computations for SOKE ciphersuites, some additional hash isneeded to obtain this exponent from the password string
password . In the protocol description, we do not care about
details of the hash and simply use the hash result pw (in the
exponent space) as the “effective password” instead: anyone knowing pw is actually able to impersonate the clientor the server, and the security proof shows that attacking

Proof. We are interested in the event S, which occurs
if the adversary correctly guesses the bit b involved in the
Test-queries. We furthermore consider server (unilateral)authentication: event A is set to true if a client instanceaccepts, without any server partner. Let us remember thatin this attack game, the adversary is allowed to use Corruptqueries.
7

Game G0 : This is the real protocol, in the random-oracle
model:
Advake−fs
SOKE (A) = 2 Pr[S0 ] − 1

messages it receives from the oracle instances. More precisely, we replace Hash by Hash0 when computing the valueof PreMasterSecret whenever the values (C, S, X ? kY ) weregenerated by oracle instances. Note that we can safely doso due to the absence of collisions in the transcript. Like in
G3 , any value PreMasterSecret computed during such passive sessions becomes completely independent of Hash and
DH-ResultC/S .

(1)

SAdvauth
SOKE (A) = Pr[A0 ].

Let us furthermore define the event Sw/tA = S ∧ ¬A, whichmeans that the adversary wins the Real-Or-Random gamewithout breaking authentication.

As in previous games, we can upper-bound the difference inthe success probabilities of A in games G4 and G3 by upperbounding the probability that A queries the hash function
Hash on (C, S, pw, X ? kY kDH-ResultC/S ), for such a passive
transcript. We call this event AskH-Passive-Send. Towards
this goal, we consider an auxiliary game G4 ’, in which thesimulation of the players changes slightly without affecting
the view of the adversary. In this simulation, we choose at
random one of the Send(S, “start”)-queries being asked to S
and we reply with Y = V (hoping that is one of the sessions
that the adversary simply forwards the message). On theclient side, we change the simulation whenever it receives as
input a message that? was generated by a server instance, bycomputing X ? as g x . If the event AskH-Passive-Send occurs
and our guess for the active
session is correct,
then we can?
?
extract K = CDHg,G (g x /U pw , V ) = V x /CDHg,G (U, V )pw
from ΛHash :Game G1 : In this game, we simulate the hash oracles (Hash, but also an additional hash function Hash0 :({0, 1}? ×)3 → {0, 1}` that will appear in the Game G3
as usual by maintaining hash lists ΛHash and ΛHash0 . We
also simulate all the instances, as the real players would do,for the Send-queries and for the Execute, Test and Corruptqueries.
Game G2 : We cancel games in which some collisions appear on the transcripts (C, S, X ? , Y ), and on the master secrets. Regarding the transcripts, the distance follows fromthe birthday paradox since at least one element of each transcript is generated by an honest participant (at least one ofthem in each of the qactive active attacks, and all of themin the qpassive passive attacks). Likewise, in the case of themaster keys, a similar bound applies since Hash is assumed
to behave like a random oracle (which outputs `-bit bitstrings):
qpassive 2
qhash 2
qactive 2++.
Pr[Coll2 ] ≤
2q
2q 2
2`+1

Pr[AskH-Passive-Send4 ] ≤qactive × qhash × Succcdh
g,G (t + 2τe ).

Game G5 : In this game, we make one of the most significant modifications. We replace the oracle Hash by the private oracle Hash0 whenever the input to this query contains
an element that was not generated by an oracle instanceand no Corrupt-query has occurred. More precisely, if either the value X ? or Y in the Hash-query (C, S, pw, X ? kY k
DH-ResultC/S ) was generated by the adversary, then we reply to this query using Hash0 (C, S, X ? kY ) as long as no Corrupt-query has occurred. Clearly, the games G5 and G4
are indistinguishable as long as A does not query the hashfunction Hash on an input (C, S, pw, X ? kY kDH-ResultC/S ),where DH-ResultC/S = CDHg,G (X ? /U pw , Y ), for some execution transcript (C, S, X ? , Y ). We denote this bad event
by AskHbC-Active. Thus,

Game G3 : In this game, we show that the success probability of the adversary is negligible in passive attacks via
Execute-queries. To do so, we modify the way in which wecompute the pre-master secret PreMasterSecret in passive
sessions that take place before or after a Corrupt-query. Moreprecisely, whenever the adversary asks a Execute-query, we
compute the pre-master secret PreMasterSecret as Hash0 (C,S, X ? kY ) using the private oracle Hash0 instead of the oracle
Hash. As a result, it holds that any value of PreMasterSecretcomputed during a passive session becomes completely independent of Hash and DH-ResultC/S , which are no longer
needed in these sessions. Please note that the oracle Hash isstill being used in active sessions.

| Pr[A5 ] − Pr[A4 ] | ≤ Pr[AskHbC-Active]| Pr[Sw/tA5 ] − Pr[Sw/tA4 ] | ≤ Pr[AskHbC-Active]

The games G3 and G2 are indistinguishable unless the adversary A queries the hash function on (C, S, pw, X ? kY k
DH-ResultC/S ), for such a passive transcript: we denotesuch event by AskH-Passive-Exe. In order to upper-boundthe probability of this event, we consider an auxiliary game
G3 ’, in which the simulation of the players changes—but
the distributions remain perfectly identical. Since we do notneed to compute DH-ResultC/S for the simulation of Execute?
?
queries, we can simulate Y as V y and X ? as g x . If event?
AskH-Passive-Exe occurs, one can extract K = CDHg,G (V y ,x?
pw
x? y ?
y ? pwg /U ) = V/CDHg,G (U, V )from ΛHash :Pr[AskH-Passive-Exe3 ] ≤ qhash × Succcdh
g,G (t + 2τe ).

(4)

(2)

(5)

Game G6 : In this game, we replace the pseudo-randomfunctions by truly random functions for all the sessions inwhich the value of PreMasterSecret has been derived with theprivate oracle Hash0 . Since the value PreMasterSecret that isbeing used as the secret key for the pseudo-random function
is independently and uniformly distributed, the distance canbe proven by a classical sequence of hybrid games, where
the counter is on the pre-master secrets. That is, each timea new pre-master secret is set, we increment the counter.
Then, Pr[Sw/tA6 ] = 21 .

(3)

| Pr[A6 ] − Pr[A5 ] | ≤ qsession Advprf (t, 1)| Pr[Sw/tA6 ] − Pr[Sw/tA5 ] | ≤ qsession Advprf (t, 2).

Game G4 : In this game, we consider passive attacks via
Send-queries, in which the adversary simply forwards the8(6)has (X ? , Y, pw 0 , K0 = CDHg,G (X ? /U pw 0 , Y )) and (X ? , Y,
pw 1 , K1 = CDHg,G (X ? /U pw 1 , Y )). We denote this event
CollH.

Game G7 : In this game, we exclude collisions on MAC
keys for all the sessions in which the pre-master secret
PreMasterSecret has been derived with the private oracle
Hash0 (which event is denoted CollPRF). Let `m denote thelength of MAC keys. Since for these sessions, the MAC keys
are independently and uniformly distributed, the probabilities differ from those in the previous game by at mostPr[CollPRF7 ] ≤ qhash 2 /2`m .

In order to upper-bound the probability of event CollH, weconsider an auxiliary game in which the simulation of theplayers changes slightly without affecting the view of the adversary. The goal is to use the adversary to help us computethe computational Diffie-Hellman value of U and V . In thissimulation, we choose at random one of the Send(S, “start”)queries being asked to S and we reply with Y = V in thehope that this is the session which leads to a collision in thetranscript. For all other sessions, Y is simulated as g y . Now,
let us assume that the event CollH happens. If our guess for
the Send(S, “start”)-query was correct, then we can extract
the value CDHg,G (U, V ) as (K1 /K0 )u , where u is the inverseof (pw 0 − pw 1 ), by simply guessing the indices of the twohash queries involved in the collision. We note that u isguaranteed to exist since pw 0 6= pw 1 . It follows that

(7)

Game G8 : In this game, we exclude games wherein forsome transcript (C, S, X ? , Y ), there are two passwords pw 0
and pw 1 such that the corresponding pre-master secrets leadto a collision of the MAC-values (which event is denoted
CollM).
Since we know that MAC-keys are truly random and different from each other at this point, the event CollM meansthat a MAC with a random key (one of the qhash possible
values) may be a forgery for another random key. Thus, byrandomly choosing the two indices for the hash queries, we
get the following upper-bound:
Pr[CollM8 ] ≤ qhash 2 × Succmac (t, 0).

Pr[CollH] ≤ qsend × qhash 2 × Succcdh
g,G (t + τe )When the event CollH does not happen, for each transcript (X ? , Y ) in which Y was created by server instance,
there is at most one password value pw such that the tuple(X ? , Y, K = CDHg,G (X ? /U pw , Y )) is in ΛHash . As a result,the probability of the adversary in impersonating a client
reduces to trying one password at a time. Thus,(8)

Game G9 : Before proceeding with the analysis, we first
split the event AskHbC-Active into two disjoint sub-cases
depending on whether the adversary impersonates theclient or the server. We denote these events AskHbCw S
and AskHbCw C, respectively. In this game, we focus on
AskHbCw C only. We now reject all the authenticators sentby the adversary for all the sessions in which the pre-mastersecret PreMasterSecret has been derived with the private oracle Hash0 : Pr[A9 ] = 0. In order to evaluate the distance
between the games G9 and G8 , we consider the probabilityof the event AskHbCw C, in which the adversary succeeds infaking the server by sending a valid authenticator before a
Corrupt-query.

Pr[AskHbCw S10 ] ≤ qfake−client /N +qsend × qhash 2 × Succcdh
g,G (t + τe )This concludes the proof of Theorem 5.1.

6.

CONCLUSION

The present paper describes efficient and provably secure
methods for password-based authentication in the TLS protocol. Besides formal security arguments and good efficiency, these SOKE-TLS ciphersuites offer a message flowthat is convenient in practice because the user identity andpassword need only be supplied if one of these ciphersuites
has actually been negotiated in the TLS handshake. We provide a low-level specification of these ciphersuites for TLS
in [1]. In that document (intended for eventual publication as an Internet RFC), we specify the ciphersuites, provide standard group parameters and correct instantiations
for the cryptographic transformations, define data structures for the handshake messages and the formatting ofdata on the wire, as well as additional handshake protocol details. The final goal of the authors is to publish as
open source an implementation of these ciphersuites for the
OpenSSL software toolkit conforming to this specification.
This will, we hope, benefit open-source products such as the
Globus Toolkit whose communications’ security is based on
the OpenSSL software.

To evaluate the probability of event AskHbCw C, we note
that, up to the moment in which a Corrupt-query occurs,
no information on the password pw of a user is revealed
to the adversary, despite the fact that the password is stillused in the computation of X ? . To see that, note that, forany given transcript (X ? , Y ) in which X ? was created byan oracle instance and for each password pw , there exists avalue x ∈ Zq such that X ? = g x U pw which is never revealed
to the adversary. Moreover, since we have removed collisions
on the pre-master secrets, on the MAC keys, and on the
MAC values, there is at most one password that can lead toa valid authenticator. As a result, the probability that theadversary succeeds in sending a valid authenticator in eachsession is at most 1/N . Thus, we get
Pr[AskHbCw C9 ] ≤ qfake−server /N.

(10)

(9)

Game G10 : We finally concentrate on the success probability of the adversary in faking the client. What we show inthis game is that the adversary cannot eliminate more than
one password in the dictionary by impersonating a client.
To do so, we first upper-bound the probability that, forsome transcript (X ? , Y ) in which Y was created by server
instance, there are two hash queries in ΛHash such that one

7.

ACKNOWLEDGMENTS

The first and fifth authors have been supported in part by
the European Commission through the IST Program under Contract IST-2002-507932 ECRYPT. The third author
was supported by the Director, Office of Science, Office9

of Advanced Scientific Computing Research, Mathematical Information and Computing Sciences Division, of the
U.S. Department of Energy under Contract No. DE-AC0376SF00098. This document is report LBNL-57609. See
http://www-library.lbl.gov/disclaimer.

[12] E. Bresson, O. Chevassut, and D. Pointcheval. New
security results on encrypted key exchange. In F. Bao,
R. Deng, and J. Zhou, editors, PKC 2004, volume2947 of LNCS, pages 145–158. Springer-Verlag, Mar.
2004.

8.

[13] T. Dierks and C. Allen. RFC 2246 - The TLS Protocol
Version 1.0. Internet Activities Board, Jan. 1999.

REFERENCES[1] M. Abdalla, E. Bresson, O. Chevassut, A. Essiari,
B. Möller, and D. Pointcheval. SOKE ciphersuites forpassword-based authentication in TLS. Work in
Progress, to be published as Internet Draft, 2006.

[14] W. Diffie and M. E. Hellman. New directions incryptography. IEEE Transactions on Information
Theory, 22:644–654, 1978.
[15] L. Fang, S. Meder, O. Chevassut, and F. Siebenlist.
Secure password-based authenticated key exchange forweb services. In E. Damiani and H. Maruyama,
editors, Proceedings of the ACM Workshop on Secure
Web Services (SWS), Fairfax, VA, USA, Oct. 29, 2004.

[2] M. Abdalla, O. Chevassut, and D. Pointcheval.
One-time verifier-based encrypted key exchange. In
S. Vaudenay, editor, PKC 2005, volume 3386 of
LNCS, pages 47–64. Springer-Verlag, Jan. 2005.
[3] M. Abdalla, P.-A. Fouque, and D. Pointcheval.
Password-based authenticated key exchange in thethree-party setting. In S. Vaudenay, editor, PKC 2005,
volume 3386 of LNCS, pages 65–84. Springer-Verlag,
Jan. 2005.

[16] I. T. Foster and C. Kesselman. The Grid 2: Blueprint
for a New Computing Infrastructure. Morgan
Kaufmann, 2004.
[17] I. T. Foster, C. Kesselman, G. Tsudik, and S. Tuecke.
A security architecture for computational grids. In
ACM CCS 98, pages 83–92. ACM Press, Nov. 1998.

[4] M. Abdalla and D. Pointcheval. Simple
password-based encrypted key exchange protocols. In
A. Menezes, editor, CT-RSA 2005, volume 3376 of
LNCS, pages 191–208. Springer-Verlag, Feb. 2005.

[18] J. Katz, R. Ostrovsky, and M. Yung. Forward secrecy
in password-only key exchange protocols. In
S. Cimato, C. Galdi, and G. Persiano, editors, SCN
02, volume 2576 of LNCS, pages 29–44.
Springer-Verlag, Sept. 2002.

[5] M. Bellare, D. Pointcheval, and P. Rogaway.
Authenticated key exchange secure against dictionary
attacks. In B. Preneel, editor, EUROCRYPT 2000,
volume 1807 of LNCS, pages 139–155.
Springer-Verlag, May 2000.

[19] S. Lucks. Open key exchange: How to defeat
dictionary attacks without encrypting public keys. In
Workshop on Security Protocols, École Normale
Supérieure, 1997.

[6] M. Bellare and P. Rogaway. Random oracles arepractical: A paradigm for designing efficient protocols.
In ACM CCS 93, pages 62–73. ACM Press, Nov. 1993.

[20] P. D. MacKenzie. The PAK suite: Protocols forpassword-authenticated key exchange. Technical
Report 2002-46, DIMACS, 2002.

[7] M. Bellare and P. Rogaway. The AuthA protocol for
password-based authenticated key exchange.
Contributions to IEEE P1363, Mar. 2000.

[21] D. Pointcheval and J. Stern. Security arguments for
digital signatures and blind signatures. Journal of
Cryptology, 13(3):361–396, 2000.

[8] S. M. Bellovin and M. Merritt. Encrypted key
exchange: Password-based protocols secure against
dictionary attacks. In 1992 IEEE Symposium on
Security and Privacy, pages 72–84. IEEE Computer
Society Press, May 1992.

[22] R. L. Rivest, A. Shamir, and L. M. Adleman. A
method for obtaining digital signature and public-key
cryptosystems. Communications of the ACM,
21(2):120–126, 1978.

[9] S. M. Bellovin and M. Merritt. Augmented encrypted
key exchange: A password-based protocol secureagainst dictionary attacks and password filecompromise. In ACM CCS 93, pages 244–250. ACM
Press, Nov. 1993.

[23] M. Steiner, P. Buhler, T. Eirich, and M. Waidner.
Secure password-based cipher suite for TLS. ACM
Transactions on Information and System Security,4(2):134–157, 2001.
[24] D. Taylor, T. Wu, N. Mavroyanopoulos, andT. Perrin. Using SRP for TLS authentication. IETF
Internet Draft, TLS Working Group, Aug. 19, 2004.

[10] V. Boyko, P. D. MacKenzie, and S. Patel. Provably
secure password-authenticated key exchange using
Diffie-Hellman. In B. Preneel, editor,
EUROCRYPT 2000, volume 1807 of LNCS, pages
156–171. Springer-Verlag, May 2000.

APPENDIX
A. EQUIVALENCE OF THE SPCCDH AND
CDH PROBLEMS[11] E. Bresson, O. Chevassut, and D. Pointcheval.
Security proofs for an efficient password-based key
exchange. In ACM CCS 03, pages 241–250. ACM
Press, Oct. 2003.

Here we show that the Set Password-based ChosenBasis Computational Diffie-Hellman SPCCDHg,G problem is
10Let A be an adversary against the SPCCDHg,G -problem,with success probability α = 1/n + ε. Then, we can use
the splitting lemma, with β = ε/2, on

equivalent to the (basic) computational Diffie-Hellman problem CDHg,G . With same notations as in Section 3.1, if one
has:
1
Succspccdh (t, s, n) ≥ + ε,n˘¯then, with ν = max n1 , 2ε , one has:
„
«
1
εν
+ν .
(11)
Succcdh (2t + τe ) ≥ 2 ×
2sn

A = {(ω, U, X)} and B = {1, . . . , n} ≈ D.
Our adversary B receives as input a random CDHg,G instance(U, X). It chooses a random tape ω for A: with probability greater than ε/2, the success probability is greaterthan 1/n + ε/2, over the probability space B = {1, . . . , n}.
It is thus a multiple of 1/n, not smaller than 1/n + ν,
where ν is the maximum in {1/n, ε/2}. One first simply
runs A with a random k, and with probability greater than
1/n + ν, one gets a first set S1 with K = CDHg,G (X, Y /U k ).
One runs A again, with another random k0 6= k, andwith probability greater than ν, one gets a second set S20with K 0 = CDHg,G (X, Y /U k ). Then, CDHg,G (X, U ) =0(K/K 0 )1/(k−k ) . By choosing two elements at random in S1and S2 , one gets CDHg,G (X, U ) with probability 1/s2 .

Proof. For proving this relation, one simply applies the
splitting lemma [21]:Lemma A.1. [Splitting Lemma] Let S ⊂ A × B such that
Pr[(a, b) ∈ S] ≥ α. For any β < α, definenoT = (a, b) ∈ A × B 0Pr [(a, b0 ) ∈ S] ≥ α − β .
b ∈B

Then
(i)

Pr[T ] ≥ β,(ii)∀(a, b) ∈ T, 0Pr [(a, b0 ) ∈ S] ≥ α − β.
b ∈B11