Internet Draft R. Zuccherato(Entrust Technologies) S/MIME Working Group~~March~~June1999 expires in six months Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for S/MIME~~<draft-ietf-smime-small-subgroup-00.txt>~~<draft-ietf-smime-small-subgroup-01.txt>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 Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months 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 http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright (C) The Internet Society (1999). 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~~relevent~~relevantto~~the~~implementations ofS/MIME~~standard~~version 3in which protection is required and the methods that can be used to~~to~~prevent these attacks. 1. Introduction This document will describe those situations in which protection from "small-subgroup" type attacks are required when using Diffie-Hellman key agreement~~as described in~~[x942]~~for S/MIME.~~in implementations of S/MIME version 3 [CMS, MSG].Thus, the ephemeral-static modes of Diffie-Hellman will be~~focussed~~focusedon. 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 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, increased key size, 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 required. 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).~~These types of attacks are~~It isnot~~possible~~worth the effortto~~prevent,~~attempt to prevent these attackssince the other party~~may always~~in the key agreement gets the shared secret and can simplymake the~~encrypted text public anyway.~~plaintext public.1.1 Notation In this document we will use the same notation as in [x942]. 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~~(yb^~~xa (mod p)~~xa) mod p=~~ya~~(ya^~~xb~~xb)mod p where ^ denotes exponentiation. ya is~~party a's~~Party A'spublic key; ya = g ^ xa mod p yb is~~party b's~~Party B'spublic key; yb = g ^ xb mod p xa is~~party a's~~Party A'sprivate key xb is~~party b's~~Party B'sprivate key 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~~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=1~~y^xmod~~p.~~p = 1.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~~<q)~~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, or if ciphertext encrypted with the~~given~~agreed uponkey is available, information about the user's private key can be obtained. Assume~~party a~~Party Ahas a properly formatted public key ya and that~~party b~~Party Bhas a public key yb that is not of the form described in Section 1.1,~~but~~rather ybhas order~~r~~r,where r<<q. Thus yb^r=1 mod p. Now, when~~party a~~Party Aproduces ZZ as yb^xa mod p, there will only be r possible values for~~ZZ.~~ZZ instead of p-1 possible values.If~~party a~~Party Aencrypts plaintext with this value and makes that ciphertext available to~~party b, party b~~Party B, Party Bonly 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~~p.~~r.Similarly, if~~party a~~Party Auses ZZ to decrypt a ciphertext and~~relays information about the decryption~~Party B is ableto~~party b,~~determine whether or not decryption was performed correctly, theninformation about xa can be obtained.~~Also,~~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 mountedif~~party b has~~Party B choosesa public key of the form~~yb=g^xb*f~~yb=g^xb*f,where f is an element of small~~order similar attacks are applicable. This is because party a~~order. In this situation Party Awill~~now~~compute ZZ=yb^xa=g^(xa*xb)*f^xa mod p. Again,~~party b~~Party Bcan compute g^(xa*xb) andcantherefore~~only has to~~exhaust the small number of possible values of f^xa mod p to determine information about xa. 2. Situations~~where protection is required~~Where Protection Is RequiredThis section~~will describe~~describesthe situations in which the sender of a message should~~protect itself~~obtain protectionagainst this type of attack and also those situations in which the receiver of a message should~~protect itself.~~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. This~~static, asisalwaysthe case in [x942]. 2.1~~For~~Message Sender This section describes situations in whichthe~~sender of a~~messagesender should be protected.If the sender's key is~~ephemeral~~ephemeral,(i.e. ephemeral-static Diffie-Hellman is being used), then no protection is required. In this situation only the~~recipient~~recipients of the messagecan obtain the plaintext and corresponding ciphertext and therefore determine information about the private key using the~~"small- subgroup"~~"small-subgroup"attacks. However, the~~recipient~~recipientscan 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 required because in this situation~~the~~arecipientmounting a small-subgroup attackwill obtain the plaintext and corresponding ciphertext and therefore could obtain information about the private key using the "small-subgroup" attacks. This information could then be used to attack other messages protected with~~this~~the same statickey. 2.2~~For the recipient of a~~Message Recipient This section describes situations in which themessagerecipient should be protected.If absolutely no information on the decryption of the ciphertext is available to any other party than the~~recipient~~recipient,then protection is not required because this attack requires information on whether the decryption was successful to be sent to the attacker.~~In this situation one must be sure~~So, no protective measures are needed if the implementation ensuresthat no information about the decryption can leak out.~~For example,~~However, protection may be warranted ifhuman 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 required. 3. Methods~~of protection~~Of ProtectionThis section~~lists methods~~describes five protective measuresthat senders and recipients of messages can use to protect~~themseleves~~themselvesfrom~~"small-subgroup"~~"small- subgroup"attacks. 3.1 Public Key Validation This method is described in Section 2.1.5 of~~[x942]~~[x942],and its description is repeated here. If this method is used, it should be used to validate public keysof the other partyprior 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. Note that this procedure may be subject to pending patents. 3.2 CA Performs Public Key Validation The~~CA~~Certification Authority (CA)could perform the Public Key Validation method~~of~~described inSection 3.1~~once for all entities in~~prior to signing and issuinga~~PKI. However,~~certificate containing a Diffie-Hellman public key. Inthisway, any party using the public key can be assured that a trusted third party has already performed the key validation process. This methodis only viable for static public~~keys and thus~~keys. When Static-Static Diffie-Hellmanis~~always possible as a method of protection for~~employed, boththe~~sender, but only sometimes possible for~~sender and recipient are protected whenthe~~receiver (when Static- Static DH~~CA has performed public key validation. However, when Ephemeral-Static Diffie- Hellmanis~~implemented).~~employed, only the sender can be protected. Since the sender uses an ephemeral public key, the CA cannot perform the validation on that public key.In this situation a method must exist to assure the user that the CA has actually performed this~~test. Possibilities include~~verification. The CA can notify certificate users that it has performed the validationby reference to the CA's Certificate Policy~~and~~(CP)andCertification Practice Statement(CPS) [RFC2527]or through extensions in the~~user's~~certificate. 3.3 Choice of Prime p The prime p could be chosen such that~~p-1=2*q*r~~p-1=2*q*jwhere~~r~~jis the product of large primes (large means~~>=q).~~greater than or equal to q).This will prevent an attacker from being able to find an element of small order modulo~~p and~~p,thus~~mount this~~thwarting the small-subgroupattack.~~To~~One method toproduce primes of this~~form,~~form is to runthe prime generation algorithm~~could be run~~multiple times until~~a~~an appropriateprime~~with this form~~is obtained. As an example, the value of~~r~~jcould be tested for primality. If~~it~~jis~~prime~~prime, thenthe value of p could be accepted, otherwise the prime generation algorithm would be run again, until a value of p is produced with~~r~~jprime. 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. Thus, this method may not be appropriate in circumstances where~~even~~the loss of~~one~~a singlebit of the private key is a concern. Another~~option~~method to produce primes of this formis to choose the prime p such that p =~~2*q*r~~2*q*j+ 1 where~~r~~jis 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. 3.4 Compatible Cofactor Exponentiation This method of protection is specified in [p1363] and [KALISKI]. It involves modifying the computation of ZZ. Instead of computing ZZ as ZZ=yb^xa mod p,~~party a~~Party Awould compute it as ZZ=(yb^j)^c mod p where c=j^(-1)*xa mod q. (Similarly for~~party b.)~~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 this procedure may be subject to pending patents. 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. 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 [x942] and therefore is not interoperable with implementations conformant to [x942].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 this procedure may be subject to pending patents. 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~~specifically allowed~~possiblein S/MIME,~~some users may however attempt to use this mode and thus~~it might be used in other protocol environments. Thuswe will~~describe~~briefly discussprotection for this case as well. In most ephemeral-ephemeral key agreements protection is required for both entities. In this situation~~an~~a third partyattacker could modify 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~~which~~thatcomes 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~~Section 3.1.~~Sections 3.1, 3.4 or 3.5.Protection from these attacks is not required however if the other party's ephemeral public key has been signed by the other party.~~For~~Anexampleof this isin the Station-To-Station protocol~~[STS] no protection is required because~~[STS]. Since the owner authenticates the public key,a third party~~would not be able to alter the other party's public key~~cannot modify itand~~thus~~therefore cannot mount an attack. Thus,the only person that could attack~~the~~an entity'sprivate key is the other~~party, who will be able to decrypt the message anyway. Since~~authenticated entity inthe~~private~~key~~is~~agreement. However, since both public keys areephemeral,~~no other messages would be compromised even if~~they only protectthe~~entire private key was compromised.~~current session that the attacker would have access to anyway.5. Security Considerations This entire document~~concerns~~addressessecurity~~considerations.~~considerations in the implementation of Diffie-Hellman key agreement.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 per- tain 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[RFC2527] S. Chokhani and W. Ford, "Internet X.509 Public Key Infrastructure, Certificate Policy and Certification Practices Framework", RFC 2527, March 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.[CMS] R. Housley, "Cryptographic Message Syntax", draft-ietf-smime-cms- XX.txt, work in progress.[KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for Diffie-Hellman primitives", Electronics Letters, vol. 34, no. 25, December 10, 1998, pp. 2396-2397. [LAW98] 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.[MSG] B. Ramsdell, "S/MIME Version 3 Message Specification", draft-ietf- smime-msg-0X.txt, work in progress.[x942] E. Rescorla, "Diffie-Hellman Key Agreement Method", draft-ietf- smime-x942-0X.txt, work in progress. 8.~~Authors' Addresses~~Author's AddressRobert Zuccherato Entrust Technologies 750 Heron Road Ottawa, Ontario Canada K1V 1A7 robert.zuccherato@entrust.com Appendix A. Full Copyright Statement Copyright (C) The Internet Society (date). 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. In addition, the 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 the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of develop- ing Internet standards in which case the procedures for copyrights defined in the Internet Standards process shall 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.