On cryptography and dogmas
antirez.com
antirez.com
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.
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'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.
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.
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.
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.
The long passphrase sentence you posted that happens to be all lower-case letters is seemingly random though.
Here we are entering in the field of the "user component" as well. It is pretty hard...
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.
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.
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 =/
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.
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 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.
Eventually, things called "best practices" become the basis of hysterical and utterly worthless Pavlovian responses as occurred en masse here.
The whole conversation is really a lot of "willy waving" as one British guy wrote somewhere a number of years ago.
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.
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"
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.
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.
Note that I also trust that we should try to follow well established and proven standard, simply not as drones.
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 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.
This is an interesting set of slides that captures the same thoughts:
http://www.bsdcan.org/2010/schedule/attachments/135_crypto1hr.pdfhttp://codahale.com/how-to-safely-store-a-password/
(also explains _why_)
> 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.
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/
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.
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.
https://groups.google.com/group/sci.crypt/msg/92fe3e4e1edf0d...
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.
First of all: try to understand what you read
I didn't read your blog post, as I clearly stated at the beginning :-)
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.
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).
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 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.
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.
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.
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.
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.
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.
"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
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.
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!
Don't try to get clever, just use random passwords.
Here's your problem -- it's a wrong question. "Better than brute force" doesn't mean that the brute force attack is practically unfeasible.
I continue to believe I didn't asked a wrong question.
But you may know an answer.
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'.
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.
And no, your method is not secure.
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!
I personally use a scheme similar to yours, but with PBKDF2. Also, I'm no crypto expert.
Edit: changed "iheartjustinbieber" to hash("iheartjustinbieber") in the last sentence.
In general the math is trivial:
(alphabet_size ^ password_size) / hashes_per_second
It's still better to be using a slower hash function, but a good salt helps.
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.
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.
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 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.
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.
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.