1236 lines
78 KiB
Plaintext
1236 lines
78 KiB
Plaintext
Making an Asymmetric PAKE
|
||
Quantum-Annoying by Hiding Group Elements‡
|
||
|
||
Marcel Tiepelt1[0000−0002−3389−208X] , Edward Eaton2 , and Douglas
|
||
Stebila3[0000−0001−9443−3170]
|
||
|
||
KASTEL, Karlsruhe, Germany, marcel.tiepelt@kit.edu
|
||
1
|
||
2
|
||
National Research Council Canada, Ottawa, Ontario, Canada
|
||
3
|
||
University of Waterloo, Waterloo, Ontario, Canada, dstebila@uwaterloo.ca
|
||
|
||
|
||
|
||
Abstract The KHAPE-HMQV protocol is a state-of-the-art highly ef-
|
||
ficient asymmetric password-authenticated key exchange protocol that
|
||
provides several desirable security properties, but has the drawback of
|
||
being vulnerable to quantum adversaries due to its reliance on discrete
|
||
logarithm-based building blocks: solving a single discrete logarithm al-
|
||
lows the attacker to perform an offline dictionary attack and recover the
|
||
password. We show how to modify KHAPE-HMQV to make the protocol
|
||
quantum-annoying: a classical adversary who has the additional ability
|
||
to solve discrete logarithms can only break the protocol by solving a dis-
|
||
crete logarithm for each guess of the password. While not fully resistant
|
||
to attacks by quantum computers, a quantum-annoying protocol could
|
||
offer some resistance to quantum adversaries for whom discrete logar-
|
||
ithms are relatively expensive. Our modification to the protocol is small:
|
||
encryption (using an ideal cipher) is added to one message. Our analysis
|
||
uses the same ideal cipher model assumption as the original analysis
|
||
of KHAPE, and quantum annoyingness is modelled using an extension
|
||
of the generic group model which gives a classical adversary a discrete
|
||
logarithm oracle.
|
||
|
||
Keywords: password-authenticated key exchange · quantum-resistant
|
||
· quantum-annoying · generic group model
|
||
|
||
|
||
|
||
|
||
1 Introduction
|
||
A wide-spread method for authentication in client-server situations involves a key
|
||
exchange where the server is authenticated through a public key infrastructure,
|
||
‡
|
||
This version of the contribution has been accepted for publication, after peer re-
|
||
view but is not the Version of Record and does not reflect post-acceptance improve-
|
||
ments, or any corrections. The Version of Record of this contribution is published in
|
||
ESORICS 2023, Lecture Notes in Computer Science, vol 14344, available online at:
|
||
https://doi.org/10.1007/978-3-031-50594-2_9. Use of this Accepted Version is subject
|
||
to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/
|
||
gp/open-research/policies/accepted-manuscript-terms.
|
||
2 Tiepelt, Eaton and Stebila
|
||
|
||
while the client authenticates themselves with a password by transmitting the
|
||
password directly over the encrypted channel. This method is suboptimal since
|
||
the user’s password is exposed to the server.
|
||
A password authenticated key exchange (PAKE) protocol enables two parties
|
||
to perform a key exchange, authenticated using mutual knowledge of a shared
|
||
password, without revealing the password to the network or to each other. The
|
||
setting of PAKEs allows two kinds of attacks: online attacks (the adversary
|
||
interacting with either party), and offline attacks (the adversary operating locally
|
||
based on what is has observed from previous online interactions). Password-
|
||
based protocols are always vulnerable to online dictionary attacks, where the
|
||
adversary can rule out one password guess with each online interaction with
|
||
a party. The goal of a PAKE is to ensure that offline dictionary attacks are
|
||
infeasible, for example because of an intractability assumption. While PAKEs
|
||
have been known for decades, there was little progress in adoption for many
|
||
years, but there is renewed interest in adoption of PAKEs via a variety of recent
|
||
and ongoing standardization efforts [18,6,19,1,2].
|
||
This paper focuses on KHAPE [10], a compiler that turns a key hiding au-
|
||
thenticated key exchange (KH-AKE) and a PAKE into an asymmetric PAKE
|
||
(aPAKE). Asymmetric PAKEs improve upon regular PAKEs by forcing an at-
|
||
tacker to perform an exhaustive search on the password even after server com-
|
||
promise, since the value stored by the server cannot be used to impersonate the
|
||
client. The OPAQUE framework [13] introduced the notion of strong asymmet-
|
||
ric PAKEs (saPAKE), which further guarantees that no pre-computation can
|
||
be performed to aid in the exhaustive search for the password in the case of
|
||
server compromise. This is achieved by combining an oblivious pseudo-random
|
||
function (OPRF) and a PAKE.
|
||
Most PAKEs are based on the hardness of solving the discrete logarithm prob-
|
||
lem (see [11] for an overview), making them vulnerable to attacks by quantum
|
||
computers, thus motivating the question of building PAKEs that are quantum-
|
||
resistant. The obvious answer is to build new PAKEs that rely on post-quantum
|
||
intractability assumptions, and post-quantum PAKEs are starting to emerge
|
||
in the literature. These new PAKEs (e.g., see [4]) are based on key encapsu-
|
||
lation mechanisms to match the standardized quantum-secure encryption [15].
|
||
However, there may be other interim options requiring fewer modifications by
|
||
augmenting existing protocols.
|
||
|
||
Quantum-annoying PAKEs. During the CFRG PAKE standardization process
|
||
in 2019, it was observed [20] for one of the Diffie–Hellman-based candidates that
|
||
even if an attacker could solve discrete logarithms, they could not immediately
|
||
recover the password. Instead, an attacker seemed to have to do a discrete log-
|
||
arithm for each guess of the password even during an offline dictionary attack:
|
||
this property was named “quantum-annoying”. If solving such a problem remains
|
||
reasonably expensive, then a moderate level of security can still be achieved.
|
||
Eaton and Stebila [7] developed a formalization of the quantum-annoying
|
||
property for PAKEs by considering a classical adversary working in the generic
|
||
group model who is given the additional power of a discrete logarithm oracle.
|
||
Making an Asymmetric PAKE Quantum-Annoying 3
|
||
|
||
They showed that the base version of the symmetric PAKE protocol CPace [3]
|
||
was quantum-annoying in the generic group model. One main characteristic of
|
||
CPace that lead to it being quantum-annoying is that the password π shared by
|
||
the client and server is used to derive a generator gπ of the group, and then a
|
||
Diffie–Hellman key exchange is performed using that generator (gπxy ). But from
|
||
the perspective of an adversary who only sees Diffie–Hellman public keys (gπx
|
||
and gπy ), no information is gained about the password π since for each π ′ there
|
||
′
|
||
is an x′ such that gπx′ = gπx .
|
||
|
||
Our contributions. Whereas CPace is a symmetric PAKE, the KHAPE-HMQV
|
||
protocol constructed by the KHAPE compiler [10] is an asymmetric PAKE, so
|
||
compromise of a server using KHAPE-HMQV does not enable the adversary to
|
||
impersonate a user without first performing an offline dictionary attack. How-
|
||
ever, the protocol is not quantum-annoying: after seeing just a single transcript,
|
||
a single discrete logarithm computation suffices to enable an offline dictionary
|
||
attack to recover the user’s password. We address this vulnerability by presenting
|
||
the QA-KHAPE protocol, a quantum-annoying variant of KHAPE-HMQV. As
|
||
shown in Fig. 1, our modifications entail encapsulating an additional key into the
|
||
server-stored credentials, which is later used by the principals to encrypt their
|
||
Diffie–Hellman key-pairs prior to exchanging messages. This effectively means
|
||
that each guess of the password causes the transcript to decrypt (under a sym-
|
||
metric key dependent on the password) to a different pair of Diffie–Hellman
|
||
public keys, so a new discrete logarithm must be performed each time.
|
||
The changes to the protocol require only minimal computational and commu-
|
||
nication overhead, with the same number of rounds as KHAPE-HMQV and only
|
||
a single additional ideal cipher ciphertext (increasing the server-client cipher-
|
||
text from three to four elements). The client-server communication remains un-
|
||
changed, and the protocol requires two additional ideal cipher computations, one
|
||
encryption, and one decryption.
|
||
We show that QA-KHAPE is quantum-annoying following the methodology
|
||
of [7]: the adversary is a classical adversary in the generic group model with
|
||
the addition of a discrete logarithm oracle. In Section 3.1, we define a secur-
|
||
ity game in the generic group model tailored to capturing the core quantum
|
||
annoying property of the QA-KHAPE protocol. In Section 4, we apply this to
|
||
show that QA-KHAPE is secure in a quantum-annoying variant of the standard
|
||
Bellare–Pointcheval–Rogaway (BPR) security model for asymmetric password
|
||
authenticated key exchange.
|
||
|
||
Limitations. Just as in the original security proof of KHAPE by [10], our analysis
|
||
also relies on the ideal cipher assumption. Care must be taken for an instantiation
|
||
of the IC, which is discussed in [10, Section 8].
|
||
Further, we wish to highlight for the reader that the “quantum annoying”
|
||
security notion is an intermediate notion below fully quantum-resistant. One
|
||
limitation of the quantum annoying security notion is that it has a narrow view
|
||
of quantum capabilities: by using a formalism in the generic group model with
|
||
a discrete logarithm oracle, we are effectively assuming that the only quantum
|
||
4 Tiepelt, Eaton and Stebila
|
||
|
||
operation an adversary will do is run Shor’s algorithm, which is certainly less
|
||
than the full power available to a polynomial time quantum computer.
|
||
Even just considering security against quantum computers running Shor’s
|
||
algorithm, a protocol “secure” in the quantum-annoying model is still vulnerable
|
||
to attacks by quantum computers, it is just that the attack scales in the size of
|
||
the password space. This leads to the question of the cost of computing a discrete
|
||
logarithm on a quantum computer. While it is impossible to predict the efficiency
|
||
of quantum computers in the far future, current research suggests that the first
|
||
generations of quantum computers capable of solving cryptographically relevant
|
||
discrete logarithm problems will require significant resources in order to do so
|
||
[17,8,9,16]. These estimates are undoubtedly coarse and may be off by several
|
||
orders of magnitude, but it is plausible that even for early cryptographically
|
||
relevant quantum computers, computing a single discrete logarithm will not be
|
||
cheap, and that computing millions of discrete logarithms to find the password
|
||
in a quantum-annoying PAKE may be prohibitively expensive.
|
||
More recently, a preprint has examined the “multiple discrete logarithm”
|
||
problem induced by the quantum annoying model [12]. In this work, the authors
|
||
show that it is possible to (asymptotically) solve m discrete logarithm problems
|
||
(in a generic group) with a quantum computer more efficiently than m times
|
||
the cost of a single Shor’s instance. In particular, their algorithm solves m dis-
|
||
crete logarithms with around log m times fewer quantum group operations (if
|
||
m = Ω(log p), where p is the size of the group). This comes at the expense of re-
|
||
quiring large quantum memory to compute everything simultaneously. Whether
|
||
this represents a concrete improvement to the ability of an adversary to break
|
||
quantum annoying security (and if so, how large the grouping m should be) is
|
||
an interesting open question. Our proofs bound the adversary’s success probab-
|
||
ility in terms of the number of discrete logarithm oracle queries made. If it is
|
||
a practical improvement to group such queries, this does not affect our proofs,
|
||
only how the induced bounds translate to real-world estimates of adversary cost.
|
||
|
||
|
||
2 Preliminaries
|
||
2.1 Quantum Annoying-ness in the Generic Group Model.
|
||
In the normal generic group model there is a multiplicative public representation
|
||
of group elements taken uniformly from {0, 1}κ , and an additive secret represent-
|
||
ation in Zp . The public representations have no intrinsic structure, and so any
|
||
information about the group is obtained through the group operation oracle.
|
||
Let ⟨g⟩ = G be a generic group of size p with group operation ◦. When gw ◦ gv
|
||
is queried, for example (g v , g w ) 7→ g v+w , a table Tggm is used to retrieve the
|
||
secret representations of gv and gw , v, w ∈ Zp . Then v + w (mod p) is the secret
|
||
representation of g v+w . If g v+w has already been given a public representation,
|
||
that is returned. Otherwise, a uniformly random string is sampled from {0, 1}κ ,
|
||
assigned as a new public representation to g v+w in the table Tggm , and provided
|
||
back to the querier. Similarly, the discrete logarithm oracle Dlog : G × G → Zp
|
||
takes as input two group elements and outputs the discrete logarithm. The query
|
||
Making an Asymmetric PAKE Quantum-Annoying 5
|
||
|
||
Dlog(gv , gw ) can be responded to by looking up gv and gw in Tggm and returning
|
||
w · v −1 (mod p).
|
||
The generic group model is a powerful tool, but limited in its ability to reason
|
||
about whether the adversary’s interactions with the discrete logarithm oracle are
|
||
sufficient to determine Dlog(g, gt ) for a specific group element gt . Naturally, if
|
||
they have made exactly this query, the discrete logarithm is known. But other
|
||
queries, such as Dlog(g, gt2 ), are also sufficient to make Dlog(g, gt ) knowable.
|
||
The framework of [7] simulates the generic group model in such a way that
|
||
such specific statements can be made. Let G1 , G2 , . . . Gµ be a collection of (pub-
|
||
lic representations of) group elements whose discrete logarithm (with respect to
|
||
the group generator g) are of potential interest to the adversary. When we main-
|
||
tain the group, rather than imbuing these group elements with specific secret
|
||
representations in Zp , we instead denote each as a formal independent variable
|
||
χ1 , . . . , χµ . Group operations now correspond to addition over a vector space of
|
||
dimension µ+1. For example, in computing (G1 ◦G1 )◦G2 we would calculate the
|
||
secret representation as 2χ1 + χ2 and give this a unique public representation in
|
||
{0, 1}κ . Thus, secret representations
|
||
P can now be written as a linear combination
|
||
of the χi variables, i.e., α0 + i αi χi .
|
||
Thinking about how these secret representations interact with the Dlog
|
||
oracle is how we can start to reason about what discrete logarithms are. Say P the
|
||
adversary queries Dlog(A, B), and the secret representation of A is α0 + αi χi
|
||
(respectively with β for B). If the adversary is given the response δ (so that
|
||
Aδ = B), P this imposes Pa constraint on our variables. Specifically, it says that
|
||
δ (α0 + αi χi ) = β0 + βi χi , which we can rewrite as
|
||
µ
|
||
X
|
||
(δαi − βi )χi = β0 − δα0 . (1)
|
||
i=1
|
||
|
||
This linear constraint lets us define an equivalence relation: if two secret repres-
|
||
entations are the same ‘modulo’ the linear constraints imposed by responses to
|
||
Dlog, they should have the same public representation. Consequently, if, mod-
|
||
ulo these constraints, a secret representation χi is equivalent to some a ∈ Zp ,
|
||
then Dlog(g, Gi ) has taken on a definite value a, whether or not it was actually
|
||
queried. Otherwise, it can still take on any possible value.
|
||
By taking the coefficients of the χi variables in Equation 1 we can construct
|
||
a matrix D and a vector ⃗r (we write vectors as column vectors), so that the set
|
||
of constraints
|
||
P is easily summarized as D⃗ χ = ⃗r. Similarly, a secret representation
|
||
a0 + ai χi can be written as the pair (a0 , ⃗a). In more detail, the equivalence
|
||
relation can be defined as follows:
|
||
|
||
Definition 1. For group elements ga , gb with secret representation (a0 , ⃗a) and
|
||
(b0 , ⃗b), we say that ga is (D, ⃗r)-equivalent to gb if there exists an ω
|
||
⃗ ∈ ZqpD such
|
||
that ω ⃗ D = ⃗a − ⃗b and ω
|
||
T T T T
|
||
⃗ ⃗r = b0 − a0 .
|
||
Note that this is indeed an equivalence relation (reflexivity is proven by taking
|
||
⃗ = ⃗0, symmetry is proven by taking −⃗
|
||
ω ω , and transitivity is proven by taking
|
||
6 Tiepelt, Eaton and Stebila
|
||
|
||
ω
|
||
⃗1 +ω ⃗ 2 ). The reason that this definition gives us what we want is that when it is
|
||
satisfied, we have P that b0 −aP 0 =ω⃗ T ⃗r = ω χ = (⃗aT −⃗bT )⃗
|
||
⃗ T D⃗ χ = ⃗aT χ⃗ −⃗bT χ⃗ , telling
|
||
us that a0 + ai χi = b0 + bi χi , as we expect. We can now describe how the
|
||
G and the Dlog oracle are simulated in full detail. Note that the simulation
|
||
is not efficient [7, Sec. 4], since the simulation requires to search through all
|
||
previous queries to check if a linear relationship exists. However, the purpose of
|
||
the framework is to give an information-theoretic bound (in the generic group
|
||
model) relative to the number of discrete logarithm queries to define a specific
|
||
discrete logarithm, thus the exact efficiency is not relevant.
|
||
Dlog(g V , g W ): If gV or gW do not exist in Tggm , then abort. Otherwise, let
|
||
(v0 , ⃗v ), (w0 , w)
|
||
⃗ be secret representations of gV , gW respectively. Sample a random
|
||
vector ⃗s such that D⃗s = ⃗r and compute δ = (w0 + ⟨w, ⃗ ⃗s⟩)/(v0 + ⟨⃗v , ⃗s⟩) mod p.
|
||
Add the row δ⃗v T − w ⃗ T to D, and value w0 − δv0 to vector ⃗r. Then δ is the
|
||
discrete logarithm that is returned. This corresponds to [7, Alg. 2].
|
||
◦(g V , g W ): If gV or gW do not exist in Tggm , then abort. Otherwise, for the
|
||
secret representations (v0 , ⃗v ), (w0 , w),
|
||
⃗ let (z0 , ⃗z) = (v0 + w0 , ⃗v + w).
|
||
⃗ If z appears
|
||
in Tggm , return the corresponding public representation. Otherwise, check if there
|
||
exists an entry (f0 , f⃗) of Tggm that is (D, ⃗r)-equivalent to (z0 , ⃗z). If so, return
|
||
the public representation of that entry. If no such (D, ⃗r)-equivalent entry exists,
|
||
sample a new public representation, add the entry Tggm [gZ ] = (z0 , ⃗z) and return
|
||
g Z . This corresponds to [7, Alg. 5].
|
||
With this setup, we can prove Lemma 1, which is a generalization of [7,
|
||
Lemma 1] and an instantiation of which is used in a game hop in Section 3.2.
|
||
Lemma 1 (Unique Solutions). Let ga and gb be public representations of
|
||
group elements, with corresponding secret representations (a0 , ⃗a), (b0 , ⃗b). Let (D, ⃗r)
|
||
be the current set of constraints on discrete logarithms. Then the discrete logar-
|
||
⃗T
|
||
respect to ga is defined if and only if [b |b0 ] is in the rowspace
|
||
ithm of gb with
|
||
−D ⃗r
|
||
of the matrix .
|
||
⃗aT a0
|
||
Proof. The discrete logarithm is defined if and only if there exists an α such
|
||
that gaα is (D, ⃗r)-equivalent to gb . By definition, this is the same as the existence
|
||
of α, ω
|
||
⃗ such that ω ⃗ T D = α⃗aT − ⃗bT , and ω⃗ T ⃗r = b0 − αa0 . We can rewrite this
|
||
h i T −D ⃗
|
||
r
|
||
relation as ⃗bT | b0 = −⃗ ω
|
||
⃗
|
||
|
||
ω T D + α⃗aT | ω
|
||
⃗ T ⃗r + αa0 = α .
|
||
⃗aT a0
|
||
This establishes that if the discrete logarithm is defined, [⃗b | b0 ] is indeed in
|
||
the rowspace, and if it is in the rowspace that the discrete logarithm is defined
|
||
(and equal to the α value that is the scalar for the ‘a’ row). ⊔
|
||
⊓
|
||
Corollary 1. Let gb be the public representation of a group element and (b0 , ⃗b)
|
||
the corresponding secret representation. Let g be the generator of the group, which
|
||
has secret representation (1, ⃗0). Then the discrete logarithm of gb with respect to
|
||
g is defined if and only if ⃗b is in the row span of D.
|
||
Proof. We apply Lemma 1 with ⃗a = ⃗0. Since the zero vector cannot affect the
|
||
row span, we can conclude that ⃗bT must be in the row span of D.
|
||
Making an Asymmetric PAKE Quantum-Annoying 7
|
||
|
||
Table 1. Examples for simulation of queries to the generic group model group oper-
|
||
ation and the ideal cipher. The queries are in order from top to bottom. The public
|
||
representations returned from the oracle are uniformly random strings that contain no
|
||
information beyond what was given in the query and particularly are sampled inde-
|
||
pendently.
|
||
|
||
Oracle Label Public Representation Secret Representation
|
||
Initialization g0 11001100110111101 1
|
||
◦(g0 , g0 ) g0 g0 11001010110011101 2
|
||
IC ga 11011000101110001 χa (uniformly random index a)
|
||
IC gb 11000111111001110 χb (uniformly random index b)
|
||
◦(ga , gb ) ga gb 10111100011100111 χa + χb
|
||
|
||
|
||
Table 2. Example simulation of the Dlog oracle with public and secret representations
|
||
as in Table 1 and with a generic group of size p = 29. The vector ⃗s is sampled at random
|
||
such that D⃗s = ⃗r, and δ is the returned discrete logarithm as described in the Dlog
|
||
oracle. For the vector ⃗s only the relevant entries are displayed as integers in Z29 , and all
|
||
other entries are marked with ∗, denoting a random integer which does not impact the
|
||
computation of δ. The first Dlog query adds a zero-vector to D, since the Dlog (i.e.,
|
||
2) was already defined by the secret representation. Since D and ⃗r are empty, there is
|
||
no restriction on the choice of ⃗s. The 2nd and 3rd query return a random integer δ in
|
||
the solution space. The response to the 4th query was already constrained by the 2nd
|
||
and 3rd query, which can also be seen by checking that the vector corresponding to ⃗b
|
||
was already in the row span of D before this query was received.
|
||
|
||
Add to D Add to ⃗r
|
||
Dlog(g v , g w ) gv gw ⃗s δ χ1 χa χb
|
||
Dlog(g, g1 ) 1 2 (∗, ∗, ∗) 2 (forced by relations) 0 0 0 0
|
||
Dlog(g, ga ) 1 χa (∗, 13, ∗) 13 (random in Zp ) 0 −1 0 −13
|
||
Dlog(ga , gc ) χa χa + χb (∗, 13, 4) (13+4)
|
||
13
|
||
≡ 8 mod 29 (random in Zp ) 0 7 −1 0
|
||
Dlog(g, gb ) 1 χb (∗, 13, 4) 4 (forced by relations) 0 0 −1 −4
|
||
|
||
|
||
|
||
|
||
For the other direction we know that there exists some ω ⃗ such that ω ⃗ T D = ⃗bT .
|
||
Then we claim that the discrete logarithm between g and gb is b0 + ω ⃗ T ⃗r. This is
|
||
T ⃗
|
||
because we want (b0 + ω ⃗ ⃗r, 0) to be (D, ⃗r)-equivalent to gb , and indeed we can
|
||
see that −⃗ω satisfies −⃗ω T D = −⃗bT and −⃗ ω T ⃗r = b0 − (b0 + ω
|
||
⃗ T ⃗r) as desired. ⊔ ⊓
|
||
|
||
|
||
|
||
Table 1 gives an example of queries defining public and secret representa-
|
||
tions of the generic group model. Table 2 gives an example for simulating Dlog
|
||
queries, showing the cases where the Dlog can take a uniformly random value
|
||
in Zp and when the Dlog between two elements is already defined (but has not
|
||
yet been queried).
|
||
8 Tiepelt, Eaton and Stebila
|
||
|
||
2.2 Security Model for Asymmetric PAKE
|
||
The BPR00 model [5] for security of an asymmetric password-authenticated
|
||
key exchange protocol is defined by the interaction of a set of instances Π iP
|
||
of principals P , which are either a client C or server S, and i denotes the i-th
|
||
such instance. Each principal takes as input a long-lived (LL) secret. The client’s
|
||
LL secret is a password π; the server’s secrets are the credentials credS [C] that
|
||
are established during a Registration phase. The model further defines a set
|
||
of oracles that correspond to an adversary’s interaction with principals that
|
||
run the protocol in question. The adversary may receive a passive transcript
|
||
(Execute queries), or actively engage (Send queries) in the communication.
|
||
They may further request the session key (Reveal queries) or corrupt instances
|
||
(Corrupt queries) which effectively returns the principal’s long-lived keys (weak
|
||
corruption). The security is defined by the adversary’s probability to decide if
|
||
they received a session key or a random string after submitting a Test query
|
||
to a fresh instance. In the setting of quantum-annoying-ness, fresh means that
|
||
neither the instance nor any partnered instance may be corrupted. A challenge
|
||
bit that is sampled uniformly random before any interaction takes place decides
|
||
which of the two (i.e., real-or-random) is the case. In the generic group model, the
|
||
adversary additionally gets access to the group operation and discrete logarithm
|
||
oracle (cf. Section 2.1). A protocol is quantum-annoying in the BPR00 model, if
|
||
the adversary’s advantage to output the challenge bit is bounded by the number
|
||
of Send queries (qSend ) and discrete logarithm queries (qDlog ),
|
||
1 qSend + qDlog
|
||
AdvQA-BPR
|
||
Protocol (A) = Pr [A guesses challenge bit] − ≤ + ϵ , (2)
|
||
2 N
|
||
with a password space of size N and ϵ negligible in the security parameter κ.
|
||
|
||
2.3 KHAPE-HMQV
|
||
The KHAPE compiler [10] transforms a key-hiding authenticated key exchange,
|
||
a PAKE, a random oracle, and an ideal cipher into an asymmetric PAKE which
|
||
provides key establishment with key integrity and confirmation, mutual authen-
|
||
tication and forward secrecy. A highly efficient instantiation [10, Fig. 14] uses
|
||
the HMQV [14] protocol, the security of which is based on the computational
|
||
Diffie–Hellman problem.
|
||
KHAPE is split into a registration and an aPAKE phase. During registration
|
||
the server generates the KH-AKE key-pairs (a, A := g a ), (b, B := g b ), partially
|
||
encrypts them using the password as a key, e ← IC.E(π, a, B), and stores the
|
||
ciphertext along with (A, b). All other values are discarded. In the aPAKE phase
|
||
the server generates a key-pair (y, Y ) and sends (Y, e) to the client. The client de-
|
||
crypts e using their password and generates a key pair (x, X). A Diffie–Hellman
|
||
session is computed from (a, x, B, Y ) which is used to derive a key-confirmation
|
||
value τ , and later the session key. The key confirmation is sent along with the
|
||
value X to the server, who computes the equivalent Diffie–Hellman session from
|
||
(b, y, A, X), verifies the key confirmation, and either computes a session key and
|
||
Making an Asymmetric PAKE Quantum-Annoying 9
|
||
|
||
Registration on Server input (π, C) (a, A), (b, B) fresh AKE keys; sk ←
|
||
−
|
||
$
|
||
{0, 1}κ
|
||
e ← IC1 .E(π, a, B, sk )
|
||
store credS [C] = (b, A, e, sk )
|
||
|
||
aPAKE C(sid, S, π) S(sid, C, credS [C]
|
||
e, Y
|
||
a, B, sk ← IC1 .D(π, e) y←
|
||
−
|
||
$
|
||
Zp , Y ← g y
|
||
x← −
|
||
$
|
||
Zp , X ← g x
|
||
hX ← H1 (sid, C, S, X), hY ← H1 (sid, C, S, Y )
|
||
x+hX ·a
|
||
σC ← Y · B hY
|
||
k1 ← H2 (sid, C, S, X, Y, σC )
|
||
cX ← IC2 .E(sk, X) cX , τ ▷ In KHAPE-HMQV, X is sent instead of cX
|
||
τ ← prf(k1 , 1)
|
||
X ← IC2 .D(sk, cX )
|
||
hX ← H1 (sid, C, S, X), hY ← H1 (sid, C, S, Y )
|
||
y+hY ·b
|
||
σS ← X · AhX
|
||
k2 ← H2 (sid, C, S, X, Y, σS )
|
||
if τ ̸= prf(k2 , 1): γ = K2 = ⊥
|
||
γ
|
||
if γ ̸= prf(k1 , 2): K1 ← ⊥ else: γ ← prf(k2 , 2), K2 ← prf(k2 , 0)
|
||
else: K1 ← prf(k1 , 0)
|
||
|
||
Figure 1. QA-KHAPE: quantum-annoying variant of KHAPE-HMQV [10, Fig 14],
|
||
with our changes compared to KHAPE-HMQV highlighted.
|
||
|
||
|
||
a new key confirmation (which is send to the client), or sets both to ⊥. The
|
||
client checks the key confirmation and computes the session key, or sets it to ⊥.
|
||
In the quantum-annoying setting, KHAPE-HMQV is susceptible to an offline
|
||
attack on the password using a single discrete logarithm query. Given a transcript
|
||
(e, Y, X, τ ) an adversary can determine a list of possible values for KH-AKE
|
||
key-pairs: each password guess πi gives a pair of candidate values (ai , Bi ) ←
|
||
IC.D(πi , e). Additionally, they can query the discrete logarithm oracle once on
|
||
the value X, receiving x. Then for each password guess (i.e., for each ai , Bi ), they
|
||
can verify if the Diffie–Hellman completion results in the key-confirmation value
|
||
τ from the transcript, effectively providing an offline method to check passwords.
|
||
|
||
|
||
2.4 Quantum-Annoying KHAPE-HMQV
|
||
|
||
Our QA-KHAPE protocol, presented in Fig. 1, is a quantum-annoying aPAKE.
|
||
The construction is based on KHAPE-HMQV and requires only minimal changes,
|
||
which are highlighted in the figure. During the registration phase the server gen-
|
||
erates an additional secret key sk which is then encrypted using the π and stored
|
||
as part of the credentials. Correspondingly, during the aPAKE phase the client
|
||
decrypts e obtaining this key sk, which they use to encrypt the ephemeral value
|
||
X, resulting in the ciphertext c, which is then sent to the server. Briefly speaking,
|
||
QA-KHAPE is quantum-annoying because an adversary receiving a transcript
|
||
10 Tiepelt, Eaton and Stebila
|
||
|
||
must now solve a discrete logarithm for every decryption of c or e to verify if a
|
||
password guess was correct. This comes at the cost of an additional secret key
|
||
to be stored as credentials, which increases the size of first message from server
|
||
to client. The client has to perform one additional decryption and encryption,
|
||
while the server has to perform one additional decryption.
|
||
|
||
Security. The QA-KHAPE protocol is a quantum-annoying aPAKE in the gen-
|
||
eric group (cf. Section 2.1), ideal cipher and random oracle model and features
|
||
mutual authentication and key confirmation. No perfect forward secrecy can be
|
||
achieved in the setting of quantum-annoying for KHAPE-HMQV, because com-
|
||
promise of any party releases a static secret that, together with the public value
|
||
e, removes all the ambiguity on the group elements in question (i.e., A, B, X).
|
||
This enables an offline attack on the password using only a single discrete log-
|
||
arithm query. Note that a quantum-annoying PAKE achieving perfect forward
|
||
secrecy would mean to establish a secure, authenticated key without taking ad-
|
||
vantage of the password or credentials, which seemingly contradicts the main
|
||
point of a PAKE; establishing this formally is an interesting question for future
|
||
work.
|
||
All other properties of KHAPE-HMQV are preserved, for example, security
|
||
based on the computational Diffie–Hellman assumption against purely classical
|
||
attackers, and thus a full fall back to security of KHAPE-HMQV. The quantum-
|
||
annoying security is summarized in our main contribution, Theorem 1.
|
||
|
||
Theorem 1. Let G be a cyclic group of size p, H1 , H2 be random oracles and
|
||
IC1 , IC2 ideal ciphers with ciphertext space {0, 1}n1 , {0, 1}n2 respectively. Let
|
||
qSend , qExec , qHi , qICi , q◦ , qDlog be the number of queries to the QA-BPR oracles,
|
||
and let ϵprf an adversary’s chance to distinguish prf from a random function. Let
|
||
N be the size of the password space for π. Then the advantage of an adversary
|
||
to win the QA-BPR game for the QA-KHAPE protocol in Fig. 1 is bounded by
|
||
|
||
qDlog + qSend
|
||
AdvQA-KHAPE
|
||
QA-BPR ≤ +ϵ (3)
|
||
N
|
||
qExec + qSend (qIC1 + qIC2 + q◦ )2 + (qDlog q◦2 ) qExec qExec + qSend
|
||
ϵ := −1 + + n1 +
|
||
ϵprf p 2 2 n2
|
||
2 2 2
|
||
qSend · (q◦ + 1) (2qIC1 + qIC2 ) (qIC1 ) (2qIC1
|
||
+ qIC2
|
||
) (qIC1
|
||
) qH2
|
||
+ + + + + +
|
||
p p 2κ p 2κ p
|
||
|
||
We prove Theorem 1 in two steps: first, in Section 3.1, we introduce the
|
||
KHAPECORE -game that captures the quantum-annoying property of QA-KHAPE
|
||
in the generic group model. Briefly speaking, the game models the aPAKE
|
||
without key-confirmation values and is defined such that any adversary can only
|
||
win if they query the correct Diffie–Hellman completion to the random oracle.
|
||
This allows us to quantify the number of discrete logarithm queries required,
|
||
and to prove that every password guess requires either an online interaction, or
|
||
a respective discrete logarithm query. Formally, this is captured in Theorem 2
|
||
Making an Asymmetric PAKE Quantum-Annoying 11
|
||
|
||
which we prove in Section 3.2. Second, we reduce the QA-BPR-security of the
|
||
QA-KHAPE protocol to the KHAPECORE -game, which is represented by The-
|
||
orem 1 and which we prove in Section 4. Together, these yield the proof of the
|
||
quantum-annoying property.
|
||
|
||
|
||
3 Generic Group Security: KHAPECORE
|
||
|
||
We define a game KHAPECORE that captures the quantum annoying property
|
||
of the protocol in Fig. 1, namely the indistinguishability of the keys k1 , k2 from
|
||
random, which translates the approach of [7, Sec 3] into the setting of an aPAKE.
|
||
|
||
|
||
3.1 Security Game
|
||
|
||
The game is defined over a set [L] registrants; each l ∈ [L] is associated with
|
||
static, secret variables πl , skl , al , Bl and a static, public variable el . The vari-
|
||
ables are set on initialization of the KHAPECORE -game via the Registration
|
||
oracle (cf. Algorithm 1), along with uniformly random sampled challenge bit s.
|
||
Additionally, each registrant l is associated with a counter ctrl initialized to 0
|
||
corresponding to the interaction with the lth set of static variables. Each in-
|
||
teraction is called an instance. The adversary may interact with an arbitrary
|
||
number of registrants and instances through a set of oracles, eventually allowing
|
||
the adversary to obtain the keys k1 , k2 . The challenge bit determines if these
|
||
keys are real (if s = 0), in which case they are computed from Diffie-Hellman
|
||
session, or random (if s = 1).
|
||
|
||
Interface. The oracles take as input a value l matching a set of static vari-
|
||
ables which are used by the game to respond to a query. Ephemeral variables
|
||
for an instance (l, ctrl ) are stored for consistent use by the other oracles. The
|
||
PassiveExec oracle (cf. Algorithm 2) corresponds to a passive execution of
|
||
the protocol in Fig. 1, excluding the key confirmation values. The ActiveC or
|
||
ActiveS oracles (cf. Algorithms 4 and 5), correspond to interacting with, or im-
|
||
personating, either party in the QA-KHAPE protocol, and thus at most one of
|
||
the two may be queried for each instance. The Active oracles compute, depend-
|
||
ing on the value of the challenge bit s, either a key value kl,ctrl ,i from the input
|
||
and the static variables or output a uniformly random string. The GetStatic
|
||
oracle (cf. Algorithm 3) mimics the corruption of parties, which causes the game
|
||
to reprogram the outputs of the Active oracles into the respective positions be-
|
||
fore it returns the secret static variables. Finally, the adversary is given access to
|
||
the random oracles H1 , H2 , the block-ciphers IC1 , IC2 modeled by ideal ciphers
|
||
and access to an interface of the generic group model.
|
||
|
||
Output. The KHAPECORE -game outputs 1 if the adversary’s output matches
|
||
the challenge bit s or if they if they query H2 (l, m, X, Y, σl,C ) (respectively
|
||
H2 (l, m, X, Y, σl,S )) after submitting a query ActiveC (l, e, Y ) (respectively
|
||
12 Tiepelt, Eaton and Stebila
|
||
|
||
|
||
|
||
|
||
Algorithm 1 Registration(l) Algorithm 3 GetStatic(l)
|
||
1: πl ←
|
||
−
|
||
$
|
||
[N ], skl ←
|
||
−
|
||
$
|
||
{0, 1} κ
|
||
Require: l ≤ L
|
||
2: al , bl ←
|
||
−
|
||
$
|
||
Zp 1: Mark l corrupted; Get stored π l , skl
|
||
3: Bl ← g l , Al ← g l
|
||
b a
|
||
2: for m = 0, . . . , ctrl do
|
||
4: el ← IC1 .E(πl , al , Bl , skl ) 3: for kl,m , cl,m ← ActiveC (l, e, Y )
|
||
5: Store π l , skl , el , Al , bl 4: a, B, sk ← IC1 .D(πl , e)
|
||
5: hX = H1 (l, m, Xl,m ), hY = H1 (l, m, Y )
|
||
Algorithm 2 PassiveExec(l) 6: σC ← (Y ◦ B hY ) )xl,m +hX ·a
|
||
Require: l ≤ L 7: H2 (l, m, Xl,m , Y, σC ) := kl,m,1
|
||
1: Get stored π l , skl , el , Al , bl 8: for kl,2 ← ActiveS (l, c)
|
||
2: Increment ctrl 9: Get stored Yl,m
|
||
3: xl,ctrl , yl,ctrl ←
|
||
−
|
||
$
|
||
Zp 10: X ← IC2 .D(skl , c)
|
||
4: Xl,ctrl ← g l,ctrl , Yl,ctrl ← g l,ctrl 11:
|
||
x y
|
||
hX = H1 (l, m, X), hY = H1 (l, m, Yl,m )
|
||
5: cl,ctrl ← IC2 .E(πl , Xl,ctrl ) 12: σS ← (X ◦ Ahl,m X yl,m +hY ·bl,m
|
||
)
|
||
6: Store Yl,ctrl , ctxtl,ctrl 13: H2 (l, m, X, Yl,m , σS ) := kl,m,2
|
||
7: return el , Yl,ctrl , cl,ctrl 14: return (πl , skl )
|
||
|
||
|
||
|
||
|
||
ActiveS (l, c)), but before querying GetStatic(l) on the instance. The ad-
|
||
versary is then said to win the game. The restriction on the GetStatic oracle
|
||
mimics the fact that forward secrecy cannot be achieved in the quantum annoy-
|
||
ing model. The conditions under which the game outputs 1 are analogous to the
|
||
winning conditions of [7, Sec. 3.1].
|
||
|
||
Theorem 2 (Security of KHAPECORE ). Let qAEC , qAES be the number
|
||
of queries to the Active and qPE the number of queries to the PassiveExec
|
||
oracle. Let qICi , qHi , q◦ , qDlog be the number of queries to the ideal cipher, random
|
||
oracle, group operation and discrete logarithm oracles respectively. Then A’s
|
||
probability to win the KHAPECORE -game is bounded by
|
||
|
||
|
||
1 qAEC + qAES + qDlog
|
||
Pr [KHAPECORE ⇒ 1] ≤ + + ϵCORE (4)
|
||
2 N
|
||
// G0 ⇝ G1 // G3 ⇝ G4
|
||
2 2
|
||
(qIC1 + qIC2 + q◦ ) + (qDlog q◦ ) (qAEC + qAES ) · (q◦ + 1)
|
||
ϵCORE := +
|
||
p p
|
||
2 2 2 (5)
|
||
qPE qPE + qAE (2qIC1 + qIC2 ) (qIC1 ) (2qIC1 + q IC2 ) (qIC1
|
||
)
|
||
+ n1 + n
|
||
+ + κ
|
||
+ + κ
|
||
.
|
||
2 2 2 p 2 p 2
|
||
// G2 ⇝ G3 // G1 ⇝ G2
|
||
|
||
|
||
|
||
3.2 Proof of Theorem 2
|
||
|
||
The proof of Theorem 2 shows, informally, that the adversary’s chance to win
|
||
the KHAPECORE -game is limited by their ability to query the Dlog oracle
|
||
Making an Asymmetric PAKE Quantum-Annoying 13
|
||
|
||
|
||
|
||
|
||
Algorithm 4 ActiveC (l, e, Y ) Algorithm 5 ActiveS (l, c)
|
||
Require: l ≤ L Require: l ≤ L
|
||
1: Increment ctrl ; Get stored πl 1: Increment ctrl ; Get stored skl
|
||
2: a, B, sk ← IC1 .D(πl , e) 2: if challenge s = 0 or l corrupted :
|
||
3: xl,ctrl ←−
|
||
$
|
||
Zp , Xl,ctrl ← g xl,ctrl 3: X ← IC2 .D(skl , c)
|
||
4: cl,ctrl ← IC2 .E(sk, Xl,ctrl ) 4: hX = H1 (l, ctrl , X), hY =
|
||
5: if challenge s = 0 or l corrupted : H1 (l, ctrl , Yl,ctrl )
|
||
6: hX = H1 (l, ctrl , Xl,ctrl ), hY = 5: σC ← (X ◦ Ahl X )yl,ctrl +hY ·bl,ctrl
|
||
H1 (l, ctrl , Y ) 6: kl,ctrl ,2 = H2 (l, ctrl , X, Yl,ctrl , σl,C )
|
||
7: σC ← (Y ◦ B hY ) )xl,ctrl +hX ·a 7: else kl,ctrl ,2 ← {0, 1}
|
||
n
|
||
|
||
8: kl,ctrl ,1 = H2 (l, ctrl , Xl,ctrl , Y, σC ) 8: return kl,ctrl ,2
|
||
n
|
||
9: else kl,ctrl ,1 ← {0, 1}
|
||
10: return kl,ctrl ,1 , cl,ctrl
|
||
|
||
|
||
|
||
|
||
on the correct group element, or any of the Active oracles on a ciphertext
|
||
encoding a group element the discrete logarithm of which is known to them. In
|
||
the KHAPECORE -game, the group elements in question are computed as
|
||
x+hX ·a
|
||
σC = Y · B hY = Y x · Y hx ·a · B hY ·x · B hy ·hx ·a
|
||
= g xy · g hX ·a·y · g hY ·b·x · g hY ·hX ·a·b (6)
|
||
y hX ·y hY ·b hX ·hY ·b hX y+hY ·b
|
||
|
||
=X ·A ·X ·A = X ·A = σS ,
|
||
|
||
where computing σC , σS depends on either the knowledge of Dlog(g, B) or
|
||
Dlog(g, X). The framework presented in Section 2.1, allows us to quantify if
|
||
these element are knowable based on the number of discrete logarithm queries.
|
||
This is possible, because the relevant group elements X, B are encrypted under
|
||
the ideal cipher. On a decryption query the ideal cipher can return a public rep-
|
||
resentations that does not admit a relation to a previously received group element
|
||
known by the adversary. To learn any such relation, the adversary then has to
|
||
query the Dlog oracle. Specifically, the relevant group elements {Bl,i , Xl,i }i∈[N ]
|
||
correspond to decryptions of (e, c) using a password guess πi and ski as keys re-
|
||
spectively. In the KHAPECORE -game, the correct pair Bl,i , Xl,i is chosen during
|
||
the Registration phase and in the Active oracles. Due to the values being en-
|
||
crypted by the ideal ciphers, the simulation does not need to commit to any
|
||
actual pair Bi , Xi .
|
||
We prove this by presenting a sequence of game hops where the the initial
|
||
game G0 (cf. Section 3.2) is the KHAPECORE -game as defined in Section 3.1,
|
||
and G4 (cf. Section 3.2) is modified such that the keys k1 , k2 are chosen uni-
|
||
formly random for every instance, and where the discrete logarithm of g and the
|
||
group elements B, X remain undefined unless sufficiently constrained by queries
|
||
to the Dlog and Active oracles. They are undefined because the ciphertexts
|
||
(e, c) are indistinguishable from random strings, and the key pair (π, sk) is no
|
||
longer defined from the PassiveExec or Active oracles. That means that the
|
||
14 Tiepelt, Eaton and Stebila
|
||
|
||
correct values for (B, X) may correspond to any of the N possible pairs. As long
|
||
as there is a degree of freedom left for these representations, the discrete logar-
|
||
ithm relative to g is also not defined, and the random oracle cannot be queried
|
||
on the respective Diffie–Hellman completion. These are only defined either if
|
||
an instance is corrupted, or if sufficiently many discrete logarithms have been
|
||
queried, allowing to quantify the adversary’s probability to win relative to the
|
||
number of Dlog queries.
|
||
|
||
G0 (KHAPECORE -game). This is the KHAPECORE as described in Section 3.1.
|
||
|
||
G1 (GGM). We modify the responses to the group operation ◦ and Dlog or-
|
||
acle by simulating the generic group as described in Section 2.1. The generator
|
||
initially given to the adversary is g 1 = g, which corresponds to the secret rep-
|
||
resentation 1. The secret representation of the neutral element is 0. Recall that
|
||
the password space is of size N . The secret variables are represented as a set
|
||
{χl,i , χl,i }i∈[N ] corresponding to the pairs Bl,i , Xl,i that can be obtained when
|
||
querying the ideal ciphers on possible values for πl or skl . The ideal cipher ICi is
|
||
maintained via a table TICi . On query IC1 .D(π, e), if TIC1 [π, e] is defined, return
|
||
TIC1 [π, e]. Otherwise, sample a random index j ← −
|
||
$
|
||
[N ] for the secret representa-
|
||
n
|
||
tion and a public representation g V ← − {0, 1} , both of which are added to the
|
||
$
|
||
|
||
|
||
table Tggm [χi,j ] := g V ; The public representation g V is returned. The simulation
|
||
of IC2 is analog.
|
||
The modification changes the distribution of the group elements: public rep-
|
||
resentations returned from the ideal ciphers (on new inputs) in the simulation
|
||
√
|
||
are unique, whereas the adversary would expect a collision after p new quer-
|
||
ies. Additionally, the adversary would expect to see collisions between random
|
||
public representations, and the elements returned from (sufficiently many) group
|
||
operations. This happens with probability (qIC1 + qIC2 + q◦ )2 /p.
|
||
Further, a group element may be assigned two distinct public representations,
|
||
if first computed from group operations and then returned from an IC query (or
|
||
vice versa). For example, if the public representation gx was returned from an
|
||
IC query, and the representation gx̄ = g x was assigned from group operations,
|
||
then the adversary may detect the modification by computing Dlog(g 1 , g x ) = x.
|
||
The probability that this happens for group elements randomly assigned by the
|
||
ideal cipher and for all Dlog queries is qDlog q◦2 /p. Overall, the adversary can
|
||
distinguish the two games with probability at most
|
||
|
||
(qIC1 + qIC2 + q◦ )2 + qDlog q◦2
|
||
. (7)
|
||
p
|
||
|
||
G2 (Ideal Ciphers Output). We change the ideal ciphers to output unique, ran-
|
||
dom values when queried on a new input. On query IC1 .D(π, e), if TIC1 [π, e] is
|
||
not defined, the ideal cipher IC1 samples key pairs a, b ← −$
|
||
Zp and sk ← {0, 1}κ ,
|
||
generates public keys A = g , B = g and a key sk ← {0, 1}κ , and programs
|
||
a b
|
||
|
||
TIC1 [π, e] := a, B, sk. In the case of a collision, i.e., if (a, B, sk) has been as-
|
||
signed to a value in the map TIC1 [π, ·] for any value ·, G2 aborts. Since (a, B, sk)
|
||
Making an Asymmetric PAKE Quantum-Annoying 15
|
||
|
||
are independent random variables, the probability for an abort is bounded by
|
||
2qIC1/p + qIC1/2κ , neglecting the a deduction for a simultaneous collision of all vari-
|
||
|
||
ables. Since the values a, B, sk are unique, two different queries will never output
|
||
the same values, whereas the adversary would eventually expect a collision in
|
||
G1 . The same argument applies to IC2 . In total, the divergence is bounded by
|
||
2 2 2
|
||
2qIC1 + qIC2 (qIC1 ) 2qIC 1
|
||
+ qIC 2
|
||
(qIC 1
|
||
)
|
||
+ κ
|
||
+ + κ
|
||
. (8)
|
||
p 2 p 2
|
||
G3 (Random Ciphertexts). We modify the game to not sample any keys π
|
||
and sk and to output random strings e ← −$
|
||
{0, 1}n1 , c ←
|
||
−
|
||
$
|
||
{0, 1}n2 in the Pass-
|
||
iveExec and ActiveC oracles, which removes the game’s commitment to any
|
||
value stored in (e, c). Analogous to the modification in G2 , the game aborts if
|
||
the values were previously assigned. At the same time the GetStatic oracle is
|
||
changed to reflect the modification: the simulation first decrypts the ciphertext
|
||
using freshly sampled keys π and sk. The Dlog oracle provides the values neces-
|
||
sary to compute the Diffie–Hellman session such that the output of the Active
|
||
oracles can be programmed into the correct position of the ideal cipher. For a
|
||
detailed algorithm of the modified (and “final”) PassiveExec and GetStatic
|
||
oracle we refer the reader to Appendix A1. The distribution of (e, c) returned by
|
||
PassiveExec and ActiveC is the same as in G2 unless it aborts. Since (e, c)
|
||
are sampled uniformly random from the ciphertext space, the probability for
|
||
this to happen is bounded by
|
||
qPE qPE + qAEC
|
||
+ . (9)
|
||
2 n1 2 n2
|
||
G4 (Embed Random Keys). The Active oracles are modified to always return
|
||
random strings k ← −$
|
||
{0, 1}κ for non-corrupted instances. To notice this change,
|
||
the adversary must query H2 (ctr, X, Y, σi ), where the Diffie–Hellman completion
|
||
σi depends on either the knowledge of Dlog(g, X) and B, or the knowledge of
|
||
Dlog(g, B) and X, both of which are not defined by the game unless GetStatic
|
||
has been queried, in which case the adversary cannot win the game anymore.
|
||
The probability that Dlog(g, X) or Dlog(g, B) are knowable to the ad-
|
||
versary is bounded by Corollary 1, which tells us that the discrete logarithms
|
||
are defined if an only if ⃗b, ⃗x are in the row span of D. Both, ⃗b and ⃗x, are basis
|
||
vectors with a 1 at the position of the random index associated with the re-
|
||
spective secret variable. The number of basis vectors that can appear in the row
|
||
span are upper bounded by the rank of the matrix D, which is increased by 1 for
|
||
each Dlog query. Therefore, the probability that the adversary can force the
|
||
definition for any one value out of N many of these is bounded by qDlog/N .
|
||
Remark: Only public representations returned from the ideal ciphers, and
|
||
possibly group elements that come from group operation applied to these group
|
||
elements, provide useful input to the Dlog oracle, since the discrete logarithm
|
||
relation for group elements originating purely from g is already known to the
|
||
adversary. Therefore, the probability is
|
||
min(qIC1 + qIC2 , qDlog ) qDlog
|
||
≤ . (10)
|
||
N N
|
||
16 Tiepelt, Eaton and Stebila
|
||
|
||
Additionally, the adversary may submit a query with a group element, the
|
||
discrete logarithm of which is known to them. The input ê to the ActiveC oracle
|
||
is either a value formerly returned from a previous query to PassiveExec, in
|
||
which case the adversary must also query the ideal cipher and the Dlog oracle
|
||
and there is a chance of (q◦ +1)/p that the discrete logarithm of the group element
|
||
decrypted by ActiveC is known to them. If ê was crafted by the adversary, i.e.,
|
||
ˆ such that the discrete logarithm
|
||
if they queried the ideal cipher on values â, B̂, sk
|
||
of B̂ is known to them, then they expect an /N chance that there choice of pw
|
||
1 ˆ
|
||
was correct, and that ActiveC used b̂ to compute the Diffie–Hellman session.
|
||
In total, this result in a divergence for ActiveC queries bounded by
|
||
qAEC · (q◦ + 1) qAEC
|
||
+ . (11)
|
||
p N
|
||
For ActiveS , the adversary may submit a value cˆx for which the same arguments
|
||
hold, resulting in a total probability for either of both occurring of
|
||
|
||
(qAEC + qAES ) · (q◦ + 1) qAEC + qAES
|
||
+ . (12)
|
||
p N
|
||
Finally, the adversary’s advantage to distinguish the simulation from the real
|
||
game based on Dlog queries depends on the knowledge of at least one key from
|
||
a Active oracle, resulting in a factor of min(qAEC + qAES , 1), thus bounding the
|
||
overall divergence by
|
||
|
||
min(qAEC + qAES , 1)·
|
||
!
|
||
(qAEC + qAES ) · (q◦ + 1) qAEC + qAES + min(qIC1 + qIC2 , qDlog ) (13)
|
||
+
|
||
p N
|
||
|
||
(qAEC + qAES ) · (q◦ + 1) qAEC + qAES + qDlog
|
||
≤ + (14)
|
||
p N
|
||
.
|
||
In G4 , the PassiveExec and ActiveC oracle output random values as
|
||
ciphertexts e, c that do not commit to any values a, B, π or X. Particularly,
|
||
the values Dlog(g, X), Dlog(g, B) are defined only upon corruption or after a
|
||
number of Active and Dlog queries relative to the password space N . The
|
||
Active∗ oracles further output a random key independent of the challenge bit
|
||
s = 0. The adversary is left with either guessing the challenge bit, or querying
|
||
values to H2 . This concludes the proof of Theorem 2. ⊔
|
||
⊓
|
||
|
||
|
||
4 aPAKE Security: Sketch of Proof of Theorem 1
|
||
The security of the QA-KHAPE protocol (cf. Figure 1) is proven in the QA-BPR
|
||
(cf. Section 2.2) model. Recall that the adversary may interact through the
|
||
Execute, Send, Reveal, Corrupt and Test oracles after the Registration
|
||
phase, where the protocol defines how the principals respond. Additionally, the
|
||
Making an Asymmetric PAKE Quantum-Annoying 17
|
||
|
||
adversary has access to the group operation, Dlog and random oracle, ideal
|
||
cipher and pseudo-random function prf , as described in Section 2.1, and is
|
||
bounded by Theorem 1. In this section we offer a summary of the proof’s main
|
||
ideas and provide a complete description in Appendix A2.
|
||
We consider a sequence of games starting with G0 , which corresponds to the
|
||
QA-KHAPE protocol illustrated in Figure 1. As we progress to G3 , the sessions
|
||
keys are chosen independent and uniformly at random, ensuring that the ad-
|
||
versary A is reduced to a simple guessing attack. Throughout this reduction
|
||
process, we present a an adversary B on the KHAPECORE -game, which main-
|
||
tains a mapping between instances of the KHAPECORE -game and instances of
|
||
principals in the QA-BPR-model. To achieve this, we utilize a procedure called
|
||
CoreMap, which bears resemblance to the getUV procedure described in [7,
|
||
App. B.2] (cf. Appendix A1 for further details). Intuitively, two counters ctrC,S
|
||
and ctrC,S,sid , are employed to either map to a set of static variables indexed by
|
||
l or to an instance ctrl in the KHAPECORE -game. The oracles provided by the
|
||
KHAPECORE challenger are referred to as KHAPECORE .Oracle.
|
||
In the sequence of games, the first modification occurs in G1 , where we re-
|
||
place the keys k1 , k2 in the Execute oracle with random strings. This change is
|
||
reflected in the Corrupt oracle, which now programs the random string instead
|
||
of the actual keys into the random oracle. The distinction between G0 and G1 can
|
||
be reduced to an attacker on the KHAPECORE -game. To differentiate between
|
||
these two games, we can provide an extractor for a winning query: utilizing
|
||
the CoreMap, the calls to the Execute and Send oracles can be forwarded
|
||
to the KHAPECORE .PassiveExec, which returns (eC,S,sid , YC,S,sid , cC,S,sid ),
|
||
These outputs can be queries to KHAPECORE .Active∗ , which provides
|
||
(cC,S,sid , k C,S,1 ) or k C,S,2 . Using from these keys, the confirmation values (τ, γ)
|
||
that genuinely follow the protocol are computed.
|
||
In the modified game, all calls to the ideal cipher are simulated perfectly by
|
||
forwarding queries to, and responses from, the KHAPECORE -game. However,
|
||
queries to the random oracle are not simulated perfectly, because the adversary
|
||
can submit a query not associated with an instance in the KHAPECORE , and that
|
||
gets mapped to different value in the KHAPECORE -game later on. Nonetheless,
|
||
in every call to H2 in the KHAPECORE , either the group element X or Y is
|
||
chosen uniformly at random from the group, ensuring that the the adversary’s
|
||
probability of querying the same group element beforehand is at most qH2/p.
|
||
The Test queries in G1 are simulated perfectly, since the keys are chosen uni-
|
||
formly at random, ensuring that the key confirmation values follow the expected
|
||
distribution. In the non-Test queries, as the KHAPECORE instances are real-
|
||
or-random based on the respective challenge bit. Specifically, the keys (k1 , k2 )
|
||
are real-or-random values. However, the adversary can only detect this if they
|
||
can query the random oracle H2 for the position of the programmed random
|
||
keys. Such a query would immediately be a winning query in the KHAPECORE -
|
||
game. Therefore, the adversary’s ability to distinguish between the two games
|
||
can be limited by their capability to win the KHAPECORE -game, which can be
|
||
quantified relative to the number of Dlog queries they submit.
|
||
18 Tiepelt, Eaton and Stebila
|
||
|
||
In game G2 , the modification is extended to the active queries (i.e., Send).
|
||
The extractor for the KHAPECORE -game acts nearly identical. The only differ-
|
||
ence is that the quantification of KHAPECORE advantage is now also impacted
|
||
by the adversary’s ability to query ciphertexts (e, c), the discrete logarithm of the
|
||
decryption of which is knowable to them. This adds an additional term for the
|
||
number of Send queries. The probability to detect the modifications from the
|
||
non-Test queries in game G1 and G2 result in the term (qDlog +qSend )/N + ϵCORE .
|
||
The last modification occurs in game G3 , where we exchange the sessions keys
|
||
with random values. Since the keys (k1 , k2 ) are already random strings, and the
|
||
session key is the output of the prf, this can be reduced to the adversary’s ability
|
||
to distinguish prf from a random function, i.e., ϵprf . This adds an additional
|
||
divergence of (qExecute + qSend )ϵprf and concludes the proof.
|
||
|
||
Acknowledgements M.T. was supported by funding from the topic Engin-
|
||
eering Secure Systems of the Helmholtz Association (HGF) and by KASTEL
|
||
Security Research Labs. D.S. was supported by Natural Sciences and Engineer-
|
||
ing Research Council of Canada (NSERC) Discovery grant RGPIN-2022-03187
|
||
and NSERC Alliance grant ALLRP 578463-22.
|
||
|
||
|
||
References
|
||
1. IEEE standard specification for password-based public-key cryptographic tech-
|
||
niques. IEEE Std 1363.2-2008 (2009). https://doi.org/10.1109/IEEESTD.2009.
|
||
4773330
|
||
2. Information technology — personal identification — ISO-compliant driving licence.
|
||
ISO/IEC 18013-3:2027 (2017)
|
||
3. Abdalla, M., Haase, B., Hesse, J.: Security analysis of CPace. In: Tibouchi, M.,
|
||
Wang, H. (eds.) ASIACRYPT 2021, Part IV. LNCS, vol. 13093, pp. 711–741.
|
||
Springer, Heidelberg (Dec 2021). https://doi.org/10.1007/978-3-030-92068-5_24
|
||
4. Beguinet, H., Chevalier, C., Pointcheval, D., Ricosset, T., Rossi, M.: Get a cake:
|
||
Generic transformations from key encaspulation mechanisms to password authen-
|
||
ticated key exchanges. In: Applied Cryptography and Network Security: 21st Inter-
|
||
national Conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023, Proceedings,
|
||
Part II. p. 516–538. Springer-Verlag, Berlin, Heidelberg (2023). https://doi.org/
|
||
10.1007/978-3-031-33491-7_19, https://doi.org/10.1007/978-3-031-33491-7_19
|
||
5. Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure
|
||
against dictionary attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS,
|
||
vol. 1807, pp. 139–155. Springer, Heidelberg (May 2000). https://doi.org/10.1007/
|
||
3-540-45539-6_11
|
||
6. Bourdrez, D., Krawczyk, D.H., Lewi, K., Wood, C.A.: The OPAQUE Asymmet-
|
||
ric PAKE Protocol. Internet-Draft draft-irtf-cfrg-opaque-10, Internet Engineering
|
||
Task Force (Mar 2023), https://datatracker.ietf.org/doc/draft-irtf-cfrg-opaque/
|
||
10/
|
||
7. Eaton, E., Stebila, D.: The “quantum annoying” property of password-
|
||
authenticated key exchange protocols. In: Cheon, J.H., Tillich, J.P. (eds.) Post-
|
||
Quantum Cryptography - 12th International Workshop, PQCrypto 2021. pp. 154–
|
||
173. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-81293-5_9
|
||
Making an Asymmetric PAKE Quantum-Annoying 19
|
||
|
||
8. Gheorghiu, V., Mosca, M.: Benchmarking the quantum cryptanalysis of symmetric,
|
||
public-key and hash-based cryptographic schemes. arXiv:1902.02332 (2019)
|
||
|
||
9. Gidney, C., Ekerå, M.: How to factor 2048 bit RSA integers in 8 hours us-
|
||
ing 20 million noisy qubits. Quantum 5, 433 (2021). https://doi.org/10.22331/
|
||
q-2021-04-15-433, https://doi.org/10.22331/q-2021-04-15-433
|
||
|
||
10. Gu, Y., Jarecki, S., Krawczyk, H.: KHAPE: Asymmetric PAKE from key-hiding
|
||
key exchange. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part IV. LNCS,
|
||
vol. 12828, pp. 701–730. Springer, Heidelberg, Virtual Event (Aug 2021). https:
|
||
//doi.org/10.1007/978-3-030-84259-8_24
|
||
|
||
11. Hao, F., van Oorschot, P.C.: Sok: Password-authenticated key exchange – theory,
|
||
practice, standardization and real-world lessons. In: Proceedings of the 2022 ACM
|
||
on Asia Conference on Computer and Communications Security. p. 697–711. ASIA
|
||
CCS ’22, Association for Computing Machinery, New York, NY, USA (2022). https:
|
||
//doi.org/10.1145/3488932.3523256, https://doi.org/10.1145/3488932.3523256
|
||
|
||
12. Hhan, M., Yamakawa, T., Yun, A.: Quantum complexity for discrete logarithms
|
||
and related problems. Cryptology ePrint Archive, Paper 2023/1054 (2023), https:
|
||
//eprint.iacr.org/2023/1054, https://eprint.iacr.org/2023/1054
|
||
|
||
13. Jarecki, S., Krawczyk, H., Xu, J.: OPAQUE: An asymmetric PAKE protocol se-
|
||
cure against pre-computation attacks. In: Nielsen, J.B., Rijmen, V. (eds.) EURO-
|
||
CRYPT 2018, Part III. LNCS, vol. 10822, pp. 456–486. Springer, Heidelberg
|
||
(Apr / May 2018). https://doi.org/10.1007/978-3-319-78372-7_15
|
||
|
||
14. Krawczyk, H.: HMQV: A high-performance secure Diffie-Hellman protocol. In:
|
||
Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 546–566. Springer, Heidelberg
|
||
(Aug 2005). https://doi.org/10.1007/11535218_33
|
||
|
||
15. NIST: Nist: Selected algorithm 2022 (2022), https://csrc.nist.gov/Projects/
|
||
post-quantum-cryptography/selected-algorithms-2022
|
||
|
||
16. Parker, E., Vermeer, M.J.D.: Estimating the energy requirements to operate a
|
||
cryptanalytically relevant quantum computer. arXiv:2304.14344 (2023)
|
||
|
||
17. Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.E.: Quantum resource estimates
|
||
for computing elliptic curve discrete logarithms. In: Takagi, T., Peyrin, T. (eds.)
|
||
ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 241–270. Springer, Heidelberg
|
||
(Dec 2017). https://doi.org/10.1007/978-3-319-70697-9_9
|
||
|
||
18. Schmidt, J.M.: Requirements for Password-Authenticated Key Agreement (PAKE)
|
||
Schemes. RFC 8125 (Apr 2017). https://doi.org/10.17487/RFC8125, https://
|
||
www.rfc-editor.org/info/rfc8125
|
||
|
||
19. Taubert, T., Wood, C.A.: SPAKE2+, an Augmented PAKE. Internet-Draft draft-
|
||
bar-cfrg-spake2plus-08, Internet Engineering Task Force (May 2022), https://
|
||
datatracker.ietf.org/doc/draft-bar-cfrg-spake2plus/08/, work in Progress
|
||
|
||
20. Thomas, S.: Re: [Cfrg] proposed PAKE selection process. CFRG
|
||
Mailing List (Jun 2019), https://mailarchive.ietf.org/arch/msg/cfrg/
|
||
dtf91cmavpzT47U3AVxrVGNB5UM/#
|
||
20 Tiepelt, Eaton and Stebila
|
||
|
||
A1 Oracles for Proof of Theorem 2
|
||
|
||
Algorithms 6 to 8 are detailed oracles for the proof of Theorem 2 in Section 3.2.
|
||
|
||
|
||
|
||
Algorithm 6 Sim. of Regis- Algorithm 8 Sim. of GetStatic(l)
|
||
tration(l) Require: l ∈ Z
|
||
1: el ←
|
||
−
|
||
$ n
|
||
{0, 1} 1 1: Mark l corrupted; π l ← [N ], skl ← {0, 1}κ
|
||
2: Store el 2: for m = 0, . . . , ctrl do
|
||
3: for kl,m , cl,m ← ActiveC (l, e, Y )
|
||
4: a, B, sk ← IC1 .D(πl , e)
|
||
5: X ← IC2 .D(sk, cl,m ); x ← Dlog(g, X)
|
||
6: hX = H1 (l, m, X), hY = H1 (l, m, Y )
|
||
Algorithm 7 Sim. of Pass- 7: σl,m,C ← (Y ◦ B hY ) )x+hX ·a
|
||
iveExec(l) 8: H2 (l, m, X, Y, σl,m,C ) := kl,m,1
|
||
9: for kl,2 ← ActiveS (l, c)
|
||
1: Get stored el ; Increment ctrl
|
||
10: X ← IC2 .D(skl , c)
|
||
2: cctr,X ←
|
||
−
|
||
$
|
||
{0, 1}n2
|
||
3: yctr ← Zp , Yctr ← g
|
||
yctr 11: a, B, sk2 ← IC1 .D(πl , el ); b ← Dlog(g, B)
|
||
4: return (Yctr , ectr ), (cctr,X ) 12: hX = H1 (m, l, X), hY = H1 (m, l, Ym,l )
|
||
13: σm,l,C ← (X ◦ AhX )yl +hY ·b
|
||
14: H2 (m, l, X, Ym,l , σm,l,S ) := km,l,2
|
||
15: return (πl , skl )
|
||
|
||
|
||
|
||
|
||
A2 Full Proof of Theorem 1
|
||
|
||
We offer the complete proof of Theorem 1 as a sequence of game hops.
|
||
First, the function CoreMap(C, S, sid) uses the counter ¯l mapping to the
|
||
static variables indexed with l, and ctrl̄ , ctrC,S , ctrC,S,sid corresponding to
|
||
the instances using these static variables. All variables are initialized to zero.
|
||
The CoreMap works as follows: if the ctrC,S,sid > 0, the respective tran-
|
||
script ectrC,S , YctrC,S ,ctrC,S,sid , cctrC,S ,ctrC,S,sid has been generated before and is
|
||
returned. Otherwise, if ctrC,S = 0, then this is the first interaction with
|
||
registrant l. The reduction sets ctrC,S ← ¯l, ctrl̄ ← 1, increments ¯l, cor-
|
||
responding to ctrl in the KHAPECORE , and sets ctrC,S,sid ← 1. The or-
|
||
acle KHAPECORE .PassiveExec(ctrC,S ) is queried; the output stored and
|
||
returned. If ctrC,S > 0, The reduction sets ctrC,S,sid ← ctrl̄ , increments
|
||
ctrl̄ and queries KHAPECORE .PassiveExec(ctrC,S ). The output is stored in
|
||
ectrC,S , YctrC,S ,ctrC,S,sid , cctrC,S ,ctrC,S,sid and returned.
|
||
|
||
G0 (Figure 1). This is the real protocol.
|
||
|
||
G1 (Passive Sessions). The game is modified by replacing the keys k1 , k2
|
||
with random values for passively observed sessions. Particularly, on input
|
||
Making an Asymmetric PAKE Quantum-Annoying 21
|
||
|
||
Execute(C, S, sid), we set k1 = k2 ← {0, 1}κ and compute the key con-
|
||
firmation values τ, γ and sessions keys using the prf . The adversaries or-
|
||
acle calls to all instances l for which Execute has been called are simu-
|
||
lated as follows: First, the simulation invokes CoreMap(C, S, sid) to obtain
|
||
k1 , c′X from KHAPECORE .ActiveC (ctrC,S,sid , e, Y ), is used to compute the
|
||
confirmation values τ, γ. On a Corrupt(C, S) query, the extraction calls
|
||
KHAPECORE .GetStatic(ctrC,S ) returning πl , skl , which programs the key k1
|
||
returned by a KHAPECORE .Active oracle into the correct position of the ran-
|
||
dom oracle H2 . The extraction receives a, B, sk from the ideal cipher on query
|
||
IC1 .D(sk1 , e) as well as the discrete logarithm b from KHAPECORE .Dlog(B).
|
||
It then computes A ← g a . Let P be a table corresponding to all N passwords.
|
||
The extraction sets π ← P[sk1 ], i.e., the sk1 ’th entry of the table and returns
|
||
π, (e, A, b, sk), which is a perfect simulation.
|
||
|
||
|
||
For the queries H1 (sid, C, S, ∗), if the entry ctrC,S,sid is defined, the query is
|
||
forwarded to the KHAPECORE -challenger, and the result is returned. Otherwise,
|
||
a random value is sampled uniformly at random from the range of H1 , and a table
|
||
is maintained for consistent responses. H2 (sid, C, S, ∗) is simulated analogous to
|
||
H1 . All queries to IC1 and IC2 are forwarded to the KHAPECORE -challenger.
|
||
In Section 4 the divergence qH2/p from this simulation, i.e., the random oracle
|
||
and ideal cipher queries, has already been discussed.
|
||
|
||
|
||
Finally, the adversary may query a Test or Reveal query, receiving the
|
||
session key from the KHAPECORE -game, In the first case, if a Test query has
|
||
been received, extraction either simulates either G0 , if the KHAPECORE chal-
|
||
lenge bit is zero, or G1 , if the KHAPECORE challenge bit s is one. When s = 0,
|
||
the values of e, cX as well as τ, γ are distributed as expected (i.e., as in G0 ),
|
||
since the keys k1 = k 2 are identical and thus γ can also be computed from k 1 .
|
||
On the other hand, if s = 1, the key k1 is chosen uniformly random as expected,
|
||
and thus the key confirmation values also have the expected distribution.
|
||
In the second case, if a Reveal query has been received, key k1 returned
|
||
from the simulation is real-or-random, but would be expected to always be real,
|
||
resulting in a divergence. However, from an adversary detecting this change
|
||
an extraction of a winning query to the KHAPECORE can be provided: In or-
|
||
der to notice the change, the adversary A has to query the random oracle on
|
||
H2 (sid, C, S, X, Y, σC ) or H2 (sid, C, S, X, Y, σS ), both of which allow to instantly
|
||
win the KHAPECORE -game. Note that the key confirmation values returned by
|
||
the aPAKE impact the advantage to win the KHAPECORE , since even a passive
|
||
execution allows to verify if a derived session key is correct. Therefore, the term
|
||
min(qAEC + qAES , 1) is 1. Further, the inputs to CoreMap.Active∗ are sampled
|
||
in KHAPECORE .PassiveExec such that no new group elements, the discrete
|
||
logarithm of which is knowable to the adversary, have to be considered in the
|
||
probability to win the KHAPECORE -game. Consequently, the number of these
|
||
queries is exactly the number of Execute queries. The probability to detect the
|
||
22 Tiepelt, Eaton and Stebila
|
||
|
||
difference between game G0 and G1 is then bounded by
|
||
qDlog qH
|
||
+ ϵpassiv + 2 (15)
|
||
N p
|
||
2 2
|
||
(qIC1 + qIC2 + q◦ )2 + (qDlog q◦2 ) qIC 1
|
||
+ qExecute qIC 2
|
||
+ qExecute
|
||
ϵpassiv := + n
|
||
+ . (16)
|
||
p 2 1 2 n2
|
||
|
||
G2 (Active Sessions). In G2 , the modifications(i.e., replacing k1 , k2 with random
|
||
strings), are extended to active sessions:
|
||
For an active session impersonating a client C, the oracle calls are mod-
|
||
ified as follows: On input Send(C, l, M = (S, sid)) the simulation responds
|
||
with the values e, Y retrieved from KHAPECORE .PassiveExec. On input
|
||
Send(C, l, M = (S, sid, cX , τ )) we sample the k 2 ← {0, 1}κ uniformly at ran-
|
||
dom and computes τ ′ ← prf(k2 , 1). The session key and the key confirmation
|
||
value are generated from k1 , k2 based on τ = τ ′ as in an genuine execution of
|
||
the protocol.
|
||
For an active session impersonating a server S, the oracle calls are modified
|
||
as follows: On input Send(C, l, M = (S, sid, e, Y )) the simulation samples a uni-
|
||
formly random value for k 1 ← {0, 1}κ and computes the key confirmation value
|
||
τ using the prf. On input Send(C, l, M = (S, sid, γ)) we compute γ ′ ← prf(k1 , 2)
|
||
and set the session key conditionally on the outcome of γ = γ ′ (i.e., as in the real
|
||
protocol). On queries to the random oracle, ideal cipher, Reveal and Corrupt
|
||
the reduction behaves identical to G1 , and thus the divergence is identical.
|
||
Eventually, the adversary may query a Test or Reveal query receiving a ses-
|
||
sion key from the KHAPECORE . To bound the adversaries chance to detect the
|
||
modification, a similar extractor of a winning query to the KHAPECORE -game
|
||
is provided. Similarly to Appendix A2, the reduction calls CoreMap to map
|
||
instances of the QA-BPR-game to instances of the KHAPECORE -game. The ex-
|
||
traction of a winning query on the adversary Send queries to clients and servers
|
||
is examined separately.
|
||
Impersonation of clients: On Send(C, l, M = (S, sid)) the extraction calls
|
||
CoreMap(C, S, sid), which causes ctrC,S to become defined if it previously
|
||
was not, and the retrieved values e, Y are returned. On Send(C, i, M =
|
||
(S, sid, cX , τ )) the reduction calls CoreMap(C, S, sid) to subsequently obtain
|
||
k2 ← KHAPECORE .Active(ctrC,S , cX ). The key confirmation value τ ′ is com-
|
||
puted from the obtained key using the prf . The session key and key confirmation
|
||
value are set conditioned on τ = τ ′ as in the real protocol.
|
||
Impersonation of Server : On Send(S, i, M = (C, sid, j, e, Y )), the reduction
|
||
calls CoreMap(C, S, sid), which causes ctrC,S to become defined it it previously
|
||
was not. Then the reduction calls k1 ← KHAPECORE .Active(ctrC,S , e, Y ) and
|
||
computes the key confirmation value τ genuinely using the prf , and returns
|
||
cX , τ . On Send(S, i, M = (C, j, γ, sid)), the reduction computes γ ′ from the
|
||
key k2 using the prf and compares this to γ. If they match, the session key
|
||
is set to K1 ← prf(k1 , 0), and otherwise, to ⊥. For Send the arguments are
|
||
analogous to G1 : If Test was queried, the reduction simulates G1 (and thus
|
||
G0 ) perfectly if the KHAPECORE challenge bit s = 0, and simulates G2 if s =
|
||
Making an Asymmetric PAKE Quantum-Annoying 23
|
||
|
||
1(except for inconsistencies in the random oracle). Otherwise, the adversary
|
||
can detect the change only by querying the random oracle on either of the
|
||
two inputs H2 (sid, C, S, X, Y, σC ) or H2 (sid, C, S, X, Y, σS ), both of which are
|
||
winning queries for the reduction in KHAPECORE .
|
||
The number of Active queries for which the adversary may choose the input
|
||
is bounded by the number of Send queries, bounding the difference between
|
||
game G1 and G2 by
|
||
(qDlog + qSend ) qH
|
||
+ ϵactiv + 2 (17)
|
||
N p
|
||
with
|
||
2 2
|
||
(qIC1 + qIC2 + q◦ )2 + (qDlog q◦2 ) qIC 1
|
||
+ qSend qIC 2
|
||
+ qSend
|
||
ϵactiv := + + (18)
|
||
p 2n1 2n2
|
||
.
|
||
|
||
G3 (Random Sessions Keys). The final modification in G3 (i.e., replacing the
|
||
session keys with random strings) was discussed in Section 4, resulting in the
|
||
term (qExec + qSend )ϵprf . The sessions keys are now uniformly random and inde-
|
||
pendent of the password and credentials leaving adversary to a guessing attack.
|
||
The probability that the adversary can distinguish G0 from G3 is bounded
|
||
by
|
||
(qDlog + qSend ) qH2
|
||
+ + (qExec + qSend )ϵprf + ϵ , (19)
|
||
N p
|
||
with
|
||
2 2
|
||
(qIC1 + qIC2 + q◦ )2 + (qDlog q◦2 ) (qIC + qSend + qExec ) (qIC + qSend + qExec )
|
||
ϵ≤ + 1
|
||
+ 2
|
||
.
|
||
p 2n1 2 n2
|
||
(20)
|
||
This conclude the proof. ⊔
|
||
⊓
|
||
|