Thanks for your detailed response on the convergent encryption issue.

In this post, I'll just focus on one very interesting question that you raise: "When do either of these attacks on convergent encryption apply?".

In my original note I was thinking about the allmydata.org "Tahoe" Least Authority Filesystem. In this post I will attempt to follow your lead in widening the scope. In particular GNUnet and Freenet are currently active projects that use convergent encryption. The learn-partial-information attack would apply to either system if a user were using it with files that she intended not to divulge, but that were susceptible to being brute-forced in this way by an attacker.

On Mar 20, 2008, at 10:56 PM, Jim McCoy wrote:

On Mar 20, 2008, at 12:42 PM, zooko wrote:

  Security engineers have always appreciated that convergent
  encryption allows an attacker to perform a
  confirmation-of-a-file attack -- if the attacker already knows
  the full plaintext of a file, then they can check whether a
  given user has a copy of that file.

The truth of this depends on implementation details, and is an
assertion that cannot be said to cover all or even most of the
potential use-cases for this technique.

You're right. I was writing the above in the context of Tahoe, where, as Brian Warner explained, we do not attempt to hide the linkage between users and ciphertexts. What I wrote above doesn't apply in the general case.

However, there is a very general argument about the applicability of these attacks, which is: "Why encrypt?".

If your system has strong anonymity properties, preventing people from learning which files are associated with which users, then you can just store the files in plaintext.

Ah, but of course you don't want to do that, because even without being linked to users, files may contain sensitive information that the users didn't intend to disclose. But if the files contain such information, then it might be acquired by the learn-partial- information attack.

When designing such a system, you should ask yourself "Why encrypt?". You encrypt in order to conceal the plaintext from someone, but if you use convergent encryption, and they can use the learn-partial-information attack, then you fail to conceal the plaintext from them.

You should use traditional convergent encryption (without an added secret) if:

1.  You want to encrypt the plaintext, and
2.  You want convergence, and
3. You don't mind exposing the existence of that file (ignoring the confirmation-of-a-file attack), and 4. You are willing to bet that the file has entropy from the attacker's perspective which is greater than his computational capacity (defeating the learn-partial-information attack).

You should use convergent encryption with an added secret (as recently implemented for the Tahoe Least Authority Filesystem) if:

1.  You want to encrypt the plaintext, and
2. You want convergence within the set of people who know the added secret, and 3. You don't mind exposing the existence of that file to people in that set, and 4. You are willing to disclose the file to everyone in that set, or else you think that people in that set to whom you do not wish to disclose the file will not try the learn-partial-information attack, or if they do that the file has entropy from their perspective which is greater than their computational capacity.

I guess the property of unlinkability between user and file addresses issue 3 in the above list -- the existence of a file is a much less sensitive bit of information than the existence of a file in a particular user's collection.

It could also effect issue 4 by increasing the entropy the file has from an attacker's perspective. If he knows that the ciphertext belongs to you then he can try filling in the fields with information that he knows about you. Without that linkage, he has to try filling in the fields with information selected from what he knows about all users. But hiding this linkage doesn't actually help in the case the attacker is already using everything he knows about all users to attack all files in parallel.

Note that using an added secret does help in the parallel attack case, because (just like salting passwords) it breaks the space of targets up into separate spaces which can't all be attacked with the same computation.

The first problem is isolating the original
ciphertext in the pool of storage.  If a file is encrypted using
convergent encryption and then run through an error-correction
mechanism to generate a number of shares that make up the file an
attacker first needs to be able to isolate these shares to generate
the orginal ciphertext.  FEC decoding speeds may be reasonably fast,
but they are not without some cost.  If the storage pool is
sufficiently large and you are doing your job to limit the ability of
an attacker to see which blocks are linked to the same FEC operation
then the computational complexity of this attack is significantly
higher than you suggest.

The attacker can do this job more easily, in two ways:

1. He doesn't need to erasure-decode in order to check whether a given erasure-coded share was generated from a given plaintext. He can work forward from guessed-plaintext to encryption key to partial ciphertext to partial erasure coded share, and check that. (Brian Warner already explained that this is actually even easier for an attacker in Tahoe, because he can then go from encryption key to storage index and check that, but in this post I'm trying to address the more general case.)

2. In the "parallel attack", he doesn't need to figure out which erasure-coded shares correspond to which files. For example, suppose he collects the first 32 bytes of many "blocks", where a block is the output of erasure coding after encryption. Then he tries plausible plaintexts, generates the encryption key, generates the first few bytes of ciphertext, and then generates the first 32 bytes of erasure coded share. (The details vary here depending on the encryption and erasure coding, but you see that for typical encryption and typical erasure coding, this is much less work than you might think.) Now he checks if the 32 bytes that he generated appear in the set of 32-byte block headers that he collected. If he gets a match, then he has learned the full contents of a file in the system, although he doesn't know which file or which user.



The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to