On cryptography and dogmas(antirez.com)
antirez.com
On cryptography and dogmas
http://antirez.com/post/crypto-dogmas.html
108 comments
The whole situation is moronic.
It's hard to look at the whole discussion here and not wish that Cody had just asked Salvatore in private if he wanted a better hash function, rather than calling him out for it on the thread announcing Salvatore's new program. I've been exactly where Cody is and have learned that there's little productive conversation to be had when someone is excitedly announcing a new project.
At the same time, Salvatore was too prickly about this. His response was dictated by emotion and not his head, and it's painted him into a corner of referring to sound crypto as "dogma" that can be navigated by programmer common sense. He's wrong about that and I suspect he knows it. He could still have been snippy about being told to add bcrypt to his sample application, without trying to make a principled stand about the merits of different KDFs. This isn't the first time Salvatore has been stridently wrong about crypto on HN.
Coda, like the fabled honey badgers of yore, does not give a fuck. If you understand that going in, it's hard to be pissed at him.
One of the charming things about Salvatore's code is that it's build largely without deps. It is probably my favorite thing about Redis, that you can download it and simply type "make"; it doesn't have an autoconf script and implements its own event library. It takes craftsmanship to do that on something as significant as Redis.
It is indeed a downside of bcrypt that it pulls in a dep. If you are avoiding deps as a matter of principle, use a different KDF (this applies only to KDFs; if you need encryption and you DIY, you're boned). But as soon as you write a Gemfile, I reserve the right to make fun of you for hand-rolling your KDF.
It's hard to look at the whole discussion here and not wish that Cody had just asked Salvatore in private if he wanted a better hash function, rather than calling him out for it on the thread announcing Salvatore's new program. I've been exactly where Cody is and have learned that there's little productive conversation to be had when someone is excitedly announcing a new project.
At the same time, Salvatore was too prickly about this. His response was dictated by emotion and not his head, and it's painted him into a corner of referring to sound crypto as "dogma" that can be navigated by programmer common sense. He's wrong about that and I suspect he knows it. He could still have been snippy about being told to add bcrypt to his sample application, without trying to make a principled stand about the merits of different KDFs. This isn't the first time Salvatore has been stridently wrong about crypto on HN.
Coda, like the fabled honey badgers of yore, does not give a fuck. If you understand that going in, it's hard to be pissed at him.
One of the charming things about Salvatore's code is that it's build largely without deps. It is probably my favorite thing about Redis, that you can download it and simply type "make"; it doesn't have an autoconf script and implements its own event library. It takes craftsmanship to do that on something as significant as Redis.
It is indeed a downside of bcrypt that it pulls in a dep. If you are avoiding deps as a matter of principle, use a different KDF (this applies only to KDFs; if you need encryption and you DIY, you're boned). But as soon as you write a Gemfile, I reserve the right to make fun of you for hand-rolling your KDF.
Just to say that I apologize with the HN community and with my twitter followers about my behavior in the past hours. I and coda both made mistakes in our interaction.
What is good is that the result is that, at least, I'm understanding more on the topic. But I guess all this was not needed to reach this goal.
Edit: oh and another thing is, I'm very entusiast about lamer news, but not because of the code, that many programers can implement without troubles, but because of the project.
Slashdot, programming reddit, HN, gave me a lot as a programmer. It is an honor for me to partecipate to a public discussion with so much skilled people here. So I think creating a consortium, like a non profit org, to make this even better, could be awesome.
What is good is that the result is that, at least, I'm understanding more on the topic. But I guess all this was not needed to reach this goal.
Edit: oh and another thing is, I'm very entusiast about lamer news, but not because of the code, that many programers can implement without troubles, but because of the project.
Slashdot, programming reddit, HN, gave me a lot as a programmer. It is an honor for me to partecipate to a public discussion with so much skilled people here. So I think creating a consortium, like a non profit org, to make this even better, could be awesome.
I'm going to be using Lamer News as the basis for a (non-programmer) project. Thank you for releasing it.
here the point is that what I suggested was into an RFC but everybody was too focused on pointing me on bcrypt. I'm not telling that you should invent your crypto, also this is stated in the article.
RFCs are to the crypto literature what Wikipedia is to the history of the Balkans.
This is another instance where I don't care so much about your particular choices, but where you've said something I have a hard time letting go. You can't point to chapter/verse of an RFC as evidence of the soundness of a crypto construction. Sometimes RFCs document good ideas, but other times they don't.
This is another instance where I don't care so much about your particular choices, but where you've said something I have a hard time letting go. You can't point to chapter/verse of an RFC as evidence of the soundness of a crypto construction. Sometimes RFCs document good ideas, but other times they don't.
"It is very important to force users to add non alphanumerical characters and a few capital letters in the password IF security is very important for your application. "
Not it's not. What's important is that users pick a password randomly from a large pool. For example, there's nothing wrong with a long password all in lowercase if the characters are picked randomly (see, for example, how Google 2-factor authentication handles application specific passwords).
"But guess what? This morning I discovered that actually the algorithm PBKDF1 described into RFC2898 does exactly what I proposed."
Actually PBKDF1 has been deprecated since 2000 and replaced by PBKDF2 which doesn't use SHA1 (it uses HMAC-SHA1 instead). And PBKDF1 is a key derivation function, it's not designed to be slow (as is, for example, bcrypt).
Nevertheless, you could iterate SHA1 if you wish.
Not it's not. What's important is that users pick a password randomly from a large pool. For example, there's nothing wrong with a long password all in lowercase if the characters are picked randomly (see, for example, how Google 2-factor authentication handles application specific passwords).
"But guess what? This morning I discovered that actually the algorithm PBKDF1 described into RFC2898 does exactly what I proposed."
Actually PBKDF1 has been deprecated since 2000 and replaced by PBKDF2 which doesn't use SHA1 (it uses HMAC-SHA1 instead). And PBKDF1 is a key derivation function, it's not designed to be slow (as is, for example, bcrypt).
Nevertheless, you could iterate SHA1 if you wish.
PBKDF1 is a key derivation function, it's not designed to be slow (as is, for example, bcrypt)
No that's actually one of the purposes of a KDF:
http://tools.ietf.org/html/rfc2898#page-8 4.2 Iteration Count An iteration count has traditionally served the purpose of increasing the cost of producing keys from a password, thereby also increasing the difficulty of attack. For the methods in this document, a minimum of 1000 iterations is recommended. This will increase the cost of exhaustive search for passwords significantly, without a noticeable impact in the cost of deriving individual keys.
No that's actually one of the purposes of a KDF:
http://tools.ietf.org/html/rfc2898#page-8 4.2 Iteration Count An iteration count has traditionally served the purpose of increasing the cost of producing keys from a password, thereby also increasing the difficulty of attack. For the methods in this document, a minimum of 1000 iterations is recommended. This will increase the cost of exhaustive search for passwords significantly, without a noticeable impact in the cost of deriving individual keys.
What's wrong with long password with all lowercase characters which are not picked randomly? Apart from someone looking at you typing, why would "fuwaiunviohugihyeurpqwjiosnxjcewiorhewuioahfdsfeaw" be worse than "i like unicorns in the morning and hedgehogs in the evening"?
There's nothing really wrong with that as long as it's not predictable in some way. For example, if you knew that all my passwords were song lyrics in lowercase then you could attack my passwords using list of all the world's song lyrics (which would be much smaller than all random lowercase strings of length X).
If you come up with something you can remember that's long and unlikely someone else can guess the search space for then you'll be ok.
If you come up with something you can remember that's long and unlikely someone else can guess the search space for then you'll be ok.
If I knew your passwords were all song lyrics, that's already a failure of security.
If those become common enough, then you have reduced your symbols from 50 (your first example) to 11 (your second) where five ("in the and in the") are typical joining words. We can imagine password crackers can just combine the words in the dictionary just like they currently combine letters and give a higher priority to looking for combinations of conjunctions. The random letters make these approaches a lot more difficult.
It depends what you mean by "random" in this case. Things that would not be random include all-lowercase passwords drawn from personal things such as your name, kid's names, etc - things that can be guessed/found through research.
The long passphrase sentence you posted that happens to be all lower-case letters is seemingly random though.
The long passphrase sentence you posted that happens to be all lower-case letters is seemingly random though.
Sure, but I suspect the 16 chars requirement is too much. It is simpler for users to remember $t33.llar10 then a 16 chars password IMHO in most cases. If you make it hard to accept for users they'll end with the same small world repeated N times.
Here we are entering in the field of the "user component" as well. It is pretty hard...
Here we are entering in the field of the "user component" as well. It is pretty hard...
You're making the fallacy of assuming whats easy for you is easy for everyone else. As the xkcd comic pointed out, which is easier to remember? "x1.Tlm98" or "trix are for kids!"
If you try to remember your password, you've done something horribly wrong. 99% of my passwords come straight out of pwgen, and I immediately have my browser remember them so I don't have to.
Those of us with the right kind of memory system (patterned numbers and letters go straight to long-term until no longer needed, can't remember the fancy Latin word for it) have no problem memorizing any kind of password, as long as it is not both extra-long and extra-meaningless. Of course, I'm also the kind of person that doesn't trust password managers.
Having the ability to memorize passwords helps, since you obviously have to memorize at least a couple of passwords (such as those for your personal system). I'd just argue that when you have dozens of sites you use (which you hopefully use different passwords on), you shouldn't try to memorize passwords for them all, just generate passwords and have your browser remember them.
I think it's important to not confuse "dogma" with "development best practices," a lack of which is one of the problems that is hurting software development. People go off and do their own versions of password hashing because they don't know what's the best practice or think they'r e being safe.
Is it important that you know why brcypyt is a best practice? Yes. I understand that it (tunably) is slow and uses a random salt, which I also know is a best practice for hashing passwords. Is doing repetitive sha1s going to work well enough? Probably, but I don't know enough about cryptography to know fo sure. So when smart people say, "use bcrypt," I do just that.
Programming is too big of a topic for everyone to understand everything about what they're using. We have to trust others.
Is it important that you know why brcypyt is a best practice? Yes. I understand that it (tunably) is slow and uses a random salt, which I also know is a best practice for hashing passwords. Is doing repetitive sha1s going to work well enough? Probably, but I don't know enough about cryptography to know fo sure. So when smart people say, "use bcrypt," I do just that.
Programming is too big of a topic for everyone to understand everything about what they're using. We have to trust others.
IMHO, the thing that bothered me about the whole exchange was that it could have been avoided with a little bit of common courtesy. Instead it turned into a "oh let's go roll that pull request".
I picked up pretty early on that antirez wanted to know the "why" first since one of his stated goals was keeping deps to a minimum. What could have been a nice productive discussion about crypto standards was fucked up by ego, asshattery and language barriers.
Oh and github pull requests are TOTALLY the appropriate place to have those kinds of discussions =/
I picked up pretty early on that antirez wanted to know the "why" first since one of his stated goals was keeping deps to a minimum. What could have been a nice productive discussion about crypto standards was fucked up by ego, asshattery and language barriers.
Oh and github pull requests are TOTALLY the appropriate place to have those kinds of discussions =/
Absolutely. Coda Hale's "fuck tact" statement does a neat job of ignoring that "fuck tact" leads to stupid arguments like this.
Oh totally agree. I saw on person who commented on Salvatore's blog that said, "I just lost all respect for you and your project (Redis)." That seems like a rather large knee-jerk reaction.
This comment from Coda Hale is worth a look: https://github.com/antirez/lamernews/pull/8#issuecomment-248...
Looks like an unfortunate interaction all the way around: I have to admit reading the blog post I felt that the "dogma" lay on the other end of the table...now this link seems to confirm that suspicion.
There is a reason people said, "use bcrypt," and certainly Coda is well qualified to elucidate the details.
Side note: It's a little disappointing to see this kind of negativity shoot up on the front page. But by the same token I'm glad that HN readers are so observant and timf linked to a more complete history of what went down.
There is a reason people said, "use bcrypt," and certainly Coda is well qualified to elucidate the details.
Side note: It's a little disappointing to see this kind of negativity shoot up on the front page. But by the same token I'm glad that HN readers are so observant and timf linked to a more complete history of what went down.
You can't evaluate the interaction reading that pull request comments. The key point is that I was marked as clueless for the idea of iterating SHA1. I was replied that it was ok only after other guys showed it was a proven and ok alternative.
I don't like when people turn down learning. I don't like dogmas. I also have the bad habit of reacting in a non kind way after being stretched too much, read the insults I got on twitter. I'm usually very kind but there is a limit to what I tollerate.
I don't like when people turn down learning. I don't like dogmas. I also have the bad habit of reacting in a non kind way after being stretched too much, read the insults I got on twitter. I'm usually very kind but there is a limit to what I tollerate.
Reading the discussion comes off as you getting very personal in the attacks while most of the comments were centered around code/crytography.
I also am confused by you stating that 'resorting to best practices can be dangerous.' If they are the best practices, they should be the least dangerous one would think?
I've got no horse in this race but that's my opinion and confusion.
I also am confused by you stating that 'resorting to best practices can be dangerous.' If they are the best practices, they should be the least dangerous one would think?
I've got no horse in this race but that's my opinion and confusion.
Things that get the "best practices" label slapped on them are not inherently "best". At best, they reflect conventional wisdom in a particular field. Unfortunately, conventional wisdom is often wrong, and rarely challenged.
Eventually, things called "best practices" become the basis of hysterical and utterly worthless Pavlovian responses as occurred en masse here.
Eventually, things called "best practices" become the basis of hysterical and utterly worthless Pavlovian responses as occurred en masse here.
This particular conventional wisdom was not wrong. Your comment, which consists largely of innuendo, is part of the problem, not part of the solution.
I didn't say it was wrong, I said it was useless. Screaming "use bcrypt" is no more helpful than screaming "don't use goto", and being an ass when someone tries to figure out what the actual problem is just turns them off to your "wisdom".
Your comparison is false. "goto" is a stylistic nit. Insecure password hashes are not.
Forest for the trees. This isn't about technical details, it's a question of psychology. Screaming platitudes at people and being a jerk when they ask "Why?" will not result in them following your advice, regardless of its correctness.
I understand your argument and I think I understand why you make it. We're trained to be skeptical (as scientists of one sort or another), but in reality, I really do wonder if most best practices actually have inherent flaws or if its a perception issue because we notice the times its wrong and not the overwhelming number of times it is right?
antirez was very civilized initially. That pull request has a wall of "use bcrypt" comments. It is just a despicable instance of mob mentality.
"Despicable"? Are you sure that's the word you want to use? I'm not fully on Coda's side on this (it's a silly news site, and I've told more than one HN'er to just stretch SHA1 with iterations), but a great way to guarantee that I end up there is to polarize the discussion with comments like this.
It's actually people like you who create stupid flame wars like this. Do you actually have an opinion about bcrypt versus PBKDF1? Or are you just sitting on the sidelines chanting "FIGHT FIGHT FIGHT"?
Incidentally: in the fully polarized discussion, Salvatore loses.
It's actually people like you who create stupid flame wars like this. Do you actually have an opinion about bcrypt versus PBKDF1? Or are you just sitting on the sidelines chanting "FIGHT FIGHT FIGHT"?
Incidentally: in the fully polarized discussion, Salvatore loses.
Despicable to just add "use bcrypt" comment without understanding why antirez was against it and not responding to his comments. There were several people on that thread who corrected antirez but did it in a civilized manner. I was specifically talking about people who just added "use bcrypt" and not coda
What is "people like me"?
I don't have an opinion about bcrypt v/s PBKDF1. I have an opinion about how people should provide feedback. I don't know where you get the idea that I'm chanting "fight fight fight". Exactly the opposite actually. Provide constructive feedback and don't just mindlessly litter a discussion with "use bcrypt"
What is "people like me"?
I don't have an opinion about bcrypt v/s PBKDF1. I have an opinion about how people should provide feedback. I don't know where you get the idea that I'm chanting "fight fight fight". Exactly the opposite actually. Provide constructive feedback and don't just mindlessly litter a discussion with "use bcrypt"
Since you don't have an opinion about the actual subject we're discussing, you're really only here to talk about people. People I assume you don't actually know. You think you're contributing, but you're just like the kids on the playground taunting the two kids who look like they're about to fight.
You are just trolling. Calm down! I don't think you are even reading my comments fully.
Again I don't know where you are getting the idea that I'm taunting anyone. Also I'm not commenting on people but their collective behaviour. It is an important difference. You are just making baseless allegations.
"two kids" ? If you are referring to coda & antirez, I specifically said I was not referring to coda.
Again I don't know where you are getting the idea that I'm taunting anyone. Also I'm not commenting on people but their collective behaviour. It is an important difference. You are just making baseless allegations.
"two kids" ? If you are referring to coda & antirez, I specifically said I was not referring to coda.
When five people show up on a pull request, out of nowhere, unsolicited, and tell me to use a library that I don't know well, and the first one of them is the author of that library, then I expect some sort of reasonable explanation beyond "use my library." Cargo-culting library usage is just as bad as cargo-culting functions or classes. Just pointing that out.
I've seen this a few times on Github^H^H^H^H^H^H the internet - someone makes a snide comment on an thread, tweets about it, and then a flood of dipshit pile-on comments follow.
It's cargo cult cryptography. Saying "use bcrypt" is fine, but understand why you say "use bcrypt."
If my first exposure to the world of cryptography and information security had involved someone like that, I'd have written them all off as arrogant quacks to be ignored.
Be careful. Tptacek may show up soon to explain in more detail why this is a dangerous direction to go, but the fact that PBKDF2 is a reasonably well-studied key stretching algorithm is the only reason I'd be comfortable iterating SHA1.
To put it simply, there's just so many incredibly subtle ways to introduce weaknesses into crypto that even if you really do understand everything that's going on, you'll still break things by building it yourself.
To put it simply, there's just so many incredibly subtle ways to introduce weaknesses into crypto that even if you really do understand everything that's going on, you'll still break things by building it yourself.
I'm not tpatcek, but yes there's a reason why PBKDF2 doesn't do it that way. Because SHA1(SHA1(SHA1(SHA1(...)))) is broken. Approximately 0.8*log_2(iteration count) bits of entropy are lost with that construction.
http://eprint.iacr.org/2010/384
http://eprint.iacr.org/2010/384
the whole point is in the "to explain". As far it is a matter of explaining everything is fine and I and others can improve. The problem is when you see 8000 tweets just saying "use bcrypt" without having a clue about what is wrong about another approach.
Note that I also trust that we should try to follow well established and proven standard, simply not as drones.
Note that I also trust that we should try to follow well established and proven standard, simply not as drones.
Marshray started getting dead comments for some reason 4 days ago, but his reply to my top comment is extremely relevant:
> I'm not tpatcek, but yes there's a reason why PBKDF2 doesn't do it that way. Because SHA1(SHA1(SHA1(SHA1(...)))) is broken. Approximately 0.8*log_2(iteration count) bits of entropy are lost with that construction. http://eprint.iacr.org/2010/384
It's not a horrifying game-over break to go from 160 bits of entropy to 154 with 1,000 iterations, but you're not getting the security you thought you were; and there's no amount of personal investigation into the problem that would have helped--this is the kind of thing that takes an ecosystem of very smart people working very hard for a long time.
> I'm not tpatcek, but yes there's a reason why PBKDF2 doesn't do it that way. Because SHA1(SHA1(SHA1(SHA1(...)))) is broken. Approximately 0.8*log_2(iteration count) bits of entropy are lost with that construction. http://eprint.iacr.org/2010/384
It's not a horrifying game-over break to go from 160 bits of entropy to 154 with 1,000 iterations, but you're not getting the security you thought you were; and there's no amount of personal investigation into the problem that would have helped--this is the kind of thing that takes an ecosystem of very smart people working very hard for a long time.
antirez, while I really appreciate the sentiment that one should not simply follow dogmas but be curious/question/understand them, there is a fine balance. In your case, if it were a learning exercise, it's perfectly fine to invest time and understand why other approaches are bad.
But if you're writing a software that other people depend on, perhaps it's best if you follow widely accepted principles, but do the questioning and curiosity _later_. On a meta level, depending on a person's level of curiosity, it's very difficult to answer why certain things are the way they are. Sometimes, you just have to take the word for it. :)
I am not pointing fingers at you specifically, but it's just a general observation. I do not know if Lamer News was just an experiment, or a serious effort that others can use.
Cheers,
But if you're writing a software that other people depend on, perhaps it's best if you follow widely accepted principles, but do the questioning and curiosity _later_. On a meta level, depending on a person's level of curiosity, it's very difficult to answer why certain things are the way they are. Sometimes, you just have to take the word for it. :)
I am not pointing fingers at you specifically, but it's just a general observation. I do not know if Lamer News was just an experiment, or a serious effort that others can use.
Cheers,
I agree with you. The problem comes when we are so focused on proven stuff that we end allowing only one possibility at all, since the implementation I suggested was well established practice with an RFC.
> The problem comes when we are so focused on proven stuff...
I sympathize with your overall point, but there's a really good reason why the focus should be on proven stuff: because it's been proven.
You are building an application which will be responsible for safeguarding some of its users' information. You should typically want to do that using a proven approach. If nothing else, it's a cover-your-ass situation: if it turns out that the proven approach has a flaw, you can at least say that you followed standard practices. If your invention has a flaw, you hold all the responsibility.
I hate to fall back to argument-by-analogy (but I have to, since I'm not a cryptographer), but you're somewhat in the situation of installing a fire suppression system for someone, and you're saying, "Well, I don't want to use halon for this, even though it's what all the experts say I should use, because I don't want to deal with the company selling the halon equipment. So let's just use lots and lots of kitchen fire extinguishers instead. They do the same job, and if I use lots of them, it will work just as well."
Maybe. Maybe it will. But, if it doesn't, you will be responsible for having made a decision that flies in the face of lots of advice from lots of very smart people, and the consequences of that decision will affect not just you but also anyone that uses your system.
edit: On the more technical side of things, maybe nobody has yet pointed you to Bruce Schneier's 2005 article on SHA1 weaknesses (http://www.schneier.com/blog/archives/2005/02/cryptanalysis_...). There are several very good points in there about the dangers of using broken cryptographic algorithms. By stretching a broken hash, you could be -- and probably are -- compounding its weaknesses. i.e., you might be making it easier to find a collision, not harder. And, that article was written almost 7 years ago; since then, newer low-cost hardware has been made available which can compute 33 billion MD5 hashes per second (http://blog.zorinaq.com/?e=42), and that was almost a year ago. I swear I read this year about some Russian kids doing a lot better than that, and that ignores things like EC2 which make it economical to do heavy-duty distributed hash breaking.
I sympathize with your overall point, but there's a really good reason why the focus should be on proven stuff: because it's been proven.
You are building an application which will be responsible for safeguarding some of its users' information. You should typically want to do that using a proven approach. If nothing else, it's a cover-your-ass situation: if it turns out that the proven approach has a flaw, you can at least say that you followed standard practices. If your invention has a flaw, you hold all the responsibility.
I hate to fall back to argument-by-analogy (but I have to, since I'm not a cryptographer), but you're somewhat in the situation of installing a fire suppression system for someone, and you're saying, "Well, I don't want to use halon for this, even though it's what all the experts say I should use, because I don't want to deal with the company selling the halon equipment. So let's just use lots and lots of kitchen fire extinguishers instead. They do the same job, and if I use lots of them, it will work just as well."
Maybe. Maybe it will. But, if it doesn't, you will be responsible for having made a decision that flies in the face of lots of advice from lots of very smart people, and the consequences of that decision will affect not just you but also anyone that uses your system.
edit: On the more technical side of things, maybe nobody has yet pointed you to Bruce Schneier's 2005 article on SHA1 weaknesses (http://www.schneier.com/blog/archives/2005/02/cryptanalysis_...). There are several very good points in there about the dangers of using broken cryptographic algorithms. By stretching a broken hash, you could be -- and probably are -- compounding its weaknesses. i.e., you might be making it easier to find a collision, not harder. And, that article was written almost 7 years ago; since then, newer low-cost hardware has been made available which can compute 33 billion MD5 hashes per second (http://blog.zorinaq.com/?e=42), and that was almost a year ago. I swear I read this year about some Russian kids doing a lot better than that, and that ignores things like EC2 which make it economical to do heavy-duty distributed hash breaking.
Interesting points. Another way to convince oneself, is that even experienced professionals are prone to make mistakes.
This is an interesting set of slides that captures the same thoughts:
This is an interesting set of slides that captures the same thoughts:
http://www.bsdcan.org/2010/schedule/attachments/135_crypto1hr.pdfAsk and you shall receive:
http://codahale.com/how-to-safely-store-a-password/
(also explains _why_)
http://codahale.com/how-to-safely-store-a-password/
(also explains _why_)
I'll be succinct: if I found a client iterating SHA1 to build a password hash, I would not write them up for it.
When I saw SHA1(password|salt) in the readme of https://github.com/antirez/lamernews I knew a flame was coming, and that "use bcrypt" and "cryptography is hard" will popup, but not really exactly why?
Thanks for this post antirez, because after diving a little, now I know better the reason, the risks, that tarsnap creator uses scrypt (http://www.tarsnap.com/scrypt.html), that really "cryptography is hard", he also makes bugs (http://www.daemonology.net/blog/2011-01-18-tarsnap-critical-...)
And this funny little gem: http://xkcd.com/538/
Thanks for this post antirez, because after diving a little, now I know better the reason, the risks, that tarsnap creator uses scrypt (http://www.tarsnap.com/scrypt.html), that really "cryptography is hard", he also makes bugs (http://www.daemonology.net/blog/2011-01-18-tarsnap-critical-...)
And this funny little gem: http://xkcd.com/538/
It seems it started a flamewar about sha1 and bcrypt.
First: scrypt (http://www.tarsnap.com/scrypt/) is far better than bcrypt.
Second here is the general idea behind the scrypt algorithm (from the scrypt slides):
Algorithm ROMix:
Theorem:
Under the random oracle model, the class of functions ROMix are sequential memory-hard.
More intuitively,
Then the algorithm access them in pseudo random order.
Which means that is is not only very long to compute but also need a lot of memory.
Now zealot should say _use scrypt_! not bcrypt. And also, even if cryptography is difficult, the idea behind is not so difficult.
First: scrypt (http://www.tarsnap.com/scrypt/) is far better than bcrypt.
Second here is the general idea behind the scrypt algorithm (from the scrypt slides):
Algorithm ROMix:
Given
a hash function H,
an input B (the user password),
and an integer parameter N (computational hardness),
compute: j ← Integerify(X ) mod N
X ← H (X ⊕ Vj )
N times; and output X.
Theorem:
Under the random oracle model, the class of functions ROMix are sequential memory-hard.
More intuitively,
V_0 = H(B)
V_1 = H(H(B))
...
X = V_N = H(H( ... H(B) ...) )
Then the algorithm access them in pseudo random order.
Which means that is is not only very long to compute but also need a lot of memory.
Now zealot should say _use scrypt_! not bcrypt. And also, even if cryptography is difficult, the idea behind is not so difficult.
> First: scrypt (http://www.tarsnap.com/scrypt/) is far better than bcrypt.
Is there any independent analysis on scrypt? Only paper on scrypt I've seen comes from Colin. That's not meant as an attack; I'm interested in learning more, but can't find anything else.
Is there any independent analysis on scrypt? Only paper on scrypt I've seen comes from Colin. That's not meant as an attack; I'm interested in learning more, but can't find anything else.
I couldn't be bothered to read the article entirely, but what he proposes at the end (iterating SHA) is likely broken:
https://groups.google.com/group/sci.crypt/msg/92fe3e4e1edf0d...
https://groups.google.com/group/sci.crypt/msg/92fe3e4e1edf0d...
Setting aside that this is a brute force attack on the hash rather than the key, only made possible because of dropped bits, the method here doesn't apply. It depends on there being no initial salt. All further iterations of sha1 can be salt free and still safe from this attack since you are not able to feed an arbitrary string into the key function.
Edit: Thinking about it I should be more specific, especially since I got confused myself for a moment. The key is that you don't salt the same way at each step. So a unique salt per iteration is great, salting the first iteration is fine, salting zero or all iterations with a particular salt ruins you.
Edit: Thinking about it I should be more specific, especially since I got confused myself for a moment. The key is that you don't salt the same way at each step. So a unique salt per iteration is great, salting the first iteration is fine, salting zero or all iterations with a particular salt ruins you.
I think this is a different context where it does not make the attack harder. Our context is different AFAIK and the approach works.
I guess the difference is that you're not actually interested in slowing down the generation of a collision, just that of a dictionary attack.
This is how it works. Here the attack they want to mount is the following: find another string, ANY string, that will hash to the same output, but only 32 bits of the output.
Since it is any string, it can also be a SHA1 itself. So what you do is to start with an "X" that can be ANY ANY value, even "foo". And you start doing:
But the output 65536 iterations ago was it! The string that will output that specific 32 bit output after SHA1() nested 65536 times. So you want to go backward but it is not possible, SHA1 can't be inverted.
So what you do? You start again from "X" and stop exactly 65536 iterations before you found the wanted value.
Obviously doing 65536 more SHA1s of that string you get the previous output. So you found your string.
Why the original poster says that the attack takes 2x time but can even optimized? Since you can store the value of SHA1 at 10000 iterations, at 20000 and so forth. Then instead of re-running the iteration again you start from the nearest cached value.
Is it clear now? Otherwise please ask me and I'll be willing to help.
Edit: do you see that chat? This is the dogmatic approach we don't need. gcp found a random message on sci.crypt, and it used it as an universal proof that nested SHA1 is wrong (well he said "likely" actually). It may be wrong for other reasons perhaps, but not for this. First of all: try to understand what you read.
Since it is any string, it can also be a SHA1 itself. So what you do is to start with an "X" that can be ANY ANY value, even "foo". And you start doing:
x = SHA1(x)
x = SHA1(x)
... again and again ...
But the output 65536 iterations ago was it! The string that will output that specific 32 bit output after SHA1() nested 65536 times. So you want to go backward but it is not possible, SHA1 can't be inverted.
So what you do? You start again from "X" and stop exactly 65536 iterations before you found the wanted value.
Obviously doing 65536 more SHA1s of that string you get the previous output. So you found your string.
Why the original poster says that the attack takes 2x time but can even optimized? Since you can store the value of SHA1 at 10000 iterations, at 20000 and so forth. Then instead of re-running the iteration again you start from the nearest cached value.
Is it clear now? Otherwise please ask me and I'll be willing to help.
Edit: do you see that chat? This is the dogmatic approach we don't need. gcp found a random message on sci.crypt, and it used it as an universal proof that nested SHA1 is wrong (well he said "likely" actually). It may be wrong for other reasons perhaps, but not for this. First of all: try to understand what you read.
I think there's a fairly huge difference between pointing out an exact attack on the primitive you propose versus dogmatically rejecting it because it's not commonly used. For one, it's possible to have this discussion and arrive at an obvious conclusion (attack does not apply).
First of all: try to understand what you read
I didn't read your blog post, as I clearly stated at the beginning :-)
First of all: try to understand what you read
I didn't read your blog post, as I clearly stated at the beginning :-)
You need to salt each round of SHA-1 otherwise you don't add much security.
You may also want to use SHA-256 instead of SHA-1 and that doesn't add any new dependency AFAIK. Ideally you should use SHA-3 as soon as it's available. SHA-1 is becoming weaker each day...
You may want to offer the possibility to easily replace the password hash algorithm via a snapin (so people who like bcrypt can use it).
You may also want to use SHA-256 instead of SHA-1 and that doesn't add any new dependency AFAIK. Ideally you should use SHA-3 as soon as it's available. SHA-1 is becoming weaker each day...
You may want to offer the possibility to easily replace the password hash algorithm via a snapin (so people who like bcrypt can use it).
Hello, please care to share why without an iteration dependent salt it is less secure? I guess what you mean is:
Note: this is not a pre-image attack. Thanks.
x = SHA1(password|salt)
for i from 0 to N do {
x = SHA1(x|i)
}
Note: this is not a pre-image attack. Thanks.
You protect yourself against any future weakness in the hash where it would be possible to simplify composed calls.
You say
So it is quite natural that the schema I proposed of computing SHA1(SHA1(SHA1(..))) will just do that, adding rounds to SHA1. So for the fundamental properties of SHA1 it should be computationally unfeasible to write a function SHA1000 that is equivalent to 1000 times SHA1 nested but that can be computed easily.
This is logic, but puts too much faith in SHA-1.
Crypto is hard because you assemble black boxes which never fully satisfy the advertized properties.
Nevertheless I think the best is to make it easy to change the algorithm as you will always find someone to tell you it's not secure enough.
You say
So it is quite natural that the schema I proposed of computing SHA1(SHA1(SHA1(..))) will just do that, adding rounds to SHA1. So for the fundamental properties of SHA1 it should be computationally unfeasible to write a function SHA1000 that is equivalent to 1000 times SHA1 nested but that can be computed easily.
This is logic, but puts too much faith in SHA-1.
Crypto is hard because you assemble black boxes which never fully satisfy the advertized properties.
Nevertheless I think the best is to make it easy to change the algorithm as you will always find someone to tell you it's not secure enough.
I tend to be of the opinion that strength of hashes s overrated, other security measures should jump in and this whole discussion should be cooled down.
That said, but nesting sha1 calls you are reducing the size of the output set at each step. You will end up with a reasonably smaller possible hashes. I don't know why everybody seems to ignore this.
Does password hashing qualifies as chryptography? I don't think so.
That said, but nesting sha1 calls you are reducing the size of the output set at each step. You will end up with a reasonably smaller possible hashes. I don't know why everybody seems to ignore this.
Does password hashing qualifies as chryptography? I don't think so.
"That said, but nesting sha1 calls you are reducing the size of the output set at each step"
I don't think so otherwise finding collisions would be trivial. What you do when using nested SHA1 is just to run a cryptographically secure PRNG with a 160 bit internal state.
I don't think so otherwise finding collisions would be trivial. What you do when using nested SHA1 is just to run a cryptographically secure PRNG with a 160 bit internal state.
The in-depth security means you design your system so that it doesn't fall apart if only one of the pieces fall.
As for your comment on the PRNG, it's actually not a very good design. You would rather use a cipher in stream mode which is indeed fed from a hash, because the cipher will have a better and more predictable behaviour over time.
I however don't understand why people were repeating bcrypt as a mantra on your git pull.
As for your comment on the PRNG, it's actually not a very good design. You would rather use a cipher in stream mode which is indeed fed from a hash, because the cipher will have a better and more predictable behaviour over time.
I however don't understand why people were repeating bcrypt as a mantra on your git pull.
"It is very important to force users to add non alphanumerical characters and a few capital letters in the password IF security is very important for your application."
This is a mistake. Virtually all users respond to these requirements using one of a small number of tactics. The requirements add little to no entropy, which makes them very dangerous, because that leads to the mistaken belief that "all our passwords are strong".
The only secure password is a randomly generated one. You can use words/phrases a la diceware or xkcd if it's easier to remember.
This is a mistake. Virtually all users respond to these requirements using one of a small number of tactics. The requirements add little to no entropy, which makes them very dangerous, because that leads to the mistaken belief that "all our passwords are strong".
The only secure password is a randomly generated one. You can use words/phrases a la diceware or xkcd if it's easier to remember.
In case you haven't seen the long thread of comments on the pull request that lead to this blog post: https://github.com/antirez/lamernews/pull/8
Regardless of who is right or wrong on this issue, I have to say I'm pretty impressed with antirez for keeping his cool and being up for genuine dialogue in the face of some pretty brutal and abusive comments from Coda Hale and others.
Security stuff like this is exactly what you shouldn't be having this type of "genuine dialog" about unless you are an expert. Thats not a slight against antirez-I sure as hell am not a security expert either. The point is, this is an area where people shouldn't be trying to get clever. Even in this same thread, jgc has pointed out that PBKDF1 is deprecated, and that it's not designed to be slow (and thus not a good candidate for a password hashing function). Is he right? Maybe. I don't know. Do you? Does antirez?
Yes, the folks commenting on that pull request were being dicks, but that doesn't mean this is the appropriate response.
This is a well reasoned response, but I want to point out that there is nothing wrong with acknowledging that one is a non-expert and wanting to engage in discussion regardless.
Some participants in this thread and in the conversations with antirez seem to think that all developers who are not experts should always blindly obey the cryptography best practices handed down from on high without ever being interested in the details or questioning the whys or wherefores of those practices.
Some participants in this thread and in the conversations with antirez seem to think that all developers who are not experts should always blindly obey the cryptography best practices handed down from on high without ever being interested in the details or questioning the whys or wherefores of those practices.
I am the creator of YPassword, and each time I asked if my algorithm was secure I stumbled upon a lot of people not understanding anything about cryptography that claimed to me:
"Hey! sha1 is sooo absolutely insecure! Use bcrypt!" :-/
"Hey! bcrypt is sooo incredibly insecure! Use scrypt!" (only implemented in C).
You know what? I finished to read the scrypt paper. In fact _theoretically_ scrypt is far more secure than bcrypt, himself (AFAIK) better than PBKDF1. And the general algorithm behind scrypt is _simple_. Not as simple as sha1^n but almost as simple.
I tried to answer my theoretical question two times now. Each time I never meet any real security expert, only a bunch of zealot. And I know they are all zealot because I discussed with a lot of security expert (searchers) during my Ph. D. And I know far more about security than people reading my question might think. Even if it feels like, my question is _not_ a newbie question. But I am not an expert either.
I try my chance with you dear HNers. Here is the question:
Let
"Hey! sha1 is sooo absolutely insecure! Use bcrypt!" :-/
"Hey! bcrypt is sooo incredibly insecure! Use scrypt!" (only implemented in C).
You know what? I finished to read the scrypt paper. In fact _theoretically_ scrypt is far more secure than bcrypt, himself (AFAIK) better than PBKDF1. And the general algorithm behind scrypt is _simple_. Not as simple as sha1^n but almost as simple.
I tried to answer my theoretical question two times now. Each time I never meet any real security expert, only a bunch of zealot. And I know they are all zealot because I discussed with a lot of security expert (searchers) during my Ph. D. And I know far more about security than people reading my question might think. Even if it feels like, my question is _not_ a newbie question. But I am not an expert either.
I try my chance with you dear HNers. Here is the question:
Let
sha1(salt|pass)=S
This is exactly the kind of batshit comment I'm talking about when I say Salvatore shouldn't be calling bcrypt "dogma", even when not using bcrypt is a reasonable choice for him.
In the nineteen seventies, Unix password files had random per user salts --- not salts derived from one another, but random ones --- and those password hashes were better than this one.
In the nineteen seventies, Unix password files had random per user salts --- not salts derived from one another, but random ones --- and those password hashes were better than this one.
Hi! As you are an expert in the domain, do you know if my method to generate personal password seems secure?
Typically, instead of memorizing a lot of random password, I memorize only one password and for each website I use the password:
sha1(password|domainname)
Until here nobody give me a clear answer, and therefore I assume it is secure while not any flaw is discovered.
And more precisely, I use
sha1(password|number|domainname)
because, if I fear my password was discovered, I change it by incrementing the number.
I would be very grateful if you mind answer my question. Thanks!
Typically, instead of memorizing a lot of random password, I memorize only one password and for each website I use the password:
sha1(password|domainname)
Until here nobody give me a clear answer, and therefore I assume it is secure while not any flaw is discovered.
And more precisely, I use
sha1(password|number|domainname)
because, if I fear my password was discovered, I change it by incrementing the number.
I would be very grateful if you mind answer my question. Thanks!
That's vulnerable to a length extension attack: sha1(passwd|am) can be used to derive sha1(passwd|amazon). (See Wikipedia for a discussion.)
Don't try to get clever, just use random passwords.
Don't try to get clever, just use random passwords.
Thank you so much! It is exactly what I was looking for.
a known attack better than brute force
Here's your problem -- it's a wrong question. "Better than brute force" doesn't mean that the brute force attack is practically unfeasible.
Here's your problem -- it's a wrong question. "Better than brute force" doesn't mean that the brute force attack is practically unfeasible.
Your problem is you assumed I use my method to encrypt user password. Not at all. I use my method to generate personal password. And I know I use a very secure master password which make brute force attack practically unfeasible. My main password is more than 16 char long.
I continue to believe I didn't asked a wrong question.
But you may know an answer.
I continue to believe I didn't asked a wrong question.
But you may know an answer.
If there is, most of the people don't know about it, but will still jump in to defend their dogmas till the last drop of sweat.
I'm a cryptography illiterate, I know zero besides the basics, i.e. common sense. But it does annoy me deeply, the amount of people talking about cryptography with a pretentious attitude.
I am glad you ask that question, and I'm suspecting nobody will say 'yes'.
I'm a cryptography illiterate, I know zero besides the basics, i.e. common sense. But it does annoy me deeply, the amount of people talking about cryptography with a pretentious attitude.
I am glad you ask that question, and I'm suspecting nobody will say 'yes'.
The main problem with this question is I get a lot a answer that simply aren't answer to this question, but only the basic good usage of cryptography.
Until here, nobody said 'yes', then I assume my method is secure.
I would have loved to know if this specific question is asked for any kind of hash function, or if nobody never ask such question. For me it seems as a natural question which seem a bit more difficult than finding a collision but easier than cracking completely the hash function.
Until here, nobody said 'yes', then I assume my method is secure.
I would have loved to know if this specific question is asked for any kind of hash function, or if nobody never ask such question. For me it seems as a natural question which seem a bit more difficult than finding a collision but easier than cracking completely the hash function.
To answer your question, AFAIK there are no known first preimage attacks on SHA-1 yet.
And no, your method is not secure.
And no, your method is not secure.
Thanks for your answer. Could you explain me how my method is not secure assuming:
Is the problem linked to sha1 or if I use any other hash this method also fail?
I presume the _only_ method you advocate for is to have a lot of different passwords for each website is to store randomly generated password inside a keychain system. Could you enlighten me? How do you deal with your own password?
Thanks.
edit: it seems we reached the max depth. Thank you Dmitry!
1. The pass is long
2. The preimage is known
Is the problem linked to sha1 or if I use any other hash this method also fail?
I presume the _only_ method you advocate for is to have a lot of different passwords for each website is to store randomly generated password inside a keychain system. Could you enlighten me? How do you deal with your own password?
Thanks.
edit: it seems we reached the max depth. Thank you Dmitry!
Table on estimated cost of hardware to crack a password in 1 year from scrypt paper: http://i.imgur.com/sAOwS.png
I personally use a scheme similar to yours, but with PBKDF2. Also, I'm no crypto expert.
I personally use a scheme similar to yours, but with PBKDF2. Also, I'm no crypto expert.
Can someone explain to me how salts help a hashing algorithm secure itself against a rainbow table? For example, let's say my password is "justinbieber", which then has a salt prefixed to it which turns it into "iheartjustinbieber". If an attacker is unfortunately able to gain access to the hash of my password and the rainbow table he uses has an entry for hash("iheartjustinbieber"), how is that any more secure than the original?
Edit: changed "iheartjustinbieber" to hash("iheartjustinbieber") in the last sentence.
Edit: changed "iheartjustinbieber" to hash("iheartjustinbieber") in the last sentence.
You have to use the salt in a way that is not trivially breakable. Look up HMAC for the only approved way I know of to do it (whoops, dogma; you can probably invent many ways to do it, but HMAC is simple and considered secure, and I don't know anything else that is). Anyone suggesting just making the salt longer is missing the whole damn point of this debate: Cryptography is really hard to get right and smarter people than all of us have screwed it up. Thus, relying on only the best decisions checked by many others is not "dogma"; its the only sensible decision.
I completely agree with your "don't roll your own crypto" argument. But there's a difference between using a hash and inventing your own cryptography.
What kind of use did you have in mind with "trivially breakable"? hash(salt+pass) ?
My point is just that _some_ (not all) things considered unsafe in crypto is still good enough for this kind of use.
What kind of use did you have in mind with "trivially breakable"? hash(salt+pass) ?
My point is just that _some_ (not all) things considered unsafe in crypto is still good enough for this kind of use.
The wikipedia article on HMAC has a good discussion of why hash(salt+pass) isn't the best way to good.
"The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with MAC = H(key ∥ message). However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC. The alternative, appending the key using MAC = H(message ∥ key), suffers from the problem that an attacker who can find a collision in the (unkeyed) hash function has a collision in the MAC. Using MAC = H(key ∥ message ∥ key) is better, however various security papers have suggested vulnerabilities with this approach, even when two different keys are used.[1][3][4]
No known extensions attacks have been found against the current HMAC specification which is defined as H(key1 ∥ H(key2 ∥ message)) because the outer application of the hash function masks the intermediate result of the internal hash. The values of ipad and opad are not critical to the security of the algorithm, but were defined in such a way to have a large Hamming distance from each other and so the inner and outer keys will have fewer bits in common."
The why crypto works is that cryptographers -- some of the most OCD pedants you will ever know -- find a nano-scale fracture in one small relatively unimportant part of an algorithm, and then wrench it open into a gaping lava-spewing chasm of exploitation and credit card theft.
Please just use best practices, but realize that they will be periodically be updated.
"The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with MAC = H(key ∥ message). However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC. The alternative, appending the key using MAC = H(message ∥ key), suffers from the problem that an attacker who can find a collision in the (unkeyed) hash function has a collision in the MAC. Using MAC = H(key ∥ message ∥ key) is better, however various security papers have suggested vulnerabilities with this approach, even when two different keys are used.[1][3][4]
No known extensions attacks have been found against the current HMAC specification which is defined as H(key1 ∥ H(key2 ∥ message)) because the outer application of the hash function masks the intermediate result of the internal hash. The values of ipad and opad are not critical to the security of the algorithm, but were defined in such a way to have a large Hamming distance from each other and so the inner and outer keys will have fewer bits in common."
The why crypto works is that cryptographers -- some of the most OCD pedants you will ever know -- find a nano-scale fracture in one small relatively unimportant part of an algorithm, and then wrench it open into a gaping lava-spewing chasm of exploitation and credit card theft.
Please just use best practices, but realize that they will be periodically be updated.
Well, people have already talked about extension attacks in general, but to be specific: I can potentially calculate the state of the hash algorithm after the salt bytes have been processed, meaning I can precompute to reduce it to hash'(pass) — I consider that broken if you intended to create the function mac(salt,pass). If you have a salt per user, then that's not so bad, but why bother guessing?
Cryptography comes down to much more than using the right primitives. You also have to use the right implementations of those primitives (timing attacks), combined in the right ways (double stream cipher failure), and you have to be sure that the properties you want give you the protection you want (CBC without mac doesn't give you authentication). If you aren't using something with a wikipedia page that describes the entire system, and has some papers describing it and suggesting attacks on it, then you are inventing your own cryptography.
Cryptography comes down to much more than using the right primitives. You also have to use the right implementations of those primitives (timing attacks), combined in the right ways (double stream cipher failure), and you have to be sure that the properties you want give you the protection you want (CBC without mac doesn't give you authentication). If you aren't using something with a wikipedia page that describes the entire system, and has some papers describing it and suggesting attacks on it, then you are inventing your own cryptography.
Actually, rainbow tables don't really matter anymore.
With the new GPU password bruteforcing techniques, it is easier and faster to just rent more Amazon EC2 machines. They're that fast.
Yes it's more expensive than rainbow tables (which are practically free), but not prohibitively so. Especially not for a criminal org bent on cc fraud, anyway.
With the new GPU password bruteforcing techniques, it is easier and faster to just rent more Amazon EC2 machines. They're that fast.
Yes it's more expensive than rainbow tables (which are practically free), but not prohibitively so. Especially not for a criminal org bent on cc fraud, anyway.
It's more secure because if someone else has the password "justinbieber", and their salt is "ihate", then there will be two different hashes. The attacker will have to crack each individually to find out that they have the same password, instead of getting two for the price of one.
If your salt is something like rkD'O:$|tW:kU}SPuuLZ/X(iwtQzVG" then you've kicked up the size of the necessary rainbow table exponentially, or forced them to compute a custom rainbow table for _just_ your salt.
It's still better to be using a slower hash function, but a good salt helps.
It's still better to be using a slower hash function, but a good salt helps.
btw it is important to stress that:
1) slow hash function. 2) per user random salt. 3) everything you want
don't help if the password is "apple".
So also you need:
4a) force users to passwords with required length / non alphanumerical chars, ...
or
4b) relax the security requirements.
1) slow hash function. 2) per user random salt. 3) everything you want
don't help if the password is "apple".
So also you need:
4a) force users to passwords with required length / non alphanumerical chars, ...
or
4b) relax the security requirements.
If you don't use a salt, I can use one of the freely available rainbow tables online to look up your password from the sha1 hash. If you use a salt I cannot do that.
However, if you use the SAME salt for all your passwords, if I compromise your database I simply have to generate my own rainbow table of sha1(salt + actual_password) to use.
If you use a different salt for each user, I have to calculate one rainbow table per user, which is much more time consuming. That said, one user (an admin) is often enough to cause enough damage.
However, if you use the SAME salt for all your passwords, if I compromise your database I simply have to generate my own rainbow table of sha1(salt + actual_password) to use.
If you use a different salt for each user, I have to calculate one rainbow table per user, which is much more time consuming. That said, one user (an admin) is often enough to cause enough damage.
the salt should be a long complex string that is unlikely to be a prefix in your table. Also if the salt is just long this is enough, since the table will hold anyway passwords up to a given length.
I see what you mean. That will no doubt work for the time being, but it does make me wonder how "future proof" that method is. Calculating hashes for any number of character combinations is trivially parallelizable. Even today, price aside, it wouldn't take much effort to spin up a large number of machines on AWS or a similar service to increase the speed in which new hashes could be added to a rainbow table. Eventually the size of the rainbow table will increase to the point where it would also contain the long salt + hash.
There are only two possibilities to get more security: either don't use password based authentication or force your users to pick passwords of 16 chars or more (or smaller if you can force capitalized letters, non alphanum chars...).
In general the math is trivial:
In general the math is trivial:
(alphabet_size ^ password_size) / hashes_per_second
Do you mean generating a new rainbow table for each possible value of the salt?
[deleted]
Obligatory: http://xkcd.com/936/
Twitter: the worlds premier platform for sanctimonious whining from people who don't know you.
Anyone can invent a cryptosystem that they themselves can't break. That's why you need a community, over a long period of time, searching for flaws. Going with the herd is exactly the right thing to do here.