Key derived from source files; deduplicated file storage

Question

I'm wondering if the following system would be a secure way to store frequently duplicated files.

1. Hash the source file, deterministically derive a key from it.
   • The source file(s) are likely to be high entropy (PDFs, archives of multiple files etc)
2. Use that key to encrypt the source file.
3. Upload that encrypted file to any public network.
   • If the files are "encrypted", the storage provider does not have to be trusted.

To access/share the files, the address of the encrypted file and the source hash would need to be shared. The advantage I'm going for here is even if two people have the same source file (which is likely in my use case), it would only have to be stored once, saving storage costs.

My question from a storage provider's standpoint; Is this system secure? (assuming good hash and key derivation functions are used)

Edit: I'm not concerned about the key changing since the storage will primarily be content addressed (IPFS like) and is for long term storage rather than regular updates.

Answer 1

No, this is not generally secure. You cannot have deduplication with other users' files and privacy. But this depends on your exact threat model/security goals.

Using the hash of a file to encrypt it is called convergent encryption, and is a deterministic encryption method. Notably, there is no secret key that would add security to the ciphertext. Instead, any security comes from the entropy in the plaintext files alone.

It is clear that this scheme can't offer e.g. semantic security, and an attacker can efficiently learn something from the ciphertext. In particular it is trivial to verify if one of your files matches a publicly known file. Furthermore, PDF documents such as form letters might look high-entropy, but actually only differ in a few fields. This can be brute-forced. Also, a malicious service provider can pre-compute encryptions of documents they're interested in.

The solution of this is to stop using a deterministic encryption method. For example, adding a sufficient amount of random bits per block/file will help, but will also destroy deduplication opportunities. Using a real symmetric encryption with a secret key would be another solution, and would at lesst allow deduplication among holders of the same key.

You claim that your plaintext has high entropy. This is a strong assumption. Note that if your plaintext is high-entropy, then deduplication is unlikely and you might as well use a secure encryption method instead. In the context of this discussion, entropy must not be understood relative to all-zero bits but relative to the distribution of content known to other participants. If every user knows 1000 files of which one is the same 2GB large movie, that file only has around 10 bits of security, or actually zero since a fingerprint for the convergently encrypted file can be precomputed by everyone. Since your scheme doesn't feature secrets, it is impossible to distinguish between legitimate users and malicious attackers.

Answer 2

@brynk suggested looking at TahoeLAFS, and apart from the obvious confirmation caveat, it seems to prove that encryption as described in the question is possible and secure.

(if anyone knows otherwise please post an answer)

Edit: Reading more TahoeLAFS docs it seems like convergent encryption is relatively common, I didn't know it was called that.