CA2236495C - Authenticated key agreement protocol - Google Patents
Authenticated key agreement protocol Download PDFInfo
- Publication number
- CA2236495C CA2236495C CA 2236495 CA2236495A CA2236495C CA 2236495 C CA2236495 C CA 2236495C CA 2236495 CA2236495 CA 2236495 CA 2236495 A CA2236495 A CA 2236495A CA 2236495 C CA2236495 C CA 2236495C
- Authority
- CA
- Canada
- Prior art keywords
- entity
- key
- public
- private
- session value
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
- H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
- H04L9/0838—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these
- H04L9/0841—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these involving Diffie-Hellman or related key agreement protocols
- H04L9/0844—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these involving Diffie-Hellman or related key agreement protocols with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Computer And Data Communications (AREA)
- Communication Control (AREA)
Abstract
A key agreement method between a pair of entities i and j in a digital data communication system, wherein each entity has a private and corresponding public key pair S i,P i and S j,P j respectively and the system, having global parameters for generating elements of a group, the method comprising the steps of: (a) entity i selecting a random private session value R i; (b) forwarding a public session value corresponding to the private session value R i to the entity j; (c) entity j computing a long term shared secret key k' derived from entity i's public key and j's private key utilizing a first function H i; (d) the entity j utilizing entity j utilizing the key k' and computing an authenticated message on entity identities i, j and entities public session keys and forwarding the authenticated message to entity i; (e) the entity i verifying the received authenticated message; (f) the entity i computing the long term shared secret key k' derived from the entity j's public key and i's private key in accordance with the first function H i; (g) the entity i utilizing the long term shared secret key k' and computing an authenticated message on the entities i and j identity information and the entities public session keys and forwarding the authenticated message to the entity j; (h) entity j verifying the received authenticated message; and (i) upon both the entities i and j verifying the authenticated message, computing a short term shared secret key utilizing a respective entity's session public and private keys.
Description
AUTHENTICATED KEY AGREEMENT PROTOCOL
This invention relates to cryptographic systems and in particular, to authenticated key agreement protocols used in the cryptographic systems.
A key agreement problem exists when two entities wish to agree on keying information in secret over a distributed network. Solutions to the key agreement problem whose security is bas,ed on a Diffie-Hellman problem in finite groups have been used extensively.
Suppose however, that entity i wishes to agree on secret keying information with entity j.
Each party desires an assurance that no party, other than i andj, can possibly compute the keying infermation agreed upon. This may be termed the authenticated key agreement (AK) problein.
Clearly, this problem is harder than the key agreement problem in which i does not care which entity it is agreeing on a key with, for in this problem i stipulates that the key may be shared with j and no other entity.
Several techniques related to the Diffie-Hellman problem have been proposed to solve the AK problem. However, no practical solutions have been provably demonstrated to achieve this goal and this deficiency has led, in many cases, to the use of flawed protocols.
Since in the AK problem, i merely desires that only j can possibly compute the key and not that j has actually computed the key, solutions are often said to provide implicit (key) authentication. If i wants to make sure, in addition, that j really has computed the agreed key, then key confirmation is incorporated into the key agreement protocol leading to so-called explicit authentication. The resulting goal is called authenticated key agreement with key coiifirmation (AKC). It may be seen that key confirmation essentially adds the assurance t:hat i really is communicating withj. Thus, the goal of key confirmation is similar to the goal of entity authentication as defined in Diffie-Hellman. More precisely however, the incorporation of entity authentication into the AKA protocol provides i the additional assurance that j can compute the key, rather than the stronger assurance that j has actually computed the key.
A number of distinct types of attacks have been proposed against previous schemes.
There are two major attacks which a protocol should withstand. The first is a passive attack, where an adversary attempts to prevent a protocol from achieving its goal by merely observing honest entities carrying out the protocol. The second is an active attack where an adversary adclitionally subverts the communication themselves in any way possible by injecting messages, intercepting messages, replaying messages, altering messages and the like.
It is thus essential for any secure protocol to withstand both passive and active attacks since an adversary can reasonably be assumed to have these capabilities in a distributed network.
It is therefore desirable to provide a key agreement protocol that mitigates at least some of the above advantages.
SUMMARY OF THE INVENTION
A key agreement method between a pair of entities i and j in a digital data cornmunication system, wherein each said entity has a private and corresponding public key pairs S;, P; and Sj,Pj respectively and the system, having global parameters for generating elements of a group, said method comprising the steps of:
(a) entity i selecting a random private session value R;;
(b) forwarding a public session value corresponding to said private session value R;
to said entity j;
(c) entityj computing a long term shared secret key k' derived from entity i's public key andj's private key utilizing a first function H1;
(d) said entityj utilizing entityj utilizing said key k' and computing an authenticated message on entity identities i, j and entities public session keys and forwarding said authenticated message to entity i;
(e) said entity i verifying said received authenticated message;
(f) said entity i computing said long term shared secret key k' derived from said entityj's public key and i's private key in accordance with said first function :H1;
(g) said entity i utilizing said long term shared secret key k' and computing an authenticated message on said entities i and j identity information and said entities public session keys and forwarding said authenticated message to said entityj;
(h) entity j verifying said received authenticated message; and (i) upon both said entities i and j verifying said authenticated message, computing a short term shared secret key utilizing a respective entity's session public and private keys.
This invention relates to cryptographic systems and in particular, to authenticated key agreement protocols used in the cryptographic systems.
A key agreement problem exists when two entities wish to agree on keying information in secret over a distributed network. Solutions to the key agreement problem whose security is bas,ed on a Diffie-Hellman problem in finite groups have been used extensively.
Suppose however, that entity i wishes to agree on secret keying information with entity j.
Each party desires an assurance that no party, other than i andj, can possibly compute the keying infermation agreed upon. This may be termed the authenticated key agreement (AK) problein.
Clearly, this problem is harder than the key agreement problem in which i does not care which entity it is agreeing on a key with, for in this problem i stipulates that the key may be shared with j and no other entity.
Several techniques related to the Diffie-Hellman problem have been proposed to solve the AK problem. However, no practical solutions have been provably demonstrated to achieve this goal and this deficiency has led, in many cases, to the use of flawed protocols.
Since in the AK problem, i merely desires that only j can possibly compute the key and not that j has actually computed the key, solutions are often said to provide implicit (key) authentication. If i wants to make sure, in addition, that j really has computed the agreed key, then key confirmation is incorporated into the key agreement protocol leading to so-called explicit authentication. The resulting goal is called authenticated key agreement with key coiifirmation (AKC). It may be seen that key confirmation essentially adds the assurance t:hat i really is communicating withj. Thus, the goal of key confirmation is similar to the goal of entity authentication as defined in Diffie-Hellman. More precisely however, the incorporation of entity authentication into the AKA protocol provides i the additional assurance that j can compute the key, rather than the stronger assurance that j has actually computed the key.
A number of distinct types of attacks have been proposed against previous schemes.
There are two major attacks which a protocol should withstand. The first is a passive attack, where an adversary attempts to prevent a protocol from achieving its goal by merely observing honest entities carrying out the protocol. The second is an active attack where an adversary adclitionally subverts the communication themselves in any way possible by injecting messages, intercepting messages, replaying messages, altering messages and the like.
It is thus essential for any secure protocol to withstand both passive and active attacks since an adversary can reasonably be assumed to have these capabilities in a distributed network.
It is therefore desirable to provide a key agreement protocol that mitigates at least some of the above advantages.
SUMMARY OF THE INVENTION
A key agreement method between a pair of entities i and j in a digital data cornmunication system, wherein each said entity has a private and corresponding public key pairs S;, P; and Sj,Pj respectively and the system, having global parameters for generating elements of a group, said method comprising the steps of:
(a) entity i selecting a random private session value R;;
(b) forwarding a public session value corresponding to said private session value R;
to said entity j;
(c) entityj computing a long term shared secret key k' derived from entity i's public key andj's private key utilizing a first function H1;
(d) said entityj utilizing entityj utilizing said key k' and computing an authenticated message on entity identities i, j and entities public session keys and forwarding said authenticated message to entity i;
(e) said entity i verifying said received authenticated message;
(f) said entity i computing said long term shared secret key k' derived from said entityj's public key and i's private key in accordance with said first function :H1;
(g) said entity i utilizing said long term shared secret key k' and computing an authenticated message on said entities i and j identity information and said entities public session keys and forwarding said authenticated message to said entityj;
(h) entity j verifying said received authenticated message; and (i) upon both said entities i and j verifying said authenticated message, computing a short term shared secret key utilizing a respective entity's session public and private keys.
BRIEF DESCRIPTION OF TI-IE DRAWINGS ' These and other features of the preferred embodiments of the invention will become more apparent in the following detailed description in which reference is made to the appended dra.wings wherein:
Figure I is a schematic diagram of a digital data communication system;
Figure 2, 3; 4 and 5, are embodiments of a key agreement protocol according to the presentinvention.
DFSCBIPTTON OF THE PREFERRED F.MBODIlvDrNTS
In the foIlowing discussion, the notation as outlined below is utilized and descn'bed more fitlly in the DifSe-Hellman paper entitled "New Directions in Cryptography", IEEE Transactions on Information Theory, November 1976.
Referring to figm-e 1, a data communication system 10 includes a pair of entities or correspondents, desigaated as a sender i and a recipient j who are connected by a communication chaane116. Each of the correspondents, i and j inclixles an encryption unit 18,20 that may process digital infonmation and prepare it for tmis*+++ss+on through c1amel 16 as will be described below. Furthermore, the encryption units may be either a dedicated processor or a general purpose processor includin.g software for programming the general purpose computcr to perform specific cryptographic functions.
in the following discussion, kj is i's key pair kt together withj"s public value, and a transcript of the ord.ered set of messages h-ansmitted and received by i andj is used to arrive at the agreed key.
The protocols are descn'bed in terms of arithmetic operations in a subgroup generated by an element a of piime order q in the multiplicative group Z' p-1} where p is a prime. In each case, an entity's .private value is an element SpfZ,, ={1,2,..q -1} , and the corresponding public value is Pj = a" M'OD'2, so that r"s key pair is K,, =(S!, Pi ). It is to be noted that the protocols can be descdbed eqmIly well in terms of the arirhmetic operations ia any finite group and, of course, this would require the conversion of the seciaity assumptions on the Diffie-Hellman problem to that group.
FurthermQore, any particular rum of a protocol is caIled a session. Fqr example, the keying information agreed in the course of a protocol run is referred to as a session key. The individual messages that form a protocol rizn are called flows.
The protocols as described below employ various primitives. Of these primitives, the:
two primitives used are message authentication codes (MAC) and Diffie-Hellman schemes (Dl3S). Of course, some applications may wish to use another primitive to achieve confirmation.
For example, if the agreed session key is later to be used for encryption, it seems sensible to employ an encryption scheme to achieve key confirmation rather than waste time implementing a MAC.
Referring now to figure 2, a graphical representation of a first embodiment of an AKC
protocol (Protocol 1) according to the present invention is shown generally by the numeral 22.
We use E R to denote an element chosen independently at random, and commas to denote a unique encoding through concatenation (or any other unique encoding). Let H, and H 2 represent independent random oracles and (p, q, a) are global parameters. The random oracles may be defined in terms of coin tosses in the following way. It is assumed that all parties are provided with a black-box random function H(.) :{0,1}k _> {0,1k }. When H is queried for the first time, say on string x, it returns the string of length k corresponding to its first k coin tosses as H(x).
Wlien queried with a second string say x', first H compares x and x'. If x' =
n, H again ret.urns its first k coin tosses H(n). Otherwise H returns its second k tosses as H(x'). In instantiations, H
is generally modeled by a hash function H. When entity i wishes to initiate a run of P with the entityj, i selects an element at random R; ER Zq and sends a R' to j. On receipt of this stringõ j checks that 2<- ex R, <- p-1 and (a R)v =1, then j chooses Ri E R Zy , and computes a Ri and k' == H, (a"'i ). Finally,, j uses k' to compute MACk. (2, i, j, a`?' , a`~' ), and sends this authenticated message to i. (Recall that MACk.(m) represents the pair (m,a), not just the tag a). On receipt of this string, i checks that the form of this message is correct, and that 2<-aR' <- p-1 and (a'4j Y = 1. The entity i then computes k'= H, (a'''' ), recall that a" is j's long term public key, an<i verifies the authenticated message it received. If so, i accepts, and sends back to j AL4Ck, (3, i, j, aR' , a R' ). Upon receipt of this string, j checks the form of the message, verifies the authenticated message, and accepts. Both parties compute the agreed session key as k= H2 (a R'R' ). [f at any stage, a check or verification performed by f or j fails, then that party terminates the protocol run, and rejects.
In practice, entity i may wish to append its identity to the first flow of Protocol 1. We omit this identity because certain applications may desire to identify the entities involved at the packet level rather than the message level - in this instance, identifying i again is therefore superfluous.
Note that entities use two distinct keys in Protocol 1 - one key for confirmation and a different key as the session key for subsequent use. In particular, the common practice of using the same key for both confirmation and as the session key may be disadvantageous if this means thc same key is used by more than one pruaitive.
Protocol 1 is different from most proposed AKC protocols in the manner that entities employ their long-te=jn secret values and session-specific secret values. Most proposed protocols use both long-term secrets and short-term secrets in the formation of all keys. In Protocol 1, long-term secrets and short-term secrets are used in quite independent ways. Long-term secrets are used only to form a session-independent confirmation key and short-term secrets only to form the agreed session key. Conceptually, this approach has both advantages and disadvantages over more traditional techniques. On the plus side, the use of long-term keys and short-term keys is distinct, serving to clarify the effects of a key compromise - compromise of a long-term secret is fatal to the security of firiure sessions, and must be remedied immediately, whereas compromise of a short-term secret effects only that particular session. On the negative side, both entities must maintain a long-temn shared secret key k' in Protocol 1.
Protocol 2.
Protocol 2 is an AKC protocol designed to deal with some of the disadvantages of Protocoll. It is represented graphically in figure 3. The actions performed by entities i andj are similar to those of Protocol 1, except that the entities use both their short-term and long-term values in the computation of both the keys they employ. Specifically, the entities use k' = H, (a R`R' , a S'S' ) as their MAC key for this session, and k = Hz (a P'R' , a s's' ) as the agreed session key. Unlike Protocol 1, both long-term secrets and both short-term secrets are used in Pmtocol 2 to form each key. While this makes the effect of a compromise of one of these values less clear, it also means that there is no long-term shared key used to MAC
messages in every session between i and j. However, the two entities do still share a long-term secret value a s,s This value must therefore be carefully guarded against compromise, along with S; and Sj themselves. Conceptually, it is possible to separate the AK phase and the key confirmation phase in Protocol 2.
Protocol 3. An embodiment of a secure AK protocol is illustrated in figure 4 which shows a graphical representation of the actions taken by i and j in a run of Protocol 3. To see that Protocol 3 is not a secure AK protocol if an adversary can reveal unconfirmed session keys, nol:ice the following attack. E begins two runs of the protocol, one with II;
j , and one with 17; j.
Suppose II; ~ sends a R. , and II; ~ sends a R'i . E now forwards a R` to II
J, and a R'i to II j.
E can now discover the session key k = Hz (aR'R' , as's' ) held by II; ~ by revealing the (same) key held by II; j .
In this protocol, care must be taken when separating authenticated key agreement froin key confirmation. Protocol 3 above is not a secure AK protocol in the full model of distributed cornputing, but can nonetheless be turned into a secure AKC protocol, as in Protocol 2. At issue here is whether it is realistic to expect that an adversary can learn keys that have not been confirmed.
Therefore, in this description we have tried to separate the goals of AK and AKC. A
reason we have endeavored to separate authenticated key agreement from key confirmation is to allow flexibility in how a particular implementation chooses to achieve key confirmation. For ex~unple, architectural considerations may require key agreement and key confirmation to be separated - some systems may provide key confirmation during a`real-time' telephone coiiversation subsequent to agreeing a session key over a computer network, while others may instead prefer to carry out confirmation implicitly by using the key to encrypt later communications.
The reason that we have specified the use of a subgroup of prime order by the DHSs iis to avoid various known session key attacks on AK protocols that exploit the fact that a key may be forced to lie in a small subgroup of Z p. From the point of view of the security proofs, we could equally well have made assumptions about DHSs defined in Z p rather than a subgroup of Z *
p.
Figure I is a schematic diagram of a digital data communication system;
Figure 2, 3; 4 and 5, are embodiments of a key agreement protocol according to the presentinvention.
DFSCBIPTTON OF THE PREFERRED F.MBODIlvDrNTS
In the foIlowing discussion, the notation as outlined below is utilized and descn'bed more fitlly in the DifSe-Hellman paper entitled "New Directions in Cryptography", IEEE Transactions on Information Theory, November 1976.
Referring to figm-e 1, a data communication system 10 includes a pair of entities or correspondents, desigaated as a sender i and a recipient j who are connected by a communication chaane116. Each of the correspondents, i and j inclixles an encryption unit 18,20 that may process digital infonmation and prepare it for tmis*+++ss+on through c1amel 16 as will be described below. Furthermore, the encryption units may be either a dedicated processor or a general purpose processor includin.g software for programming the general purpose computcr to perform specific cryptographic functions.
in the following discussion, kj is i's key pair kt together withj"s public value, and a transcript of the ord.ered set of messages h-ansmitted and received by i andj is used to arrive at the agreed key.
The protocols are descn'bed in terms of arithmetic operations in a subgroup generated by an element a of piime order q in the multiplicative group Z' p-1} where p is a prime. In each case, an entity's .private value is an element SpfZ,, ={1,2,..q -1} , and the corresponding public value is Pj = a" M'OD'2, so that r"s key pair is K,, =(S!, Pi ). It is to be noted that the protocols can be descdbed eqmIly well in terms of the arirhmetic operations ia any finite group and, of course, this would require the conversion of the seciaity assumptions on the Diffie-Hellman problem to that group.
FurthermQore, any particular rum of a protocol is caIled a session. Fqr example, the keying information agreed in the course of a protocol run is referred to as a session key. The individual messages that form a protocol rizn are called flows.
The protocols as described below employ various primitives. Of these primitives, the:
two primitives used are message authentication codes (MAC) and Diffie-Hellman schemes (Dl3S). Of course, some applications may wish to use another primitive to achieve confirmation.
For example, if the agreed session key is later to be used for encryption, it seems sensible to employ an encryption scheme to achieve key confirmation rather than waste time implementing a MAC.
Referring now to figure 2, a graphical representation of a first embodiment of an AKC
protocol (Protocol 1) according to the present invention is shown generally by the numeral 22.
We use E R to denote an element chosen independently at random, and commas to denote a unique encoding through concatenation (or any other unique encoding). Let H, and H 2 represent independent random oracles and (p, q, a) are global parameters. The random oracles may be defined in terms of coin tosses in the following way. It is assumed that all parties are provided with a black-box random function H(.) :{0,1}k _> {0,1k }. When H is queried for the first time, say on string x, it returns the string of length k corresponding to its first k coin tosses as H(x).
Wlien queried with a second string say x', first H compares x and x'. If x' =
n, H again ret.urns its first k coin tosses H(n). Otherwise H returns its second k tosses as H(x'). In instantiations, H
is generally modeled by a hash function H. When entity i wishes to initiate a run of P with the entityj, i selects an element at random R; ER Zq and sends a R' to j. On receipt of this stringõ j checks that 2<- ex R, <- p-1 and (a R)v =1, then j chooses Ri E R Zy , and computes a Ri and k' == H, (a"'i ). Finally,, j uses k' to compute MACk. (2, i, j, a`?' , a`~' ), and sends this authenticated message to i. (Recall that MACk.(m) represents the pair (m,a), not just the tag a). On receipt of this string, i checks that the form of this message is correct, and that 2<-aR' <- p-1 and (a'4j Y = 1. The entity i then computes k'= H, (a'''' ), recall that a" is j's long term public key, an<i verifies the authenticated message it received. If so, i accepts, and sends back to j AL4Ck, (3, i, j, aR' , a R' ). Upon receipt of this string, j checks the form of the message, verifies the authenticated message, and accepts. Both parties compute the agreed session key as k= H2 (a R'R' ). [f at any stage, a check or verification performed by f or j fails, then that party terminates the protocol run, and rejects.
In practice, entity i may wish to append its identity to the first flow of Protocol 1. We omit this identity because certain applications may desire to identify the entities involved at the packet level rather than the message level - in this instance, identifying i again is therefore superfluous.
Note that entities use two distinct keys in Protocol 1 - one key for confirmation and a different key as the session key for subsequent use. In particular, the common practice of using the same key for both confirmation and as the session key may be disadvantageous if this means thc same key is used by more than one pruaitive.
Protocol 1 is different from most proposed AKC protocols in the manner that entities employ their long-te=jn secret values and session-specific secret values. Most proposed protocols use both long-term secrets and short-term secrets in the formation of all keys. In Protocol 1, long-term secrets and short-term secrets are used in quite independent ways. Long-term secrets are used only to form a session-independent confirmation key and short-term secrets only to form the agreed session key. Conceptually, this approach has both advantages and disadvantages over more traditional techniques. On the plus side, the use of long-term keys and short-term keys is distinct, serving to clarify the effects of a key compromise - compromise of a long-term secret is fatal to the security of firiure sessions, and must be remedied immediately, whereas compromise of a short-term secret effects only that particular session. On the negative side, both entities must maintain a long-temn shared secret key k' in Protocol 1.
Protocol 2.
Protocol 2 is an AKC protocol designed to deal with some of the disadvantages of Protocoll. It is represented graphically in figure 3. The actions performed by entities i andj are similar to those of Protocol 1, except that the entities use both their short-term and long-term values in the computation of both the keys they employ. Specifically, the entities use k' = H, (a R`R' , a S'S' ) as their MAC key for this session, and k = Hz (a P'R' , a s's' ) as the agreed session key. Unlike Protocol 1, both long-term secrets and both short-term secrets are used in Pmtocol 2 to form each key. While this makes the effect of a compromise of one of these values less clear, it also means that there is no long-term shared key used to MAC
messages in every session between i and j. However, the two entities do still share a long-term secret value a s,s This value must therefore be carefully guarded against compromise, along with S; and Sj themselves. Conceptually, it is possible to separate the AK phase and the key confirmation phase in Protocol 2.
Protocol 3. An embodiment of a secure AK protocol is illustrated in figure 4 which shows a graphical representation of the actions taken by i and j in a run of Protocol 3. To see that Protocol 3 is not a secure AK protocol if an adversary can reveal unconfirmed session keys, nol:ice the following attack. E begins two runs of the protocol, one with II;
j , and one with 17; j.
Suppose II; ~ sends a R. , and II; ~ sends a R'i . E now forwards a R` to II
J, and a R'i to II j.
E can now discover the session key k = Hz (aR'R' , as's' ) held by II; ~ by revealing the (same) key held by II; j .
In this protocol, care must be taken when separating authenticated key agreement froin key confirmation. Protocol 3 above is not a secure AK protocol in the full model of distributed cornputing, but can nonetheless be turned into a secure AKC protocol, as in Protocol 2. At issue here is whether it is realistic to expect that an adversary can learn keys that have not been confirmed.
Therefore, in this description we have tried to separate the goals of AK and AKC. A
reason we have endeavored to separate authenticated key agreement from key confirmation is to allow flexibility in how a particular implementation chooses to achieve key confirmation. For ex~unple, architectural considerations may require key agreement and key confirmation to be separated - some systems may provide key confirmation during a`real-time' telephone coiiversation subsequent to agreeing a session key over a computer network, while others may instead prefer to carry out confirmation implicitly by using the key to encrypt later communications.
The reason that we have specified the use of a subgroup of prime order by the DHSs iis to avoid various known session key attacks on AK protocols that exploit the fact that a key may be forced to lie in a small subgroup of Z p. From the point of view of the security proofs, we could equally well have made assumptions about DHSs defined in Z p rather than a subgroup of Z *
p.
It may be noted in particular that, as is the case with Protocol 3, many previous AK
protocols do riot contain asymmetry in the formation of the agreed key to distinguish which entity involved is the protocol's initiator, and which is the protocol's responder.
Protocol 4. Again, in this protocol instead of describing the actions of i andj verbally, we illustrate these actions in figure 5. While at first glance, Protocol 4 may look almost identical to the well-known MTI protocol, where the shared value computed is as;R;+s,,e;
, notice the following important distinction. Entity i calculates a different key in Protocol 4 depending on whether i believes it is the initiator or responder. In the first case, i computes k== H, (aSR', aS'R' ), and in the second case k = H2 (a s'R' , as`R' ) As we noted above, such asymmetry is desirable in a secure AK protocol. Of course, such asymmetry is not always desirable -- a particular environment may require that i calculate the same key no matter whether i is the initiator or responder.
If indeed it can be shown that Protocol 4 is a secure AK protocol, then it can be turned into a secure AKC protocol in the same spirit as Protocol 2.
One issue is how to instantiate the random oracles H, and HZ. A hash function such as SHA-1 should provide sufficient security for most applications. It can be used in various ways to provide instantiations of independent random oracles. For example, an implementation of' Protocol 1 may choose to use:
H, (x) := SHA -1(01, x) and H Z(x) := SHA -1(10, x) A particularly efficient instantiation of the random oracles used in Protocol 2 is possible using SHA-l or RIPEMD-160. Suppose 80-bit session keys and MAC keys are required.
Then the first 80 bits of SHA -1(a R`x' , as'S' ) can be used as k' and the second 80 bits used as k. Of coiirse, such efficient implementations may not offer the highest conceivable security assuraiice of any instantiation.
It is easy to make bandwidth savings in implementations of the AKC protocols.
Instead of sending the full authenticated messages (m,a) in flows 2 or 3, in both cases the entity can omit much of m, leaving the remainder of the message to be inferred by its recipient.
In some applications, it may not be desirable to carry out a protocol run each time a new session key is desired. Considering specifically Protocol 2 by way of example, entities may wish to compute the agreed key as:
protocols do riot contain asymmetry in the formation of the agreed key to distinguish which entity involved is the protocol's initiator, and which is the protocol's responder.
Protocol 4. Again, in this protocol instead of describing the actions of i andj verbally, we illustrate these actions in figure 5. While at first glance, Protocol 4 may look almost identical to the well-known MTI protocol, where the shared value computed is as;R;+s,,e;
, notice the following important distinction. Entity i calculates a different key in Protocol 4 depending on whether i believes it is the initiator or responder. In the first case, i computes k== H, (aSR', aS'R' ), and in the second case k = H2 (a s'R' , as`R' ) As we noted above, such asymmetry is desirable in a secure AK protocol. Of course, such asymmetry is not always desirable -- a particular environment may require that i calculate the same key no matter whether i is the initiator or responder.
If indeed it can be shown that Protocol 4 is a secure AK protocol, then it can be turned into a secure AKC protocol in the same spirit as Protocol 2.
One issue is how to instantiate the random oracles H, and HZ. A hash function such as SHA-1 should provide sufficient security for most applications. It can be used in various ways to provide instantiations of independent random oracles. For example, an implementation of' Protocol 1 may choose to use:
H, (x) := SHA -1(01, x) and H Z(x) := SHA -1(10, x) A particularly efficient instantiation of the random oracles used in Protocol 2 is possible using SHA-l or RIPEMD-160. Suppose 80-bit session keys and MAC keys are required.
Then the first 80 bits of SHA -1(a R`x' , as'S' ) can be used as k' and the second 80 bits used as k. Of coiirse, such efficient implementations may not offer the highest conceivable security assuraiice of any instantiation.
It is easy to make bandwidth savings in implementations of the AKC protocols.
Instead of sending the full authenticated messages (m,a) in flows 2 or 3, in both cases the entity can omit much of m, leaving the remainder of the message to be inferred by its recipient.
In some applications, it may not be desirable to carry out a protocol run each time a new session key is desired. Considering specifically Protocol 2 by way of example, entities may wish to compute the agreed key as:
H Z(a r R' , a s'S' , counter) Then, instead of running the whole protocol each time a new key is desired, most of the tirrie the counter is simply incremented. Entities need then only to resort to using the protocol itself every now and then to gain some extra confidence in the `freshness' of the session keys they're using.
In Protocols 1, 2, and 3, performance and security reasons may make it desirable to use a larger (and presumably more secure) group for the static Diffie-Hellman number (a, S'S' ) than for the ephemeral Diffie-Hellman number (aZRR' ) calculation. The larger group is desirable because the static number will be used more often. The static numbers may be cached to provide a speed up in session key calculation.
Finally, note that a practical instantiation of G (assume G generates key pairs for each entity) using certificates should check knowledge of the secret value before issuing a certificate on the corresponding public value. We believe that this is a sensible precaution in any implementation of a Certification Hierarchy.
While the invention has been described in connection with the specific embodiment thereof, and in a specific use, various modifications thereof will occur to those skilled in the art without departing from the spirit of the invention as set forth in the appended claims. For example, each entity will usually generate key pairs itself and then get them certified by a certification authority.
The terms and expressions which have been employed in this specification are used as terms of description and not of limitations, there is no intention in the use of such terms and expressions to exclude any equivalence of the features shown and described or portions thereof, but it is recognized that various modifications are possible within the scope of the claims to the invention.
In Protocols 1, 2, and 3, performance and security reasons may make it desirable to use a larger (and presumably more secure) group for the static Diffie-Hellman number (a, S'S' ) than for the ephemeral Diffie-Hellman number (aZRR' ) calculation. The larger group is desirable because the static number will be used more often. The static numbers may be cached to provide a speed up in session key calculation.
Finally, note that a practical instantiation of G (assume G generates key pairs for each entity) using certificates should check knowledge of the secret value before issuing a certificate on the corresponding public value. We believe that this is a sensible precaution in any implementation of a Certification Hierarchy.
While the invention has been described in connection with the specific embodiment thereof, and in a specific use, various modifications thereof will occur to those skilled in the art without departing from the spirit of the invention as set forth in the appended claims. For example, each entity will usually generate key pairs itself and then get them certified by a certification authority.
The terms and expressions which have been employed in this specification are used as terms of description and not of limitations, there is no intention in the use of such terms and expressions to exclude any equivalence of the features shown and described or portions thereof, but it is recognized that various modifications are possible within the scope of the claims to the invention.
Claims (12)
1. A key agreement method between a pair of entities i and j in a digital data communication system, wherein each said entity has a private and corresponding public key pairs S i, P i and S j, P j respectively, said system having global parameters for generating elements of a group, said method comprising the steps of:
(a) said entity i selecting a random private session value R i;
(b) said entity i forwarding a public session value corresponding to said private session value R i to said entity j;
(c) said entity j computing a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H i;
(d) said entity j utilizing said key k' for computing a first authenticated message on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(e) said entity j forwarding said first authenticated message to said entity i;
(f) said entity i verifying said first authenticated message;
(g) said entity i computing said key k', the key k' derived from said entity j's public key P j and said entity i's private key S i in accordance with said first function H
i;
(h) said entity i utilizing said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forwarding said second authenticated message to said entity j;
(h) entity j verifying said second authenticated message; and (i) said entity i computing a short term shared secret key using said private session value R i and said public session value of said entity j; and (j) said entity j computing said short term shared secret key using said private session value R j and said public session value of said entity i.
(a) said entity i selecting a random private session value R i;
(b) said entity i forwarding a public session value corresponding to said private session value R i to said entity j;
(c) said entity j computing a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H i;
(d) said entity j utilizing said key k' for computing a first authenticated message on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(e) said entity j forwarding said first authenticated message to said entity i;
(f) said entity i verifying said first authenticated message;
(g) said entity i computing said key k', the key k' derived from said entity j's public key P j and said entity i's private key S i in accordance with said first function H
i;
(h) said entity i utilizing said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forwarding said second authenticated message to said entity j;
(h) entity j verifying said second authenticated message; and (i) said entity i computing a short term shared secret key using said private session value R i and said public session value of said entity j; and (j) said entity j computing said short term shared secret key using said private session value R j and said public session value of said entity i.
2. The method according to claim 1 wherein any one or both of said authenticated messages is a message authentication code (MAC).
3. The method according to claim 1 or claim 2 wherein said first function H1 is a hash function.
4. A computer readable medium carrying computer executable instructions for causing a cryptographic unit to execute the method according to any one of claims 1 to 3.
5. A cryptographic unit comprising a cryptographic processor, a memory, a data connection and computer readable instructions stored in said memory for performing the steps according to any one of claims 1 to 3.
6. A system for key agreement in a digital data communication system having global parameters for generating elements of a group, said system comprising a pair of entities i and j, said entities having private and corresponding public key pairs S i, P i and S j, P j respectively, said system being configured for:
(a) said entity i selecting a random private session value R i;
(b) said entity i forwarding a public session value corresponding to said private session value R i to said entity j;
(c) said entity j computing a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H1;
(d) said entity j utilizing said key k' for computing a first authenticated message on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(e) said entity j forwarding said first authenticated message to said entity i;
(f) said entity i verifying said first authenticated message;
(g) said entity i computing said key k', the key k' derived from said entity j's public key P j and said entity i's private key S i in accordance with said first function H1;
(h) said entity i utilizing said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forwarding said second authenticated message to said entity j;
(h) entity j verifying said second authenticated message; and (i) said entity i computing a short term shared secret key using said private session value R i and said public session value of said entity j; and (j) said entity j computing said short term shared secret key using said private session value R j and said public session value of said entity i.
(a) said entity i selecting a random private session value R i;
(b) said entity i forwarding a public session value corresponding to said private session value R i to said entity j;
(c) said entity j computing a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H1;
(d) said entity j utilizing said key k' for computing a first authenticated message on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(e) said entity j forwarding said first authenticated message to said entity i;
(f) said entity i verifying said first authenticated message;
(g) said entity i computing said key k', the key k' derived from said entity j's public key P j and said entity i's private key S i in accordance with said first function H1;
(h) said entity i utilizing said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forwarding said second authenticated message to said entity j;
(h) entity j verifying said second authenticated message; and (i) said entity i computing a short term shared secret key using said private session value R i and said public session value of said entity j; and (j) said entity j computing said short term shared secret key using said private session value R j and said public session value of said entity i.
7. A key agreement method between a first entity i and a second entity j in a digital data communication system, said entities having private and corresponding public key pairs S i, P i and S j, P j respectively, said system having global parameters for generating elements of a group, said method comprising said first entity i:
(a) selecting a random private session value R i;
(b) forwarding a public session value corresponding to said private session value R i to said second entity j;
(c) receiving from said entity j a first authenticated message, said first authenticated message being computed using a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H1, said first authenticated message computed on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(d) verifying said first authenticated message;
(e) computing said key k', the key k' derived from said entity j's public key P j and said entity i's private key S i in accordance with said first function H1;
(f) utilizing said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forwarding said second authenticated message to said entity j to enable said entity j to verify said second authenticated message;
and (g) computing a short term shared secret key using said private session value R i and said public session value of said entity j;
wherein said entity j may also compute said short term shared secret key using said private session value R j and said public session value of said entity i.
(a) selecting a random private session value R i;
(b) forwarding a public session value corresponding to said private session value R i to said second entity j;
(c) receiving from said entity j a first authenticated message, said first authenticated message being computed using a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H1, said first authenticated message computed on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(d) verifying said first authenticated message;
(e) computing said key k', the key k' derived from said entity j's public key P j and said entity i's private key S i in accordance with said first function H1;
(f) utilizing said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forwarding said second authenticated message to said entity j to enable said entity j to verify said second authenticated message;
and (g) computing a short term shared secret key using said private session value R i and said public session value of said entity j;
wherein said entity j may also compute said short term shared secret key using said private session value R j and said public session value of said entity i.
8. The method according to claim 7 wherein any one or both of said authenticated messages is a message authentication code (MAC).
9. The method according to claim 7 or claim 8 wherein said first function H1 is a hash function.
10. A computer readable medium carrying computer executable instructions for causing a cryptographic unit to execute the method according to any one of claims 7 to 9.
11. A cryptographic unit comprising a cryptographic processor, a memory, a data connection and computer readable instructions stored in said memory for performing the steps according to any one of claims 7 to 9.
12. A system for key agreement in a digital data communication system having global parameters for generating elements of a group, said system comprising at least one of a pair of first and second entities i and j, said entities having private and corresponding public key pairs S i, P i and S j, P j respectively, said system being configured for having said first entity i:
(a) select a random private session value R i;
(b) forward a public session value corresponding to said private session value R i to said second entity j;
(c) receive from said entity j a first authenticated message, said first authenticated message being computed using a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H1, said first authenticated message computed on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(d) verify said first authenticated message;
(e) compute said key k', the key k' derived from said entity j's public key P
j and said entity i's private key S i in accordance with said first function H1;
(f) utilize said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forward said second authenticated message to said entity j to enable said entity j to verify said second authenticated message; and (g) compute a short term shared secret key using said private session value R
i and said public session value of said entity j;
wherein said entity j may also compute said short term shared secret key using said private session value R j and said public session value of said entity i.
(a) select a random private session value R i;
(b) forward a public session value corresponding to said private session value R i to said second entity j;
(c) receive from said entity j a first authenticated message, said first authenticated message being computed using a long term shared secret key k' derived from said entity i's public key P i and said entity j's private key S j utilizing a first function H1, said first authenticated message computed on entity identities of i and j, the public session value of entity i and a public session value of entity j corresponding to a private session value R j of said entity j;
(d) verify said first authenticated message;
(e) compute said key k', the key k' derived from said entity j's public key P
j and said entity i's private key S i in accordance with said first function H1;
(f) utilize said key k' for computing a second authenticated message on the entity identities of i and j and the entities' public session values and forward said second authenticated message to said entity j to enable said entity j to verify said second authenticated message; and (g) compute a short term shared secret key using said private session value R
i and said public session value of said entity j;
wherein said entity j may also compute said short term shared secret key using said private session value R j and said public session value of said entity i.
Priority Applications (6)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2236495 CA2236495C (en) | 1998-05-01 | 1998-05-01 | Authenticated key agreement protocol |
| JP2000547728A JP2002514841A (en) | 1998-05-01 | 1999-05-03 | Authentication key agreement protocol |
| EP99917701A EP1075746B1 (en) | 1998-05-01 | 1999-05-03 | Authenticated key agreement protocol |
| AU35902/99A AU3590299A (en) | 1998-05-01 | 1999-05-03 | Authenticated key agreement protocol |
| PCT/CA1999/000356 WO1999057844A1 (en) | 1998-05-01 | 1999-05-03 | Authenticated key agreement protocol |
| DE69928519T DE69928519T2 (en) | 1998-05-01 | 1999-05-03 | PROTOCOL ON CONVENTION ON AN AUTHENTICATED KEY |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2236495 CA2236495C (en) | 1998-05-01 | 1998-05-01 | Authenticated key agreement protocol |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CA2236495A1 CA2236495A1 (en) | 1999-11-01 |
| CA2236495C true CA2236495C (en) | 2009-08-04 |
Family
ID=29275636
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA 2236495 Expired - Lifetime CA2236495C (en) | 1998-05-01 | 1998-05-01 | Authenticated key agreement protocol |
Country Status (1)
| Country | Link |
|---|---|
| CA (1) | CA2236495C (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10797868B2 (en) * | 2018-05-31 | 2020-10-06 | Irdeto B.V. | Shared secret establishment |
-
1998
- 1998-05-01 CA CA 2236495 patent/CA2236495C/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| CA2236495A1 (en) | 1999-11-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6336188B2 (en) | Authenticated key agreement protocol | |
| Agrawal et al. | PASTA: password-based threshold authentication | |
| US5889865A (en) | Key agreement and transport protocol with implicit signatures | |
| Lysyanskaya et al. | Sequential aggregate signatures from trapdoor permutations | |
| Dutta et al. | Pairing-based cryptographic protocols: A survey | |
| US7480384B2 (en) | Method for distributing and authenticating public keys using random numbers and Diffie-Hellman public keys | |
| Wang et al. | An improved identity-based key agreement protocol and its security proof | |
| Fang et al. | Anonymous conditional proxy re-encryption without random oracle | |
| EP1075746B1 (en) | Authenticated key agreement protocol | |
| Hoang et al. | Password-based authenticated key exchange based on signcryption for the Internet of Things | |
| CA2236495C (en) | Authenticated key agreement protocol | |
| Shim | Further analysis of ID-based authenticated group key agreement protocol from bilinear maps | |
| CN117914482B (en) | A reverse firewall method for identity key negotiation | |
| Zhou et al. | Efficient ID-based authenticated group key agreement from bilinear pairings | |
| Chen | An interpretation of identity-based cryptography | |
| Yi et al. | ID-Based group password-authenticated key exchange | |
| Fiore et al. | Identity-based key exchange protocols without pairings | |
| Shao | Enhanced certificate-based encryption from pairings | |
| Tan et al. | On the security of an attribute-based signature scheme | |
| Muñiz et al. | Strong forward security in identity-based signcryption | |
| Chandrasekar et al. | Signcryption with proxy re-encryption | |
| Itkis et al. | Intrusion-resilient signatures, or towards obsoletion of certificate revocation | |
| Lin et al. | Provably secure three-party password-authenticated key exchange | |
| Smith | Digital Signcryption | |
| Kim et al. | ID-Based authenticated multiple-key agreement protocol from pairings |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EEER | Examination request | ||
| MKEX | Expiry |
Effective date: 20180501 |