I disagree wholeheartedly. The article is based around the fallacy we've seen time and time again, of throwing more cryptography at a problem that cryptography alone cannot solve. In the end, a crappy password is a crappy password. Successfully discouraging your users from using a crappy password has much better repercussions (for the user, for you, and for the web in general) than switching from a hash-based authentication system to bcrypt. Use bcrypt for additional security, but do not use it in an attempt to solve the problem of crappy passwords that the article falsely claims bcrypt solves.
To be more technical, bcrypt, like PBKDF2 and other schemes of that nature, add a significant amount of additional computation by iteratively applying a primitive, but still maintain a relatively small circuit size (in comparison to the primitive itself, which is usually designed to fit onto smart cards and the like). Creating and using algorithms which are "memory-hard" or require larger circuits reduces the number of circuits one can place on some area of silicon and drives up the cost of an attack. In other words, mounting an attack on bcrypt or PBKDF2 is still cheaper and potentially much faster than we'd like it to be (which is the reason those algorithms are "tunable"--you scale the number of iterations up as computers become faster). This, along with some example memory-hard functions was the topic of Percival's paper, "Stronger Key Derivation via Sequential Memory-Hard Functions," which correctly cites Bernstein as the source of emphasis on practicality in measuring an attack not by computational complexity, but the cost of launching the attack. See http://www.bsdcan.org/2009/schedule/attachments/87_scrypt.pd... if you're interested in reading further.
The mistake you're making is thinking of bcrypt as a protection for end-users and their passwords.
It isn't. Bcrypt exists to protect application developers.
A user with a crappy password is getting his account busted one way or another. You're right to point that out. Cryptography won't solve that problem.
The problem crypto solves is this: a crappy web app that loses its user table is royally screwed if its devs settled for "salted hashes". At the whim of their attackers, hundreds or thousands of their user's passwords are going to hit Rapidshare. That's what the devs will be famous for.
Bcrypt keeps that from happening. You'll get famous behind losing 1000 passwords. You won't get famous behind losing 20.
A poorly-written web app whose SQL database is compromised has bigger problems than protecting the integrity of poorly chosen passwords (especially if they store financial information).
Losing such a collection of salted hashes does not render one "royally screwed." Those hashes (or HMACs) are still cryptographically secure, which means it's computationally infeasible to find a first preimage provided the password doesn't suck. You seem to think (or are at least implying) that bcrypt is impervious to standard iterative bruteforce attacks, but that's just not the case. Much like PBKDF2, and other iterative hashing techniques, bcrypt is more resistant, but still "vulnerable" to such an "attack." bcrypt's main advantage over other iterative techniques, in my opinion, is the 4KiB of s-boxes used by Blowfish.
A poorly-written web app whose SQL database is compromised has bigger problems than protecting the integrity of poorly chosen passwords (especially if they store financial information).
Are you suggesting that because a comprise is bad, nothing should be done to reduce the magnitude of the impact? This argument does not hold up in general, and it is especially weak when arguing about using encryption algorithms with freely available, high quality implementations. The developer effort required to use bcrypt is minimal.
Also, you seem to be making the incorrect assumption that only poorly written web applications get their databases compromised. Web applications with excellent security get their databases stolen for a variety of other reasons. Even if the programmers do everything right, a careless employee might get his/her password sniffed or stolen by a key logger. If a company uses external hosting, its database could get stolen because of a mistake by the hosting providers.
In summary, the risk of your database being stolen is always present, regardless of the diligence of the the programmers who implemented the web application. The fact that a compromise is bad is not justification for ignoring simple security measures that take minimal effort to implement.
The effort required to implement bcrypt in new systems is indeed small, and such a method is the suggested way to do, but depending on the amount of users, the effort required to port an existing database over to bcrypt (e.g., Facebook) could be immense, and the result disastrous if not done with great care.
Ptacek said, and I quote, "... a crappy web app ..." so why do you only cite me as making the "incorrect assumption that only poorly written web apps have their databases compromised?"
Again, I agree that is the case in new systems, but I disagree that one is "effed," as the article puts it, if they have a large database of salted hashes.
I should have been more precise in the article. Here:
A system which uses an adaptive hash function like bcrypt is ~6 orders of magnitude less effed in the event of a compromised database than a system which uses a standard hash algorithm and a salt, ceteris paribus.
I would hope you agree that those ~6 orders of magnitude could well be the difference between "not noticeably effed" and "profoundly effed."
He's implying that using bcrypt (and other iterative hash functions like PBKDF2 and scrypt) raises the cost of mounting a dictionary attack compared to commonly-used and -recommended hash algorithms like SHA256.
Losing a Unix password file in the 1990s would have been newsworthy. Password files were "secured" using Unix crypt(3), an algorithm that at least made a nod towards resisting brute force attacks --- so much so that when PHK wrote FreeBSD's md5 scheme, he iterated it PBKDF-style, because even then it was clear that using cryptographic hashes "straight" was a bad idea.
The biggest differences between Mindvox losing it's password file in 1995 and a webapp losing its user table in 2010 are:
* Web apps are getting fielded with straight SHA1 hashes, which is inferior even to FreeBSD's original MD5 hash scheme.
* Brute force attacks have gotten much faster.
The main advantage to bcrypt over, say, AES, is that the key setup is really slow. Mazieres spotted a weakness in Blowfish and turned it into a benefit.
Is there some real argument you have with me? I agree: if you lose your user table, you have real problems apart from losing password hashes --- though we could bicker about which of those problems is worse. Where are you disagreeing with me?
I never said SHA-1, a cryptographically insecure hash, was a good choice. It's important to note in your differences that, for the most part, cryptographic hash functions in current use have gotten much slower (e.g., SHA-256 vs MD5), but are also getting much better (SHA-3 competition).
The argument I have is this: The passwords that are going to be hitting Rapidshare in your scenario are the crappy or short ones, whether you use bcrypt, scrypt, PBKDF2, salted hashes or HMAC. Encourage them to use bcrypt or some other iterative technique for the security benefits, but don't exaggerate and tell them that they're "effed" if they have salted hashes. They're still a long way away from storing passwords in plaintext.
You're arguing for the sake of arguing. The developing weaknesses in SHA-1 don't make it a poor password hash. That's an irrelevant factoid you threw in to cloud the argument.
Pick a number of passwords to lose from a table. Hash them with any of the SHA-3 contestants and a "salt": you will lose more. Hash them with bcrypt, you will lose less.
Again I'm left asking you: what's your point? What are you trying to prove? That you know that there's a SHA-3 contest? You haven't refuted anything this article says; in fact, you keep accidentally managing to validate it.
I'm not "arguing for the sake of arguing." I'm trying to explain my point to you, and I'm doing so in a polite manner, which is exactly what I'd expect from you.
The weaknesses in SHA-1 make it a poor cryptographic hash, which make it a poor pseudorandom function, which has a significant potential to make it a poor password hash.
My point, for the second time, is that you're not "effed" if you use salted hashes.
I'm not trying to "prove" anything. I'm stating my opinion on the matter. This isn't a pissing contest, rather, a forum for discussion.
All public results against SHA-1 are collision attacks. Password hashing doesn't rely on collision-resistance, only one-wayness. Not even MD5 has any published preimage attacks against it. The known weaknesses in these functions have nothing to do with why they're poor choices for password storage.
I'd like you to explain how you'd exploit a problem with SHA-1, or, to make it more interesting, MD5 or MD4, to attack a "typical" hashed password (say, Keychain.app "memorable") more quickly than via iterated brute force.
Currently such attacks are infeasible, but there are some very interesting, and very promising families of collision-based attacks (such as herding) which may yield results in that area, although such attacks may only work in specific cases.
Uh. All of the current SHA-3 candidates are as fast or faster than SHA-1. That's one of the contest's design goals:
NIST expects SHA–3 to have a security strength that is at least as good as the hash algorithms currently specified in FIPS 180–2, and that this security strength will be achieved with significantly improved efficiency.
Yes, that's why I specifically said, "in current use." No one should be using SHA-3 hash functions. SHA-256 and SHA-1 are much slower than MD5 and very much slower than MD4. The "Getting much better" comment was in reference to speed improvements as well as security improvements (such as removal of vulnerability to length-extension attacks).
Also, you point out that "successfully discouraging your users from using a crappy password has much better repercussions." This is true, and I'm curious to know how you personally achieve this with your users, given that the vast majority[1] of users choose spectacularly crap passwords.
I'm familiar with cperciva's scrypt, and I think it's a great solution. That said, I've only seen C and Ruby bindings for it.
I'd love to recommend its use over bcrypt, as memory constraints are much more expensive than computational constraints, but recommending something most developers don't have access to would result in more weak hashing schemes in production.
In any language with sane FFI, scrypt is pretty easy to write new bindings for. At my previous job I wrote a complete scrypt plugin for Openfire in a weekend, and only a couple hours of that was for writing the JNI bindings.
I'm no cryptographer, so maybe this is a silly question... Any reason why I shouldn't just reimplement it in the high level language of my choice and release it open source?
You're talking about a completely different problem.
Yes, many users pick crappy passwords. That's a social problem, one that is difficult to address with technology[1].
Storing passwords on the server is unrelated to whether or not the user picked a good password. If an attacker gets ahold of a copy of your database, they will have a much easier time of turning SHA1 hashes of passwords into actual passwords than of turning bcrypt-encrypted passwords into actual passwords (the latter being orders of magnitude more difficult, maybe to the point of being impractical as a target vector).
[1] You can always do things like require certain types of password complexity: minimum length, choice of characters from different character classes and cases, etc. But then you end up just moving the problem elsewhere: instead of using the crappy password they remember, the user has to write down their complex password, or maybe even store it in a text file on their hard drive.
The bruteforce attack described in the article primarily affects short and dictionary-based passwords. If the password is of sufficient length and complexity (the keyspace is large enough), then bruteforcing becomes computationally infeasible. What the article proposes is, essentially, to use a more computationally expensive algorithm for the benefit of protecting shorter, weaker, passwords. I disagree, and think that increasing the computational cost of the algorithm itself should be used to enhance the security of passwords, rather than having their security depend entirely on that increased cost.
Good passwords stored as a salted hash, or preferably, as an HMAC, are in no way insecure. I feel that implying otherwise is a disservice.
You sound like someone who has never run John the Ripper.
There clearly are passwords that are impractical to crack. To get one, just "head /dev/random | openssl sha1".
Nobody uses passwords like that. They're irrelevant. Instead, the smart ones use passwords that contain a combination of words, numbers, and punctuation. John the Ripper has been cracking those passwords for over a decade.
"Salted hashes" are insecure. They'd have been rejected by the FreeBSD team in 1997. If you choose to make a religion out of not using bcrypt, do what the RFC says and use PBKDF.
But wait. What if I use a 64 bit salt and then AES-encrypt the password with a key I store half on my server and half in a cookie I send to the user and then they'd have to break AES to get my passwords? How about that, Coda Hale?
Using a new and unproven hashing primitive to add a constant factor is much more secure than encrypting with a reliable, heavily researched protocol because __________________
Only experts should be allowed to innovate in the security domain. Passwords on lolcats are serious business!
We certainly don't want people in the software engineering industry to come up with new ideas, implement them, and see how they work in real life. That could lead to advancement in the field, and that would be bad, because I might have to learn something new. Shudder.
For a significant portion of users, the lolcats password is equivalent to the gmail password, which is game over. But don't let that get in the way of your learning experience, which is simply going to converge on bcrypt anyways.
Unlike most areas of software design, security is adversarial. If you innovate, you are betting your users' privacy on you personally being able to stay ahead of every attackers' ability to find flaws. This becomes unethical if you aren't even familiar with the current state of the art, because some attackers surely are.
I am a crypto noob, so please excuse me if I sound stupid. But why not force your users to pick a password that is at least 8 characters and contains at least one digit, one capitalized letter, one lowercase letter and one special character, then gen a 16-byte salt and run it through SHA-512? The examples given in the article are for 6 lowercase alpha-only characters, which has always been relatively trivial to crack.
I acknowledge that bcrypt seems like a simple safeguard against password attacks, but I don't doubt a hacker's ingenuity in developing a method to make attacks against it reasonable - especially if it becomes widely adopted. And I think once you've lost your password database you're already completely fucked, in one way or another.
Once you go down the road of "not doubting a hacker's ingenuity", you might as well give up and stop applying OS patches. In any case, with "16 byte salts and SHA-512", you're pitting hackers against the folk wisdom of PHP developers. With bcrypt, you're pitting hackers against the IACR. You can't know everything, but you can pick the right battles.
Folk wisdom of PHP developers? I think the creators of crypt() are probably smarter than this.
Password hashes are part of a way to mitigate a particular situation: deciphering a login credential when the password database has been exposed. Shadow files are locked down to root-only because you should never trust people with your password hashes. If somebody has the hash, it's just a matter of time. I don't assume time is on my side.
If bcrypt() somehow makes it near-impossible to brute force password hashes in a "reasonable amount of time", we'd no longer need our shadow files to be root-only. We could give our bcrypt hashes out to the world and say, "Ha! TRY to crack this!" But you don't do that. Because you know deep down in your heart, once that hash is out in the open, the game is over. It's possible someone will crack it so you cannot trust it.
And if someone got access to your locked-down password database, someone is deep enough in your system to have at least read-only access to your password database. Whether or not they can decode the password they probably have other ways of getting whatever it is they really want, which is rarely just an account credential.
I will, however, agree that bcrypt appears to buy you much more time in the event that your password database is exposed. I am skeptical of how much more time that would be under the right circumstances, though, and the potential consequences of CPU exhaustion in the event of some kind of small DoS on the authentication layer.
Also: can you please comment on the original point of my post, which was using a complex password in addition to a fast salted hash? When compared to bcrypt and its purpose/results, is this still an inadequate technical solution, and why?
(edited to make 3rd paragraph not retarded and add request for clarification)
You're asking about the relative merit of two hash functions, one of which allows your attacker to test a candidate password in 1 millisecond, the other of which allows the same in less than 1 nanosecond. Using the latter provides your attacker with a 1,000,000x productivity boost. Personally, I'm not that generous.
As far as CPU exhaustion, there are some huge sites which use bcrypt (like, in the top 10)[1]. It is not a problem, provided you choose your work factor carefully.
As far as complex passwords, use them. Try to get your users to use them. But it's an orthogonal concern: your attacker will still be able to work their way through the gigantic keyspace of your monster passwords at 1,000,000x the rate of what they could do if you'd have used bcrypt.
[1] Just looked this up. Not the top 10, but the top 15 for sure.
If you controlled the passwords your users chose, you might be in a position to talk about "strong passwords" combining with "salted hashes" to make a reasonable solution.
Here's a bcrypt hash. Crack it, and I'll donate $200 to the charity of your choice. It's not random, and the cost factor on the hash is not high.
I'll forgo a mathematical argument in favor of a practical one. If you have a choice between offloading complexity to your users or your developers, you should choose your developers every time. Rather that requiring complex password schemes from your users, have your developers use a slow hashing algorithm instead.
So say we tone it down to a more feasible 0.01 seconds per hash, or to put it another way, 100 requests per second. That's only 4.8 months to crack that password. There'll certainly be future hardware advances, plus GPUs could be used to bring that down. And you can be sure someone used "password" or "123456".
Moral of the story: use long and multiple passwords.
I'm sorry if I'm completely misunderstanding, but couldn't a hacker generate a rainbow table once - of all the common passwords, say - and then, once they get a copy of the database in which the password hashes are stored, simply compare them? In the same way that md5 rainbow tables exist, which greatly reduce the computations required when looking for passwords?
Unless, of course, you salt them (which would turn it into 4.8 months to break all the common passwords in a table, building a rainbow table with the salt taken in mind - the only situation in which you're spending 4.8 months per user is if they're each salted differently, for example with the username)- but the article doesn't suggest salting bcrypt, so I'm ignoring that.
Complete noob. Can you explain this more. if you bcrypt(12345) isn't the result always same ? If the hash varies then what does the inbuilt nonce depend on ?
Despite the pages and pages and pages and pages of conversation about how to select and format "salts", adding random nonces to hashes is not one of the world's great CS problems.
I don't understand it still. The cost factor and the string remains the same but different hashes are produced. So if a user inputs "hi,mom" and the app generates a hash, how is it going to be the same as the one in DB ?
Or did you make a mistake and the cost factors are supposed to different ?
I haven't seen this link on this thread yet so here we go:
http://people.redhat.com/drepper/sha-crypt.html
Ulrich Drepper's implementation of a work factor in SHA password hashing. He addresses a popular article on bcrypt() and how using SHA allows one to follow NIST guidelines and still have the advantage of a time-consuming algorithm.
me@myhost ~/ :) time perl -le'print crypt("some-password","\$6\$rounds=900000\$myrandomsalt")'
$6$rounds=900000$myrandomsalt$O4u/Z5FRNBi3fw6YhAM1V1hC1LAawq9Ri65Kx77GchzOWieXeRs6w83bYqotyqBcz.WE29NygNli93dBDAbpt/
real 0m3.996s
user 0m3.990s
sys 0m0.005s
If someone could comment on this in comparison to bcrypt I would appreciate it. Why should we use bcrypt if this exists in modern crypt() implementations?
A nice post, but it could use some more explanation about designing password hashes.
For example salt + iterative hash works extremely well too, that's what is done in the OpenPGP format (http://www.ietf.org/rfc/rfc4880.txt - 3.7.1.3 Iterated and Salted S2K).
We implemented http digest authentication (http://en.wikipedia.org/wiki/Digest_access_authentication) in our application for the following reasons:
- We needed to securely authenticate users connecting with browsers and rss readers without ssl.
- We needed an encryption algo that we could implement in javascript so as to provide reasonably secure login without ssl.
Is there any way to do the above while storing bcrypt passwords on the server? Does using bcrypt in these scenarios force you to use https and pass full text passwords to the server?
Presumably, bcrypt is something that has been vetted by crypto experts, whereas your idea is just some random thing you thought up. Maybe you personally are a crypto expert and know for a fact that your plan will work, but the vast majority of people aren't. A packaged solution like bcrypt that doesn't give the developer enough rope to hang themselves (and their users) is a much better idea.
and just be done with it, rather than having to decide between ROT13 (kidding), hashing, salted hashing, HMAC, etc. A couple years ago I thought applying SHA1 to a password before storing it in the DB was perfectly fine. Later I discovered that it was better to use a salt. More recently I've discovered that both of those approaches are flawed. Fortunately I've never written a large-scale application that deals with storing passwords, but I'm sure there are many application developers like me who would write much safer password storage routines if they didn't have to be the one to select an algorithm.
Now, I'm not saying bcrypt is the answer (I know nothing about it beyond what I've read on HN), but that's the general problem with your hypothetical proposal.
whereas your idea is just some random thing you thought up
He might also have got the idea from one of tptacek's suggestions not long ago.
The difference between doing the iterations and bcrypt is.. well.. not massive in a practical sense. You could do either (if your already MD5'ing passwords once [hmmmm], for example, then it is a quicker solution)
There's a difference: bcrypt (and moreso scrypt) were designed to be hard to speed up, while SHA1 was designed at least in part to be easy to speed up.
But in practical terms, "stretched" SHA1 is fine. I won't bitch at anyone for using it.
Nothing enormous; that's basically what PBKDF1 does. cperciva might correct me on this, but IIRC there are some minor concerns, addressed by PBKDF2, which is a slightly more complicated construction, about the iterated hash function degenerating into cycles. I don't think there have ever been any practical results exploiting this. PBKDF2 is just as good a choice as bcrypt, and a better-supported one.
bcrypt has a slight advantage over PBKDF2 in that it requires a larger ASIC area. It's only a constant factor better than PBKDF2, but making an attack 5x more expensive is still somewhat useful.
The problem with using a scheme designed to be computationally intensive is that it doesn't scale. How can I justify 0.3 seconds of computation time if I'm dealing with tens of thousands of connections per second?
First, tens of thousands of connections per second boils down to orders of magnitude fewer logins. In a typical modern web app, plenty of entire sessions are completed off a stored session token and never touch the login code.
Second, plenty of apps that are far bigger than yours have scaled bcrypt without event. 37signals is a public example. Other larger apps are using it without talking about it.
Third, in the spectacularly unlikely event that password hashing became a scalability obstacle, it's pure compute and scales horizontally without a problem. Note: I've never heard of someone having to do this.
Finally, the whole point of bcrypt is that it's tuneable. You dial it up to your pain threshold, and in the process cripple brute force attackers.
If those tens of thousands of connections per second are tens of thousands on logins, per second, then the computational value of your hash function seems likely to be the least of your problems :)
In this case, it does. If the client's job is to hash the password then send it to the server for comparison, you've basically got plaintext passwords. They may be quite long, but we're at that place where things don't scale anymore.
Derive a 256-bit key from your password, then send that 256-bit key to the server. Nobody is ever going to perform a brute-force search against the 256-bit derived keyspace, so any attack will need to run the KDF against a list of likely passwords in order to get a list of likely keys.
I am perfectly willing to stake FreeBSD's security on the belief that nobody will ever perform a brute-force search against a 256-bit keyspace.
For that matter, Microsoft, Apple, RedHat, Debian, and Ubuntu all make the same or (usually) even weaker assumptions in their respective packaging and/or updating systems.
HTTP Digest support pretty much requires you to hash passwords using MD5(salt:password), if there’s a way to support HTTP Digest while storing bcrypt hashed passwords I’d love to know.
Why do we care about HTTP Digest? It provides a standard technique to avoid sending clear passwords from client to server. This is particularly handy when the client server communication isn’t encrypted (a poor man’s SSL if you will), but sounds like a good idea in general.
In principle you could create a variant of HTTP Digest using bcrypt instead of MD5 however you’d break browser and rss reader compatibility and AFAIK there are currently no javascript bcrypt implementations.
Hence I’m guessing that web apps storing bcrypt hashed passwords are forced to send clear-ish passwords from client to server and therefore must rely on the presence of an ssl/https connection.
Obviously ssl should be used whenever possible, but I wonder to what extent sending clear passwords doesn’t create other forms of vulnerability?
It probably still makes sense to salt before hashing. It might take months to crack a password using bcrypt, but is there something preventing a database of bcrypt hashes being built? (serious question)
The article is using a definition of "store" of which I was previously unaware. If you'd like to store passwords (eg, in a keyring or password manager), use GPG.
The article is talking about the problem of storing passwords in a database in order to authenticate logins. This is for people writing web-apps, not users looking to secure their own passwords.
The passwords aren't being stored, though; a value derived from them is. In a properly designed system, it is computationally infeasible for an attacker to obtain the original password given the derived value.
Proper design of such a system is the subject of the post. If you're a developer who doesn't want to think about the design of such systems, that's fantastic! Just use bcrypt.
from the bcrypt page: the other [bit of terrible advice] recommends reversible encryption, which is rarely needed and should only be used as a last resort.
Why is reversible encryption a terrible idea for passwords?
Because it means with <single piece of secret info>, your entire customer base's worth of passwords is now decrypted.
You've now gone from "Even if we get attacked, we've chosen a provably difficult / secure storage method. The damage should be negligible." to "If we get attacked - I hope like hell they don't get <single piece of secret info>."
An attack is an attack. If they can get in and steal your password database, what's to say that they can't get access to the key that decrypts your reversible database?
In other words, the information needed to extract the true raw-text password is actually included in the encrypted string.
With a hash, only a representation of the raw-text is being stored. Even if you knew exactly what was done to create that representation, you're still a long way off from understanding the raw-text.
If you treat both the key and the salt as being "known to the developer only" and either of these becomes compromised, you still don't have they raw-text of a hash, but you've got everything you need for the encrypted.
Is that it? bcrypt is good only because it is slow? In that case, why don't we use whatever we like (MD5, SHA1, SHA256, SHA512, SHA-3, etc) and add a sleep(500); just before the call? It is guaranteed to keep up with Moore's law as well!
I thought the attack was against the application. The article talks about the security of the raw data in the database. I missed that on my first read. Sorry for that.
I really don't want to use this word, but this is retarded. Something like RFC 2898 would be a good starting point for explaining why. http://www.ietf.org/rfc/rfc2898.txt
I'm guessing you haven't read Provos and Mazières' USENIX paper. In the design considerations, they say:
In general, a password algorithm, whatever its cost, should execute with near optimal efficiency in any setting in which it sees legitimate use, while offering little opportunity for speedup in other contexts.
PBKDF1 and PBKDF2 both rely upon general-purpose hash functions, which are much faster in dedicated computing environments such as FPGA or GPU clusters. The Eksblowfish algorithm at the heart of bcrypt is extremely resistent to optimization.
This is crucial for password storage, since if a CUDA implementation is 3-4 orders of magnitude faster than the implementation your application uses, you've just chipped off a huge chunk of the advantage offered by your hash function.
What a bizarre comment. PBKDFn and bcrypt are two very similar approaches to the same problem. If you're married to PKCS/IETF standards, go ahead and use PBKDF2. You're still essentially following the advice of this blog post.
To be more technical, bcrypt, like PBKDF2 and other schemes of that nature, add a significant amount of additional computation by iteratively applying a primitive, but still maintain a relatively small circuit size (in comparison to the primitive itself, which is usually designed to fit onto smart cards and the like). Creating and using algorithms which are "memory-hard" or require larger circuits reduces the number of circuits one can place on some area of silicon and drives up the cost of an attack. In other words, mounting an attack on bcrypt or PBKDF2 is still cheaper and potentially much faster than we'd like it to be (which is the reason those algorithms are "tunable"--you scale the number of iterations up as computers become faster). This, along with some example memory-hard functions was the topic of Percival's paper, "Stronger Key Derivation via Sequential Memory-Hard Functions," which correctly cites Bernstein as the source of emphasis on practicality in measuring an attack not by computational complexity, but the cost of launching the attack. See http://www.bsdcan.org/2009/schedule/attachments/87_scrypt.pd... if you're interested in reading further.