Hacker News Reader

Comment by esutton | Hacker News Reader

I'm confused, they mentioned at techcrunch disrupt that they are able to offer infinite storage because they are deduplicating data. Fine. But they also said that they will be doing client side encryption. Contradiction - encrypted data cannot be deduplicated.

View on HN

What if in the header of the file they put an md5sum that is not encrypted?

I don't think that would represent a data leak, and you could then dedupe based on md5sums...

But only one of the two users could decrypt the block - useless.

downvoters: If I encrypt a plaintext, and you encrypt the same plaintext, we'll have different ciphertexts. If we detect that we encrypted the same plaintext, how do we deduplicate? (Also, I would consider that a leak.)

I encourage everyone in this thread to read up on convergent encryption.

http://research.microsoft.com/apps/pubs/default.aspx?id=7421... http://www.ssrc.ucsc.edu/Papers/storer-storagess08.pdf

I encourage anyone who is thinking of implementing convergent encryption to read "Convergent Encryption Reconsidered" from the tahoe guys: http://www.mail-archive.com/cryptography@metzdowd.com/msg089...

(tldr; there are serious security/privacy vulnerabilities with convergent encryption)

Client-side encryption does not exclude server-side decryption, ie: only encrypt it on the wire, not the storage device.

Like Dropbox.

from their faq: Your Data Is Secure Bitcasa encrypts your data before it is sent to the cloud. It is actually impossible for Bitcasa to access any of your data for any reason.

"Client-side encryption" generally means that only the client can decrypt the data. Unfortunately, if you forget your key, you can't reset your password to recover your data.

> Contradiction - encrypted data cannot be deduplicated.

That's correct; there might be a middle ground that's yet to be explored and proved secure.

Check previous discussion here: http://news.ycombinator.com/item?id=2570538

wouldn't deduplicating encrypted data still work but your hit rate would just be a lot lower. you would have to work on a block instead of a file level but in theory you could dedupe file blocks that had been encrypted, because either way in the end its just bits.

Or is the assumption that with encrypted data you are so incredibly unlikely to see hits that its not worth doing...

if a file is encrypted correctly, you should not be able to compress it or match it to the same file encrypted a second time.

I understand that, but couldn't two different files encrypted with two different keys theoretically share some identical blocks. Obviously this is way less likely than two unencrypted files sharing blocks but still it could happen.

The hell it can't.

Block-level de-duplication can easily work for encrypted data.

Deleted comment

While a different password / key would make the same data decrypt to different data, you don't necessarily have to do de-dupe on blocks of the encryption-cipher-size, so these values can easily overlap.

Blocks of data can be treated completely independently of the encryption. The block size is not necessarily the same as the encryption cipher block size (if you're using a block cipher).

Say, a chunk of 4000 different files all have a few disk blocks that contain the same pattern of data. You can store those few blocks once, instead of 4000 times. With encryption, this is still possible, but it's going to be slower, as the data segments will be more randomly distributed. It is still, however, possible and will result in savings.

the problem with this theory is that deduplication works so well with file backup as the largest files we have are most often music and video, something that is highly replicated amongst file sharing users. i.e millions of users have the same Beatles album. Yet, when each persons album is encrypted it will be entirely different than every other persons album. If they were in any way similar it was not correctly encrypted. Thus the hit rate will be almost negligible. So than you say OK, but maybe the block level code of the encryption of my Beatles album is similar to the block level code of the encryption of my Eminem album, and than we can save storage there. The problem with this is that encryption algorithms aim to make their input files output as close to a random distribution as possible. Meaning not only are those two copies of the beetles albums going to be as different from each other, but they will be different from any other file. To sum it up, a well encrypted file should be uniformly random -> meaning it is uncompressible - > two different uniformly random files are still random relative to each other and when put together still cannot be compressed.

At the 'infinite' scale of storage that they're discussing, you should still see a savings. It's not going to be 30% or 80%, but it will be savings. De-duplication CAN still take place.

actually it should be close to nothing, encrypted data cannot be compressed as it is supposed to be uniformly random. If it can be compressed, the encryption algorithm is weak.

also on stage at tech crunch disrupt the founders were talking about the majority of the data be deduplicated

The easy solution is to segment easily deduplicated data from 'private' data. Perhaps sufficiently deduplicated data doesn't count against your quota. (as amazon does with music)

The problem with this is that the data which you want to de-dupe are the big files that everyone has a copy of; files like mp3s, videos, etc. Unfortunately these are the same files that users are most likely to not want the RIAA/MPAA to know about and keep private.

The short version of all of this is that Bitcasa can't actually pull off what they are claiming and still maintain any user security/privacy.

Reply on news.ycombinator.com