On 05/31/2012 11:28 AM, Nico Williams wrote:
Yes, but note that one could address that with some assumptions, and
with some techniques that one would reject when making a better hash
-- the point is to be slow,
More precisely, the point is to take a tunable amount of time with
strong assurance that an attacker will be unable to perform the
computation with significantly less computational resources.
The deliberate consumption of computational resources is a price that
the defender has to pay in order to impose costs on the attacker. This
ought to be an advantageous strategy for the defender as long as the
attacker is expected to need to invoke the function many times more.
But the defender's and attacker's cost structure is usually very
different. The defender (say a website with a farm of PHP servers)
doesn't get to choose when to begin the computation (legitimate users
can log in at any time) and he pays a cost for noticeable latency and
server resources.
The attacker costs are proportional to the number of guesses he needs to
make to reverse the password. Hopefully this is dominated by wrong
guesses. But the attacker is free to parallelize the computation across
whatever specialized hardware he can assemble in the time that the
credentials are valid (sometimes years). Some attackers could be using
stolen resources (e.g. botnets for which they do not pay the power bill).
Starting with:
Ep = password entropy in bits (chosen by the user)
N = iteration count (chosen by the defender)
Dd(N) = defender's per-iteration cost for N iterations. A nonlinear
function determined primarily by factors out of anyone's
control.
Aa = attacker's algorithmic advantage. This is never < 1.0 because
the attacker is free to use the same algorithm as the defender.
Ah = attacker's hardware and parallelism advantage. This is
never < 1.0 because the attacker is free to use the same
commodity hardware as the defender.
Aw = attacker's server and electric power cost advantage. Probably
close to 1.0 or, in the case of a botnet, easily 1000 or even
infinite.
The defender's advantage to having a work factor looks something like:
N * 2**Ep
Ad = ------------------------------
Dd(N) * Aa * Ah * Ap
Observations:
* The defender's goal is to maximize this function and for a given PBKDF
his only knob to turn is N.
* The attackers goal is to reduce it. If the defender can't find an N
with an Ad significantly than 1.0, he may be better of not imposing a
work factor at all.
* Ep is the only exponential in the whole function. The individual user
has all the leverage in this situation.
* If individual users can be shown to present a different Ep to the
attacker, it could be beneficial to adjust N independently per user. For
example a website might say to a user: "Want to log in 2 seconds faster
next time? Pick a longer password!"
* N appears in both the numerator and denominator. In the denominator it
goes nonlinear and very fuzzy. Yuck!
* The defender would like to increase Ep, but nobody has a really great
way do that yet.
* Cryptographers mainly try to defend Aa and Ah.
* It seems like the defender's best strategy is to increase N until
people begin to notice and complain.
* Clearly the attacker's best move is to beg, borrow, or steal a botnet.
Only a noob would spend billions of dollars on the world's largest
datacenter in the middle of the desert somewhere when they could instead
spend a fraction of that money developing a popular video game and have
millions of users happily bearing the cost of power and hardware
depreciation to provide you with GPU-hours.
so things that make a PBKDF slower are OK:
PBKDF2' = PBKDF2(P' = to_password(memory_hard(P, S, p)) +
to_password(PBKDF2(P, S, p)), S, p)
where P, S, and p are the password, salt and PBKDF parameters,
to_password() generates a password from a key, and + concatenates
strings.
No one would build an H' from H that way. But for a PBKDF it seems
sensible (but see below).
Can PBKDF2' be weaker than PBKDF2?
Yes.
It could turn out to result in an Aa or Ah significantly greater than
1.0. It could end up being usefully parallelizable so it can be
evaluated more efficiently when testing many passwords at one time
rather than one at a time. Even if it just reduced the performance of
other things, say webserver software, sharing the defender's hardware it
could be a step backwards.
It could also be that memory_hard(P, S, p) introduces
impractical-to-mitigate timing or other side channel attacks that leaked p.
As long as PBKDF2 does not throw
away any entropy, and as long as knowing one portion of the password
(say, if the memory_hard function turns out to be weak) is not enough
to guess the remainder from PBKDF2's output, then I think the answer
has to be "no". Now, I'm making assumptions here. Clearly PBKDF2 can
toss some entropy out,
Last I checked, PBKDF2 re-introduced all the starting entropy from P and
S at every iteration. So it shouldn't lose any significant entropy.
for example, so at least one of my two
assumptions is incorrect, but is it enough to wreck the security of my
PBKDF2' construction?
I don't know that what you have proposed is specific enough to answer that.
If memory_hard did not take P and S and instead took
memory_hard(PBKDF2("usage 2" + P, S, N))
it might be easier to think about. We would have less to worry about if
P were passed through a salted one way function before it were handed to
memory_hard.
- Marsh
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
