While this is possibly an interesting UI experiment, this paragraph says everything you need to know about real-world use:
Utilizing something like bcrypt as a hash function
is not an option, because the number of rounds needs
to be reasonably low for it to work in real-time in
Javascript.
If you're not using a slow hash function like bcrypt, you're doing password hashing wrong. Your users' passwords are vulnerable to brute-force attacks as soon as your database is compromised. (And "my database will never be compromised" is not a valid response.) Before doing anything with your users' passwords, read this:
http://codahale.com/how-to-safely-store-a-password/
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 normally comment on articles unless I've read them in their entirety, and this was no exception. I've re-read that paragraph in context several times, and I don't think it's entirely clear that you only meant it can't be done browser-side. That paragraph reads to me like you're saying bcrypt can't be used at all.
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.
I'd say this is likely to increase the amount of time you spend hashing by about an order of magnitude. When you're using bcrypt, which takes a lot of computational power, I think that's likely to be significant. Especially because, in this case, you really can't afford to be queuing up requests--if you don't have the computational power to process them immediately, you get even worse at giving instant feedback. And again, that defeats the purpose of having this as a UI feature.
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.
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?
No, I think you're confusing my issues with the ones of the poster to whom that was a reply. My concerns are not so much about security of doing more hashing server side, but rather that you will be burning more cpu to do this cute thing when you could be using that cpu to increase the work factor which users might actually care about. And since modern web auth systems already use ajax to check the password and simply modify the page if the password is wrong, the argument that it's better to see confirmation before submitting rather than submit and wait for confirmation doesn't seem to make sense.
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.
Green check if the password is valid, rather than this grid that's meaningless anyway... all it does is leak (hopefully) useless information about the first n (8?) bits of the bcrypt function. There's no correlation between how close the password is to the stored password, and how close the bcrypt hashes are to each other. You really only care about one thing... does it match or not? And if it does, you might as well check if it matches the full hash and not the first 8 bits... since you'd only be sending back a binary indicator to the client's browser.
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.
> you might as well check if it matches the full hash
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.
Assuming a site that originally allows 5 login attempts and locks for 15 minutes after that, under normal conditions that's an average of 180 seconds per attempt.
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.
I'm pretty sure the "stored password hash" in the article's flow diagram need not be the same as the one which is used for authentication.
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.
I think in that particular section he is referring to the possibility of allowing to client to validate the hash, which would be bad because it opens up the possibility of brute forcing. I don't think he means you shouldn't use bcrypt on the server side.
Furthermore, if someone is using a password manager like they probably should be for most sites (since average people are not going to remember more than a few passwords, and password reuse is bad), there is no benefit to this system.
True, but I think most average people do not use password managers. As far as I remember, IE, Firefox, and Chrome all ask to save passwords using a toolbar that slides in at the top or bottom of the page. All average users I have seen when that toolbar appears have ignored it. (I don't know how people react to Safari's modal dialog box, though.)
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.
Indeed. People should rather review and make sure their registration and login forms work seamlessly with password managers, at least the popular ones (lastpass, 1password, etc).
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.
Hmm... 1,000 clients trying to log in from machines with pretty fast CPUs, and you want to shift this highly compute-intensive, uncacheable, froo-froo-feature support load to the 1/5/10 servers on the backend?
There's no need to derive hinting (reduced) hash from the bcrypt hash of the password. Since all that's needed is even distribution of password space into 2^N classes, it can easily be done by looking at N bits of any password hash. Since N is low, even something like a now-obsolete MD5 would work.
But these "classes" have no meaning. The only thing that means anything is whether the entire hash matches or not. Comparing a subset of bits just gives you random results, (aside from the case where the entire original hash matches).
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.
Get of your high horse. Yes theoretically you should use bcrypt. Just as you should exercise and eat healthy. In reality very few people do that.
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.
Copying/pasting the above password doesn't immediately get you the full square - something to do with the security provisions mentioned later in the article. Deleting a character and re-typing it works, though.
Is the complex pattern really necessary for this sort of thing to work? If the password doesn't match, why not just show a big red cross (or other form validation error)?
Taking the idea to the next level, why not just auto-submit the form when there's a good likelihood of a match? (Apart from likely breaking user expectations, and the possibility of some unlucky users having a hash collision halfway through their password.)
> If the password doesn't match, why not just show a big red cross..
It wouldn't look as cool :)
I was actually considering changing the text color on the password field on a match. Starting with gray and turning it black if there's a match, but it seemed to be too strongly implying that the password was 100% correct. And so I settled on something a bit more ambiguous.
This is certainly pretty, in a das blinkenlights sort of way.
I'd guess that most people aren't going to be looking at a little kanji-esque pictogram for guidance. They're going to click the "forgot password?" link after the first fail. Ambient data only works when you have an inkling about what the ambient display is reflecting.
More damning, though, is that this is trying to solve a problem by dragging the solution in an incorrect way. If you're typing in your password, you're doing it wrong. Use a password manager. Sell your users on the value, too.
You cannot use a cryptographic secure hash function to calculate a distance between data. If this were possible you could use a gradient descent like algorithm to find pre images. (I.e. the whole hash changes if you change one bit in the input)
And when I tested it, it looked like the symbol was completely random. (As it should be)
There's nothing on the backend, just one hardcoded username and password. All it does is takes an sha1 of statically salted password, adds up all bytes and masks with 0xff. This yields 1-byte hash reductions, which are compared for equality.
With these provisions in place, the password hinting should provide brute-forcing protection comparable to that of regular authentication mechanisms.
VERY bold statement and directly false? Since you a) also hints the hash and, indirectly, b) are forced to use a fast hash.
If there are 256 classes of hashes it is trivial to detect which class belongs to the user, I don't get the brute-force mitigations that is presented. Since this is done for every character sent you could just precompute 256 different passwords that generate the 256 different classes. And brute-forcing 256 passwords is trivial, especially since the current implementation request a new (reduced) hash for every character.
I don't understand what you don't understand, sorry.
Think of it this way - for every new password that you put into the database, run it through some function that spits out N bits. Remember these bits. Then, when you have a password candidate, pass it through the same function and check if the bits are the same. That's all there's to it.
The main exploitation risk is that hinting can be used to quickly reject candidate passwords when running a brute-force discovery (so that only remaining positives need to be run through the full authentication process). The provisions listed are to mitigate this risk, i.e. to make hinting unfit for the quick pre-filtering purpose.
Think of it this way - for every new password that you put into the database, run it through some function that spits out N bits.
And since those N bits are based on the password those N bits tell you something about the password. Directly or indirectly you leak information about the password.
His point is that the tradeoff isn't too bad: leak 8 bits, get pretty lights. Now for me, the pretty lights are basically nil because I don't see the improvement over just failing a login attempt, the way every other system in the world works. Also, the average password probably isn't very complicated (my guess is around 30 bits of entropy on average) which means every bit is precious. If you're going to ditch 8 of them, you better be getting some damn good usability improvements, which this thing doesn't give.
The thing that really confuses me is the indicator on the right - what do the different states mean? From reading the page, it seems like there are only two states that matter, likely or unlikely. But the way the indicator is constructed seems to suggest that it tells you how close you are to the actual password. If there are really only two states that matter, why not just have some sort of binary indicator?
Indicator has two states - gray and black. Gray is further animated as a visual gimmick, the actual arrangement of it has no meaning. The idea is that the animation gives you visual feedback on typing and the change of color confirms that the password is not definitively wrong. And the assumption is that after some use, the users will get accustomed to seeing black indicator immediately prior to hitting Enter.
Though since this is going through hashing, the number of matching bits has (by design) zero correlation to how close the P/W is. In which case, yeah, I think the binary indicator would be more useful and intuitive.
In particular, if you just type "qwertyuiop" or "asdfghjkl" or the like, the password looks at least as good (better, really) than when you type the correct password, right up to the last character. So, not very useful?
This doesn't make any sense. There is no "reduction" of a cryptographic hash that shows you anything other than "100% match" or "not 100% match". Essentially this is just displaying a random symbol along the side until the password matches completely.
EDIT: I'm surprised more people aren't commenting on this. It should be clear that if there were any way to tell if a match were "close", that would totally defeat the purpose of a cryptographic hash.
Essentially all this does it check the password (well, with extra meaningless false positives) without you having to press return.
Exactly, it's just testing 8 bits of the hash rather than the whole thing. So there is a considerably greater than zero chance of a false positive on totally unrelated words... it's all quite silly.
The part where you seem to be treating it like a breakthrough of some sort, when it's just a fun little gimmick. Your indicator is beyond useless, I just tried it on a user and they had no idea what that was supposed to indicate. There's similar reports out there. The setup is somewhat complex. The extra computational and network resources are not something to sneeze at. It looks like a fun project, but the idea that many sites would actually use this is quite silly
> you seem to be treating it like a breakthrough of some sort
Hahahahaha... seriously, where? What does make it seem that way? This is few hours worth of effort. That damn indicator took the longest to draw. Here, have a look at runner-ups - http://drbl.in/dpbA, http://drbl.in/dpgl
"Essentially all this does it check the password (well, with extra meaningless false positives) without you having to press return."
You're absolutely right. That's a far clearer explanation of what's happening here. A standard login form is rate limited to protect from brute force attempts, when calling a url for each character entered, this is problematic. I think the value in his approach is that it makes it significantly harder to brute force the password.
But the "reduction" adds no benefit. You might as well just check the whole hash and eliminate the false positives, which have no purpose. (A false positive has no correlation with being "closer" to the real password.)
All you're doing is shifting the time at which you check the password, from when the form is submitted, to when each key is pressed.
You seem to be wanting to assume that a correlation between some subset of the input bits leads to a correlation between some subset of the hash bits. But that's exactly what a cryptographic hash function is designed to prevent.
EDIT: The brute-forcing issue assumes that you treat form submissions and keypresses differently. In other words, why would you ignore a billion mismatches on keypresses and then raise an alarm on a few failed form submissions? You're just dividing the detection into two different phases, for no real purpose.
If you need that you can always rate limit it with the exception that you can add to passwords
e.g. if you queried "abc" perviously "abcd" does not count to the rate limit, but "bcd" does.
I don't know how I feel about this. To tell you the truth, I already did some small use test with 2 users (medium and advanced). And they both have a bit of trouble understanding what that sign was for.
Thanks for the blue outline report. Should be fixed now.
The idea is that the purpose of the indicator becomes obvious after some repeated use, and that it is not too intrusive or distracting on its own to be confusing to the new users.
The only realistic utility of this feature is that it could let you "guess" when the user has finished typing their password and check it automatically upon completion without them needing to press return. That would be a neat gimmick, but I don't see it working out.
The issues are twofold:
1. The obvious, it reduces an attacker's search space by the guess accuracy, in this case 256 times. To maintain equivalent security you must compensate for this by increasing the work of your hash function 256 times. Depending on your password's entropy (and thus your default work factor) this may or may not be acceptable. For user-supplied passwords secure hashes should take order of 100ms -- 10ms at the least -- and increasing that many orders of magnitude is definitely not acceptable. This, alas, pretty much breaks the idea, but putting it aside:
2. There will be collisions. The odds of a particular collision are 1/256; since an 8-character password contains seven chances for a collision, ballpark one in 36 of your users will have at least one collision during their password. This means that to maintain the seamless experience, you need to check the crypto-hash on the server silently, without indicating checking or failure to the user (anything else would be confusing). This introduces a number of very weird problems which you can definitely not be sure you have accurately addressed.
So, not really a good plan for passwords. Still a neat hack, though.
The author attempted to solve issue #1 by adding the 1000-msec delay for the first challenge and unrelated-password request throttling. That solves the issue for attackers using the client API (they can't narrow their search space).
The author has already acknowledged in the article that, were an attacker to get ahold of the stored password hash, they would have "everything needed to carry out brute-forcing."
I agree this is probably a deal breaker and defeats the purpose of using a hash function with a work factor like bcrypt.
Cryptographic hashes generally are selected for avalanche; changing one bit in the input should change about half of the output bits. This won't work as described with normal crypto hashes -- there are some hashes which do "nearness", but they have other tradeoffs.
I wouldn't do any of this, but if you really want to, it's interesting to think about the tradeoffs.
The more sane way to do this is to store some related hashes during original password creation time, or data about the password. The lowest hanging fruit with the least security risk is "is capslock on?" -- Mac OSX indicates this locally in the password dialog box. Next, just knowing the length is probably the most useful thing -- revealing that a 14 character password is 14 characters cuts the search space. This may or may not be acceptable. An attacker exhaustively brute forcing normally starts with "enter" and then moves up to single character, double character, etc. Say it is 4 character numeric only -- knowing it is 10^4 vs. (10^4 + 10^3 + 10^2 + 10^1 + 10^0) only costs you 11%. (obviously in real life you use common password lists, data about the user, etc., but for a 4-digit pin, especially one known to be randomly assigned, this is valid)
The next thing would be some kind of "finger alignment check" i.e. warning you immediately if the first character doesn't match -- maybe revealing the first character of the password, stored independently from the rest of it. Assuming it's random, it reduces the effective length of the password by 1 character -- taking an alphanumeric 14 down to an alphanumeric 13, or 62^14 vs. 62^14. Possibly ok.
Your experiment is attempting to produce a complicated method for a server to tell a user that they might not have typoed their password. This is probably not an issue because:
1. There is (to my knowledge) no reason to hide the password field with asterisks unless you have someone looking over your shoulder. If you really want to check for typos, use an 'unhide password field' icon/buttom like Android has.
2. Passwords are dead. I wouldn't even worry about somebody abusing this method because the user's password is probably "password1". Implement a second factor and you don't have to worry as much about a typo for a 20 character password.
3. Password managers never make typos.
4. Humans are fallible, typos happen, make it secure enough to handle typos or we're all doomed.
I'm pretty into this idea, im not sure there is enough information here for me to act on it but if i could be assured its safe (enough) and would require minimal impact to our existing hashing scheme, id give it a go.
Author's here. Reading the comments I feel like clarifying a couple of things :)
--- Clarification 1 ---
The goal of "hashing/reduction" step is to sort all possible passwords into M buckets. Then when a hint request comes in, we check if the typed-in password is in the same bucket as the one we have on file.
That's it.
One way to do this classification is described above. It is not the only way. One can take an MD4 of a string, extract the middle byte and call it a class ID. That would work as well (though it would require computing password "class" upon user registration, when the password is still in a clear). What we want is for related strings such as "password" and "passworf" to be in different classes, and this maps naturally to using cryptographic hashes.
--- Clarification 2 ---
The indicator pictogram has exactly two states - black and gray. The gray state is animated by randomizing its pattern to provide visual feedback on typing. It does not indicate if the currently typed password is "closer" to or "farther" from the target one. The gray always means just one thing - the password is invalid.
Thank you for clarifying, it makes a lot more sense now. I see how you could use bcrypt for actual authentication and some much faster method for hinting.
I think part of the confusion lies in the flow diagram, which maps "stored password hash" to "reduction". In your "class ID" example, what is the difference between the stored password hash and the reduction? What is the purpose of the stored password hash if you always reduce it the same way? Why not just store the reduction? I suppose you might employ a two-phase reduction process (one static and one dynamic), but is this really necessary? What is the advantage?
An interesting exercise I suppose but solving a completely non-existent problem. The problem is sites departing from the more than adequate password requirement of 6 chars and nothing more.
Also, I hate input fields like that where the label disappears immediately (I don't even really like that label positioning in the first place). If you want to improve usability, fix that instead.
There is no "password nearness". The entered password is either in the same bucket (identified by an N-bit ID) as the stored password, or it is not. That's it. In former case the hint indicator is black, in latter it's not (though it is animated to a random state).
This is interesting, however the fact that the password indicator gives me a more positive reading for 'qwerty' rather than the correct password minus one letter ('inconsequentia') means to me this is not really 'hinting', just saying yes or no.
It is nice to do this on the login page itself (rather than the usual click and 30-seconds to load a 'your username or password is invalid' - where you need to retype both again), however I assume that you probably have unlimited attempts to 'guess' the password, and thus it is probably quite susceptible to abuse.
On Mac OS X most recent version of Firefox it sometimes shows the shape to the right as entirely darkened and other times not when I type "inconsequential". Any reason for this?
Not the author, but from the description, you can only request one check at a time. When you get the results of your current check back, you get a new token.
I'm guessing that the server got too busy to serve a request, either the last request, or any previous one, so that you broke the token chain. Another possibility could be a bug with the timing of events, such that it doesn't realize the field has changed.
The author seems to be lurking around here, maybe he'll have a better idea.
The author appears to have given some consideration to security implications (one-use tokens, demanding relatedness, delays, presumably some protection against timing attacks, etc.); my main concerns are:
* This approach requires granting access to read the raw password hash to the password-tester application
* High resource cost for marginal user utility
* These password-check attempts do not count as logon failures, likely defeating intrusion detection measures
There are probably more issues but there are top-of-head. FWIW Lotus Notes has always done something similar as you type.
It does. What I mean by 'the application' is the backend / web app.
To put it another way, a better design allows no application code to read the hash from storage; the application can only ask the storage or security service to compare a supplied value for correctness. Fail enough times in rapid succession and the security service locks the account for a few minutes, preventing any comparisons during that period.
Opening the door to testing the hash itself outside of these constraints is the weakness I am suggesting.
