Browse Prior Art Database

Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for (RFC2785)

IP.com Disclosure Number: IPCOM000003384D
Original Publication Date: 2000-Mar-01
Included in the Prior Art Database: 2000-Sep-13
Document File: 9 page(s) / 23K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

R. Zuccherato: AUTHOR

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.

This text was extracted from a ASCII Text document.
This is the abbreviated version, containing approximately 13% of the total text.

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

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 ^...