rfc2785.txt

RFC 的详细文档！

Network Working Group                                     R. Zuccherato
Request for Comments: 2785                         Entrust Technologies
Category: Informational                                      March 2000


       Methods for Avoiding the "Small-Subgroup" Attacks on the
             Diffie-Hellman Key Agreement Method for S/MIME

Status 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 encumbered






Zuccherato                   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 2000


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 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 in Section 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 2000


2.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 in Section 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 in Section 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 a



Zuccherato                   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