1040 lines
58 KiB
Plaintext
1040 lines
58 KiB
Plaintext
Owl: An Augmented Password-Authenticated
|
||
Key Exchange Scheme
|
||
|
||
Feng Hao1 , Samiran Bag1 , Liqun Chen2 , and Paul C. van Oorschot3
|
||
1
|
||
University of Warwick, UK
|
||
{feng.hao, samiran.bag}@warwick.ac.uk
|
||
2
|
||
University of Surrey, UK
|
||
liqun.chen@surrey.ac.uk
|
||
3
|
||
Carleton University, Canada
|
||
paulv@scs.carleton.ca
|
||
|
||
|
||
Abstract. We present Owl, an augmented password-authenticated key
|
||
exchange (PAKE) protocol that is both efficient and supported by secu-
|
||
rity proofs. Owl is motivated by recognized limitations in SRP-6a and
|
||
OPAQUE. SRP-6a is the only augmented PAKE that has enjoyed wide
|
||
use in practice to date, but it lacks the support of formal security proofs,
|
||
and does not support elliptic curve settings. OPAQUE was proposed
|
||
in 2018 as a provably secure and efficient alternative to SRP-6a, and
|
||
was chosen by the IETF in 2020 for standardization, but open issues
|
||
leave it unclear whether OPAQUE will replace SRP-6a in practice. Owl
|
||
is obtained by efficiently adapting J-PAKE to an asymmetric setting,
|
||
providing additional security against server compromise yet with lower
|
||
computation than J-PAKE. Owl is provably secure, efficient and agile
|
||
in supporting implementations in diverse multiplicative groups and el-
|
||
liptic curve settings. To the best of our knowledge, Owl is the first aug-
|
||
mented PAKE solution that provides systematic advantages over SRP-6a
|
||
in terms of security, computation, message sizes, and agility.
|
||
|
||
|
||
1 Introduction
|
||
Password authenticated key exchange (PAKE) allows two parties to establish
|
||
a high-entropy session key only based on a shared low-entropy secret (e.g., a
|
||
memorable password) [3]. In general, there are two types of PAKE protocols:
|
||
balanced and augmented (also resp. called symmetric and asymmetric PAKE).
|
||
In the former, two parties share a common secret (e.g., a password or a hash
|
||
of a password). In the latter, which is customized for a client-server setting, a
|
||
client holds a password but the server stores only a one-way transformation of it.
|
||
The idea is that reversing the transformation requires an offline search that pro-
|
||
ceeds by guessing through an enumeration of candidate passwords. Augmented
|
||
PAKE improves security (vs. balanced PAKE) in case of server compromise: in
|
||
a balanced PAKE, any plaintext credentials stolen from a server can be directly
|
||
used to impersonate clients, but in an augmented PAKE, to recover plaintext
|
||
passwords requires an offline search. This is an easy way to make attacks more
|
||
expensive, without involving tamper-resistant hardware or multiple servers [19].
|
||
Many augmented PAKE protocols are available in the literature, but only
|
||
SRP-6a [28] has been widely implemented in practice, e.g., in iCloud, 1Password
|
||
and ProtonMail [14]. (It is the latest version of SRP-3, following a series of revi-
|
||
sions to patch weaknesses in the 1998 Secure Remote Password 3 protocol [30].)
|
||
Security concerns [20] have been raised related to its heuristic design. The pro-
|
||
tocol also requires working over the whole range of a multiplicative group Z∗p
|
||
(where p is a safe prime, i.e., p = 2q + 1 with q also prime). This makes modular
|
||
exponentiation relatively expensive—e.g., given a 3072-bit p, the exponent for
|
||
modular exponentiation is 3072 bits, and one exponentiation is 3072/256 = 12
|
||
times as costly as an exponentiation in 3072-bit DSA with 256-bit exponents.
|
||
Finally, SRP-6a does not support elliptic curve implementations.
|
||
OPAQUE is an augmented PAKE scheme proposed by Jarecki et al. in
|
||
2018 [20] and was selected by IETF for standardization in 2020. An advan-
|
||
tage promoted in its favor is so-called pre-computation security: if a server is
|
||
compromised, an attacker cannot use pre-computed tables to speed up offline
|
||
search. In contrast, for some augmented schemes, a single pre-computed table
|
||
can be used thereafter to efficiently recover many passwords. Compared to SRP-
|
||
6a, however, the advantage is less: if a server is compromised, while it is possible
|
||
for an attacker to speed up password guessing using a pre-computed table, a
|
||
unique table must be pre-computed per user (because of SRP-6a’s salt), signif-
|
||
icantly increasing attack costs in terms of memory used and pre-computation
|
||
time. OPAQUE also has formal security proofs (SRP-6a does not), and seems
|
||
to be much more efficient than others (for caveats, see §4).
|
||
However, OPAQUE has three limitations. First, it relies on a constant-time
|
||
hash-to-curve (H2C) function, which is non-trivial to implement [5]. Second,
|
||
the critical reliance on H2C renders the protocol unspecified in multiplicative
|
||
groups in the original paper. When OPAQUE is instantiated in such a group,
|
||
its performance advantages diminish (see §4). Third, in every login session of
|
||
OPAQUE, the server sends a pre-computed ciphertext using authenticated en-
|
||
cryption and a password-derived encryption key. When the password is changed,
|
||
the pre-computed ciphertext will change, hence revealing whether the password
|
||
has been changed from the last login [12]. Assume the credentials have been
|
||
stolen from a server. If a user diligently changes their password, their account
|
||
can remain safe. However, in OPAQUE, a passive attacker can monitor the login
|
||
sessions to identify users who have not changed the password and then prioritize
|
||
the brute-force attack against those. This attack does not apply to SRP-6a.
|
||
These above issues point to the need for an augmented PAKE scheme that
|
||
is efficient across both multiplicative and elliptic curve settings, is supported
|
||
by security proofs, and does not reveal information about password changes.
|
||
We address this therein through an approach distinct from previous augmented
|
||
PAKE designs. We efficiently adapt the symmetric J-PAKE scheme [13] to an
|
||
asymmetric setting, yielding a new scheme: Owl.1 Compared with J-PAKE, Owl
|
||
provides additional security against server compromise with even lower compu-
|
||
1
|
||
Owls have asymmetric ears with one higher than the other. This asymmetry helps
|
||
owls pinpoint the source of a sound in darkness.
|
||
|
||
|
||
2
|
||
tation overall. We show that Owl is secure based on the Computational Diffie-
|
||
Hellman (CDH) and Decision Diffie-Hellman (DDH) assumptions in the random
|
||
oracle model (§3). We evaluate the performance of Owl and show that Owl has
|
||
systematic advantages over SRP-6a in terms of security, computation, message
|
||
sizes, and cryptographic agility in implementations (§4).
|
||
|
||
|
||
2 Protocol specification of Owl
|
||
Here we provide a specification of the Owl protocol. To ease comparison, we
|
||
reuse J-PAKE notation where possible, including x1 , x2 , x3 and x4 for J-PAKE’s
|
||
four ephemeral private keys. We modify J-PAKE by fixing x3 per user (thus
|
||
leveraging the server storage available in the asymmetric setting) and further-
|
||
more combine the modified J-PAKE with a compiler due to Hwang et al. [16],
|
||
achieving augmented security in an asymmetric setting. (By design a compiler
|
||
always adds cost for converting a balanced PAKE, but our method saves cost.)
|
||
|
||
2.1 Setup
|
||
We describe the protocol in a DSA-like group G (the specification works the
|
||
same in an elliptic curve setting). Let p and q be two large primes such that
|
||
q | p − 1. The protocol operates in the subgroup of Z∗p of prime order q. Any
|
||
non-identity element in this subgroup can serve as a generator, denoted g. Un-
|
||
less specified otherwise, all modular operations are performed with reference
|
||
to the modulus p. Let t be a (low-entropy) user-specific secret, obtained by
|
||
t = H(username∥password) mod q, were H is a secure one-way function and ∥
|
||
denotes concatenation. We define π = H(t) mod q as a shared secret to be used
|
||
for authenticated key exchange and T = g t mod p as a password verifier to be
|
||
stored on the server. As in J-PAKE, we require π ̸= 0 mod q. As summarized
|
||
in Fig. 1, the protocol comprises two main phases: initial registration and login
|
||
(authenticated key exchange); for completeness, we also cover password update.
|
||
|
||
2.2 Initial registration
|
||
To register an account on a server, a user computes t = H(U ∥w) mod q. Here
|
||
U denotes her username; w her (weak) password. She then computes π =
|
||
H(t) mod q, T = g t mod p, and sends (U, π, T ) to the server through a secure
|
||
channel (e.g., over TLS or out-of-band). The server chooses a random secret
|
||
x3 ∈R [1, q − 1], and computes a public key X3 = g x3 mod p together with a
|
||
zero-knowledge proof Π3 = ZKP{x3 : g, X3 } to prove the knowledge of the ex-
|
||
ponent x3 . When the context is clear, we shorten the notation to ZKP{x3 }. A
|
||
concrete instantiation based on Schnorr [26] is given in Appendix A. The server
|
||
stores {U : X3 , Π3 , π, T } as the password verification file for U , and deletes x3 .
|
||
We will use π as a shared secret to run a modified J-PAKE protocol by
|
||
using the pre-computed X3 and Π3 values instead of freshly generating them for
|
||
each login session as in the original J-PAKE protocol. This modification does not
|
||
|
||
3
|
||
Init registration
|
||
User (U, w) Server (S)
|
||
t = H(U ∥w) mod q x3 ∈R [0, q − 1], X3 = g x3
|
||
π = H(t) mod q Π3 = ZKP{x3 }
|
||
T = g t mod p U, π, T Stores {U : X3 , Π3 , π, T }
|
||
−−−−−−−−−→
|
||
(Secure channel)
|
||
Login
|
||
User (U, w) Server (S, {U : X3 , Π3 , π, T })
|
||
t = H(U ∥w) mod q
|
||
π = H(t) mod q
|
||
x1 ∈R [0, q − 1], X1 = g x1
|
||
Π1 = ZKP{x1 }
|
||
x2 ∈R [1, q − 1], X2 = g x2
|
||
Π2 = ZKP{x2 } U, X1 , X2 , Π1 , Π2 Verify Π1 , Π2 , X2 ̸= 1
|
||
−−−−−−−−−−−−−−−→
|
||
x4 ∈R [1, q − 1], X4 = g x4
|
||
Π4 = ZKP{x4 }
|
||
β = (X1 X2 X3 )x4 ·π
|
||
Verify Π3 , Π4 , Πβ , X4 ̸= 1 S, X3 , X4 , Π3 , Π4 , β, Πβ Πβ = ZKP{x4 · π}
|
||
←−−−−−−−−−−−−−−−−−−−
|
||
α = (X1 X3 X4 )x2 ·π
|
||
Πα = ZKP{x2 · π}
|
||
K = (β/X4x2 ·π )x2
|
||
h = H(K∥Transcript)
|
||
r = x1 − t · h mod q α, Πα , r Verify Πα
|
||
−−−−−−−−−→
|
||
K = (α/X2x4 ·π )x4
|
||
h = H(K∥Transcript)
|
||
Verify g r · T h = X1
|
||
k = H(K) k = H(K)
|
||
Password update
|
||
User (U, w, w′ ) Server (S, {U : X3 , Π3 , π, T })
|
||
t = H(U ∥w′ ) mod q
|
||
′
|
||
|
||
π ′ = H(t′ ) mod q
|
||
′
|
||
T ′ = g t mod p π′ , T ′ Replaces (π, T ) with (π ′ , T ′ )
|
||
−−−−−−−−−→
|
||
(Secure PAKE channel)
|
||
|
||
Fig. 1. The Owl protocol. U is the user’s identity, w her (weak) password.
|
||
|
||
|
||
|
||
|
||
affect the security of the session key, as we will show in §3. We define π as a secret
|
||
salted by a unique username. This is to ensure that upon server compromise if
|
||
an attacker wishes to use a pre-computed table to launch an offline dictionary
|
||
attack, he needs to build a unique pre-computed table for each user. In addition
|
||
to modifying J-PAKE, we adopt a method proposed by Hwang et al. to enable
|
||
a client to securely prove the knowledge of t for T = g t based on a variant of
|
||
Schnorr non-interactive ZKP [16] with details below.
|
||
|
||
|
||
4
|
||
2.3 Login
|
||
The protocol runs between a client user (with unique identity U ) and server (with
|
||
identity S). The user initiates the communication. Both sides check: U ̸= S.
|
||
There are three flows in the login process to perform authenticated key ex-
|
||
change as presented in Figure 1. The first two flows are the same as in J-
|
||
PAKE except that X3 is fixed per user. In the third flow, the computation
|
||
of r is based on a compiler proposed by Hwang et al. [16] to prove the knowl-
|
||
edge of t for g t in an asymmetric PAKE setting; here, we use X1 as a commit-
|
||
ment (which is included in Transcript). Our definition of Transcript herein
|
||
is a record of the items exchanged between U and S for computing a common
|
||
session key. Transcript = U ∥X1 ∥X2 ∥Π1 ∥Π2 ∥S∥X3 ∥X4 ∥Π3 ∥Π4 ∥β∥Πβ ∥α∥Πα .
|
||
If U and S have used the same passwords, they will derive a common ses-
|
||
sion key (for simplicity, using a one-way hash H as a key derivation function):
|
||
k = H(K) = H(g (x1 +x3 )·x2 ·x4 ·π ). Optionally, they can perform explicit key con-
|
||
firmation by using standard methods (e.g., NIST SP 800-56A).
|
||
|
||
2.4 Password update
|
||
After the successful authenticated key exchange process, both parties use the
|
||
session key k to create a secure channel. Through this secure channel, the user
|
||
can update the password by sending π ′ , T ′ to the server as shown in Fig. 1.
|
||
The server updates the password verifier file for U accordingly. One reason for a
|
||
user to update her password is suspicion that the old password was compromised.
|
||
Owl’s forward secrecy property (§3.2) ensures that a passive attacker who knows
|
||
the old password cannot learn the session key k, and hence cannot learn the new
|
||
password. Although OPAQUE and SRP-6a do not discuss this explicitly, they
|
||
can use a similar method to update the password.
|
||
|
||
|
||
3 Security analysis
|
||
Hwang et al. [16] proposed a compiler to convert a symmetric PAKE to an
|
||
asymmetric one based on a variant of Schnorr non-interactive ZKP and proved
|
||
its security in a universally composable (UC) model. We adopt the method of
|
||
Hwang et al. as part of our protocol (more specifically, proving the knowledge
|
||
of t for T = g t ; see Fig. 1). As Hwang et al.’s compiler has been proven secure
|
||
in the UC model on the assumption that the session key from the symmetric
|
||
PAKE is secure, we focus on proving the security of the session key derived from
|
||
the modified J-PAKE.
|
||
|
||
3.1 Security assumption
|
||
The security proof of Owl is based on the intractability of Multiple Decision
|
||
Diffe-Hellman (MDDH) [23] and Square Computational Diffie-Hellman (SCDH)
|
||
assumptions. We show that DDH and MDDH assumptions are equivalent. The
|
||
SCDH and CDH assumptions are also equivalent, as shown by Bao et al. [1].
|
||
|
||
|
||
5
|
||
DDH
|
||
Assumption 1 (DDH): For any PPT adversary A, AdvA (λ) ≤ negl(λ),
|
||
where,
|
||
|
||
DDH $ $
|
||
AdvA − Zq ]−P r[A(g, g a , g b , g c ) a, b, c ←
|
||
(λ) = P r[A(g, g a , g b , g ab ) = 1 a, b ← − Zq ]
|
||
|
||
Assumption 2 (MDDH): For n ∈ poly(λ), any PPT adversary A, the fol-
|
||
lowing two distributions are computationally indistinguishable.
|
||
|
||
$
|
||
R0 = (g, g a , g bi , g abi ) : i ∈ [1, n] a, b1 , b2 , . . . , bn ←
|
||
− Zq
|
||
|
||
$
|
||
R1 = (g, g a , g bi , g ci ) : i ∈ [1, n] a, b1 , b2 , . . . , bn , c1 , c2 , . . . , cn ←
|
||
− Zq
|
||
|
||
We define the advantage of A in distinguishing between R0 and R1 as,
|
||
|
||
M DDH
|
||
AdvA (λ) = P r[A(R0 ) = 1] − P r[A(R1 ) = 1]
|
||
|
||
M DDH
|
||
Hence, AdvA (λ) ≤ negl(λ), for a PPT adversary A.
|
||
|
||
Lemma 1. Assumption 1 and Assumption 2 are equivalent.
|
||
|
||
Proof. (⇒): If there is an adversary A against Assumption 2, we could use it
|
||
to construct another adversary B against Assumption 1. This has been proved
|
||
in Lemma 4 by Kurosawa and Nojima [23]. (⇐): Let us assume that we have
|
||
an adversary B, against the DDH assumption. We use it to construct another
|
||
adversary A, against Assumption 2. A receives as input g, g a , and bi , Ωdi ∈
|
||
$
|
||
{g a·bi , Ri }, for i ∈ [1, n], where Ri ←
|
||
− G. It then invokes B with g, g a , g bk , and
|
||
Ωdk for some k ∈ [1, n]. B has to check if Ωdk = g a·bk or a random element in G.
|
||
If B is successful, so will be A. Hence, the result holds.
|
||
|
||
$ $
|
||
Assumption 3 (CDH): Given x, y ← − G, define CDHg (g x , g y ) =
|
||
− Zq , and g ←
|
||
g . Consider the following security experiment ExpCDH
|
||
xy
|
||
A (λ). In this experiment,
|
||
the challenger randomly chooses three elements g, X = g x , Y = g y from G.
|
||
Then the adversary A is invoked with these three as inputs. A has to com-
|
||
pute CDHg (X, Y ) from these parameters. The experiment is successful if A
|
||
can compute CDHg (X, Y ) correctly. The advantage of an adversary A, against
|
||
|
||
|
||
ExpCDH
|
||
A (λ)
|
||
$
|
||
g←
|
||
−G
|
||
$
|
||
X←
|
||
−G
|
||
$
|
||
Y ←
|
||
−G
|
||
C ← A(g, X, Y )
|
||
?
|
||
Return C = CDHg (X, Y )
|
||
|
||
|
||
6
|
||
ExpCDH
|
||
A (λ) is given by
|
||
CDH
|
||
AdvA (λ) = P r[ExpCDH
|
||
A (λ) = 1]
|
||
CDH
|
||
As such, for any PPT adversary A AdvA (λ) ≤ negl(λ).
|
||
|
||
$ $
|
||
Assumption 4 (SCDH): Given x ← − G, define SCDHg (g x ) =
|
||
− Zq , and g ←
|
||
x2
|
||
g . Consider the following security experiment ExpSCDH
|
||
A (λ). In this experi-
|
||
ment, the challenger randomly chooses two elements g and X = g x from G.
|
||
Then the adversary A is invoked with these two as inputs. A has to compute
|
||
SCDHg (X) from these parameters. The experiment is successful if A can com-
|
||
pute SCDHg (X) correctly. The advantage of an adversary A, against ExpSCDH
|
||
A (λ)
|
||
|
||
|
||
ExpSCDH
|
||
A (λ)
|
||
$
|
||
g←
|
||
−G
|
||
$
|
||
X←−G
|
||
C ← A(g, X)
|
||
?
|
||
Return C = SCDHg (X)
|
||
|
||
|
||
|
||
is given by
|
||
SCDH
|
||
AdvA (λ) = P r[ExpSCDH
|
||
A (λ) = 1].
|
||
SCDH
|
||
As such, for any PPT adversary A AdvA (λ) ≤ negl(λ).
|
||
|
||
Lemma 2. Assumption 3 and Assumption 4 are equivalent [1].
|
||
|
||
3.2 Session key indistinguishability
|
||
|
||
Impersonating the server First, we consider an active adversary impersonat-
|
||
ing the server without having the password verification file. We define a security
|
||
experiment ExpRN A
|
||
DKey
|
||
(λ) to model the adversary impersonating the server.We
|
||
introduce a simulator SIM to interact with an adversary A. In this experiment,
|
||
SIM can replace the session key with the hash of a random element of G, and
|
||
it will not be possible for A to distinguish if the key it has received was the ac-
|
||
tual key or a randomly chosen key when the adversary had chosen an incorrect
|
||
password. If the passwords used by the two parties do not match, both sides end
|
||
up calculating different keys. In this attack scenario, the simulator responds to
|
||
the queries of the attacker impersonating the server to a legitimate client with-
|
||
out knowing the password verification file. The simulator follows the protocol
|
||
specifications and sends appropriate information to the attacker against all its
|
||
queries. In the end, the simulator calculates the session key. The simulator then
|
||
flips a coin and returns either the actual session key or a random one depending
|
||
upon the outcome of the coin tossing. We show that the attacker will not be able
|
||
to distinguish between the two keys if the password chosen by the attacker w′ is
|
||
|
||
|
||
7
|
||
not the one (w) used by the simulator. So, if the session key is compromised, the
|
||
attacker will learn nothing about the actual password used by the simulator.
|
||
In the security experiment ExpRN A
|
||
DKey
|
||
(λ), we define g as a random genera-
|
||
tor of the mathematical group G. D is a dictionary of passwords. |D| ∈ poly(λ).
|
||
H is a secure hash function (modelled as FRO ). The adversary A = (A0 , A1 , A2 )
|
||
is a three stage adversary. Here, CDHg (A, B) denotes the Computational Diffie-
|
||
Hellman of two elements A, and B with respect to g. Also SCDHg (A) denotes
|
||
the square Computational Diffie-Hellman of an element A with respect to g.
|
||
First, the challenger generates the public parameters. Then she chooses a gener-
|
||
$
|
||
ator g from G, and a password w from D. The challenger chooses X1 , X2 ← − G,
|
||
and invokes A0 with the specific parameters as shown in the experiment. A0 out-
|
||
puts x2 , x4 ∈ Z∗q . Then the challenger computes R, and invokes A1 . A1 outputs
|
||
a password guess w′ ∈ D and obtains π ′ = H(H(U ∥w′ )). Then the challenger
|
||
calculates a raw key K0 , and randomly samples K1 from G. The challenger
|
||
randomly chooses one of K0 and K1 , and invokes A2 with its hash value. A2
|
||
has to identify whether H(K0 ) or H(K1 ) was passed to her as the input. The
|
||
experiment is successful if A2 can identify the correct challenge.
|
||
Note that if w = w′ (or π = π ′ ), K0 will be equal to CDHg (X1 , X2 )x4 π ∗
|
||
X2x3 x4 π . As such, A2 can distinguish between H(K0 ) and H(K1 ) easily. So,
|
||
we define the advantage of A as P r[ExpRN A
|
||
DKey
|
||
(λ) = 1|π ̸= π ′ ] − 21 . Now,
|
||
RN DKey RN DKey
|
||
P r[ExpA (λ) = 1] = P r[ExpA (λ) = 1|π = π ′ ] ∗ P r[π = π ′ ] +
|
||
RN DKey
|
||
P r[ExpA (λ) = 1|π ̸= π ′ ] ∗ P r[π ̸= π ′ ]. If π = π ′ , A2 can easily win the ex-
|
||
periment. Therefore, P r[ExpRN A
|
||
DKey
|
||
(λ) = 1|π = π ′ ] = 1. So, P r[ExpRN A
|
||
DKey
|
||
(λ) =
|
||
RN DKey
|
||
1] = P r[ExpA (λ) = 1|π ̸= π ] ∗ (1 − P r[π = π ]) + P r[π = π ′ ] =
|
||
′ ′
|
||
|
||
P r[ExpRN A
|
||
DKey
|
||
(λ) = 1|π ̸= π ′ ](1 − |D|1
|
||
) + |D|1
|
||
. Now, A2 can always win with 21
|
||
probability by making a random guess. Therefore, P r[ExpRN A
|
||
DKey
|
||
(λ) = 1|π ̸=
|
||
π ′ ] ≥ 12 . Let us assume that P r[ExpRN
|
||
A
|
||
DKey
|
||
(λ) = 1|π ̸
|
||
= π ′
|
||
] = 1
|
||
2 +X, where X is
|
||
RN DKey RN DKey
|
||
used to define the advantage of A against ExpA (λ). So, P r[ExpA (λ) =
|
||
|D|
|
||
1] = (X + 12 )(1 − |D| 1 1
|
||
) + |D| . Therefore, X = |D|−1 ∗ (P r[ExpRNA
|
||
DKey
|
||
(λ) =
|
||
|D|
|
||
1
|
||
1] − |D| ) − 12 = |D|−1 ∗ (P r[ExpRN
|
||
A
|
||
DKey 1
|
||
(λ) = 1] − 2|D| − 21 ). Since, |D| is poly(λ),
|
||
|D| |D|
|
||
|D|−1 is a little higher than 1. So, we can eliminate the |D|−1 part in the above
|
||
expression. Therefore, we define the advantage of an adversary A against the
|
||
security experiment ExpRN
|
||
A
|
||
DKey
|
||
(λ) as below:
|
||
RN DKey 1 1
|
||
AdvA (λ) = P r[ExpRN
|
||
A
|
||
DKey
|
||
(λ) = 1] − −
|
||
2|D| 2
|
||
|
||
Theorem 1. Under the SCDH and DDH assumptions with access to FRO , for
|
||
RN DKey
|
||
any PPT adversary A = (A0 , A1 , A2 ), AdvA (λ) ≤ negl(λ).
|
||
Proof. We show that if there exists an adversary A against the security experi-
|
||
RN DKey
|
||
ment AdvA , we can use it to construct another adversary B, against the
|
||
$
|
||
security experiment ExpSCDH
|
||
A (λ). B receives as input A ←
|
||
− G. Its aim is to com-
|
||
$
|
||
− Zq , and assigns X1 = g x1 , and X2 = A.
|
||
pute SCDHg (A). It selects random x1 ←
|
||
|
||
|
||
8
|
||
ExpRN
|
||
A
|
||
DKey
|
||
(λ)
|
||
(G, D, H) ← Setup(1λ )
|
||
$
|
||
g←
|
||
−G
|
||
w←
|
||
− D, π = H(H(U ∥w))
|
||
$
|
||
X1 , X2 ← −G
|
||
(x3 , x4 , state0 ) ← A0 (g, G, D, X1 , X2 )
|
||
R ← (CDHg (X1 , X2 ) ∗ X2x3 +x4 )π
|
||
(w′ , state1 ) ← A1 (state0 , R)
|
||
π ′ = H(H(U ∥w′ ))
|
||
′ ′ ′
|
||
K0 ← CDHg (X1 , X2 )x4 ·π ∗ X2x3 ·x4 ·π ∗ SCDHg (X2 )x4 ·(π −π)
|
||
$
|
||
K1 ←
|
||
−G
|
||
$
|
||
d← − {0, 1}
|
||
Ω ← H(Kd )
|
||
d′ ← A2 (state1 , Ω)
|
||
?
|
||
Return (d = d′ )
|
||
|
||
|
||
(x +x +x )π
|
||
It invokes A0 and receives x3 , and x4 . Then B computes R = X2 1 3 4 .
|
||
B invokes A1 and receives w′ , thus π ′ = H(H(U ∥w′ )). If π ′ = π, B aborts
|
||
and outputs a random element from G. Else, B samples a random string from
|
||
{0, 1}λ , and assigns this to Ω. When A0 , A1 or A2 makes an oracle query to
|
||
H, B answers them. For each such query, B samples a random string and re-
|
||
turns it. If a query is repeated, B returns the same string it had returned
|
||
earlier. B keeps a log of all query-response pairs. After A2 has returned, B
|
||
A1 or A2 . It ′randomly
|
||
checks all the queries made by x2selects one query-response
|
||
′
|
||
x4 ·π x4 ·π
|
||
pair ⟨K0 , k0 ⟩ where K0 = (X1 X2 X3 ) /X2 = CDHg (X1 , X2 )x4 ·π ∗
|
||
′ ′
|
||
X2x3 ·x4 ·π ∗ SCDHg (X2 )x4 ·(π −π) represents the raw keying material computed
|
||
′
|
||
by A and k0 the session key. B computes C = (K0 /(CDHg (X1 , X2 )x4 π ∗
|
||
′ ′
|
||
X2x3 ∗x4 π ))1/(x4 (π −π)) = SCDHg (X2 ) and outputs C. Let us now calculate the
|
||
success probability of B. B wins if the following events happen together:
|
||
– π ̸= π ′
|
||
– A queries H(K0 ).
|
||
Since H is modelled as a random oracle FRO , A2 cannot identify d without
|
||
querying H(K0 ). Thus, the probability that A queries H(K0 ) is at least equal to
|
||
P r[ExpRN A
|
||
DKey
|
||
(λ) = 1] − 12 . Now, the probability that H(K0 ) will be queried
|
||
and K0 will have the term SCDHg (X2 ) as a factor is P r[ExpRN A
|
||
DKey
|
||
(λ) =
|
||
′
|
||
P r[π=π ] 1 ′
|
||
1] − 2 − 2 . First, we calculate the value of P r[π = π ]. If A can guess
|
||
the value of π from R, then the probability of this event happening could be
|
||
as high as 1. However, the probability that A can guess the value of π from
|
||
DDH
|
||
R is bounded by AdvA (λ) (i.e., distinguishing CDHg (X1 , X2 ) from ran-
|
||
dom). Thus, P r[π = π ′ ] ≤ |D| 1
|
||
+ AdvA DDH
|
||
(λ). Hence, the probability that A
|
||
will query K0 is at least P r[ExpRN
|
||
A
|
||
DKey 1
|
||
(λ) = 1] − 2|D| − 12 AdvA
|
||
DDH
|
||
(λ) − 12 .
|
||
Now, B randomly picks a query and computes SCDHg (A) on the basis of
|
||
|
||
|
||
9
|
||
that. So if there are Q queries to H, the probability that B will pick the cor-
|
||
rect one is 1/Q. Thus, AdvBSCDH (λ) ≥ (1/Q) ∗ (P r[ExpRN A
|
||
DKey
|
||
(λ) = 1] −
|
||
1 1 DDH 1 RN DKey 1 DDH
|
||
2|D| − 2 Adv A (λ) − 2 ) = (1/Q)(Adv A (λ) − 2 Adv A (λ)). Hence,
|
||
RN DKey
|
||
AdvA (λ) ≤ Q ∗ AdvBSCDH (λ) + 12 ∗ AdvA
|
||
DDH
|
||
(λ).
|
||
|
||
Impersonating the client Next, we consider an active adversary impersonat-
|
||
ing the client without knowing the password. We consider a security experiment
|
||
ExpRNA
|
||
DKey1
|
||
(λ), which emulates the event when the attacker tries to imper-
|
||
sonate the user to a legitimate server without knowing the password. In this
|
||
experiment, we introduce an oracle O that can be queried by the adversary.
|
||
This oracle models the event that the adversary can exploit the fact the server
|
||
uses the same value of X3 across all the executions of the protocol. So, the adver-
|
||
sary can try to impersonate the client and execute the protocol with the server
|
||
multiple times and can receive the second-flow messages from the server for dif-
|
||
ferent values of X4 , but a single value of X3 . In the end, the goal of the adversary
|
||
is to distinguish between the session key computed by an honest instance and
|
||
a random string. Similar to the case of ExpRN A
|
||
DKey
|
||
(λ), the advantage of the
|
||
adversary A, against the security experiment ExpRN A
|
||
DKey1
|
||
(λ) (which models
|
||
an attacker impersonating the user) is defined as
|
||
|
||
RN DKey1 1 1
|
||
AdvA (λ) = P r[ExpRN
|
||
A
|
||
DKey1
|
||
(λ) = 1] − −
|
||
2|D| 2
|
||
|
||
ExpRN
|
||
A
|
||
DKey1
|
||
(λ)
|
||
(G, D, H) ← Setup(1λ )
|
||
$
|
||
g←
|
||
−G
|
||
w←
|
||
− D, π = H(H(U ∥w))
|
||
$
|
||
X3 , X4 ←
|
||
−G
|
||
$
|
||
d← − {0, 1} O()
|
||
(x1 , x2 ) ← AO (g, G, D, X3 , X4 ) $
|
||
X← −G
|
||
R ← − (CDHg (X3 , X4 ) ∗
|
||
(x1 , x2 ) ← A(X)
|
||
X4 x1 +x2 )π
|
||
R← − (CDHg (X3 , X) ∗ X x1 +x2 )π
|
||
w′ ← A(R)
|
||
Return R
|
||
π ′ = H(H(U ||w′ ))
|
||
′
|
||
B0 ← CDHg (X3 , X4 )x2 ·π ∗
|
||
′ ′
|
||
X4x1 ·x2 ·π ∗ SCDHg (X4 )x2 (π −π)
|
||
$
|
||
B1 ←−G
|
||
d′ ← A(H(Bd ))
|
||
?
|
||
return d = d′
|
||
Theorem 2. Under the SCDH and MDDH assumptions with access to FRO ,
|
||
RN DKey1
|
||
for any PPT adversary A, AdvA (λ) ≤ negl(λ).
|
||
Proof. We can show that if there exists an adversary A against the security ex-
|
||
periment ExpRN
|
||
A
|
||
DKey1
|
||
(λ), we can use it in the construction of another adversary
|
||
|
||
|
||
10
|
||
B again the experiment ExpSCDH
|
||
A (λ). The proof is almost the same as the proof
|
||
of Theorem 1. The only difference is that because of the use of a fixed X3 value
|
||
across the sessions, we use Assumption 2 instead of Assumption 1. All other argu-
|
||
ments are the same. Thus, we substitute the DDH assumption of Theorem 1 with
|
||
RN DKey1
|
||
Assumption 2, and have AdvA (λ) ≤ Q∗AdvA M DDH
|
||
(λ)+ 12 ∗AdvA
|
||
SCDH
|
||
(λ).
|
||
Hence, the result follows.
|
||
|
||
|
||
Session key exposure The following experiment ExpKeyExp A (λ) models the
|
||
event where the attacker gets hold of an actual session key after the key is
|
||
derived. We will show that the actual session key is indistinguishable from a
|
||
random key in the view of the attacker even with the knowledge of the password
|
||
KeyExp
|
||
(i.e., forward secrecy [13]). This can happen if AdvA (λ) is negligible, where
|
||
|
||
KeyExp 1
|
||
AdvA (λ) = P r[ExpKeyExp
|
||
A (λ) = 1] − .
|
||
2
|
||
|
||
|
||
|
||
ExpKeyExp
|
||
A (λ)
|
||
(G, D, H) ← Setup(1λ )
|
||
$
|
||
g←
|
||
−G
|
||
$
|
||
X4 ← −G
|
||
(π, state) ← A0 (G, D, H, g, X4 )
|
||
$
|
||
X1 , X2 , X3 ←
|
||
−G
|
||
α ← CDHg (X1 ∗ X3 ∗ X4 , X2 )π
|
||
β ← CDHg (X1 ∗ X2 ∗ X3 , X4 )π
|
||
K0 ← H(CDHg (X1 ∗ X3 , X2 )π·logg X4 )
|
||
$
|
||
− {0, 1}∗
|
||
K1 ←
|
||
$
|
||
d← − {0, 1}
|
||
d′ ← A∞ (state, X1 , X2 , X3 , α, β, Cd )
|
||
?
|
||
return d = d′
|
||
|
||
|
||
Theorem 3. Under the DDH and SCDH assumptions with access to FRO , for
|
||
KeyExp
|
||
any PPT adversary A, AdvA (λ) ≤ negl(λ).
|
||
|
||
Proof. We show that if there exists an adversary A against the experiment
|
||
ExpKeyExp
|
||
A (λ), it could be used in the construction of another adversary B
|
||
against the security experiment ExpSCDH
|
||
B (λ). The adversary B works as fol-
|
||
$
|
||
lows: it receives as input an X4 ←
|
||
− G, and it needs to compute SCDHg (X4 ).
|
||
$ $
|
||
The adversary B proceeds as follows: It selects x1 ← − Zq , x2 , a ← − Z∗q and
|
||
x1 x2 a
|
||
sets X1 = g , X2 = g , and X3 = X4 ∗ g . That is, B implicitly sets
|
||
x3 = logg X3 = a + logg X4 . Let A = (A0 , A1 ) be a two-stage adversary. When
|
||
A0 is invoked with the corresponding parameters, it outputs the password π
|
||
from the dictionary D. B can compute α = (g x1 x2 ∗ X42x2 ∗ g x2 a )π . B samples
|
||
|
||
|
||
11
|
||
$
|
||
random β ← − G. Now, B samples a string {0, 1}∗ , and assigns this to Cd . A1
|
||
is then invoked with all the necessary parameters. If A0 can identify d, it will
|
||
have to query CDHg (X1 ∗ X3 , X2 )π·logg X4 . B checks all the queries made by A1 .
|
||
From all the queries made by A1 , B randomly picks one query ∆, and outputs
|
||
1/x2 π
|
||
SCDHg (X4 ) = (∆(x1 +a)) . Now, we calculate the advantage of the adversary B.
|
||
X4
|
||
Note that in this experiment we replace β with a random element from G. Ac-
|
||
cording to the DDH assumption, CDHg (X1 ∗ X2 ∗ X3 , X4 ) is indistinguishable
|
||
from random. Therefore, replacing it with a random element will reduce the ad-
|
||
DDH
|
||
vantage of A by a factor of AdvA (λ). Let us assume that A1 makes Q queries
|
||
to H. B selects one query made by A1 to H, and calculates SCDHg (X4 ) on the
|
||
KeyExp
|
||
basis of this. Thus, AdvBSCDH (λ) ≥ 1/Q ∗ (AdvA (λ) − AdvADDH
|
||
(λ)). That
|
||
KeyExp DDH SCDH
|
||
is, AdvA (λ) ≤ AdvA (λ) + Q ∗ AdvB (λ). Hence, the result holds.
|
||
|
||
|
||
4 Related work and comparison
|
||
|
||
Many augmented PAKE schemes have been proposed in the past three decades.
|
||
Hao and van Oorschot [14] categorize PAKE schemes according to whether they
|
||
require an ideal cipher, a hash-to-group function, or a trusted setup (see Fig. 2).
|
||
KHAPE [9],OKAPE [6] and aEKE [4] are examples that rely on an ideal cipher,
|
||
an abstract building block that is assumed to not leak any information about the
|
||
encryption content even when the encryption key has low entropy (e.g., using
|
||
a password as the key) [2]. However, how to instantiate such an ideal cipher
|
||
has remained an open problem [14]. VTBPEKE [25], KC-SPAKE2+ [27] and
|
||
Bradley et al.’s scheme [5] rely on a trusted setup but a compromise in this setup
|
||
will break key exchange sessions for all users [25]. PAK-Z+ [8], AuCPace [10]
|
||
and OPAQUE [20] rely on a hash-to-group (also called hash-to-curve in an EC
|
||
setting) function, which is assumed to map a password to a random generator of
|
||
a designated group in constant time 2 . However, instantiating this function is not
|
||
easy as we will explain later. SRP-6a does not depend on an ideal cipher, a hash-
|
||
to-group function or a trusted setup, which has contributed to its wide adoption
|
||
in real-world applications [14]. AMP and AugPAKE follow a similar design as
|
||
SRP with the aim of better efficiency. AMP has been repeatedly revised to patch
|
||
vulnerabilities [24]. AugPAKE has not been published in a peer-reviewed paper
|
||
(it is described in an IETF RFC), and its security proof is questioned [20].
|
||
In this section, we focus on comparing Owl with SRP-6a and OPAQUE. We
|
||
chose SRP-6a because it is the only augmented PAKE that has been widely
|
||
used in practice. Although many provably secure augmented PAKE schemes
|
||
have been proposed (see Figure 2), they generally rely on assumptions of an
|
||
ideal cipher, a trusted setup or a hash-to-group function; however, difficulties
|
||
in the realization of such assumptions have hindered the deployment of these
|
||
schemes [14]. We chose OPAQUE because it was selected by the IETF as a
|
||
candidate for standardization and a possible replacement for SRP-6a.
|
||
2
|
||
A non-constant-time mapping could leak the password through timing attacks [29].
|
||
|
||
|
||
12
|
||
[4, 6, 9] [5, 25, 27] [8, 10, 20]
|
||
|
||
|
||
Yes Yes Yes
|
||
|
||
|
||
No No No SRP-6a,
|
||
A-PAKE IC? TS? H2G?
|
||
Owl
|
||
|
||
|
||
|
||
Fig. 2. Overview of selected Augmented PAKE (A-PAKE) schemes and dependence on
|
||
various assumptions. IC: Ideal Cipher. TS: Trusted Setup. H2G: Hash-to-Group (also
|
||
called Hash-to-Curve in an EC setting). SRP-6a and Owl do not require any ideal
|
||
cipher, trusted setup or hash-to-group functions.
|
||
|
||
Hash-to-group/hash-to-curve. In the original OPAQUE paper [20], the
|
||
authors specify the protocol only in an EC setting, not in any multiplicative
|
||
group (MODP). The rationale was however not explained. To provide insights
|
||
into this design choice, we first need to clarify the hash-to-group (H2G) and
|
||
hash-to-curve (H2C) functions. OPAQUE relies on H2C to map a password to a
|
||
random prime-order generator on an elliptic curve in constant time. H2G is the
|
||
equivalent function in a MODP group. The original idea of using H2G in PAKE
|
||
is from Jablon’s 1996 design of SPEKE [18]. More concretely, SPEKE defines a
|
||
safe prime p = 2q + 1 as the modulus, i.e., q is also prime. The H2G function
|
||
with input a is defined as f (a) = a2 mod p, which forms the basis of SPEKE
|
||
as standardized in IEEE 1363.2 [17]. However, using a safe prime as modulus
|
||
makes modular exponentiations costly. Extending this construction to a DSA
|
||
group (which uses short exponents) and EC proves harder than it seems.
|
||
– DSA. For a DSA group (p, q, g), IEEE 1363.2 defines the H2G function with
|
||
input a as: f (a) = a(p−1)/q [17]. This function has two known issues: 1) it is
|
||
costly due to the long exponent; 2) it may return an identity element (called
|
||
an ‘invalid’ output). IEEE 1363.2 does not define any handling for ‘invalid’
|
||
outputs; handling such exceptions can forfeit the constant-time property.
|
||
– EC. To do the equivalent of H2G in EC, IEEE 1363.2 defined an H2C func-
|
||
tion based on a trial-and-increment method. The IEEE function guarantees
|
||
the output is a prime-order generator (no ‘invalid’ output) and works with
|
||
general curves, but is vulnerable to timing attacks [29]. IEEE 1363.2 was
|
||
officially withdrawn in 2019. In 2023, IETF summarized custom-built H2C
|
||
functions for selected curves [15], but existing functions do not exclude low-
|
||
order (i.e., ‘invalid’) points by design and may not work with future curves.
|
||
Excluding invalid points at the output can break the constant-time property.
|
||
|
||
Computational performance. SRP-6a mandates the use of a safe prime
|
||
p = 2q + 1 where q is also a prime as the modulus. This leaves the protocol
|
||
undefined for a multiplicative group with short exponents such as DSA, as well
|
||
as for an elliptic curve setting. OPAQUE is built on two building blocks: 1)
|
||
authenticated key exchange (AKE) and 2) hash-to-curve. After OPAQUE was
|
||
|
||
|
||
13
|
||
MODP (safe prime) MODP (DSA) Elliptic Curve
|
||
Scheme Flows KC
|
||
Client Server Client Server Client Server
|
||
SRP-6a 3/4 Exp 2(x12)+1 2(x12)+1 – – – –
|
||
OPAQUE 3/2 Imp 4.5(x12) 3.5(x12) 1(x11)+6.5† 5.5† 4.5+H2C‡ 3.5
|
||
Owl 1/3 Imp – – 14 13 11 10
|
||
Table 1. Comparison among selected PAKE schemes. The flows column gives the
|
||
number of flows for registration/login respectively. Computational cost columns give
|
||
the number of exponentiation in the MODP setting, assuming a 3072-bit modulus for
|
||
concreteness. 2(×12) denotes that the cost of one exponentiation (3071-bit exponent) is
|
||
about the same as 12 typical 3072-bit DSA group exponentiations (256-bit exponent).
|
||
The hash-to-group function in OPAQUE requires an exponentiation with a 2816-bit
|
||
exponent (co-factor), which has cost equal to 11 exponentiations with 256-bit exponent
|
||
in DSA. H2C denotes (yet unknown) cost of a hash-to-curve function. † denotes having
|
||
concerns about ‘invalid’ output. ‡ denotes having concerns about computational cost,
|
||
‘invalid’ output and agility. KC: key confirmation. Exp: explicit. Imp: implicit.
|
||
|
||
|
||
selected by IETF, its designers modified the protocol by using 3DH instead
|
||
of HMQV to instantiate AKE in an IETF Internet draft [22]. Here, we will
|
||
evaluate the performance of OPAQUE based on using HMQV as specified in
|
||
the original paper [20]. (The performance will decrease when 3DH is used). The
|
||
OPAQUE paper assumes a H2C function to map a password to a generator of the
|
||
prime-order (sub)group on an elliptic curve, which leaves the protocol undefined
|
||
for the MODP setting. We fill this gap by using two known H2G functions as
|
||
defined for SPEKE and PAK in IEEE 1363.2 [17] to do the equivalent of hash-
|
||
to-curve in two MODP settings respectively: 1) using a safe-prime modulus; 2)
|
||
using DSA groups. Table 1 summarizes the comparison results (see Hao and
|
||
van Oorschot [14] for a detailed breakdown of cost for SRP-6a and OPAQUE;
|
||
also note that the elliptic curve implementation of Owl has a fewer number of
|
||
scalar multiplications than modular exponentiations in the DSA implementation
|
||
because the public key validation in the EC setting incurs a negligible cost whilst
|
||
in the DSA setting, it requires one full modular exponentiation). Owl has clear
|
||
advantages over SPR-6a in terms of flows, computation, and agility to work with
|
||
both MODP and EC settings. Implementing OPAQUE in DSA gives a lower
|
||
computation cost than using a safe-prime modulus (at the expense of having the
|
||
‘invalid’ output issue). In the DSA setting, the client requires more computation
|
||
than Owl, but the server requires less. A direct comparison between the two in
|
||
the EC setting is difficult due to the cost of H2C yet unclear (aside from the
|
||
‘invalid’ output and the agility issues that need to be addressed).
|
||
Round efficiency. Owl only requires one flow in the registration process,
|
||
fewer than others. Between Owl and OPAQUE, OPAQUE seems to have the
|
||
advantage of needing only two flows in the login process; Owl needs three. The
|
||
(theoretical) advantage of a two-flow OPAQUE is that it allows the server to
|
||
be authenticated in the second flow (based on explicit key confirmation) before
|
||
the client is authenticated. However, doing so is dangerous as it will expose the
|
||
server to an undetectable online dictionary attack [21], in which a malicious client
|
||
|
||
|
||
14
|
||
Schemes MODP (safe prime) MODP (DSA) Ellipic Curve
|
||
SRP-6a 768 B – –
|
||
OPAQUE 2688 B 2336 B† 225 B‡
|
||
Owl – 2720 B 609 B
|
||
Table 2. Comparison of message sizes in bytes (B) among selected PAKE schemes.
|
||
The ‘MODP (safe prime)’ column gives the size in a MODP setting, assuming a 3072-
|
||
bit safe-prime modulus. The ‘MODP (DSA)’ column gives the size in a MODP setting,
|
||
assuming a 3072-bit DSA group with a 256-bit exponent. The “Elliptic Curve” column
|
||
gives the size in an EC setting, assuming a 256-bit prime-order EC group. † denotes
|
||
having concerns about ‘invalid’ output. ‡ denotes having concerns about computational
|
||
cost, ‘invalid’ output and agility.
|
||
|
||
|
||
|
||
does not send the third flow and it is impossible for the server to distinguish
|
||
the authentication failure from a drop-out. (In an asymmetric setting, the server
|
||
is always online, and hence is more vulnerable to online guessing attacks than
|
||
a client.) Preventing this attack requires the client to be authenticated first.
|
||
Hence, OPAQUE actually requires the same three flows as Owl in the login.3
|
||
Message size. We now compare the message size among the three protocols.
|
||
For simplicity, we only consider the login phase and focus on public-key crypto-
|
||
graphic data (excluding auxiliary data such as user identities). Furthermore, we
|
||
only consider implicit key confirmation, hence excluding explicit key confirma-
|
||
tion strings that apply to all schemes. Table 2 summarizes the result. SRP-6a [28]
|
||
involves exchanging two group elements in the login process (we omit the salt).
|
||
Assume a 3072-bit safe-prime modulus is used. The total size is 3072 × 2 = 6,144
|
||
bits = 768 bytes. OPAQUE [20] involves exchanging four group elements and
|
||
an encrypted string using an authenticated encryption scheme (containing two
|
||
group elements and a private key generated from the registration phase). Assume
|
||
OPAQUE uses the same 3072-bit safe-prime modulus as SRP-6a. The total size
|
||
is approximately 3072 × 6 + 3071 = 21,503 bits = 2,688 bytes (we omit the size
|
||
of the IV and the message authenticated code). If a 3072-bit DSA group is used
|
||
instead, the total size is 3072 × 6 + 256 = 18,688 bits = 2,336 bytes. Assume an
|
||
EC setting where the group has a prime order of 256 bits. We assume a group
|
||
element requires 257 bits in a compressed form. Hence, the size of the messages
|
||
is 257 × 6 + 256 = 1,798 bits = 225 bytes. Owl involves sending 6 group elements,
|
||
6 Schnorr ZKP and a short response in the key exchange process. In a 3072-bit
|
||
DSA group, the size of each ZKP (h, r) is 512 bits (see App. §2.1). Hence, the
|
||
total size is 3072 × 6 + 512 × 6 + 256 = 21,760 bits = 2,720 bytes. In an EC
|
||
setting, the size is 257 × 6 + 512 × 6 + 256 = 4,870 bits = 609 bytes. Although
|
||
Owl involves sending more group elements than SRP-6a, it can actually use less
|
||
bandwidth because of its agile support for EC implementations. In the same EC
|
||
setting, the size of the messages in Owl is bigger than that in OPAQUE, but Owl
|
||
is more flexible to work with any elliptic curve that is suitable for cryptography
|
||
3
|
||
The original conference paper describes OPAQUE as a two-flow scheme, but the full
|
||
version has updated the specification requiring three flows in the login [20].
|
||
|
||
|
||
15
|
||
while OPAQUE is restricted by the availability of a constant-time and correct
|
||
(no ‘invalid’ output) H2C function on that curve.
|
||
|
||
|
||
5 Conclusion
|
||
|
||
In this paper, we present a new augmented PAKE protocol called Owl. Our de-
|
||
sign strategy is to utilize Schnorr non-interactive zero-knowledge proof to enforce
|
||
every party to follow the protocol specification honestly. We prove the security
|
||
of Owl based on the standard DDH and CDH assumptions in the random oracle
|
||
model. Through a thorough evaluation, we show Owl provides systematic advan-
|
||
tages over SRP-6a in terms of provable security, computation, bandwidth and
|
||
agility for implementation in versatile group settings. Owl’s agility is attributed
|
||
to the fact that it utilizes only the most basic addition/multiplication operations
|
||
on an elliptic curve (equivalently, multiplication/exponentiation in MODP) plus
|
||
a standard one-way hash function for implementation without depending on any
|
||
ideal cipher, trusted setup, hash-to-group functions or special group character-
|
||
istics (such as the mandated use of a safe-prime modulus in SRP-6a).
|
||
|
||
|
||
Acknowledgement
|
||
|
||
We thank Rene Struik for highlighting to us that the augmented PAKE problem
|
||
had remained unsolved when the IETF PAKE selection process was concluded in
|
||
2020 and encouraging us to explore a new solution. We thank anonymous referees
|
||
for their helpful comments. Hao is supported by EPSRC (EP/T014784/1). Van
|
||
Oorschot is supported by an NSERC Discovery Grant. Chen is supported by the
|
||
EU program: 952697, 101019645, 101069688, 101070627, and 101095634.
|
||
|
||
|
||
References
|
||
1. F. Bao, R. Deng, and H. Zhu. Variations of diffie-hellman problem. In ICICS,
|
||
2003.
|
||
2. M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key exchange secure
|
||
against dictionary attacks. In Eurocrypt, 2000.
|
||
3. S. Bellovin and M. Merritt. Encrypted key exchange: password-based protocols
|
||
secure against dictionary attacks. In IEEE S&P, 1992.
|
||
4. S. Bellovin and M. Merritt. Augmented encrypted key exchange: A password-based
|
||
protocol secure against dictionary attacks and password file compromise. In CCS,
|
||
1993.
|
||
5. T. Bradley, S. Jarecki, and J. Xu. Strong asymmetric PAKE based on trapdoor
|
||
CKEM. In Crypto. Springer, 2019.
|
||
6. B.F. Dos Santos, Y. Gu, S. Jarecki, and H. Krawczyk. Asymmetric pake with low
|
||
computation and communication. In Eurocrypt. Springer, 2022.
|
||
7. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification
|
||
and signature problems. In Crypto, 1987.
|
||
8. C. Gentry et al. PAK-Z+. Submission to IEEE P1363.2, 2005.
|
||
|
||
|
||
16
|
||
9. Y. Gu, S. Jarecki, and H. Krawczyk. KHAPE: Asymmetric PAKE from key-hiding
|
||
key exchange. In Crypto, 2021.
|
||
10. B. Haase and B. Labrique. AuCPace: Efficient verifier-based PAKE protocol tai-
|
||
lored for the IIoT. IACR Trans. CHES, pages 1–48, 2019.
|
||
11. F. Hao. Schnorr non-interactive zero-knowledge proof. RFC 8235, 2017.
|
||
12. F. Hao. Prudent practices in security standardization. IEEE Communications
|
||
Standards Magazine, 2021.
|
||
13. F. Hao and P. Ryan. Password authenticated key exchange by juggling. In SPW,
|
||
2008.
|
||
14. F. Hao and P.C. van Oorschot. SoK: Password-Authenticated Key Exchange–
|
||
Theory, Practice, Standardization and Real-World Lessons. In AsiaCCS, 2022.
|
||
15. A. Hernández, S. Scott, N. Sullivan, R. Wahby, and C. Wood. Hashing to elliptic
|
||
curves. IETF RFC 9380, 2023.
|
||
16. J Hwang, S. Jarecki, T. Kwon, J. Lee, J. Shin, and J. Xu. Round-reduced mod-
|
||
ular construction of asymmetric password-authenticated key exchange. In SCN.
|
||
Springer, 2018.
|
||
17. IEEE Standards Association. IEEE 1363.2-2008: IEEE Standard Specification
|
||
for Password-Based Public-Key Cryptographic Techniques. https://standards.
|
||
ieee.org/standard/1363_2-2008.html.
|
||
18. D. Jablon. Strong password-only authenticated key exchange. SIGCOMM Com-
|
||
puter Commun. Review, 26(5):5–26, 1996.
|
||
19. D. Jablon. Password authentication using multiple servers. In CT-RSA, 2001.
|
||
20. S. Jarecki, H. Krawczyk, and J. Xu. OPAQUE: An asymmetric PAKE protocol
|
||
secure against pre-computation attacks. In Eurocrypt, 2018. See also IACR e-print
|
||
2018/163.
|
||
21. Y. Kobayashi et al. Gateway threshold password-based authenticated key exchange
|
||
secure against undetectable on-line dictionary attack. In ICETE. IEEE, 2015.
|
||
22. H. Krawczyk, D. Bourdrez, K. Lewi, and C. Wood. The OPAQUE asymmetric
|
||
PAKE protocol. IETF draft-irtf-cfrg-opaque-12, 2023.
|
||
23. K. Kurosawa and R. Nojima. Simple adaptive oblivious transfer without random
|
||
oracle. In AsiaCrypt, pages 334–346. Springer, 2009.
|
||
24. T. Kwon. Revision of AMP in IEEE P1363.2 and ISO/IEC 11770-4. Submission
|
||
to IEEE P1363, 2005.
|
||
25. D. Pointcheval and G. Wang. VTBPEKE: Verifier-based two-basis password ex-
|
||
ponential key exchange. In AsiaCCS, 2017.
|
||
26. Claus-Peter Schnorr. Efficient signature generation by smart cards. Journal of
|
||
cryptology, 4(3):161–174, 1991.
|
||
27. V. Shoup. Security Analysis of SPAKE2+. In TCC, 2020.
|
||
28. SRP Protocol Design. http://srp.stanford.edu/design.html. Includes descrip-
|
||
tion of SRP-6a. Accessed 10 February 2023.
|
||
29. M. Vanhoef and E. Ronen. Dragonblood: Analyzing the Dragonfly handshake of
|
||
WPA3 and EAP-pwd. In IEEE S&P, 2020.
|
||
30. T. Wu. The Secure Remote Password protocol. In NDSS, 1998.
|
||
|
||
|
||
Appendix
|
||
A Schnorr non-interactive zero-knowledge proof
|
||
Given a private key x ∈R [0, q − 1] and the corresponding public key X =
|
||
g x mod p, we use Schnorr non-interactive zero-knowledge (NIZK) proof to convey
|
||
|
||
|
||
17
|
||
the knowledge of the exponent x without revealing its value [11]. Specifically, to
|
||
generate a zero-knowledge proof for ZKP{x : g, X}, the prover chooses a random
|
||
secret v ∈R [0, q −1], computes V = g v mod p, and outputs (h, r) as the “proof”,
|
||
where h = H(g∥V ∥X∥ProverID) and r = v − x · h mod q. ProverID represents
|
||
the prover’s unique identity. H(·) is a secure one-way hash function which serves
|
||
to transform an interactive ZKP into a non-interactive one based on the Fiat-
|
||
Shamir heuristics [7]. Verification of the ZKP requires that the verifier check:
|
||
1) X has the correct prime order; and
|
||
?
|
||
2) h = H(g∥g r · X h ∥X∥ProverID), where h is the received value.
|
||
Note: In the original J-PAKE protocol [13], the Schnorr ZKP contains (V, r)
|
||
while we use (h, r). The two are equivalent [11, §4] with the same computation
|
||
cost, but the latter has a more compact size in a MODP setting.
|
||
|
||
|
||
|
||
|
||
18
|
||
|