Show HN: Password validity hinting
swapped.cc
swapped.cc
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.
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.
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.
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.
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.
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.
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.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
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.)
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.
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.
What if it said just said "WRONG" inside <blink> tags?
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)
Edit: It's called the avalanche effect http://en.wikipedia.org/wiki/Avalanche_effect
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.
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.
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.
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.
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.
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.
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.
Which part exactly?
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
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.
This is exactly what it does. See this comment for details - http://news.ycombinator.com/item?id=3689051
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.
It also didn't help the fact that the outline of the password was distracting: http://dl.getdropbox.com/u/4651065/files/2012/3/Screen%20Sho...
The idea itself is interesting, though without previous explanation or knowledge it's just hard to guess what it is about.
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 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 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.
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.
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.
Thanks for sharing.
--- 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.
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?
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.
The neat thing about ChromaHash is that it never compares the user-entered password to the real hash, that is done by the users memory.
The unfortunate part is that it doesn't help if you don't use a website frequently.
My only wonder would be how to implement this so that it doesn't confuse or intimidate users... but I'm sure there is an answer to that.
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.
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.
There are probably more issues but there are top-of-head. FWIW Lotus Notes has always done something similar as you type.
No, it doesn't.
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.
Also thanks for the downvote.
http://news.ycombinator.com/item?id=3689024
And I didn't downvote you (not that I even can).
There's the whole section that talks about that.