< draft-ietf-smime-small-subgroup-01.txt   draft-ietf-smime-small-subgroup-02.txt >
Internet Draft R. Zuccherato(Entrust Technologies) Internet Draft R. Zuccherato(Entrust Technologies)
S/MIME Working Group November 1999
expires in six months expires in six months
Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman
Key Agreement Method for S/MIME Key Agreement Method for S/MIME
<draft-ietf-smime-small-subgroup-01.txt> <draft-ietf-smime-small-subgroup-02.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts. groups may also distribute working documents as Internet-Drafts.
skipping to change at page 1, line 53 skipping to change at page 1, line 54
"small-subgroup" type attacks are required when using Diffie-Hellman key "small-subgroup" type attacks are required when using Diffie-Hellman key
agreement [x942] in implementations of S/MIME version 3 [CMS, MSG]. agreement [x942] in implementations of S/MIME version 3 [CMS, MSG].
Thus, the ephemeral-static modes of Diffie-Hellman will be focused on. Thus, the ephemeral-static modes of Diffie-Hellman will be focused on.
The situations that require protection are those in which an attacker 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 could determine a substantial portion (i.e. more than a few bits) of a
user's private key. user's private key.
Protecting oneself from these attacks involves certain costs. These Protecting oneself from these attacks involves certain costs. These
costs may include additional processing time either when a public key is costs may include additional processing time either when a public key is
certified or a shared secret key is derived, increased parameter certified or a shared secret key is derived, increased parameter
generation time, increased key size, and possibly the licensing of generation time, and possibly the licensing of encumbered technologies.
encumbered technologies. All of these factors must be considered when All of these factors must be considered when deciding whether or not to
deciding whether or not to protect oneself from these attacks, or protect oneself from these attacks, or whether to engineer the
whether to engineer the application so that protection is not required. application so that protection is not required.
We will not consider "attacks" where the other party in the key 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 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 a small set of possible values) without attempting to compromise the
to prevent these attacks since the other party in the key agreement gets private key. It is not worth the effort to attempt to prevent these
the shared secret and can simply make the plaintext public. 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 draft may also be used to provide
protection from similar attacks on elliptic curve based Diffie-Hellman.
1.1 Notation 1.1 Notation
In this document we will use the same notation as in [x942]. In In this document we will use the same notation as in [x942]. In
particular the shared secret ZZ is generated as follows: particular the shared secret ZZ is generated as follows:
ZZ = g ^ (xb * xa) mod p ZZ = g ^ (xb * xa) mod p
Note that the individual parties actually perform the computations: Note that the individual parties actually perform the computations:
skipping to change at page 2, line 48 skipping to change at page 2, line 52
In this discussion, a "static" public key is one that is certified and 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 used for more than one key agreement, and an "ephemeral" public key
is one that is not certified but is used only one time. 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 The order of an integer y modulo p is the smallest value of x greater
than 1 such that y^x mod p = 1. than 1 such that y^x mod p = 1.
1.2 Brief Description of Attack 1.2 Brief Description of Attack
For a complete description of these attacks see [LAW] and [LIM]. For a complete description of these attacks see [LAW98] and [LIM].
If the other party in an execution of the Diffie-Hellman key agreement 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 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 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 information about the user's private key. In particular, if information
on whether or not a given decryption was successful is available, or if on whether or not a given decryption was successful is available, if
ciphertext encrypted with the agreed upon key is available, information ciphertext encrypted with the agreed upon key is available, or if a MAC
about the user's private key can be obtained. computed 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 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, has a public key yb that is not of the form described in Section 1.1,
rather yb has order r, where r<<q. Thus yb^r=1 mod p. Now, when Party rather yb has order r, where r<<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 A produces ZZ as yb^xa mod p, there will only be r possible values for
ZZ instead of p-1 possible values. ZZ instead of q 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 If Party A encrypts plaintext with this value and makes that ciphertext
available to Party B, Party B only needs to exhaustively search through available to Party B, Party B only needs to exhaustively search through
r possibilities to determine which key produced the ciphertext. When r possibilities to determine which key produced the ciphertext. When
the correct one is found, this gives information about the value of xa 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 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 Party B is able to determine whether or not decryption was performed
correctly, then information about xa can be obtained. The actual number correctly, then information about xa can be obtained. The actual number
of messages that must be sent or received for these attacks to be 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 successful will depend on the structure of the prime p. However, it is
skipping to change at page 4, line 54 skipping to change at page 5, line 4
3.2 CA Performs Public Key Validation 3.2 CA Performs Public Key Validation
The Certification Authority (CA) could perform the 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 method described in Section 3.1 prior to signing and issuing a
certificate containing a Diffie-Hellman public key. In this way, any certificate containing a Diffie-Hellman public key. In this way, any
party using the public key can be assured that a trusted third party has party using the public key can be assured that a trusted third party has
already performed the key validation process. This method is only already performed the key validation process. This method is only
viable for static public keys. When Static-Static Diffie-Hellman is viable for static public keys. When Static-Static Diffie-Hellman is
employed, both the sender and recipient are protected when the CA has employed, both the sender and recipient are protected when the CA has
performed public key validation. However, when Ephemeral-Static Diffie- performed public key validation. However, when Ephemeral-Static Diffie-
Hellman is employed, only the sender can be protected. Since the sender Hellman is employed, only the sender can be protected. Since the sender
uses an ephemeral public key, the CA cannot perform the validation on uses an ephemeral public key, the CA cannot perform the validation on
that public key. that public key.
In this situation a method must exist to assure the user that the CA has In the case of a static public key a method must exist to assure the
actually performed this verification. The CA can notify certificate 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.
users that it has performed the validation by reference to the CA's Note that this procedure may be subject to pending patents.
Certificate Policy (CP)and Certification Practice Statement (CPS)
[RFC2527] or through extensions in the certificate.
3.3 Choice of Prime p 3.3 Choice of Prime p
The prime p could be chosen such that p-1=2*q*j where j is the product The prime p could be chosen such that p-1=2*q*j where j is a large prime
of large primes (large means greater than or equal to q). This will or is the product of large primes (large means greater than or equal to
prevent an attacker from being able to find an element of small order q). This will prevent an attacker from being able to find an element of
modulo p, thus thwarting the small-subgroup attack. One method to small order modulo p, thus thwarting the small-subgroup attack. One
produce primes of this form is to run the prime generation algorithm method to produce primes of this form is to run the prime generation
multiple times until an appropriate prime is obtained. As an example, algorithm multiple times until an appropriate prime is obtained. As an
the value of j could be tested for primality. If j is prime, then the example, the value of j could be tested for primality. If j is prime,
value of p could be accepted, otherwise the prime generation algorithm then the value of p could be accepted, otherwise the prime generation
would be run again, until a value of p is produced with j prime. algorithm would be run again, until a value of p is produced with j
prime.
However, since with primes of this form there is still an element of However, since with primes of this form there is still an element of
order 2 (i.e. -1), one bit of the private key could still be lost. order 2 (i.e. -1), one bit of the private key could still be lost.
Thus, this method may not be appropriate in circumstances where the loss Thus, this method may not be appropriate in circumstances where the loss
of a single bit of the private key is a concern. of a single bit of the private key is a concern.
Another method to produce primes of this form is to choose the prime p Another method to produce primes of this form is to choose the prime p
such that p = 2*q*j + 1 where j is small (i.e. only a few bits). In this such that p = 2*q*j + 1 where j is small (i.e. only a few bits). In this
case, the leakage due to a small subgroup attack will be only a few case, the leakage due to a small subgroup attack will be only a few
bits. Again, this would not be appropriate for circumstances where the bits. Again, this would not be appropriate for circumstances where the
loss of even a few bits of the private key is a concern. loss of even a few bits of the private key is a concern.
Additionally, other methods (i.e. public key validation) can be combined
with this method in order to prevent the loss of a few bits of the
private key.
3.4 Compatible Cofactor Exponentiation 3.4 Compatible Cofactor Exponentiation
This method of protection is specified in [p1363] and [KALISKI]. It This method of protection is specified in [p1363] and [KALISKI]. It
involves modifying the computation of ZZ. Instead of computing ZZ as involves modifying the computation of ZZ. Instead of computing ZZ as
ZZ=yb^xa mod p, Party A would compute it as ZZ=(yb^j)^c mod p where ZZ=yb^xa mod p, Party A would compute it as ZZ=(yb^j)^c mod p where
c=j^(-1)*xa mod q. (Similarly for Party B.) c=j^(-1)*xa mod q. (Similarly for Party B.)
If the resulting value ZZ satisfies ZZ==1, then the key agreement should If the resulting value ZZ satisfies ZZ==1, then the key agreement should
be abandoned because the public key being used is invalid. be abandoned because the public key being used is invalid.
 End of changes. 14 change blocks. 
28 lines changed or deleted 42 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/