RFC 2785 (rfc2785) - Page 3 of 11
Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for S/MIME
Alternative Format: Original Text Document
RFC 2785 Methods for Avoiding "Small-Subgroup" Attacks March 2000
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, if ciphertext encrypted with the agreed upon
key is available, or if a MAC computed with the agreed upon key is
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 a
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 mod
p. Now, when Party A produces ZZ as yb^xa mod p, there will only be
r possible values for ZZ instead of q-3 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 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 r. Similarly, if Party A uses ZZ to
decrypt a ciphertext and Party B is able to determine whether or not
decryption was performed correctly, then information about xa can be
obtained. The actual number 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 not unreasonable to expect
that the entire private key could be determined after as few as one
hundred messages.
A similar attack can be mounted if Party B chooses a public key of
the form yb=g^xb*f, where f is an element of small order. In this
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 small
number of possible values of f^xa mod p to determine information
about xa.
An attack is also possible if Party B has a public key yb of order r
where r factors into small integers but is not necessarily a small
integer itself. In this case, the attacker needs to know the value
ZZ computed by Party A. From this value Party B can solve for Party
A's private key modulo r using the Pohlig-Hellman [PH] algorithm.
Zuccherato Informational