-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On May 30, 2012, at 4:28 AM, Maarten Billemont wrote:
> If I understand your point correctly, you're telling me that while scrypt
> might delay brute-force attacks on a user's master password, it's not
> terribly useful a defense against someone building a rainbow table.
> Furthermore, you're of the opinion that the delay that scrypt introduces
> isn't very valuable and I should just simplify the solution with a hash
> function that's better trusted and more reliable.
>
> Tests on my local machine (a MacBook Pro) indicate that scrypt can generate
> 10 hashes per second with its current configuration while SHA-1 can generate
> about 1570733. This doesn't quite seem like a "trivial" delay, assuming
> rainbow tables are off the... table. Though I certainly wish to see and
> understand your point of view.
My real advice, as in what I would do (and have done) is to run PBKDF2 with
something like SHA1 or SHA-256 HMAC and an absurd number of iterations, enough
to take one to two seconds on your MBP, which would be longer on ARM. There is
a good reason to pick SHA1 here over SHA256 and that is that the time
differential will be more predictable.
Let me digress for a moment. It's a truism of security that complexity is the
enemy of security and simple things are more secure. We just had such a
discussion on this list in the last week. However, saying that is kinda like
saying that you should love your mother because she loves you. Each of those is
something it's impossible to disagree with -- how can you be against simplicity
or loving your mother? But neither of them is actionable. The truism about my
mother doesn't say how much I should spend on her birthday present. It doesn't
tell me if I should come home early from work so I can spend more time with her
or spend more time at work so I can be successful and she'll be proud of me.
They are each true, but each meaningless, since I can use the principle to
defend either A or ~A.
Having said that, the sort of simplicity that I strive for and that I like is
something that I call understandability. It isn't code size, or anything like
that, it's how well I can not only understand it, but intuit it. It is similar
to the mathematical concept of elegance in that it is an aesthetic principle.
Like loving my mother, I might do something today and its opposite tomorrow
because it is aesthetic within its context.
I've read the scrypt paper maybe a half-dozen times. As a matter of fact, I
just went and read it again while writing this note. Each time I read it, I nod
as I follow along and when I get to the end of the paper, I'm not sure I
understand it any more. I remain unconvinced. I think it complex. I think it
inelegant. It fails my understandability test. This is not rational, and I know
that; this is why I said that this is something that gentlepersons can disagree
on. I don't think that because *I* don't like it that *you* shouldn't like it.
I also mean no disrespect to Colin Percival, who is jaw-droppingly brilliant. I
read his paper and say "Wow" even as I remain unconvinced.
I also start to poke at it in some odd ways, mentally. I have a friend who
builds custom supercomputers. These things have thousands of CPUs and tens of
terabytes of memory. Would scrypt hold up to its claims in such an environment?
I don't know, and my eyebrow is raised.
Let us suppose that someone were to spend billions of dollars making a
supercomputing site out in the desert somewhere. Would scrypt stand up to the
analytic creativity that they show? I don't know. Moreover, I am irrationally
skeptical; I believe that it would not, and I have no rational reason for it.
Lastly, I fixate on Table 1 of the scrypt paper, on page 14. Estimated cost of
hardware to crack a password in 1 year. In the middle row-section we see an
estimate for a 10 character password. It would take (according to the paper)
$160M to make a computer that would break 100ms of PBKDF2-HMAC-SHA256. The
comparison is against 64ms of scrypt and a cost estimate of $43B. In the next
row-section down, it gives a comparison of 5s of PBKDF2 for $8.3B versus 3.8s
of scrypt for $175T.
PBKDF2 is understandable. It's simple. In my head, I can reach into my mental
box of cryptographic Lego and pull out a couple SHA blocks, snap them to an
HMAC crossbar, and then wrap the thing in a PBKDF2 loop and see the whole thing
in my head. It's understandable. I *believe* Colin Percival's number that 100ms
of iteration will cost $160M (assuming 2009 hardware costs, at standard
temperature and pressure) to break, and I think "Wow. That's good enough." And
if it isn't -- we can up it to 200ms, and handwave out to $300M hardware cost.
I can also mentally adjust those against using GPUs and other accelerators
because it's understandable.
In contrast, I can't get a mental model of scrypt. It is mentally complex and
because of that complexity I don't trust it. I also worry about running it in
constrained environments (like a smartphone). I worry about other things that I
won't bore you with, too. I've made my point.
The bottom line is that my reading of the scrypt paper makes me feel *better*
about PBKDF2 and think it's simple, manageable, and gosh-darn-it, I like it.
But -- this is an aesthetic decision. I don't fault you or anyone else for
coming to the opposite conclusion. Scrypt is a brilliant piece of work, and I
am willing to accept that my tastes are my problem. This is a place where
gentlepersons can disagree.
>
> When you say SHA-1 is broken, are you referring to this property or something
> else? I was unaware of any other issues that SHA-1 suffers but the others do
> not.
>
One of my meta-principles of crypto engineering (I apologize for not adding it
to the previous discussion) is that you should never do something that stupid
people will think you're stupid for doing. This is a corollary to "never argue
with an idiot, people might not be able to tell the difference" and a lemma
towards "never wrestle with a pig, you both get dirty and the pig enjoys it."
In practice -- in this *specific* practice -- there's nothing wrong with using
SHA1 here. As a matter of fact, note that I suggested using PBKDF2-HMAC-SHA1
above because it gives better delta between Intel and ARM above.
But when you do this, someone's going to write you an email telling you that
SHA1 is broken and you shouldn't use it. You'll write back patiently explaining
that you aren't relying on collision-resistance so it's okay. Then someone else
will write you with the same question, and you'll reply to them. Then you'll
put it up as a FAQ on your web site. Then you'll have someone write a flaming
blog post about what an idiot you are, and when you reply to them, they just
won't let go. Then you'll change it to a 1024-bit SHA3 because that's just ever
so much easier than arguing with people.
There are a number of "bugs" in PGP that were "fixed" not because they were
broken but because I got tired of explaining that they were okay. Some time
ago, I was working with Phil Zimmermann on a protocol and I made a tweak to
something clever he had done and he objected that his cleverness was something
that stupid people would think is stupid. He objected until I said, "Does this
mean that I can reply to the people who don't like it with, 'Phil can explain
this ever so much better than I can'?"
>>
>> The real problem you have, however, is in the counter. First of all a
>> counter is not a salt. A salt is an arbitrary non-security parameter. But
>> arbitrary means random, just not secret. A counter is a counter.
>>
>> The counter has two problems to it. One is that it doesn't add to the
>> security of the system. The other it makes system utterly useless.
>>
>> An attacker can easily brute force through the site keys by just running a
>> counter. That's why I say it doesn't add to the security. Even if you used
>> scrypt here, too, it wouldn't matter much. It's still easy to brute force.
>>
>> However, this completely ruins the system for the end user. The end user
>> can't just remember their master password and the site name. They have to
>> remember what *order* they did it in too, which ruins everything. You can't
>> sync this across devices, you have to keep track of orders, and so on. You
>> need to remove the counter.
>>
>> I understand why you did it. You did it because that way two people with the
>> same master password on the same site aren't going to have the same password
>> -- which would give away the master password to the other one, as well as
>> leaking to an attacker that you picked a lousy password, even if they don't
>> immediately know what it is (cue the rainbow tables). Ironically, this is
>> kinda like the recent RSA/GCD thing in that your security oops can be made
>> into a disaster if someone else makes the same oops.
>
> Actually, you make very good points but you're a little off on what the
> meaning of the counter in the algorithm is. Granted, the text doesn't really
> explain clearly.
>
> The counter is actually zero by default for every site; the user need not
> remember the order that they created sites in, the order does not increment
> the counter. The purpose of the counter is solely to give the user the
> ability to create a *new* password for a site, without needing to change the
> site name or his master password. Think about the eventuality that the
> user's site password is compromised or he has been sharing it with his
> girlfriend but then breaks up. Time to increment the site's password counter.
>
> That does very little to help with the issues you highlighted, of course.
> Two users with the same master password will indeed end up with the same site
> password for each site given a standard counter value of 0. The algorithm in
> its current form assumes users won't see each others' passwords. It is, of
> course, entirely feasible that a password database is exposed, but the chance
> that the master password of the attacker matches that of one of the users in
> the exposed database is slim.
>
I understand better. I still point out that the counter ruins your requirement
that the user need only know their master password and the site (and perhaps a
user name). I think this is one of the strengths of your system, and I think
you should keep that property, in spite of the obvious weakness it leaves in.
Understandable is good.
>>
>> You can fix this one by substituting the person's site username for the
>> counter. In this revision, you have K_s = HASH(M + U.length + U + S.length +
>> S). That's a much better construction.
>
> Seeing as Master Password currently does not have any real salt (such as a
> username might provide), you are correct that it is vulnerable to rainbow
> table-based attacks. Adding in a username is a good solution, but it means
> the user has another something they need to remember. And usernames are,
> just like passwords, something many people have trouble keeping track of. I
> might consider asking for the user's real full name instead and use that as a
> salt in the hash like you propose here.
Not bad as an addition. But I'd just say "name." People like me who don't have
a real full name would wonder what to type there.
The cost here, however, is adding complexity that is hard to explain to people.
Worse, the dumber they are, the harder it is to explain that it's safe.
Jon
-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii
wj8DBQFPxxe0sTedWZOD3gYRAoKQAKDtbK/88XZzHNTR06BqWsL9VOJ9eQCfUxOV
KY+Y+i4V8zq6Fe3T36wv1pk=
=UT9X
-----END PGP SIGNATURE-----
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
