Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 20 down vote favorite
10

Recently a company called Bitcasa demonstrated a product of cloud storage. they indicated that they would use "Convergent Encryption" to secure your data and de-duplicate, essentially one copy of the same file between users.

From what I can read on a university paper about Secure Data Duplication which makes mention of "Convergent Encryption" and assuming this is what this is referring too.

My question is, what security implications of using this technology and is it truly secure that you cannot get the key based on chunk data being used to generate different keys between users.

Reference interview on Washington post

share|improve this question
2  
This same question is asked here: security.stackexchange.com/questions/7142/… – Nakedible Sep 20 '11 at 10:13
You should explain your notion of "secure", as convergent encryption is either secure or not secure depending on your definition. – Nakedible Sep 20 '11 at 10:14

5 Answers

up vote 25 down vote accepted

If it's implemented properly, it is as secure as any other form of encryption in preventing those who don't know the data from obtaining it from the encrypted data. However, it does have one fundamental limitation that, so far as we know, is inherent in the technology -- Anyone who has the same file you have can potentially prove that you have that file.

The general way such algorithms work is as follows:

  1. The object to be encrypted is validated to ensure it is suitable for this type of encryption. This generally means, at a minimum, the the file is sufficiently long. (There is no point in encrypting, say, 3 bytes this way. Someone could trivially encrypt every 3-byte combination to create a reversing table.)

  2. Some kind of hash of the decrypted data is created. Usually a specialized function just for this purpose is used, not a generic one like SHA-1. (For example, HMAC-SHA1 can be used with a specially-selected HMAC key not used for any other purpose.)

  3. This hash is called the 'key'. The data is encrypted with the key (using any symmetric encryption function such as AES-CBC).

  4. The encrypted data is then hashed (a standard hash function can be used for this purpose). This hash is called the 'locator'.

  5. The client sends the locator to the server to store the data. If the server already has the data, it can increment the reference count if desired. If the server does not, the client uploads it. The client need not send the key to the server. (The server can validate the locator without knowing the key simply by checking the hash of the encrypted data.)

  6. A client who needs access to this data stores the key and the locator. They send the locator to the server so the server can lookup the data for them, then they decrypt it with the key. This function is 100% deterministic, so any clients encrypting the same data will generate the same key, locator, and encrypted data.

share|improve this answer
3  
Great answer. However, one more attack: an attacker can guess plaintexts and test if you have that file. This attack will reveal passwords in configuration files that haven't been modified otherwise, for example. – Nakedible Sep 20 '11 at 10:16
1  
Thanks. That's really another way of phrasing the same attack. But the different phrasing does suggest other ways the 'weakness' could be exploited. (The most obvious way would be if you had something you weren't supposed to have, such as taking classified material home with you.) – David Schwartz Sep 20 '11 at 10:23
@Nakedible: this attack is totally unavoidable in the case of Bitcasa, because it is a feature of the system to detect files with identical contents, so that storage can be optimized. – Thomas Pornin Sep 20 '11 at 13:03
4  
Actually, I realized there's a fairly simple solution to that problem: Every once in a while, the system randomly gives a group of locators to randomly-selected users (and does not track which it gave or who to). And every once in a while, a user randomly requests the contents corresponding to a locator he actually doesn't have the key to. (This causes issues with knowing how long to keep data and how to bill for storage, but it proves that the attack is not "totally unavoidable" or "inherent in the technology"!) – David Schwartz Sep 20 '11 at 13:25
If you use AES-CBC in step 3 then typically you would use a random initialization vector. Then the whole system is not 100% deterministic. – Peter Dolberg Feb 9 at 7:05
show 1 more comment
up vote 11 down vote

People have been aware of the danger of the "confirmation of a file" attack for a long time, since immediately after convergent encryption was first proposed on the cypherpunks mailing list in 2006. However, most people do not appear to appreciate the more subtle danger of the "learn the remaining information" attack (the one that Nakedible alludes to above). We discovered this latter attack in the Tahoe-LAFS project because independent researcher Drew Perttula spotted the issue and informed us about it, thus winning one of our "Hack Tahoe-LAFS!" prizes. I wrote a brief paper explaining the difference between these two attacks and the countermeasure that we deployed in Tahoe-LAFS which protects against both attacks:

http://tahoe-lafs.org/hacktahoelafs/drew_perttula.html

See also this publication, which unfortunately doesn't cite Drew Perttula's results:

Harnik-2010-“Side Channels in Cloud Services—Deduplication in Cloud Storage”

share|improve this answer
1  
I was asked over on the security stack exchange (security.stackexchange.com/questions/7142/… ) to explain more about this. – Zooko Oct 1 '11 at 5:24
1  
There are two possible attacks. The first one, which we call the "confirmation of a file attack" is the obvious problem that deduplication exposes the fact that the two things were the same as each other. This issue was immediately appreciated and discussed when convergent encryption was first proposed (not under that name) on the cypherpunks mailing list in 1996. (Before Microsoft applied for a patent on convergent encryption, so the cypherpunks discussion is prior art that invalidates the Microsoft patent.) – Zooko Oct 1 '11 at 5:24
2  
The second attack, which we call "learn the remaining information", is not so obvious, and as far as I know nobody was aware of this attack until 2008 when Drew Perttula and Brian Warner developed it as an attack against the Tahoe-LAFS secure filesystem. In the "learn the remaining information" attack, the attacker can make guesses about a few secret, random, unknown parts of a larger file and then find out if one of their guesses is correct. Please see the write-up at: tahoe-lafs.org/hacktahoelafs/drew_perttula.html – Zooko Oct 1 '11 at 5:25
up vote 2 down vote

There is a new theoritical analysis as a new cryptographic primitive, denoted as message lock encryption provided by Mihir Bellare et al to capture convergent encryption.

I am updating my answer regarding the paper abstract. The paper models all existing convergent encryption schemes and it gives the first security definitions of a convergent encryption with cryptographic treatment. It identifies two attacks on the schemes. The tag consistency and the strong tag consistency. Tag consistency means that i cannot compute the tag for file1 and use that encrypt file2 (duplicate facking attakcs). And Strong tag consistency (STC) means that an attacker cannot creates an empty file and when a user tries to store a file that has the same tag with the empty file it keeps storing the empty file. Thus STC protects against erasure attacks. After identifying the weaknesses of existing schemes the paper produces a new one that is one pass (key generation,tag,encryption in one time) by randomizing the encryption. Each user derives the same tag for the same user but they use different keys to encrypt.The xor of he randomize keys with the tag is appended to the ciphertext so in decryption once you know the common tag you xor it with the specific part of the ciphertext to obtain the secret key and you decrypt. You can check page 12 the RCE scheme at the table

share|improve this answer
Thanks for the link – though this is not an actual answer. Could you add a summary of the article here, so it becomes an answer? – Paŭlo Ebermann♦ Nov 12 '12 at 19:32
@PaŭloEbermann, I think this answer is fine as is. It is already a reasonable answer: it points to relevant work in the research literature where people can learn more. I don't know why people on StackExchange get all caught up in giving people a hard time over linking to an external resource. (There is no realistic likelihood that the paper is going to disappear from the Internet or that the IACR ePrint service is going to go away.) – D.W. Nov 13 '12 at 6:41
2  
@PaŭloEbermann I will try to sum up my answer according to the article. It's a good motivation and exercise for me :) – curious Nov 13 '12 at 11:35
up vote -1 down vote

There is a weak point that never mentioned: convergent encryption is unable to choose encryption key, if the hash vale is happened a weak encryption key, the encryption is easy to be attacked.

share|improve this answer
5  
If your encryption primitive has weak keys it sucks, use a better primitive. It's also easy to implement convergent encryption rejects certain keys. This is not a valid problem in practice. – CodesInChaos Dec 2 '12 at 18:31
4  
The probability of obtaining a weak key in this way is negligibly small (unless your crypto algorithm is incredibly broken). Better to worry about getting struck by lightning...twice...in the same hour.... or to worry that a cosmic ray may cause a bitflip error during the crypto computation and cause your secrets to be accidentally printed in the clear. – D.W. Dec 3 '12 at 9:18
up vote -2 down vote

The encryption key of convergent encryption is fixed, it seems that there exists issue in case the encryption key need be changed, such as revoking access right. e.g. I grant access right to someone, the digital envelop containing encryption key has been sent to him, but I find that I made mistake to grant access right to wrong person, I want to revoke the access right . If the system can change the encryption key, revoking access right can be implemented by changing encryption key before that guy retrieves file, but convergent encryption is not applicable for this purpose.

Another possible issue is: It is said that convergent encryption can only use ECB encryption, which is weaker than CBC.

share|improve this answer
1  
Could you provide a reference for the last sentence? I'm not sure what you meant but convergent encryption certainly doesn't need to use ECB (or even CBC, for that matter - any mode of operation will do). – Thomas Dec 3 '12 at 6:13
Storing data with convergent encryption uses hash value of encrypted data as locator, this fact requires same plain text encrypted by same encryption key obtaining same encrypted data, so that ECB is required. – Alex Dec 3 '12 at 7:33
3  
You are confusing deterministic modes of operation with deterministic encryption. You can encrypt the same plaintext with CBC using the same key and IV and you'll get the same ciphertext. ECB/CBC/etc. have nothing to do with it. – Thomas Dec 3 '12 at 7:41
2  
Tahoe LAFS uses convergent encryption with AES in CTR mode. So your last sentence is clearly wrong. It simply derives both key and IV deterministically from the hash of the plaintext (and a convergence secret) – CodesInChaos Dec 3 '12 at 9:40
How about the first issue I raised? Is it a real issue?@CodesInChaos @Thomas My last sentence is not accurate, sorry for it. I was saying that if the encryption algorithm enable same plaintext and same encryption key obtaining different cypertext, the encryption will be more difficult to be attacked. If using CTR/CBC with same IV, the encryption is a little bit weaker. – Alex Dec 4 '12 at 22:45
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.