Internet Draft R. Zuccherato(Entrust Technologies)
S/MIME Working Group June 1999
expires in six months
Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman
Key Agreement Method for S/MIME
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright (C) The Internet Society (1999). 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
required 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 are required when using Diffie-Hellman key
agreement [x942] in implementations of S/MIME version 3 [CMS, MSG].
Thus, the ephemeral-static modes of Diffie-Hellman will be focused on.
The situations that require protection 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, increased key size, and possibly the licensing of
Zuccherato Page 1
encumbered 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 required.
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). 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.
1.1 Notation
In this document we will use the same notation as in [x942]. 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
xb is Party B's private key
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.
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, or if
ciphertext encrypted with the agreed upon key is available, information
about the user's private key can be obtained.
Assume Party A has a properly formatted 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<