Is there a way to store files encrypted with different data and detect they are the same file ? If there was, wouldn't this allow LEO to verify this and issue DCMA notices ?
I haven't tested cyphertite, but I've been meaning too. I mean, Ryan McBride is involved in the project as well as other OpenBSD devs. I'm hoping it has the same level of polish as OpenBSD.
I understand is possible to do operations on encrypted data (which results in an encrypted result) all without having the key to the data (or the result), and maybe there's a way to do this to allow the duplication.
If there is it could (but shouldn't ?) be used.
The issue here, to me at least, is that someone malicious that has exactly the same data could encrypt it and then verify the above.
It's also highly experimental at this point, from what I remember.
[1] As a trivial example, let's say you give me a very large number, and your encryption scheme is to add some number, n, of zero bits at the end. Only you know how many bits you're adding - n is your private key. Regardless of what you pick for n, I can multiply your number by 2 (i.e. bit-shift it) and give the result back to you, which you would then be able to decrypt to the result of the calculation.
This works for any value of n, so I can't tell if two original numbers are the same by inspecting the ciphertexts.
The keyword is "convergent" encryption. We used something like this at Iron Mountain Digital many years ago (they still do, AFAIK), and it is used in BitCasa today.
You should read the papers, but essentially the concept can be boiled down to encrypting the plaintext with a hash of the plaintext.
Since there is no way to derive the hash of a plaintext from an encrypted block, there is no way to hack the key other than regular old brute force. But if the same data is uploaded twice, the same hash is computed, and thus the same encryption is used, and thus the encrypted cipher text is identical.
The encryption keys can be stored separately from the cipher text. In particular, the user who uploaded the data would store the hashes (this would already happen in most backup applications anyway). Then, for retrieval, they give the hash and the block location to the server, who is now able to decrypt it. By stealing the server, you gain zero access to plaintext data.
Very cool stuff :)
But your 'random salt' idea suffers from the attacker just generating all possible encryptions of the plaintext due to the small number possibilities. The "convergence key" is solely a security-parameter-length key that you can pass around to your friends so that your files will dedupe with theirs while not being susceptible to confirmation attacks by others.
That's a nice catch-22, as you need contents of the file to obtain the key to decrypt it.
Deduplication could be even more effective if the file was first split into variable-size content-dependent blocks using rolling hash (like rsync does) and then each block was encrypted this way separately (this way same MP3s with different ID Tags would still be mostly deduplicated).
Of course the more you make deduplication easier the more you indirectly disclose about contents of the file, so this is a security/privacy trade-off.