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

Document Type RFC - Informational (March 2000; No errata)
Last updated 2013-03-02
Stream IETF
Formats plain text pdf htmlized bibtex
Stream WG state (None)
Document shepherd No shepherd assigned
IESG IESG state RFC 2785 (Informational)
Consensus Boilerplate Unknown
Telechat date
Responsible AD (None)
Send notices to (None)
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,
Show full document text