RFC 2785 (rfc2785) - Page 3 of 11

Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for S/MIME

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