Network Working Group R. Zuccherato Request for Comments: 2785 Entrust Technologies Category: Informational March 2000 Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for S/MIME Status of this Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved.
AbstractIn some circumstances the use of the Diffie-Hellman key agreement scheme in a prime order subgroup of a large prime p is vulnerable to certain attacks known as "small-subgroup" attacks. Methods exist, however, to prevent these attacks. This document will describe the situations relevant to implementations of S/MIME version 3 in which protection is necessary and the methods that can be used to prevent these attacks. RFC2631] in implementations of S/MIME version 3 [RFC2630, RFC2633]. Thus, the ephemeral-static and static-static modes of Diffie-Hellman will be focused on. Some possible non-S/MIME usages of CMS are also considered, though with less emphasis than the cases arising in S/MIME. The situations for which protection is necessary are those in which an attacker could determine a substantial portion (i.e. more than a few bits) of a user's private key. Protecting oneself from these attacks involves certain costs. These costs may include additional processing time either when a public key 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 agreement merely forces the shared secret value to be "weak" (i.e. from a small set of possible values) without attempting to compromise the private key. It is not worth the effort to attempt to prevent these 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 memo may also be used to provide protection from similar attacks on elliptic curve based Diffie- Hellman. RFC2631]. In particular the shared secret ZZ is generated as follows: ZZ = g ^ (xb * xa) mod p Note that the individual parties actually perform the computations: ZZ = (yb ^ xa) mod p = (ya ^ xb) mod p where ^ denotes exponentiation. ya is Party A's public key; ya = g ^ xa mod p yb is Party B's public key; yb = g ^ xb mod p xa is Party A's private key; xa is in the interval [2, (q - 2)] xb is Party B's private key; xb is in the interval [2, (q - 2)] p is a large prime 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 (g has order q mod p) q is a large prime j a large integer such that p=q*j + 1 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 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 than 1 such that y^x mod p = 1.
LAW] and [LIM]. 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 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 on whether or not a given decryption was successful is available, if ciphertext encrypted with the agreed upon 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. 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. If Party A encrypts plaintext with this value and makes that ciphertext available to Party B, Party B only needs to exhaustively search through r possibilities to determine which key produced the ciphertext. When 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 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. A similar attack can be mounted if Party B chooses a public key of the form yb=g^xb*f, where f is an element of small order. In this situation Party A will compute ZZ=yb^xa=g^(xa*xb)*f^xa mod p. Again, Party B can compute g^(xa*xb) and can therefore exhaust the small number of possible values of f^xa mod p to determine information about xa. An attack is also possible if Party B has a public key yb of order r where r factors into small integers but is not necessarily a small integer itself. In this case, the attacker needs to know the value ZZ computed by Party A. From this value Party B can solve for Party A's private key modulo r using the Pohlig-Hellman [PH] algorithm.
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. RFC2631].
Section 2.1.5 of [RFC2631], and its description is repeated here. If this method is used, it should be used to validate public keys of the other party prior to computing 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, the key is invalid. 2. Compute y^q mod p. If the result == 1, the key is valid. Otherwise the key is invalid. Section 3.1 prior to signing and issuing a 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 already performed the key validation process. This method is only viable for static public keys. When Static- Static Diffie-Hellman is employed, both the sender and recipient are protected when the CA has performed public key validation. However, when Ephemeral-Static Diffie-Hellman is employed, only the sender can be protected by having the CA perform public key validation. Since the sender generates an ephemeral public key, the CA cannot perform 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.
P1363] and [KALISKI]. It involves modifying the computation of ZZ by including j (the cofactor) in the computations and is compatible with ordinary 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. Instead of computing ZZ as 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.) 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. P1363]. Similar to the 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 ZZ=(yb^j)^xa mod p. (Similarly for Party B.) However, with this method the resulting ZZ value is different from what is computed in [RFC2631] and therefore is not interoperable with implementations conformant to [RFC2631]. 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.
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.
[KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for Diffie-Hellman primitives", Electronics Letters, vol. 34, no. 25, December 10, 1998, pp. 2396-2397. [LAW] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An efficient protocol for authenticated key agreement", Technical report CORR 98-05, University of Waterloo, 1998. [LIM] C.H. Lim and P.J. Lee, "A key recovery attack on discrete 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. [P1363] IEEE P1363, Standard Specifications for Public Key Cryptography, 1998, work in progress. [PH] S.C Pohlig and M.E. Hellman, "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance", IEEE Transactions on Information Theory, vol. 24, 1972, pp. 106-110.
[RFC2527] Chokhani, S. and W. Ford, "Internet X.509 Public Key Infrastructure, Certificate Policy and Certification Practices Framework", RFC 2527, March 1999. [RFC2630] Housley, R., "Cryptographic Message Syntax", RFC 2630, June 1999. [RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", RFC 2631, June 1999. [RFC2633] Ramsdell, B., "S/MIME Version 3 Message Specification", RFC 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.
Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.