Proof that a encrypted file has the same content as an (existing) original

Question

Assume that Alice has a file F which she is going to send, in encrypted form, to Bob. Alice possesses F and the public encryption key K of Bob in form of an X509-certificate. She generates the file E using the encryption algorithm CNT_3DES, BitsInKey = 192 (RSA PKCS#1 encryption method). She sends to Bob the file E through a certified mail system which will get a digital signature and a time stamp from an external authentication authority. Therefore it is possible to include in the body of the mail any information, including hash codes, that will be accepted as well known before the creating time of the mail.

After some time Alice has to proof to Mike that the file E send to Bob has the same content of the file F. But Mike does not have the private key of Bob for decrypting the file. And encrypting the file F now produces a different file than E since encryption adds a random padding on encryption stage. How can this proof be given from Alice to Mike? As explained, it is possible to include in the body of the mail any useful information that will be necessary for this proof.

I hope that I explained my problem in a sufficiently clear way. And sorry for my poor English.

Answer 1

Retaining the 3DES encryption key would probably do it. Now simply use the same IV as before and encrypt the file; the IV is only random when it is initially chosen. Alice could also encrypt the key and store it together with the message.

You'd have to prove that you used the same key. That's no problem for larger messages in CBC mode where the possible plaintext is known, but for good measure, I'd include a MAC over the IV and ciphertext in the mail header.

---

Alternatively, and possibly better than using a MAC, is to transmit the random padding with the message and store the secret key. That way you can regenerate the wrapped key by pairing the padded key with a raw RSA operation, proving that it was that specific key you used.

It might be better in the sense that creating a covert channel is harder if all the information is shown to Mike. It has the drawback that it requires access to raw RSA operation, which may not be directly available to you.

Answer 2

You say that you're using 3DES, which is a symmetric secret-key encryption method, but also that you're encrypting the file using Bob's public key (for, presumably, some asymmetric cryptosystem like RSA). This suggests that you are (or the software you're using is) actually using hybrid encryption, where you first generate a random symmetric 3DES key, encrypt the file E with that key, and then encrypt the key with Bob's public key.

Given this, a simple way for Alice to prove that the encrypted file E sent to Bob was actually created using the plaintext file F is for her to save the random 3DES key K used to encrypt the file, and hand it over to Mike. Mike can then decrypt the file E sent to Bob using the key K, and compare it with the known plaintext F.

A subtlety here is that this doesn't prove that K was the encrypted key that Alice sent to Bob. However, as long as the messages are reasonably long, coming up with two 3DES keys that would decrypt the same ciphertext to two different meaningful plaintexts is pretty difficult (especially if one of the plaintexts is fixed in advance). So, in practice, if Alice did send some key other than K to Bob, all Bob would get when decrypting E would be random gibberish (and if the ciphertext E included a MAC for integrity protection, it would almost surely fail to validate).

If Alice does wish to prove that she didn't send random gibberish to Bob, things get trickier. In general, any secure public-key encryption scheme must be non-deterministic, so Mike cannot simply re-encrypt K with Bob's public key and compare it with the encrypted key sent by Alice.

However, if Alice also stores all the random inputs used in the process of encrypting K, then she can also provide those to Mike, and thus allow him to confirm that the encrypted key sent by Alice to Bob is indeed a valid encryption of the 3DES key K (and, therefore, that K is what Bob would have received when he decrypted it using his private key).