4 ms·

Well encryption changes this. Assuming the key is in the hand of the user (which if it isn't kind of breaks the full point of encryption in this case) then each

Well encryption changes this. Assuming the key is in the hand of the user (which if it isn't kind of breaks the full point of encryption in this case) then each file will have a different digest and won't be detected as a duplicate. 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 ?

thefreeman 14y ago
I believe if you could verify two separately encrypted files were the same it would defeat the purpose of encryption completely. By definition a secure encryption system cannot allow this.
- BrokenPipe 14y ago
  True. You know what I was thinking ? homomorphic encryption 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.
  - karamazov 14y ago
    Homomorphic encryption allows you to encrypt the data and then operate on it. It doesn't (necessarily) imply that each plaintext has exactly one encrypted version. [1] 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.
- TylerE 14y ago
  That depends entirely on what you are trying to accomplish. I suspect this is all about plausible deniability.
- cmurphycode 14y ago
  Actually, there are encryption schemes that allow deduplication. They leak information (that the file you have already exists), but the encrypted bits themselves are secure. 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 :)
  - vy8vWJlco 14y ago
    Knowing the mapping between a hash of some plaintext and it's de-duplicated ciphertext means a person can just provide a list of hashes and ask Mega to delete their corresponding ciphertexts, even if they can't break the encryption. At least if they maintain their ignorance they can truthfully say they don't have the power to track down a ciphertext for any given plaintext hash. Hopefully they will, and just provide bulk cloud storage, with people holding onto their little key files. It's much easier to back up a 1KB key-file (or whatever form it comes in) than the encrypted 250GB blob it protects.
    - mindslight 14y ago
      Derive your encryption key from the contents of the file and a "convergence key". The "convergence key" can then be null for global convergence, a shared secret for a privately shared convergence, or a random nonce for no convergence. The derived encryption key is stored the same in every case. When encrypting a file, clients trade off using space versus a file getting deleted if the server is required to remove the ciphertext. The server never knows the difference.
- Dylan16807 14y ago
  It weakens it but it certainly doesn't defeat it. Guessing entire files is generally much harder than guessing encryption keys, and we don't exactly think of brute force as defeating the purpose of encryption.
marios 14y ago
You can do deduplication on chunks of the file. AFAIK, this is what cyphertite[1] does. Split each file in 256KB chunks, store their checksum and match those against a db do avoid resending / copying the same data over and over again. 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. [1] https://www.cyphertite.com/ https://www.cyphertite.com/
- BrokenPipe 14y ago
  thanks for the link, interesting.
- bgaluszka 14y ago
  Tarsnap [1] does that too. [1] http://www.tarsnap.com/ http://www.tarsnap.com/
pornel 14y ago
You can encrypt file with a crypto hash of its contents (e.g. `key=sha1(file)`). 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.
- JoshTriplett 14y ago
  A system like that prevents browsing contents if you don't know what you're looking for, but it doesn't prevent asking questions like "Do you have a copy of this file?", or enforcing a blacklist based on file contents.

thefreeman 14y ago

I believe if you could verify two separately encrypted files were the same it would defeat the purpose of encryption completely. By definition a secure encryption system cannot allow this.

BrokenPipe 14y ago
True. You know what I was thinking ? homomorphic encryption 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.
- karamazov 14y ago
  Homomorphic encryption allows you to encrypt the data and then operate on it. It doesn't (necessarily) imply that each plaintext has exactly one encrypted version. [1] 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.
TylerE 14y ago
That depends entirely on what you are trying to accomplish. I suspect this is all about plausible deniability.
cmurphycode 14y ago
Actually, there are encryption schemes that allow deduplication. They leak information (that the file you have already exists), but the encrypted bits themselves are secure. 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 :)
- vy8vWJlco 14y ago
  Knowing the mapping between a hash of some plaintext and it's de-duplicated ciphertext means a person can just provide a list of hashes and ask Mega to delete their corresponding ciphertexts, even if they can't break the encryption. At least if they maintain their ignorance they can truthfully say they don't have the power to track down a ciphertext for any given plaintext hash. Hopefully they will, and just provide bulk cloud storage, with people holding onto their little key files. It's much easier to back up a 1KB key-file (or whatever form it comes in) than the encrypted 250GB blob it protects.
  - mindslight 14y ago
    Derive your encryption key from the contents of the file and a "convergence key". The "convergence key" can then be null for global convergence, a shared secret for a privately shared convergence, or a random nonce for no convergence. The derived encryption key is stored the same in every case. When encrypting a file, clients trade off using space versus a file getting deleted if the server is required to remove the ciphertext. The server never knows the difference.
Dylan16807 14y ago
It weakens it but it certainly doesn't defeat it. Guessing entire files is generally much harder than guessing encryption keys, and we don't exactly think of brute force as defeating the purpose of encryption.

marios 14y ago

You can do deduplication on chunks of the file. AFAIK, this is what cyphertite[1] does. Split each file in 256KB chunks, store their checksum and match those against a db do avoid resending / copying the same data over and over again. 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. [1] https://www.cyphertite.com/ https://www.cyphertite.com/

BrokenPipe 14y ago
thanks for the link, interesting.
bgaluszka 14y ago
Tarsnap [1] does that too. [1] http://www.tarsnap.com/ http://www.tarsnap.com/

pornel 14y ago

You can encrypt file with a crypto hash of its contents (e.g. `key=sha1(file)`). 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.

JoshTriplett 14y ago
A system like that prevents browsing contents if you don't know what you're looking for, but it doesn't prevent asking questions like "Do you have a copy of this file?", or enforcing a blacklist based on file contents.