[tahoe-dev] [p2p-hackers] convergent encryption reconsidered -- salting and key-strengthening
krstic at solarsail.hcs.harvard.edu
Mon Mar 31 10:47:47 UTC 2008
On Mar 30, 2008, at 9:37 PM, zooko wrote:
> 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.
Tahoe doesn't run this service either. I can't use it to make guesses
at any of the values you mentioned. I can use it to make guesses at
whole documents incorporating such values, which is in most cases a
highly non-trivial distinction.
To make such guesses, I need to account for at least:
- file formats, since an e-mail message has a different on-disk
representation depending on the recipient's e-mail client,
- temporal and transport variance, as PDF documents generally
incorporate a generation timestamp, and e-mail messages include
routing headers (with timestamps!),
- document modifications due to variables other than the one(s) being
guessed, e.g. names, e-mail addresses, customized unsubscribe links.
I would be interested to see an actual real-world example of how a
document would fall to this attack. It strikes me as a cute threat in
theory, but uninteresting in practice.
> *** Convergent encryption exposes whatever data is put into it to
> the sorts of attacks that already apply to passwords.
Sometimes, under highly peculiar circumstances, etc.
> 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
FWIW, I have discussed this threat verbally with colleagues when I was
asked for possible designs for OLPC's server-based automatic backup
system. I dismissed it at the time as 'not a real-world concern'. I
might even have it in my notes, but those weren't published, so it's
> 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.
Yeah, sorry, I wasn't being clear. I should've just said "a key
strengthening function" rather than naming anything in particular.
> This would have a performance impact on normal everyday use of Tahoe
> without, in my current estimation, making a brute-force/dictionary
> attack infeasible.
Adding, say, 5 seconds of computation to the time it takes to store a
file is likely to be lost as noise in comparison with the actual
network upload time, while still making an attacker's life
_dramatically_ harder than now.
> 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)
Again, is there a real-world example of the kind of data or documents
that would show this to be a serious problem? While it's technically
true that you're targeting all the users in parallel when brute
forcing, note that if you're not actually hyper-targeting your attack,
you need to brute force _all_ the variables I mention above in
parallel, except in pathological cases -- and those, if you know of
some, would be interesting for the discussion.
> economy of scale, and can profitably invest in specialized tools,
> even specialized hardware such as a COPACOBANA .
The OpenBSD eksblowfish/bcrypt design can't be bitsliced and generally
doesn't lend itself well to large speedups in hardware, by design.
Ivan Krstić <krstic at solarsail.hcs.harvard.edu> | http://radian.org
More information about the tahoe-dev