This is to track the report by De Feo et al.
Revisions and Commits
- 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.
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.
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.