[119157] in cryptography@c2.net mail archive
Re: [p2p-hackers] convergent encryption reconsidered -- salting and key-strengthening
daemon@ATHENA.MIT.EDU (=?UTF-8?Q?Ivan_Krsti=C4=87?=)
Mon Mar 31 11:13:17 2008
Cc: Cryptography <cryptography@metzdowd.com>,
tahoe-dev@allmydata.org
From: =?UTF-8?Q?Ivan_Krsti=C4=87?= <krstic@solarsail.hcs.harvard.edu>
To: theory and practice of decentralized computer networks <p2p-hackers@lists.zooko.com>
In-Reply-To: <C5A20284-A303-4B30-8861-12ABCB4AA8D3@zooko.com>
Date: Mon, 31 Mar 2008 06:47:47 -0400
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 =20=
at any of the values you mentioned. I can use it to make guesses at =20
whole documents incorporating such values, which is in most cases a =20
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 =20
document would fall to this attack. It strikes me as a cute threat in =20=
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 =20=
asked for possible designs for OLPC's server-based automatic backup =20
system. I dismissed it at the time as 'not a real-world concern'. I =20
might even have it in my notes, but those weren't published, so it's =20
moot.
> 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 =20
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 =20=
file is likely to be lost as noise in comparison with the actual =20
network upload time, while still making an attacker's life =20
_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 =20=
that would show this to be a serious problem? While it's technically =20
true that you're targeting all the users in parallel when brute =20
forcing, note that if you're not actually hyper-targeting your attack, =20=
you need to brute force _all_ the variables I mention above in =20
parallel, except in pathological cases -- and those, if you know of =20
some, would be interesting for the discussion.
> economy of scale, and can profitably invest in specialized tools,
> even specialized hardware such as a COPACOBANA [1].
The OpenBSD eksblowfish/bcrypt design can't be bitsliced and generally =20=
doesn't lend itself well to large speedups in hardware, by design.
Cheers,
--
Ivan Krsti=C4=87 <krstic@solarsail.hcs.harvard.edu> | http://radian.org
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
