With GPG, can 3rd party verify that message has been encrypted by specific public key?

Question

Bob is sending message X to Alice. He encrypts X with Alice's public key using gpg and sends her encrypted message (ciphertext).

Later Alice claims that Bob made a mistake and the ciphertext was not created with her public key.

Can Bob prove to 3rd party that the encrypted message is in fact encrypted with Alice's public key?

The resulting encrypted message is different every time even when message X is the same (Will encrypting the same file with GnuPG and the same key produce the same ciphertext?) so the 3rd party can't just encrypt it again and comapre results. Is there any other way?

If possible, please give commands how to execute this in existing software.

EDIT: Alice is not cooperating. X can be revealed to 3rd party (but better if possible without)

Answer 1

Maybe sort of.

The pk-encrypted-sk packet in PGP (see rfc4880 5.1) normally contains the 64-bit 'long' keyid of the recipient's key; this is intended to help the recipient use the correct decryption key if they have more than one, and to help the recipient identify which tag-1 packet (if any) is for them in a message encrypted to multiple recipients. It may be suppressed by substituting zero if desired. This can be displayed by any number of PGP analysis/debugging tools, including gpg --list-packets.

If Bob is accused only of a mistake, not of cheating on or lying about sending the message, and did not use GnuPG's --hidden-recipient or similar, this is probably sufficient. If Bob is accused of (even contributory) malfeasance it might help if when the message was sent (or at least prior to any dispute) he signed it, had it timestamped by a TSA, or both, but you'd have to be more specific about the case or range of possible cases to be handled. (ObSecStack: what's your threat model?)

Assuming the key blob is still available or can be obtained e.g. from a keyserver, this almost 'proves' what key Bob used. It is presently difficult, but not impossible, to generate a false key (second-preimage) for a long keyid. (It is easy for 32-bit 'short' keyids often used for manual selection or 'verification', see https://evil32.com .) It is practical to generate collisions for 64-bit, but that would require Alice to knowingly collude in a false claim; see above about threat model.

However, that does not constitute proof the key used was (or still is) Alice's -- it is quite possible that Bob did in fact make a mistake. What reason or evidence did he use in choosing that key to encrypt to?

• Just having a key with Alice's name in it is NOT proof it is her key -- those are trivial to fake.

• Having a key with Alice's name in it that was signed by trusted other parties is better evidence, but not absolute -- with enough effort someone could have posed as Alice to get a fake key signed.

• Even if Alice actually gave Bob this key, can he prove (1) she did so and (2) he at all times thereafter maintained it on device(s) or storage that no one else could have tampered with?

Note: similar to Is it possible to prove which public key was used to encrypt a message? which covers a broader range than just PGP. Also
Can I check who can decrypt my GPG message after I encrypt it?
What information is leaked from an OpenPGP encrypted file?
Can all the (other) recepients of a PGP encrypted message be identified?
which I didn't see earlier.

Answer 2

No.

If you don't know the private key, There is no way to check if a PGP-encrypted message is encrypted with a specific public key even if the plain text message is known.

Answer 3

Disclaimer: This answer is wrong, as outlined by the comments below.

I have to partially contradict the answer by Moonsik Park.

If Bob still has the plaintext of X, and the 3rd party (Theo) knows Alice's public key, Bob can hand over X to Theo, and Theo can encrypt X with Alice's public key and compare the results of that with the ciphertext Bob sent to Alice.

However, you state that Alice is not cooperating, so Alice can always claim that the message she received is not the one Bob claims to have sent. Unless there is external proof that the ciphertext Bob claims to have sent is identical to what Alice has received, there's really no way to validate that Alice has received any specific message, or indeed any message at all.