21 ms·

While that is an absolutely ridiculous requirement, couldn't it be satisfied securely by creating on the order of 1-10k modifications of each password when crea

While that is an absolutely ridiculous requirement, couldn't it be satisfied securely by creating on the order of 1-10k modifications of each password when created, and hashing those? That would be enough to add numbers to the end, switch case, reverse, randomly change letters etc. It's a lot of trouble to go through just because of the ignorance of a client, but it would be enough to check that magic box on the requirements list and be done with it, rather than having to go to all of the trouble of trying to educate the client and risk them going elsewhere.

jmah 15y ago
It's 3am and I've been drinking, but this seems feasible: When the user changes their password, encrypt the old password with a key derived from the new one (you have both in plaintext at this point, when entering old/new passwords). Then hash the new one as usual. Then when the user goes to change their password again, you have the plaintext of the current one, which unlocks the previous password, and so on back in the chain. You can then compare the new password with previous passwords for similarity.
- swixmix 15y ago
  I like this idea, but I don't think it can be enforced. If I "forget" my password, then all the history is lost with it.
  - stcredzero 15y ago
    If the old password is "forgotten" and can't be retrieved by the user who made it up, then it doesn't seem like that big a risk.
    - jbri 15y ago
      The issue is that once your users figure out the system, they'll always "forget" what their password was once it's getting around to expiring.
      - erikano 15y ago
        The method I am about to mention here is based on that which was outlined earlier by somebody else [1]. As I will mention further down, the method I suggest here will give the administrator and the CEO the opportunity to conspire and retrieve users passwords without the affected users knowledge, but I will here assume that such could not happend and that if they really wanted to do so, they could find other means anyway (keylogging, etc.) First time: On his client, the user is asked to enter a password which is checked to comply with password rules. This password is salted and hashed before it is stored on a central machine. n-th time: On his client, the user first enters password "n - 1" which is then salted and hashed and sent to the central machine for comparison. If hashes match, you may enter the new password "n" which is checked to comply with password rules. Password "n - 1" is then encryted with password "n" and stored on the central machine. Password "n" is stored on the central machine in two forms: 1) Salted and hashed. 2) Encrypted with a public key. Password "n" is encrypted with a public key and stored on a he central machine. Also, when this machine stores the new public key encrypted password, it deletes its own records of any previous public key encrypted password for the user in question. Through recursion, all old passwords ("n - 2" ... "1") are decrypted and the new password is checked so that it does not match any previous password and that it is not a simple permutation of any of those. If the user forgets his password, the administrator physically logs into a machine which is very tightly secured. This machine does not allow inbound connections of any kind over the network and can only make outbound connections to the central storage machine. Furthermore, the machine does not allow the usage of any removable media (CD, DVD, USB stick, etc.). The drives of the machine in strongly encrypted, as is the private key which is stored on this machine. In order to decrypt the disc of the machine, two passwords are needed. One of the passwords is held by the administrator, the other by the CEO of the company. The same goes for the private key which also has two passwords, both of which are needed to decrypt it. Thus, two people must be involved in order to decrypt the password for a user. Once the administrator and the CEO has logged into the machine, they connect to the central storage and retrieve the encrypted key for the user and then they open their shared private key and decrypt the password. After the user has been given his old password, he must create a new password following the procedure described above. That way, the administator and the CEO does not know the users new password (unless they conspire to do so, but that would be breach of trust). http://news.ycombinator.com/item?id=2820976 http://news.ycombinator.com/item?id=2820976
- diolpah 15y ago
  "It's 3am and I've been drinking, but this seems feasible" I have come up with some astoundingly dumb ideas that were preceded by exactly the above thought. However, there was some sheer brilliance, as well.
swixmix 15y ago
A better method would be to save previous password hashes when a password is changed, then check hashes of permutations of the new password against the previous ones.
- palish 15y ago
  That would verify they aren't bouncing from password A to password B and back to A again... but that's all.
  - swixmix 15y ago
    That would only be true if it didn't keep history. Let's assume my previous two passwords are "love123" and "hate098". If I try to use a new password "love124", then the permutation checker (which, for the moment, knows the new password in plaintext) should check the hash of "love123" and reject it.
    - palish 15y ago
      Oh. If you write a permutation checker that happens to output one of your old passwords, then yeah, that'd work. I wonder if that's feasible. It's an interesting idea. Computing hashes is relatively cheap, so I wonder if, say, 1,000 "permutation checks" would be enough. (Although if you're using bcrypt to store passwords, which you should be, then apparently it's not so cheap.) But.. 26 letters in the alphabet + ten digits = 36... and 36^n grows really, really fast. So maybe you'd need way more than 1k permutation checks.
- zizee 15y ago
  That was my first thought too, but it does not satisfy the "similar" part of the requirement.
  - saurik 15y ago
    It does, because if the new password is similar to the old one, you can either modify the old one to get the new one or modify the new one to get the old one.
nikcub 15y ago
If you are storing passwords properly with bcrypt, then the 1-10k permutations will take far too long to calculate, especially considering that you need to give the user feedback on their new password choice being ok or not within ~100ms (Edit: so the match might be quick, but pre-comp of the hashes and storing them is not. how the hell would you store 1-10k hashes associated with a user anyway? :) )
- robtoo 15y ago
  When setting a password, you compare the new password to the old hashes, which were calculated the last time the password was changed. So user feedback should be speedy enough. Only once the password is deemed acceptable does the system need to pre-calculate the hashes for the next time the password is changed. Of course, pre-calculating 10,000 bcrypt hashes might be too computationally expensive anyway, but the user wouldn't see a delay.
  - nikcub 15y ago
    you are right - I have it the wrong way around. still you need to do the calculations and find somewhere to store all of those hashes but I can't think of any other way of making 'similar to' work
  - gus_massa 15y ago
    If you use a different salt for each modification of the old password, you must compute the all the hashes of the new password. Another problem is that to prevent the use of the very old passwords, you should keep the hashes of the modifications. To make the comparations fast, you have to use the same hash. Now you have a list of #password-changes * #passwords-modifications, and if an intruder get them, it is possible to make a mini-rainbow attack.
- reitzensteinm 15y ago
  What kind of bcrypt run times should be targeted? In my back of the envelope calculations I used 100ms per core, which would make 80/s on an 8 core machine, or 12.5s for 1k hashes and 2 minutes for 10k. Which doesn't seem unreasonable. You can give the user feedback on their new password choice after just one hash. The permutations would be stored from their last password set, so it would just be a simple lookup to determine whether a given new password is similar to an old one. I'm in no way recommending this - it was just an amateur guess at a method to fulfill the requirements without exposing a massive security vulnerability.

jmah 15y ago

It's 3am and I've been drinking, but this seems feasible: When the user changes their password, encrypt the old password with a key derived from the new one (you have both in plaintext at this point, when entering old/new passwords). Then hash the new one as usual. Then when the user goes to change their password again, you have the plaintext of the current one, which unlocks the previous password, and so on back in the chain. You can then compare the new password with previous passwords for similarity.

swixmix 15y ago
I like this idea, but I don't think it can be enforced. If I "forget" my password, then all the history is lost with it.
- stcredzero 15y ago
  If the old password is "forgotten" and can't be retrieved by the user who made it up, then it doesn't seem like that big a risk.
  - jbri 15y ago
    The issue is that once your users figure out the system, they'll always "forget" what their password was once it's getting around to expiring.
    - erikano 15y ago
      The method I am about to mention here is based on that which was outlined earlier by somebody else [1]. As I will mention further down, the method I suggest here will give the administrator and the CEO the opportunity to conspire and retrieve users passwords without the affected users knowledge, but I will here assume that such could not happend and that if they really wanted to do so, they could find other means anyway (keylogging, etc.) First time: On his client, the user is asked to enter a password which is checked to comply with password rules. This password is salted and hashed before it is stored on a central machine. n-th time: On his client, the user first enters password "n - 1" which is then salted and hashed and sent to the central machine for comparison. If hashes match, you may enter the new password "n" which is checked to comply with password rules. Password "n - 1" is then encryted with password "n" and stored on the central machine. Password "n" is stored on the central machine in two forms: 1) Salted and hashed. 2) Encrypted with a public key. Password "n" is encrypted with a public key and stored on a he central machine. Also, when this machine stores the new public key encrypted password, it deletes its own records of any previous public key encrypted password for the user in question. Through recursion, all old passwords ("n - 2" ... "1") are decrypted and the new password is checked so that it does not match any previous password and that it is not a simple permutation of any of those. If the user forgets his password, the administrator physically logs into a machine which is very tightly secured. This machine does not allow inbound connections of any kind over the network and can only make outbound connections to the central storage machine. Furthermore, the machine does not allow the usage of any removable media (CD, DVD, USB stick, etc.). The drives of the machine in strongly encrypted, as is the private key which is stored on this machine. In order to decrypt the disc of the machine, two passwords are needed. One of the passwords is held by the administrator, the other by the CEO of the company. The same goes for the private key which also has two passwords, both of which are needed to decrypt it. Thus, two people must be involved in order to decrypt the password for a user. Once the administrator and the CEO has logged into the machine, they connect to the central storage and retrieve the encrypted key for the user and then they open their shared private key and decrypt the password. After the user has been given his old password, he must create a new password following the procedure described above. That way, the administator and the CEO does not know the users new password (unless they conspire to do so, but that would be breach of trust). http://news.ycombinator.com/item?id=2820976 http://news.ycombinator.com/item?id=2820976
diolpah 15y ago
"It's 3am and I've been drinking, but this seems feasible" I have come up with some astoundingly dumb ideas that were preceded by exactly the above thought. However, there was some sheer brilliance, as well.

swixmix 15y ago

A better method would be to save previous password hashes when a password is changed, then check hashes of permutations of the new password against the previous ones.

palish 15y ago
That would verify they aren't bouncing from password A to password B and back to A again... but that's all.
- swixmix 15y ago
  That would only be true if it didn't keep history. Let's assume my previous two passwords are "love123" and "hate098". If I try to use a new password "love124", then the permutation checker (which, for the moment, knows the new password in plaintext) should check the hash of "love123" and reject it.
  - palish 15y ago
    Oh. If you write a permutation checker that happens to output one of your old passwords, then yeah, that'd work. I wonder if that's feasible. It's an interesting idea. Computing hashes is relatively cheap, so I wonder if, say, 1,000 "permutation checks" would be enough. (Although if you're using bcrypt to store passwords, which you should be, then apparently it's not so cheap.) But.. 26 letters in the alphabet + ten digits = 36... and 36^n grows really, really fast. So maybe you'd need way more than 1k permutation checks.
zizee 15y ago
That was my first thought too, but it does not satisfy the "similar" part of the requirement.
- saurik 15y ago
  It does, because if the new password is similar to the old one, you can either modify the old one to get the new one or modify the new one to get the old one.

nikcub 15y ago

If you are storing passwords properly with bcrypt, then the 1-10k permutations will take far too long to calculate, especially considering that you need to give the user feedback on their new password choice being ok or not within ~100ms (Edit: so the match might be quick, but pre-comp of the hashes and storing them is not. how the hell would you store 1-10k hashes associated with a user anyway? :) )

robtoo 15y ago
When setting a password, you compare the new password to the old hashes, which were calculated the last time the password was changed. So user feedback should be speedy enough. Only once the password is deemed acceptable does the system need to pre-calculate the hashes for the next time the password is changed. Of course, pre-calculating 10,000 bcrypt hashes might be too computationally expensive anyway, but the user wouldn't see a delay.
- nikcub 15y ago
  you are right - I have it the wrong way around. still you need to do the calculations and find somewhere to store all of those hashes but I can't think of any other way of making 'similar to' work
- gus_massa 15y ago
  If you use a different salt for each modification of the old password, you must compute the all the hashes of the new password. Another problem is that to prevent the use of the very old passwords, you should keep the hashes of the modifications. To make the comparations fast, you have to use the same hash. Now you have a list of #password-changes * #passwords-modifications, and if an intruder get them, it is possible to make a mini-rainbow attack.
reitzensteinm 15y ago
What kind of bcrypt run times should be targeted? In my back of the envelope calculations I used 100ms per core, which would make 80/s on an 8 core machine, or 12.5s for 1k hashes and 2 minutes for 10k. Which doesn't seem unreasonable. You can give the user feedback on their new password choice after just one hash. The permutations would be stored from their last password set, so it would just be a simple lookup to determine whether a given new password is similar to an old one. I'm in no way recommending this - it was just an amateur guess at a method to fulfill the requirements without exposing a massive security vulnerability.