0

Lets assume I want to give my hypothetic 10mio users userbase a good feedback on their password strength. Besides the classical entropy tests and top500 list of bad passwords, I might want it to be based on "there are already more than N users with the same password" (for N maybe 100).

So aside of the state-of-the-art multiround salted hashed password stuff I naively store a big table with password:counter pairs (and maintain it through password changes) and tell the user his password is bad when that counter reaches N. Now of course this defeats my good password hash management: whoever gets that table has all the possible passwords and can just try them trivially. I could hash them, which would just add some time factor far too small to be secure.

So how can I (if at all) maintain any statistics that will allow me to have these counters (or something similar enough with not too many false positives) without the statistics data being more of a security risk when exposed than the table of password hashes?

Improve this question

3 Answers 3

Reset to default
3

As @aviv pointed out, revealing to a user that some other user also has the same password is a problem.

If you really intend to maintain such statistics, then you have another inherent problem: the "statistics engine" can only help any attacker, since it outputs a list of passwords that are in use. Even a reduced form which merely says "this password is already used by somebody else" allows the attacker to break passwords much faster, for the following reason. Good password hashing uses salts so that attackers cannot try to break 10 millions of passwords in parallel. If hashing is unsalted, then the attacker can hash a potential password once, and compare the resulting hash value against all 10 millions hashes; in that way, the attacker breaks 10 millions of passwords for the cost of breaking one. Salts prevent that. Salts are good.

Now suppose that you have a statistics engine which can tell you, when a user enters his new password, whether that password is already used by somebody else or not (even without telling how many users have chosen it). Then an attacker, who could get a copy of your database (you hash passwords precisely because you fear that scenario), can run the same "engine" on his own computers. Thus, he can "submit" a potential password to the engine, and learn whether it is used by one of the 10 millions of users or not. This allows him to prune his huge list of potential passwords down to the ones that are really worth the effort: instead of trying one billion passwords on each hashed value, he will try only the 1000 or so passwords for which he got hits from the statistics engine. You've just made the attacker's task one million times easier.

The only way out of this problem is to make sure that the attacker will never be able to access the statistics (which, in turns, implies that they won't be shown to the users themselves). This suggests the following:

  • When a user chooses his password, the password is hashed as usual (with bcrypt or anything similar).

  • The password is also asymmetrically encrypted with a given RSA public key. Asymmetric encryption is randomized, so the encrypted results don't allow for dictionary attacks. A 2048-bit RSA key is enough to encrypt data elements up to 245 bytes, which ought to be enough for passwords.

  • The corresponding private key is kept on an offline machine (thus presumably immune to remote attacks). At regular intervals, the "statistics officer" gather the encrypted passwords from the server, transfers them to the offline machine (with a USB drive or something similar), decrypts them, and runs statistics.

Improve this answer
2
  • It was probably not clear, but I was thinking of an "your password is weak" output which upon a second thought might still be prone to a similar attack, assuming that people start using passwords being non-weak based on standard metric, and the only reason for being weak is left is that another 100 people use that password too. You seem to think it triggers for when already one other user uses the same, but I wanted it to be N (maybe 100 is bad, so set whatever seems useful). Wouldn't the described attack then be much less feasible, assuming that users chose a pw that will not trigger?
    – PlasmaHH
    Commented Jul 23, 2014 at 13:18
  • So, a message like, "That password has already been used by many other users of this site. Please choose another." ? Great. Now I have a confirmed password used by N number of users. all I have to do is brute-force account names, which are not private.
    – schroeder ♦
    Commented Jul 23, 2014 at 15:59
2

I dont think you want to do that at all... you will be giving hints about other user's passwords. If I get the message that 1 other user is using my password - now I have valuable information. I might even know or guess who that user is if I have some prior knowledge on him

Improve this answer
1
  • Surely that message would not be that someone else uses it, but that your password is weak (and also not for 1 but for N). But the question is more hypothetical, on how to be able to do it, if at all. If you sleep nicer with it, assume that I am doing this for my own statistics (hint: I am not doing all this at all).
    – PlasmaHH
    Commented Jul 23, 2014 at 13:11
0

You should NOT be able to determine if any user have the same passwords given the information in your database. It's just a security risk by design.

If you really want to do something like that, at the very least please never tell the user the actual reason, just say something like "Your password is not complex enough" coupled with the generic lower/upper/digit/special check.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .