CA 02581119 2007-03-30
KEY AGREEMENT AND TRANSPORT PROTOCOL
The present invention relates to key agreement
protocols for transfer and authentication of encryption
keys.
To retain privacy during the exchange of
information it is well known to encrypt data using a key.
,The key must be chosen so that the correspondents are
able to encrypt and decrypt messages but such that an
interceptor cannot determine the contents of the message.
In a secret key cryptographic protocol, the
correspondents share a common key that is secret to them.
This requires the key to be agreed upon between the
correspondents and for provision to be made to maintain
the secrecy of the key and provide for change of the key
should the underlying security be compromised.
Public key cryptographic protocols were first
proposed in 1976 by Diffie-Hellman and utilized a public
key made available to all potential correspondents and a
private key known only to the intended recipient. The
public and private keys are related such that a message
encrypted with the public key of a recipient can be
readily decrypted with the private key but the private
key cannot be derived from the knowledge of the
plaintext, ciphertext and public key.
Key establishment is the process by which two
(or more) parties establish a shared secret key, called
the session key. The session key is subsequently used to
achieve some cryptographic goal, such as privacy. There
are two kinds of key agreement protocol; key transport
CA 02581119 2007-03-30
2
protocols in which a key is created by one party and
securely transmitted to the second party; and key
agreement protocols, in which both parties contribute
information which jointly establish the shared secret
key. The number of message exchanges required between
the parties is called the number of passes. A key
establishment protocol is said to provide implicit key
authentication (or simply key authentication) if one
party is assured that no other party aside from a
specially identified second party may learn the value of
the session key. The property of implicit key
authentication does not necessarily mean that the second
party actually possesses the session key. A key
.establishment protocol is said to provide key
confirmation if one party is assured that a specially
identified second party actually has possession of a
particular session key. If the authentication is
provided to both parties involved in the protocol, then
the key authentication is said to be mutual if provided
to only one party, the authentication is said to be
unilateral.
There are various prior proposals which claim
to provide implicit key authentication.
Examples include the Nyberg-Rueppel one-pass
protocol and the Matsumoto-Takashima-Imai (MTI) and the
Goss and Yacobi two-pass protocols for key agreement.
The prior proposals ensure that transmissions
between correspondents to establish a common key are
CA 02581119 2007-03-30
3
secure and that an interloper cannot retrieve the session
key and decrypt the ciphertext. In this way security for
sensitive transactions such as transfer of funds is
provided.
For example, the MTI/A0 key agreement protocol
establishes a shared secret K, known to the two
correspondents, in the following manner:-
1. During initial, one-time setup, key generation
and publication is undertaken by selecting and
publishing an appropriate system prime p and
generator aeZp in a manner guaranteeing
authenticity. Correspondent A selects as a
long-term private key a random integer
"a",1<_a<p-2, and computes a long-term public
key ZA = a' mod p. B generates analogous keys
b, zB. A and B have access to authenticated
copies of each other's long-term public key.
2. The protocol requires the exchange of the
following messages.
A --B: a"mod p (1)
A - B: ay mod p (2)
The values of x and y remain secure during such
transmissions as it is impractical to determine the
exponent even when the value of a and the exponentiation
is known provided of course that p is chosen sufficiently
large.
CA 02581119 2007-03-30
4
3. To implement the protocol the following steps
are performed each time a shared key is
required.
(a) A chooses a random integer x,l<x<p-2, and
sends B message (1) i.e. a' mod p.
(b) B chooses a random integer y,l<y<p-2, and
sends A message (2) i.e. ay mod p.
(c) A computes the key K = (aY)'zBz mod p.
(d) B computes the key K=(a") zA y mod p.
(e) Both share the key K - ab"+".
In order to compute the key K, A must use his
secret key a and the random integer x, both of which are
known only to him. Similarly B must use her secret key b
and random integer y to compute the session key K.
Provided the secret keys a,b remain uncompromised, an
interloper cannot generate a session key identical to the
other correspondent. Accordingly, any ciphertext will
not,be decipherable by both correspondents.
As such this and related protocols have been
considered satisfactory for key establishment and
resistant to conventional eavesdropping or man-in-the-
middle attacks.
In some circumstances it may be advantageous
for an adversary to mislead one correspondent as to the
true identity of the other correspondent.
In such an attack an active adversary or
interloper E modifies messages exchanged between A and B,
CA 02581119 2007-03-30
with the result that B believes that he shares a key K
with E while A believes that she shares the same key K
with B. Even though E does not learn the value of K the
misinformation as to the identity of the correspondents
5 may be useful.
A practical scenario where such an attack may
be launched successfully is the following. Suppose that
B is a bank branch and A is an account holder.
Certificates are issued by the bank headquarters and
within the 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.
If no further authentication is done in the encrypted
deposit message (which might be the case to save
bandwidth) then the deposit will be made to E's account.
It is therefore an object of the present
invention to provide a protocol in which the above
disadvantages are obviated or mitigated.
According therefore to the present invention
there is provided a method of authenticating a pair of
correspondents A,B to permit exchange of information
therebetween, each of said correspondents having a
respective private key a,b and a public key pA,pB derived
from a generator a and respective ones of said private
keys a,b, said method including the steps of
CA 02581119 2007-03-30
6
i) a first of said correspondents A selecting a
first random integer x and exponentiating a function f(a)
including said generator to a power g(x) -to provide a first
exponentiated function f (a)Y(4;
ii) said first correspondent A forwarding to a
second correspondent B a message including said first
exponentiated function f (a)g(*;
iii) said correspondent B selecting a second random
integer y and exponentiating a function f'(a) including
said generator to a power'g(y) to provide a second
exponentiated function f'(a)$O;
iv) said second correspondent B constructing a
session key K from information made public by said first
correspondent A and information that is private to said
second correspondent B, said session key also being
constructible by said first correspondent A for
information made public by B and information that is
private to said first correspondent A;
v) said second correspondent B generating a value
h of a function F[v,K] where F[ff,K] denotes a
cryptographic function applied conjointly to zr and K and
where ir is a subset of the public information provided by
B thereby to bind the values of n and K;
vi) said second of said correspondents B forwarding
a message to said first correspondent A including said
second exponential function f' (a)g~Y) and said value h of
said cryptographic function F[v,K];
CA 02581119 2007-03-30
7
vii) said first correspondent receiving said message
and computing a session key K' from information made
public by said second correspondent B and private to said
first correspondent A;
viii) said first correspondent A computing a value h'
of a cryptographic function h,h' F[zr,K'); and
ix) comparing said values obtained from said
cryptographic functions F to confirm their
correspondence.
As the session key K can only be generated
using information that is private to either A or B, the
binding of K with n with the cryptographic function h
prevents E from extracting K or interjecting a new value
function that will correspond to that obtained by A.
Embodiments of the invention will now be
described by way of example only,with reference to the
accompanying drawings in which.
Figure 1 is a schematic representation of a
data communication system.
Referring therefore to Figure 1, a pair of
correspondents, 10,12, denoted as correspondent A and
correspondent B, exchange information over a
communication channel 14. A cryptographic unit 16,18 is
interposed between each of the correspondents 10,12 and
the channel 14. A key 20 is associated with each of the
cryptographic units 16,18 to convert plaintext carried
between each unit 16,18 and its respective correspondent
10,12 into ciphertext carried on the channel 14.
CA 02581119 2007-03-30
8
In operation, a message generated by
correspondent A, 10, is encrypted by the unit 16 with the
key 20 and transmitted as ciphertext over channel 14 to
the unit 18.
The key 20 operates upon the ciphertext in the
unit 18 to generate a plaintext message for the
correspondent B, 12. Provided the keys 20 correspond,
the message received by the correspondent 12 will be that
sent by the correspondent 10.
In order for the system shown in Figure 1 to
operate it is necessary for the keys 20 to be identical
and therefore a key agreement protocol is established
that.allows the transfer of information in a public
manner to establish the identical keys. A number of
protocols are available for such key generation and
embodiments of the present invention will be described
below in the context of modifications of existing
protocols.
A commonly used set of protocols are
collectively known as the Matsumoto-Takashima-Imai or
"MTI" key agreement protocols, and are variants of the
Diffie-Hellman key exchange. Their purpose is for
parties A and B to establish a secret session key K.
The system parameters for these protocols are a
prime number p and a generator a of the multiplicative
group Z*p. Correspondent A has private key a and public
key PA = a'. Correspondent B has private key b and public
b
key pB = a. In all four protocols exemplified below,
CA 02581119 2007-03-30
9
textA refers to a string of information that identifies
party A. If the other correspondent B possesses an
authentic copy of correspondent A's public key, then
textA will contain A's public-key certificate, issued by
a trusted center; correspondent B can use his authentic
copy of the trusted center's public key to verify
correspondent A's certificate, hence obtaining an
authentic copy of correspondent A's public key.
In each example below it is assumed that an
interloper E wishes to have messages from A identified as
having originated from E herself. To accomplish this, E
selects a random integer e, 1<e<p-2, computes pE=(pA) =a'
mod p, and gets this certified as her public key. E does
not know the exponent ae, although she knows e. By
substituting textE for textA, the correspondent B will
assume that the message originates from E rather than A
and use E's public key to generate the session key K. E
also intercepts the message from B and uses his secret
random integer e to modify its contents. A will then use
that information to generate the same session key
allowing A to communicate with B.
The present invention is exemplified by
modifications to 4 of the family of MTI protocols which
foil this new attack thereby achieving the desired
property of mutual implicit authentication. In the
modified protocols exemplified below F(X,Y) denotes a
cryptographic function applied to a string derived from x
and y. Typically and as exemplified a hash function,
CA 02581119 2007-03-30
such as the NIST "Secure Hash Algorithm"(SHA-1), is
applied to the string obtained by concatenating X and Y
but it will be understood that other cryptographic
functions may be used.
5 Example 1 - MTI/AO protocol
The existing protocol operates as follows:-
1. Correspondent A generates a random integer
x, 1<x<p-2, computes a", and sends {a",textA} to
party B.
10 2. Correspondent B generates a random integer
y, 1<y<p-2, computes aY, and sends {ay, textB} to
party A.
3. Correspondent A computes K = (ay) =(pB) _= av+b:.
4. Correspondent B computes K = (a=) b(pA) Y= a'Y+ax.
A common key K is thus obtained. However, with
this arrangement, interloper E may have messages
generated by correspondent A identified as having
originated from E in the following manner.
1. E intercepts A's message {a",textA} and replaces
it with {a",textE}. The provision of the
message textE identifies the message as having
originated at E.
2. B sends {ay,textB} to E, who then forwards
{(a'') ', textB} to A. Since A receives textB, he
assumes the message originates at B and, as he
does not know the value of y, assumes that ay
is valid information.
CA 02581119 2007-03-30
11
3. A computes K=(a'y)'(pB)" = a' y+bx.
4. B computes K = (a") b(pE),. = aw,'+bx.
5. A and B now share the key K, even though B
believes he shares a key with E.
Accordingly any further transactions from A to
B will be considered by B to have originated at E. B
will act accordingly crediting instruction to E. Even
though the interloper E does not learn the value of the
session key K nevertheless the assumption that the
message originates at E may be valuable and achieve the
desired effect.
To avoid this problem, the protocol is modified
as follows:-
1. A generates a random integer x,l<x<p-2,
computes ax, and sends {a",textA} to party B.
2. B generates a random integer y,1<y<p-2, and
computes a'', K=(a")b(pA)y=aay+bz, and a- value h of
cryptographic hash function F( or'', a'y+b=) which is
a function of public information 7r and the key
K. B sends {ay,h,textH} to party A.
3. A computes K= (a'')'(pB)" = a''+b". A also
computes a value h' of cryptographic hash
function F(ay,K) and verifies that this value is
equal to h.
If E attempts to interpose her identification,
textE, the attack fails on the modified protocols because
CA 02581119 2007-03-30
12
in each case B sends the hash value F(rr,K), where rr is
B's random exponential, ay, thereby binding together the
values of v and K. E cannot subsequently replace the
value of 7T with 7r' and compute F(rr , K) since E does not
know K. Even though E knows ay, this is not sufficient to
extract K from the hash value h. Accordingly, even if E
interposes the value ay so that the keys 20 will agree,
the values h,h' will not.
Example 2 MTI/BO protocol
In this protocol,
1. A generates a random integer x,l<x<p-2,
computes (pB)= = ab", and sends {ab",text,,} to
party B.
2. B generates a random integer y,l<y<p-2,
computes (pA) y = (z'y, and sends {a'Y, textB} to
party A.
3. A computes K = (a$Y) e-iaX=aXaY
4. B computes K = ( ab"') b-las'=aX'''
This protocol is vulnerable to the interloper E if,
1. E replaces A's message {ab",textA} with
{ab",textE} to identify herself as the originator
to the message.
2. B sends {(pE)y,textB} to E, who then computes
(( PE) y) B-1 = a''' and forwards { a'' , text$} to A.
CA 02581119 2007-03-30
13
3. A computes K = ( L1LaY) 8 laX=aX+y
4. B computes K = ( (Xb") b-l''=a"+Y
5. A and B now share the key K, even though B
believes he shares a key with E.
This protocol may be modified to resist E's attack as
follows.
1. A generates a random integer x,15xSp-2,
computes (pB) Z= abx, and sends {abz, text~} to
party B.
2. B generates a random integer y,1SySp-2, and
computes (pA)y = a'y, K = (ab") b-laY=aX'y , and
the value h of hash function F(a''', aZ+Y) . B
sends { a'y, h, textB} to A.
3. A computes K ( aay) a-iax=aX'y A also computes
the value h' of hash function F(a", K) and
verifies that this value is equal to h.
Once again, E cannot determine the session key
K and so cannot generate a new value of the hash function
to maintain the deception.
Example 3 - MTI/CO protocol
This protocol operates as follows:-
1. A generates a random integer x,l<x<p-2,
computes (pB)" = ab", and sends {ab",textA} to
party B.
2. B generates a random integer y,1<y<p-2,
computes (pA)Y = a''', and sends {aly,textB} to
party A.
CA 02581119 2007-03-30
14
3. A computes K = (aY) $_lX=axy
4. B computes K = ( abX) b-ly=a'''y
The interloper E may interpose her identity as follows:-
1. E replaces A's message {ab",textA} with
{abz, textE} .
2. B sends {(pE)r,textB} to E, who then computes
((pE) Y) o-l = a"' and forwards {a'y, textB} to A.
3. A computes K = (aaY) a-lX=a"'3'
4. B computes K = (ab"') b-ly=a"3'
5. A and B now share the key K, even though B
believes he shares a-key with E.
To avoid this attack protocol is modified as follows:-
1. A generates a random integer x,1<x<p-2,
computes (pB)" = ab", and sends {ab", textA} to
party B.
2. B generates a random integer y,l<y<p-2, and
computes (PA) y= a'y, K = (abx) b-'y=a"y and value
h of hash function F(a", a"Y) . B sends
{a'y, h, textB} to party A.
3. A computes K = (a8y) a-lX=a"'' . A also computes
the value h' of F(a",K) and verifies that this
value is equal to h.
CA 02581119 2007-03-30
Example 4 - MTI/C1 protocol
In this protocol:-
1. A generates a random integer x,1<x<p-2,
computes (pB)' = a'b", and sends {a'bz, text,,} to
5 party B.
2. B generates a random integer y,l<y<p-2,
computes (pA) by = a'bY, and sends {a'by, textB} to
party A.
3. A computes K = (a'b'')" = aabxy.
10 4. B computes K = (aabz) Y = a'bv.
E can act as an interloper as follows:-
1. E replaces A's message {a'bz,textA} with
{ a'bx, textE}
15 2. B sends {(pE)by,textB} to E, who then computes
((pE) "s')o-1 = a'y and forwards {a'by, textB} to A.
3. A computes K = (aae'')" = a'b"''.
4. B computes K = (aA")Y = a'b"y.
5. A and B now share the key K, even though B
believes he shares a key with E.
To avoid this, the protocol is modified as follows:-
1. A generates a random integer x,1<x<p-2,
computes (pB) x = a'b", and sends { cz'b", textA} to
party B.
2. B generates a random integer y,l<y<p-2, and
computes (p,,)b'' = aie'',K = (a'b")y = a'b'n, and
CA 02581119 2007-03-30
16
h = F(a'b'',a bxy) . B sends {aRbY,h,textB} to party
A.
3. A computes K (a'by)" = a"Y. A also computes
h' = F(a'by,K) and verifies that this value is
equal to h.
In each of the modified protocols discussed
above, key confirmation from B to A is provided.
As noted above instead of F being a
cryptographic hash function other functions could be
used. For example, an option available is to choose
F = eK, where E is the encryption function of a suitable
symmetric-key encryption scheme, and K is the session key
established. Because E cannot generate the session key
K, it is similarly not able to generate the value of the
function F and therefore cannot interpose for the
correspondent A.
The technique described above can be applied to
other similar key exchange protocols, including all of
the 3 infinite classes of MTI protocols called MTI-A(k),
MTI-B(k) and MTI-C(k).
The Goss authenticated key exchange protocol is
similar to the MTI/A0 protocol, except that the session
key is the bitwise exclusive-OR of a'y' and ab"; that is K
a'Y ab" instead of being the product of a'' and ab". Hence
the attack on the MTI/A0 protocol and its modification
can be extended in a straightforward manner to the case
of the Goss protocol.
CA 02581119 2007-03-30
17
Similarly Yacobi's authenticated key exchange
protocol is exactly the same as the MTI/AO protocol,
except that a is an element of the group of units Z'õ
where n is the product of 2 large primes. Again, the
attack on the MTI/A0 protocol and its modification can be
extended in a straightforward manner to the case of the
Goss protocol.
A further way of foiling the interposition of E
is to require that each entity prove to a trusted center
that it knows the exponent of a that produces its public
key P, before the center issues a certificate for the
public key. Because E only knows "e" and not "ae" it
would not meet this requirement. This can be achieved
through zero knowledge techniques to protect the secrecy
of the private keys but also requires the availability of
a trusted centre which may not be convenient.
Each of the above examples has been described
with a 2 pass protocol for key authentication. One pass
protocols also exist to establish a key between
correspondents and may be similarly vulnerable.
As an example the Nyberg-Rueppel one pass key
agreement protocol will be described and a modification
proposed.
The purpose of this protocol is for party A and
party B to agree upon a secret session key K.
The system parameters for these protocols are a
prime number p and a generator a of the multiplicative
group Z. User A has private key a and public key
CA 02581119 2007-03-30
18
pA = a'. User B has private key b and public key pB = ab.
1. A selects random integers x and t, 1<x,t<p-2.
2. A computes r = (pB) 'a-' mod p and s = x - ra mod
(p-1), and sends {r,s,textA} to B.
3. B recovers the value ax mod'p by computing
a'(pA)' mod p and then computes the shared
session key K (raX)b-1 = ar mod p.
If interloper E wishes to have messages from A
identified as having originated from herself, E selects a
random integer e, l<e<p-2, computes p$ = a , and gets this
certified as her public key.
1. E intercepts A's message {r,s,textA} and
computes ax = a' (pA) r and ab' = ra".
2. E then selects a random integer x', i<x'<p-2,
computes r'= abta-"l mod p and s'=x'-r'e mod
(P-1).
3. E sends {r',s',textE} to B.
4. B recovers the value ak' mod p by computing
a''(pE) " mod p and then computes K (r /a"') b-1=a t
mod p.
5. A and B now share the key K, even though B
believes he shares a key with E.
To foil such an attack the protocol is modified
by requiring A to also transmit a value h of F(pA,K),
where F is a hash function, an encryption function of a
symmetric-key system with key K or other suitable
CA 02581119 2007-03-30
19
cryptographic function. The modified protocol is the
following.
1. A selects random integers x and t, 1<x,t<p-2.
2. A computes r = (pB) 'CZ-" mod p, s = x - ra mod
(p-1), session key K = a' mcd p and the value h
of hash function F(pA,K). A sends {r,s,h,textA}
to B.
3. B recovers the value a' mod p by computing
a' (põ) ' mod p and then computes the shared
session key K (ra")b-1 = at mod p. B also
computes the value h' of function F(pA,K) and
verifies that this value is equal to h.
Again therefore by binding together the public
information n and the session key K in the hash function,
the interposition of E will not result in identical hash
functions h,h'.
. In each case it can be seen that a relatively
simple modification to the protocols involving the
binding of public and private information in a
cryptographic function foils the interposition of
interloper E.
All the protocols discussed above have been
described in the setting of the multiplicative group Z*P.
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 (in particular the
f inite f ield GF ( 2 ) , subgroups of Z'P of order q, and the
CA 02581119 2007-03-30
group of points on an elliptic curve defined over a
finite field. In each case an appropriate generator a
will be used to define the public keys.
The protocols discussed above can also be
5 modified in a straightforward way to handle the situation
when each user picks their own system parameters p and a
(or analogous parameters if a group other than Z'Pis
used).
