One document matched: draft-ietf-smime-small-subgroup-00.txt

Internet Draft                       R. Zuccherato(Entrust Technologies)     
S/MIME Working Group                                          March 1999
expires in six months                                         


Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman 
                    Key Agreement Method for S/MIME
                <draft-ietf-smime-small-subgroup-00.txt>


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 
relevent to the S/MIME standard in which protection is required and the 
methods that can be used to 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 as described in [x942] for S/MIME.  Thus, the ephemeral-static 
modes of Diffie-Hellman will be focussed 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 
encumbered technologies.  All of these factors must be considered when 

Zuccherato                                                        Page 1

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).  These types of attacks are not 
possible to prevent, since the other party may always make the encrypted 
text public anyway.

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=1 mod p. 

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 <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 given 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, 
but 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 ZZ. 

Zuccherato                                                        Page 2

If party a encrypts plaintext with this value and makes that ciphertext 
available to party b, party b only needs to exhaustively search through 
r possibilities to determine which key produced the ciphertext.  When 
the correct one is found, this gives information about the value of xa 
modulo p.  Similarly, if party a uses ZZ to decrypt a ciphertext and 
relays information about the decryption to party b, information about xa 
can be obtained.

Also, if party b has a public key of the form yb=g^xb*f where f is an 
element of small order similar attacks are applicable.  This is because 
party a will now compute ZZ=yb^xa=g^(xa*xb)*f^xa mod p.  Again, party b 
can compute g^(xa*xb) and therefore only has to exhaust the small number 
of possible values of f^xa mod p to determine information about xa.

2. Situations where protection is required

This section will describe the situations in which the sender of a 
message should protect itself against this type of attack and also those 
situations in which the receiver of a message should protect itself.  
Each entity may decide independently whether it requires protection from 
these attacks.

This discussion assumes that the recipient's key pair is static.  This 
is the case in [x942].

2.1 For the sender of a message

If the sender's key is ephemeral (i.e. ephemeral-static Diffie-Hellman 
is being used), then no protection is required.  In this situation only 
the recipient can obtain the plaintext and corresponding ciphertext and 
therefore determine information about the private key using the "small-
subgroup" attacks.  However, the recipient can always decrypt the 
message and since the sender's key is ephemeral, even if the recipient 
can learn the entire private key no other messages are at risk.

If the sender's key is static (i.e. static-static Diffie-Hellman is 
being used), then protection is required because in this situation the 
recipient will obtain the plaintext and corresponding ciphertext and 
therefore could obtain information about the private key using the 
"small-subgroup" attacks.  This information could then be used to attack 
other messages protected with this key.

2.2 For the recipient of a message

If absolutely no information on the decryption of the ciphertext is 
available to any other party than the recipient then protection is not 
required because this attack requires information on whether the 
decryption was successful to be sent to the attacker.  In this situation 
one must be sure that no information about the decryption can leak out.  
For example, human users may give this information to the sender via out 
of band means (e.g. through telephone conversations). 

If information on the decryption is available to any other party , then 
protection is required.



Zuccherato                                                        Page 3


3. Methods of protection

This section lists methods that senders and recipients of messages can 
use to protect themseleves from "small-subgroup" attacks.

3.1 Public Key Validation

This method is described in Section 2.1.5 of [x942] and its description 
is repeated here.  If this method is used, it should be used to validate 
public keys prior to computing the shared secret ZZ.  The public key to 
be validated is y.

     1. Verify that y lies within the interval [2,p-1]. If it does not,
        the key is invalid.
     2. Compute y^q mod p. If the result == 1, the key is valid.
        Otherwise the key is invalid.

Note that this procedure may be subject to pending patents.


3.2 CA Performs Public Key Validation

The CA could perform the Public Key Validation method of Section 3.1 
once for all entities in a PKI.  However, this is only viable for static 
public keys and thus is always possible as a method of protection for 
the sender, but only sometimes possible for the receiver (when Static-
Static DH is implemented).  

In this situation a method must exist to assure the user that the CA has 
actually performed this test.  Possibilities include by reference to the 
CA's Certificate Policy and Certification Practice Statement or through 
extensions in the user's certificate.

3.3 Choice of Prime p

The prime p could be chosen such that p-1=2*q*r where r is the product 
of large primes (large means >=q).  This will prevent an attacker from 
being able to find an element of small order modulo p and thus mount 
this attack.  To produce primes of this form, the prime generation 
algorithm could be run multiple times until a prime with this form is 
obtained.  As an example, the value of r could be tested for primality.  
If it is prime the value of p could be accepted, otherwise the prime 
generation algorithm would be run again, until a value of p is produced 
with r prime.

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.  
Thus, this method may not be appropriate in circumstances where even the 
loss of one bit of the private key is a concern.

Another option is to choose the prime p such that p = 2*q*r + 1 where r 
is small (i.e. only a few bits). In this 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 loss of even a few bits of the 
private key is a concern.

Zuccherato                                                        Page 4


3.4 Compatible Cofactor Exponentiation 

This method of protection is specified in [p1363] and [KALISKI].  It 
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 
c=j^(-1)*xa mod q.  (Similarly for party b.) 

If the resulting value ZZ satisfies ZZ==1, then the key agreement should 
be abandoned because the public key being used is invalid.

Note that this procedure may be subject to pending patents.

4. Ephemeral-Ephemeral Key Agreement

This situation is when both the sender and recipient of a message are 
using ephemeral keys.  While this situation is not specifically allowed 
in S/MIME, some users may however attempt to use this mode and thus we 
will describe protection for this case as well.

In most ephemeral-ephemeral key agreements protection is required for 
both entities.  In this situation an attacker could modify the other 
entity's public key in order to determine the user's private key (as 
described in Section 1.2). Another possibility is that the attacker 
could modify both parties' public key so as to make their shared key 
predictable.  For example, the attacker could replace both ya and yb 
with some element of small order, say -1.  Then, with a certain 
probability, both the sender and receiver would compute the same shared 
value which comes from some small, easily exhaustible set.  

Note that in this situation if protection was obtained from the methods 
of Section 3.3, then each user must ensure that the other party's public 
key does not come from the small set of elements of small order.  This 
can be done either by checking a list of such elements, or by 
additionally applying the methods of Section 3.1.
 
Protection from these attacks is not required however if the other 
party's ephemeral public key has been signed by the other party.  For 
example in the Station-To-Station protocol [STS] no protection is 
required because a third party would not be able to alter the other 
party's public key and thus the only person that could attack the 
private key is the other party, who will be able to decrypt the message 
anyway.  Since the private key is ephemeral, no other messages would be 
compromised even if the entire private key was compromised.

5. Security Considerations

This entire document concerns security considerations.

6. Intellectual Property Rights

The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to per-
tain to the implementation or use of the technology described in this
document or the extent to which any license under such rights might
or might not be available; neither does it represent that it has made

Zuccherato                                                        Page 5

any effort to identify any such rights.  Information on the IETF's
procedures with respect to rights in standards-track and standards-
related documentation can be found in BCP-11.  Copies of claims of
rights made available for publication and any assurances of licenses
to be made available, or the result of an attempt made to obtain a
general license or permission for the use of such proprietary rights
by implementors or users of this specification can be obtained from
the IETF Secretariat.

The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice
this standard.  Please address the information to the IETF Executive
Director.

7. References

[STS] W. Diffie, P.C. van Oorschot and M. Wiener, "Authentication and 
authenticated key exchanges", Designs, Codes and Cryptography, vol. 2, 
1992, pp. 107-125.

[KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for 
Diffie-Hellman primitives", Electronics Letters, vol. 34, no. 25, 
December 10, 1998, pp. 2396-2397.

[LAW98] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An 
efficient protocol for authenticated key agreement", Technical report 
CORR 98-05, University of Waterloo, 1998.

[LIM] C.H. Lim and P.J. Lee, "A key recovery attack on discrete log-
based schemes using a prime order subgroup", B.S. Kaliski, Jr., editor, 
Advances in Cryptology - Crypto '97, Lecture Notes in Computer Science, 
vol. 1295, 1997, Springer-Verlag, pp. 249-263.

[P1363] IEEE P1363, Standard Specifications for Public Key Cryptography, 
1998, work in progress.

[x942] E. Rescorla, "Diffie-Hellman Key Agreement Method", draft-ietf-
smime-x942-0X.txt, work in progress.

8. Authors' Addresses

Robert Zuccherato
Entrust Technologies
750 Heron Road
Ottawa, Ontario
Canada K1V 1A7
robert.zuccherato@entrust.com









Zuccherato                                                        Page 6

Appendix A.  Full Copyright Statement

   Copyright (C) The Internet Society (date). All Rights Reserved.
   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  In addition, the
   ASN.1 modules presented in Appendices A and B may be used in whole or
   in part without inclusion of the copyright notice.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of develop-
   ing Internet standards in which case the procedures for copyrights
   defined in the Internet Standards process shall be followed, or as
   required to translate it into languages other than English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns. This
   document and the information contained herein is provided on an "AS
   IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK
   FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT
   LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL
   NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY
   OR FITNESS FOR A PARTICULAR PURPOSE.































Zuccherato                                                        Page 7