## 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