On 05/31/2012 04:08 PM, Nico Williams wrote:
On Thu, May 31, 2012 at 2:03 PM, Marsh Ray<ma...@extendedsubset.com> wrote:
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,
[...]
Starting with:
Ep = password entropy in bits (chosen by the user)
N = iteration count (chosen by the defender)
For memory-hard PBKDFs you also need a memory size parameter, though
you might derive that from N.
That could be useful.
We could also model the memory access latency and bandwidth of the
defender's servers and the number of CPU cores trying to do other useful
stuff over the same main memory bus and so on. I figured I'd quit while
I was ahead. :-) The defender can think about his own systems in as much
detail as he wishes, but biggest unknowns in the equations are still the
capabilities of his future attackers.
Another big thing I left out is the cost of time to the attacker. Does
he have a deadline? What is the value over time of a user's password. We
used to think of password change policies as putting a hard expiration
limit on the value of this data, but now we know that users typically
share passwords across systems and just put a counter digit at the end
to share them across time. Also, a password often represents the only
entropy securing certain Wifi and VPN protocols so the attacker may have
obtained a packet capture that will remain useful to decrypt long into
the future.
* 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!"
Nice. But again, in practice this won't work. You might think that
for a single master password users could get into the 48 bits of
entropy range, but probably not.
Well what about this (just thinking out loud):
Current password change policies can only occasionally recover the
former level of security after a silent breach, but they make it harder
for users to remember entropic passwords all the time.
What if instead of asking users to throw out their old password and
choose a brand new completely independent strong one every 90 days we
instead asked users to append 12 more characters to their old password?
This way they could get better at remembering longer sequences
incrementally with more practice over time.
Of course once it becomes too long (seems like a good problem to have)
we could start dropping the same number of characters from the front.
Could we in just three password change periods have users on rolling 36
character passwords?
OK so maybe we don't get the same catastrophic fully reseeding property
of a traditional password replacement policy, but if the string the user
appends is subjected to the same length and complexity requirements in
place now then it seems like a rolling long password could be no worse.
Can PBKDF2' be weaker than PBKDF2?
Yes.
Mine or any PBKDF2' in principle?
In principle.
I don't see how my PBKDF2' construction ends up being more
parallelizable than PBKDF2 such that PBKDF2' can run faster than
PBKDF2 -- you need to compute PBKDF2 before you can compute PBKDF2'
and I see no way around that. If memory_hard() is not nearly as
memory-hard (and/or slow) as initially thought then PBKDF2' will not
help much, but it should still not hinder either.
Say memory_hard() was designed with DES as the fundamental primitive
(for slowness of course) back when servers could only spare a 128 MiB of
memory at a time.
Today's attacker would be able to parallelize the DES with a bitslice
implementation on a video card with 4 GB RAM and GPU that can hide
random memory latencies with single-clock context switching between 64
threads.
The defender cannot benefit from that parallelism, he has to hash the
passwords one at a time as users authenticate.
So it doesn't matter how high you turn up parameter N, or even to a
degree M; it's not (just) a question of scaling parameters to track
Moore's law. It's that a hash function that looked as-hard-as-practical
a few years ago turns out to be more a bit more efficient in parallel on
the attacker's hardware than in serial on the defenders'.
Another example:
On 05/31/2012 10:43 AM, Adam Back wrote:
That
particular one has a disadvantage that it requires a few megs of pre-baked
numbers to be shipped with the library.
A few MB of static constants sounds to me like a resource that may be
shareable in the attacker's parallel synchronous implementation, but
maybe even demand-paged in the defender's system.
Unless... unless N
is tuned down on the theory that memory_hard() adds strength -- if it
turns out not to then having turned N down will greatly help the
attacker.
It could also be that memory_hard(P, S, p) introduces
impractical-to-mitigate timing or other side channel attacks that leaked p.
Sure. But let's assume that memory_hard() isn't awful. It just isn't
yet accepted, and it might have some weaknesses. I'd hope that by now
everyone pays attention to timing side channels (but power side
channels? not so much).
No kidding. Did you see http://www.cl.cam.ac.uk/~sps32/qvl_proj.html ?
We can test for timing leaks. We can't test
for as-yet undiscovered optimizations.
You've proposed a nice little construction with which to build memory
hard from components, some of which are well-understood and some of
which are new. You haven't accompanied it with a mathematical proof of
security and even if you had many of us would still be skeptical.
It's because the value of memory_hard() is built on a lot of assumptions
about future hardware availability and the framework for analyzing it's
security benefit seems really quite new (if it's ever been formally
described yet at all).
So it comes down to a lot of specifics that will have to be stared at
and analyzed by a lot of smart (and probably busy) people for a long
time before any such algorithm could be given the same level of official
blessing as plain PBDKF2.
Sure, but I think you're making my point: there are things we could do
to make a PBKDF2' that is at least as strong as PBKDF2.
I think you're right about that.
As long as we
don't respond to PBKDF2' by tuning down N I think that's possible,
trivially possible. But the risk is probably quite high that N will
get turned down ("it used to take 1s to login, now it takes 2s!"->tune
down N so it takes 1s with the new PBKDF2').
Maybe that's even the default assumption? That's what we get if we think
of users having a fixed tolerance for authentication latency. As M goes
up, N must go down.
But how does (M, N) get chosen in practice? This is probably the hardest
to quantify variable on the defender's side. I just put it down as a
cost to the defender that's some nonlinear function of N.
I can only relate my own experience. Not having worked with a wide
variety of high-scale websites in my career as a software developer I
may not be the best person to describe Dd(N). Nevertheless, here's the
evolution of my relationship with the cost of N. (Names and dates
omitted to protect the guilty.)
* I read the Bcrypt paper when reading about the design choices in
OpenBSD. This is probably the first time I heard about work factor.
* I'm a software developer on a product and see a place in the design
where an additional work factor would be beneficial. Based on the
reaction I got when I introduced the lead developers to the concept of a
"state machine", I keep my mouth shut and do not propose any more
radical ideas. (This company had password security already figured out
anyway. They simply mandated that all passwords be all upper case
because "that's the last thing password cracking programs check for".)
* I suggest we include some degree of extra computational load in a
credential validation function. The boss thinks I am joking, does the
Amadeus laugh, and walks off to a meeting.
* I tell the head operations person of a website we are developing that
we really ought to include a work factor into the credentials
validation. He says flatly "No way. There is no way we are doing any
extra work on our web servers."
* The next time I need to implement a credentials validation routine, I
just go ahead and hard code the largest work factor I think I can get
away with. I choose N such that it produces a brief but noticeable delay
on my development box, probably a few hundred ms. This results in an N
that is quite generous by published practices. No one ever notices or
complains about the CPU cost.
(Again this covers many years and several employers and some details are
synthesized, etc.)
I'm sharing my story not to try to hold myself up as some kind of
pioneering software developer in a world of laggards, just to say here's
how I've seen N get chosen in practice. I imagine many companies will
take great delight in using their formal process to convene a committee
of stakeholders to select N. Others will choose the minimum value
required by their auditors and industry standards. Others will choose
N=1 (yes this happens). Others will test different values systematically
to select the largest N their systems can tolerate acceptably.
Regardless, the process by which N is chosen seems almost as much of a
security factor as N itself.
- Marsh
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
