Degenerate ElGamal & duplicate key IDs

[Juraj Šarinay]

Hello

I have been playing around with ElGamal encryption within OpenPGP and
found out that GnuPG (2.1.17 tested) accepts degenerate ElGamal
ciphertexts with the first component equal to one, such as the attached
degenerate_universal.txt.gpg.

Every ElGamal private key (with appropriate modulus length) can be used
to "decrypt" such degenerate messages. Maybe the recipient should be
warned that the the content was actually sent in clear. I would even
consider rejecting all such messages as invalid.

I have generated a "corresponding" ElGamal public subkey with g=y=1 and
found out that it can be imported and used to produce degenerate ElGamal
ciphertexts. See the attached fake_subkey.gpg. Please consider treating
such degenerate subkeys as invalid.

I had a rather far-fetched scenario in mind, where a legitimate ElGamal
public subkey is swapped for a degenerate one with the same ID. This
could lead to an arguably "easier" MITM attack, because all the messages
encrypted under the fake subkey decrypt with the legitimate one. I have
actually generated two example ElGamal keys, one reasonable and the
other one degenerate, with identical IDs. For more context, see
http://www.sarinay.com/blog/taher-was-not-here/

In the course of my experiments, I also generated two primary DSA keys
with identical IDs and ran into another minor issue. When verifying a
signature, if there are multiple public keys with the appropriate key
ID, GnuPG appears to select the key that was imported first. If there
are two legitimate public keys with identical IDs, the validity of a
signature may depend on the internal ordering of the keys.

I have attached two example public keys, DSA_1_cert_sign.gpg and
DSA_2_certonly.gpg. The file signed.txt.gpg is signed with the first
key. If I import DSA_1 first and DSA_2 second, the signature verifies
fine. If I import the public keys the other way around, GnuPG reports
that the signature is bad. Only DSA_1 actually has the sign flag set, so
I expected that DSA_2 would be skipped and DSA_1 tried instead. Would it
not make sense to try all the public keys with the appropriate ID?

If we do that, what should be output if none matches? Is it "BAD
signature" or "Can't check signature: No public key"? The former is what
we currently output if one key was tried, the latter if none. Why the
difference? Every time GnuPG outputs "BAD signature", it could still be
valid under a key we do not have.

In this particular case, GnuPG appears to behave as if IDs were unique,
yet there is partial support for multiple keys with identical IDs. Why
bother with the support at all? It could be argued that the chance of a
random ID collision within a relatively small keyring is indeed
negligible. The few colliding pairs we have seen so far were AFAIK all
artificially generated examples. Have there been genuine collisions in
the wild? It might be a good idea to warn the user that a repeated ID is
probably an attack attempt and only actually allow the coexistence of
the keys if imported in expert mode.


Best Regards

Juraj


-------------- next part --------------
A non-text attachment was scrubbed...
Name: degenerate_universal.txt.gpg
Type: application/pgp-encrypted
Size: 373 bytes
Desc: not available
URL: </pipermail/attachments/20161231/034ddcfc/attachment.pgp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fake_subkey.gpg
Type: application/pgp-encrypted
Size: 273 bytes
Desc: not available
URL: </pipermail/attachments/20161231/034ddcfc/attachment-0001.pgp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DSA_1_cert_sign.gpg
Type: application/pgp-encrypted
Size: 988 bytes
Desc: not available
URL: </pipermail/attachments/20161231/034ddcfc/attachment-0002.pgp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DSA_2_certonly.gpg
Type: application/pgp-encrypted
Size: 988 bytes
Desc: not available
URL: </pipermail/attachments/20161231/034ddcfc/attachment-0003.pgp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signed.txt.gpg
Type: application/pgp-encrypted
Size: 144 bytes
Desc: not available
URL: </pipermail/attachments/20161231/034ddcfc/attachment-0004.pgp>