RFC 2785

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

📅 published March 2000, from ietf

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

  • RFC: 2785 🎀
  • Stream: Network Working Group 🌸
  • Author: R. Zuccherato, Entrust Technologies ✨
  • Category: Informational 📖
  • Date: March 2000 🗓️
  • Obsoletes / Updates: nothing listed here 🦋

Status of this Memo 💅

Okay so this memo is just here to inform the Internet community 🫶 It does not specify an Internet standard of any kind, so nobody is being told to do anything. It's also unlimited distribution, so share it with your whole group chat 💜

Copyright (C) The Internet Society (2000). All Rights Reserved.

Abstract 🔮

Okay, so here's the tea ☕ Using Diffie-Hellman key agreement in a prime order subgroup of a large prime p can be vulnerable to these sneaky things called "small-subgroup" attacks 😭 BUT there are ways to stop them, so it's not all doom 💖 This doc walks through the situations where you need protection when you're implementing S/MIME version 3, plus the methods you can use to block these attacks 🛡️✨

1. Introduction 🧚

So this document is all about when you need protection from "small-subgroup" type attacks when you're using Diffie-Hellman key agreement [RFC2631] in S/MIME version 3 implementations [RFC2630, RFC2633] 🎀 The main focus is the ephemeral-static and static-static modes of Diffie-Hellman. We also look at some non-S/MIME ways of using CMS, but with way less focus than the S/MIME stuff 🫠

The situations where you actually need protection are the ones where an attacker could figure out a substantial chunk (like, more than a few bits) of a user's private key 😳

Now, protecting yourself isn't free 💸 It can cost you extra processing time when a public key gets certified or when a shared secret key gets derived, longer parameter generation time, and maybe even licensing for encumbered technologies. You have to weigh all of this when you decide whether to protect yourself from these attacks, or whether to engineer your app so protection just isn't needed 🤔

We're not going to cover "attacks" where the other party in the key agreement just forces the shared secret to be "weak" (meaning it comes from a small set of possible values) without trying to compromise the private key 🙄 Honestly, it isn't worth the effort to prevent these, because the other party already gets the shared secret and could just make the plaintext public anyway 🤷‍♀️

The methods in this memo may also be used to protect against similar attacks on elliptic curve based Diffie-Hellman 🦋

1.1 Notation 📝

So we're going to use the same notation as [RFC2631] 💅 Especially, the shared secret ZZ is generated like this:

ZZ = g ^ (xb * xa) mod p

Here's the part that's actually fun: the individual parties do the computations themselves, like this:

ZZ = (yb ^ xa)  mod p  = (ya ^ xb)  mod p

where ^ means 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; 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 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

Quick vibe check on the terms: a "static" public key is one that's certified and gets used for more than one key agreement 📜 An "ephemeral" public key is one that's not certified and only gets used one time ⚡

The order of an integer y modulo p is the smallest value of x greater than 1 such that y^x mod p = 1 🧮

1.2 Brief Description of Attack 💀

If you want the full breakdown of these attacks, check out [LAW] and [LIM] 📚

Here's the situation: if the other party in a Diffie-Hellman key agreement has a public key that's not in the form described above, but is of small order (where small means less than q), they may be able to learn something about the user's private key 😱 Specifically, if they can tell whether a given decryption worked, or if they can see ciphertext encrypted with the agreed key, or a MAC computed with the agreed key, info about the user's private key can leak out 🙈

Let's make it concrete. Say Party A has a valid public key ya, and Party B has a public key yb that's not in the form from Section 1.1. Instead, yb has order r, where r is much less than q, so yb^r=1 mod p. Now when Party A makes ZZ as yb^xa mod p, there are only r possible values for ZZ instead of q-3 possible values 😬 Party B doesn't know ZZ yet, but can just exhaustively search for it 🔍

If Party A encrypts plaintext with this value and makes that ciphertext available to Party B, Party B only has to search through r possibilities to figure out which key made the ciphertext. Once they find the right one, that tells them something about xa modulo r 🫣 It works the same way if Party A uses ZZ to decrypt something and Party B can tell whether the decryption went correctly. How many messages have to be sent or received for these attacks to work depends on the structure of the prime p. Still, it's not unreasonable to expect the entire private key could be figured out after as few as one hundred messages 💔

A similar attack works if Party B picks a public key of the form yb=g^xb*f, where f is an element of small order. In that case Party A computes ZZ=yb^xa=g^(xa*xb)*f^xa mod p. Party B can compute g^(xa*xb), so they can run through the small number of possible values of f^xa mod p and learn something about xa 🫠

There's also an attack if Party B has a public key yb of order r, where r factors into small integers but isn't necessarily a small integer itself. Here the attacker needs to know the value ZZ that Party A computed. From that value, Party B can solve for Party A's private key modulo r using the Pohlig-Hellman [PH] algorithm 🧠

Honestly though, this one isn't as practical as the cases above. Those cases recover info about the private key from the use of ZZ, not from ZZ itself, using exhaustive search 💅

2. Situations Where Protection Is Necessary 🛡️

This section goes through when the sender of a message should get protection against this type of attack, and when the receiver should get protection too. Each entity can decide on its own whether it needs protection from these attacks 🫶

This discussion assumes the recipient's key pair is static, which is always the case in [RFC2631] 📌

2.1 Message Sender 📤

This section covers the situations where the message sender should be protected.

If the sender's key is ephemeral (so ephemeral-static Diffie-Hellman is being used), then no protection is necessary 🙌 In this case, only the recipients of the message can get the plaintext and corresponding ciphertext, so only they could work out info about the private key using "small-subgroup" attacks. But the recipients can always decrypt the message anyway, and since the sender's key is ephemeral, even if the recipient learns the whole private key, no other messages are at risk ✨ Also, if two or more recipients picked the same domain parameters (p,q,g), the same ephemeral public key can be used for all of them. Since the key is ephemeral and only tied to a message the recipients can already decrypt, no interesting attacks are possible 💖

If the sender's key is static (so static-static Diffie-Hellman is being used), then protection is necessary 😤 Here's why: a recipient running a small-subgroup attack might be able to get the plaintext from another recipient (maybe one with a valid public key that they also control) and then learn info about the private key. Plus, the attacker doesn't even need to know the plaintext to test whether a key is correct, as long as the plaintext has enough redundancy (for example, ASCII). That info could then be used to attack other messages protected with the same static key 💀

2.2 Message Recipient 📥

This section covers the situations where the message recipient should be protected.

If absolutely no info about decrypting the ciphertext is available to anyone other than the recipient, then protection isn't necessary 🎉 That's because this attack needs info about whether the decryption succeeded to be sent to the attacker. So no protective measures are needed if the implementation makes sure no decryption info can leak out. However, protection may still be worth it if human users might pass this info to the sender through out-of-band means (for example, phone calls) 📞

If info about the decryption is available to any other party, then protection is necessary 🚨 Specifically, protection is needed if any protocol event lets another party conclude that decryption succeeded. Things like replies and returning signed receipts are examples of these events 📨

3. Methods Of Protection 🧰

This section describes five protective measures that senders and recipients can use to protect themselves from "small-subgroup" attacks 🦋

Heads up: some of the procedures in this section may be subject to patents or pending patents ⚠️

3.1 Public Key Validation ✅

This method is described in Section 2.1.5 of [RFC2631], and its description is repeated here. If this method is used, it should be used to validate the other party's public keys before computing the shared secret ZZ. The public key being 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 Validation 🏛️

The Certification Authority (CA) could run the Public Key Validation method from Section 3.1 before it signs and issues a certificate containing a Diffie-Hellman public key 🎀 That way, anyone using the public key can be sure a trusted third party already did the key validation 🫶 This method only works for static public keys. With Static-Static Diffie-Hellman, both the sender and the recipient are protected when the CA has done public key validation 💖 But with Ephemeral-Static Diffie-Hellman, only the sender can be protected this way. The sender generates an ephemeral public key, and the CA can't validate a key it never sees 😭

For a static public key, there has to be some method to assure the user that the CA actually did this verification 🔐 The CA can let certificate users know it performed validation by pointing to its Certificate Policy (CP) and Certification Practice Statement (CPS) [RFC2527], or through extensions in the certificate ✨

3.3. Choice of Prime p ✨

okay so the prime p could be picked so that p-1=2*q*k, where k is a big prime or a product of big primes (big means greater than or equal to q) 💖. This stops an attacker from finding an element (other than 1 and p-1) of small order modulo p, which thwarts the small-subgroup attack 🛡️. One way to get primes like this is to run the prime generation algorithm over and over until you get a good one 🔁. For example, you can test whether k is prime. If k is prime, the value of p is accepted. If not, the prime generation algorithm runs again until it produces a p with a prime k 🧚.

ngl though, with this shape there's still an element of order 2 (that's p-1), so one bit of the private key could still leak 😬. So this method may not be appropriate when losing even a single bit of the private key is a concern 💀.

Another option is to choose the prime p so that p = 2*q*k + 1, where k is small (only a few bits). In this case the leakage from a small subgroup attack is only a few bits 🦋. Again, this isn't great if losing even a few bits of the private key is a concern. Here q is large. Fun fact: in DSA, q is limited to 160 bits for performance reasons, but Diffie-Hellman doesn't have to follow that rule 👑.

And other methods (like public key validation) can be combined with this approach so you don't lose those few bits 🫶.

3.4. Compatible Cofactor Exponentiation 🎀

this method is specified in [P1363] and [KALISKI]. It changes how ZZ gets computed by bringing j (the cofactor) into the math 🔥. It's compatible with ordinary Diffie-Hellman when both parties' public keys are valid, which is iconic 💅. If a party's public key is invalid, the resulting ZZ will either be 1 or an element of order q. So the small subgroup elements either get detected or cancelled out 🙌. This method requires that gcd(j,q)=1.

Instead of computing ZZ=yb^xa mod p, Party A would compute ZZ=(yb^j)^c mod p, where c=j^(-1)*xa mod q. (Party B does the same thing, just flipped 🔄.)

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 when j is larger than q, which is usually the case with Diffie-Hellman, this method is less efficient than the method of Section 3.1 🐢.

3.5. Non-compatible Cofactor Exponentiation 🌈

this method is specified in [P1363]. It's similar to the method of Section 3.4 in that it also brings j (the cofactor) into the computation of ZZ 🦋. If a party's public key is invalid, the resulting ZZ will either be 1 or an element of order q, so the small subgroup elements either get detected or cancelled ✨. This method requires that gcd(j,q)=1.

Instead of computing ZZ=yb^xa mod p, Party A would compute ZZ=(yb^j)^xa mod p. (Party B does the same, flipped 🔄.) But heads up: with this method the resulting ZZ value is different from what [RFC2631] computes, so it is not interoperable with implementations that follow [RFC2631] 🙈.

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 when j is larger than q, which is usually the case with Diffie-Hellman, this method is less efficient than the method of Section 3.1 🐌.

4. Ephemeral-Ephemeral Key Agreement 🌸

this is the situation where both the sender and the recipient of a message are using ephemeral keys 🧚. It's not possible in S/MIME, but it might show up in other protocol environments, so we'll briefly talk about protection for this case too 💜.

Implementers should note that some of the procedures described in this section may be the subject of patents or pending patents.

Ephemeral-ephemeral key agreement gives an attacker more flexibility, since both parties' public keys can be changed and they can be coerced into computing the same key from a small space 😳. In the ephemeral-static case, though, only the sender's public key can be changed, and only the recipient can be coerced into computing a key from a small space by an outside attacker 🛡️.

So in some ephemeral-ephemeral key agreements, protection may be necessary for both entities 🫣. One possibility is that the attacker modifies both parties' public keys to make the 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 Sections 3.1, 3.4 or 3.5 📝.

Protection from these attacks is not necessary, however, if the other party's ephemeral public key has been authenticated. The authentication may be in the form of a signature, MAC, or any other integrity protection mechanism 🔐. An example of this is the Station-To-Station protocol [STS]. Since the owner authenticates the public key, a third party cannot modify it and therefore cannot mount an attack 🙅‍♀️. So the only person who could attack an entity's private key is the other authenticated entity in the key agreement. Even then, since both public keys are ephemeral, they only protect the current session, which the attacker would have access to anyway 🥲.

5. Security Considerations 😭

This entire document addresses security considerations in the implementation of Diffie-Hellman key agreement. Every single bit of it is about keeping your implementation safe, so please don't skip any of it, bestie 🚨💀

6. Intellectual Property Rights 📜

the IETF takes no position on whether any intellectual property or other rights that might be claimed to apply to the implementation or use of the technology in this document are valid or in scope, or on how far any license under those rights might or might not be available. It also doesn't say it has tried to find any such rights 🤷‍♀️. Info on the IETF's procedures for rights in standards-track and standards-related documents can be found in BCP-11 📚. Copies of claims of rights that were made available for publication, plus any assurances of licenses to be made available, or the result of an attempt to get a general license or permission to use 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 send that information to the IETF Executive Director 💌.

7. References 📚

[KALISKI] B.S. Kaliski, Jr., "Compatible cofactor multiplication for
          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, "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.

[PH]      S.C Pohlig and M.E. Hellman, "An improved algorithm for
          computing logarithms over GF(p) and its cryptographic
          significance", IEEE Transactions on Information Theory,
          vol. 24, 1972, pp. 106-110.

[RFC2527] Chokhani, S. and W. Ford, "Internet X.509 Public Key
          Infrastructure, Certificate Policy and Certification
          Practices Framework", RFC 2527, March 1999.

[RFC2630] Housley, R., "Cryptographic Message Syntax", RFC 2630, June
          1999.

[RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", RFC
          2631, June 1999.

[RFC2633] Ramsdell, B., "S/MIME Version 3 Message Specification", RFC
          2633, June 1999.

[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.

8. Author's Address 🎀

Robert Zuccherato
Entrust Technologies
750 Heron Road
Ottawa, Ontario
Canada K1V 1A7

EMail: robert.zuccherato@entrust.com

Copyright (C) The Internet Society (2000). All Rights Reserved.

okay, so this document and translations of it can be copied and handed out to others 📄. Derivative works that comment on or explain it, or help with implementing it, can be prepared, copied, published and distributed, in whole or in part, without restriction of any kind 🙌. The only condition is that the above copyright notice and this paragraph are included on all those copies and derivative works 🔖. 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. The exceptions are when it's needed for developing Internet standards (in which case the copyright procedures in the Internet Standards process must be followed) or when it's 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 in it 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 🥹.

Acknowledgement 🫶

funding for the RFC Editor function is currently provided by the Internet Society 💖✨

📦 where this page comes from