On cryptography and dogmas

http://antirez.com/post/crypto-dogmas.html

by jcsalterego • 15 years ago

64 107 15 years ago

timf• 15 years ago

This comment from Coda Hale is worth a look: https://github.com/antirez/lamernews/pull/8#issuecomment-248...

llambda• 15 years ago

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.

antirez13• 15 years ago

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.

boundlessdreamz3• 15 years ago

antirez was very civilized initially. That pull request has a wall of "use bcrypt" comments. It is just a despicable instance of mob mentality.

nknight5• 15 years ago

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.

khafra3• 15 years ago

...and then your customer's credit card info would have showed up on an FTP server in Romania six months later.

nathanwdavis• 15 years ago

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

khafra3• 15 years ago

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.

antirez13• 15 years ago

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.

xtacy2• 15 years ago

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,

nwjsmith• 15 years ago

Ask and you shall receive:

http://codahale.com/how-to-safely-store-a-password/

(also explains _why_)

khafra3• 15 years ago

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.

marshray2• 15 years ago

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

tptacek11• 15 years ago

I'll be succinct: if I found a client iterating SHA1 to build a password hash, I would not write them up for it.

epenn2• 15 years ago

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.

antirez13• 15 years ago

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.

epenn2• 15 years ago

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.

showerst• 15 years ago

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.

antirez13• 15 years ago

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, ...

4b) relax the security requirements.

stevelosh• 15 years ago

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.

Fluxx3• 15 years ago

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.

Robin_Message2• 15 years ago

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.

gizzlon2• 15 years ago

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.

tripzilch• 15 years ago

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.

Fluxx3• 15 years ago

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.

lusis• 15 years ago

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 =/

thaumaturgy2• 15 years ago

Absolutely. Coda Hale's "fuck tact" statement does a neat job of ignoring that "fuck tact" leads to stupid arguments like this.

Fluxx3• 15 years ago

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.

mef2• 15 years ago

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.

jcdavis• 15 years ago

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.

mef2• 15 years ago

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.

jgrahamc2• 15 years 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• 15 years ago

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"?

jgrahamc2• 15 years ago

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.

brown9-2• 15 years ago

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.

Xurinos• 15 years ago

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.

antirez13• 15 years ago

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...

pork3• 15 years ago

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!"

JoshTriplett2• 15 years ago

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.

marshray2• 15 years ago

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.

gcp3• 15 years ago

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...

antirez13• 15 years ago

I think this is a different context where it does not make the attack harder. Our context is different AFAIK and the approach works.

gcp3• 15 years ago

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.

Dylan16807• 15 years ago

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.

falava• 15 years ago

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/

aaronsw• 15 years ago

This 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.

antirez13• 15 years ago

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.

tptacek11• 15 years ago

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.

tptacek11• 15 years ago

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.

antirez13• 15 years ago

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.

Zash• 15 years ago

Obligatory: http://xkcd.com/936/

shin_lao3• 15 years ago

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).

antirez13• 15 years ago

Hello, 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_lao3• 15 years ago

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.

skeptical2• 15 years ago

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.

yogsototh7• 15 years ago

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

  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)?

tptacek11• 15 years ago

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.

yogsototh7• 15 years ago

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!

dchest3• 15 years ago

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.

yogsototh7• 15 years ago

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.

skeptical2• 15 years ago

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'.

yogsototh7• 15 years ago

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.

JonnieCache• 15 years ago

Twitter: the worlds premier platform for sanctimonious whining from people who don't know you.

jasonwatkinspdx• 15 years 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.

yogsototh7• 15 years ago

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:

    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• 15 years ago

> 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.

On cryptography and dogmas

Related Stories