idnits 2.17.1 draft-ietf-smime-small-subgroup-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 6 longer pages, the longest (page 2) being 59 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 7 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 72 has weird spacing: '...ya ^ xb mod p...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'LAW' is mentioned on line 96, but not defined == Unused Reference: 'LAW98' is defined on line 302, but no explicit reference was found in the text == Unused Reference: 'P1363' is defined on line 311, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'STS' -- Possible downref: Non-RFC (?) normative reference: ref. 'KALISKI' -- Possible downref: Non-RFC (?) normative reference: ref. 'LAW98' -- Possible downref: Non-RFC (?) normative reference: ref. 'LIM' -- Possible downref: Non-RFC (?) normative reference: ref. 'P1363' Summary: 4 errors (**), 0 flaws (~~), 8 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft R. Zuccherato(Entrust Technologies) 2 expires in six months 4 Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman 5 Key Agreement Method for S/MIME 6 8 Status of this Memo 10 This document is an Internet-Draft and is in full conformance with 11 all provisions of Section 10 of RFC2026. 13 Internet-Drafts are working documents of the Internet Engineering 14 Task Force (IETF), its areas, and its working groups. Note that other 15 groups may also distribute working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet-Drafts as reference 20 material or to cite them other than as "work in progress." 22 The list of current Internet-Drafts can be accessed at 23 http://www.ietf.org/ietf/1id-abstracts.txt 25 The list of Internet-Draft Shadow Directories can be accessed at 26 http://www.ietf.org/shadow.html. 28 Copyright (C) The Internet Society (1999). All Rights Reserved. 30 Abstract 32 In some circumstances the use of the Diffie-Hellman key agreement scheme 33 in a prime order subgroup of a large prime p is vulnerable to certain 34 attacks known as "small-subgroup" attacks. Methods exist, however, to 35 prevent these attacks. This document will describe the situations 36 relevent to the S/MIME standard in which protection is required and the 37 methods that can be used to to prevent these attacks. 39 1. Introduction 41 This document will describe those situations in which protection from 42 "small-subgroup" type attacks are required when using Diffie-Hellman key 43 agreement as described in [x942] for S/MIME. Thus, the ephemeral-static 44 modes of Diffie-Hellman will be focussed on. The situations that 45 require protection are those in which an attacker could determine a 46 substantial portion (i.e. more than a few bits) of a user's private key. 48 Protecting oneself from these attacks involves certain costs. These 49 costs may include additional processing time either when a public key is 50 certified or a shared secret key is derived, increased parameter 51 generation time, increased key size, and possibly the licensing of 52 encumbered technologies. All of these factors must be considered when 54 deciding whether or not to protect oneself from these attacks, or 55 whether to engineer the application so that protection is not required. 57 We will not consider "attacks" where the other party in the key 58 agreement merely forces the shared secret value to be "weak" (i.e. from 59 a small set of possible values). These types of attacks are not 60 possible to prevent, since the other party may always make the encrypted 61 text public anyway. 63 1.1 Notation 65 In this document we will use the same notation as in [x942]. In 66 particular the shared secret ZZ is generated as follows: 68 ZZ = g ^ (xb * xa) mod p 70 Note that the individual parties actually perform the computations: 72 ZZ = yb ^ xa (mod p) = ya ^ xb mod p 74 where ^ denotes exponentiation. 76 ya is party a's public key; ya = g ^ xa mod p 77 yb is party b's public key; yb = g ^ xb mod p 78 xa is party a's private key 79 xb is party b's private key 80 p is a large prime 81 g = h^((p-1)/q) mod p, where 82 h is any integer with 1 < h < p-1 such that h^((p-1)/q) mod p > 1 83 (g has order q mod p) 84 q is a large prime 85 j a large integer such that p=q*j + 1 87 In this discussion, a "static" public key is one that is certified and 88 is used for more than one key agreement and an "ephemeral" public key is 89 one that is not certified but is used only one time. 91 The order of an integer y modulo p is the smallest value of x greater 92 than 1 such that y^x=1 mod p. 94 1.2 Brief Description of Attack 96 For a complete description of these attacks see [LAW] and [LIM]. 98 If the other party in an execution of the Diffie-Hellman key agreement 99 method has a public key not of the form described above, but of small 100 order (where small means =q). This will prevent an attacker from 202 being able to find an element of small order modulo p and thus mount 203 this attack. To produce primes of this form, the prime generation 204 algorithm could be run multiple times until a prime with this form is 205 obtained. As an example, the value of r could be tested for primality. 206 If it is prime the value of p could be accepted, otherwise the prime 207 generation algorithm would be run again, until a value of p is produced 208 with r prime. 210 However, since with primes of this form there is still an element of 211 order 2 (i.e. -1), one bit of the private key could still be lost. 212 Thus, this method may not be appropriate in circumstances where even the 213 loss of one bit of the private key is a concern. 215 Another option is to choose the prime p such that p = 2*q*r + 1 where r 216 is small (i.e. only a few bits). In this case, the leakage due to a 217 small subgroup attack will be only a few bits. Again, this would not be 218 appropriate for circumstances where the loss of even a few bits of the 219 private key is a concern. 221 3.4 Compatible Cofactor Exponentiation 223 This method of protection is specified in [p1363] and [KALISKI]. It 224 involves modifying the computation of ZZ. Instead of computing ZZ as 225 ZZ=yb^xa mod p, party a would compute it as ZZ=(yb^j)^c mod p where 226 c=j^(-1)*xa mod q. (Similarly for party b.) 228 If the resulting value ZZ satisfies ZZ==1, then the key agreement should 229 be abandoned because the public key being used is invalid. 231 Note that this procedure may be subject to pending patents. 233 4. Ephemeral-Ephemeral Key Agreement 235 This situation is when both the sender and recipient of a message are 236 using ephemeral keys. While this situation is not specifically allowed 237 in S/MIME, some users may however attempt to use this mode and thus we 238 will describe protection for this case as well. 240 In most ephemeral-ephemeral key agreements protection is required for 241 both entities. In this situation an attacker could modify the other 242 entity's public key in order to determine the user's private key (as 243 described in Section 1.2). Another possibility is that the attacker 244 could modify both parties' public key so as to make their shared key 245 predictable. For example, the attacker could replace both ya and yb 246 with some element of small order, say -1. Then, with a certain 247 probability, both the sender and receiver would compute the same shared 248 value which comes from some small, easily exhaustible set. 250 Note that in this situation if protection was obtained from the methods 251 of Section 3.3, then each user must ensure that the other party's public 252 key does not come from the small set of elements of small order. This 253 can be done either by checking a list of such elements, or by 254 additionally applying the methods of Section 3.1. 256 Protection from these attacks is not required however if the other 257 party's ephemeral public key has been signed by the other party. For 258 example in the Station-To-Station protocol [STS] no protection is 259 required because a third party would not be able to alter the other 260 party's public key and thus the only person that could attack the 261 private key is the other party, who will be able to decrypt the message 262 anyway. Since the private key is ephemeral, no other messages would be 263 compromised even if the entire private key was compromised. 265 5. Security Considerations 267 This entire document concerns security considerations. 269 6. Intellectual Property Rights 271 The IETF takes no position regarding the validity or scope of any 272 intellectual property or other rights that might be claimed to per- 273 tain to the implementation or use of the technology described in this 274 document or the extent to which any license under such rights might 275 or might not be available; neither does it represent that it has made 277 any effort to identify any such rights. Information on the IETF's 278 procedures with respect to rights in standards-track and standards- 279 related documentation can be found in BCP-11. Copies of claims of 280 rights made available for publication and any assurances of licenses 281 to be made available, or the result of an attempt made to obtain a 282 general license or permission for the use of such proprietary rights 283 by implementors or users of this specification can be obtained from 284 the IETF Secretariat. 286 The IETF invites any interested party to bring to its attention any 287 copyrights, patents or patent applications, or other proprietary 288 rights which may cover technology that may be required to practice 289 this standard. Please address the information to the IETF Executive 290 Director. 292 7. References 294 [STS] W. Diffie, P.C. van Oorschot and M. Wiener, "Authentication and 295 authenticated key exchanges", Designs, Codes and Cryptography, vol. 2, 296 1992, pp. 107-125. 298 [KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for 299 Diffie-Hellman primitives", Electronics Letters, vol. 34, no. 25, 300 December 10, 1998, pp. 2396-2397. 302 [LAW98] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An 303 efficient protocol for authenticated key agreement", Technical report 304 CORR 98-05, University of Waterloo, 1998. 306 [LIM] C.H. Lim and P.J. Lee, "A key recovery attack on discrete log- 307 based schemes using a prime order subgroup", B.S. Kaliski, Jr., editor, 308 Advances in Cryptology - Crypto '97, Lecture Notes in Computer Science, 309 vol. 1295, 1997, Springer-Verlag, pp. 249-263. 311 [P1363] IEEE P1363, Standard Specifications for Public Key Cryptography, 312 1998, work in progress. 314 [x942] E. Rescorla, "Diffie-Hellman Key Agreement Method", draft-ietf- 315 smime-x942-0X.txt, work in progress. 317 8. Authors' Addresses 319 Robert Zuccherato 320 Entrust Technologies 321 750 Heron Road 322 Ottawa, Ontario 323 Canada K1V 1A7 324 robert.zuccherato@entrust.com 326 Appendix A. Full Copyright Statement 328 Copyright (C) The Internet Society (date). All Rights Reserved. 329 This document and translations of it may be copied and furnished to 330 others, and derivative works that comment on or otherwise explain it 331 or assist in its implementation may be prepared, copied, published 332 and distributed, in whole or in part, without restriction of any 333 kind, provided that the above copyright notice and this paragraph are 334 included on all such copies and derivative works. In addition, the 335 ASN.1 modules presented in Appendices A and B may be used in whole or 336 in part without inclusion of the copyright notice. However, this 337 document itself may not be modified in any way, such as by removing 338 the copyright notice or references to the Internet Society or other 339 Internet organizations, except as needed for the purpose of develop- 340 ing Internet standards in which case the procedures for copyrights 341 defined in the Internet Standards process shall be followed, or as 342 required to translate it into languages other than English. 344 The limited permissions granted above are perpetual and will not be 345 revoked by the Internet Society or its successors or assigns. This 346 document and the information contained herein is provided on an "AS 347 IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK 348 FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT 349 LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL 350 NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY 351 OR FITNESS FOR A PARTICULAR PURPOSE.