6 ms·
On cryptography and dogmas
- timf 15y agoThis comment from Coda Hale is worth a look: https://github.com/antirez/lamernews/pull/8#issuecomment-2481391 https://github.com/antirez/lamernews/pull/8#issuecomment-248...
- llambda 15y agoLooks 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.
- antirez 15y agoYou 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.
- ohashi 15y agoReading 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.
- nknight 15y agoThings 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.
- tptacek 15y agoThis particular conventional wisdom was not wrong. Your comment, which consists largely of innuendo, is part of the problem, not part of the solution.
- nknight 15y agoI 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".
- tptacek 15y agoYour comparison is false. "goto" is a stylistic nit. Insecure password hashes are not.
- nknight 15y agoForest 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.
- ohashi 15y agoI 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?
- boundlessdreamz 15y agoantirez was very civilized initially. That pull request has a wall of "use bcrypt" comments. It is just a despicable instance of mob mentality.
- adestefan 15y agoIt's cargo cult cryptography. Saying "use bcrypt" is fine, but understand why you say "use bcrypt."
- icey 15y agoI'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.
- tptacek 15y ago"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.
- nknight 15y agoIf 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.
- nathanwdavis 15y agoIn 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 https://github.com/antirez/lamernews/pull/8
- deleted 15y ago[deleted]
- khafra 15y agoBe 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.
- antirez 15y agothe 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.
- xtacy 15y agoantirez, 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,
- antirez 15y agoI 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.
- epenn 15y agoCan 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.
- antirez 15y agothe 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.
- epenn 15y agoI 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.
- antirez 15y agoThere 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: (alphabet_size ^ password_size) / hashes_per_second gives you the amount of seconds needed to crack a password. You can set hashes_per_second to 1 billion for attacks that a private can do with little money. Maybe set it to 1000 billions per second if you want to protect yourself against bigger entities. But once you enlarge the alphabet_size and the password_size it is fast to reach a point where no brute force attack is feasible at all.
- Fluxx 15y agoI 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.
- lusis 15y agoIMHO, 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 =/
- thaumaturgy 15y agoAbsolutely. Coda Hale's "fuck tact" statement does a neat job of ignoring that "fuck tact" leads to stupid arguments like this.
- Fluxx 15y agoOh 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.
- mef 15y agoRegardless 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.
- jcdavis 15y agoSecurity 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.
- mef 15y agoThis 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.
- jgrahamc 15y ago"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.
- viraptor 15y agoWhat'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"?
- jgrahamc 15y agoThere'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.
- gcp 15y agoI 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/92fe3e4e1edf0d0f?hl=nl https://groups.google.com/group/sci.crypt/msg/92fe3e4e1edf0d...
- antirez 15y agoI think this is a different context where it does not make the attack harder. Our context is different AFAIK and the approach works.
- gcp 15y agoI guess the difference is that you're not actually interested in slowing down the generation of a collision, just that of a dictionary attack.
- antirez 15y agoThis 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: x = SHA1(x) x = SHA1(x) ... again and again ... right? Well in the average case after 2^31 iterations you find a collision, right? 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.
- falava 15y agoWhen I saw SHA1(password|salt) in the readme of https://github.com/antirez/lamernews 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 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-security-bug.html http://www.daemonology.net/blog/2011-01-18-tarsnap-critical-...) And this funny little gem: http://xkcd.com/538/ http://xkcd.com/538/
- aaronsw 15y agoThis is moronic. Cryptography is very hard and one tiny mistake can ruin everything. In that kind of situation, do you want to do something clever and new that you just thought up or do you want to go with what's been tried and tested by many? 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.
- antirez 15y agohere 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.
- tptacek 15y agoRFCs 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.
- tptacek 15y agoThe 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.
- Zash 15y agoObligatory: http://xkcd.com/936/ http://xkcd.com/936/
- shin_lao 15y agoYou 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).
- antirez 15y agoHello, please care to share why without an iteration dependent salt it is less secure? I guess what you mean is: x = SHA1(password|salt) for i from 0 to N do { x = SHA1(x|i) } But in our specific context how this helps? In other words, how the attacker is able to compute N-times-nested-SHA1 faster than performing all the iterations? Note: this is not a pre-image attack. Thanks.
- shin_lao 15y agoYou 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.
- skeptical 15y agoI 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.
- yogsototh 15y agoI 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 sha1(salt|pass)=S Knowing "salt" and "S", is there a known attack better than brute force to discover "pass" or sha1(salt2|pass) where salt2 is known and dependent only of salt (for example salt2 = salt + 1)?
- tptacek 15y agoThis 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.
- yogsototh 15y agoHi! 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!
- JonnieCache 15y agoTwitter: the worlds premier platform for sanctimonious whining from people who don't know you.
- jasonwatkinspdx 15y ago"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.
- yogsototh 15y agoIt seems it started a flamewar about sha1 and bcrypt. First: scrypt (http://www.tarsnap.com/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:  V_i =H^i(B) (0 <= i < N) and X = H^N(B), then iterate j ← Integerify(X ) mod N X ← H (X ⊕ Vj ) N times; and output X. The function Integerify can be any bijection from {0, 1}^k to {0...2^k −1}. 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) ...) ) V_i are filled with pseudo random values. 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.
- rnicholson 15y ago> First: scrypt (http://www.tarsnap.com/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.