It seems like you Ctrl-F'd for bcrypt and didn't read anything else on that page. The part you quoted explains why moving hash checks to the browser is not a practical option. It has nothing to do with storing passwords. Moreover it has nothing to do with actual (complete) password hashes either.
PS I've been dealing extensively with applied cryptography for over 10 years, and I happen to know few things on the subject. Don't assume ignorance by a keyword match.
I don't think using bcrypt for this is feasible in any case. From a UI perspective bcrypt hurts you in the first place, because your feedback is going to take at least a few hundred milliseconds, so you lose the instant feedback that makes this potentially.
From the perspective of the person hosting whatever service is using this there are problems too. The first step from your "How It Works" section is this:
On the server side, it first hashes entered password
the same way it's done when doing regular authentication.
You having 10 years of applied cryptography experience means very little to me. Cryptography is one of those things it's very easy to get wrong even with experience. And getting it wrong has potentially very dangerous consequences.
Surely you must realize that there's more than one way to sort random strings into 2^N buckets.
If you feel like criticizing, go for the general idea. Nitpicking on the implementation details is (to borrow from a comment below) silly.
If you're trying to use maximally secure work factors, bcrypt should take upwards of a second. You'll encourage users to get into the habit of waiting that long before submitting just so they can get the gratification of seeing the design mesh.
If you're using a lower work factor already, it's probably because you need to limit cpu use because your system is popular and is doing lots of authentications. Assuming a minimum password length of 8, you'll be doing an order of magnitude more bcrypt calls for those users who still type in their passwords (and by implementing this, you're encouraging them to keep doing so). How will that work unless you decrease the work factor by a similar amount? If you can afford to be doing more bcrypts, you should be increasing the work factor, not doing stuff like this. Wasn't that his point?
You're waiting for (bcrypt + network latency) in either case. If the standard behavior is unusable (because the auth page reloads if there's an auth error), that's a design problem, to be addressed by not reloading the page on auth errors, not by adding gimmicks IMO.
Furthermore, if you insist on this sort of thing, why not pass back a boolean indicator of whether the full hash matched, and display a checkmark when it's right? You could even automatically log-in the user if it matches. Since you would be doing a full bcrypt each time anyway, in order to do the 8-bit comparison, and you've put limits in place to prevent abuse...
it's better to see confirmation before submitting rather than submit and wait for confirmation doesn't seem to make sense.
Personally I feel less comfortable with an outright rejection ('Username/password is wrong' in bold red) than with a subtle hint that something's not quite right with what I typed. Subconsciously. So I think the addition of a real-time validity hint makes it for a smoother and more pleasurable user experience.
You still end up lagging because of the time it takes to do the hash check, and if I were typing in a password I would hit enter and not wait for either a neat grid or a checkmark. If the password is wrong when the user has voluntarily submitted the form, that's when you break out the red warning, but it shouldn't take any longer to do that than to display a green checkmark. The difference is one requires the user to press enter first, the other doesn't but requires testing every single intermediate stage the password goes through.
Finally, I'm not thrilled with the idea of a page sending incomplete passwords to a server, which may well be compromised, before I press enter. What if someone types the password for another site by accident, but corrects it before pressing enter? I know some sites already do ajaxy stuff with usernames and passwords, but I don't have to be happy about it.
It is possible to look at the sun in a telescope, but only twice in a lifetime :) What you say is possible, but I don't know how to coalesce the need for near real-time response and the resistance to the brute-force attacks. That's unless you are referring to once a second validation, in which case the brute-force is still an issue.
> if I were typing in a password I would hit enter and not wait for either a neat grid or a checkmark
I don't know about you, but I get a feeling that I mistyped a password now and then and sometimes I am actually right. So my options here are to wipe it clean and retype or to somehow check if the password is more or less OK. This is what hinting is for. Also, as I said on the description page, the second use is to quickly cycle through a list of (disposable) passwords to see which one I used on a site.
> Finally, I'm not thrilled with the idea of a page sending incomplete passwords to a server
I hear you, valid point. And don't get me started on a page sending incomplete search queries to the server.
Assume your site allows N 8-bit partial preimage hash checks before a 15 minute lockout. (I would suggest, with 8 char minimum passwords, that you only count passwords that are 8-16 or 8-24 characters long. Otherwise a cat might try to test a several hundred char long password and the user will be locked out. DoS by feline.)
Under your system, seconds per crack attempt is (900/N + 900/5 * N/256). The first term is the number of pseudo-successful attempts with the fast 8-bit check, and the second term is checking those 1/256 passwords using the slow 5-checks-per-15-minute full auth check.
If you allow 40 8-bit checks before a lockout (N=40), you get 50.625 seconds per check.
Allowing full checks at a faster rate of 40 per 15 minutes, the second term disappears and you get to check at 22.5 seconds/check.
Obviously these decrease security, but if you're concerned about one check per 22.5 seconds, or even 1 check per 10 seconds, why would you want to decrease the effective check rate at all, from the nominal 3 minutes per check that's closer to standard? I don't think that going from 50 seconds to 22 seconds is "looking at the sun in a telescope" :)
The 256 hash buckets are going to create collisions. Given 8 char minimums, 7 incomplete passwords will be checked per user. That's at least one collision for an incomplete password per 37 users (7 * 37 > 256).
At least 1 out of 256 users will have the most common mistype of their password also collide with the real hash to 8 bits. Their only option is to change their password.
An attempt to reduce collisions would further decrease the time per cracking attempt, and since rock bottom is 22.5 seconds/request in that example, I don't think that's so horrible a price for a boost in usability, if you're going to implement this sort of password correctness hinting at all.
For example, the stored password hash might be `substr(md5_hex($password), 0, 5)`. More than enough information to tell if you're wrong, but not enough information to tell if you're right.
You can still use bcrypt for authentication if you like.
Probably they consider the toolbar "one of those computer things" and avoid it because they're worried they wouldn't understand it. And if they read it, they might be worried about whether they're really understanding the feature correctly and just ignore it in the end to be safe.
All too often I run into a form that is either not auto-filled or where some javascript magic fails when it's autofilled (e.g. the page claims "password too short" until I fake some keystrokes manually).
Hint: If your login procedure is annoying then I'll come back less often (or not at all) for that reason alone.
Depending on work factors and whatnot, it's now a backend load balancing issue. But it's probably solvable.
If something like this worked, it would provide a method of breaking the hash in a piecemeal fashion, which would mean the hash algorithm never worked properly in the first place.
EDIT: reply to below: The only thing it can tell you is that two passwords don't match. It tells you nothing about whether they're similar. (And also doesn't tell you they do match, for which you need the whole hash.)
What do you mean? They work for my purpose, which is being able to tell "password" and "passwrod" apart. There will be false positives, of course, but an (educated) assumption is that they are not going to be frequent for lexically related inputs.
And for those who don't, this is a real possibility. That said I don't think this would be impossible to use with bcrypt and a reasonable load-factor. JS on a virtual machine is pretty fast these days.