3 ms·

I remember a paper, from Microsoft I think, where the proposed method was to keep a list of all passwords and prevent any password to be used more than X times.

I remember a paper, from Microsoft I think, where the proposed method was to keep a list of all passwords and prevent any password to be used more than X times. This way no password becomes common. But it would likely be frustrating for users who try to find a password (like trying to find a username on Hotmail: everything is taken!).

tdrgabi 14y ago
Doesn't that mean that you keep the passwords in clear? They don't have a user => password relation, but having a list of passwords to go through will make any bruteforce attack extremely fast.
- Fletch137 14y ago
  I would expect that you'd just compare the hash, effectively performing half of the log in process to check if the password's okay. I imagine it'd be pretty costly in terms of performance if every time you wanted to create a new user you had to hash the password, then check against a (potentially huge) table to see if that password had been used >X times. Hopefully I'm being short-sighted or missing something that'd mean this could be done simply and quickly, because in theory it sounds like quite a good idea.
  - omh 14y ago
    If you're using per-user salting (and you should be) then you have to do n hash calculations, not just one calculation and n comparisons. Might be feasible for a small number of users on an internal app, but unlikely to work on a big or public site. I'd also be worried about information leakage. If you tell me that I can't use my password then I now know that it's used by someone else. If I work out who that is (which could be quite easy) then I can impersonate them.
    - Fletch137 14y ago
      Even more performance-intensive than I thought - possibly why it's not been implemented. Assuming you know that a given password can be used 10 times and there's a database of 100,000 users in your scenario above, how would you work out who that is?
- mseebach2 14y ago
  You could at least bcrypt them all with the same salt, however, it's a long step backwards from individual salting. Also, then you can't check for "[common base password][phone number]" or some variation that's exactly as dangerous as just using a common password - if you kept a plaintext list, you could do substring searches. The more important lesson here is probably that your users insisting on using crappy passwords isn't really a problem for technology to solve. If you users aren't in the mindset of feeling an obligation towards protecting the data, there are much bigger holes in the network than password complexity enforcement. http://www.smbc-comics.com/comics/20120220.gif http://www.smbc-comics.com/comics/20120220.gif http://www.theregister.co.uk/2008/04/16/password_security/ http://www.theregister.co.uk/2008/04/16/password_security/
  - Fletch137 14y ago
    I think that the main problem is always going to be the end users. I'd like to say that fingerprints or iris scans would solve the issue, but they have their own problems (e.g. having a backup password in case prints or scans aren't recognised). I agree that it really should be the user's attitude that needs to change, but there will always be that one person even if the other 99% of people get things right - so I think that at least trying to build a system to compensate for this is just as worthwhile as educating users. I quite like the idea from XKCD [http://xkcd.com/936/ http://xkcd.com/936/] of using words instead of letters (but also have a few problems with it), perhaps rather than having passwords, we should have pass sentences that also have requirements (8 words of more, at least 2 punctuation marks, for example) or are generated for the user (could be nonsense sentences or contain misspelt words).
  - lifeisstillgood 14y ago
    Is it me or is individual salting rather redundant. I can see why using one salt forevermore is rubbish but if I salt a different user with a different lt each time, but I need to keep that salt in plaintext next to the hash. Making the whole salting thing a bit redundant if I get a linked in style loss I certainly see a benefit in padding out user passwords to say 128 bits each time, combined with crypt it will slow down any mass brute force /rainbow attack. Pre-edit edit: I just answered my own question did I not.
- danielweber 14y ago
  I'm still groggy but here's one proposal: 1. Set up something like a bloom filter, tuned to give lots of false positives. 2. Fill the list with the 100,000 most common passwords. 3. Every time someone proposes a password, see if it hits. If so, goto 3. If not, let them use the password and insert it into the list. I think you probably want to scrypt[1] the passwords first. If someone gets the list, they can rule out that no one has certain passwords. I'm not sure how much of a failure that is. [1] EDIT: I mean scrypt without a hash, which might be nonsense. Or the same hash for everyone. Yes, this sucks for storing individual passwords, but it helps you build the "master list." I'm not sure there is a way around this paradox if you want to have a master list, but the bloom filter will throw a lot of noise into the mix.

tdrgabi 14y ago

Doesn't that mean that you keep the passwords in clear? They don't have a user => password relation, but having a list of passwords to go through will make any bruteforce attack extremely fast.

Fletch137 14y ago
I would expect that you'd just compare the hash, effectively performing half of the log in process to check if the password's okay. I imagine it'd be pretty costly in terms of performance if every time you wanted to create a new user you had to hash the password, then check against a (potentially huge) table to see if that password had been used >X times. Hopefully I'm being short-sighted or missing something that'd mean this could be done simply and quickly, because in theory it sounds like quite a good idea.
- omh 14y ago
  If you're using per-user salting (and you should be) then you have to do n hash calculations, not just one calculation and n comparisons. Might be feasible for a small number of users on an internal app, but unlikely to work on a big or public site. I'd also be worried about information leakage. If you tell me that I can't use my password then I now know that it's used by someone else. If I work out who that is (which could be quite easy) then I can impersonate them.
  - Fletch137 14y ago
    Even more performance-intensive than I thought - possibly why it's not been implemented. Assuming you know that a given password can be used 10 times and there's a database of 100,000 users in your scenario above, how would you work out who that is?
mseebach2 14y ago
You could at least bcrypt them all with the same salt, however, it's a long step backwards from individual salting. Also, then you can't check for "[common base password][phone number]" or some variation that's exactly as dangerous as just using a common password - if you kept a plaintext list, you could do substring searches. The more important lesson here is probably that your users insisting on using crappy passwords isn't really a problem for technology to solve. If you users aren't in the mindset of feeling an obligation towards protecting the data, there are much bigger holes in the network than password complexity enforcement. http://www.smbc-comics.com/comics/20120220.gif http://www.smbc-comics.com/comics/20120220.gif http://www.theregister.co.uk/2008/04/16/password_security/ http://www.theregister.co.uk/2008/04/16/password_security/
- Fletch137 14y ago
  I think that the main problem is always going to be the end users. I'd like to say that fingerprints or iris scans would solve the issue, but they have their own problems (e.g. having a backup password in case prints or scans aren't recognised). I agree that it really should be the user's attitude that needs to change, but there will always be that one person even if the other 99% of people get things right - so I think that at least trying to build a system to compensate for this is just as worthwhile as educating users. I quite like the idea from XKCD [http://xkcd.com/936/ http://xkcd.com/936/] of using words instead of letters (but also have a few problems with it), perhaps rather than having passwords, we should have pass sentences that also have requirements (8 words of more, at least 2 punctuation marks, for example) or are generated for the user (could be nonsense sentences or contain misspelt words).
- lifeisstillgood 14y ago
  Is it me or is individual salting rather redundant. I can see why using one salt forevermore is rubbish but if I salt a different user with a different lt each time, but I need to keep that salt in plaintext next to the hash. Making the whole salting thing a bit redundant if I get a linked in style loss I certainly see a benefit in padding out user passwords to say 128 bits each time, combined with crypt it will slow down any mass brute force /rainbow attack. Pre-edit edit: I just answered my own question did I not.
danielweber 14y ago
I'm still groggy but here's one proposal: 1. Set up something like a bloom filter, tuned to give lots of false positives. 2. Fill the list with the 100,000 most common passwords. 3. Every time someone proposes a password, see if it hits. If so, goto 3. If not, let them use the password and insert it into the list. I think you probably want to scrypt[1] the passwords first. If someone gets the list, they can rule out that no one has certain passwords. I'm not sure how much of a failure that is. [1] EDIT: I mean scrypt without a hash, which might be nonsense. Or the same hash for everyone. Yes, this sucks for storing individual passwords, but it helps you build the "master list." I'm not sure there is a way around this paradox if you want to have a master list, but the bloom filter will throw a lot of noise into the mix.