Our tentative plan is:

• Short-tem: Increase Windows size fix for 1.9.3 to mitigate the described attack.
• Middle-term: Implement blinding for Elgamal and DSA in 1.9.4
• Long-term: Move to a constant-time fixed window size for 1.10.0

For DSA, I had assumed similar attack could be effective.

But the particular attack scenario is: an environment with automatic decryption enabled (which can be remotely controlled to examine the side channel signal many times).

This would be difficult to set up for DSA. Remotely controlled environment, asking signing same message, using deterministic DSA... would be not that practical.

So, in my opinion, applying the patch for ElGamal exponent blinding is enough (for now).

This would be difficult to set up for DSA. Remotely controlled
environment, asking signing same message, using deterministic
DSA... would be not that practical.

Good point.

Do we have CVE number assigned?

The paper describes another problem: interoperability (or interpretation) of "ElGamal encryption", and its impact.

• In libgcrypt and GnuPG, it may be considered that it's defined as:
  • Generalized ElGamal encryption (8.4.2 of Handbook of Applied Cryptography), as (1) The multiplicative group Zp^* of integers modulo a prime p
  • with the specific ways of:
    • selecting p by Lim and Lee method
    • selecting a cyclic group G (within Zp^*)

• Other implementations may consider it as: Basic ElGamal encryption (8.4.1 of Handbook of Applied Cryptography)

The former, selection of random integer k for encryption is done by 1 <= k <= n, where n is the order of the group G.

The latter, selection of random integer k for encryption is done by 1 <= k <= p - 2.

For the Lim-and-Lee prime, smaller k is ok, but for key which is based on Basic ElGamal encryption, it's not OK.

Let me rephrase from a viewpoint of mine (an implementer).

(I manage to pull out the books of HAC and Applied Cryptography, from dusty shelf.)

For me, it looks like:

• It would be considered as: Basic ElGamal encryption, with an optimization

• The "optimization" was introduced by the commit in 2000: rC74386120dad6: See ChangeLog: Fri Jul 14 19:38:23 CEST 2000 Werner Koch, which was subsequently fixed by the commit in 2003: rC78531373a342: (sign, do_encrypt, gen_k): Make sure that a small K is only used for encryption.

The optimization works well. But it's not good when considering other possible implementations. Because it assumes the specific property of key.
It should have been standardized when introducing this optimization.

To standardize, it becomes clear to define it as Generalized ElGamal encryption with a cyclic group.

CVE-2021-33560

I looks like the "cipher: Hardening ElGamal by introducing exponent blinding too." commit [1] was never applied to 1.8.x. Is that intentional? If so, is there a specific reasoning that it's not needed in 1.8.x? Thanks!

[1] - https://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commit;h=e8b7f10be275bcedb5fc05ed4837a89bfd605c61

The paper addresses two issues.
(1) https://ibm.github.io/system-security-research-updates/2021/07/20/insecurity-elgamal-pt1
(2) https://ibm.github.io/system-security-research-updates/2021/09/06/insecurity-elgamal-pt2

Unfortunately, CVE-2021-33560 was misused. It was updated by someone to refer (2).

When I requested an CVE to MITRE, my intention is for (1).

Anyhow, (since it was misused), it seems that the authors got new one for that: CVE-2021-40528

For (2), by GnuPG Team, it is not handled as a security bug (while the authors claim that both as vulnerabilities). It is handled as an improvement of the implementation.

If distributions consider that it might be an issue (of security attack), they can apply the patch of the commit to 1.8 series.

The problem of (2), is local side-channel attacks to ElGamal encryption.
We evaluated the impact, mainly for the use case of GnuPG; ElGamal keys are not that popular any more. When such an attack is possible, easier attacks would be possible.

Thanks for the clarification!