Subject: [openpgp] IND-CPA security of OpenPGP's ElGamal implementation

From: Roger Ellenberger <[email-masked]>
Date: Sat, 8 Dec 2018 16:16:59 +0100

Hi,

We are currently working on a Firefox extension which allows us to
encrypt and decrypt OpenPGP messages using partially-trusted remote
keystores. We perform the asymmetric decryption operations on these
remote keystores using a threshold ElGamal scheme. We develop this
extension as our thesis project at Bern University for Applied Sciences.

ElGamal is our preferred asymmetric algorithm since we make use of
threshold cryptography and the threshold scheme of ElGamal is much
simpler compared to threshold RSA.

Working on the decryption of OpenPGP messages we saw in the section 5.1
of RFC4880 that the symmetric key $s$ with algorithm identifier and
checksum is encoded and padded using PKCS#1 v1.5 EME encoding. The
result of the EME encoding $eme_encode(s) = m$ then is encrypted using
ElGamal.

A short recap of ElGamal: We use the Groups Z*_p and G_q for ElGamal,
where p is a safe prime, $q = (p-1)/2$ and $G_q$ is a subgroup of
$Z*_p$. Encryption is defined as follows:

$
enc(y, r, m):   G_q x Z_q x G_q -> G_q x G_q
             :=  (c_1, c_2) = (g**k mod p, m * y**k mod p)
$

According literature one need to map $m$ into $G_q$ to guarantee that
ElGamal ist IND-CPA secure. According the RFC this check is not
performed, but an encoding/padding is applied to the plaintext.

Long story short: We would like to know what the considerations have
been to use ElGamal combined with a PKCS-EME encoding, since without the
encoding/padding it actually lacks of CPA security. Unfortunately we did
not find any authoritative reference which give a statement about
ElGamal security when $m$ is not in G_q but padded.

Thank you very much in advance for your help.

Best regards,
Tobias and Roger

---

From: Watson Ladd <[email-masked]>
Date: Sat, 8 Dec 2018 10:42:56 -0800

On Sat, Dec 8, 2018 at 7:21 AM Roger Ellenberger
<[email-masked]> wrote:
><snip>

I suspect the only leak is one bit, namely whether or not m is a
quadratic residue mod p or not. The impact on the security is minimal.
But why not use threshold IECS as https://tools.ietf.org/html/rfc6637
does and avoid this quirk?

> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Jon Callas <[email-masked]>
Date: Sat, 8 Dec 2018 16:44:25 -0800

> On Dec 8, 2018, at 7:16 AM, Roger Ellenberger <[email-masked]> wrote:
> 
> […]
> 

What a wonderful idea. I really like it.

The short answer to your question is that there aren’t any references. I concur with Watson that any issue is minimal, especially if you’re using Elgamal keys that are 3K to 4K.

A longer answer is that OpenPGP is pretty much the first substantial protocol to use Elgamal keys. Back in the late ‘90s, when patents were an issue, the then "PGP 3” system which became “PGP 5” and then that became standardized as OpenPGP, wanted an alternative to RSA. The RSA patent expired in the year 2000, but the discrete log patents expired in ’97. Thus, there was a real reason for wanting a discrete  log option. They picked Elgamal because you can use it more or less as if it were RSA. As time went on, Elgamal signatures fell by the wayside over DSA, leaving Elgamal for encryption.

Derek Atkins might remember more, because a lot of those original decisions were made by some combination of him, Colin Plumb, and Hal Finney.

	Jon

---

From: Heiko Stamer <[email-masked]>
Date: Sun, 9 Dec 2018 10:02:19 +0100

> performed, but an encoding/padding is applied to the plaintext.

I stumble upon the same problem [1] when creating DKGPG some months ago. 
In my oppinion it cannot be solved without revising ElGamal in the RFC. 
Maybe the work of Sakurai and Shizuya [2] can help to understand some 
implications of the RFC authors choice at that time.

[1] slide #17 of https://www.nongnu.org/libtmcg/dg81_slides.pdf
[2] https://link.springer.com/content/pdf/10.1007/3-540-49264-X_28.pdf

Best regards,
Heiko.

---

From: Roger Ellenberger <[email-masked]>
Date: Sun, 9 Dec 2018 11:14:10 +0100

> What a wonderful idea. I really like it.
Very appreciated. We're thrilled you like it.

> A longer answer is that OpenPGP is pretty much the first substantial protocol to use Elgamal keys. Back in the late ‘90s, when patents were an issue, the then "PGP 3” system which became “PGP 5” an…
We already supposed that there might be historical reasons for that. So
that's exactly the sort of reply we hoped to get. That's awesome. Thanks
a lot Jon.

> Derek Atkins might remember more, because a lot of those original decisions were made by some combination of him, Colin Plumb, and Hal Finney.
We are pleased to get as much information as possible if anymore
remembers more. However Jon's answer is already a big leap forward.

Cheers
Tobias and Roger

---

From: Derek Atkins <[email-masked]>
Date: Mon, 10 Dec 2018 11:21:18 -0500

Jon Callas <joncallas=[email-masked]> writes:

> A longer answer is that OpenPGP is pretty much the first substantial
> protocol to use Elgamal keys. Back in the late ‘90s, when patents were
> an issue, the then "PGP 3” system which became “PGP 5” and then that
> became standardized as OpenPGP, wanted an alternative to RSA. The RSA
> patent expired in the year 2000, but the discrete log patents expired
> in ’97. Thus, there was a real reason for wanting a discrete log
> option. They picked Elgamal because you can use it more or less as if
> it were RSA. As time went on, Elgamal signatures fell by the wayside
> over DSA, leaving Elgamal for encryption.
>
> Derek Atkins might remember more, because a lot of those original
> decisions were made by some combination of him, Colin Plumb, and Hal
> Finney.

As I recall, we added DSA and ElGamal to attempt to work around the RSA
patents.  For a while, IIRC, PGP3/5 did not even support RSA at all,
making it harder to interact with PGP2 -- at least for a short while.
This was all back in 1996-1997 when this work was done.

> 	Jon

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant