42
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ This same question is asked here: security.stackexchange.com/questions/7142/… $\endgroup$
    – Nakedible
    Commented Sep 20, 2011 at 10:13
  • 2
    $\begingroup$ You should explain your notion of "secure", as convergent encryption is either secure or not secure depending on your definition. $\endgroup$
    – Nakedible
    Commented Sep 20, 2011 at 10:14

6 Answers 6

Reset to default
42
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 7
    $\begingroup$ 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. $\endgroup$
    – Nakedible
    Commented Sep 20, 2011 at 10:16
  • 2
    $\begingroup$ 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.) $\endgroup$
    – David Schwartz
    Commented Sep 20, 2011 at 10:23
  • 6
    $\begingroup$ 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"!) $\endgroup$
    – David Schwartz
    Commented Sep 20, 2011 at 13:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Dolberg
    Commented Feb 9, 2013 at 7:05
  • 1
    $\begingroup$ @DavidSchwartz: most of these systems use a fixed IV (perhaps all zeros) because the key is unique to each block. And because the locator is a hash of the plaintext, it can be checked to ensure the data wasn't tampered with. So even though they use CBC or CTR mode, there is zero overhead for IV or authentication tag storage and transmission. $\endgroup$
    – rmalayter
    Commented May 19, 2014 at 13:09
19
$\begingroup$

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”

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ I was asked over on the security stack exchange (security.stackexchange.com/questions/7142/… ) to explain more about this. $\endgroup$
    – Zooko
    Commented Oct 1, 2011 at 5:24
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Zooko
    Commented Oct 1, 2011 at 5:24
  • 2
    $\begingroup$ 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 $\endgroup$
    – Zooko
    Commented Oct 1, 2011 at 5:25
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Paŭlo Ebermann
    Commented Nov 12, 2012 at 19:32
  • $\begingroup$ @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.) $\endgroup$
    – D.W.
    Commented Nov 13, 2012 at 6:41
  • 3
    $\begingroup$ @PaŭloEbermann I will try to sum up my answer according to the article. It's a good motivation and exercise for me :) $\endgroup$
    – curious
    Commented Nov 13, 2012 at 11:35
2
$\begingroup$

One security issue of original convergent encryption is, it is vulnerable to off-line brute force attack. If the adversary knows the entire message space, it can sample each message, computes the hash, encrypts with the computed hash (key) and compares the ciphertext of sampled message with the target ciphertext. If both are the same, the adversary can deduce the sampled message equals the message underlying the target ciphertext. This type of attack has been recognized by Bellare et al., and they formalised a semantic security definition under unpredictability assumption (i.e., not allow the adversary to predict and sample message). The following work DupLESS prevents the off-line brute force attack by introducing a third party entity for co-generating the encryption key, i.e., the encryption key depends on both the message content and a system-wide secret key, which is kept by the third party, so that the outside adversary (not accessing the third-party entity) cannot launch off-line brute force attack.

Another (possible) weakness of convergent encryption is, it might be vulnerable to statistical attack. Although the RCE scheme (having been summarized in one answer before) can generate random ciphertext, the tag for message must be deterministic. The tag consistency defined in Bellare et al. requires, if two messages are the same, they must have identical tag. The tags essentially reflect the probabilistic distribution of plain messages. If the message space is with limited min-entropy, and the adversary has some pre-knowledge about the distribution of the message space, it might successfully guess some messages with significant probability.

Improve this answer
$\endgroup$
-3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 8
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Dec 2, 2012 at 18:31
  • 6
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Dec 3, 2012 at 9:18
-3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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). $\endgroup$
    – Thomas
    Commented Dec 3, 2012 at 6:13
  • $\begingroup$ 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. $\endgroup$
    – Alex
    Commented Dec 3, 2012 at 7:33
  • 3
    $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Dec 3, 2012 at 7:41
  • 3
    $\begingroup$ 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) $\endgroup$
    – CodesInChaos
    Commented Dec 3, 2012 at 9:40
  • $\begingroup$ 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. $\endgroup$
    – Alex
    Commented Dec 4, 2012 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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