rfc2785.txt

RFC 的详细文档！

   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: [e-mail]
























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]