Oh of course, but I can see it being used fairly widely since it does have (esp on larger networks) the obvious advantage of being able to save a LOT on hardware if a lot of stored data is duplicates.
I don't think a lot of backup providers do this but file-mesh services and file sharing services surely do.
My point is specifically that many of them are doing so in this ridiculous way. You can try for yourself: upload a bunch of pirated mp3s and see if the transfer is suspiciously fast.
But saying that other companies are doing things wrong, doesn't mean you have to throw the baby out with the bathwater - you can still do de-duping, you just won't do it in a way that exposes vulnerabilities/etc.
The article makes it sound like it cannot be done.
To my knowledge, it cannot be done in a way that addresses the privacy concern: that a court could require the storage operators to answer such questions about their customers as described in the article.
If there's a way around that, I am your eager student.
By the way, some people have suggested using reference counts as a solution. You then know, for example two or more users share duplicate data, but not which two users. My feeling is that, at some time, you did know which users those were (when the counts were incremented.) I like to stay within the realm of "we are not capable of knowing" instead of simply, "as it happens, we don't know anymore."
As long as they have the files in plaintext, I prefer the 'ridiculous' method for the speed benefits. If you upload data unencrypted and expect perfect privacy on it you're fooling yourself.
While that may be why SpiderOak does what they do, I disagree with most of their arguments?
First, you can do variable block-based de-duplication, which is how major storage vendors do it - not per-file, which doesn't really buy you much.
Leveraging this in the SAN firmware also prevents their ridiculous file transfer 'vulnerability' (which only exists due the way they wrote their software) - all of your files copy over the network to the storage system. Once they're on the storage system, at some later time and asynchronously, the storage system runs a dedupe on the blocks, and winnows down its storage. Think of it like transparently compressing on the storage side, only, hopefully, less intense on I/O.
Finally, they could simply encrypt everything and then they can't answer subpoenas about who has knowledge of what - it was all encrypted immediately after uploading, and no log is kept. If the data doesn't exist, you can't be forced to give it up...
One of the big challenges of scaling a backup service is maximizing the upload rate from customers, so there's a strong incentive to do the de-duplication before the upload when possible. I don't wish to call anyone out specifically, but several storage services operate exactly in this way.
I disagree that requiring end-users to effectively operate their own encryption software is a robust path to privacy.
IIRC, SpiderOak doesn't encrypt your files "immediately after uploading". Files are encrypted on the client side even before they're uploaded. Therefore SpiderOak never even sees unencrypted data. That's their "zero knowledge" policy. They think it's better to make it impossible for themselves ever to have any idea what files they're hosting, rather than saying "We used to know X seconds ago, but we don't know anymore."
The blog doesn't mention whether or not SpiderOak uses block-level deduplication. Maybe it's part of their storage infrastructure, maybe isn't. But all that client-side encryption would severely reduce the number of duplicate blocks even if everyone uploaded the same file.
"In a large enough population of data, collisions [of cryptographic hash values] happen."
True, but this does not happen in practice. Using SHA-1 as an example hash function, you'd need about 10^24 different files before you would expect a 50% chance of a collision. You are not going to come anywhere near this limit, 10^24 different files have not been created during the entire span of human history.
... and yet SHA1 collisions have happened. According to NIST, "Federal agencies should stop using SHA-1 for...applications that require collision resistance as soon as practical"
Regrettably, we don't actually have any truly ideal hash functions yet.
I did a Google search for a SHA-1 collision and I thought nobody had found a collision yet, they had just found a collision attack in the 2^50-2^60 range.
Of course, turning a collision into an exploit in this case would be challenging. (Preimage attacks ⊂ collision attacks.)
Not that any of the rest of this argument makes much sense, but SpiderOak (says it) uses SHA256. There are no induced collisions on the horizon for SHA256, and there won't be accidental ones in this data set.
> In a large enough population of data, collisions happen.
So you pick a hash function whose space is so large that the risk of collision is less than the risk of any other possible reason for accidental mis-identification (like all the file's bytes spontaneously switching to the collided file's bytes). You can have databases with trillions of objects with less than a one in a million chance of collision in a 256-bit space.
Realistically, there are a lot of things that are better to worry about than a one-in-a-million chance of losing a file. And if you really need so many objects that that's not enough, just increase the size of the hash space.
Yes; if you increase the hash space sufficiently, these problems go away. I don't think wide hashing has really become a standard industry practice though, because services want to pick the option that is least burdensome to end users' CPUs. Another issue is that once they have a big de-duplication database established based on a particular hash, switching is expensive. I suspect a lot of shops are using md5 still.
Perhaps. That said, even a SHA-512 sum on my computer seems to take a little less than a CPU-second per hundred megabytes. Odds are you're not going to be uploading that fast, so you should be able to do that work "online" and not have a noticeable impact on either upload throughput or user-visible impact. This is doubly true on a multi-core device, since the sha sum I quoted was single-threaded. I would think the more important thing to minimize is user-impacting disk latency from the backup scan.
23 comments
[ 3.3 ms ] story [ 45.9 ms ] threadI don't think a lot of backup providers do this but file-mesh services and file sharing services surely do.
The article makes it sound like it cannot be done.
If there's a way around that, I am your eager student.
By the way, some people have suggested using reference counts as a solution. You then know, for example two or more users share duplicate data, but not which two users. My feeling is that, at some time, you did know which users those were (when the counts were incremented.) I like to stay within the realm of "we are not capable of knowing" instead of simply, "as it happens, we don't know anymore."
Thats why at the end of the post they say that even if they decided to deduplicate in the future, they would have no way of retroactively doing it.
First, you can do variable block-based de-duplication, which is how major storage vendors do it - not per-file, which doesn't really buy you much.
Leveraging this in the SAN firmware also prevents their ridiculous file transfer 'vulnerability' (which only exists due the way they wrote their software) - all of your files copy over the network to the storage system. Once they're on the storage system, at some later time and asynchronously, the storage system runs a dedupe on the blocks, and winnows down its storage. Think of it like transparently compressing on the storage side, only, hopefully, less intense on I/O.
Finally, they could simply encrypt everything and then they can't answer subpoenas about who has knowledge of what - it was all encrypted immediately after uploading, and no log is kept. If the data doesn't exist, you can't be forced to give it up...
I disagree that requiring end-users to effectively operate their own encryption software is a robust path to privacy.
The blog doesn't mention whether or not SpiderOak uses block-level deduplication. Maybe it's part of their storage infrastructure, maybe isn't. But all that client-side encryption would severely reduce the number of duplicate blocks even if everyone uploaded the same file.
True, but this does not happen in practice. Using SHA-1 as an example hash function, you'd need about 10^24 different files before you would expect a 50% chance of a collision. You are not going to come anywhere near this limit, 10^24 different files have not been created during the entire span of human history.
Regrettably, we don't actually have any truly ideal hash functions yet.
Of course, turning a collision into an exploit in this case would be challenging. (Preimage attacks ⊂ collision attacks.)
So you pick a hash function whose space is so large that the risk of collision is less than the risk of any other possible reason for accidental mis-identification (like all the file's bytes spontaneously switching to the collided file's bytes). You can have databases with trillions of objects with less than a one in a million chance of collision in a 256-bit space.
Realistically, there are a lot of things that are better to worry about than a one-in-a-million chance of losing a file. And if you really need so many objects that that's not enough, just increase the size of the hash space.
This explains why adding the ubuntu netbook iso image to the Dropbox folder, synced in milliseconds.
My friend was going a little nuts wondering if Dropbox choked.