Challenge-response signatures and secure diffie-hellman protocols

Aspects of the invention generally relate to signatures that are provably secure to the transmitting and receiving parties of the information exchange. More specifically, the challenge-response signature scheme allows both the verifier and the signer to calculate the same signature or associated signature, the former grasping the challenge. By doing so, the latter can do this by knowing the private signature key, which, in exemplary embodiments, involves a traditional key exchange protocol, including a variant of the well-known MQV protocol. It has the property of enabling a provable and safe transformation of.

As originally proposed, the Diffie-Hellman (DH) key exchange protocol 100 illustrated in Figure 1 is considered secure against eavesdropping specialist attackers. A myriad of ad hoc proposals were made as a result of the quest for an "authenticated Diffie-Hellman" protocol to resist active man-in-the-middle attacks, many of which were abandoned. It is known to be or suffering from shortcomings. With the development of strict security models for key exchange over the last few years, those skilled in the art can now determine the security of these protocols and develop designs that can prove to be realistically active attacks. I'm in a pretty good position.

As expected, adding security features against active attacks results in additional complexity in both communication and computation. The latter is particularly important in protocols authenticated by public key techniques, which usually require additional expensive group exponentiation. In addition to the need for robust security, many practical applications for key exchange have forced designers to improve the performance costs associated with authentication mechanisms, especially those based on public keys. ..

A field of research initiated by Matsumoto, Takashima, and Imai in 1986 is the search for a public key (PK) authentication DH protocol that will add minimal complexity to the protocol. Theoretically, and up to the guaranteed public key exchange, it is hoped that protocol communication will look exactly like a basic DH exchange. In this technique, protocol authentication must be obtained through a key derivation procedure, which is the basic Diffie-Hellman key g.^xyRather than agreeing on, the parties must agree with the party's public / private key and g.^x, G^yWill agree on the key to combine.

Partly because of the practical advantages that such a protocol would offer, and partly because of the mathematical challenges behind such a design, the "implicit authentication Diffie-Hellman protocol" Many protocols, often referred to, have been developed based on this technique. Not only can this technique generate a very efficient protocol in terms of communication, but it can also potentially provide significant computational savings by combining authentication and key derivation procedures. For these reasons, some of these "implicit authentication" protocols are standardized by major national and international security standards.

Of these protocols, the MQV protocol appears to be widely standardized. This protocol has been standardized by many organizations and has recently been the key to the "next generation cryptography for protecting US government information," including the protection of "confidential or line-of-business national security information." It has been announced by the National Security Agency (NSA) as an exchange mechanism.

In addition, MQVs appear to be designed to meet a number of security goals. The basic version of the MQV protocol is described, for example, in US Pat. No. 5,761305 issued by Vanstone et al.

However, despite its appeal and success, MQV has so far avoided formal analysis in well-defined key exchange models. The present invention is motivated by the desire to perform such an analysis. At the time of the study, the inventor had almost all of the stated MQV goals to be implemented in the Canetti and Krawczyk computational key exchange models, and as described in the provisional application above. I realized that I could prove that it wasn't valid.

As a result, concerns about the security of this conventional protocol have been raised to the inventor. Therefore, based on this analysis that traditional MQV protocols were not demonstrably secure, there is a need for additional security against MQVs, preferably while preserving their existing performance and versatility.<patcit num="1"><text>U.S. Pat. No. 5,761305</text></patcit>

<p> Given the above and other exemplary problems, drawbacks, and disadvantages of conventional systems, one exemplary feature of the invention is to achieve the security goals of the MQV Protocol in a demonstrable manner. To provide a method and structure for a new variant of MQV, referred to herein as HMQV.</p><p> Another exemplary feature of the invention is to demonstrate a new digital signature scheme referred to herein as "challenge-response signature".</p><p> Another exemplary feature of the invention is that both the challenger and the signer can calculate the same signature or associated signature, the former choosing the challenge and the latter grasping the secret signature key. As providing a protocol mechanism that has the property of being able to do this, a version derived from the Schnorr identification scheme and referred to herein as the "exponential challenge response" (XCR) signature scheme. It is to demonstrate this challenge-response signature method as an inclusion.</p><p> Therefore, one exemplary object of the invention is a structure and method for improving security with respect to the authentication Diffie-Hellman protocol, wherein security can be substantiated by implementing the concept of XCR signature schemes therein. Is to provide.</p>

<p> In the first exemplary aspect of the invention, the receiving party (verifier) who chooses the secret value x to calculate the value X = F1 (x) in order to achieve the above features and objectives. Includes, where F1 contains a first given function with at least one argument, where the value x is one of at least one argument of F1 between the two parties interconnected by a device or network. The method of exchange is described herein. The signing party (signer) chooses the secret value y to calculate the value Y = F2 (y), where F2 contains a second given function with at least one argument, the value y. Is one of at least one argument of F2. The signer gets the value X, and the signer has a private key b and a public key B. The signer calculates the value s = F3 (y, b, X), where F3 contains a third predetermined function with at least three arguments, where the value y, the private key b, and the value X are of F3. Three of at least three arguments. There is a fourth given function F4 (x, Y, B) to calculate the value s', F4 has at least three arguments, and the value x, the value Y, and the public key B are at least F4. Three of the three arguments, but the value s is not an argument of F4. There is no secret shared between the verifier and the signer that serves as the basis for any argument in any of the functions F1, F2, F3, and F4. The verifier can consider the values s and s'as valid authenticators if the value s'is determined to be related to the value s in a given manner.</p><p> The second and third exemplary aspects of the invention consist of a device that performs the method described in the previous paragraph and a plurality of machine-readable instructions that can be executed by a digital processor to perform the method. Signal transmission media that specifically implement the program are also described herein.</p><p> In a fourth exemplary aspect of the invention, methods for establishing an authenticated key between two parties interconnected by a device or network are also described herein. The first party has a private key a and a public key A, where the private key a is 0<u style="single">&lt;</u>a<u style="single">&lt;</u>An integer such that q-1, where q is a positive integer, g is the generator of a finite group of degree q, A is generated by the value g, and A = g.^aIs the element within the group calculated as. The second party is the private key b and the public key B = g^{b b}And the private key b is 0<u style="single">&lt;</u>b b<u style="single">&lt;</u>It is an integer such that it becomes q-1. The first party has the value X = g^xSelect the secret value x to calculate, x is 0<u style="single">&lt;</u>x<u style="single">&lt;</u>It is an integer such that it becomes q-1, and the value X is transmitted to the second party. The second party has the value Y = g^ySelect the secret value y to calculate, y is 0<u style="single">&lt;</u>y<u style="single">&lt;</u>It is an integer such that q-1 and the value Y is transmitted to the first party. The first party has the value s = f₁(Y, B, m)^{{f2 (x, a, m')}}Where m, m'contains messages known or exchanged between both parties, the second party has the value s'= f₃(X, A, m')^{{f4 (y, b, m)}}To calculate. Function f₂And f₄At least one of them contains a function H with at least one argument, such one argument is at least one of the messages m and m'where H is a one-way function (one-way). It includes a function, an encryption function, and a cryptographic function, which is one of the cryptographic hash functions. The first and second parties derive a shared key from the values s and s', respectively.</p><p> The above and other objectives, aspects, and advantages will be better understood from the following detailed description of a preferred embodiment of the invention in the context of the drawings.</p>

Next, with reference to the drawings, in particular FIGS. 1-11, exemplary embodiments of the methods and structures according to the invention are shown.

As a preliminary note about groups and notations, all protocols and operations discussed herein are cyclic group G of order q, which is typically the prime number generated by the generator g. Is assumed. The bit length of q is | q | (for example,<maths num="1"><img file="JP2009526411A_D0001.tif" /></maths>Is represented by the logarithm of q with the base 2 rounded to the nearest neighbor (meaning the logarithm of q), and this quantity is used as an implicit security parameter. The parameters G, g, and q are assumed to be constant and known in advance to both parties, as is practically common, for the sake of simplicity. Alternatively, these values could be included in certificates, etc.

Although the multiplication representation of group operations is used herein, the processing is an additive group such as an elliptical curve, or any other algebraic group or specific group, finite field. ), Composite moduli, etc. are equally applicable. In the protocol, the public key represented by uppercase letters (eg A, B) is the element in group G, and the private key represented by the corresponding lowercase letters (eg a, b) is Z._qIs the origin of, and here Z_qRepresents a set of integers 0, 1, ..., Q-1.

For example, public key A = g^aCorresponds to the private key a. The party holding A as its public key<maths num="2"><img file="JP2009526411A_D0002.tif" /></maths>Will be referred to as A hat hereafter. Represented by, traditionally considered "Alice" (second party)<maths num="3"><img file="JP2009526411A_D0003.tif" /></maths>Will be referred to as the B hat hereafter. Is traditionally considered "Bob"). Generally, "hat notation" is used to represent the logical ID or "distinguishing" ID of a party within a protocol, such as name, email address, or role. In some cases, these IDs can be augmented with digital certificates. Although not repeated herein, for the more complete mathematical analysis provided in the provisional application, all parties within the protocol, including the attacker, are deemed to be achieved via a stochastic polynomial time machine. Is done. The attacker is also represented by M, where M can mean "malicious".

Therefore, as illustrated in Figure 1, the session key calculation for the basic unauthenticated Diffie-Hellman protocol 100 consists of an exchange between a two-party A hat and a B hat, with the party A hat first having its own key. X = g^xTo Party B Hat, then Party B Hat has his key Y = g^yRespond by returning to the party A hat, where x and y are the set Z, respectively._qA secret randomly selected by A and B hats from, and the shared session key is g^xyIs calculated as.

In the description herein, the symbol to represent random selection._RIt should be noted that may be used. For example, x _RZ_qIs typically an integer Z by using a random number generator or a pseudo-random number generator_qIt means that the value x is randomly selected from the set of.

MQV protocol Communication with the MQV protocol is not possible, except that the A-hat and B-hat IDs may contain additional information such as public key certificates or all of these IDs may be omitted together. , Identical to the basic unauthenticated DH protocol 100 depicted in Figure 1.

2 Message Authentication The first challenge in designing a key exchange protocol is to prevent successful attacks based on the playback of the first protocol message. This is a problem because the first message cannot contain any form of session-specific "freshness guarantee" given by the responder (for example, a nonce or a fresh DH value). There is something. One solution to this problem is to provide freshness through session key calculations.

For example, the two-message Diffie-Hellman protocol 200 illustrated in Figure 2 is authenticated using a digital signature adopted from the ISO (International Organization for Standardization) 9973 protocol. G under the signature of B hat^xThe inclusion provides freshness in the certification, but this security feature is not present in the A-Hat message. But the session key g^xyIs randomized by the fresh y, so it is guaranteed to be fresh (as well as independent of other session keys). However, the attacker uses a single pair (x, g) by the A hat in a session with the B hat.^x) Is found, the security of the protocol is broken, in which case the attacker<maths num="4"><img file="JP2009526411A_D0004.tif" /></maths>Also learn. This allows an attacker to vaguely spoof A-hat against B-hat using the same message and knowledge of x without having to learn the long-term secret signing key of A-hat.

This is ephemeral session specific information (for example, pairs (x, g)^x)) This is a serious vulnerability that violates the basic principle that other sessions must not be destroyed by disclosure. Many applications have this pair (x, g)^xThis is especially important considering that) is calculated offline and will be kept in storage that is not as protected as a long-term private key, for example.

Therefore, the question is how to design a two-message protocol that is not affected by replay attacks even if temporary information is leaked. Including the long-term private key in the session key calculation is a natural answer. This was the approach undertaken in a 1986 study by Matsumoto, Takashima, and Imai, which motivated many of Diffie-Hellman's so-called "implicit authentication" variants, including MQV. In this approach, each party has a long-term DH public key and a corresponding secret exponent, and a session is generated by combining a session-specific temporary DH value with both parties' public and private keys. To. Therefore, the security of such protocols as a whole depends on the exact details of this key combination. Surprisingly, this seemingly simple idea is difficult to achieve reliably, and all previous proposals have some drawbacks.

Then, considering the following natural solutions to the problem of combining temporary and long-term keys in session key calculation, if A and B hats want to exchange keys, they are both basic Diffie- Run the Hellman protocol and K = g^{(x + a) (y + b)}= (YB)^{x + a}= (XA)^{y + b}Calculate the session key as. In this case, if the attacker learns x instead of a, the attacker cannot calculate K.

However, as demonstrated by the simple attack below, the protocol is still insecure, i.e. M is the value x^*∈_RZ_qSelect and X^*= g^{X *}Calculate / A and X to B hat as spoofing of initial message from A hat^*To send. B hat sends Y = gy and session key K = (X^*A)^{y + b}To calculate. Unfortunately, M puts K (BY)^{x *}It can also be calculated as. Therefore, this protocol is not secure.

Moreover, the calculation of K is for the constants d and e, K = g^{(x + da) (y + eb)}Even if it is changed to, the attack is still possible. In contrast, the simple attack described above may not work if the constants d, e can change with X, Y so that the attacker cannot control e and Y individually. This idea brings us back to the MQV design, where d =<maths num="5"><img file="JP2009526411A_D0005.tif" /></maths>Will be referred to as the X bar hereafter. And e =<maths num="6"><img file="JP2009526411A_D0006.tif" /></maths>Will be referred to as the Y bar hereafter. Is.

Calculation of session key K in MQV 301, 302 are illustrated in Figure 3, where party A hat is the long-term secret key a Z._qAnd the corresponding public key A = g^aAnd own. Similarly, B's private / public key pair is (b, B = g).^{b b}), And the temporary DH value is X = g^x, Y = g^yWhere x and y are selected by A and B, respectively. The session key calculation also uses the values d = X bar and e = Y bar, where X bar = 2 for l = | q | / 2.^l+ (X mod 2^l) And Y bar = 2^l+ (Y mod 2^l).

Calculation of session key by A hat is X = g^xOff-line exponentiation to calculate and B^eOn-line exponentiation and (YB) for calculating^e)^{x + da}It should be noted that additional online exponentiation is required for. However, the second power uses an exponent e of length | q | / 2, so it is a "half exponentiation" (for example, the number of modular multiplications for a regular exponentiation of g). It should also be noted that is considered to be half). The same calculation count is valid for the B hat.

Overall, MQV performance is really impressive, with the same communication as the basic unauthenticated DH protocol (except the possibility of transmitting a certificate as part of the identities of both parties), half a power more than the basic protocol. , Only a 25% increase in calculations to achieve a certification exchange. This is significantly better than either of the proven DH protocols that rely on digital signatures or public key cryptography for authentication, with more expensive computation and increased bandwidth. It is also the most efficient of the implicit authentication DH protocols, the closest of which requires three full exponentiations, but provides substantially less security features. It is a "Unified Model" protocol.

This exceptional performance and security commitment makes MQV an attractive candidate when choosing an authentication DH protocol. For these reasons, this protocol has been adopted by many standards and has been widely discussed in the literature. However, one of the unanswered questions so far is how secure the MQV protocol is, as none of the formal models of key exchange security performed successfully formal analysis of the MQV protocol. That's what it means.

MQV designers, on the other hand, were clear about the security goals behind the design. These are intrinsic security against spoofing and known key attacks, including resistance to "unknown key share (UKS)" attacks, as well as perfect forward secrecy (PFS) and KCI (keys). Leakage spoof: key-compromise impersonation) Includes more specific features such as resistance to attacks. Resistance to known key attacks represents the principle that disclosure of temporary session-specific secrets must not compromise the security of other sessions.

The PFS and KCI characteristics refer to confining security damage if a party's private key is leaked to Attacker M. More specifically, PFS allows M to retain the session key even if both parties are destroyed after any session key established between the two unbroken parties has been erased from the memory of both parties. It means that you cannot learn. Resistance to KCI attacks learns the long-term secret key of one party A-hat, so an attacker who can clearly spoof A-hat against another party is the other unbroken party against A-hat. Needs to be unable to spoof.

Unfortunately, as further described in the provisional application above, the results of our analysis show that, when formally studied, none of these properties are satisfied by the MQV protocol. Specifically, the Canetti and Krawczyk security models demonstrate that this protocol is vulnerable to a range of attacks that contradict the security characteristics described above that are said to be satisfied by MQV. ing.

HMQV protocol The HMQV protocol (H can be considered to mean hash) is an addition to the traditional MQV protocol shown in step 302 for comparison in some exemplary embodiments. Is a simple but powerful variant of MQV that can contain hashes as shown in step 303 of Figure 3. However, alternative embodiments that do not perform hashing and do not use techniques other than hashing are discussed herein and are also included in the concepts of the present invention, and as a first matter, one of these exemplary embodiments It should also be noted that one or more hash steps are not a prerequisite for the present invention. A more basic concept of the present invention relates to a challenge-response signing scheme from which some applications and embodiments have evolved, including an exemplary hash version of the MQV protocol.

As is well known in the art, hashes require the use of hash functions to convert character strings to numbers, fixed length strings (eg, hashes or message digests), etc. as output. The basic function of hash functions in cryptography means that retrieving the original data is infeasible, and building blocks of data that match a given hash value must also be infeasible. To provide a "one-way" or "irreversible" transformation. Hash functions can range from simple "mixing" functions to transformations that resemble purely random scrambles. The latter is called a "strong cryptographic hash function" and is often modeled in cryptographic analysis by an ideal random function (or "random oracle").

Some hash functions are widely used for strong cryptographic hashes. For example, MD5 takes a block of data of any size as input and uses a table of values based on a sine function for processing data in bit-by-bit operations, additions, and 64-byte blocks. This produces a 128-bit (16-byte) hash. Another major hash function is the NIST (National Institute of Standards and Technology) Secure Hash Algorithm (SHA), which provides 160-bit hashes.

Typically, hash functions are not used directly for cryptography, but cryptographic functions provide one-way transformations, and thus for some hash applications, including some exemplary embodiments of the invention. Applicable. Hash functions are also suitable for data authentication and are called private keys (in these settings, MAC in the case of Message Authentication Code) and in the case of pseudo-Random Function. Often referred to as PRF) or with a signing method (in which case the hash value is used for "message digest"), it is used for this purpose.

Various exemplary embodiments of the invention use at least one hash function H summarized as an ideal random oracle in the security analysis detailed in the provisional application above. The two tasks in which the function H is used in these exemplary embodiments are, first, the calculation of the indices d, e, and second, the derivation of the session key itself.

The first task, by way of example, uses two arguments to H and outputs a string of length | q | / 2, and the second task applies H to a single argument and specifies it. Outputs a key of length (for example, 128 bits). To simplify the notation, the same symbol H is used to represent both application examples of the hash function. In fact, it can handle variable-length inputs and probably uses some combination of truncation / expansion in generating hash results to fit the above two tasks. You will be using a single H with adjustable output size, for example SHA-1.

However, when using a hash as in the first task, instead of just hashing the message or party ID, you can include additional arguments such as timestamps, nonces, etc. as input to the hash function. It should also be noted that it is not necessarily limited to two arguments.

When using hashes, the hash function used to generate the exponents d, e (typically with l = | q | / 2 bit output) is<maths num="7"><img file="JP2009526411A_D0007.tif" /></maths>Will be referred to as the H bar hereafter. Often represented by, the hash function that has a k-bit output and is applied to the σ value is represented by H. In practice, the same hash function with different output lengths can be used, so the symbol H may be used instead of the H bar. As a mnemonic, the bar inside the H bar indicates that the output of this function is used as an exponent.

Like MQV, the communication of the HMQV protocol is the same as the basic DH exchange previously illustrated in Figure 1, but certificates may be added. As illustrated in Figure 3, the calculation of the session key K, unlike that of the MQV in the calculation of the values d and e, requires a hash of the party's own DH value and the peer's ID. The typical output of this hash is l = | q | / 2 bits. In addition, in one exemplary embodiment, the HMQV<maths num="8"><img file="JP2009526411A_D0008.tif" /></maths>Specifies a hash from the value to the k-bit key, where k is the desired session key length. In alternative embodiments, one or both σ functions are not hashed.

From this description, it can be seen that HMQV retains the excellent performance of MQV in terms of both communication and computation. At the same time, HMQV overcomes all the security shortcomings of MQV discussed in the provisional patent application above to the maximum extent possible with the two-message protocol further discussed and proven there. A more complete description of the security characteristics and benefits of HMQV and its variants is provided later in this application.

Challenge-response signature It must be clear how the HMQV protocol differs from the MQV protocol, but in a sense there is another aspect of the invention that is more basic. That is, the main technical tool that exists as the central design and analytical element behind HMQV is called "challenge-response signature" and is based on a new variant of Schnorr's identification method that uses the Fiat-Shamir method. A new form of interactive signature that will be realized. The result is an "exponential challenge-response" (XCR) signature of the present invention. The relationship between Schnorr and Fiat-Shamir methods and XCR signatures is discussed below.

These XCR signatures are secure in the random oracle model (based on the Computational Diffie-Hellman or CDH hypothesis-see below) and are exemplary by both verifiers and signers. Has the property that the same signature can be calculated. The former achieves this by knowing the challenge, and the latter can do this by knowing the private signing key. Variations on the calculation of the same signature include calculating different but relevant signatures for signers and verifiers.

For example, the signature value calculated by one may be a hash variant of the signature calculated by the other, or both signatures may be related by some particular algebraic characteristic or the like. The various HMQV protocols of the invention are one of the exemplary mechanisms for using these XCR signatures, which provide authentication (of DH values and peer IDs) and session key calculations.

Therefore, the XCR signature and its "dual version" (eg DCR), in brief, provide a natural interpretation of the underlying ideas of HMQV design and analysis, both technically and conceptually. It is a thing.

In addition, it should be noted that XCR signatures can also be used in applications beyond the HMQV protocol. In each basic form, XCR signatures do not provide the classic functionality of digital signatures because they are interactive, challenge-specific, and non-transferable. That is, they cannot be used for non-repudiation.

In contrast, they provide a characteristic "deniable authentication" in the case of any application, including key exchange, thereby providing a message to the recipient of the XCR signature. Alternatively, the source and integrity of the key can be guaranteed, but the source cannot be proved to a third party. In particular, these signatures and the resulting key exchange protocols are ideally suitable for "off-the record" communication and privacy protection. In addition, non-interactive versions of XCR exist as described below and in some cases provide an alternative to established signature schemes such as the well-known Digital Signature Algorithm (DSA).

Like the legitimate digital signature method, in the challenge-response signature method, the signer has a private / public key pair that is used to generate and verify the signature, respectively, and the verifier uses the signer's authentic public key. It is supposed to be obtained. In particular, the parties are not expected to share a secret prior to the start of the signature protocol, and such a shared secret is not required for signature calculations. However, in its basic form, in contrast to legitimate signatures, challenge-response signatures are interactive and the recipient of the signature (for example, before the signer generates the signature on a given message). The verifier) needs to issue a challenge to the signer. A secure challenge-response signature scheme needs to ensure that no one other than a legitimate signer can generate a signature that convinces the challenger to accept the signature as valid. Above all, signatures are not only message-specific, but also challenge-specific.

In contrast, guaranteeing the verifiability of a signature by a challenger is of interest, and therefore there are no assumptions or requirements regarding the transferability of a signature or verifiability by a third party. Moreover, the particular method described below has the property that the party choosing the challenge can always generate a valid signature for that particular challenge on any message. More important with respect to this application, what distinguishes this scheme from other interactive signatures is that the verifier can use the challenge to calculate the same (or associated) signature string as the signer.

As mentioned above, g is the generator of the group G of degree q (usually a prime number). Also, H is | q | / 2 bits<maths num="9"><img file="JP2009526411A_D0009.tif" /></maths>Is a hash function that outputs, but again, the use of "prime order" and the specific length of the output of H are only exemplary design details of the exemplary embodiments. , Not essential to the present invention.

Definition of XCR signature method The exponential challenge-response (XCR) signature method 500 illustrated in Figure 4 is defined as follows. That is, the signer in the XCR method represented by the B hat is the private key b _RZ_qAnd public key B = g^{b b}And own. The verifier (or challenger) represented by the A hat is x _RZ_qIn the case of A hat is X = g^xProvides the first challenge X to calculate as, where x is selected by the A hat and kept secret. The signature of the B hat on a given message m using Challenge X is<maths num="10"><img file="JP2009526411A_D0010.tif" /></maths>Is defined as a pair, where Y = g^yAnd y _RZ_qIs selected by the B hat and the exponent y + H bar (Y, m) b is converted modulo q. Verifier A hat, it's<maths num="11"><img file="JP2009526411A_D0011.tif" /></maths>Only if it is determined that (message m and challenge X = g)^xAbout) Accept signature pairs (Y, σ) as valid.

The following notation is used here. That is, for a given message m, challenge X, and value Y,<maths num="12"><img file="JP2009526411A_D0012.tif" /></maths>Is defined as. That is,<maths num="13"><img file="JP2009526411A_D0013.tif" /></maths>Represents a second element in the XCR signature pair. As a general note, any above use of the word "message" can be represented by a bitstream containing transmitted data, files, media, etc., which in itself can be a hash version of a longer message. It is worth noting that it represents data or information in a format. This message can be entered to both parties as illustrated in Figure 5, can be transmitted from one party to another, or can be provided by a third party, an external source, or the like.

As described in this application, the advantages of XCR signatures are the soundness of the analysis (verifiable), computability by both verifiers and provers, and duality (single calculation is signed by two or more parties). (Representing a combination of), "hashability" (ie, the ability to process and validate hash signatures), derivation of keys or common values, non-transferability and denialability, (traditional from denialable signatures) Includes convertibility (to undeniable signatures), providing a more robust alternative to DSS (especially in interactive environments), and the existence of non-interactive variants.

It can be an example to motivate the design of the XCR scheme through its association with Schnorr's identification scheme from which the XCR signature is derived. Schnorr's (interactive) identification scheme is for a given input B = g^{b b}Consists of proof that we know the discrete logarithm b for. Suppose the B hat represents the certifier of this method (who owns b) and the A hat represents the verifier (whose input B is given). The basic Schnorr identification consists of the following three messages. (i) B hat is y _RZ_qSelect, Y = g^yTo A hat. (ii) A hat is a random value e _RZ_qRespond with. (iii) The B hat sends the value s = y + eb to the A hat. A hat is g^s= YB^eAccept only if is valid.

This protocol is a public-coin zero-knowledge proof of knowledge (b) for an honest verifier A hat (eg, a person who randomly and uniformly chooses e). Therefore, this is a secure signature scheme that can be substantiated by the random oracle model via the well-known Fiat-Shamir method, ie.<maths num="14"><img file="JP2009526411A_D0014.tif" /></maths>Can be converted to.

Next, consider the following four-message variant of the Schnorr protocol, to which the first message from A-hat to B-hat is added. In this first message, the A hat has the value X = g^xTo the B hat. Then three messages from Schnorr's method follow, but in message (iii), the fourth message of the modified protocol, the B hat does not send s = y + eb to the A hat. S = X^sTo send. A hat is S = (YB^e)^xOnly accept if. It turns out that this protocol is a proof of the "ability" of the B hat to calculate the Diffie-Hellman value CDH (B, X) for any value X G. Moreover, this protocol is zero-knowledge for verifier A hats that randomly choose e, and X can be chosen arbitrarily.

By applying the Fiat-Shamir transform to this protocol, the challenge-response signature XCR of the present invention is obtained. It also explains why the term "exponent" is used when naming the XCR method, with the Schnorr method s = y + eb as the X in the last message of this protocol.^sRefers to replace with.

Additional aspects of XCR signature scheme security based on the CDH hypothesis are further discussed in the provisional application above.

In explaining some of the above terms, the two elements in G, U = g^u, V = g^vIn the case of, the result of applying the Diffie-Hellman calculation to U and V is represented by CDH (U, V) (for example, CDH (U, V) = g).^uv). This algorithm is called a "CDH solver for G" when it takes a pair of elements (U, V) in G as input and outputs a Diffie-Hellman result CDH (U, V). The main intractability assumption used in the analysis further provided in the provisional application is the Computational Diffie-Hellman (CDH) hypothesis. For all efficient CDH solving routines for G, U, V _RIf the probability that the solution routine calculates the correct value CDH (U, V) for the pair (U, V) with respect to G is negligible (this probability is taken for the random coins of the solution routine and the choice of U, V). Is randomly and independently performed within G), and the CDH hypothesis can be said to be valid in group G.

Number of bits in H bar (Y, m) Let l be the number of bits in the H bar (Y, m). Obviously, the smaller l is, the more efficient the signature method is. On the other hand, if the exponent H bar (Y, m) is predictable, the signing scheme becomes unstable, so if l is too small, it indicates that the security bound is bad. However, the question is how large l is needed for security.

The setting l = 1/2 | q | provides a good security performance trade-off, and therefore with the exemplary specification of the XCR signature (and for its exemplary application to the HMQV protocol of the invention). It turns out that this value is used (see the provisional application discussion above).

Change the order of dialogue with B In particular, in some application examples of XCR signatures applied to the analysis of the HMQV protocol, the order of dialogue between the Challenger A hat and the signer B hat can be changed.

In the above definition of the XCR method, the A hat provides a challenge X to the B hat and at the same time presents a message m to the B hat, so that the B hat is a signature pair.<maths num="15"><img file="JP2009526411A_D0015.tif" /></maths>You can respond immediately with. The modified version currently under consideration involves the following dialogues: (i) The A hat presents the message m to the B hat, the B hat outputs Y, and at some point thereafter. (ii) A hat provides (Y, m, X) to B hat, B hat<maths num="16"><img file="JP2009526411A_D0016.tif" /></maths>Is output.

It is then assumed that Party F queries B Hat to take this modified order. In particular, F can interleave various dialogues with the B hat, i.e. F can perform several instances of step (i) before performing the corresponding step (ii). This requires the B hat to retain its post-step (i) state with the values Y, y, and m. Then, when F presents (Y, m, X) in step (ii), the B hat checks and if it has a pair (Y, m) in that state.<maths num="17"><img file="JP2009526411A_D0017.tif" /></maths>Responds with and removes (Y, m) from that state (if the B hat does not have a pair (Y, m) in that state, it does not issue its signature).

Note that this specification of the B-hat action ensures that the B-hat does not use the same Y value for two different signatures. Simulation of Y selection by B-hat does not require knowledge of X, but only because it needs only the value of m to determine the H bar (Y, m)), proof of the security of the XCR signature Can easily be verified that is still valid for this modified order.

Hash XCR variant (HCR) It is possible to replace a pair of XCR signatures (Y, σ) with a pair (Y, H (σ)), where H is a hash function, and such a "hash XCR" signature is abbreviated as "HCR". Will be done. Note that the XCR property allows the verifier to recalculate σ for Y, so given Y, H (σ) can also be calculated, so the modified HCR signature can be verified.

HCR signatures have a range of characteristics that are important in some settings. For example, the signature may be shorter than the legitimate XCR signature, resulting in a random or pseudo-random value, which may prevent an attacker from learning the algebraic structure in σ. ..

Especially in interactive and verifier-specific authentication environments (such as key exchange protocols), HCR signatures provide a more secure alternative to DSA signatures. In fact, in DSA, a single temporary index (for example, the component r = g of the DSA signature)^kDisclosure of k) in makes the signature method completely unstable by revealing the private signature key, and even if the temporary exponent y is revealed to the attacker, the HCR signature cannot be forged (however, this). If the signer tests the order of Challenge X or uses co-factor exponentiation to force its value to at least order q).

Non-interactive XCR variant The XCR (and HCR) signature can be made non-interactive but verifier-specific by writing X = A, where A is the verifier's public key, as illustrated in Figure 6. Is. It provides a highly efficient, non-interactive, verifier-specific denial authentication mechanism. In one variant, instead of using the party A hat's unique public key A, the latter can publish one or more challenges for use by the signer (for example, post on a website). Therefore, these challenges are available even if the A-hat itself is not available at the time of signing.

Convertible XCR signature The salient properties of XCR signatures, including those based on shared secret and public key cryptography, which distinguish them from other "denialable" challenge-response mechanisms, make these signatures legitimate denials. The ability to "convert" into a unique signature. Convertible signatures have the property of denial authentication, that is, they can only be verified by the intended recipient, but the signer also creates a given signature without revealing his private signature key. Can finally prove that he is a person.

This convertibility from a private signature to a public signature may be necessary, for example, for informal professional communications that must be converted into verifiable public records after a few years. For XCR signatures, the signature (Y, σ) on the message m based on Challenge X is converted to a legitimate denial signature by a legitimate signer by revealing the value y + H bar (Y, m) b. can do.

Other (receiver-specific) convertible signatures have been presented in the literature, but in any case the intended receiver (or challenger) cannot recalculate the signature on its own, so: As illustrated by the double XCR signature in, this recalculation property does not share many of the benefits it offers for XCR signatures.

Double XCR Signature (DCR) One of the important characteristics of the XCR signature is that the challenger who chooses the challenge can calculate the signature on his own. Here, a related challenge-response signature with the property that any two parties, A-hat and B-hat, can interact with each other in the dual role of challenger and signer, each generating a signature that no third party can forge. A method of utilizing this property to derive a method (referred to herein as "double XCR method" or DCR for short) is shown. Moreover, this makes this scheme important to the HMQV protocol, and the resulting signatures by A and B hats have the same value. More precisely, they have the same XSIG component in the XCR signature pair.

Definition: Double (exponential) challenge-response (DCR) signature method. A hat and B hat are public keys A = g, respectively.^a, B = g^{b b}Two parties with. m₁, M₂Is two messages. Each message m₁, M₂The double XCR signatures (DCR for short) on the A and B hats above are X, Y, and<maths num="18"><img file="JP2009526411A_D0018.tif" /></maths>It is defined as a triplet of values, where X = g^xAnd Y = g^yAre the challenges selected by the A and B hats, respectively, and the symbols d and e are the H bars (X, m, respectively).₁) And H bar (Y, m₂). (See Figure 7.)

Therefore, the basic characteristic of DCR signatures is that after exchanging the values X and Y (including x and y selected by the A and B hats, respectively), both the A and B hats have the same signature.<maths num="19"><img file="JP2009526411A_D0019.tif" /></maths>Can be calculated (and verified). this is,<maths num="20"><img file="JP2009526411A_D0020.tif" /></maths>It can be seen from the equivalence, where x + da and y + eb are converted modulo q.

Moreover, as demonstrated in the provisional application considerations above, an attacker cannot calculate to be able to carry out this signature.

Roughly speaking, double signature is a challenge YB^eMessage based on m₁Challenge XA at the same time as the XCR signature by the A hat above^dMessage based on m₂XCR signature by B hat above. More precisely, the values d and e are during the signing process (message m)₁, M₂The DCR signature of the B hat is not chosen by the attacker, as it is determined (perhaps by a hostile choice) A = g^aCan be demonstrated to be safe with respect to.

Formal description of the basic HMQV protocol The HMQV protocol, in its basic two-message exchange, from which both parties A and B hats<maths num="21"><img file="JP2009526411A_D0021.tif" /></maths>Diffie-Hellman value X = g that acts as a challenge to calculate the double XCR signature^xAnd Y = g^yConsists of an exchange between the two parties. The session key is then derived by hashing this value. In this way, the signature itself does not need to be transmitted, and it is the uniqueness of the signature that guarantees the common derived value of the session key, and the exchange was performed by the claimed parties A hat and B hat. It is the unique ability to calculate the key (equivalently, the signature) that enables proof.

Basically, the message m for which the signature is calculated₁, M₂Since is the peer's ID (ie, A hat, B hat), both parties get the assurance that the key they calculate is uniquely bound to the correct ID. It is essential to include the IDs of both parties in this way, as well as the temporary Diffie-Hellman values under the signature (especially in the calculation of the values d and e), in order to avoid any authentication failure such as a UKS attack. is there.

Therefore, the session of the HMQV protocol between the two parties A hat and B hat has a DH value X = g with the session key calculated as H (π).^xAnd Y = g^yConsists of the basic Diffie-Hellman exchange of (Figure 1), where<maths num="22"><img file="JP2009526411A_D0022.tif" /></maths>Is. That is, π is calculated as a double signature of A and B hats for each other's IDs. The above signature is represented by the abbreviation π (A hat, B hat, X, Y), ie<maths num="23"><img file="JP2009526411A_D0023.tif" /></maths>And here d = H bar (X, B hat), e = H bar (Y, A hat), A = g^a, B = g^yAre the public keys of both parties A hat and B hat, respectively. It should be noted at this point that π (A hat, B hat, X, Y) = π (B hat, A hat, Y, X). In some variants, H (π) can be replaced by a different function of π, in particular the hash can contain additional information such as the IDs of both parties.

The HMQV protocol is typically run on a multi-party network where any of the parties can be called to run the protocol. Each time a party calls a protocol, a session (a local state containing information related to this particular instance of the protocol) is created, which can generate outgoing messages and session key output upon completion. During a session, a party can be activated by three types of activations (in the description below, the A hat represents the ID of the party being activated, and the B hat is the intended peer for the session. Represents an ID). 1.Initiate (A hat, B hat): A hat has a value of X = g^x, X _RZ_qCreates a local session of HMQV that identifies it as an (incomplete) session (A hat, B hat, X) and outputs the value X as its outgoing message. The meaning of this activation is that the A hat has been activated as the initiator of the session with the B hat, and X is a message that will be delivered to the peer B hat as part of this session. Party A hat is called the "holder" (or "owner") of the session, B hat is called the "peer" for the session, and X is called the outgoing (DH) value. 2. Respond (A hat, B hat, Y): Check that A hat is Y 0. If so, the A hat has the value X = g^x, X _RZ_qGenerates, outputs X, and completes the session with ID (A hat, B hat, X, Y) and session key H (π ((A hat, B hat, X, Y)). The A hat is activated as the responder in a session with a peer B hat and an incoming call value Y. In this case, the A hat completes the session immediately (no more incoming messages). Note that if is zero, the A hat ignores the launch. 3. Complete (A hat, B hat, X, Y): A hat checks that Y 0 and that it has a public session with an ID (A hat, B hat, X). If any of these conditions are not met, the A hat ignores the activation, and if so, the A hat is the session ID (A hat, B hat, X, Y) and the session key K = H (π ((A)). Complete a session with hat, B hat, X, Y)), which represents the delivery of a second message in this protocol by the incoming value Y, which is the response from peer B hat (according to allegations). There is.

3 Message HMQV-C protocol The 3 message HMQV-C (C stands for "key Confirmation") protocol is depicted in Figure 8. This protocol enjoys all the security characteristics of HMQV, especially the same computational cost. However, this adds a third message to the protocol and slightly increases the length of the protocol message.

Instead, HMQV-C provides some characteristics that the basic HMQV protocol lacks, including key verification, PFS, and universal composability.

Key confirmation The HMQV protocol provides a basic guarantee for the party A hat that completes the session with the peer B hat and the session key K, and if the B hat is not destroyed, only the B hat can probably figure out K. .. What this protocol does not provide is a guarantee for A-Hat that B-Hat has completed the session or calculated the session key. Moreover, B-Hat may not have been "active" during the session.

Same for both two-message public key-based protocols (assuming that earlier communication between A and B hats did not create any pre-shared state, as in a typical public key scenario). This is not the only drawback of HMQV, as is true. In addition, as pointed out by Shoup, the seemingly natural goal of both parties to ensure that the peer completes the session before each starts using that key is any key exchange protocol. But it cannot be achieved. In fact, an attacker can always thwart this mutual guarantee by preventing the last protocol message from arriving at its destination.

However, if the guarantee to each of the parties that the peer was able to calculate the key is weak (but not necessarily the guarantee that the key will be output to the calling application), that guarantee is achievable and the literature confirms the key. It is called a characteristic. Although not critical to the basic security of key exchange (for example, lack of key verification is not a threat to the privacy or certainty of key-protected communications), this property is useful in some applications. An operational sanity check can be provided.

In this case, the protocol HMQV-C is more suitable than HMQV because the additional MAC value allows key verification. Moreover, MAC validation confirms the fact that this peer owns a matching session (ie, has the same peer and the same session key), along with the active involvement of the identified peer in the session. To achieve these characteristics, the HMQV-C MAC does not need to be applied to any particular session information, but is simply used to indicate the "direction" of the message and to prevent reflections. Note that it needs to be applied to one bit. Also, a protocol consisting of only the first two messages of HMQV-C provides key verification to the invoker (which allows you to add useful features to HMQV without increasing the number of protocol messages. It is also worth keeping in mind.

In many applications of key exchange, as a result of lack of key verification, party A hat begins to use the key, for example to send protection information to B hat, but B hat still has the key established. Since there is no such information, some form of "denial of service" (DoS) attack can occur that cannot process this information. As it is said, mutual "session completion" confirmation is unattainable, so this situation cannot be completely avoided.

Moreover, it is a more serious form of public key behavior-based protocol, forcing a party to spend a considerable computational cycle (and create a session state) before discovering peer invalidity. DoS attacks exist. There are several useful but limited scope countermeasures against DoS attacks that can be applied to any key exchange protocol (including HMQV) at the expense of adding protocol messages.

Full Transfer Secret (PFS) Full transfer secrecy is a highly desirable property of key exchange protocols that does not compromise the security of old session keys in the event of a long-term private key leak. More formally, if the unbroken party A hat establishes a key exchange session with the unbroken peer B hat, the attacker destroys the A hat after the K expires in the A hat or If an attacker destroys the B hat after K has expired in the B hat, the session key K remains safe. Neither of the two-message protocols with implicit authentication, including HMQV, can provide a complete complete transfer secret to an active attacker. Instead, the best you can hope for is the weak form of PFS provided by HMQV. The main advantage of HMQV-C over the basic two-message HMQV is that it raises the inherent limitations of HMQV and provides full PFS, as further explained in the provisional application.

General-purpose configurable security The Canetti / Krawczyk model for key exchange is the basis for the analysis of MQV and HMQV in provisional applications, ensuring the security of the key exchange protocol when run concurrently with other applications, as in the real world environment. It has been extended to a more ambitious model with the goal of. This model is known as the Universal-Composability (UC) model for key exchange.

In the case of HMQV-C, when the first party to complete the session outputs its session key, it can be seen that the peer state contains only information that can be "simulated" from the public information in the protocol and session key. .. Canatti / Krawczyk, along with the other security characteristics of HMQV set forth in the provisional application, show that these characteristics are sufficient to ensure general-purpose configurability of the HMQV protocol.

1 pass HMQV The one-pass key exchange protocol shown in Figure 9 consists of a single message sent from the sender A hat to the receiver B hat, unless both parties and the session are corrupted as defined below. From there, both parties use their private and public keys to derive a unique key that only A and B hats will probably know.

The requirements from the established key are the same as the legitimate key exchange protocol, except that the message received by the B hat may be a replay of an old message from the A hat. This regeneration is unavoidable with the one-pass protocol, but may be detectable by other means such as synchronization time or shared state.

In addition, due to the lack of session-specific input from the B-hat, such a protocol cannot provide PFS because the key must be computable with the sole knowledge of the B-hat's private key.

In one embodiment of the invention, the public key A = g, respectively.^a, B = g^{b b}The one-pass HMQV protocol between the A hat and the B hat is a single value X = g transmitted from the A hat to the B hat.^xConsists of, where x _RZ_qIs selected by the A hat. The session key K is calculated by the A hat as follows. (i) (A hat, B hat) shall represent a message containing two IDs A hat and B hat, and d should be the result of d = H bar (X, (A hat, B hat)). Set. (ii)<maths num="24"><img file="JP2009526411A_D0024.tif" /></maths>To calculate. (iii) Set K = H (σ, A hat), where H outputs the number of bits equal to the required key length. For the same key K, after checking that X 0, K = H ((XA) by B hat^d)^{b b}) Is calculated. In the transformation, K = H (σ, A hat, B hat).

In other words, the key of this embodiment of the 1-pass HMQV is derived from the non-interactive XCR prominence using the public key of the B-hat as a challenge.

It has also been pointed out that the one-pass protocol can be used as an authentication chosen-ciphertext secure (CCA) encryption method. That is, the A hat can transmit the message m, which is encrypted (against the chosen-ciphertext attack) and authenticated (by the A hat), to the B hat. In one embodiment, the A hat would transmit a triad (X, c, t), where X = g.^xAnd c is the key K₁Based on the symmetric selection of message m, plaintext secure (CPA) is the ciphertext obtained as encryption, where t is the key K.₂The MAC value calculated for c based on. Key K₁And K₂Is derived from the key K calculated from X, as in the 1-pass HMQV protocol.

The overall cost of this procedure is two powers (one offline) for the A hat and 1.5 for the B hat. This is only 1/2 more power for the B hat compared to alternative CCA encryption methods such as DHIES (Diffie-Hellman Integrated Encryption Scheme), but instead from the A hat. (In the case of DHIES, this certification would return a full additional signature from the A hat). This efficient authentication CCA encryption is very attractive and usually very attractive for "store-and-forward" applications such as the popular "Pretty-Good Privacy (PGP)" application. Much cheaper than the sign-and-encrypt paradigm. In this case, the only warning is that the ID A hat (and perhaps its certificate) must be transmitted in clear text, as it is necessary for the decryption operation.

Of the other characteristics of the above protocol, it is worth noting that it can only be used as a verifier-specific signature for the A-hat on message m, without necessarily adding an encryption part. However, this signature is unique to the recipient and therefore does not provide non-repudiation. Instead, it provides denialability, which is a very valuable feature in many applications such as PGP.

It should be noted that many standards that employ MQV also employ its one-pass variant. For standards that are interested in adopting HMQV in its various forms (1 message, 2 messages, and 3 messages), the one-pass protocol defines key derivation, similar to the derivation of other variants of HMQV. That will make sense.

Specifically, by replacing Y with B in the double signature that defines the HMQV protocol, the following values are obtained for one pass key, with A and B hats being respectively.<maths num="25"><img file="JP2009526411A_D0025.tif" /></maths>and<maths num="26"><img file="JP2009526411A_D0026.tif" /></maths>And set the key K to a hash of these (equal) values. Note that in this case, the exponent e does not add any value to the protocol, except to make it compatible with other variants. This actually reduces protocol efficiency somewhat.

However, there is an additional value between the 1-pass version of the HMQV with the d = H bar (X, (A hat, B hat)) and the 2-message version with the d = H bar (X, B hat). The contradiction persists. The method of providing compatibility between the three modes has d = H bar (X, B hat), e = H bar (Y, A hat) in any of these, where Y for one pass. ID A hat, where = B and the session key derivation function, that is, K = H (σ, A hat, B hat) (having the order of A hat and B hat defined using some fixed criteria). B hats will be added. This replaces the need to add an A hat in the calculation of d. It also has the advantage of strengthening the HMQV in the event of a pre-computed DH value leak and avoiding potentially unknown key-sharing attacks.

Summary of HMQV security aspects Compared to the traditional MQV protocol, the HMQV protocol offers several performance advantages, including: HMQV demonstrably eliminates the need for expensive prime order tests on DH values transmitted by this protocol. As demonstrated in the provisional application, the only way an attacker can benefit from a choice of rogue DH values is to choose them to be zero, and therefore a simple non-zero. Checking is all you need in HMQV. Therefore, there is no need for a prime degree test or a cofactor h that is used concurrently in the MQV protocol.

Below is a list of the characteristics that the HMQV protocol achieves in a mathematically demonstrable way. (1) HMQV is a strong formal key exchange model of Canetti and Krawczyk and is secure. (2) HMQV withstands spoofing by an attacker who cannot access the private keys of both parties. (3) HMQV applies an XCR signature to the IDs of the parties to the exchange, thus establishing a unique bond between the IDs and keys of those parties by avoiding UKS and other authentication attacks. .. (4) HMQV is safe in the presence of partial leaks of session keys and other session information, in other words, HMQV is resistant to so-called "known key" attacks. Among other things, different session keys are guaranteed to be "computational independent" of each other. (5) This protocol provides an additional level of protection known as resistance to "key-compromise impersonation (KCI)" attacks, that is, it can impersonate another party against A. Prevent an attacker who learns Party A's private key. (6) The 3-message HMQV protocol with key verification provides a verifiable Full Transfer Secret (PFS), i.e., even if the long-term private keys of the two parties are finally disclosed, those parties before the leak. The session key created by is still secure. (7) A three-message protocol with key verification enjoys the additional security advantage of a so-called "general purpose configurable" key exchange protocol, i.e., can be securely configured by other protocols. (8) HMQV security does not rely on special tests on the format and structure of static public keys, and the so-called "proof of ownership" of the corresponding private key. possession) is not required. This advantage of HMQV over similar protocols, including MQV, frees Certificate Authority (CA) from the burden of performing such special checks on registered public keys, resulting in a more realistic approach. Provides a practical security guarantee, especially because many local CAs cannot or are not configured to perform such checks. Moreover, it is worth keeping in mind that the legitimate execution of such tests (eg, proof of ownership) by the CA exposes the protocol to additional security vulnerabilities. (9) The two-message and three-message HMQV protocols do not require testing the order of temporary public keys (ie, values X and Y), thus avoiding tests that can be expensive in some cases. However, such tests are necessary if it is the security of the protocol to withstand an attacker who may learn the temporary private keys of both parties. This test is also necessary for the security of the 1-pass HMQV protocol. Like MQV, these tests can be replaced by a "cofactor power" of the σ value in the protocol. Depending on the underlying algebraic group, additional tests on the elements of the group, such as attribution within a given group, may be required.

One of the key advantages of the HMQV protocol of the present invention is that it is arguably the most efficient authentication Diffie in the presence of a wide range of security properties that can prove to be formally and mathematically valid. -It is a Hellman key exchange protocol. In fact, this formal falsifiability is one of the major differences between HMQV and its predecessor MQV.

Not only did MQV fail to provide proof of security, but over time the explicit weaknesses of this protocol, including some of the weaknesses first mentioned in the provisional application above, have become apparent (over time). For example, a study by Kaliski and a report by Rogaway et al.). Such weaknesses or attacks have invalidated some of the security claims made by the inventor regarding MQV, and in particular have been shown to be unable to prove that MQV is secure.

Comparison of XCR signature and MQV "Implicit Signature" As a method of comparison, it is worth noting that the MQVs described in patents and academic papers also use the concept of signature in protocol design and description. This is referred to as "implicit signature" in relation to MQV and follows the more traditional notion of digital signatures in which only the owner of the private signing key can generate a signature value (specifically, MQV is Refers to an ElGamal-like signature formed by the primary combination of a private signing key with a temporary private key and a public key). However, the protocol does not fully utilize these signature characteristics. Among other things, the MQV protocol does not use signatures as a way to explicitly authenticate the identities of the parties to that protocol, thereby the famous "unknown key share (UKS)" discovered by Kaliski. A serious authentication failure such as occurs.

In contrast, HMQV incorporates two key elements into its design. One is the use of XCR, which is an exponential version of the ElGamal signature. More specifically, this is an exponential version of the Schnorr signature, and then this is a specific instantiation of the ElGamal signature. The other is the explicit signature of the peer's ID, which guarantees the secure binding of the session key to the peer of the session and, among other things, prevents authentication failures such as UKS.

An important novelty of XCR signatures is the property that both the signer and the verifier (or challenger) can calculate the same signature. This property is typically found in authentication mechanisms based on symmetric-key cryptography (ie, when both the signer and verifier have an a-priori shared key), but is new to public key-based signatures. Is. XCR signatures, like HMQV, are not only perfectly suited for derivation of shared keys, but also offer various advantages as an authentication tool, some of which are as described above.

It should be apparent to those skilled in the art that the present invention includes various embodiments.

Therefore, in one exemplary embodiment, there are two parties, verifier V and signer S. Signer S has private key b and public key B, and verifier V owns or obtains S's authentic public key B (eg, via a digital certificate sent by S). is assumed. Authentication protocols for a given message m include: (1) V selects the secret value x and the value X = F₁Calculate (x), where F₁Is a given function, then sends X to S. (2) S selects the secret value y and the value Y = F₂Calculate (y), where F₂Is a given function, then sends Y to V. (3) S is the value s = F₃Calculate (y, b, X, m), where F₃Is a given function, then sends s to V. (4) V is the value s = F₄Calculate (x, Y, B, m) and determine the certainty of m based on the value s'and its association to the received value s.

Some exemplary variants of this embodiment include: (a) F₁, F₂Is a one-way function. In XCR, these one-way functions are X = g^xAnd Y = g^yIs. (b) In the XCR signature, this function<maths num="27"><img file="JP2009526411A_D0027.tif" /></maths>and<maths num="28"><img file="JP2009526411A_D0028.tif" /></maths>Is. (c) Accept m as an authentication only if s = s. This final variant thereby takes advantage of the typical XCR signature characteristics that allow the verifier to recalculate the signature by understanding the secret behind Challenge X. (d)<maths num="29"><img file="JP2009526411A_D0029.tif" /></maths>And test H (s') = s and so on.

In at least one embodiment of the XCR application to HMQV, the value s calculated by S in step (3) is never sent to V. Instead, V calculates a value s'that should be identical to s (unless S is an impostor) and uses s (which is σ in HMQV) there. Derivation of the session key from. Above all, V never performs explicit validation. In this embodiment, it is not a method for verifying the certainty of message m, thereby calculating a common "authenticated value" (ie, a value that only both parties can calculate), and this value. There is a way that is uniquely bound to each ID (an essential condition in a typical key exchange protocol achieved with HMQV by signing the IDs of both parties via a double XCR signature). It will be.

Additional variations are described in the description and claims above.

An exemplary hardware implementation FIG. 10 illustrates a typical hardware configuration of an information processing / computer system according to the invention, which preferably has at least one processor or central processing unit (CPU) 1011. ..

The CPU 1011 is a random access memory (RAM) 1014, read-only memory (ROM) 1016, input / output (I / O) adapter 1018 (disk device) via the system bus 1012. To connect peripherals such as the 1021 and tape drive 1040 to bus 1012), user interface adapter 1022 (keyboard 1024, mouse 1026, speaker 1028, microphone 1032, or other user interface device, or any of these. (To connect the combination to bus 1012), communication adapter 1034 to connect the information processing system to data processing networks, the Internet, intranets, personal area networks (PANs), etc., and bus 1012 to display devices 1038. Or interconnected to a display adapter 1036 for connecting to a printer 1039 (eg, a digital printer) or both.

In addition to the hardware / software embodiments described above, different aspects of the invention include methods performed on a computer to perform the methods described above. As an example, this method can be implemented in the particular embodiments discussed above.

Such a method can be realized, for example, by manipulating a computer performed by a digital data processor to execute a series of machine-readable instructions. These instructions can reside on various types of signal transmission media.

Therefore, this aspect of the invention specifically implements a program consisting of a plurality of machine-readable instructions that can be executed by a digital data processor incorporating the CPU 1011 and the hardware described above in order to carry out the methods of the invention. Targets programmed products including signal transmission media.

The signal transmission medium can include, for example, the RAM housed in the CPU 1011 represented by the high speed access storage device. Alternatively, the instructions can be contained in other signal transmission media such as the magnetic data storage diskette 1100 (FIG. 11), which can be accessed directly or indirectly by the CPU 1011.

Whether housed in diskette 1100, computer / CPU1011, or elsewhere, instructions are DASD storage (eg, traditional "hard disk" or RAID arrays). , Magnetic tape, electronic read-only memory (eg ROM, EPROM, or EEPROM), optical storage (eg CD-ROM, WORM, DVD, digital optical tape, etc.), paper "punch" cards, or digital and It can be stored in various machine-readable data storage media such as analog communication links and other suitable signal transmission media including transmission media such as radio. In one exemplary embodiment of the invention, the machine-readable instruction can include software object code.

<figref num="1">It is a figure which shows the basic (unauthenticated) Diffie-Hellman protocol 100.</figref><figref num="2">FIG. 5 shows a two-message Diffie-Hellman protocol 200 authenticated by using a digital signature.</figref><figref num="3">HMQV shows a comparison of the calculation of the session key K of the conventional MQV protocol to the calculation of the session key of the HMQV protocol of the present invention 300, and which is the hash of an exemplary embodiment that is an addition to the hash used in MQV. It is a figure demonstrating how to use.</figref><figref num="4">Figure 3 shows a different graphic representation of the HMQV protocol 400.</figref><figref num="5">It is a figure which shows the calculation 500 of XCR exemplarily.</figref><figref num="6">It is a figure which shows an example of the calculation 600 of a non-interactive XCR signature.</figref><figref num="7">It is a figure which shows the calculation 700 of the double XCR signature by two parties.</figref><figref num="8">3 Message Key Confirmation (HMQV-C) This is a diagram showing HMQV exemplified by Protocol 800.</figref><figref num="9">It is a figure which shows the HMQV which was carried out exemplarily in 1 pass key exchange 900.</figref><figref num="10">It is a figure exemplifying the exemplary hardware / information processing system 1000 for incorporating the present invention therein.</figref><figref num="11">FIG. 5 illustrates a signal transmission medium 1100 (eg, a storage medium) for storing the steps of the program of the method according to the invention.</figref>