# Provably-Secure (Chinese Government) SM2 and Simplified SM2 Key Exchange Protocols

Authors: Ang Yang; Junghyun Nam; Moonseong Kim; Kim-Kwang Raymond Choo
Journal: The Scientific World Journal
 (2014)

---

## Abstract

We revisit the SM2 protocol, which is widely used in Chinese
commercial applications and by Chinese government agencies. Although
it is by now standard practice for protocol designers to provide security
proofs in widely accepted security models in order to assure protocol implementers
of their security properties, the SM2 protocol does not have
a proof of security. In this paper, we prove the security of the SM2 protocol
in the widely accepted indistinguishability-based Bellare-Rogaway
model under the elliptic curve discrete logarithm problem (ECDLP)
assumption. We also present a simplified and more efficient version of
the SM2 protocol with an accompanying security proof.


---

## Body

## 1. Introduction

Due to the potential of elliptic curve cryptography (ECC) to offer similar security to established public-key cryptosystems at reduced key sizes, it has become a subject of research focus. For example, we observe an emerging trend in the use of identity-based (ID-based) cryptography, such as ID-based key agreement protocols using pairings. The latter include ID-based authenticated key agreement (ID-AKA) protocol. ID-AKA protocols (as well as other key establishment protocols such as [1–4]) allow a shared secret key to be established between two or more parties for subsequent cryptographic use. The first two-party ID-AKA protocol was proposed by Shamir, which is based on Weil Pairing [5]. Shamir’s protocol requires a trusted key generation center (KGC). Challenges associated with KGC are well documented, and Alriyami and Paterson proposed the first certificateless two-party authenticated key agreement (CTAKA) protocol that does not require a KGC [6]. Since then, a number of CTAKA protocols have been proposed in the literature [7–9]. Most of these CTAKA protocols are, however, based on bilinear pairings. The latter is expensive, especially in comparison to RSA algorithm [10, 11].A number of recently published certificateless ECC-based AKA protocols that do not require the use of pairings have been proposed. For example, in 2007, Zhu et al. proposed a pairing-free ID-AKA protocol [12]. However, the combination of a pairing-free ID-based signature scheme with the Diffie-Hellman key exchange in the proposed protocol results in larger computation complexity and message size. In addition, the protocol and the ECC-based pairing-free ID-AKA protocol of Cao et al. [13] require three rounds of message exchanges. Another later protocol of Cao et al. reduces the minimum message exchange rounds to two and the protocol was proven secure in the Bellare-Rogaway model [10]. He et al. also independently proposed a two-round certificateless ID-AKA protocol without the use of pairings [14] and a three-round certificateless ID-AKA protocol without the use of pairings [2], respectively.In 2011, the Chinese government published an ECC-based key exchange protocol, SM2 [15]. According to the official report from the Chinese Government State Cryptography Administration and various media releases, SM2 protocol is mandatory in various cryptographic applications used by Chinese government agencies from 1st July, 2011 [16–18]. A 2005 survey by Boyd and Choo revealed that the purported security of several published ID-based protocols is based on heurstic security arguments. A number of protocols were also found to be proven secure in a restricted model. This study highlighted the need for more rigorously tested identity-based protocols [19]. Surprisingly, we observed that despite the wide usage of the SM2 protocol among Chinese commercial applications/electronics, it does not have a security proof.A protocol’s goal is defined as the properties that the protocol aims to achieve. As Boyd and Mathuria suggested, any attack on a protocol is only valid if it violates some property that the protocol was intended to achieve [20]. Without identifying at an early stage the properties and/or goals that a protocol offers, one can debate the validity of attacks against a published protocol since it may not be clear whether the protocol is not intended to provide assurances against the properties being exploited [21]. This reinforced the importance of having a security proof for protocols, particularly those that are widely used by government agencies and in the private sector.Our contributions in this paper are two-fold.(1)
We prove the SM2 protocol secure in the widely accepted indistinguishability-based model of Bellare and Rogaway under the ECDLP assumption.
(2)
We propose a simplified version of SM2 protocol that is more efficient, and prove it secure in the Bellare-Rogaway model under the ECDLP assumption.In the next section, we will briefly review the model that we work in. We revisit the SM2 protocol and prove it secure in Section3. Section 4 describes our simplified SM2 protocol and its proof of security. Finally, the last section concludes the paper.


## 2. Overview of the Bellare-Rogaway Model

In the Bellare-Rogaway model [22, 23], the adversary (denoted by A) controls the communication channel by interacting with a set of Π
U
1
,
U
2
i oracles. Π
U
1
,
U
2
i is defined to be the ith instantiation of a protocol participant, U
1 in a specific protocol run and U
2 is the other protocol participant, with whom U
1 wishes to establish a secret key. The predefined oracle queries are described informally as follows.(i)
TheSend
(
U
1
,
U
2
,
i
,
m
) query allows A to send a message m to another protocol participant at will. In other words,
(a)
Π
U
1
,
U
2
i, upon receiving the query, will compute what the protocol specification demands. The response message and/or decision will then be sent to A,
(b)
ifΠ
U
1
,
U
2
i has either accepted with some session key or terminated, this will be made known to A.
(ii)
TheReveal
(
U
,
i
) query allows A to expose a previously accepted session key. In other words, U
i, upon receiving this query and if it has accepted and holds some session key, will send this session key back to A.
(iii)
TheCorrupt
(
U
) query allows A to learn the complete internal state of U. This models the real world scenario of a corrupted insider.
(iv)
TheTest
(
U
1
,
U
2
,
i
) query is the only oracle query that does not correspond to any of A’s abilities. If Π
U
1
,
U
2
i has accepted with some session key and is being asked aTest
(
U
1
,
U
2
,
i
) query; then depending on a randomly chosen bit b, A is given either the actual session key or a session key drawn randomly from the session key distribution.Definition 1 (Definition of Partnership).
Let us denoteΠ
A
,
B
i and Π
B
,
A
j as two oracles in the protocol run. These two oracles are considered partners if and only if(i)
bothΠ
A
,
B
i and Π
B
,
A
j have accepted the same session key,
(ii)
onlyΠ
A
,
B
i and Π
B
,
A
j (i.e., no other oracle) have accepted with the same session ID (i.e., SID, which is defined to be the concatenation of the message flows) and agreed on the same set of principals (i.e., the initiator and the responder of the protocol).Definition 2 (Definition of Freshness).
OracleΠ
A
,
B
i holds a fresh session key at the end of execution, if and only if all the following conditions are satisfied: (i)
Π
A
,
B
i has accepted with, or without, a partner oracle Π
B
,
A
j,
(ii)
Π
A
,
B
i and Π
B
,
A
j (if such a partner oracle exists) has/have not been sent a Reveal  query,
(iii)
bothA and B (if such a partner exists) has/have not been sent a Corrupt  query.The definition of security depends on the notions of partnership as outlined in Definition1 and freshness as outlined in Definition 2 and is defined using the game G and played between A and a collection of Π
U
x
,
U
y
i oracles for players U
x
,
U
y
∈
{
U
1
,
…
,
U
N
p
} and instances i
∈
{
1
,
…
,
N
s
}. A runs the game simulation G, whose setting is as follows.(i)
Send,  Reveal,   andCorrupt  oracle queries are sent by A in any order at will.
(ii)
A chooses a fresh session on which to be tested by sending a Test  query to the fresh oracle associated with the test session at some point during G. This chosen test session must be fresh (in the sense of Definition 2). Depending on a randomly chosen bit b, A is given either the actual session key or a session key drawn randomly from the session key distribution.
(iii)
A continues making any Send, Reveal,   and Corrupt  oracle queries of its choice.
(iv)
A will eventually terminate G and outputs its guess of the value of b, denoted as b
′.We measureA’s success in G in terms of A’s advantage in distinguishing whether A receives the real key or a random value (i.e., whether b
′
=
b).Letk be a security parameter. Then, the advantage function of A is denoted byAdv
A
(
k
), where
(1)
A
d
v
A
(
k
)
=
2
×
P
r
[
b
′
=
b
]
-
1
.Definition 3 (Definition of Security).
A protocol is secure in the Bellare-Rogaway model if both the following requirements are satisfied.(1)
Two oracles accept the same key when the protocol is run in the absence of a malicious adversary.
(2)
For all probabilistic, polynomial-time (PPT) adversariesA, Adv
A
(
k
) is negligible.


## 3. A Provably-Secure SM2 Key Exchange Protocol

### 3.1. SM2 Key Exchange Protocol

The notations used in SM2 protocol (Table1) are as follows:(i)
A, B: two SM2 protocol participants with identities ID
A and ID
B respectively,
(ii)
a, b: a, b
∈
f
q: the parameters of the elliptic curve E on F
q where elliptic function is y
2
=
x
3
+
a
x
+
b,
(iii)
F
q: the prime field F includes q elements,
(iv)
E
(
F
q
): the set of all points on the elliptic curve E defined over F
q,
(v)
G: the base point of elliptic curve, order of G is prime number that G
=
(
x
G
,
y
G
),
(vi)
h: cofactor, h
=
#
E
(
F
q
)
/
n, n is the order of G,
(vii)
D: the space of number that D
=
[
1
,
n
-
1
],
(viii)
(
d
,
P
): long-term private and public key pair,
(ix)
K: session key,
(x)
ID: identification of client,
(xi)
Z: hash value of identification, the length of Z is e
n
t
l
e
n
A bits,
(xii)
H
v
(
): one-way hash function,
(xiii)
(
r
,
R
): temporary private and public key pair,
(xiv)
k
l
e
n and e
n
t
l
e
n: the bit length of the key and ID, respectively,
(xv)
KDF
(
Z
,
k
l
e
n
): the one-way key derivation hash function whose output length is k
l
e
n,
(xvi)
x
∥
y: concatenation of two strings x and y,
(xvii)
⊥: there is no message or the value is not known.Table 1
SM2 key exchange protocol.
A
B
d
A
,
E
(
F
q
)
,
G
,
n
,
Z
A
,
Z
B
,
P
A
,
P
B
,
H
(
)
,
KDF
(
)
,
G
d
B
,
E
(
F
q
)
,
G
,
n
,
Z
A
,
Z
B
,
P
A
,
P
B
,
H
(
)
,
KDF
(
)
,
G
Randomly selectsr
A
∈
[
1
,
n
-
1
]
Randomly selectsr
B
∈
[
1
,
n
-
1
]
ComputesR
A
=
[
r
A
]
G
=
(
x
1
,
y
1
)
ComputesR
B
=
[
r
B
]
G
=
(
x
2
,
y
2
)
Computesx
1
¯
=
2
w
+
(
x
1
&
(
2
w
-
1
)
)
Computesx
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
)
Computest
A
=
(
d
A
+
x
1
¯
·
r
A
)
mod
⁡
n
Computest
B
=
(
d
B
+
x
2
¯
·
r
B
)
mod
⁡
n
→
R
A
Computesx
1
¯
=
2
w
+
(
x
1
&
(
2
w
-
1
)
)
ComputesV
=
[
h
·
t
B
]
(
P
A
+
[
x
1
¯
]
R
A
)
=
(
x
V
,
y
V
)
ComputesK
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
klen
)
ComputesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
←
R
B
,
S
B
Computesx
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
)
ComputesU
=
[
h
·
t
A
]
(
P
B
+
[
x
2
¯
]
R
B
)
=
(
x
U
,
y
U
)
ComputesK
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B
,
klen
)
ComputesS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
VerifiesS
1
=
?
S
B
ComputesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
→
S
A
ComputesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
VerifiesS
2
=
?
S
A
Key establishedK
A
=
K
B
Key establishedK
B
=
K
A
SID is (R
A
∥
R
B) or (R
A
∥
R
B
∥
S
B
∥
S
A) in the case where key confirmation is required.A randomly selects d
A
∈
[
1
,
n
-
1
] and computes P
A
=
[
d
A
]
G
=
(
x
A
,
y
A
), prior to sending P
A to B. B will also randomly select d
B
∈
[
1
,
n
-
1
] and compute P
B
=
[
d
B
]
G
=
(
x
B
,
y
B
), before sending P
B to A. The public parameters are (
E
(
F
q
)
,
G
,
n
,
Z
A
,
Z
B
,
P
A
,
P
B
). And Z
A and Z
B are hash values of the identification of A and B, respectively, where Z
A
=
H
(
E
N
T
L
A
∥
ID
A
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
A
∥
y
A
) and Z
B
=
H
(
E
N
T
L
B
∥
ID
B
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
B
∥
y
B
). To establish a session key with client B,(1)
clientA will now run the protocol as follows:
(a)
randomly selectsr
A
∈
[
1
,
n
-
1
],
(b)
computesR
A
=
[
r
A
]
G
=
(
x
1
,
y
1
) and x
1
¯
=
2
w
+
(
x
1
&
(
2
w
-
1
)
) where w
=
⌈
(
⌈
log
⁡
2
(
n
)
⌉
/
2
)
⌉
-
1,
(c)
computest
A
=
(
d
A
+
x
1
¯
·
r
A
)
mod
⁡
n,
(d)
sendsR
A to client B;
(2)
upon receiving the messageR
A from client A, B will perform the following:
(a)
randomly selectsr
B
∈
[
1
,
n
-
1
],
(b)
computesR
B
=
[
r
B
]
G
=
(
x
2
,
y
2
), x
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
), t
B
=
(
d
B
+
x
2
¯
·
r
B
)
mod
⁡
n, V
=
[
h
·
t
B
]
(
P
A
+
[
x
1
¯
]
R
A
)
=
(
x
V
,
y
V
) and K
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
k
l
e
n
),
(c)
(optional for key confirmation) computesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(d)
SendsR
B to client A (optional for key confirmation, B will also send S
B to A);
(3)
upon receiving the messages,R
B (and S
B), from B, client A will perform the following:
(a)
computesx
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
), U
=
[
h
·
t
A
]
(
P
B
+
[
x
2
¯
]
R
B
)
=
(
x
U
,
y
U
) and K
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B
,
k
l
e
n
),
(b)
(optional for key confirmation) computesS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(c)
verifiesS
1
=
?
S
B, and if it returns true then A is assured that B actually has possession of the session key, otherwise, terminates the protocol run and outputs ⊥,
(i)
(optional for key confirmation, computesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)),
(ii)
SendsS
A to client B;
(4)
(optional for key confirmation) upon receiving the message (S
A) from client A, client B will perform the following:
(a)
computesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(b)
verifies whetherS
A
=
?
S
2,
(c)
if the verification returns wrong, then clientB terminates the protocol run and outputs ⊥,
(d)
otherwise, clientB is assured that A actually has possession of the session key;
(5)
session key established isK
A
=
K
B,
(6)
SID is(
R
A
∥
R
B
) or (
R
A
∥
R
B
∥
S
B
∥
S
A
) in the case where key confirmation is required.


### 3.2. Security Proof

The security of the protocol—see Theorem5—is based on the ECDLP assumption (see Definition 4) in the random oracle model.Definition 4 (ECDLP Assumption).
The ECDLP problem is defined as follows:(2)
Instance:
E
∖
F
p
,
P
,
Q
∈
E
(
F
p
)
Output:
k
∈
N
*
,
k
>
1
such
that
Q
≡
k
P
mod
⁡
p
.
If we can solve the discrete logarithm problem (DLP) [26], then we can also (immediately) solve the ECDLP problem.Theorem 5.
SM2 protocol is secure in the sense of Definition3 when the underlying hash and key derivation schemes are modelled as random oracles and the elliptic curve discrete logarithm problem (ECDLP) assumption is satisfied in E
(
F
q
).The soundness requirement is trivial to verify. We will now concentrate on proving the indistinguishability requirement.In the usual tradition of reductionist proofs, we assume that there exists an adversaryA against the protocol (i.e., A has a nonnegligible advantage, η
(
k
), where k is the security parameter), and we then construct a solver S that makes use of A to solve the ECDLP problem. In other words, S will simulate the view of A by answering allSend,Reveal,Corrupt, andTest queries of A. S will start by randomly selecting two users, I and J, and a session number, i, as the test session. S will also manage two random oracles, H and KDF, in order to answer A’s queries. More specifically when the H oracle is queried, S will check whether the tuple is already in the H-list and output the stored response. Otherwise, S will respond with the appropriate output, H
(
⋯
), and adds the tuple (
H
(
⋯
)
,
U
,
i
) to the H-list. S will answer KDF queries in the same manner.(i)
Send
(
Ω
I
,
Ω
J
,
j
,
m
) queries: for any well-formed Send queries from A, S can trivially answer with the right output as the protocol specification demands. Specifically, S answers the query as follows.
(a)
IfΩ
I = initiator and Ω
J = responder, then the S will output the message m
=
(
R
I
,
Z
I
,
Z
J
,
P
I
,
P
J
).
(b)
Consider the case thatΩ
J = initiator, Ω
I = responder, and message m
=
R
I.
(1)
IfS has rejected the message m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages (
R
J
,
S
J
) to A. Otherwise, S will abort the simulation and output ⊥.
(c)
AssumeΩ
I = initiator, Ω
J = responder, and messages m
=
R
J
,
S
J.
(1)
IfS has rejected the messages m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages S
I to A. Otherwise, S will abort the simulation and output ⊥.
(ii)
Reveal
(
Ω
,
j
) queries: if Ω
j
=
I
i or Ω
j
=
J
i, then S will abort the simulation and fail. Otherwise this query can be answered with the right session key as long as U
j has accepted and neither Ω nor its partner has been corrupted. However, such a session will be rendered unfresh.
(iii)
Corrupt
(
Ω
) queries: this query can be easily answered as per the protocol specifications, unless Ω
=
I or Ω
=
J. In the latter scenario, S will abort the simulation and fail.
(iv)
Test
(
Ω
1
,
Ω
2
,
j
,
m
) queries: if Π
U
1
,
U
2
j
≠
Π
I
,
J
i, then S will abort the simulation and fail. Otherwise, S will check whether Π
Ω
1
,
Ω
2
j has accepted and that the session is fresh. If so, A will be given either the actual session key or a session key drawn randomly from the session key distribution, depending on the randomly chosen bit b.ForA to distinguish whether the value returned is the actual session key or a session key drawn randomly from the session key distribution, A has to determine the correct values of U
=
(
x
U
,
y
U
) or V
=
(
x
V
,
y
V
) to compute the session key (since K
I
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B, k
l
e
n
) and K
J
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B, k
l
e
n
)). For this to happen,(i)
A has to guess the long-term private key d
I and short-term private key r
I in order to compute t
I and hence, the session key K
I. If A is able to successfully guess d
I and r
I via P
I
=
[
d
I
]
G and R
I
=
[
r
I
]
G, then S would be able to use A to solve the ECDLP problem. Let Succ
d
I
E
C
D
L
P and Succ
r
I
E
C
D
L
P denote A’s advantage in computing the correct values of d
I and r
I, respectively, and Succ
A
U denotes the event that A can successfully guess the session key using the computed values of d
I and r
I. So we have
(3)
Pr
⁡
[
Succ
d
I
E
C
D
L
P
]
=
1
|
D
|
;
Pr
⁡
[
Succ
r
I
E
C
D
L
P
]
=
1
|
D
|
,
Pr
⁡
[
Succ
A
U
]
=
Pr
⁡
[
Succ
d
I
E
C
D
L
P
]
·
Pr
⁡
[
Succ
r
I
E
C
D
L
P
]
=
1
|
D
|
2
.
(ii)
A has to guess the correct value of V. Similar to the above, we let Succ
d
J
ECDLP and Succ
r
J
E
C
D
L
P denote A’s advantage in computing the correct value of d
J and r
J, respectively, and Succ
A
V denotes the event that A can successfully guess the session key using the computed values of d
J and r
J. So we have
(4)
Pr
⁡
[
Succ
d
J
E
C
D
L
P
]
=
1
|
D
|
;
Pr
⁡
[
Succ
r
J
E
C
D
L
P
]
=
1
|
D
|
,
Pr
⁡
[
Succ
A
V
]
=
Pr
⁡
[
Succ
d
J
E
C
D
L
P
]
·
Pr
⁡
[
Succ
r
J
E
C
D
L
P
]
=
1
|
D
|
2
.There is, therefore, a negligible advantage of A distinguishing whether the value returned is the actual session key or a session key drawn randomly from the session key distribution. Let q
t and Succ
A
SM
2 denote the number of Test  queries asked and the event that A can correctly distinguish the session key, respectively. We now have
(5)
Pr
⁡
[
Succ
A
SM
2
]
=
(
1
-
Pr
⁡
[
Succ
A
U
¯
]
Pr
⁡
[
Succ
A
V
¯
]
)
·
q
t
=
(
1
-
(
1
-
1
|
D
|
2
)
·
(
1
-
1
|
D
|
2
)
)
·
q
t
=
2
q
t
|
D
|
2
-
q
t
|
D
|
4
.SinceD
=
[
1
,
n
-
1
], n
→
∞, D
→
∞, 1
/
|
D
|
2
→
0, 1
/
|
D
|
4
→
0, q
t
≪
D, and q
t
/
|
D
|
2
→
0, q
t
/
|
D
|
4
→
0, we have (
(
2
q
t
/
|
D
|
2
)
-
(
q
t
/
|
D
|
4
)
)
→
0 and (
(
2
q
t
/
|
D
|
2
)
-
(
q
t
/
|
D
|
4
)
)
=
(
q
t
/
|
D
|
2
)
(
2
-
(
1
/
|
D
|
2
)
)
>
0. Therefore,
(6)
Pr
⁡
[
Succ
A
SM
2
]
=
2
q
t
|
D
|
2
-
q
t
|
D
|
4
⟶
0
.This concludes the proof for Theorem5.


## 3.1. SM2 Key Exchange Protocol

The notations used in SM2 protocol (Table1) are as follows:(i)
A, B: two SM2 protocol participants with identities ID
A and ID
B respectively,
(ii)
a, b: a, b
∈
f
q: the parameters of the elliptic curve E on F
q where elliptic function is y
2
=
x
3
+
a
x
+
b,
(iii)
F
q: the prime field F includes q elements,
(iv)
E
(
F
q
): the set of all points on the elliptic curve E defined over F
q,
(v)
G: the base point of elliptic curve, order of G is prime number that G
=
(
x
G
,
y
G
),
(vi)
h: cofactor, h
=
#
E
(
F
q
)
/
n, n is the order of G,
(vii)
D: the space of number that D
=
[
1
,
n
-
1
],
(viii)
(
d
,
P
): long-term private and public key pair,
(ix)
K: session key,
(x)
ID: identification of client,
(xi)
Z: hash value of identification, the length of Z is e
n
t
l
e
n
A bits,
(xii)
H
v
(
): one-way hash function,
(xiii)
(
r
,
R
): temporary private and public key pair,
(xiv)
k
l
e
n and e
n
t
l
e
n: the bit length of the key and ID, respectively,
(xv)
KDF
(
Z
,
k
l
e
n
): the one-way key derivation hash function whose output length is k
l
e
n,
(xvi)
x
∥
y: concatenation of two strings x and y,
(xvii)
⊥: there is no message or the value is not known.Table 1
SM2 key exchange protocol.
A
B
d
A
,
E
(
F
q
)
,
G
,
n
,
Z
A
,
Z
B
,
P
A
,
P
B
,
H
(
)
,
KDF
(
)
,
G
d
B
,
E
(
F
q
)
,
G
,
n
,
Z
A
,
Z
B
,
P
A
,
P
B
,
H
(
)
,
KDF
(
)
,
G
Randomly selectsr
A
∈
[
1
,
n
-
1
]
Randomly selectsr
B
∈
[
1
,
n
-
1
]
ComputesR
A
=
[
r
A
]
G
=
(
x
1
,
y
1
)
ComputesR
B
=
[
r
B
]
G
=
(
x
2
,
y
2
)
Computesx
1
¯
=
2
w
+
(
x
1
&
(
2
w
-
1
)
)
Computesx
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
)
Computest
A
=
(
d
A
+
x
1
¯
·
r
A
)
mod
⁡
n
Computest
B
=
(
d
B
+
x
2
¯
·
r
B
)
mod
⁡
n
→
R
A
Computesx
1
¯
=
2
w
+
(
x
1
&
(
2
w
-
1
)
)
ComputesV
=
[
h
·
t
B
]
(
P
A
+
[
x
1
¯
]
R
A
)
=
(
x
V
,
y
V
)
ComputesK
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
klen
)
ComputesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
←
R
B
,
S
B
Computesx
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
)
ComputesU
=
[
h
·
t
A
]
(
P
B
+
[
x
2
¯
]
R
B
)
=
(
x
U
,
y
U
)
ComputesK
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B
,
klen
)
ComputesS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
VerifiesS
1
=
?
S
B
ComputesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
→
S
A
ComputesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
VerifiesS
2
=
?
S
A
Key establishedK
A
=
K
B
Key establishedK
B
=
K
A
SID is (R
A
∥
R
B) or (R
A
∥
R
B
∥
S
B
∥
S
A) in the case where key confirmation is required.A randomly selects d
A
∈
[
1
,
n
-
1
] and computes P
A
=
[
d
A
]
G
=
(
x
A
,
y
A
), prior to sending P
A to B. B will also randomly select d
B
∈
[
1
,
n
-
1
] and compute P
B
=
[
d
B
]
G
=
(
x
B
,
y
B
), before sending P
B to A. The public parameters are (
E
(
F
q
)
,
G
,
n
,
Z
A
,
Z
B
,
P
A
,
P
B
). And Z
A and Z
B are hash values of the identification of A and B, respectively, where Z
A
=
H
(
E
N
T
L
A
∥
ID
A
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
A
∥
y
A
) and Z
B
=
H
(
E
N
T
L
B
∥
ID
B
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
B
∥
y
B
). To establish a session key with client B,(1)
clientA will now run the protocol as follows:
(a)
randomly selectsr
A
∈
[
1
,
n
-
1
],
(b)
computesR
A
=
[
r
A
]
G
=
(
x
1
,
y
1
) and x
1
¯
=
2
w
+
(
x
1
&
(
2
w
-
1
)
) where w
=
⌈
(
⌈
log
⁡
2
(
n
)
⌉
/
2
)
⌉
-
1,
(c)
computest
A
=
(
d
A
+
x
1
¯
·
r
A
)
mod
⁡
n,
(d)
sendsR
A to client B;
(2)
upon receiving the messageR
A from client A, B will perform the following:
(a)
randomly selectsr
B
∈
[
1
,
n
-
1
],
(b)
computesR
B
=
[
r
B
]
G
=
(
x
2
,
y
2
), x
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
), t
B
=
(
d
B
+
x
2
¯
·
r
B
)
mod
⁡
n, V
=
[
h
·
t
B
]
(
P
A
+
[
x
1
¯
]
R
A
)
=
(
x
V
,
y
V
) and K
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
k
l
e
n
),
(c)
(optional for key confirmation) computesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(d)
SendsR
B to client A (optional for key confirmation, B will also send S
B to A);
(3)
upon receiving the messages,R
B (and S
B), from B, client A will perform the following:
(a)
computesx
2
¯
=
2
w
+
(
x
2
&
(
2
w
-
1
)
), U
=
[
h
·
t
A
]
(
P
B
+
[
x
2
¯
]
R
B
)
=
(
x
U
,
y
U
) and K
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B
,
k
l
e
n
),
(b)
(optional for key confirmation) computesS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(c)
verifiesS
1
=
?
S
B, and if it returns true then A is assured that B actually has possession of the session key, otherwise, terminates the protocol run and outputs ⊥,
(i)
(optional for key confirmation, computesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)),
(ii)
SendsS
A to client B;
(4)
(optional for key confirmation) upon receiving the message (S
A) from client A, client B will perform the following:
(a)
computesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(b)
verifies whetherS
A
=
?
S
2,
(c)
if the verification returns wrong, then clientB terminates the protocol run and outputs ⊥,
(d)
otherwise, clientB is assured that A actually has possession of the session key;
(5)
session key established isK
A
=
K
B,
(6)
SID is(
R
A
∥
R
B
) or (
R
A
∥
R
B
∥
S
B
∥
S
A
) in the case where key confirmation is required.


## 3.2. Security Proof

The security of the protocol—see Theorem5—is based on the ECDLP assumption (see Definition 4) in the random oracle model.Definition 4 (ECDLP Assumption).
The ECDLP problem is defined as follows:(2)
Instance:
E
∖
F
p
,
P
,
Q
∈
E
(
F
p
)
Output:
k
∈
N
*
,
k
>
1
such
that
Q
≡
k
P
mod
⁡
p
.
If we can solve the discrete logarithm problem (DLP) [26], then we can also (immediately) solve the ECDLP problem.Theorem 5.
SM2 protocol is secure in the sense of Definition3 when the underlying hash and key derivation schemes are modelled as random oracles and the elliptic curve discrete logarithm problem (ECDLP) assumption is satisfied in E
(
F
q
).The soundness requirement is trivial to verify. We will now concentrate on proving the indistinguishability requirement.In the usual tradition of reductionist proofs, we assume that there exists an adversaryA against the protocol (i.e., A has a nonnegligible advantage, η
(
k
), where k is the security parameter), and we then construct a solver S that makes use of A to solve the ECDLP problem. In other words, S will simulate the view of A by answering allSend,Reveal,Corrupt, andTest queries of A. S will start by randomly selecting two users, I and J, and a session number, i, as the test session. S will also manage two random oracles, H and KDF, in order to answer A’s queries. More specifically when the H oracle is queried, S will check whether the tuple is already in the H-list and output the stored response. Otherwise, S will respond with the appropriate output, H
(
⋯
), and adds the tuple (
H
(
⋯
)
,
U
,
i
) to the H-list. S will answer KDF queries in the same manner.(i)
Send
(
Ω
I
,
Ω
J
,
j
,
m
) queries: for any well-formed Send queries from A, S can trivially answer with the right output as the protocol specification demands. Specifically, S answers the query as follows.
(a)
IfΩ
I = initiator and Ω
J = responder, then the S will output the message m
=
(
R
I
,
Z
I
,
Z
J
,
P
I
,
P
J
).
(b)
Consider the case thatΩ
J = initiator, Ω
I = responder, and message m
=
R
I.
(1)
IfS has rejected the message m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages (
R
J
,
S
J
) to A. Otherwise, S will abort the simulation and output ⊥.
(c)
AssumeΩ
I = initiator, Ω
J = responder, and messages m
=
R
J
,
S
J.
(1)
IfS has rejected the messages m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages S
I to A. Otherwise, S will abort the simulation and output ⊥.
(ii)
Reveal
(
Ω
,
j
) queries: if Ω
j
=
I
i or Ω
j
=
J
i, then S will abort the simulation and fail. Otherwise this query can be answered with the right session key as long as U
j has accepted and neither Ω nor its partner has been corrupted. However, such a session will be rendered unfresh.
(iii)
Corrupt
(
Ω
) queries: this query can be easily answered as per the protocol specifications, unless Ω
=
I or Ω
=
J. In the latter scenario, S will abort the simulation and fail.
(iv)
Test
(
Ω
1
,
Ω
2
,
j
,
m
) queries: if Π
U
1
,
U
2
j
≠
Π
I
,
J
i, then S will abort the simulation and fail. Otherwise, S will check whether Π
Ω
1
,
Ω
2
j has accepted and that the session is fresh. If so, A will be given either the actual session key or a session key drawn randomly from the session key distribution, depending on the randomly chosen bit b.ForA to distinguish whether the value returned is the actual session key or a session key drawn randomly from the session key distribution, A has to determine the correct values of U
=
(
x
U
,
y
U
) or V
=
(
x
V
,
y
V
) to compute the session key (since K
I
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B, k
l
e
n
) and K
J
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B, k
l
e
n
)). For this to happen,(i)
A has to guess the long-term private key d
I and short-term private key r
I in order to compute t
I and hence, the session key K
I. If A is able to successfully guess d
I and r
I via P
I
=
[
d
I
]
G and R
I
=
[
r
I
]
G, then S would be able to use A to solve the ECDLP problem. Let Succ
d
I
E
C
D
L
P and Succ
r
I
E
C
D
L
P denote A’s advantage in computing the correct values of d
I and r
I, respectively, and Succ
A
U denotes the event that A can successfully guess the session key using the computed values of d
I and r
I. So we have
(3)
Pr
⁡
[
Succ
d
I
E
C
D
L
P
]
=
1
|
D
|
;
Pr
⁡
[
Succ
r
I
E
C
D
L
P
]
=
1
|
D
|
,
Pr
⁡
[
Succ
A
U
]
=
Pr
⁡
[
Succ
d
I
E
C
D
L
P
]
·
Pr
⁡
[
Succ
r
I
E
C
D
L
P
]
=
1
|
D
|
2
.
(ii)
A has to guess the correct value of V. Similar to the above, we let Succ
d
J
ECDLP and Succ
r
J
E
C
D
L
P denote A’s advantage in computing the correct value of d
J and r
J, respectively, and Succ
A
V denotes the event that A can successfully guess the session key using the computed values of d
J and r
J. So we have
(4)
Pr
⁡
[
Succ
d
J
E
C
D
L
P
]
=
1
|
D
|
;
Pr
⁡
[
Succ
r
J
E
C
D
L
P
]
=
1
|
D
|
,
Pr
⁡
[
Succ
A
V
]
=
Pr
⁡
[
Succ
d
J
E
C
D
L
P
]
·
Pr
⁡
[
Succ
r
J
E
C
D
L
P
]
=
1
|
D
|
2
.There is, therefore, a negligible advantage of A distinguishing whether the value returned is the actual session key or a session key drawn randomly from the session key distribution. Let q
t and Succ
A
SM
2 denote the number of Test  queries asked and the event that A can correctly distinguish the session key, respectively. We now have
(5)
Pr
⁡
[
Succ
A
SM
2
]
=
(
1
-
Pr
⁡
[
Succ
A
U
¯
]
Pr
⁡
[
Succ
A
V
¯
]
)
·
q
t
=
(
1
-
(
1
-
1
|
D
|
2
)
·
(
1
-
1
|
D
|
2
)
)
·
q
t
=
2
q
t
|
D
|
2
-
q
t
|
D
|
4
.SinceD
=
[
1
,
n
-
1
], n
→
∞, D
→
∞, 1
/
|
D
|
2
→
0, 1
/
|
D
|
4
→
0, q
t
≪
D, and q
t
/
|
D
|
2
→
0, q
t
/
|
D
|
4
→
0, we have (
(
2
q
t
/
|
D
|
2
)
-
(
q
t
/
|
D
|
4
)
)
→
0 and (
(
2
q
t
/
|
D
|
2
)
-
(
q
t
/
|
D
|
4
)
)
=
(
q
t
/
|
D
|
2
)
(
2
-
(
1
/
|
D
|
2
)
)
>
0. Therefore,
(6)
Pr
⁡
[
Succ
A
SM
2
]
=
2
q
t
|
D
|
2
-
q
t
|
D
|
4
⟶
0
.This concludes the proof for Theorem5.


## 4. A Provably-Secure Simplified SM2 Key Exchange Protocol

In this section, we propose a more efficient version of the SM2 protocol—see Table2—and prove its security in the Bellare-Rogaway model.Table 2
Simplified SM2 key exchange protocol.
A
B
pub:E
(
F
q
)
,
G
,
n
,
H
(
)
,
KDF
(
)
,
G
,
P
A
,
P
B
,
Z
A
,
Z
B
Randomly selectsr
A
∈
[
1
,
n
-
1
]
Randomly selectsr
B
∈
[
1
,
n
-
1
]
Computest
A
=
(
d
A
·
r
A
)
mod
⁡
n
Computest
B
=
(
d
B
·
r
B
)
mod
⁡
n
ComputesR
A
=
[
t
A
]
G
=
(
x
1
,
y
1
)
ComputesR
B
=
[
t
B
]
G
=
(
x
2
,
y
2
)
→
R
A
ComputesV
=
[
t
B
]
·
R
A
+
d
B
·
P
A
=
(
x
V
,
y
V
)
ComputesK
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
klen
)
ComputesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
←
R
B
,
S
B
ComputesU
=
[
t
A
]
·
R
B
+
d
A
·
P
B
=
(
x
U
,
y
U
)
ComputesK
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B
,
klen
)
ComputesS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
VerifiesS
1
=
?
S
B
ComputesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
→
S
A
ComputesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
)
VerifiesS
2
=
?
S
A
Key establishedK
A
=
K
B
Key establishedK
B
=
K
A
SID is (R
A
∥
R
B) or (R
A
∥
R
B
∥
S
B
∥
S
A) in the case where key confirmation is required.


### 4.1. Protocol Description

A randomly selects d
A
∈
[
1
,
n
-
1
] and computes long-term public key P
A
=
[
d
A
]
G
=
(
x
A
,
y
A
) and Z
A
=
H
(
E
N
T
L
A
∥
ID
A
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
A
∥
y
A
). It then sends P
A and Z
A to B. B also randomly selects d
B
∈
[
1
,
n
-
1
] and computes P
B
=
[
d
B
]
G
=
(
x
B
,
y
B
) and Z
B
=
H
(
E
N
T
L
A
∥
ID
A
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
B
∥
y
B
), prior to sending P
B and Z
B to A. E
(
F
q
)
,
G
,
n
,
H
(
)
,
KDF
(
)
,
G
,
P
A
,
P
B
,
Z
A
,
Z
B are system parameters. To establish a session key with B,(1)
A will now run the protocol as follows:
(a)
randomly selectsr
A
∈
[
1
,
n
-
1
],
(b)
computest
A
=
(
d
A
·
r
A
)
mod
⁡
n and R
A
=
[
t
A
]
G
=
(
x
1
,
y
1
),
(c)
sendsR
A to B;
(2)
upon receivingP
A from A, B will perform the following:
(a)
randomly selectsr
B
∈
[
1
,
n
-
1
],
(b)
computest
B
=
(
d
B
·
r
B
)
mod
⁡
n, R
B
=
[
t
B
]
G
=
(
x
2
,
y
2
), V
=
[
t
B
]
·
R
A
+
d
B
·
P
A
=
(
x
V
,
y
V
), and K
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
klen
),
(c)
(optional for key confirmation) computesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(d)
sendsR
B to A (optionally for key confirmation, B will also send S
B to A);
(3)
upon receivingR
B (and S
B, optionally for key confirmation) from B, A will perform the following:
(a)
computesU
=
[
t
A
]
·
R
B
+
d
A
·
P
B
=
(
x
U
,
y
U
) and K
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B, k
l
e
n
),
(b)
(optional for key confirmation) computeS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(c)
verifies thatS
1
=
?
S
B, and if it returns true, then A is assured that B actually has possession of the session key, otherwise, terminates the protocol run and outputs ⊥,
(i)
(optional for key confirmation) computesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(ii)
SendS
A to client B;
(4)
(optional for key confirmation) upon receivingS
A, B will perform the following:
(a)
computesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(b)
verifies whetherS
A
=
?
S
2,
(c)
if the verification returns wrong, then clientB terminates the protocol run and outputs ⊥. If it returns true, then B is assured that A actually has possession of the session key. Otherwise, terminates the protocol run and outputs ⊥;
(
5
)
session key established is K
A
=
K
B,
(
6
)
SID is (
R
A
∥
R
B
) or (
R
A
∥
R
B
∥
S
B
∥
S
A
) in the case where key confirmation is required.


### 4.2.  Security Proof

Theorem 6.
The simplified SM2 protocol (Table2) is secure in the sense of Definition 3 when the underlying hash and key derivation schemes are modelled as random oracles and the ECDLP assumption is satisfied in E
(
F
q
).The proof process is similar to that of Section3.2.(i)
Send
(
Ω
I
,
Ω
J
,
j
,
m
) queries: for any well-formedSendqueries from A, S can trivially answer with the right output as the protocol specification demands. Specifically, S answers the query as follows.
(a)
IfΩ
I = initiator and Ω
J = responder, then the S will output the message, m
=
R
I, to the query.
(b)
Consider the case thatΩ
J = initiator, Ω
I = responder, and messages m
=
R
I.
(1)
IfS has rejected the message m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages (
R
J
,
S
J
) to A. Otherwise, S will abort the simulation and output ⊥.
(c)
AssumeΩ
I = initiator, Ω
J = responder, and messages m
=
R
J
,
S
J.
(1)
IfS has rejected the messages m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages S
I to A. Otherwise, S will abort the simulation and output ⊥.Simulations for theReveal,Corrupt, andTest follow that of Section 3.2.ForA to distinguish whether the value returned is the actual session key or a session key drawn randomly from the session key distribution (i.e., whether b
=
0 or b
=
1), A has to determine the correct values of U
=
(
x
U
,
y
U
) or V
=
(
x
V
,
y
V
) (since K
I
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B, k
l
e
n
) and K
J
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B, k
l
e
n
)). For this to happen, A has to obtain the correct value of d
I
·
r
I in order to compute t
I and consequently, the session key K
I. For A to obtain t
I, A has to be able to compute from R
I since R
I
=
[
t
I
]
G.LetSucc
t
I
E
C
D
L
P denote A’s advantage in computing t
I from R
I, and we have
(7)
Pr
⁡
[
Succ
t
I
E
C
D
L
P
]
=
1
|
D
|
.LetSucc
t
J
E
C
D
L
P denote A’s advantage in computing t
J from R
J, and we have
(8)
Pr
⁡
[
Succ
t
J
E
C
D
L
P
]
=
1
|
D
|
.LetSucc
A
ESM
2 denote the event that A is able to distinguish whether the value returned is the actual session key or a session key drawn randomly from the session key distribution. We then have
(9)
Pr
⁡
[
Succ
A
ESM
2
]
=
(
1
-
Pr
⁡
[
Succ
t
I
E
C
D
L
P
¯
]
·
Pr
⁡
[
Succ
t
J
E
C
D
L
P
¯
]
)
·
q
t
=
(
1
-
(
1
-
1
|
D
|
)
2
)
·
q
t
=
2
q
t
|
D
|
-
q
t
|
D
|
2
.SinceD
=
[
1
,
n
-
1
], n
→
∞, D
→
∞, 2
/
|
D
|
→
0, 1
/
|
D
|
4
→
0, q
t
≪
D, and 2
q
t
/
|
D
|
→
0, q
t
/
|
D
|
2
→
0, we have (
(
2
q
t
/
|
D
|
)  −  (
q
t
/
|
D
|
2
)
)
→
0 and (
(
2
q
t
/
|
D
|
)
-
(
q
t
/
|
D
|
2
)
)
=
(
q
t
/
|
D
|
)
(
2
-
(
1
/
|
D
|
)
)
>
0. It follows that Pr
⁡
[
Succ
A
ESM
2
]
=
(
2
q
t
/
|
D
|
)
-
(
q
t
/
|
D
|
2
)
→
0.This concludes the proof for Theorem6.


## 4.1. Protocol Description

A randomly selects d
A
∈
[
1
,
n
-
1
] and computes long-term public key P
A
=
[
d
A
]
G
=
(
x
A
,
y
A
) and Z
A
=
H
(
E
N
T
L
A
∥
ID
A
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
A
∥
y
A
). It then sends P
A and Z
A to B. B also randomly selects d
B
∈
[
1
,
n
-
1
] and computes P
B
=
[
d
B
]
G
=
(
x
B
,
y
B
) and Z
B
=
H
(
E
N
T
L
A
∥
ID
A
∥
a
∥
b
∥
x
G
∥
y
G
∥
x
B
∥
y
B
), prior to sending P
B and Z
B to A. E
(
F
q
)
,
G
,
n
,
H
(
)
,
KDF
(
)
,
G
,
P
A
,
P
B
,
Z
A
,
Z
B are system parameters. To establish a session key with B,(1)
A will now run the protocol as follows:
(a)
randomly selectsr
A
∈
[
1
,
n
-
1
],
(b)
computest
A
=
(
d
A
·
r
A
)
mod
⁡
n and R
A
=
[
t
A
]
G
=
(
x
1
,
y
1
),
(c)
sendsR
A to B;
(2)
upon receivingP
A from A, B will perform the following:
(a)
randomly selectsr
B
∈
[
1
,
n
-
1
],
(b)
computest
B
=
(
d
B
·
r
B
)
mod
⁡
n, R
B
=
[
t
B
]
G
=
(
x
2
,
y
2
), V
=
[
t
B
]
·
R
A
+
d
B
·
P
A
=
(
x
V
,
y
V
), and K
B
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B
,
klen
),
(c)
(optional for key confirmation) computesS
B
=
H
(
0
x
02
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(d)
sendsR
B to A (optionally for key confirmation, B will also send S
B to A);
(3)
upon receivingR
B (and S
B, optionally for key confirmation) from B, A will perform the following:
(a)
computesU
=
[
t
A
]
·
R
B
+
d
A
·
P
B
=
(
x
U
,
y
U
) and K
A
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B, k
l
e
n
),
(b)
(optional for key confirmation) computeS
1
=
H
(
0
x
02
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(c)
verifies thatS
1
=
?
S
B, and if it returns true, then A is assured that B actually has possession of the session key, otherwise, terminates the protocol run and outputs ⊥,
(i)
(optional for key confirmation) computesS
A
=
H
(
0
x
03
∥
y
U
∥
H
(
x
U
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(ii)
SendS
A to client B;
(4)
(optional for key confirmation) upon receivingS
A, B will perform the following:
(a)
computesS
2
=
H
(
0
x
03
∥
y
V
∥
H
(
x
V
∥
Z
A
∥
Z
B
∥
x
1
∥
y
1
∥
x
2
∥
y
2
)
),
(b)
verifies whetherS
A
=
?
S
2,
(c)
if the verification returns wrong, then clientB terminates the protocol run and outputs ⊥. If it returns true, then B is assured that A actually has possession of the session key. Otherwise, terminates the protocol run and outputs ⊥;
(
5
)
session key established is K
A
=
K
B,
(
6
)
SID is (
R
A
∥
R
B
) or (
R
A
∥
R
B
∥
S
B
∥
S
A
) in the case where key confirmation is required.


## 4.2.  Security Proof

Theorem 6.
The simplified SM2 protocol (Table2) is secure in the sense of Definition 3 when the underlying hash and key derivation schemes are modelled as random oracles and the ECDLP assumption is satisfied in E
(
F
q
).The proof process is similar to that of Section3.2.(i)
Send
(
Ω
I
,
Ω
J
,
j
,
m
) queries: for any well-formedSendqueries from A, S can trivially answer with the right output as the protocol specification demands. Specifically, S answers the query as follows.
(a)
IfΩ
I = initiator and Ω
J = responder, then the S will output the message, m
=
R
I, to the query.
(b)
Consider the case thatΩ
J = initiator, Ω
I = responder, and messages m
=
R
I.
(1)
IfS has rejected the message m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages (
R
J
,
S
J
) to A. Otherwise, S will abort the simulation and output ⊥.
(c)
AssumeΩ
I = initiator, Ω
J = responder, and messages m
=
R
J
,
S
J.
(1)
IfS has rejected the messages m, then S will respond with ⊥. Otherwise, S will verify whether m is the right format or not.
(2)
Ifm verifies correctly, then S will output messages S
I to A. Otherwise, S will abort the simulation and output ⊥.Simulations for theReveal,Corrupt, andTest follow that of Section 3.2.ForA to distinguish whether the value returned is the actual session key or a session key drawn randomly from the session key distribution (i.e., whether b
=
0 or b
=
1), A has to determine the correct values of U
=
(
x
U
,
y
U
) or V
=
(
x
V
,
y
V
) (since K
I
=
KDF
(
x
U
∥
y
U
∥
Z
A
∥
Z
B, k
l
e
n
) and K
J
=
KDF
(
x
V
∥
y
V
∥
Z
A
∥
Z
B, k
l
e
n
)). For this to happen, A has to obtain the correct value of d
I
·
r
I in order to compute t
I and consequently, the session key K
I. For A to obtain t
I, A has to be able to compute from R
I since R
I
=
[
t
I
]
G.LetSucc
t
I
E
C
D
L
P denote A’s advantage in computing t
I from R
I, and we have
(7)
Pr
⁡
[
Succ
t
I
E
C
D
L
P
]
=
1
|
D
|
.LetSucc
t
J
E
C
D
L
P denote A’s advantage in computing t
J from R
J, and we have
(8)
Pr
⁡
[
Succ
t
J
E
C
D
L
P
]
=
1
|
D
|
.LetSucc
A
ESM
2 denote the event that A is able to distinguish whether the value returned is the actual session key or a session key drawn randomly from the session key distribution. We then have
(9)
Pr
⁡
[
Succ
A
ESM
2
]
=
(
1
-
Pr
⁡
[
Succ
t
I
E
C
D
L
P
¯
]
·
Pr
⁡
[
Succ
t
J
E
C
D
L
P
¯
]
)
·
q
t
=
(
1
-
(
1
-
1
|
D
|
)
2
)
·
q
t
=
2
q
t
|
D
|
-
q
t
|
D
|
2
.SinceD
=
[
1
,
n
-
1
], n
→
∞, D
→
∞, 2
/
|
D
|
→
0, 1
/
|
D
|
4
→
0, q
t
≪
D, and 2
q
t
/
|
D
|
→
0, q
t
/
|
D
|
2
→
0, we have (
(
2
q
t
/
|
D
|
)  −  (
q
t
/
|
D
|
2
)
)
→
0 and (
(
2
q
t
/
|
D
|
)
-
(
q
t
/
|
D
|
2
)
)
=
(
q
t
/
|
D
|
)
(
2
-
(
1
/
|
D
|
)
)
>
0. It follows that Pr
⁡
[
Succ
A
ESM
2
]
=
(
2
q
t
/
|
D
|
)
-
(
q
t
/
|
D
|
2
)
→
0.This concludes the proof for Theorem6.


## 5. Conclusion

Key exchange protocols are the cornerstone of any secure communication. By proving the widely used Chinese Government SM2 protocol secure in the Bellare-Rogaway model under the ECDLP assumption, we hope that this provides a strong assurance to protocol implementers that the protocol is behaving as desired. In addition, we presented a more efficient version of the SM2 protocol with a proof of security in the Bellare-Rogaway model under the ECDLP assumption.A comparison with six existing pairing-free protocols reveals that the computational load of our simplified SM2 protocol is no more than that of the six and the SM2 protocols, yet provides both implicit key confirmation (A is assured that B can compute the session key) and explicit key confirmation (A is assured that B has actually computed the session key)—see Table 3. In Table 3, a, m, e, and h denote addition, multiplication, exponentiation, and hash operations, respectively.Table 3
Protocol comparison.
Protocol
Cost
Both implicit and explicit key confirmation?
Cao et al. (2008) [13]
10
m
+
4
a
+
4
h
+
1
e
No
Cao et al. (2010) [10]
8
m
+
3
a
+
2
h
No
He et al. (2012) [2]
6m + 5a + 2e + 2h
No
Yang and Tan (2011) [24]
6
m
+
2
h
No
He et al. (2011) [14]
5
m
+
4
a
+
2
h
No
Chen and Han (2013) [25]
9
m
+
2
a
+
7
h
+
1
e
No
SM2 [15]
5
m
+
4
a
+
3
h
Yes
Our simplified SM2 protocol
4
m
+
1
a
+
3
h
Yes



---

*Source: 825984-2014-09-02.xml*