draft-ietf-smime-small-subgroup-02.txt | rfc2785.txt | |||
---|---|---|---|---|

Internet Draft R. Zuccherato(Entrust Technologies) | ||||

S/MIME Working Group November 1999 | ||||

expires in six months | ||||

Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman | Network Working Group R. Zuccherato | |||

Key Agreement Method for S/MIME | Request for Comments: 2785 Entrust Technologies | |||

<draft-ietf-smime-small-subgroup-02.txt> | Category: Informational March 2000 | |||

Status of this Memo | ||||

This document is an Internet-Draft and is in full conformance with | ||||

all provisions of Section 10 of RFC2026. | ||||

Internet-Drafts are working documents of the Internet Engineering | Methods for Avoiding the "Small-Subgroup" Attacks on the | |||

Task Force (IETF), its areas, and its working groups. Note that other | Diffie-Hellman Key Agreement Method for S/MIME | |||

groups may also distribute working documents as Internet-Drafts. | ||||

Internet-Drafts are draft documents valid for a maximum of six months | Status of this Memo | |||

and may be updated, replaced, or obsoleted by other documents at any | ||||

time. It is inappropriate to use Internet-Drafts as reference | ||||

material or to cite them other than as "work in progress." | ||||

The list of current Internet-Drafts can be accessed at | This memo provides information for the Internet community. It does | |||

http://www.ietf.org/ietf/1id-abstracts.txt | not specify an Internet standard of any kind. Distribution of this | |||

memo is unlimited. | ||||

The list of Internet-Draft Shadow Directories can be accessed at | Copyright Notice | |||

http://www.ietf.org/shadow.html. | ||||

Copyright (C) The Internet Society (1999). All Rights Reserved. | Copyright (C) The Internet Society (2000). All Rights Reserved. | |||

Abstract | Abstract | |||

In some circumstances the use of the Diffie-Hellman key agreement scheme | In some circumstances the use of the Diffie-Hellman key agreement | |||

in a prime order subgroup of a large prime p is vulnerable to certain | scheme in a prime order subgroup of a large prime p is vulnerable to | |||

attacks known as "small-subgroup" attacks. Methods exist, however, to | certain attacks known as "small-subgroup" attacks. Methods exist, | |||

prevent these attacks. This document will describe the situations | however, to prevent these attacks. This document will describe the | |||

relevant to implementations of S/MIME version 3 in which protection is | situations relevant to implementations of S/MIME version 3 in which | |||

required and the methods that can be used to prevent these attacks. | protection is necessary and the methods that can be used to prevent | |||

these attacks. | ||||

1. Introduction | 1. Introduction | |||

This document will describe those situations in which protection from | This document will describe those situations in which protection from | |||

"small-subgroup" type attacks are required when using Diffie-Hellman key | "small-subgroup" type attacks is necessary when using Diffie-Hellman | |||

agreement [x942] in implementations of S/MIME version 3 [CMS, MSG]. | key agreement [RFC2631] in implementations of S/MIME version 3 | |||

Thus, the ephemeral-static modes of Diffie-Hellman will be focused on. | [RFC2630, RFC2633]. Thus, the ephemeral-static and static-static | |||

The situations that require protection are those in which an attacker | modes of Diffie-Hellman will be focused on. Some possible non-S/MIME | |||

could determine a substantial portion (i.e. more than a few bits) of a | usages of CMS are also considered, though with less emphasis than the | |||

user's private key. | cases arising in S/MIME. The situations for which protection is | |||

necessary are those in which an attacker could determine a | ||||

Protecting oneself from these attacks involves certain costs. These | substantial portion (i.e. more than a few bits) of a user's private | |||

costs may include additional processing time either when a public key is | key. | |||

certified or a shared secret key is derived, increased parameter | ||||

generation time, and possibly the licensing of encumbered technologies. | ||||

All of these factors must be considered when deciding whether or not to | Protecting oneself from these attacks involves certain costs. These | |||

protect oneself from these attacks, or whether to engineer the | costs may include additional processing time either when a public key | |||

application so that protection is not required. | is certified or a shared secret key is derived, increased parameter | |||

generation time, and possibly the licensing of encumbered | ||||

technologies. All of these factors must be considered when deciding | ||||

whether or not to protect oneself from these attacks, or whether to | ||||

engineer the application so that protection is not necessary. | ||||

We will not consider "attacks" where the other party in the key | We will not consider "attacks" where the other party in the key | |||

agreement merely forces the shared secret value to be "weak" (i.e. from | agreement merely forces the shared secret value to be "weak" (i.e. | |||

a small set of possible values) without attempting to compromise the | from a small set of possible values) without attempting to compromise | |||

private key. It is not worth the effort to attempt to prevent these | the private key. It is not worth the effort to attempt to prevent | |||

attacks since the other party in the key agreement gets the shared | these attacks since the other party in the key agreement gets the | |||

secret and can simply make the plaintext public. | shared secret and can simply make the plaintext public. | |||

The methods described in this draft may also be used to provide | The methods described in this memo may also be used to provide | |||

protection from similar attacks on elliptic curve based Diffie-Hellman. | protection from similar attacks on elliptic curve based Diffie- | |||

Hellman. | ||||

1.1 Notation | 1.1 Notation | |||

In this document we will use the same notation as in [x942]. In | In this document we will use the same notation as in [RFC2631]. In | |||

particular the shared secret ZZ is generated as follows: | particular the shared secret ZZ is generated as follows: | |||

ZZ = g ^ (xb * xa) mod p | ZZ = g ^ (xb * xa) mod p | |||

Note that the individual parties actually perform the computations: | Note that the individual parties actually perform the computations: | |||

ZZ = (yb ^ xa) mod p = (ya ^ xb) mod p | ZZ = (yb ^ xa) mod p = (ya ^ xb) mod p | |||

where ^ denotes exponentiation. | where ^ denotes exponentiation. | |||

ya is Party A's public key; ya = g ^ xa mod p | ya is Party A's public key; ya = g ^ xa mod p | |||

yb is Party B's public key; yb = g ^ xb mod p | yb is Party B's public key; yb = g ^ xb mod p | |||

xa is Party A's private key | xa is Party A's private key; xa is in the interval [2, (q - 2)] | |||

xb is Party B's private key | xb is Party B's private key; xb is in the interval [2, (q - 2)] | |||

p is a large prime | p is a large prime | |||

g = h^((p-1)/q) mod p, where | g = h^((p-1)/q) mod p, where | |||

h is any integer with 1 < h < p-1 such that h^((p-1)/q) mod p > 1 | h is any integer with 1 < h < p-1 such that h^((p-1)/q) mod p > 1 | |||

(g has order q mod p) | (g has order q mod p) | |||

q is a large prime | q is a large prime | |||

j a large integer such that p=q*j + 1 | j a large integer such that p=q*j + 1 | |||

In this discussion, a "static" public key is one that is certified and | In this discussion, a "static" public key is one that is certified | |||

is used for more than one key agreement, and an "ephemeral" public key | and is used for more than one key agreement, and an "ephemeral" | |||

is one that is not certified but is used only one time. | public key is one that is not certified but is used only one time. | |||

The order of an integer y modulo p is the smallest value of x greater | The order of an integer y modulo p is the smallest value of x greater | |||

than 1 such that y^x mod p = 1. | than 1 such that y^x mod p = 1. | |||

1.2 Brief Description of Attack | 1.2 Brief Description of Attack | |||

For a complete description of these attacks see [LAW98] and [LIM]. | For a complete description of these attacks see [LAW] and [LIM]. | |||

If the other party in an execution of the Diffie-Hellman key agreement | If the other party in an execution of the Diffie-Hellman key | |||

method has a public key not of the form described above, but of small | agreement method has a public key not of the form described above, | |||

order (where small means less than q) then he/she may be able to obtain | but of small order (where small means less than q) then he/she may be | |||

information about the user's private key. In particular, if information | able to obtain information about the user's private key. In | |||

on whether or not a given decryption was successful is available, if | particular, if information on whether or not a given decryption was | |||

ciphertext encrypted with the agreed upon key is available, or if a MAC | successful is available, if ciphertext encrypted with the agreed upon | |||

computed with the agreed upon key is available, information about the | key is available, or if a MAC computed with the agreed upon key is | |||

available, information about the user's private key can be obtained. | ||||

user's private key can be obtained. | Assume Party A has a valid public key ya and that Party B has a | |||

public key yb that is not of the form described in Section 1.1, | ||||

rather yb has order r, where r is much less than q. Thus yb^r=1 mod | ||||

p. Now, when Party A produces ZZ as yb^xa mod p, there will only be | ||||

r possible values for ZZ instead of q-3 possible values. At this | ||||

point Party B does not know the value ZZ, but may be able to | ||||

exhaustively search for it. | ||||

Assume Party A has a properly formatted public key ya and that Party B | If Party A encrypts plaintext with this value and makes that | |||

has a public key yb that is not of the form described in Section 1.1, | ciphertext available to Party B, Party B only needs to exhaustively | |||

rather yb has order r, where r<<q. Thus yb^r=1 mod p. Now, when Party | search through r possibilities to determine which key produced the | |||

A produces ZZ as yb^xa mod p, there will only be r possible values for | ciphertext. When the correct one is found, this gives information | |||

ZZ instead of q possible values. At this point Party B does not know | about the value of xa modulo r. Similarly, if Party A uses ZZ to | |||

the value ZZ, but may be able to exhaustively search for it. | decrypt a ciphertext and Party B is able to determine whether or not | |||

decryption was performed correctly, then information about xa can be | ||||

obtained. The actual number of messages that must be sent or | ||||

received for these attacks to be successful will depend on the | ||||

structure of the prime p. However, it is not unreasonable to expect | ||||

that the entire private key could be determined after as few as one | ||||

hundred messages. | ||||

If Party A encrypts plaintext with this value and makes that ciphertext | A similar attack can be mounted if Party B chooses a public key of | |||

available to Party B, Party B only needs to exhaustively search through | the form yb=g^xb*f, where f is an element of small order. In this | |||

r possibilities to determine which key produced the ciphertext. When | situation Party A will compute ZZ=yb^xa=g^(xa*xb)*f^xa mod p. Again, | |||

the correct one is found, this gives information about the value of xa | Party B can compute g^(xa*xb) and can therefore exhaust the small | |||

modulo r. Similarly, if Party A uses ZZ to decrypt a ciphertext and | number of possible values of f^xa mod p to determine information | |||

Party B is able to determine whether or not decryption was performed | about xa. | |||

correctly, then information about xa can be obtained. The actual number | ||||

of messages that must be sent or received for these attacks to be | ||||

successful will depend on the structure of the prime p. However, it is | ||||

not unreasonable to expect that the entire private key could be | ||||

determined after as few as one hundred messages. | ||||

A similar attack can be mounted if Party B chooses a public key of the | An attack is also possible if Party B has a public key yb of order r | |||

form yb=g^xb*f, where f is an element of small order. In this situation | where r factors into small integers but is not necessarily a small | |||

Party A will compute ZZ=yb^xa=g^(xa*xb)*f^xa mod p. Again, Party B can | integer itself. In this case, the attacker needs to know the value | |||

compute g^(xa*xb) and can therefore exhaust the small number of possible | ZZ computed by Party A. From this value Party B can solve for Party | |||

values of f^xa mod p to determine information about xa. | A's private key modulo r using the Pohlig-Hellman [PH] algorithm. | |||

2. Situations Where Protection Is Required | However, this attack is not as practical as the cases already | |||

presented, where information about the private key is recovered from | ||||

the *use* of ZZ, rather than ZZ itself, by exhaustive search. | ||||

This section describes the situations in which the sender of a message | 2. Situations Where Protection Is Necessary | |||

should obtain protection against this type of attack and also those | ||||

situations in which the receiver of a message should obtain protection. | ||||

Each entity may decide independently whether it requires protection from | ||||

these attacks. | ||||

This discussion assumes that the recipient's key pair is static, as is | This section describes the situations in which the sender of a | |||

always the case in [x942]. | message should obtain protection against this type of attack and also | |||

those situations in which the receiver of a message should obtain | ||||

protection. Each entity may decide independently whether it requires | ||||

protection from these attacks. | ||||

This discussion assumes that the recipient's key pair is static, as | ||||

is always the case in [RFC2631]. | ||||

2.1 Message Sender | 2.1 Message Sender | |||

This section describes situations in which the message sender should be | This section describes situations in which the message sender should | |||

protected. | be protected. | |||

If the sender's key is ephemeral, (i.e. ephemeral-static Diffie-Hellman | If the sender's key is ephemeral, (i.e. ephemeral-static Diffie- | |||

is being used), then no protection is required. In this situation only | Hellman is being used), then no protection is necessary. In this | |||

the recipients of the message can obtain the plaintext and corresponding | situation only the recipients of the message can obtain the plaintext | |||

ciphertext and therefore determine information about the private key | and corresponding ciphertext and therefore determine information | |||

using the "small-subgroup" attacks. However, the recipients can always | about the private key using the "small-subgroup" attacks. However, | |||

decrypt the message and since the sender's key is ephemeral, even if the | the recipients can always decrypt the message and since the sender's | |||

recipient can learn the entire private key no other messages are at | key is ephemeral, even if the recipient can learn the entire private | |||

risk. Notice here that if two or more recipients have selected the same | key no other messages are at risk. Notice here that if two or more | |||

domain parameters (p,q,g) then the same ephemeral public key can be used | recipients have selected the same domain parameters (p,q,g) then the | |||

for all of them. Since the key is ephemeral and only associated with a | same ephemeral public key can be used for all of them. Since the key | |||

message that the recipients can already decrypt, no interesting attacks | is ephemeral and only associated with a message that the recipients | |||

are possible. | can already decrypt, no interesting attacks are possible. | |||

If the sender's key is static (i.e. static-static Diffie-Hellman is | If the sender's key is static (i.e. static-static Diffie-Hellman is | |||

being used), then protection is required because in this situation a | being used), then protection is necessary because in this situation a | |||

recipient mounting a small-subgroup attack will obtain the plaintext and | recipient mounting a small-subgroup attack may be able to obtain the | |||

corresponding ciphertext and therefore could obtain information about | plaintext from another recipient (perhaps one with a valid public key | |||

the private key using the "small-subgroup" attacks. This information | also controlled by the recipient) and therefore could obtain | |||

could then be used to attack other messages protected with the same | information about the private key. Moreover, the attacker does not | |||

static key. | need to know the plaintext to test whether a key is correct, provided | |||

that the plaintext has sufficient redundancy (e.g., ASCII). This | ||||

information could then be used to attack other messages protected | ||||

with the same static key. | ||||

2.2 Message Recipient | 2.2 Message Recipient | |||

This section describes situations in which the message recipient should | This section describes situations in which the message recipient | |||

be protected. | should be protected. | |||

If absolutely no information on the decryption of the ciphertext is | If absolutely no information on the decryption of the ciphertext is | |||

available to any other party than the recipient, then protection is not | available to any other party than the recipient, then protection is | |||

required because this attack requires information on whether the | not necessary because this attack requires information on whether the | |||

decryption was successful to be sent to the attacker. So, no protective | decryption was successful to be sent to the attacker. So, no | |||

measures are needed if the implementation ensures that no information | protective measures are necessary if the implementation ensures that | |||

about the decryption can leak out. However, protection may be warranted | no information about the decryption can leak out. However, | |||

if human users may give this information to the sender via out of band | protection may be warranted if human users may give this information | |||

means (e.g. through telephone conversations). | to the sender via out of band means (e.g. through telephone | |||

conversations). | ||||

If information on the decryption is available to any other party , then | If information on the decryption is available to any other party, | |||

protection is required. | then protection is necessary. In particular, protection is necessary | |||

if any protocol event allows any other party to conclude that | ||||

decryption was successful. Such events include replies and returning | ||||

signed receipts. | ||||

3. Methods Of Protection | 3. Methods Of Protection | |||

This section describes five protective measures that senders and | This section describes five protective measures that senders and | |||

recipients of messages can use to protect themselves from "small- | recipients of messages can use to protect themselves from "small- | |||

subgroup" attacks. | subgroup" attacks. | |||

Implementers should note that some of the procedures described in | ||||

this section may be the subject of patents or pending patents. | ||||

3.1 Public Key Validation | 3.1 Public Key Validation | |||

This method is described in Section 2.1.5 of [x942], and its description | This method is described in Section 2.1.5 of [RFC2631], and its | |||

is repeated here. If this method is used, it should be used to validate | description is repeated here. If this method is used, it should be | |||

public keys of the other party prior to computing the shared secret ZZ. | used to validate public keys of the other party prior to computing | |||

The public key to be validated is y. | the shared secret ZZ. The public key to be validated is y. | |||

1. Verify that y lies within the interval [2,p-1]. If it does not, | 1. Verify that y lies within the interval [2,p-1]. If it does not, | |||

the key is invalid. | the key is invalid. | |||

2. Compute y^q mod p. If the result == 1, the key is valid. | 2. Compute y^q mod p. If the result == 1, the key is valid. | |||

Otherwise the key is invalid. | Otherwise the key is invalid. | |||

Note that this procedure may be subject to pending patents. | ||||

3.2 CA Performs Public Key Validation | 3.2 CA Performs Public Key Validation | |||

The Certification Authority (CA) could perform the Public Key Validation | The Certification Authority (CA) could perform the Public Key | |||

method described in Section 3.1 prior to signing and issuing a | Validation method described in Section 3.1 prior to signing and | |||

certificate containing a Diffie-Hellman public key. In this way, any | issuing a certificate containing a Diffie-Hellman public key. In | |||

party using the public key can be assured that a trusted third party has | this way, any party using the public key can be assured that a | |||

already performed the key validation process. This method is only | trusted third party has already performed the key validation process. | |||

viable for static public keys. When Static-Static Diffie-Hellman is | This method is only viable for static public keys. When Static- | |||

employed, both the sender and recipient are protected when the CA has | Static Diffie-Hellman is employed, both the sender and recipient are | |||

performed public key validation. However, when Ephemeral-Static Diffie- | protected when the CA has performed public key validation. However, | |||

when Ephemeral-Static Diffie-Hellman is employed, only the sender can | ||||

Hellman is employed, only the sender can be protected. Since the sender | be protected by having the CA perform public key validation. Since | |||

uses an ephemeral public key, the CA cannot perform the validation on | the sender generates an ephemeral public key, the CA cannot perform | |||

that public key. | the validation on that public key. | |||

In the case of a static public key a method must exist to assure the | ||||

user that the CA has actually performed this verification. The CA can | ||||

notify certificate users that it has performed the validation by | ||||

reference to the CA's Certificate Policy (CP) and Certification Practice | ||||

Statement (CPS) [RFC2527] or through extensions in the certificate. | ||||

Note that this procedure may be subject to pending patents. | In the case of a static public key a method must exist to assure the | |||

user that the CA has actually performed this verification. The CA | ||||

can notify certificate users that it has performed the validation by | ||||

reference to the CA's Certificate Policy (CP) and Certification | ||||

Practice Statement (CPS) [RFC2527] or through extensions in the | ||||

certificate. | ||||

3.3 Choice of Prime p | 3.3 Choice of Prime p | |||

The prime p could be chosen such that p-1=2*q*j where j is a large prime | The prime p could be chosen such that p-1=2*q*k where k is a large | |||

or is the product of large primes (large means greater than or equal to | prime or is the product of large primes (large means greater than or | |||

q). This will prevent an attacker from being able to find an element of | equal to q). This will prevent an attacker from being able to find | |||

small order modulo p, thus thwarting the small-subgroup attack. One | an element (other than 1 and p-1) of small order modulo p, thus | |||

method to produce primes of this form is to run the prime generation | thwarting the small-subgroup attack. One method to produce primes of | |||

algorithm multiple times until an appropriate prime is obtained. As an | this form is to run the prime generation algorithm multiple times | |||

example, the value of j could be tested for primality. If j is prime, | until an appropriate prime is obtained. As an example, the value of | |||

then the value of p could be accepted, otherwise the prime generation | k could be tested for primality. If k is prime, then the value of p | |||

algorithm would be run again, until a value of p is produced with j | could be accepted, otherwise the prime generation algorithm would be | |||

prime. | run again, until a value of p is produced with k prime. | |||

However, since with primes of this form there is still an element of | However, since with primes of this form there is still an element of | |||

order 2 (i.e. -1), one bit of the private key could still be lost. | order 2 (i.e. p-1), one bit of the private key could still be lost. | |||

Thus, this method may not be appropriate in circumstances where the loss | Thus, this method may not be appropriate in circumstances where the | |||

of a single bit of the private key is a concern. | loss of a single bit of the private key is a concern. | |||

Another method to produce primes of this form is to choose the prime p | Another method to produce primes of this form is to choose the prime | |||

such that p = 2*q*j + 1 where j is small (i.e. only a few bits). In this | p such that p = 2*q*k + 1 where k is small (i.e. only a few bits). In | |||

case, the leakage due to a small subgroup attack will be only a few | this case, the leakage due to a small subgroup attack will be only a | |||

bits. Again, this would not be appropriate for circumstances where the | few bits. Again, this would not be appropriate for circumstances | |||

loss of even a few bits of the private key is a concern. | where the loss of even a few bits of the private key is a concern. In | |||

this approach, q is large. Note that in DSA, q is limited to 160 | ||||

bits for performance reasons, but need not be the case for Diffie- | ||||

Hellman. | ||||

Additionally, other methods (i.e. public key validation) can be combined | Additionally, other methods (i.e. public key validation) can be | |||

with this method in order to prevent the loss of a few bits of the | combined with this method in order to prevent the loss of a few bits | |||

private key. | of the private key. | |||

3.4 Compatible Cofactor Exponentiation | 3.4 Compatible Cofactor Exponentiation | |||

This method of protection is specified in [p1363] and [KALISKI]. It | This method of protection is specified in [P1363] and [KALISKI]. It | |||

involves modifying the computation of ZZ. Instead of computing ZZ as | involves modifying the computation of ZZ by including j (the | |||

ZZ=yb^xa mod p, Party A would compute it as ZZ=(yb^j)^c mod p where | cofactor) in the computations and is compatible with ordinary | |||

c=j^(-1)*xa mod q. (Similarly for Party B.) | Diffie-Hellman when both parties' public keys are valid. If a | |||

party's public key is invalid, then the resulting ZZ will either be 1 | ||||

or an element of order q; the small subgroup elements will either be | ||||

detected or cancelled. This method requires that gcd(j,q)=1. | ||||

If the resulting value ZZ satisfies ZZ==1, then the key agreement should | Instead of computing ZZ as ZZ=yb^xa mod p, Party A would compute it | |||

be abandoned because the public key being used is invalid. | as ZZ=(yb^j)^c mod p where c=j^(-1)*xa mod q. (Similarly for Party | |||

B.) | ||||

Note that this procedure may be subject to pending patents. | If the resulting value ZZ satisfies ZZ==1, then the key agreement | |||

should be abandoned because the public key being used is invalid. | ||||

Note that when j is larger than q, as is usually the case with | ||||

Diffie-Hellman, this method is less efficient than the method of | ||||

Section 3.1. | ||||

3.5 Non-compatible Cofactor Exponentiation | 3.5 Non-compatible Cofactor Exponentiation | |||

This method of protection is specified in [p1363]. Similar to the | This method of protection is specified in [P1363]. Similar to the | |||

method of Section 3.4, it involves modifying the computation of ZZ. | method of Section 3.4, it involves modifying the computation of ZZ by | |||

including j (the cofactor) in the computations. If a party's public | ||||

key is invalid, then the resulting ZZ will either be 1 or an element | ||||

of order q; the small subgroup elements will either be detected or | ||||

cancelled. This method requires that gcd(j,q)=1. | ||||

Instead of computing ZZ as ZZ=yb^xa mod p, Party A would compute it as | Instead of computing ZZ as ZZ=yb^xa mod p, Party A would compute it | |||

ZZ=(yb^j)^xa mod p. (Similarly for Party B.) However, with this method | as ZZ=(yb^j)^xa mod p. (Similarly for Party B.) However, with this | |||

the resulting ZZ value is different from what is computed in [x942] and | method the resulting ZZ value is different from what is computed in | |||

therefore is not interoperable with implementations conformant to | [RFC2631] and therefore is not interoperable with implementations | |||

[x942]. | conformant to [RFC2631]. | |||

If the resulting value ZZ satisfies ZZ==1, then the key agreement should | If the resulting value ZZ satisfies ZZ==1, then the key agreement | |||

be abandoned because the public key being used is invalid. | should be abandoned because the public key being used is invalid. | |||

Note that this procedure may be subject to pending patents. | Note that when j is larger than q, as is usually the case with | |||

Diffie-Hellman, this method is less efficient than the method of | ||||

Section 3.1. | ||||

4. Ephemeral-Ephemeral Key Agreement | 4. Ephemeral-Ephemeral Key Agreement | |||

This situation is when both the sender and recipient of a message are | This situation is when both the sender and recipient of a message are | |||

using ephemeral keys. While this situation is not possible in S/MIME, | using ephemeral keys. While this situation is not possible in | |||

it might be used in other protocol environments. Thus we will briefly | S/MIME, it might be used in other protocol environments. Thus we | |||

discuss protection for this case as well. | will briefly discuss protection for this case as well. | |||

In most ephemeral-ephemeral key agreements protection is required for | Implementers should note that some of the procedures described in | |||

both entities. In this situation a third party attacker could modify | this section may be the subject of patents or pending patents. | |||

the other entity's public key in order to determine the user's private | ||||

key (as described in Section 1.2). Another possibility is that the | ||||

attacker could modify both parties' public key so as to make their | ||||

shared key predictable. For example, the attacker could replace both ya | ||||

and yb with some element of small order, say -1. Then, with a certain | ||||

probability, both the sender and receiver would compute the same shared | ||||

value that comes from some small, easily exhaustible set. | ||||

Note that in this situation if protection was obtained from the methods | Ephemeral-ephemeral key agreement gives an attacker more flexibility | |||

of Section 3.3, then each user must ensure that the other party's public | since both parties' public keys can be changed and they can be | |||

key does not come from the small set of elements of small order. This | coerced into computing the same key from a small space. However, in | |||

can be done either by checking a list of such elements, or by | the ephemeral-static case, only the sender's public key can be | |||

additionally applying the methods of Sections 3.1, 3.4 or 3.5. | changed, and only the recipient can be coerced by an outside attacker | |||

into computing a key from a small space. | ||||

Protection from these attacks is not required however if the other | Thus, in some ephemeral-ephemeral key agreements protection may be | |||

party's ephemeral public key has been signed by the other party. An | necessary for both entities. One possibility is that the attacker | |||

example of this is in the Station-To-Station protocol [STS]. Since the | could modify both parties' public key so as to make their shared key | |||

owner authenticates the public key, a third party cannot modify it and | predictable. For example, the attacker could replace both ya and yb | |||

therefore cannot mount an attack. Thus, the only person that could | with some element of small order, say -1. Then, with a certain | |||

attack an entity's private key is the other authenticated entity in the | probability, both the sender and receiver would compute the same | |||

key agreement. However, since both public keys are ephemeral, they only | shared value that comes from some small, easily exhaustible set. | |||

protect the current session that the attacker would have access to | ||||

anyway. | Note that in this situation if protection was obtained from the | |||

methods of Section 3.3, then each user must ensure that the other | ||||

party's public key does not come from the small set of elements of | ||||

small order. This can be done either by checking a list of such | ||||

elements, or by additionally applying the methods of Sections 3.1, | ||||

3.4 or 3.5. | ||||

Protection from these attacks is not necessary however if the other | ||||

party's ephemeral public key has been authenticated. The | ||||

authentication may be in the form of a signature, MAC, or any other | ||||

integrity protection mechanism. An example of this is in the | ||||

Station-To-Station protocol [STS]. Since the owner authenticates the | ||||

public key, a third party cannot modify it and therefore cannot mount | ||||

an attack. Thus, the only person that could attack an entity's | ||||

private key is the other authenticated entity in the key agreement. | ||||

However, since both public keys are ephemeral, they only protect the | ||||

current session that the attacker would have access to anyway. | ||||

5. Security Considerations | 5. Security Considerations | |||

This entire document addresses security considerations in the | This entire document addresses security considerations in the | |||

implementation of Diffie-Hellman key agreement. | implementation of Diffie-Hellman key agreement. | |||

6. Intellectual Property Rights | 6. Intellectual Property Rights | |||

The IETF takes no position regarding the validity or scope of any | The IETF takes no position regarding the validity or scope of any | |||

intellectual property or other rights that might be claimed to per- | intellectual property or other rights that might be claimed to | |||

tain to the implementation or use of the technology described in this | pertain to the implementation or use of the technology described in | |||

document or the extent to which any license under such rights might | this document or the extent to which any license under such rights | |||

or might not be available; neither does it represent that it has made | might or might not be available; neither does it represent that it | |||

has made any effort to identify any such rights. Information on the | ||||

any effort to identify any such rights. Information on the IETF's | IETF's procedures with respect to rights in standards-track and | |||

procedures with respect to rights in standards-track and standards- | standards-related documentation can be found in BCP-11. Copies of | |||

related documentation can be found in BCP-11. Copies of claims of | claims of rights made available for publication and any assurances of | |||

rights made available for publication and any assurances of licenses | licenses to be made available, or the result of an attempt made to | |||

to be made available, or the result of an attempt made to obtain a | obtain a general license or permission for the use of such | |||

general license or permission for the use of such proprietary rights | proprietary rights by implementors or users of this specification can | |||

by implementors or users of this specification can be obtained from | be obtained from the IETF Secretariat. | |||

the IETF Secretariat. | ||||

The IETF invites any interested party to bring to its attention any | The IETF invites any interested party to bring to its attention any | |||

copyrights, patents or patent applications, or other proprietary | copyrights, patents or patent applications, or other proprietary | |||

rights which may cover technology that may be required to practice | rights which may cover technology that may be required to practice | |||

this standard. Please address the information to the IETF Executive | this standard. Please address the information to the IETF Executive | |||

Director. | Director. | |||

7. References | 7. References | |||

[RFC2527] S. Chokhani and W. Ford, "Internet X.509 Public Key | [KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for | |||

Infrastructure, Certificate Policy and Certification Practices | Diffie-Hellman primitives", Electronics Letters, vol. 34, | |||

Framework", RFC 2527, March 1999. | no. 25, December 10, 1998, pp. 2396-2397. | |||

[STS] W. Diffie, P.C. van Oorschot and M. Wiener, "Authentication and | [LAW] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An | |||

authenticated key exchanges", Designs, Codes and Cryptography, vol. 2, | efficient protocol for authenticated key agreement", | |||

1992, pp. 107-125. | Technical report CORR 98-05, University of Waterloo, 1998. | |||

[CMS] R. Housley, "Cryptographic Message Syntax", draft-ietf-smime-cms- | [LIM] C.H. Lim and P.J. Lee, "A key recovery attack on discrete | |||

XX.txt, work in progress. | log- based schemes using a prime order subgroup", B.S. | |||

Kaliski, Jr., editor, Advances in Cryptology - Crypto '97, | ||||

Lecture Notes in Computer Science, vol. 1295, 1997, | ||||

Springer-Verlag, pp. 249-263. | ||||

[KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for | [P1363] IEEE P1363, Standard Specifications for Public Key | |||

Diffie-Hellman primitives", Electronics Letters, vol. 34, no. 25, | Cryptography, 1998, work in progress. | |||

December 10, 1998, pp. 2396-2397. | ||||

[LAW98] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An | [PH] S.C Pohlig and M.E. Hellman, "An improved algorithm for | |||

efficient protocol for authenticated key agreement", Technical report | computing logarithms over GF(p) and its cryptographic | |||

CORR 98-05, University of Waterloo, 1998. | significance", IEEE Transactions on Information Theory, | |||

vol. 24, 1972, pp. 106-110. | ||||

[LIM] C.H. Lim and P.J. Lee, "A key recovery attack on discrete log- | [RFC2527] Chokhani, S. and W. Ford, "Internet X.509 Public Key | |||

based schemes using a prime order subgroup", B.S. Kaliski, Jr., editor, | Infrastructure, Certificate Policy and Certification | |||

Advances in Cryptology - Crypto '97, Lecture Notes in Computer Science, | Practices Framework", RFC 2527, March 1999. | |||

vol. 1295, 1997, Springer-Verlag, pp. 249-263. | ||||

[P1363] IEEE P1363, Standard Specifications for Public Key Cryptography, | [RFC2630] Housley, R., "Cryptographic Message Syntax", RFC 2630, June | |||

1998, work in progress. | 1999. | |||

[MSG] B. Ramsdell, "S/MIME Version 3 Message Specification", draft-ietf- | [RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", RFC | |||

smime-msg-0X.txt, work in progress. | 2631, June 1999. | |||

[x942] E. Rescorla, "Diffie-Hellman Key Agreement Method", draft-ietf- | [RFC2633] Ramsdell, B., "S/MIME Version 3 Message Specification", RFC | |||

smime-x942-0X.txt, work in progress. | 2633, June 1999. | |||

[STS] W. Diffie, P.C. van Oorschot and M. Wiener, "Authentication | ||||

and authenticated key exchanges", Designs, Codes and | ||||

Cryptography, vol. 2, 1992, pp. 107-125. | ||||

8. Author's Address | 8. Author's Address | |||

Robert Zuccherato | Robert Zuccherato | |||

Entrust Technologies | Entrust Technologies | |||

750 Heron Road | 750 Heron Road | |||

Ottawa, Ontario | Ottawa, Ontario | |||

Canada K1V 1A7 | Canada K1V 1A7 | |||

robert.zuccherato@entrust.com | ||||

Appendix A. Full Copyright Statement | EMail: robert.zuccherato@entrust.com | |||

9. Full Copyright Statement | ||||

Copyright (C) The Internet Society (2000). All Rights Reserved. | ||||

Copyright (C) The Internet Society (date). All Rights Reserved. | ||||

This document and translations of it may be copied and furnished to | This document and translations of it may be copied and furnished to | |||

others, and derivative works that comment on or otherwise explain it | others, and derivative works that comment on or otherwise explain it | |||

or assist in its implementation may be prepared, copied, published | or assist in its implementation may be prepared, copied, published | |||

and distributed, in whole or in part, without restriction of any | and distributed, in whole or in part, without restriction of any | |||

kind, provided that the above copyright notice and this paragraph are | kind, provided that the above copyright notice and this paragraph are | |||

included on all such copies and derivative works. In addition, the | included on all such copies and derivative works. However, this | |||

ASN.1 modules presented in Appendices A and B may be used in whole or | ||||

in part without inclusion of the copyright notice. However, this | ||||

document itself may not be modified in any way, such as by removing | document itself may not be modified in any way, such as by removing | |||

the copyright notice or references to the Internet Society or other | the copyright notice or references to the Internet Society or other | |||

Internet organizations, except as needed for the purpose of develop- | Internet organizations, except as needed for the purpose of | |||

ing Internet standards in which case the procedures for copyrights | developing Internet standards in which case the procedures for | |||

defined in the Internet Standards process shall be followed, or as | copyrights defined in the Internet Standards process must be | |||

required to translate it into languages other than English. | followed, or as required to translate it into languages other than | |||

English. | ||||

The limited permissions granted above are perpetual and will not be | The limited permissions granted above are perpetual and will not be | |||

revoked by the Internet Society or its successors or assigns. This | revoked by the Internet Society or its successors or assigns. | |||

document and the information contained herein is provided on an "AS | ||||

IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK | This document and the information contained herein is provided on an | |||

FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT | "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING | |||

LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL | TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING | |||

NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY | BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION | |||

OR FITNESS FOR A PARTICULAR PURPOSE. | HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF | |||

MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | ||||

Acknowledgement | ||||

Funding for the RFC Editor function is currently provided by the | ||||

Internet Society. | ||||

End of changes. 75 change blocks. | ||||

301 lines changed or deleted | | 346 lines changed or added | ||

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |