Hacker Newsnew | comments | ask | jobs | submitlogin
Don't use bcrypt (unlimitednovelty.com)
174 points by bascule 759 days ago | comments


moxie 759 days ago | link

This article doesn't feel very well done to me. He writes: "The first cipher I'd suggest you consider besides bcrypt is PBKDF2."

PBKDF2 is not a cipher. It's a KDF, and it's almost always used with an HMAC or a cryptographic hash rather than a cipher. The thesis of this article seems to be "PBKDF2 is well understood, where bcrypt is not." In fact, the opposite is probably true.

bcrypt uses a block cipher (blowfish) to create its underlying compression function. Block ciphers are extremely well understood, have been studied to death for years, and are modeled on extremely well understood constructs. They can be used to create cryptographic hash functions, but usually aren't, because they're slow (which we don't care about in this case).

Cryptographic hash functions, by contrast, are not well understood at all. They are "magic" in many ways, and aren't modeled after anything. Many more "bad things" happen in this space than in the block cipher space. The only reason people mess with them at all is because they're faster than block ciphers, which again, we don't care about in this case.

The other appeal to PBKDF2 is because it "comes from RSA." This doesn't feel like an extremely compelling argument, but if we were going to believe it, then why not use the PKCS#12 KDF? PBKDF2 was proposed in PKCS#5, and "12" is a larger number than "5", so if we're going to do what RSA tells us we should do, they're essentially saying we shouldn't actually use PBKDF2.

-----

tptacek 759 days ago | link

Ladies & Gentlemen, Moxie Marlinspike, whose comment should be heading up this whole thread.

-----

marshray 759 days ago | link

Now I'm as much a fan of Moxie's as anybody, but I think one part of cryptography that needs to change is this tendency to excessively appeal to authority. Especially when speaking about practical issues.

-----

tptacek 759 days ago | link

So, I agree, but am happy he took the time to comment and (reasonably) concerned that his comment would be buried somewhere in the bottom third of the thread. I'm appealing to high quality comments, not authority.

-----

marshray 759 days ago | link

HN needs a way for us to take subthreads for this kind of meta-discussion and fork them into another dimension.

-----

bascule 759 days ago | link

These are all valid criticisms. Apologies for using "cipher" where I meant "algorithm"

-----

cdavidcash 759 days ago | link

Cryptographic hash functions, by contrast, are not well understood at all. They are "magic" in many ways, and aren't modeled after anything. Many more "bad things" happen in this space than in the block cipher space.

Is this a common opinion amongst practitioners? The opposite philosophy (e.g., that a random oracle is a "weaker object" than an ideal cipher) underlies some lines of work in the theoretical cryptography literature.

-----

tptacek 759 days ago | link

Yes, it's a common opinion (I quoted Schneier on it downthread).

-----

pbsd 759 days ago | link

The two models are equivalent, in fact: http://eprint.iacr.org/2008/246

This of course says nothing about how to go about building an actual cipher/hash that withstands all kinds of cryptanalysis.

Edit: apparently not so clear, I'm told: http://arxiv.org/abs/1011.1264

-----

davidcash 759 days ago | link

A better interpretation of that paper is that it is giving an upper [edit: upper bound] on how inequivalent the models are.

Also, that paper was subsequently shown to be fatally flawed. http://arxiv.org/abs/1011.1264

Anyway, yeah, a theoretical diversion.

-----

smacktoward 759 days ago | link

> I write this post because I've noticed a sort of "JUST USE BCRYPT" cargo cult... This is absolutely the wrong attitude to have about cryptography.

No. This is incorrect. This is exactly the right attitude for most developers to have about cryptography, because on a subject as complex as cryptography most developers (including me!) are nowhere near smart enough to understand the ins and outs.

Encouraging people to make their own decisions on subjects they aren't equipped to understand fully is dangerous advice. It leads to all sorts of bad outcomes. People who have to choose between options they don't really understand end up choosing things at random, or on the basis of incomplete or misleading information, or getting seized up by the need to make a choice and choosing nothing at all.

This makes cryptography one of the very few cases where a cargo-cult approach is better than the alternatives. A simple message that "this is the approach people smarter than you agree is correct, use it," repeated consistently, will help more people more completely than dumping them into the deep end of the crypto pool ever will.

-----

pnathan 759 days ago | link

> No. This is incorrect. This is exactly the right attitude for most developers to have about cryptography, because on a subject as complex as cryptography most developers (including me!) are nowhere near smart enough to understand the ins and outs.

I hear that a lot, and it always reminds me of Jante Law[1]. Its a disservice to keep telling people that they are too stupid to understand something. Too ignorant, perhaps - that can be remedied - but everyone is not too stupid to understand crypto. It's simply another field, mostly mathematical, and goof-ups are easy to make and often very costly.

edit: I should also make another point. Cryptography is exactingly and excruciatingly hard to do at industrial strength. I am not recommending people go out and roll their own crypto for production systems. It's possible for the initiated to do right; it's possible to get initiated. The uninitiated almost certainly will goof. I'd like to further point out [2], which is a discussion and break on a homebrew crypto, for a taste of the difficulties and mathematical sophistication needed.

[1] http://en.wikipedia.org/wiki/Jante_Law

[2]http://phrack.org/issues.html?issue=64&id=10#article

-----

pygorex 759 days ago | link

> Its a disservice to keep telling people that they are too stupid to understand something

That's not the point. Specialization - developing a deep understanding requires time and effort. As a developer choosing a way to store passwords securely is one task out of 1,000 I'm responsible for. So I acquire a general understanding of cryptography to make a decision - but that decision relies heavily on experts and consensus. The worst thing I can do as a developer is to go down the rabbit hole of cryptography and spend 10 hours researching an optimal password hashing scheme for my app. Sure, I've begun the journey of having a deep understanding of crypto - but I still have 999 things to do!

Which reminds me I need to get off HN and get some work done .....

-----

nknight 759 days ago | link

> So I acquire a general understanding of cryptography to make a decision

But this is precisely what the cult priests don't want you to do. There are only two words you need to know: "use bcrypt". Any attempt to learn more is heresy.

-----

pygorex 759 days ago | link

Perhaps. But so what? As a developer the buck stops with you. If something goes wrong the boss (or client) will not be impressed by an excuse of "well I just did what someone on the internet said was best practice".

However I can see the problem with such a culture if your boss happens to be a bcrypt-tard and is closed off to discussion/learning.

-----

specialist 759 days ago | link

Cryptography is exactingly and excruciatingly hard to do at industrial strength.

Related: Which is why I'm against any and all forms of electronic voting. I've done a fair share of crypto (as a user of crypto libraries) and I barely understand how it works. There's ZERO hope for the layperson to understand crypto-based voting systems.

One of the central tenets of American style voting is a public vote count. Using crypto puts the "public vote count" into the hands of a the high priesthood (a few adepts), which is a really bad idea.

-----

FaceKicker 759 days ago | link

Regardless of what you think of the kind of people who the government would contract to develop electronic voting machines, I don't think I'd call them "laypeople". Or are you saying that every individual voter needs to understand the inner workings of the system for it to be effective?

-----

specialist 759 days ago | link

Or are you saying that every individual voter needs to understand the inner workings of the system for it to be effective?

Um, yea. That's what "public vote count" means.

As for the technical competence of our nation's election administrators, have you not been paying attention? I've met many many. Great at elections. Terrible at computers. Completely and utterly reliant on the vendors. Who've manifestly demonstrated their complete inability to code their way out of a wet paper bag, much less be entrusted with the foundations of our democracy.

-----

FaceKicker 759 days ago | link

But they don't need to understand the mathematical details of the cryptographic protocol (do they?), which seemed to be what you were implying. It seems to me the details could easily be abstracted away into a sequence of idiot-proof steps, but I don't know much of anything about public voting systems.

Edit: I'm not sure why I'm getting downvoted - am I misinterpreting what specialist is saying? For another example, look at HTTPS - it secures your communication without any need for knowledge of how it's doing so, you just need to know that if you see the green lock icon you're "safe" (though I'm aware of all the usability issues, like how everyone just ignores warning messages when something goes wrong). Is there something fundamentally different about public voting systems in this regard?

-----

Xylakant 759 days ago | link

I guess you're getting downvoted because that's exactly the point: Every layperson should be able to double check the vote in case of doubt. That includes the nitty gritty details, including the security of the cryptographic protocol. Paper-Ballots are simple. There's not much to understand: Make your cross, count the votes, add up, done. If in doubt, count again. You don't need to trust any expert on anything for that.

-----

ams6110 759 days ago | link

I would say that yes, every voter needs to be able to comprehend the system. Counting paper ballots is something anyone of normal intelligence can understand. Auditing them is something everyone can understand. Not so for cryptographic based systems, particularly proprietary systems.

The only electronic voting system I'd probably be OK with is one that is totally open-source, software and hardware. The implementation must be completely transparent.

Even then, fraud will happen. Always has, always will.

-----

im_dario 759 days ago | link

There are crypto-based voting systems that are very simple to understand, although not being entirely electronic: http://www.wombat-voting.com/

By all means, there are different shades of grey. It should not be all black or white.

-----

specialist 758 days ago | link

Crypto-based voting systems are not designed to work for real-world elections. They work fine for contrived academic studies.

They all rely on one's vote being lost within a herd of votes. So if your ballot is one of a million, and the ballots are simple with a few races/issues, it's easy to have a secure one-way hash with collisions. (The collisions make it impossible to work backwards to infer how each person voted.)

Alas, real-world elections in the USA are administered at the precinct level. In my state, that's between 0 and 1000 registered voters.

Further, a general election (November) ballot will have dozens of issues and races.

So it's more than likely that any single ballot will be utterly unique. So with the voting systems I studied, it's trivial to infer how everyone voted.

I could imagine crypto-based voting systems working for certain applications. Like corporate shareholder meetings. Or maybe Australian and British style parliamentary elections. (Don't hold me to the last guess, I only have cursory knowledge of their election systems.)

Edit: I discussed these practical issues with one of the grad student authors of a crypto-based voting system. Being completely ignorant of real elections, he had NO IDEA what I was talking about. He denigrated my input; saying our elections should be easily tailored to accommodate crypto. (Good luck with that.)

Maybe it's just me, but I'm of the opinion that people setting out to solve a problem should probably make some token effort to first understand the problem. YMMV.

-----

mturmon 759 days ago | link

One more example: pseudorandom number generation (non-cryptographic). There are lots of algorithms out there, and lots more you could design, but the Mersenne twister has pretty much become the first-choice algorithm.

Especially with linear congruential generators, it's easy for people who don't know what they're doing to add "extra randomization" that makes the resulting numbers worse than the originals.

It's better for most people to not get fancy and use the standard algorithm.

-----

marshray 759 days ago | link

MT uses a lot of memory. IIRC, it's multiple KiB where 64 bits ought to do fine.

A modern CSPRNG like the SHA-3 candidate Skein can produce random data at a steady rate of only a few cycles per byte. I wonder if at some point something like that will dethrone MT for non-crypto PRNGs.

-----

mturmon 759 days ago | link

Something will dethrone the MT -- everything gets dethroned eventually. Besides what you mention, its algorithm is somewhat over-complex.

But it will be a long time before an alternative is better in a compelling way. And take a look at the list of implementations for the MT:

http://en.wikipedia.org/wiki/Mersenne_twister#Implementation...

That's not a single throne, it's a multifaceted empire.

-----

tpsreport 759 days ago | link

The point here is that this particular cargo cult around bcrypt (one subscribed to by some really loud people) has a shaky foundation and does not deserve its reputation. He's offering alternatives that have been better studied.

So, by all means, subscribe to a cargo cult for crypto. But pick the cult carefully.

-----

Firehed 759 days ago | link

He's correct in that if you've selected bcrypt for key derivation, there's a good chance you could be doing things better (for one, its output is only 184 bits long; insufficient for AES256) where PBKDF2 works in a way where you can customize the output length.

However, the point of the bcrypt argument is not that bcrypt is the best algorithm for certain things, but that it's (at a minimum) about four orders of magnitude better than most people's "secure" password storage algorithm: sha1(password). Because it requires both a salt and a work factor, even a dictionary attack is wildly impractical unless there's a massive flaw discovered in the algorithm.

If developers are going to be trained to pick a specific algorithm for password storage, I'd much prefer bcrypt (no known flaws, many benefits) over sha1 or md5 (designed to be fast for checksumming, salt not required). Might PBKDF2 be a better choice still? Very possibly; I haven't done enough research to intelligently answer - and since this is crypto, I will not best-guess it.

My real point here? The article attacks bcrypt as a key derivation algorithm, but I've never seen someone suggest it to be used in such an application. Even the post that started what you may call the bcrypt movement (http://codahale.com/how-to-safely-store-a-password/) is linked in the article, and it's titled "How to safely store a password". It is NOT titled "How to safely derive encryption keys".

So yeah, I'm calling linkbait.

-----

tptacek 759 days ago | link

It's not better than bcrypt for password storage; it's marginally worse. See downthread.

-----

smacktoward 759 days ago | link

But just the existence of multiple cargo cults causes damage, because it leads people to assume that "the experts are divided." Which will lead some people to go with the wrong batch of experts, and others to just throw up their hands in confusion and store their passwords in plain text because it's too hard for them to figure out which group of experts is right.

This is a case where unanimity in the message is important. If all the experts say "use A," people will take that to mean there's no debate about the merits of A over B and C, and use A. If some say "use A" while others say "use B" or "use C", some fraction of listeners will give up and use nothing at all.

-----

tptacek 759 days ago | link

He's wrong. (Read downthread for why I said this; my bluntness here is a mercy).

-----

bascule 759 days ago | link

You're defending cargo cult cryptography? If you try to use crypto without understanding it, you're at great risk of using it wrong.

-----

tptacek 759 days ago | link

The opposite turns out to be true in practice. People have the choice of using a simple crypto library interface (like BouncyCastle PGP) or "really getting to understand" AES, and so end up fielding software with vulnerabilities PGP addressed in the '90s.

A pithier way to say the same thing is, "you're right, except for the words 'without understanding it'".

-----

jiggy2011 759 days ago | link

It depends what level you are using it on. If you are writing crypto libraries on your own then sure you are at significant risk of screwing it up, but a good crypto library should have good defaults that will provide proper security.

Expecting every programmer who needs to build an application that stores passwords or personal information etc to have a rigorous mathematical understanding of crypto (this probably means having a PhD or similar in the subject) is just plain unrealistic.

It's sort of akin to suggesting you shouldn't allow a mechanic to change the brakes on your car without them having a detailed understanding physics.

-----

timwiseman 759 days ago | link

This is true, but most programmers don't and won't ever get a deep understanding of crypto. For that large majority, it makes complete sense to ask "What do the people who do understand crypto use in a case like this?" and use that.

That kind of copying is clearly inferior to either gaining the knowledge to make an informed decision or hiring an expert to do it for you, but for most projects that need crypto neither one of those is practical. So, copying the experts is the best practical approach in most cases.

-----

derefr 759 days ago | link

I can use a microwave without any understanding of its functioning, or I can try to understand electromagnetism well enough to build my own. I know which method I'd trust not to render me sterile.

-----

InclinedPlane 759 days ago | link

Option 1: Rely on what everyone else does.

What happens if that method is flawed? You hear about it as soon as it's discovered and it gets fixed quick.

Option 2: Roll your own stack based on a personal understanding of cryptography.

What happens if that method is flawed? Perhaps only you and an attacker could possibly know such a thing. You have to be ever vigilant and you have to acquire an incredible amount of crypto knowledge. If you ever leave the company they are pretty much fucked from then on until whatever you wrote is replaced.

Don't roll your own system.

-----

InclinedPlane 759 days ago | link

To add on to this, it is of course necessary to have enough familiarity and competence with the basic principles of cryptography to know that you're "doing what everyone else is doing" correctly, instead of just some silly pantomime, such as: http://thedailywtf.com/Articles/Topgrade,-SHA1-Encryption.as...

But it's not necessary to understand the depths of cryptography beyond that there are various black boxes that have certain properties.

-----

gfaremil 759 days ago | link

It is very dangerous to be ignorant about critical computer science fields like cryptography and just go with the cult.

I'm not saying you should build your own cryptography, but a good hacker (or a good engineer how we call them in early 90s) should understand difference between bcrypt, PBKDF2, and scrypt. At least to understand why bcrypt is better than salt+SHA-1. And some other aspects of security.

However, if somebody has no clue about cryptography and security then she/he should go with bcrypt - but I'm not sure if that person should be responsible or in business of storing somebody's critical data at all.

-----

pleasebehonest 759 days ago | link

That attitude is abrasively condescending.

Why not just say, "people who spent a lot of their time studying cryptography strongly recommend this approach. They feel the approach that you are considering is simply insecure."?

Framing things in terms of intelligence isn't going to win anyone over, if that's your goal. And it probably isn't accurate, either.

-----

tptacek 759 days ago | link

Sounds pretty close to accurate to me. Do you want to feel good, or do you want to choose good crypto? Pick one or the other.

-----

smacktoward 759 days ago | link

By all means, use different wording when passing this message along if you're worried about hurting the recipient's fee-fees. But you won't be doing them any favors if you change the message to a Stuart Smalley-style "You can do it! You're good enough! You're smart enough! And gosh darn it, people like you!" Because on this specific subject, the odds are very, very, very unlikely that they actually are.

-----

dhimes 759 days ago | link

He's probably using "smart" in the sense of "accumulated knowledge in a particular space" instead of in the sense of raw mental horsepower. http://news.ycombinator.com/item?id=3583985

-----

smacktoward 759 days ago | link

Yes, that's right. It doesn't mean that you are hopelessly non-cognitive if you can't understand the complexities of cryptography. (As I said, I certainly can't.) It just means that unless you are one of the very few people who are 1) exceptionally mathematically talented and 2) able to have spent your entire life studying the subject, it's unlikely that you could make an informed choice.

-----

jiggy2011 759 days ago | link

it's not necessarily about intelligence per se.

I think "smarter" in this context means more well read about the particular subject of crypto, although people good at that are likely to very intelligence all round too.

A different approach is not necessarily "less secure" it's just that it may have had less people banging on it trying to figure out ways to break it.

-----

tptacek 759 days ago | link

PBKDF2 is worse than bcrypt.

scrypt is better than bcrypt.

bcrypt has the advantage of being both very good, and also broadly available on web platforms. scrypt does not yet have that advantage; when it does, I will start saying "just use scrypt".

But the simple fact is: all three of these functions are fine. ANY of them is a huge step forward from what people do without them.

"Just use bcrypt" is 1000x more effective as a meme than "just use adaptive hashing" (which is what all these constructions are).

So, while I have few specific technical qualms with this article (e.g. why do I care whether something is a PKCS standard or not?), the overall message is a bit hyperbolic.

-----

cperciva 759 days ago | link

PBKDF2 is worse than bcrypt.

By roughly a factor of 5.

scrypt is better than bcrypt.

By roughly a factor of 4000.

why do I care whether something is a PKCS standard or not?

You don't care, and I don't care, but I'm sure you know lots of companies which do care (especially since PBKDF2 is a NIST standard too).

-----

tptacek 759 days ago | link

For what it's worth: when dealing with banks and financial firms, where any technology without an adequately staid and reassuring web presence is frowned upon, we happily recommend PBKDF2. There's nothing "wrong" with PBKDF2. It's just not as good as bcrypt.

-----

regularfry 759 days ago | link

When we were looking at password hashing, and the choice came down to bcrypt or scrypt (about a year ago, so recently enough), I said we should go for bcrypt because scrypt was comparatively new; inasmuch as it makes a difference, it's just had less time to be attacked.

Was I wrong?

-----

zobzu 759 days ago | link

its a sane decision. just make sure you implement properly. like everything crypto, it will be broken, eventually. but its a safer choice than a new algoritm.

it reminds me of the vulnerability issues. when apps have no known vulnerabilities, all is fine. when a new "instant root compromise of any system" comes out, its omgomgomg. Then its fixed, and all is fine again.

Except that vulnerability was always there. And other ones that are yet to be public are there too. And many of them are "omgomgomg" material.

Well crypto is the same. We don't have public data on which algorithm are broken. We just know they will be eventually, by logic or by brute force.

So, take the wise decisions, and don't forget you might eventually need to update it.

-----

cheald 759 days ago | link

This is a naive attitude. Mathematically-secure cryptography with an implementation that avoids all side-channel attacks is unbreakable, as in, would take more time than the projected heat death of the universe to brute force.

That's not to say that all implementations are secure, or that there are not undiscovered mathematical flaws in common algorithms, but the idea that all encryption is brute-forcable given enough AWS instances is just plain incorrect.

-----

repsilat 759 days ago | link

> Mathematically-secure cryptography ... is unbreakable

To expand on sibling comments: Cryptography essentially depends on the assumption that P=NP (well, not exactly, but...). It's possible, though unlikely, that mathematical discoveries could undermine all possible conventional cryptographic schemes.

As for brute-force, that's a tricky one as well. If you allow a strengthening of Moore's law that says that operations per second per dollar increase exponentially, then you can construct the following "polynomial time" algorithm for any cryptographic problem:

    Wait n*k years, where
      - n is the problem size in bits, and
      - k is a scaling factor to get the exponents to align
    Buy a computer
    Run the brute force algorithm on your new computer

-----

dekz 759 days ago | link

I don't think I follow your definition of 'Mathematically-secure' is this even an attainable definition? To expect all crypto to be eventually broken is an attitude with foresight.

-----

mikeash 759 days ago | link

How do you know that mathematically-secure cryptography can actually exist?

-----

willvarfar 759 days ago | link

This is not related to password hashing algorithms being discussed here, but:

mathematically-secure cryptography was invented in 1882/1917: http://en.wikipedia.org/wiki/One-time_pad

Fun further reading: http://en.wikipedia.org/wiki/Venona_project

Also, fun reading: The Code Book by Simon Singh, and Spycatcher by Peter Wright

-----

maaku 759 days ago | link

No you were not wrong. That is the correct, conservative attitude to take in most instances.

-----

marshray 759 days ago | link

> By roughly a factor of (5|4000).

Do you have this written up anywhere? Link?

-----

marshray 759 days ago | link

OK, it's in the Scrypt paper. http://www.tarsnap.com/scrypt/scrypt.pdf

Here's my opinion on this:

* These numbers are more appropriately expressed exponentially. I.e. "factor of 5" = 2 bits of security.

* 2 bits of security is not significant at all.

* The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry and it buys you maybe about 12 bits of security against such an attacker.

* For comparison, 128 bits of security is often considered a minimum for resisting offline bruteforce attacks (e.g. AES has a 128 bit key). Of course passwords usually don't come anywhere near close to 128 bits of effective security, so 12 bits might make the difference for some of them if you're lucky.

* In a sense, table 1 in the Scrypt paper shows that the relative difference between the functions is less significant than even relatively small variations in password strength. When the defender has 100ms of CPU to spend authenticating each password, all three functions compared cost less than $200 to break an 8 letter password and more than $150M to break a 10 character password.

* Very few attackers are going to actually spend $M++ trying to break your password (cue XKCD strip). A relevant exception might be botnets, the operators of which don't pay the power bill for their computations.

Therefore, I conclude that for most purposes these functions are mostly equivalent and quality-of-implementation and password strength issues dominate in practice.

-----

cperciva 759 days ago | link

The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry

If your attacker is using GPUs, scrypt probably gives you an even bigger win, due to the compute/memory balance they use.

-----

marshray 759 days ago | link

So I reckon he won't use GPUs then, eh?

Note that the defender pays a cost for this too though. Where he could be happily running PBKDF2 or Bcrypt in multiple Apache process on his multicore servers, Scrypt is going to completely trash the L2/L3 caches and saturate the memory bus and make everything else on the server run like a dog.

Scrypt is operating as designed, of course, but it raises the question of whether or not a defender with a busy website on a farm of multicore servers would be able to configure his work factor as high (in terms of single thread benchmark ms) with Scrypt as he would with Bcrypt or PBKDF2.

-----

moxie 759 days ago | link

I tend to think of this stuff from the cloudcracker.com perspective, which is all about cheap jobs rather than millions spent. I rarely do brute force because, honestly, it's rarely necessary. But the single biggest factor in cloudcracker.com support of a hash format really is its efficiency in GPU space.

For instance, right now I'm implementing support for the modern SHA-512 crypt() variation. It doesn't translate well into GPU space at all, which will end up meaning that I can only offer dictionaries that are half a trillion words smaller than formats which are fast on GPUs.

So far the data I'm seeing indicates that differences of that scale in dictionary size really do make a difference on the success rate of the job. So for what it's worth, from that perspective, it is a factor.

-----

Xylakant 759 days ago | link

I've yet to see a website that get bogged down with authentication request in normal operation, even if those request measure in the multiples of 10ms. The basic idea with all those "slow" password hashes is that authentication is a pretty rare request compared to all other request. Usually authentication requires a single request, at most a handfull. If you run into trouble with bcrypt/scrypt on your webservers, you're doing things wrong. If you have that many authentication requests, direct them to a dedicated server - you'll be in the league that has a large farm running anyways.

Granted, an attacker could use your slow hash for a DOS-attack, but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication.

-----

marshray 759 days ago | link

OK, but what if you're a web app that specializes in authentication (like, say, an Oath provider) or a database server where the attacker-facing app doesn't use connection pooling?

> but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication

Yes, but those things are typically easy to optimize or temporarily disable in a hurry once they come under attack. Not so much with authentication.

-----

moxie 759 days ago | link

Yep, I work close to an extremely high traffic OAuth endpoint. I think scrypt would probably "cost" a lot more in terms of actual servers required to operate it.

-----

cperciva 759 days ago | link

scrypt is tunable; you can make it use as much or as little CPU time as you want. For any particular amount of CPU time, scrypt will give you more security than bcrypt or PBKDF2 would give you for the same amount of CPU time.

-----

marshray 759 days ago | link

Perhaps it's more accurate to measure scrypt in terms of cache misses rather than CPU time? This is a different resource on multicore servers with different performance implications (at least if we're down to counting 3 or 4 bits of security).

-----

Xylakant 759 days ago | link

> OK, but what if you're a web app that specializes in authentication (like, say, an Oath provider)

Then I'd hope that you make extra double sure that your user's passwords are secure. Let's call it the cost of business.

> or a database server where the attacker-facing app doesn't use connection pooling?

We're talking how to store user-passwords here, don't we? If your database server passwords get lost or cracked, change them. Use random-generated passwords, don't reuse them.

>> but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication

> Yes, but those things are typically easy to optimize or temporarily disable in a hurry once they come under attack. Not so much with authentication.

That depends on the website. If your major content is available unauthenticated, then you might as well go and disable authentication. My major point was that you can't defend against a DOS attack by using a weaker password hash, the attacker will just throw more requests at you. In a DOS, the attacker does have the advantage of needing less computational ressources.

-----

marshray 759 days ago | link

The discussion is about best practices and the relative merits of password hashing functions. So the baseline assumption is that the server-side password database isn't perfectly secure.

In practice, the user gets to choose the password and the website at best gets to veto it or accept it without knowing how many other places it's re-used. There aren't too many sites assigning randomly generated passwords right now, I wish there were more.

Yes, some DoS attackers may be able to throw more and more resources at you until you go down. But some don't and you don't have to make it easy for them by preemptively DoSing yourself with too much password hashing! Alternatively: for some fixed amount of attacker DoS resources, your system can support a certain amount of password hash cracking resistance. Cracking resistance is thus a tradeoff with DoS resistance. The root cause of this situation is the poor entropy present in many users' choice of passwords.

Turning off authentication is generally not an option if your site has any data worth securing. If it were, an attacker could bypass your access controls by simply DoSing you until you disabled authentication.

-----

Xylakant 758 days ago | link

> The discussion is about best practices and the relative merits of password hashing functions. So the baseline assumption is that the server-side password database isn't perfectly secure.

That's right. So I don't see where database connection pooling is part of the issue and that's what my remark about random generated passwords was pointed at. You should use secure passwords to authenticate your app at the database. You should probably use md5 [1] or similar as password hashing scheme for the database credentials since this is where you really have a valid tradeoff between performance and security that allows any attacker to bog down your database. But this issue is not the scope of this discussion.

It's certainly a valid technical concern to not increase your password hashing work factor to a point where this it is a valid attack vector for DoS attacks, my point simply is that you can go quite far in terms of work factor until you reach that limit. Increasing the work-factor to a point where authentication takes 10ms will in many cases still leave other parts of your application more vulnerable.

And well, turning off authentication should imply denying access to data that requires authentication. This certainly is an option if the majority of your data is available for unauthenticated users. It certainly is not if you only store data worth securing.

[1] as postgres and mysql both do

-----

sirclueless 759 days ago | link

I thought the definition of "better" in this case is that it requires less work to get the same computational strength with scrypt. Are you saying that the memory locality issues that scrypt causes more than cancel out the computational win?

-----

marshray 759 days ago | link

In this context, work is computational strength so what we're mainly concerned about is an attacker finding a way to do the task significantly more efficiently than the defender. E.g., if the attacker can evaluate the function with half the cost on his power bill relative to the defender, then that can be thought of as knocking off 1 bit of security off the top.

The primary advantage of Scrypt over the others is that it enters a completely pathological memory locality access pattern and stays there for almost the whole function. This works to neutralize the advantage of an attacker who has a custom CPU because he probably can't also develop a custom RAM subsystem to feed it with (at least not one that's many times more efficient than what the defender has in his server).

But if you've done any performance tuning on multithreaded code, you know that cache effects caused by memory access patterns very quickly begin to dominate as multiple cores and threads are added. Things that look great in single-threaded benchmarks almost never scale linearly and there's probably nothing that will scale worse on our shared-memory multiprocessors than Scrypt. It's a feature.

So the defender (say, a busy website with commodity multicore servers) with Scrypt is likely not going to be able to take as good an advantage of his hardware. He won't be able to crank up the work factor quite as high as he could with Bcrypt or PBKDF2.

This may represent an advantage to the attacker, who doesn't have the additional constraint of keeping the response time up on a busy webserver. This attacker's advantage is probably not significant by cryptographic standards (maybe 2 or 3 bits of security lost), but pathological multithreading could represent a big issue operationally.

I'm honestly not trying to cast FUD on Scrypt here, I think it's the best function. I'm just saying like everything else multithreaded you really need to benchmark it under real-world conditions.

-----

cperciva 759 days ago | link

scrypt's memory access pattern isn't particularly pathological; it's random, sure, but it reads large blocks.

The key issue isn't the design of the RAM subsystem but instead the design of the RAM subsystem -- in particular, making sure the attacker can't "cheat" by using a smaller circuit than the defender.

-----

JoachimSchipper 759 days ago | link

You're right, but don't forget Deep Crack. (FPGA-)hardware-based attacks have only become cheaper since then; I would be surprised if the NSA doesn't have a few arrays.

(Also, 80 bits is usually enough to withstand attack, no?)

-----

marshray 759 days ago | link

Yep. There are off-the-shelf FPGA arrays available. Still, bad guys would probably find it much cheaper to rent botnet time for a $0.02/(host*day) or whatever the going rate is.

A solid 80 bits of security out of any of these functions might turn out to be safe forever. But, in practice, most password databases are going to have some fraction of users choosing passwords straight out of the cracker's dictionary, some fraction that will never ever be cracked, and the smallest fraction being crackable according to the defender's choice of work factor.

-----

JoachimSchipper 759 days ago | link

COPACOBANA cost ~$10 000 and apparently is as fast as 2500 PCs for the DES cracking it's optimized for, so ~$4/PC-work-unit plus insignificant power costs. You'd need to find someone with experience with implementing crypto in hardware, though. On the other hand, botnets risk detection.

(If you're buying in bulk, ASICs are cheaper, but few will be willing to pay for that much cracking power.)

-----

mukyu 759 days ago | link

http://events.ccc.de/congress/2010/Fahrplan/events/4203.en.h...

precis: exhaustive search on DES for $1000 in FPGAs from eBay, 2 years ago

DES is in the range of 'costs less than a new phone/iPad' to do an exhaustive search at this point

-----

marshray 759 days ago | link

Yeah, I suspect it depends on your bad guys (er, sorry, "threat model") whether or not they feel more comfortable trying to buy botnet time or acquire $10,000 worth of FPGAs in an untraceable way.

If I were a bad guy, I would prefer to not have a password-cracking special-purpose supercomputer in my possession. (But I'm not a bad guy, and in fact I would love to have a few around the house. :-)

-----

dhimes 759 days ago | link

There are a couple of links on this page:

http://www.tarsnap.com/scrypt.html

-----

haberman 759 days ago | link

> PBKDF2 is worse than bcrypt.

You seem to be speaking only to its compute time -- what do you say to the article's claim that bcrypt has a higher probability of having an unexpected attack that mitigates its computational complexity?

Also, since all of these algorithms have adjustable work factors, what does it even mean to say that one is stronger than another? Couldn't you just calibrate the work factors so that they are equivalently strong? Though naturally scrypt has strength in another dimension also (memory).

-----

tptacek 759 days ago | link

It's nonsensical. It essentially argues that SHA2 is less likely to have cryptographic results relevant to hashing in the next 5 years than Blowfish. It's also an argument the post doesn't support with any actual evidence.

But that's not my issue with the article. My issue with the article is that it takes a simple security issue with no "real" wrong answers and turns it into a tribal conflict, which has the net effect of reducing the number of people who will use adaptive hashing at all.

I'm familiar with Tony Arcieri's work and generally think highly of him; this article, though, is inexplicable and smacks of hipsterism. "I liked Nirvana but then they got popular and sold out, so now I listen to Sleater Kinney". Well, that's going to sound dumb in 10 years.

Let me say yet again that if you use PBKDF2, bcrypt, or scrypt, you are going to look smarter than the average webdev, no matter which one you pick. Do whichever is easiest.

-----

bascule 759 days ago | link

I fully admit the title is linkbait. My goal was to get people interested in the alternatives to bcrypt.

-----

JoachimSchipper 759 days ago | link

Why? "Use bcrypt" is boring from a crypto-nerd point of view, but it's a really useful meme.

-----

bascule 759 days ago | link

I thought I explained that in my blog post. scrypt is superior to bcrypt in every regard.

At the very least, I'd rather the meme be: Use bcrypt, scrypt, or PBKDF2.

-----

tptacek 759 days ago | link

The problem is that PBKDF2 isn't superior to bcrypt in every regard:

* It has marginally worse library support and is built out of universally available primitives, which increases the odds that generalist devs will DIY it.

* It is actually faster than bcrypt (see Colin's paper); in other words, even without waiting for a hypothetical research result against bcrypt, PBKDF2 is already "vulnerable".

* PBKDF2 deployments virtually all use SHA2 as their PRF, and PBKDF2/SHA2 is a construction that depends entirely on the security of hash functions; hash functions are more poorly studied than block ciphers.

* Attacker tools are (mostly, but not entirely) built out of preexisting infrastructure and not by cryptographers; of the three functions, the best accelerated brute force support is available for PBKDF2/SHA2. For instance, is there a widely-available GPU implementation of bcrypt?

* The standards process that ran for PBKDF2 did not include the extensive peer review that (say) AES went through, and isn't a significant asset for PBKDF2. Meanwhile, bcrypt had broad deployment long before PBKDF2 was widely deployed, and on higher-value target systems.

You'd rather the meme be "Use bcrypt, scrypt, or PBKDF2". I'm fine with that meme! But that's not what you said. You said "please don't use bcrypt".

PBKDF2 isn't bad. It has one significant asset: you can point to a PKCS standard to convince pointy-haired product managers to accept it into systems. But given the choice between an HN cargo cult and "technology made palatable to enterprise-grade engineering managers", I'll take the cargo cult in this instance.

(Another strength of PBKDF2 that it shares with scrypt but not bcrypt: you can use it as a proper KDF for your AES keys... but note that if you need to generate your own AES keys, you're very likely in trouble for other reasons).

-----

JoachimSchipper 759 days ago | link

I agree, but:

> PBKDF2 deployments virtually all use SHA2 as their PRF, and PBKDF2/SHA2 is a construction that depends entirely on the security of hash functions

A quick look at Wikipedia (and my own recollection) suggests that it may be more commonly used with HMAC-SHA2. Although the HMAC construction is not provably secure [1] and poorly understood, it seems to be fairly resistant to attack (e.g. HMAC-MD5 is not known to be broken, AFAIK.) Also, iterated hashes are much harder to break than single hashes.

[1] Bellare has a result based on a nonstandard but not entirely implausible assumption about the underlying hash function, IIRC. But, as you point out, hash functions are poorly understood...

-----

tptacek 759 days ago | link

You're right, but the kinds of research results that would accelerate a brute force PBKDF2/HMAC-SHA2 cracker are a superset of the results that would jeopardize HMAC-SHA2 as a MAC. Not to downplay it (it's very important that you get HMAC right) but HMAC-SHA2 is just double-applying SHA2.

I was imprecise, but my point is just, PBKDF2/xSHAx is a construction that relies entirely on the properties of cryptographic hash algorithms; scrypt and bcrypt rely instead on properties of ciphers.

-----

marshray 759 days ago | link

Except that SHA-1 and SHA-2 are constructed from a block cipher too.

"SHACAL". Look it up! ;-)

-----

drivebyacct2 759 days ago | link

Which is fine, but you've clearly dressed it up as flamebait "don't use bcrypt" outright.

-----

bdhe 759 days ago | link

PBKDF2 is worse than bcrypt.

Can you elaborate a little bit on this? Or point to a reference. Wikipedia mentions that PBKDF2 is easier to implement with ASICs or GPUs. Is that the primary reason?

-----

j_baker 759 days ago | link

How does one stay up-to-date on this stuff? Or is it just something that's easier to remember for someone who specializes in security?

-----

tptacek 759 days ago | link

bcrypt is something like a decade old. You don't have to stay up-to-date on it. The vulnerability that bcrypt accounts for dates back to 1972.

All you have to do is not design your own password hashes with SHA-2 (or Whirlpool or CubeHash or whatever some random Stack Overflow answer says you should use). You can safely keep PBKDF2, bcrypt, and scrypt in your bag of tools --- of those, only scrypt is recent --- and reach for whichever one is easiest.

-----

bascule 759 days ago | link

I can't speak for other platforms, but at least as far as Ruby goes:

    $ gem install scrypt
    Building native extensions.  This could take a while...
    Successfully installed scrypt-1.0.3
    1 gem installed

-----

tptacek 759 days ago | link

You can't go wrong with Ruby scrypt.

But then, unless you give up and don't use any of the three, you can't go wrong with any of these constructions.

-----

Xylakant 759 days ago | link

Still I'd stick with bcrypt for ruby. It's in ActiveModel, so it's in Rails. It's in Authlogic. It's the default password storage in Datamapper. I can just point my fellow developer towards the documentation and say "use bcrypt" and be reasonably sure that a basically competent developer will get it right. That's a good thing in my book. Neither scrypt or PBKDF2 have that level of integration so far. When that changes, I'll reevaluate my decision.

Still, it's certainly good to keep in mind that there are alternatives, usage profiles and requirements differ and so do the solutions.

-----

nextparadigms 759 days ago | link

Isn't that a self-fulfilling prophecy? If you buying into the "just use bcrypt" idea, how will scrypt ever change the fact that it's not widely available on the web?

-----

tptacek 759 days ago | link

I addressed this directly downthread. I don't care whether TweetYourCatFood.com uses bcrypt. Specifically, I care that:

* It's got a reliable Gem for Ruby

* It's got a reliable easy_install package for Python

* It's got a good reliable CPAN entry for Perl

* It's got a Java jar file from a reputable source

* It's got a .NET assembly from a reputable source

And what I'm saying is not that scrypt will be "safe to use" when that happens. scrypt is safe to use now; safer, marginally, than bcrypt. What I'm saying is that when that set of things happens, I will personally stop recommending bcrypt and start recommending scrypt. And I only point that out because I always feel a little bad about not recommending scrypt, which is strictly speaking better than bcrypt.

-----

cperciva 759 days ago | link

> While scrypt's cryptographic soundness, like bcrypt's, is poorly researched

I think we may have different notions of what "poorly researched" means.

-----

zheng 759 days ago | link

I think he meant it hasn't undergone the same level of public scrutiny. You've certainly spent ample time researching it, and it's obviously been tested, but possibly not as much something like AES.

-----

cperciva 759 days ago | link

OK, but PBKDF2 hasn't had very much scrutiny either. The entire field of key derivation functions has been very much neglected.

-----

tptacek 759 days ago | link

bcrypt is better tested than PBKDF2: far more publicly "testable" systems use it (bcrypt was the password file format for OpenBSD).

-----

there 759 days ago | link

was?

-----

tptacek 759 days ago | link

In the sense of "that's where it came from".

-----

More



Lists | RSS | Bookmarklet | Guidelines | FAQ | DMCA | News News | Feature Requests | Bugs | Y Combinator | Apply | Library

Search: