=q). This will prevent an attacker from -being able to find an element of small order modulo p and thus mount -this attack. To produce primes of this form, the prime generation -algorithm could be run multiple times until a prime with this form is -obtained. As an example, the value of r could be tested for primality. -If it is prime the value of p could be accepted, otherwise the prime -generation algorithm would be run again, until a value of p is produced -with r prime. +The prime p could be chosen such that p-1=2*q*j where j 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 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 j could be tested for primality. If j 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 j prime. 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 bit of the private key is a concern. +Thus, this method may not be appropriate in circumstances where the loss +of a single bit of the private key is a concern. -Another option is to choose the prime p such that p = 2*q*r + 1 where r -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. +Another method to produce primes of this form is to choose the prime p +such that p = 2*q*j + 1 where j 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. 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 would compute it as ZZ=(yb^j)^c mod p where -c=j^(-1)*xa mod q. (Similarly for party b.) +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 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 -in S/MIME, some users may however attempt to use this mode and thus we -will describe protection for this case as well. +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. In most ephemeral-ephemeral key agreements protection is required for -both entities. In this situation an attacker 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 +both entities. In this situation a third party attacker 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 comes from some small, easily exhaustible set. +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 Section 3.1. +additionally applying the methods of 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 -example in the Station-To-Station protocol [STS] no protection is -required because a third party would not be able to alter the other -party's public key and thus the only person that could attack the -private key is the other party, who will be able to decrypt the message -anyway. Since the private key is ephemeral, no other messages would be -compromised even if the entire private key was compromised. +party's ephemeral public key has been signed by the other party. 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 concerns security considerations. +This entire document addresses security 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 @@ -279,50 +325,61 @@ 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 +8. Author's Address Robert Zuccherato Entrust Technologies 750 Heron Road Ottawa, Ontario Canada K1V 1A7 robert.zuccherato@entrust.com Appendix A. Full Copyright Statement