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

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

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

expires in six months | expires in six months | |||

Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman | Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman | |||

Key Agreement Method for S/MIME | Key Agreement Method for S/MIME | |||

<draft-ietf-smime-small-subgroup-01.txt> | <draft-ietf-smime-small-subgroup-02.txt> | |||

Status of this Memo | Status of this Memo | |||

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

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

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF), its areas, and its working groups. Note that other | Task Force (IETF), its areas, and its working groups. Note that other | |||

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

skipping to change at line 53 | skipping to change at line 53 | |||

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

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

Thus, the ephemeral-static modes of Diffie-Hellman will be focused on. | Thus, the ephemeral-static modes of Diffie-Hellman will be focused on. | |||

The situations that require protection are those in which an attacker | The situations that require protection are those in which an attacker | |||

could determine a substantial portion (i.e. more than a few bits) of a | could determine a substantial portion (i.e. more than a few bits) of a | |||

user's private key. | user's private key. | |||

Protecting oneself from these attacks involves certain costs. These | Protecting oneself from these attacks involves certain costs. These | |||

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

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

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

encumbered technologies. All of these factors must be considered when | All of these factors must be considered when deciding whether or not to | |||

deciding whether or not to protect oneself from these attacks, or | protect oneself from these attacks, or whether to engineer the | |||

whether to engineer the application so that protection is not required. | application so that protection is not required. | |||

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. from | |||

a small set of possible values). It is not worth the effort to attempt | a small set of possible values) without attempting to compromise the | |||

to prevent these attacks since the other party in the key agreement gets | private key. It is not worth the effort to attempt to prevent these | |||

the shared secret and can simply make the plaintext public. | attacks since the other party in the key agreement gets the shared | |||

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

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

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 [x942]. 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: | |||

skipping to change at line 98 | skipping to change at line 102 | |||

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 and | |||

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

is one that is not certified but is used only one time. | 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 [LAW] and [LIM]. | For a complete description of these attacks see [LAW98] 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 agreement | |||

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

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

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

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

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

about the user's private key can be obtained. | computed with the agreed upon key is available, information about the | |||

user's private key can be obtained. | ||||

Assume Party A has a properly formatted public key ya and that Party B | Assume Party A has a properly formatted public key ya and that Party B | |||

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

rather yb has order r, where r<<q. Thus yb^r=1 mod p. Now, when Party | rather yb has order r, where r<<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 | A produces ZZ as yb^xa mod p, there will only be r possible values for | |||

ZZ instead of p-1 possible values. | ZZ instead of q possible values. At this point Party B does not know | |||

the value ZZ, but may be able to exhaustively search for it. | ||||

If Party A encrypts plaintext with this value and makes that ciphertext | If Party A encrypts plaintext with this value and makes that ciphertext | |||

available to Party B, Party B only needs to exhaustively search through | available to Party B, Party B only needs to exhaustively search through | |||

r possibilities to determine which key produced the ciphertext. When | r possibilities to determine which key produced the ciphertext. When | |||

the correct one is found, this gives information about the value of xa | the correct one is found, this gives information about the value of xa | |||

modulo r. Similarly, if Party A uses ZZ to decrypt a ciphertext and | modulo r. Similarly, if Party A uses ZZ to decrypt a ciphertext and | |||

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

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

of messages that must be sent or received for these attacks to be | 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 | successful will depend on the structure of the prime p. However, it is | |||

skipping to change at line 218 | skipping to change at line 223 | |||

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 Validation | |||

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

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

party using the public key can be assured that a trusted third party has | party using the public key can be assured that a trusted third party has | |||

already performed the key validation process. This method is only | already performed the key validation process. This method is only | |||

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

employed, both the sender and recipient are protected when the CA has | employed, both the sender and recipient are protected when the CA has | |||

performed public key validation. However, when Ephemeral-Static Diffie- | performed public key validation. However, when Ephemeral-Static Diffie- | |||

Hellman is employed, only the sender can be protected. Since the sender | Hellman is employed, only the sender can be protected. Since the sender | |||

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

that public key. | that public key. | |||

In this situation a method must exist to assure the user that the CA has | In the case of a static public key a method must exist to assure the | |||

actually performed this verification. The CA can notify certificate | 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. | ||||

users that it has performed the validation by reference to the CA's | Note that this procedure may be subject to pending patents. | |||

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 the product | The prime p could be chosen such that p-1=2*q*j where j is a large prime | |||

of large primes (large means greater than or equal to q). This will | or is the product of large primes (large means greater than or equal to | |||

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

modulo p, thus thwarting the small-subgroup attack. One method to | small order modulo p, thus thwarting the small-subgroup attack. One | |||

produce primes of this form is to run the prime generation algorithm | method to produce primes of this form is to run the prime generation | |||

multiple times until an appropriate prime is obtained. As an example, | algorithm multiple times until an appropriate prime is obtained. As an | |||

the value of j could be tested for primality. If j is prime, then the | example, the value of j could be tested for primality. If j is prime, | |||

value of p could be accepted, otherwise the prime generation algorithm | then the value of p could be accepted, otherwise the prime generation | |||

would be run again, until a value of p is produced with j prime. | algorithm would be run again, until a value of p is produced with j | |||

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. -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 loss | |||

of a single bit of the private key is a concern. | 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 p | |||

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

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

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

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

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

with this method in order to prevent the loss of a few bits 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. Instead of computing ZZ as | |||

ZZ=yb^xa mod p, Party A would compute it as ZZ=(yb^j)^c mod p where | ZZ=yb^xa mod p, Party A would compute it as ZZ=(yb^j)^c mod p where | |||

c=j^(-1)*xa mod q. (Similarly for Party B.) | c=j^(-1)*xa mod q. (Similarly for Party B.) | |||

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 should | |||

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

End of changes. | ||||

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/ |