As per Relevance of the word situation, we have this rfc below:
Network Working Group R.
Request for Comments: 2785 Entrust
Category: Informational March 2000
Methods for Avoiding the "Small-Subgroup" Attacks on
Diffie-Hellman Key Agreement Method for S/
Status of this
This memo provides information for the Internet community. It
not specify an Internet standard of any kind. Distribution of
memo is unlimited
Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
In some circumstances the use of the Diffie-Hellman key
scheme in a prime order subgroup of a large prime p is vulnerable
certain attacks known as "small-subgroup" attacks. Methods exist
however, to prevent these attacks. This document will describe
situations relevant to implementations of S/MIME version 3 in
protection is necessary and the methods that can be used to
these attacks
1.
This document will describe those situations in which protection
"small-subgroup" type attacks is necessary when using Diffie-
key agreement [RFC2631] in implementations of S/MIME version 3
[RFC2630, RFC2633]. Thus, the ephemeral-static and static-
modes of Diffie-Hellman will be focused on. Some possible non-S/
usages of CMS are also considered, though with less emphasis than
cases arising in S/MIME. The situations for which protection
necessary are those in which an attacker could determine
substantial portion (i.e. more than a few bits) of a user's
key
Protecting oneself from these attacks involves certain costs.
costs may include additional processing time either when a public
is certified or a shared secret key is derived, increased
generation time, and possibly the licensing of
Zuccherato Informational [Page 1]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
technologies. All of these factors must be considered when
whether or not to protect oneself from these attacks, or whether
engineer the application so that protection is not necessary
We will not consider "attacks" where the other party in the
agreement merely forces the shared secret value to be "weak" (i.e
from a small set of possible values) without attempting to
the private key. It is not worth the effort to attempt to
these attacks since the other party in the key agreement gets
shared secret and can simply make the plaintext public
The methods described in this memo may also be used to
protection from similar attacks on elliptic curve based Diffie
Hellman
1.1
In this document we will use the same notation as in [RFC2631].
particular the shared secret ZZ is generated as follows
ZZ = g ^ (xb * xa) mod
Note that the individual parties actually perform the computations
ZZ = (yb ^ xa) mod p = (ya ^ xb) mod
where ^ denotes exponentiation
ya is Party A's public key; ya = g ^ xa mod
yb is Party B's public key; yb = g ^ xb mod
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
g = h^((p-1)/q) mod p,
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
j a large integer such that p=q*j + 1
In this discussion, a "static" public key is one that is
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
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
For a complete description of these attacks see [LAW] and [LIM].
If the other party in an execution of the Diffie-Hellman
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
able to obtain information about the user's private key.
particular, if information on whether or not a given decryption
successful is available, if ciphertext encrypted with the agreed
key is available, or if a MAC computed with the agreed upon key
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
public key yb that is not of the form described in Section 1.1,
rather yb has order r, where r is much less than q. Thus yb^r=1
p. Now, when Party A produces ZZ as yb^xa mod p, there will only
r possible values for ZZ instead of q-3 possible values. At
point Party B does not know the value ZZ, but may be able
exhaustively search for it
If Party A encrypts plaintext with this value and makes
ciphertext available to Party B, Party B only needs to
search through r possibilities to determine which key produced
ciphertext. When the correct one is found, this gives
about the value of xa modulo r. Similarly, if Party A uses ZZ
decrypt a ciphertext and Party B is able to determine whether or
decryption was performed correctly, then information about xa can
obtained. The actual number of messages that must be sent
received for these attacks to be successful will depend on
structure of the prime p. However, it is not unreasonable to
that the entire private key could be determined after as few as
hundred messages
A similar attack can be mounted if Party B chooses a public key
the form yb=g^xb*f, where f is an element of small order. In
situation Party A will compute ZZ=yb^xa=g^(xa*xb)*f^xa mod p. Again
Party B can compute g^(xa*xb) and can therefore exhaust the
number of possible values of f^xa mod p to determine
about xa
An attack is also possible if Party B has a public key yb of order
where r factors into small integers but is not necessarily a
integer itself. In this case, the attacker needs to know the
ZZ computed by Party A. From this value Party B can solve for
A's private key modulo r using the Pohlig-Hellman [PH] algorithm
Zuccherato Informational [Page 3]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
However, this attack is not as practical as the cases
presented, where information about the private key is recovered
the *use* of ZZ, rather than ZZ itself, by exhaustive search
2. Situations Where Protection Is
This section describes the situations in which the sender of
message should obtain protection against this type of attack and
those situations in which the receiver of a message should
protection. Each entity may decide independently whether it
protection from these attacks
This discussion assumes that the recipient's key pair is static,
is always the case in [RFC2631].
2.1 Message
This section describes situations in which the message sender
be protected
If the sender's key is ephemeral, (i.e. ephemeral-static Diffie
Hellman is being used), then no protection is necessary. In
situation only the recipients of the message can obtain the
and corresponding ciphertext and therefore determine
about the private key using the "small-subgroup" attacks. However
the recipients can always decrypt the message and since the sender'
key is ephemeral, even if the recipient can learn the entire
key no other messages are at risk. Notice here that if two or
recipients have selected the same domain parameters (p,q,g) then
same ephemeral public key can be used for all of them. Since the
is ephemeral and only associated with a message that the
can already decrypt, no interesting attacks are possible
If the sender's key is static (i.e. static-static Diffie-Hellman
being used), then protection is necessary because in this situation
recipient mounting a small-subgroup attack may be able to obtain
plaintext from another recipient (perhaps one with a valid public
also controlled by the recipient) and therefore could
information about the private key. Moreover, the attacker does
need to know the plaintext to test whether a key is correct,
that the plaintext has sufficient redundancy (e.g., ASCII).
information could then be used to attack other messages
with the same static key
Zuccherato Informational [Page 4]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
2.2 Message
This section describes situations in which the message
should be protected
If absolutely no information on the decryption of the ciphertext
available to any other party than the recipient, then protection
not necessary because this attack requires information on whether
decryption was successful to be sent to the attacker. So,
protective measures are necessary if the implementation ensures
no information about the decryption can leak out. However
protection may be warranted if human users may give this
to the sender via out of band means (e.g. through
conversations).
If information on the decryption is available to any other party
then protection is necessary. In particular, protection is
if any protocol event allows any other party to conclude
decryption was successful. Such events include replies and
signed receipts
3. Methods Of
This section describes five protective measures that senders
recipients of messages can use to protect themselves from "small
subgroup" attacks
Implementers should note that some of the procedures described
this section may be the subject of patents or pending patents
3.1 Public Key
This method is described in Section 2.1.5 of [RFC2631], and
description is repeated here. If this method is used, it should
used to validate public keys of the other party prior to
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
3.2 CA Performs Public Key
The Certification Authority (CA) could perform the Public
Validation method described in Section 3.1 prior to signing
issuing a certificate containing a Diffie-Hellman public key.
this way, any party using the public key can be assured that
Zuccherato Informational [Page 5]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
trusted third party has already performed the key validation process
This method is only viable for static public keys. When Static
Static Diffie-Hellman is employed, both the sender and recipient
protected when the CA has performed public key validation. However
when Ephemeral-Static Diffie-Hellman is employed, only the sender
be protected by having the CA perform public key validation.
the sender generates an ephemeral public key, the CA cannot
the validation on that public key
In the case of a static public key a method must exist to assure
user that the CA has actually performed this verification. The
can notify certificate users that it has performed the validation
reference to the CA's Certificate Policy (CP) and
Practice Statement (CPS) [RFC2527] or through extensions in
certificate
3.3 Choice of Prime
The prime p could be chosen such that p-1=2*q*k where k is a
prime or is the product of large primes (large means greater than
equal to q). This will prevent an attacker from being able to
an element (other than 1 and p-1) of small order modulo p,
thwarting the small-subgroup attack. One method to produce primes
this form is to run the prime generation algorithm multiple
until an appropriate prime is obtained. As an example, the value
k could be tested for primality. If k is prime, then the value of
could be accepted, otherwise the prime generation algorithm would
run again, until a value of p is produced with k prime
However, since with primes of this form there is still an element
order 2 (i.e. p-1), one bit of the private key could still be lost
Thus, this method may not be appropriate in circumstances where
loss of a single bit of the private key is a concern
Another method to produce primes of this form is to choose the
p such that p = 2*q*k + 1 where k is small (i.e. only a few bits).
this case, the leakage due to a small subgroup attack will be only
few bits. Again, this would not be appropriate for
where the loss of even a few bits of the private key is a concern.
this approach, q is large. Note that in DSA, q is limited to 160
bits for performance reasons, but need not be the case for Diffie
Hellman
Additionally, other methods (i.e. public key validation) can
combined with this method in order to prevent the loss of a few
of the private key
Zuccherato Informational [Page 6]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
3.4 Compatible Cofactor
This method of protection is specified in [P1363] and [KALISKI].
involves modifying the computation of ZZ by including j (
cofactor) in the computations and is compatible with
Diffie-Hellman when both parties' public keys are valid. If
party's public key is invalid, then the resulting ZZ will either be 1
or an element of order q; the small subgroup elements will either
detected or cancelled. This method requires that gcd(j,q)=1.
Instead of computing ZZ as ZZ=yb^xa mod p, Party A would compute
as ZZ=(yb^j)^c mod p where c=j^(-1)*xa mod q. (Similarly for
B.)
If the resulting value ZZ satisfies ZZ==1, then the key
should be abandoned because the public key being used is invalid
Note that when j is larger than q, as is usually the case
Diffie-Hellman, this method is less efficient than the method
Section 3.1.
3.5 Non-compatible Cofactor
This method of protection is specified in [P1363]. Similar to
method of Section 3.4, it involves modifying the computation of ZZ
including j (the cofactor) in the computations. If a party's
key is invalid, then the resulting ZZ will either be 1 or an
of order q; the small subgroup elements will either be detected
cancelled. This method requires that gcd(j,q)=1.
Instead of computing ZZ as ZZ=yb^xa mod p, Party A would compute
as ZZ=(yb^j)^xa mod p. (Similarly for Party B.) However, with
method the resulting ZZ value is different from what is computed
[RFC2631] and therefore is not interoperable with
conformant to [RFC2631].
If the resulting value ZZ satisfies ZZ==1, then the key
should be abandoned because the public key being used is invalid
Note that when j is larger than q, as is usually the case
Diffie-Hellman, this method is less efficient than the method
Section 3.1.
Zuccherato Informational [Page 7]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
4. Ephemeral-Ephemeral Key
This situation is when both the sender and recipient of a message
using ephemeral keys. While this situation is not possible
S/MIME, it might be used in other protocol environments. Thus
will briefly discuss protection for this case as well
Implementers should note that some of the procedures described
this section may be the subject of patents or pending patents
Ephemeral-ephemeral key agreement gives an attacker more
since both parties' public keys can be changed and they can
coerced into computing the same key from a small space. However,
the ephemeral-static case, only the sender's public key can
changed, and only the recipient can be coerced by an outside
into computing a key from a small space
Thus, in some ephemeral-ephemeral key agreements protection may
necessary for both entities. One possibility is that the
could modify both parties' public key so as to make their shared
predictable. For example, the attacker could replace both ya and
with some element of small order, say -1. Then, with a
probability, both the sender and receiver would compute the
shared value that comes from some small, easily exhaustible set
Note that in this situation if protection was obtained from
methods of Section 3.3, then each user must ensure that the
party's public key does not come from the small set of elements
small order. This can be done either by checking a list of
elements, or by additionally applying the methods of Sections 3.1,
3.4 or 3.5.
Protection from these attacks is not necessary however if the
party's ephemeral public key has been authenticated.
authentication may be in the form of a signature, MAC, or any
integrity protection mechanism. An example of this is in
Station-To-Station protocol [STS]. Since the owner authenticates
public key, a third party cannot modify it and therefore cannot
an attack. Thus, the only person that could attack an entity'
private key is the other authenticated entity in the key agreement
However, since both public keys are ephemeral, they only protect
current session that the attacker would have access to anyway
5. Security
This entire document addresses security considerations in
implementation of Diffie-Hellman key agreement
Zuccherato Informational [Page 8]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
6. Intellectual Property
The IETF takes no position regarding the validity or scope of
intellectual property or other rights that might be claimed
pertain to the implementation or use of the technology described
this document or the extent to which any license under such
might or might not be available; neither does it represent that
has made any effort to identify any such rights. Information on
IETF's procedures with respect to rights in standards-track
standards-related documentation can be found in BCP-11. Copies
claims of rights made available for publication and any assurances
licenses to be made available, or the result of an attempt made
obtain a general license or permission for the use of
proprietary rights by implementors or users of this specification
be obtained from the IETF Secretariat
The IETF invites any interested party to bring to its attention
copyrights, patents or patent applications, or other
rights which may cover technology that may be required to
this standard. Please address the information to the IETF
Director
7.
[KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication
Diffie-Hellman primitives", Electronics Letters, vol. 34,
no. 25, December 10, 1998, pp. 2396-2397.
[LAW] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "
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
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
Cryptography, 1998, work in progress
[PH] S.C Pohlig and M.E. Hellman, "An improved algorithm
computing logarithms over GF(p) and its
significance", IEEE Transactions on Information Theory
vol. 24, 1972, pp. 106-110.
Zuccherato Informational [Page 9]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
[RFC2527] Chokhani, S. and W. Ford, "Internet X.509 Public
Infrastructure, Certificate Policy and
Practices Framework", RFC 2527, March 1999.
[RFC2630] Housley, R., "Cryptographic Message Syntax", RFC 2630,
1999.
[RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method",
2631, June 1999.
[RFC2633] Ramsdell, B., "S/MIME Version 3 Message Specification",
2633, June 1999.
[STS] W. Diffie, P.C. van Oorschot and M. Wiener, "
and authenticated key exchanges", Designs, Codes
Cryptography, vol. 2, 1992, pp. 107-125.
8. Author's
Robert
Entrust
750 Heron
Ottawa,
Canada K1V 1A
EMail: robert.zuccherato@entrust.
Zuccherato Informational [Page 10]
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
9. Full Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
This document and translations of it may be copied and furnished
others, and derivative works that comment on or otherwise explain
or assist in its implementation may be prepared, copied,
and distributed, in whole or in part, without restriction of
kind, provided that the above copyright notice and this paragraph
included on all such copies and derivative works. However,
document itself may not be modified in any way, such as by
the copyright notice or references to the Internet Society or
Internet organizations, except as needed for the purpose
developing Internet standards in which case the procedures
copyrights defined in the Internet Standards process must
followed, or as required to translate it into languages other
English
The limited permissions granted above are perpetual and will not
revoked by the Internet Society or its successors or assigns
This document and the information contained herein is provided on
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE
Funding for the RFC Editor function is currently provided by
Internet Society
Zuccherato Informational [Page 11]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
