Movatterモバイル変換

Network Working Group                                     R. ZuccheratoRequest for Comments: 2785                         Entrust TechnologiesCategory: Informational                                      March 2000Methods for Avoiding the "Small-Subgroup" Attacks on theDiffie-Hellman Key Agreement Method for S/MIMEStatus 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 encumberedZuccherato                   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 20001.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 inSection 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 20002.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 inSection 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 inSection 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 aZuccherato                   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 20003.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 ofSection 3.1.3.5 Non-compatible Cofactor Exponentiation   This method of protection is specified in [P1363].  Similar to the   method ofSection 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 ofSection 3.1.Zuccherato                   Informational                      [Page 7]

RFC 2785     Methods for Avoiding "Small-Subgroup" Attacks    March 20004. 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 ofSection 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 Sections3.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 20006. 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 inBCP-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",RFC2631, June 1999.   [RFC2633] Ramsdell, B., "S/MIME Version 3 Message Specification",RFC2633, 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.comZuccherato                   Informational                     [Page 10]

RFC 2785     Methods for Avoiding "Small-Subgroup" Attacks    March 20009.  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]