validate file encryption without decryption key

Question

I may be asking for something impossible here.

I want to know if it is possible to set up a 3rd party storage system where the service provider cannot decrypt the clients files, but can de-dupe the files if two clients upload the same file.

I think I'm right in assuming that this would require that the two clients uploading the file would have to encrypt with the same key, but this is not a problem in itself as the service could (for example) mandate that files be encrypted with a key that is a function of a hash of the file: both clients share that knowledge (without being aware of each other) but the service provider doesn't so still would not be able to encrypt.

That's all fine if the clients follow the rules and use the mandated encryption method and key corresponding to the file being uploaded. What I'm wondering is whether it is theoretically possible to choose an encryption technique whereby the service provider can verify that the client has obeyed the rules, without compromising the requirement that the service provider must not be able to decrypt the files.

Answer 1

To a large extent, the question makes no real sense, because the data is opaque for the server. Since the server will not, in any case, be able to read the decrypted files, whether two files are identical or not should not have any impact. In fact the complete scenario must be made clearer.

You have a server. The server stores "encrypted data" on behalf of some users who will send to each other the decryption keys; all decryption and encryption occurs elsewhere, and your server cannot do it. We have to assume that there is an out-of-band mechanism by which users exchange decryption keys.

What you want, as the server's owner, is to recognize when several instances of the same file are uploaded to your server, so that you may pay for the storage space only once (I just read somewhere that "The Hobbit" was the most copied movie of 2013, so you might assume that your envisioned platform would contain several hundreds of copies of that multi-gigabyte movie file). Normal, secure encryption should prevent outsiders from being able to make any assertion about the data contents, including being able to recognize whether two encrypted files have the same contents. In that sense, the de-duplication you are looking for is a weakening of the security model. We can predict that some users would not like it; for instance, if de-duplication works, then you (as the server) can detect when a user is uploading "The Hobbit".

(When de-duplication works, then it becomes possible to do some exhaustive search on file contents; this is easy to do for files which are duplicated a lot, because a file which is known to many users cannot be really that secret; and in the context of "intellectual property enforcement", heavily-duped files are of prime interest.)

If we speak in generic terms, then you cannot enforce de-duplication, because any two users who want to evade it can simply double-encrypt their data. User 1 first encrypts the file with an extra secret key, that he will share with User 2; that key is chosen randomly, so the encrypted file won't match any other instance of the same data; that encrypted file is then encrypted again with your service. Users can do such double encryption because the data is just, in fine, a file on their disk, and we assumed above that users can talk to each other independently of your server. As long as users can talk to each other, then they can exchange secret keys that you don't know of.

In some very specific contexts, it is possible to prove that some encrypted data fulfills some algebraic property without revealing it. See non-interactive Zero-Knowledge proofs. This is used in some electronic voting protocols, so that the prover may demonstrate that what he encrypted is really either a 0 or a 1, not any other integer, but without divulging the actual vote value. This won't apply to a generic file storage system, because "normal files" don't follow a discernable mathematical structure.

Therefore, if you want to enforce de-duplication against uncooperative users, then you must make it so that users cannot talk to each other. That's easier said that done... and it looks hardly feasible, since for the site to be really useful, the sender and recipient must be able to agree on at least a reference key, used to locate the file on the server.

Answer 2

If you are using public-key cryptography with digital signing for your encryption mechanism you could simply decrypt the signature using the user's public key to give you the hash to the plain text data. That hash could then be referenced against the other hashes you have stored to determine if this particular file has already been uploaded. You would, of course, have to have a copy of the user's public key.

I suppose it would be possible for the user to fake the digital signature (encrypt an invalid hash of the file and attach to the encypted file as the signature) and upload that. You wouldn't know because you can't unencrypt the file and check the hash of the plaintext against the signature. The only reason I can think for doing this though would be to trick your duplicate detection so there wouldn't be much motive for the user to do so.

If you have control over the encryption mechanism you could simply require that the encrypted file is uploaded along with a hash of it's plaintext. This also could subverted by proxying whatever upload system is used to send a faked hash.

Answer 3

If I get this correctly, you want users to upload files which the server or a middle man can not decrypt. Additionally, encrypted files with redundant plain text data must be removed.

Keeping aside the security of the actual cryptographic methods used, I believe you could do the following:

1. User selects a file to be uploaded. Client sided parsing is utilized to calculate the file's hash.
2. This hash is sent over to the server to identify if the file is a duplicate.
3. If not, either a symmetric or asymmetric approach is used to encrypt the file on the client side and then upload it to the server. A mechanism for secure host authentication and session establishment should be implemented to prevent a MiTM side channel attack vector.
4. For retrieval, the encrypted file is received from the server and decrypted on the client side.

One concern is that if you're dealing with files that require version management. In this case, the file's hash will change with its content. Having a file identifier as plain text in the encrypted file's header would allow version management without exposing any of the file contents at the server end.