[This conversation is spanning three mailing lists -- cryptography@metzdowd.com, [EMAIL PROTECTED], and tahoe- [EMAIL PROTECTED] . Some of the posts have not reached all three of those lists. I've manually added Jerry Leichter and Ivan Krstić to the approved-senders set for p2p-hackers and tahoe-dev, so that further posts by them will appear on those lists.]

On Mar 30, 2008, at 3:13 PM, Ivan Krstić wrote:

Unless I'm misunderstanding Zooko's writeup, he's worried about an
attacker going from a partially-known plaintext (e.g. a form bank
letter) to a completely-known plaintext by repeating the following

1. take partially known plaintext
2. make a guess, randomly or more intelligently where possible,
    about the unknown parts
3. take the current integrated partial+guessed plaintext, hash
    to obtain convergence key
4. verify whether that key exists in the storage index
5. if yes, you've found the full plaintext. if not, repeat from '2'.

That's a brute force search.

That's right. Your comparison to normal old brute-force/dictionary attack on passwords is a good one, and one that Jim McCoy and Jerry Leichter have alluded to as well.

Think of it like this:

Passwords are susceptible to brute-force and/or dictionary attack. We can't, in general, prevent attackers from trying guesses at our passwords without also preventing users from using them, so instead we employ various techniques:

* salts (to break up the space of targets into subspaces, of which at most one can be targeted by a given brute-force attack) * key strengthening (to increase by a constant factor the cost of checking a password) * rate-limits for on-line tries (i.e., you get only a small fixed number of wrong guesses in a row before you are locked out for a time- out period)

However, secrets other than passwords are not usually susceptible to such attacks. You can store your True Name, credit card number, bank account number, mother's maiden name, and so forth, on the same server as your password, but you don't have to worry about using salts or key strengthening on those latter secrets, because the server doesn't run a service that allows unauthenticated remote people to connect, submit a guess as to their value, and receive confirmation, the way it does for your password. (In other words, for such data we generally use an extreme form of the third defense, rate-limiting tries -- the number of guesses that an attacker gets is limited to none!)

Likewise, if you are going to store or transmit those kinds of secrets in encrypted form using a traditional randomly-generated encryption key, then you don't have to worry about brute-force/ dictionary attacks because your strong randomly-selected symmetric encryption key defies them.

The Key Point:

*** Convergent encryption exposes whatever data is put into it to the sorts of attacks that already apply to passwords.

Convergent encryption had been invented, analyzed and used for many years, but to the best of my knowledge the first time that anyone noticed this issue was March 16 of this year (at 3 AM Chicago Time), when Drew Perttula and Brian Warner made that observation. (Although to be fair some of the best-known uses of convergent encryption during these years have been sharing publicly-known files with strangers, in which case I suppose it is assumed that the cleartext does not contain secrets.)

Now PBKDF2 is a combination of the first two defenses -- salting and key strengthening. When you first suggested PBKDF2, I -- and apparently Jerry Leichter -- thought that you were suggesting its salting feature as a solution. The solution that we've come up with for Tahoe (described in my original note) is much like salting, except that the added value that gets mixed in is secret and unguessable, where I normally think of salt as non-secret.

Now I see that you are also emphasizing the key strengthening feature of PBKDF2.

"k" denotes symmetric encryption key, "p" denotes plaintext, "c" denotes ciphertext, "s" denotes salt, "E(key, plaintext)" is encryption, "H()" is secure hashing, "H^1000()" is secure hashing a thousand times over, i.e."H(H(H(H(...))))" a thousand times.

Traditional encryption:

k = random()
c = E(k, p)

Traditional convergent encryption:

k = H(p)
c = E(k, p)

Tahoe-style convergent encryption with added secret ("s"); "s" can be re-used for any number of files, but it is kept secret from everyone except those with whom you wish to converge storage.

s = random()
k = H(s, p)
c = E(k, p)

PBKDF2 (simplified); "s" can be re-used but is generally not, and it is not secret.

s = random()
k = H^1000(s, password)
c = E(k, p)

Now, one could imagine a variant of traditional convergent encryption which added key strengthening:

k = H^1000(p)
c = E(k, p)

This would have a performance impact on normal everyday use of Tahoe without, in my current estimation, making a brute-force/dictionary attack infeasible. Key strengthening allows you to choose an amount of wasted CPU that you are willing to impose on your users during normal use, and multiply the attacker's costs by exactly that amount. If the attacker has 2^64 computational capacity, and the users are willing to waste 2^10 extra computrons on each file access, then the attacker's effective capacity is reduced to 2^54.

The trade-off is actually worse than it appears since the attacker is attacking multiple users at once (in traditional convergent encryption, he is attacking *all* users at once), so he gains an economy of scale, and can profitably invest in specialized tools, even specialized hardware such as a COPACOBANA [1]. At the very least he can profitably devote many CPU cores to churning out new guesses 24/7, while for normal users it is not profitable to allocate a 24/7 CPU load to strengthening their keys. The reason for this disparity is that the attacker gets to attack everyone at once for the same cost as attacking only one target, where the defenders have to pay each for his own defense.

Next, one could imagine a variant of Tahoe's convergent encryption with added secret which adds key strengthening:

s = random()
k = H^1000(s, p)
c = E(k, p)

This would likewise be costly to normal users, but moreover it is not needed because the "s = random()" part of the algorithm locks out all attackers except those with whom s is shared from mounting such an attack at all.

Thank you for your comments on this issue. If you have further ideas, especially as would be relevant to the Tahoe Least-Authority Filesystem, I would love to hear them.


Zooko O'Whielacronx

[1] http://copacobana.org/
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to