2

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)

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.

3

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.

-1

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.

  • 2
    That's incorrect. GPG uses a hybrid encryption scheme. The plaintext you would need is the randomly generated encryption key for the symmetric cipher. If you know this (e.g. the message has multiple recipients and you are one of them) it might work. (I am not sure if there is any nonce added) – Josef Dec 10 '18 at 11:46
  • 1
    @Josef+ it still wouldn't work. For RSA enveloping, PGP uses the original PKCS1 'block type 2', now retronymed RSAES-PKCS1-v1_5, which is randomized. See RFCs 2437/3447/8017. (Note signatures are different; RSASSA-PKCS1-v1_5 is not randomized.) – dave_thompson_085 Dec 11 '18 at 2:48
  • @dave_thompson_085 thanks, I thought so but weren't sure. – Josef Dec 11 '18 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.