This is to track the report by De Feo et al.

# Description

# Revisions and Commits

# Related Objects

- Mentioned In
- T5466: Release Libgcrypt 1.8.8

T5305: Release Libgcrypt 1.9.3

E858: Weekly Standup

E857: Weekly Standup

E855: Weekly Standup - Mentioned Here
- rC74386120dad6: See ChangeLog: Fri Jul 14 19:38:23 CEST 2000 Werner Koch

rC78531373a342: (sign, do_encrypt, gen_k): Make sure that a small K is only used for encryption.

### Event Timeline

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.

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.