Thanks a lot, Jon, for taking the time and sharing your thoughts. On 30 May 2012, at 09:32, Jon Callas wrote: > Your algorithm is basically okay, but there are a couple of errors you've > made, things you and I will disagree over, and one flaw that I consider to > wreck the whole thing. But all of the problems are correctable, easily. If I > have not understood something, or read it too quickly and gotten confused, I > apologize in advance. > > Let me walk through a reduction of your system: > > (1) You take the master password and run it through a 512-bit hash function, > producing master binary secret. > > You pick scrypt for your hash function, because you think burning time and > space adds to security. I do not. This is a place where gentlepersons can > disagree, and I really don't expect to convince you that SHA-512 or Skein > would be better options. I'm convinced that I know why you're doing it, and > it would be a waste of both our times to go further. We just disagree. > > At the end of it, it hardly matters because if an attacker wishes to > construct a rainbow table, the correct way to do it is to assemble a list of > likely passwords and just go from there. It will take longer if they use > scrypt than with a real hash function, but once it's done it is done. They > have the rainbow table. > > This isn't a flaw, it just is. The goal of your system requires that you have > a master secret. But security-wise, there's no win here other than burning > some cycles in a way that the attacker can trivially replicate. > > Security-wise, I'm quite certain that scrypt isn't nearly as secure as any > real hash function you'd pick, but I'm just whining. We know that the > security is password. If they pick "puppies" as their password, it really > doesn't matter what hash function you run it through. Almost certainly, there > is not enough security in their password to make it a difference what > function you picked.
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. > > Let's call the parameters P for password and M for the master key. > > (2) You take M and construct site-specific keys. We'll call the site name N, > your counter C, and the site keys K_s. > > You compute a given site-specific key, K_s, with: > > K_s = SHA1(S + M + C), where "+" is the function that concatenates a null > byte and then the second string. > > Strictly speaking, you really ought to do it in the order K + C + S, because > that's more collision-resistant. It's good practice when computing a keyed > hash to hash the key first. In reality, it probably doesn't matter, but it > *does* save you lots of debates with people like me. Slight mix-up of parameters, but I think I can follow :-) > > You also want to hash in the length of S, too, because that's also more > collision-resistent. > > So you really want it to be K_s = SHA1(M + C + S.length + S), but that's the > only real security problems I can see. The ordering is a nit, and omitting > the length is only a problem if the hash function is broken. Speaking of > which, why not use a non-broken hash function, like SHA256, or SHA512 or > SHA512/160, if the output size matters to you? Given that you're using > scrypt, why not use a better hash function, even if it is slower? But that's > also a nit. I changed the order so that the name of the site wouldn't be last, in order to avoid length extension issues. Adding in the length of the site name would curtail those issues as well, I expect, without needing to change the order. 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. > > 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. > > 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. > > (3) You run the site key, K, through some pretty printer. I really didn't > read this and really don't care. It doesn't matter to me. TL;DR. > > All in all, it's cute. I like it enough to write this note. I advise that you: > > * Pick a real hash function or two. We can debate scrypt, but you can do > better than SHA1. Even a second scrypt is better than SHA1. Maybe. > > * Get rid of the counter. It ruins everything you were trying to do. You > really do want this to just be F(M,U,S). > > * Use the construction I ended up with above: K_s = HASH(M + U.length + U + > S.length + S). > > Jon
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
