diff options
Diffstat (limited to 'doc/rfc/rfc2785.txt')
| -rw-r--r-- | doc/rfc/rfc2785.txt | 619 |
1 files changed, 619 insertions, 0 deletions
diff --git a/doc/rfc/rfc2785.txt b/doc/rfc/rfc2785.txt new file mode 100644 index 0000000..30f6421 --- /dev/null +++ b/doc/rfc/rfc2785.txt @@ -0,0 +1,619 @@ + + + + + + +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. + +Abstract + + In 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. + +1. Introduction + + This document will describe those situations in which protection from + "small-subgroup" type attacks is necessary when using Diffie-Hellman + key agreement [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 + + + + + + +Zuccherato Informational [Page 1] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + + 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. + +1.1 Notation + + In this document we will use the same notation as in [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. + + + + + + +Zuccherato Informational [Page 2] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + +1.2 Brief Description of Attack + + For a complete description of these attacks see [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. + + + + + +Zuccherato Informational [Page 3] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + + 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. + +2. Situations Where Protection Is Necessary + + This section describes the situations in which the sender of a + 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 + + This section describes situations in which the message sender should + be protected. + + If the sender's key is ephemeral, (i.e. ephemeral-static Diffie- + Hellman is being used), then no protection is necessary. In this + situation only the recipients of the message can obtain the plaintext + and corresponding ciphertext and therefore determine information + about the private key using the "small-subgroup" attacks. However, + the recipients can always decrypt the message and since the sender's + key is ephemeral, even if the recipient can learn the entire private + key no other messages are at risk. Notice here that if two or more + recipients have selected the same domain parameters (p,q,g) then the + same ephemeral public key can be used for all of them. Since the key + is ephemeral and only associated with a message that the recipients + can already decrypt, no interesting attacks are possible. + + If the sender's key is static (i.e. static-static Diffie-Hellman is + being used), then protection is necessary because in this situation a + recipient mounting a small-subgroup attack may be able to obtain the + plaintext from another recipient (perhaps one with a valid public key + also controlled by the recipient) and therefore could obtain + information about the private key. Moreover, the attacker does not + 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. + + + + + + + + +Zuccherato Informational [Page 4] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + +2.2 Message Recipient + + This section describes situations in which the message recipient + should be protected. + + If absolutely no information on the decryption of the ciphertext is + available to any other party than the recipient, then protection is + not necessary because this attack requires information on whether the + decryption was successful to be sent to the attacker. So, no + protective measures are necessary if the implementation ensures that + no information about the decryption can leak out. However, + protection may be warranted if human users may give this information + 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 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 + + This section describes five protective measures that senders and + recipients of messages can use to protect themselves from "small- + 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 + + This method is described in 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. + +3.2 CA Performs 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 certificate containing a Diffie-Hellman public key. In + this way, any party using the public key can be assured that a + + + +Zuccherato Informational [Page 5] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + + 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. + +3.3 Choice of Prime p + + The prime p could be chosen such that p-1=2*q*k where k is a large + prime or is the product of large primes (large means greater than or + equal to q). This will prevent an attacker from being able to find + an element (other than 1 and p-1) of small order modulo p, thus + thwarting the small-subgroup attack. One method to produce primes of + this form is to run the prime generation algorithm multiple times + until an appropriate prime is obtained. As an example, the value of + k could be tested for primality. If k is prime, then the value of p + could be accepted, otherwise the prime generation algorithm would be + 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 + 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 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 such that p = 2*q*k + 1 where k is small (i.e. only a few bits). In + this 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 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 with this method in order to prevent the loss of a few bits + of the private key. + + + + + +Zuccherato Informational [Page 6] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + +3.4 Compatible Cofactor Exponentiation + + This method of protection is specified in [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. + +3.5 Non-compatible Cofactor Exponentiation + + This method of protection is specified in [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. + + + + + + + + + +Zuccherato Informational [Page 7] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + +4. Ephemeral-Ephemeral Key Agreement + + 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, it might be used in other protocol environments. Thus we + will briefly discuss protection for this case as well. + + Implementers should note that some of the procedures described in + this section may be the subject of patents or pending patents. + + Ephemeral-ephemeral key agreement gives an attacker more flexibility + since both parties' public keys can be changed and they can be + coerced into computing the same key from a small space. However, in + the ephemeral-static case, only the sender's public key can be + changed, and only the recipient can be coerced by an outside attacker + into computing a key from a small space. + + Thus, in some ephemeral-ephemeral key agreements protection may be + necessary for both entities. One 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 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 + + This entire document addresses security considerations in the + implementation of Diffie-Hellman key agreement. + + + + +Zuccherato Informational [Page 8] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + +6. Intellectual Property Rights + + The IETF takes no position regarding the validity or scope of any + intellectual property or other rights that might be claimed to + pertain to the implementation or use of the technology described in + this document or the extent to which any license under such rights + might or might not be available; neither does it represent that it + has made any effort to identify any such rights. Information on the + IETF's procedures with respect to rights in standards-track and + standards-related documentation can be found in BCP-11. Copies of + claims of rights made available for publication and any assurances of + licenses to be made available, or the result of an attempt made to + obtain a general license or permission for the use of such + proprietary rights by implementors or users of this specification can + be obtained from the IETF Secretariat. + + The IETF invites any interested party to bring to its attention any + copyrights, patents or patent applications, or other proprietary + rights which may cover technology that may be required to practice + this standard. Please address the information to the IETF Executive + Director. + +7. References + + [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. + + + + + + +Zuccherato Informational [Page 9] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + + [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. + +8. Author's Address + + Robert Zuccherato + Entrust Technologies + 750 Heron Road + Ottawa, Ontario + Canada K1V 1A7 + + EMail: robert.zuccherato@entrust.com + + + + + + + + + + + + + + + + + + + + + + + + +Zuccherato Informational [Page 10] + +RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000 + + +9. Full Copyright Statement + + Copyright (C) The Internet Society (2000). All Rights Reserved. + + This document and translations of it may be copied and furnished to + others, and derivative works that comment on or otherwise explain it + or assist in its implementation may be prepared, copied, published + and distributed, in whole or in part, without restriction of any + kind, provided that the above copyright notice and this paragraph are + included on all such copies and derivative works. However, this + document itself may not be modified in any way, such as by removing + the copyright notice or references to the Internet Society or other + Internet organizations, except as needed for the purpose of + developing Internet standards in which case the procedures for + copyrights defined in the Internet Standards process must be + followed, or as required to translate it into languages other than + English. + + The limited permissions granted above are perpetual and will not be + revoked by the Internet Society or its successors or assigns. + + This document and the information contained herein is provided on an + "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING + TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING + BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION + 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. + + + + + + + + + + + + + + + + + + + +Zuccherato Informational [Page 11] + |