An Efficient Protocol for Authenticated Key Agreement.
This paper proposes an efficient two-pass protocol for authenticated key agreement in the asymmetric (public-key) setting. The protocol is based on Diffie-Hellman key agreement and can be modified to work in an arbitrary finite group and, in particular, elliptic curve groups. Two modifications of this protocol are also presented: a one-pass authenticated key agreement protocol suitable for environments where only one entity is on-line, and a three-pass protocol in which key confirmation is additionally provided. Variants of these protocols have been standardized in IEEE P1363 [17], ANSI X9.42 [2], ANSI X9.63 [4] and ISO 15496-3 [18], and are currently under consideration for standardization and by the U.S. government's National Institute for Standards and Technology [30].
Introduction
Key establishment is the process by which two (or more) entities establish a shared secret key.
The key is subsequently used to achieve some cryptographic goal such as confidentiality or data
integrity. Broadly speaking, there are two kinds of key establishment protocols: key transport
protocols in which a key is created by one entity and securely transmitted to the second entity,
and key agreement protocols in which both parties contribute information which jointly establish
the shared secret key. In this paper, we shall only consider key agreement protocols for the
asymmetric (public-key) two-entity setting.
Let A and B be two honest entities, i.e., legitimate entities who execute the steps of a
protocol correctly. Informally speaking, a key agreement protocol is said to provide implicit key
authentication (of B to A) if entity A is assured that no other entity aside from a specifically
identified second entity B can possibly learn the value of a particular secret key. Note that the
property of implicit key authentication does not necessarily mean that A is assured of B actually
possessing the key. A key agreement protocol which provides implicit key authentication to both
participating entities is called an authenticated key agreement (AK) protocol.
Informally speaking, a key agreement protocol is said to provide key confirmation (of B to
is assured that the second entity B actually has possession of a particular secret
key. If both implicit key authentication and key confirmation (of B to are provided, then
the key establishment protocol is said to provide explicit key authentication (of B to A). A key
agreement protocol which provides explicit key authentication to both participating entities is
called an authenticated key agreement with key confirmation (AKC) protocol. For an extensive
survey on key establishment, see Chapter 12 of Menezes, van Oorschot and Vanstone [27].
Extreme care must be exercised when separating key confirmation from implicit key authen-
tication. If an AK protocol which does not offer key confirmation is used, then, as pointed out
in [10], it is desirable that the agreed key be confirmed prior to cryptographic use. This can be
done in a variety of ways. For example, if the key is to be subsequently used to achieve confiden-
tiality, then encryption with the key can begin on some (carefully chosen) known data. Other
systems may provide key confirmation during a 'real-time' telephone conversation. Separating
key confirmation from implicit key authentication is sometimes desirable because it permits flexibility
in how a particular implementation chooses to achieve key confirmation, and thus moves
the burden of key confirmation from the establishment mechanism to the application.
In this paper, we propose a new and efficient two-pass AK protocol. The protocol is based
on Diffie-Hellman key agreement [14], and has many of the desirable security and performance
attributes discussed in [10] (see x2). Two modifications of this protocol are also presented: a
one-pass AK protocol suitable for environments where only one entity is on-line, and a three-pass
protocol in which key confirmation is additionally provided.
The protocols described in this paper establish a shared secret K between two entities. A
derivation function should then be used to derive a secret key from the shared secret. This
is necessary because K may have some weak bits - bits of information about K that can be
predicted correctly with non-negligible advantage. One way to derive a secret key from K is to
apply a one-way hash function such as SHA-1 [28] to K. With the exception of Protocol 3 in
x6.2, this paper does not include key derivation functions in protocol descriptions.
All protocols described in this paper have been described in the setting of the group of points
on an elliptic curve defined over a finite field. However, they can all be easily modified to work
in any finite group in which the discrete logarithm problem appears intractable. Suitable choices
include the multiplicative group of a finite field, subgroups of Z
n where n is a composite integer,
and subgroups of Z
p of prime order q. Elliptic curve groups are advantageous because they offer
equivalent security as the other groups but with smaller key sizes and faster computation times.
The remainder of the paper is organized as follows. x2 discusses the desirable attributes of
AK and AKC protocols. x3 describes the elliptic curve parameters that are common to both
entities involved in the protocols, public keys, and methods for validating them. x4 reviews the
MTI protocols, and describes some active attacks on them. These attacks influenced the design
of the new two-pass AK protocol, which is presented in x5. x6 presents the one-pass variant of
the protocol, and the three-pass variant which provides explicit key authentication. Finally, x7
makes concluding remarks.
Desirable attributes of AK and AKC protocols
Numerous Diffie-Hellman-based AK and AKC protocols have been proposed over the years; how-
ever, many have subsequently been found to have security flaws. The main problems were that
appropriate threat models and the goals of secure AK and AKC protocols lacked formal defini-
tion. Blake-Wilson, Johnson and Menezes [10], adapting earlier work of Bellare and Rogaway [9]
in the symmetric setting, provided a formal model of distributed computing and rigorous definitions
of the goals of secure AK and AKC protocols within this model. Concrete AK and AKC
protocols were proposed, and proven secure within this framework in the random oracle model
[8]. This paper follows their definitions of goals of secure AK and AKC protocols (described
informally in x1) and their classification of threats.
A secure protocol should be able to withstand both passive attacks (where an adversary
attempts to prevent a protocol from achieving its goals by merely observing honest entities
carrying out the protocol) and active attacks (where an adversary additionally subverts the
communications by injecting, deleting, altering or replaying messages). In addition to implicit
authentication and key confirmation, a number of desirable security attributes of AK and
AKC protocols have been identified (see [10] for a further discussion of these):
1. known-key security. Each run of a key agreement protocol between two entities A and B
should produce a unique secret key; such keys are called session keys. A protocol should
still achieve its goal in the face of an adversary who has learned some other session keys.
2. (perfect) forward secrecy. If long-term private keys of one or more entities are compromised,
the secrecy of previous session keys established by honest entities is not affected.
3. key-compromise impersonation. Suppose A's long-term private key is disclosed. Clearly
an adversary that knows this value can now impersonate A, since it is precisely this value
that identifies A. However, it may be desirable that this loss does not enable an adversary
to impersonate other entities to A.
4. unknown key-share. Entity A cannot be coerced into sharing a key with entity B without
A's knowledge, i.e., when A believes the key is shared with some entity C 6= B, and B
(correctly) believes the key is shared with A.
5. key control. Neither entity should be able to force the session key to a preselected value.
Desirable performance attributes of AK and AKC protocols include a minimal number of
(the number of messages exchanged in a run of the protocol), low communication overhead
(total number of bits transmitted), and low computation overhead. Other attributes that may
be desirable in some circumstances include role-symmetry (the messages transmitted between
entities have the same structure), non-interactiveness (the messages transmitted between the
two entities are independent of each other), and the non-reliance on encryption (to meet export
requirements), hash functions (since these are notoriously hard to design), and timestamping
(since it is difficult to implement securely in practice).
3 Domain parameters and key pair generation
This section describes the elliptic curve parameters that are common to both entities involved
in the protocols (i.e., the domain parameters), and the key pairs of each entity.
3.1 Domain parameters
The domain parameters for the protocols described in this paper consist of a suitably chosen
elliptic curve E defined over a finite field F q of characteristic p, and a base point In
the remainder of this subsection, we elaborate on what "suitable" parameters are, and outline
a procedure for verifying that a given set of parameters meet these requirements.
In order to avoid the Pollard-rho [32] and Pohlig-Hellman [31] algorithms for the elliptic curve
discrete logarithm problem (ECDLP), it is necessary that the number of F q -rational points on E,
denoted #E(F q ), be divisible by a sufficiently large prime n. As of this writing, it is commonly
recommended that n ? 2 160 (see [3, 4]). Having fixed an underlying field F q , n should be
selected to be as large as possible, i.e., one should have n - q, so #E(F q ) is almost prime. In
the remainder of this paper, we shall assume that n ? 2 160 and that n ? 4 p q. By Hasse's
Theorem,
Hence implies that n 2 does not divide #E(F q ), and thus E(F q ) has a unique subgroup
of order n. Also, since
there is a unique integer h such that
namely
To guard against potential small subgroup
attacks (see x4.1), the point P should have order n.
Some further precautions should be exercised when selecting the elliptic curve. To avoid the
reduction algorithms of Menezes, Okamoto and Vanstone [24] and Frey and R-uck [16], the curve
should be non-supersingular (i.e., p should not divide (q generally, one
should verify that n does not divide q large enough so that
it is computationally infeasible to find discrete logarithms in F q C suffices in practice
[3]). To avoid the attack of Semaev [34], Smart [35], and Satoh and Araki [33] on F q -anomalous
curves, the curve should not be F q -anomalous (i.e., #E(F q ) 6= q).
A prudent way to guard against these attacks, and similar attacks against special classes of
curves that may be discovered in the future, is to select the elliptic curve E at random subject
to the condition that #E(F q ) is divisible by a large prime - the probability that a random
curve succumbs to these special-purpose attacks is negligible. A curve can be selected verifiably
at random by choosing the coefficients of the defining elliptic curve equation as the outputs of
a one-way function such as SHA-1 according to some pre-specified procedure. A procedure for
accomplishing this, similar in spirit to the method given in FIPS 186 [29] for selecting DSA
primes verifiably at random, is described in ANSI X9.62 [3].
To summarize, domain parameters are comprised of:
1. a field size q, where q is a prime power (in practice, either an odd prime, or
2. an indication FR (field representation) of the representation used for the elements of F q ;
3. two field elements a and b in F q which define the equation of the elliptic curve E over F q
(i.e., in the case p ? 3, and y in the case
4. two field elements x P and y P in F q which define a finite point of prime order
in E(F q ) (since P is described by two field elements, this implies that P 6= O, where O
denotes the point at infinity);
5. the order n of the point P ; and
6. the cofactor
Domain parameter validation. A set of domain parameters (q; FR; a; b;
can be verified to meet the above requirements as follows. This process is called domain parameter
validation.
1. Verify that q is a prime power.
2. Verify that FR is a valid field representation.
3. Verify that a, b, x P and y P are elements of F q (i.e., verify that they are of the proper
format for elements of F q ).
4. Verify that a and b define a (non-singular) elliptic curve over F q (i.e., 4a 3
the case p ? 3, and b 6= 0 in the case
5. Verify that P satisfies the defining equation of E (and that P 6= O).
6. Verify that n ? 4 p q, that n is prime, and that n is sufficiently large (e.g., n ? 2 160 ).
7. Verify that
8. Compute
verify that
9. To ensure protection against known attacks on special classes of elliptic curves, verify that
n does not divide q 20, and that n 6= q.
3.2 Key pair generation
Given a valid set of domain parameters (q; FR; a; b; h), an entity A's private key is an
integer d selected at random from the interval [1; n \Gamma 1]. A's public key is the elliptic curve point
. The key pair is (Q; d). Each run of a key agreement protocol between two entities
A and B should produce a unique shared secret key. Hence, for the protocols described in this
paper, each entity has two public keys: a static or long-term public key, and an ephemeral or
short-term public key. The static public key is bound to the entity for a certain period of time,
typically through the use of certificates. A new ephemeral public key is generated for each run
of the protocol. A's static key pair is denoted (WA ; wA ), while A's ephemeral key pair is denoted
For the remainder of this paper, we will assume that static public keys are exchanged via
certificates. Cert A denotes A's public-key certificate, containing a string of information that
uniquely identifies A (such as A's name and address), her static public key WA , and a certifying
authority CA's signature over this information. To avoid a potential unknown key-share attack
(see x4.2), the CA should verify that A possesses the private key wA corresponding to her
static public key WA . Other information may be included in the data portion of the certificate,
including the domain parameters if these are not known from context. Any other entity B can
use his authentic copy of the CA's public key to verify A's certificate, thereby obtaining an
authentic copy of A's static public key.
Public-key validation. Before using an entity's purported public key Q, it is prudent to
verify that it possesses the arithmetic properties it is supposed to - namely that Q be a finite
point in the subgroup generated by P . This process is called public-key validation [19]. Given
a valid set of domain parameters (q; FR; a; b; purported public key
be validated by verifying that:
1. Q is not equal to O;
2. xQ and y Q are elements in the field F q (i.e., they are of the proper format for elements of
3. Q satisfies the defining equation of E; and
4.
Embedded public-key validation. The computationally expensive operation in public-key
validation is the scalar multiplication in step 4. For static public keys, the validation could be
done once and for all by the CA. However, since a new ephemeral key is generated for each
run of the protocol, validation of the ephemeral key places a significant burden on the entity
performing the validation. To reduce this burden, step 4 can be omitted during key validation.
Instead, the protocols proposed in x5 and x6 ensure that the shared secret K generated is a finite
point in the subgroup generated by P . To summarize, given a valid set of domain parameters
embedded public-key validation of a purported public key
accomplished by verifying that:
1. Q is not equal to O;
2. xQ and y Q are elements in the field F q (i.e., they are of the proper format for elements of
F q ); and
3. Q satisfies the defining equation of E.
4 The MTI key agreement protocols
The MTI/A0 and MTI/C0 key agreement protocols described here are special cases of the
three infinite families of key agreement protocols proposed by Matsumoto, Takashima and Imai
[23] in 1986. They were designed to provide implicit key authentication, and do not provide key
confirmation. Closely related protocols are KEA [30] and those proposed by Goss [17] and Yacobi
[37], the latter operating in the ring of integers modulo a composite integer. Yacobi proved that
his protocol is secure against certain types of known-key attacks by a passive adversary (provided
that the composite modulus Diffie-Hellman problem is intractable). However, Desmedt and
Burmester [13] pointed out that the security is only heuristic under known-key attack by an
active adversary.
This section illustrates that the MTI/A0 and MTI/C0 families of protocols are vulnerable to
several active attacks. The small subgroup attack presented in x4.1 illustrates that the MTI/C0
protocol (as originally described) does not provide implicit key authentication. The unknown
attack presented in x4.2 illustrates that the MTI/A0 protocol does not possess the
unknown key-share attribute in some circumstances. Other active attacks on AK protocols are
discussed by Diffie, van Oorschot and Wiener [15], Burmester [11], Just and Vaudenay [20], and
Lim and Lee [22].
4.1 Small subgroup attack
The small subgroup attack was first pointed out by Vanstone [26]; see also van Oorschot and
Wiener [36], Anderson and Vaudenay [1], and Lim and Lee [22]. The attack illustrates that authenticating
and validating the static and ephemeral keys is a prudent, and sometimes essential,
measure to take in Diffie-Hellman AK protocols. We illustrate the small subgroup attack on the
MTI/C0 protocol. The protocol assumes that A and B a priori possess authentic copies of each
other's static public keys.
MTI/C0 AK protocol.
1. A generates a random integer r A , computes the point
sends to B.
2. B generates a random integer r computes the point
sends TB to A.
3. A computes
A r
4. B computes
5. The shared secret is the point K.
The small subgroup attack can be launched if the order n of the base point P is not prime;
say, . The attack forces the shared secret to be one of a small and
known subset of points.
A small subgroup attack on the MTI/C0 protocol.
1. E intercepts A's message replaces it with
2. E intercepts B's message TB and replaces it with mTB .
3. A computes
A r A (mTB
4. B computes
K lies in the subgroup of order t of the group generated by P , and hence it takes on one of only
possible values. Since the value of K can be correctly guessed by E with high probability, this
shows that the MTI/C0 protocol does not provide implicit key authentication. The effects of
this can be especially drastic because a subsequent key confirmation phase may fail to detect
this attack - E may be able to correctly compute the messages required for key confirmation.
For example, E may be able to compute on behalf of A the message authentication code (MAC)
under K of the message consisting of the identities of A and B, the ephemeral point
purportedly sent by A, and the point sent by B.
The small subgroup attack in MTI/C0 can be prevented, for example, by mandating use of
a base point P of prime order, and requiring that both A and B perform key validation on the
ephemeral public keys they receive.
1 In this case, static private keys w should be selected subject to the condition
4.2 Unknown key-share attack
The active attack on the MTI/A0 protocol described in this subsection was first pointed out
by Menezes, Qu and Vanstone [25]. The attack, and the many variants of it, illustrate that
it is prudent to require an entity A to prove possession of the private key corresponding to
its (static) public key to a CA before the CA certifies the public key as belonging to A. This
proof of possession can be accomplished by zero-knowledge techniques; for example, see Chaum,
Evertse and van de Graaf [12].
MTI/A0 AK protocol.
1. A generates a random integer r A , computes the point
sends (RA ; Cert A ) to B.
2. B generates a random integer r computes the point
sends (RB ; Cert B ) to A.
3. A computes
4. B computes
5. The shared secret is the point K.
In one variant of the unknown key-share attack, the adversary E wishes to have messages
sent from A to B identified as having originated from E herself. To accomplish this, E selects an
integer e, 1 - e - and gets this certified as her public key.
Notice that E does not know the logical private key which corresponds to her
public key (assuming, of course, that the discrete logarithm problem in E(F q ) is intractable),
although she knows e.
An unknown key-share attack on the MTI/A0 protocol.
1. E intercepts A's message (RA ; Cert A ) and replaces it with (RA ; Cert E ).
2. B sends (RB ; Cert B ) to E, who then forwards (eRB ; Cert B ) to A.
3. A computes
4. B computes
A and B now share the secret K even though B believes he shares the secret with E. Note that
does not learn the value of K. Hence, the attack illustrates that the MTI/A0 protocol does
not possess the unknown key-share attribute.
A hypothetical scenario where the attack may be launched successfully is the following; this
scenario was first described by Diffie, van Oorschot and Wiener [15]. Suppose that B is a bank
branch and A is an account holder. Certificates are issued by the bank headquarters and within
each certificate is the account information of the holder. Suppose that the protocol for electronic
deposit of funds is to exchange a key with a bank branch via a mutually authenticated key
agreement. Once B has authenticated the transmitting entity, encrypted funds are deposited
to the account number in the certificate. Suppose that no further authentication is done in
the encrypted deposit message (which might be the case to save bandwidth). If the attack
mentioned above is successfully launched then the deposit will be made to E's account instead
of A's account.
5 The new authenticated key agreement protocol
In this section, the two-pass AK protocol is described. The following notation is used in x5 and
x6. f denotes the bitlength of n, the prime order of the base point
If Q is a finite elliptic curve point, then Q is defined as follows. Let x be the x-coordinate of
Q, and let x be the integer obtained from the binary representation of x. (The value of x will
depend on the representation chosen for the elements of the field F q .) Then Q is defined to be
the integer . Observe that (Q mod n) 6= 0.
5.1 Protocol description
We now describe the two-pass AK protocol (Protocol 1) which is an optimization and refinement
of a protocol first described by Menezes, Qu and Vanstone [25]. It is depicted in Figure 1. In
this and subsequent Figures, A (w A;WA ) denotes that A's static private key and static public key
are wA and WA , respectively. Domain parameters and static keys are set up and validated as
described in x3. If A and B do not a priori possess authentic copies of each other's static public
then certificates should be included in the flows.
RA

Figure

1: Two-pass AK protocol (Protocol 1)
Protocol 1.
1. A generates a random integer r A , computes the point
sends this to B.
2. B generates a random integer r computes the point
sends this to A.
3. A does an embedded key validation of RB (see x3.2). If the validation fails, then A
terminates the protocol run with failure. Otherwise, A computes
and
If terminates the protocol run with failure.
4. B does an embedded key validation of RA . If the validation fails, then B terminates the
protocol run with failure. Otherwise, B computes
and
If terminates the protocol run with failure.
5. The shared secret is the point K.
5.2 Security notes and rationale
Although the security of Protocol 1 has not been formally proven in a model of distributed
computing, heuristic arguments suggest that Protocol 1 provides mutual implicit key authenti-
cation. In addition, Protocol 1 appears to have the security attributes of known-key security,
forward secrecy, key-compromise impersonation, and key control that were listed in x2. Another
security attribute of Protocol 1 is that compromise of the ephemeral private keys (r A and r B )
reveals neither the static private keys (wA and wB ) nor the shared secret K.
Kaliski [21] has recently observed that Protocol 1 does not possess the unknown key-share
attribute. This is demonstrated by the following on-line attack. The adversary E intercepts
A's ephemeral public key RA intended for B, and computes
certified as her static public key (note that E
knows the corresponding private key wE ), and transmits RE to B. B responds by sending RB
to E, which E forwards to A. Both A and B compute the same secret K, however B mistakenly
believes that he shares K with E. We emphasize that lack of the unknown key-share attribute
does not contradict the fundamental goal of mutual implicit key authentication - by definition
the provision of implicit key authentication is only considered in the case where B engages in the
protocol with an honest entity (which E isn't). If an application using Protocol 1 is concerned
with the lack of the unknown key-share attribute under such on-line attacks, then appropriate
confirmation should be added, for example as specified in Protocol 3.
Protocol 1 can be viewed as a direct extension of the ordinary (unauthenticated) Diffie-Hellman
agreement protocol. The quantities s A and s B serve as implicit signatures for A's
ephemeral public key RA and B's ephemeral public key RB , respectively. The shared secret is
rather than r A r BP as would be the case with ordinary Diffie-Hellman.
The expression for RA uses only half the bits of the x-coordinate of RA . This was done in
order to increase the efficiency of computing K because the scalar multiplication RAWA in (4)
can be done in half the time of a full scalar multiplication. The modification does not appear
to affect the security of the protocol. The definition of RA implies that RA 6= 0; this ensures
that the contribution of the static private key wA is not being cancelled in the formation of s A
in (1).
Multiplication by h in (2) and (4) ensures that the shared secret K (see equation (5)) is a
point in the subgroup of order n in E(F q ). The check ensures that K is a finite point.
If Protocol 1 is used to agree upon a k-bit key for subsequent use in a symmetric-key block
cipher, then it is recommended that the elliptic curve be chosen so that n ? 2 2k .
Protocol 1 has all the desirable performance attributes listed in x2. From A's point of view,
the dominant computational steps in a run of Protocol 1 are the scalar multiplications r AP ,
RBWB , and hsA (RB +RBWB ). Hence the work required by each entity is 2:5 (full) scalar mul-
tiplications. Since r AP can be computed off-line by A, the on-line work required by each entity
is only 1:5 scalar multiplications. In addition, the protocol has low communication overhead,
is role-symmetric, non-interactive, and does not use encryption or timestamping. While a hash
function may be used in the key derivation function (to derive a session key from the shared
secret K), the security of Protocol 1 appears to be less reliant on the cryptographic strength of
the hash function that some other AK protocols (such as Protocol 3 in [10]). In particular, the
requirement that the key derivation function be preimage resistant appears unnecessary. Non-
reliance on hash functions is advantageous because history has shown that secure hash functions
are difficult to design.
6 Related protocols
This section presents two related protocols: a one-pass AK protocol (Protocol 2), and a three-pass
AKC protocol (Protocol 3).
6.1 One-pass authenticated key agreement protocol
The purpose of the one-pass AK protocol (Protocol 2) is for entities A and B to establish a shared
secret by only having to transmit one message from A to B. This can be useful in applications
where only one entity is on-line, such as secure email and store-and-forward. Protocol 2 is
depicted in Figure 2. It assumes that A a priori has an authentic copy of B's static public key.
Domain parameters and static keys are set up and validated as described in x3.
RA

Figure

2: One-pass AK protocol (Protocol 2)
Protocol 2.
1. A generates a random integer r A , computes the point
sends this to B.
2. A computes s
terminates the protocol run with failure.
3. B does an embedded key validation of RA (see x3.2). If the validation fails, then B
terminates the protocol run with failure. Otherwise, B computes s
n and terminates the protocol run with failure.
4. The shared secret is the point K.
Heuristic arguments suggest that Protocol 2 offers mutual implicit key authentication. The
main security drawback of Protocol 2 is that there is no known-key security and forward secrecy
since entity B does not contribute a random per-message component. Of course, this will be
the case with any one-pass key agreement protocol.
6.2 Authenticated key agreement with key confirmation protocol
We now describe the AKC variant of Protocol 1. It is depicted in Figure 3. Domain parameters
and static keys are set up and validated as described in x3. Here, MAC is a message authentication
code algorithm and is used to provide key confirmation. For examples of provably secure and
practical MAC algorithms, see Bellare, Canetti and Krawczyk [5], Bellare, Guerin and Rogaway
[6], and Bellare, Kilian and Rogaway [7]. H 1
are (independent) key derivation functions.
Practical instantiations of H 1
include H 1
Protocol 3.
1. A generates a random integer r A , computes the point
sends this to B.
2. 2.1 B does an embedded key validation of RA (see x3.2). If the validation fails, then B
terminates the protocol run with failure.
2.2 Otherwise, B generates a random integer r computes the point
RA

Figure

3: Three-pass AKC protocol (Protocol
2.3
B terminates the protocol run with failure. The shared secret is K.
2.4 B uses the x-coordinate z of the point K to compute two shared
(z) and
(z).
sends this together with RB to A.
3. 3.1 A does an embedded key validation of RB . If the validation fails, then A terminates
the protocol run with failure.
3.2 Otherwise, A computes s
terminates the protocol run with failure.
3.3 A uses the x-coordinate z of the point K to compute two shared
(z) and
(z).
3.4 A computes MAC - 0
verifies that this equals what was sent by
B.
3.5 A computes MAC - 0
sends this to B.
4. B computes MAC - 0
verifies that this equals what was sent by A.
5. The session key is -.
AKC Protocol 3 is derived from AK Protocol 1 by adding key confirmation to the latter.
This is done in exactly the same way AKC Protocol 2 of [10] was derived from AK Protocol 3 of
[10]. Protocol 2 of [10] was formally proven to be a secure AKC protocol. Heuristic arguments
suggest that Protocol 3 of this paper is a secure AKC protocol, and in addition has all the
desirable security attributes listed in x2.
7 Concluding remarks
The paper has presented new AK and AKC protocols which possess many desirable security
attributes, are extremely efficient, and appear to place less burden on the security of the key
derivation function than other proposals. Neither of the protocols proposed have been formally
proven to possess the claimed levels of security, but heuristic arguments suggest that this is the
case. It is hoped that the protocols, or appropriate modifications of them, can, under plausible
assumptions, be proven secure in the model of distributed computing introduced in [10].

Acknowledgements

The authors would like to thank Simon Blake-Wilson and Don Johnson for their comments on
earlier drafts of this paper. Ms. Law and Dr. Solinas would like to acknowledge the contributions
of their colleagues at the National Security Agency.



--R

"Minding your p's and q's"



"Keying hash functions for message authenti- cation"
"XOR MACs: New methods for message authentication using finite pseudorandom functions"
"The security of cipher block chaining"
"Random oracles are practical: a paradigm for designing efficient protocols"
"Entity authentication and key distribution"
"Key agreement protocols and their security analysis"
"On the risk of opening distributed keys"
"An improved protocol for demonstrating possession of discrete logarithms and some generalizations"
"Towards practical 'proven secure' authenticated key distri- bution"
"New directions in cryptography"
"Authentication and authenticated key ex- changes"
"A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves"
"Cryptographic method and apparatus for public key exchange with authenti- cation"
Contribution to ANSI X9F1 working group
"Authenticated multi-party key agreement"
Contribution to ANSI X9F1 and IEEE P1363 working groups
"A key recovery attack on discrete log-based schemes using a prime order subgroup"
"On seeking smart public-key distribution sys- tems"
"Reducing elliptic curve logarithms to logarithms in a finite field"
"Some new key agreement protocols providing mutual implicit authentication"
"Key agreement and the need for authentication"
Handbook of Applied Cryptography
"Secure Hash Standard (SHS)"
"Digital signature standard"
"SKIPJACK and KEA algorithm specification"
"An improved algorithm for computing logarithms over GF (p) and its cryptographic significance"
"Monte Carlo methods for index computation mod p"
"Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves"
"Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p"
"The discrete logarithm problem on elliptic curves of trace one"
"On Diffie-Hellman key agreement with short expo- nents"
"A key distribution paradox"
--TR

--CTR
Johann Groschdl , Alexander Szekely , Stefan Tillich, The energy cost of cryptographic key establishment in wireless sensor networks, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore
Kyung-Ah Shim , Sung Sik Woo, Cryptanalysis of tripartite and multi-party authenticated key agreement protocols, Information Sciences: an International Journal, v.177 n.4, p.1143-1151, February, 2007
Kyung-Ah Shim, Vulnerabilities of generalized MQV key agreement protocol without using one-way hash functions, Computer Standards & Interfaces, v.29 n.4, p.467-470, May, 2007
Maurizio Adriano Strangio, Efficient Diffie-Hellmann two-party key agreement protocols based on elliptic curves, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Mario Di Raimondo , Rosario Gennaro , Hugo Krawczyk, Secure off-the-record messaging, Proceedings of the 2005 ACM workshop on Privacy in the electronic society, November 07-07, 2005, Alexandria, VA, USA
diffie-hellman;key confirmation;authenticated key agreement;elliptic curves