It's not clear to me why Dropbox would need your keys to de-dupe. He says so in the article, but doesn't say why.
Why not compute the file hash on your local machine before encryption, and check that hash against a master dupe list (hash, dupe_count) of all hashes from all users' pre-encrypted local files?
Secondly, I cannot see how this requires there to be an index of users hashes. Surely one could store hashes with reference count, increment when a user adds, decrement when a user deletes. The user ID isn't necessary for a reference counter.
Not saying Dropbox isn't doing what he says. But he says de-duping proves they can decrypt and proves they have a list of who has the same files. I don't see it from de-dupe alone.
The proof is indeed in the deduplication. If Dropbox can skip the upload process of some large file because another user has already uploaded it, they must also be able to decrypt that file in order to sync it with your other machines.
Or in order for you to download it through the web interface unencrypted.
I suspect that dropbox works the way you think it does, but your argument actually has a flaw. It could work like this:
- A hash computed locally (on the clients with the large unencrypted file) and sent along to be used by dropbox to detect dupes.
- The key used to encrypt the large file is some function of the file, but not of the hash. The important point is that it's not encrypted with a client specific key, but rather a file specific one. Thus if you have the file, you can compute it.
- When a dupe is detected, the server requests that the uploading client send it a copy of the key, encrypted PGP so that only the other intended clients can decrypt it
> - The key used to encrypt the large file is some function of the file, but not of the hash. The important point is that it's not encrypted with a client specific key, but rather a file specific one. Thus if you have the file, you can compute it.
That's actually an extremely interesting idea. I wonder if using some function of the data, f, to determine encryption keys, leaks information about the encrypted data? My armchair guess would be yes. Of course, the leaked amount (well, the slight-non random distribution by the key being a function of the data) might be small for large files/good function f, which would mean it's probably okay?
I've never heard of any research of a cryptosystem that works like that though, so I'd appreciate if anyone could provide some expert input (or maybe we should just email bruce schneier)
Interesting idea.. if one were to build the system as you described, there would still need to be a common link for the PGP encryption of the file-specific key.
What do you reckon this is? IIRC, based on the other Dropbox article this week, the only relevant information stored in local Dropbox preferences is your account ID and a unique API token for the specific machine.
There was no mention of a plain-text password being stored locally.
Well, dropbox allows you to access all of your data with only a password, so the PGP pair would have to be a function of the password. I'm not sure I follow about storing the password locally. One additional thing that you'd need to do that I didn't mention is keep the file encryption key PGP encrypted on the server. That way, if you know the password, you can authorize access to the file to someone else without having to transfer the file back to whatever machine you're on.
This is not cryptographically sound. Practically, it's still perfectly possible to check for the presence of a known file and find all associated accounts; formally, the standard definitions don't require that e.g. AES(K, K) is secure ("circular encryption").
More generally, cross-account deduplication always makes it possible to tell if anyone has uploaded a file before - that's the entire point!
Sure, this doesn't address the original attack under discussion, but this subthread was about whether deduplication implies that the server has access to the unencrypted file.
AES might not be suitable for this purpose, but I don't see why the scheme I proposed is necessarily weak. Do you? Anyway, I agree it's not particularly practical - if you're really concerned about data security, then encrypt before you upload.
As to your scheme - circular encryption probably works fine in practice, but there's no theoretical guarantee.
The server cannot read files, but can determine who has uploaded any one cipher- or plaintext. ("Encrypted or unencrypted file".) I think that's still bad.
I wonder if it's possible to fix that too -- that is, could the server receive and store encrypted data from a bunch of people without ever knowing who contributed which data?
> If Dropbox can skip the upload process of some large file because another user has already uploaded it, they must also be able to decrypt that file in order to sync it with your other machines.
Not necessarily. The client could send an encrypted version with only (plaintext) hashes of the pieces. EDIT: no, I'm wrong.
> Or in order for you to download it through the web interface unencrypted.
This one I will give you, unless they're doing something really weird like client side decryption through Javascript, which I'm not sure is even possible. However, they could in theory not store the key until you actually use the web interface (and you don't have to, so they wouldn't have it), and also not store the key when you do.
> Why not compute the file hash on your local machine before encryption, and check that hash against a master dupe list (hash, dupe_count) of all hashes from all users' pre-encrypted local files?
You could do this, but it would still be possible to determine which users have a copy of a particular file (or a piece of a file).
> Secondly, I cannot see how this requires there to be an index of users hashes. Surely one could store hashes with reference count, increment when a user adds, decrement when a user deletes. The user ID isn't necessary for a reference counter.
On the surface, it looks like this would discredit the first claim that I've just made. I think though that in reality it could be detected. For example, the Government could require them to wait and watch until a user downloads a file (or piece of a file) keyed by the hash of the piece whose owners need to be identified. Given that this is feasible, I don't think that there is any point implementing this measure, and it would help to maintain data integrity by not doing it.
Comments
It's not clear to me why Dropbox would need your keys to de-dupe. He says so in the article, but doesn't say why.
Why not compute the file hash on your local machine before encryption, and check that hash against a master dupe list (hash, dupe_count) of all hashes from all users' pre-encrypted local files?
Secondly, I cannot see how this requires there to be an index of users hashes. Surely one could store hashes with reference count, increment when a user adds, decrement when a user deletes. The user ID isn't necessary for a reference counter.
Not saying Dropbox isn't doing what he says. But he says de-duping proves they can decrypt and proves they have a list of who has the same files. I don't see it from de-dupe alone.
The proof is indeed in the deduplication. If Dropbox can skip the upload process of some large file because another user has already uploaded it, they must also be able to decrypt that file in order to sync it with your other machines.
Or in order for you to download it through the web interface unencrypted.
I suspect that dropbox works the way you think it does, but your argument actually has a flaw. It could work like this:
- A hash computed locally (on the clients with the large unencrypted file) and sent along to be used by dropbox to detect dupes.
- The key used to encrypt the large file is some function of the file, but not of the hash. The important point is that it's not encrypted with a client specific key, but rather a file specific one. Thus if you have the file, you can compute it.
- When a dupe is detected, the server requests that the uploading client send it a copy of the key, encrypted PGP so that only the other intended clients can decrypt it
I think that should work.
> - The key used to encrypt the large file is some function of the file, but not of the hash. The important point is that it's not encrypted with a client specific key, but rather a file specific one. Thus if you have the file, you can compute it.
That's actually an extremely interesting idea. I wonder if using some function of the data, f, to determine encryption keys, leaks information about the encrypted data? My armchair guess would be yes. Of course, the leaked amount (well, the slight-non random distribution by the key being a function of the data) might be small for large files/good function f, which would mean it's probably okay?
I've never heard of any research of a cryptosystem that works like that though, so I'd appreciate if anyone could provide some expert input (or maybe we should just email bruce schneier)
I don't see why it would need to leak much more information than you're already leaking with a hash. And I'm sure someone has investigated this idea.
Interesting idea.. if one were to build the system as you described, there would still need to be a common link for the PGP encryption of the file-specific key.
What do you reckon this is? IIRC, based on the other Dropbox article this week, the only relevant information stored in local Dropbox preferences is your account ID and a unique API token for the specific machine.
There was no mention of a plain-text password being stored locally.
Well, dropbox allows you to access all of your data with only a password, so the PGP pair would have to be a function of the password. I'm not sure I follow about storing the password locally. One additional thing that you'd need to do that I didn't mention is keep the file encryption key PGP encrypted on the server. That way, if you know the password, you can authorize access to the file to someone else without having to transfer the file back to whatever machine you're on.
This is not cryptographically sound. Practically, it's still perfectly possible to check for the presence of a known file and find all associated accounts; formally, the standard definitions don't require that e.g. AES(K, K) is secure ("circular encryption").
More generally, cross-account deduplication always makes it possible to tell if anyone has uploaded a file before - that's the entire point!
Sure, this doesn't address the original attack under discussion, but this subthread was about whether deduplication implies that the server has access to the unencrypted file.
AES might not be suitable for this purpose, but I don't see why the scheme I proposed is necessarily weak. Do you? Anyway, I agree it's not particularly practical - if you're really concerned about data security, then encrypt before you upload.
As to your scheme - circular encryption probably works fine in practice, but there's no theoretical guarantee.
The server cannot read files, but can determine who has uploaded any one cipher- or plaintext. ("Encrypted or unencrypted file".) I think that's still bad.
I wonder if it's possible to fix that too -- that is, could the server receive and store encrypted data from a bunch of people without ever knowing who contributed which data?
> If Dropbox can skip the upload process of some large file because another user has already uploaded it, they must also be able to decrypt that file in order to sync it with your other machines.
Not necessarily. The client could send an encrypted version with only (plaintext) hashes of the pieces. EDIT: no, I'm wrong.
> Or in order for you to download it through the web interface unencrypted.
This one I will give you, unless they're doing something really weird like client side decryption through Javascript, which I'm not sure is even possible. However, they could in theory not store the key until you actually use the web interface (and you don't have to, so they wouldn't have it), and also not store the key when you do.
I don't follow. How could the client send an encrypted version of a very large file using only 16 KB on the network?
Yes, you're right. Sorry.
> Why not compute the file hash on your local machine before encryption, and check that hash against a master dupe list (hash, dupe_count) of all hashes from all users' pre-encrypted local files?
You could do this, but it would still be possible to determine which users have a copy of a particular file (or a piece of a file).
> Secondly, I cannot see how this requires there to be an index of users hashes. Surely one could store hashes with reference count, increment when a user adds, decrement when a user deletes. The user ID isn't necessary for a reference counter.
On the surface, it looks like this would discredit the first claim that I've just made. I think though that in reality it could be detected. For example, the Government could require them to wait and watch until a user downloads a file (or piece of a file) keyed by the hash of the piece whose owners need to be identified. Given that this is feasible, I don't think that there is any point implementing this measure, and it would help to maintain data integrity by not doing it.