Message recovery vulnerability in ElGamal

[defeo]

https://eprint.iacr.org/2021/923 illustrates a message recovery attack in a scenario where Crypto++ encrypts a message to ElGamal public keys generated according to different conventions than those used in Crypto++. This is an issue in interoperable scenarios, such as OpenPGP.

Concretely, ElGamal ciphertexts generated by Crypto++ have the form (g^y, h^y·M) where the bitlength of y is much shorter than that of the ElGamal modulus (see https://github.com/weidai11/cryptopp/blob/434e3189/nbtheory.cpp#L1045-L1050). The attack recovers y in cases where g generates a group of composite order N, where N = q·f₁·f₂··· with f_i small.

The fix is to change the way y is sampled during encryption: sampling y with as many bits as the modulus p prevents all attacks, and is the only safe option.

[carnil]

This issue has been assigned CVE-2021-40530

[noloader]

@mouse07410,

It looks like the suggested change is from:

// gfpcrypt.cpp
Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
{
	return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
}

to:

// gfpcrypt.cpp
Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
{
	return GetSubgroupOrder()-1;
}

What I am less clear about... Should this only apply to ElGamal, or should it apply to all ElGamal-like schemes?

I am inclined to provide a new class like:

Integer DL_GroupParameters_ElGamal::GetMaxExponent() const
{
	return GetSubgroupOrder()-1;
}

And then have ElGamal encryption keys use DL_GroupParameters_ElGamal.

Do you have any thoughts?

[mouse07410]

Offhand, I don't know. And would like to catch some of my colleagues to discuss this.

Offhand, your proposed new class looks reasonable.

[noloader]

Thanks @mouse07410.

From the paper On the (in)security of ElGamal in OpenPGP that raised this issue, four configurations are analyzed. Configuration A and Configuration B are insecure due to the attack.

Configuration C uses safe primes, and Configuration D uses Lim-Lee primes. The paper considers these configurations secure. I believe Crypto++ is using a modified Configuration C.

I don't like Lim-Lee primes because keys cannot be validated without additional information, so that strikes Configuration D. In fact, GnuPG stopped publishing the information years ago so it is not possible to validate a key created by GnuPG. Nowadays it is a "trust us" situation, with "us" being GnuPG.

Lets go with unmodified Configuration C and the safe primes. Configuration C is less efficient, but it allows a user to load and validate a key before using it. Configuration C means we will no longer use WorkFactor as an estimate for the size of y; we will now use subgroup order.

[noloader]

This issue should be cleared at Commit bee8e8ca6658.

I verified the new code path was engaged, and GetMaxExponent uses GetSubgroupOrder()-1:

ElGamal validation suite running...

passed    cryptosystem key validation

Breakpoint 1, CryptoPP::DL_GroupParameters_ElGamal::GetMaxExponent (
    this=0x7fffffffca60) at gfpcrypt.h:299
299			return GetSubgroupOrder()-1;

I also verified the work factor code was not engaged for ElGamal encryption.

I set a breakpoint on nbtheory.cpp#L1045-L1050 and ran cryptest.exe v. The work factor code is still being called for DH, MQV, HMQV, FHMQV, DLIES, NR, LUC-DH, LUC-IES, EC/ECP, EC/EC2N. There may be more uses.