Page MenuHome GnuPG

On the (in)security of Elgamal in OpenPGP
Open, NormalPublic

Description

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

Event Timeline

werner created this object in space Restricted Space.
werner changed the visibility from "Public (No Login Required)" to "Subscribers".Mar 24 2021, 2:50 PM
werner changed the edit policy from "All Users" to "Subscribers".
werner shifted this object from the Restricted Space space to the S1 Public space.
werner added subscribers: aheinecke, jukivili, cbiedl.

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

werner lowered the priority of this task from High to Normal.Fri, Jun 4, 7:52 AM
werner changed the visibility from "Subscribers" to "Public (No Login Required)".