7 ms·

To Keep Passwords Safe from Hackers, Just Break Them into Bits

45 points by iProject 14y ago

xyzzy123 14y ago
Assume some perfectly secure method of storing passwords existed. Attackers would be forced to shift to compromising them at the point of entry -- i.e. modify code or scrape memory to capture them at the point they are entered on the site. An improvement (they have to be in motion, not at rest), but not a panacea. The problem is passwords... yeah, easy to state, hard to fix.
circlingthesun 14y ago
This sounds a lot like the last level of capture the flag 2.
- lucian1900 14y ago
  And is also likely to suffer from vulnerabilities because of its complexity.
- mguillemot 14y ago
  The security flaw highlighted in Stripe CTF2 was that you could check the validity of each independant chunk independantly of the others, which meant reducing the search space for bruteforce attacks. From what I understand, the technique proposed here would mean you cannot say anything about the validity of just one chunk: each server apply some operation on the password it receives and the chunk it stores, and all these operations have to be combined to say if the password was valid or not. If it's not, you cannot know which chunk was invalid.
- mattlong 14y ago
  Referring to the Stripe CTF 2.0 [1]. [1] https://github.com/stripe-ctf/stripe-ctf-2.0/tree/master/levels/8 https://github.com/stripe-ctf/stripe-ctf-2.0/tree/master/lev...
stephengillie 14y ago
Instead of storing half of the bits on a server, why not store them on a smartcard, usb drive, or other physical device, to introduce 2-factor to this system?
- 7952 14y ago
  Or even make a cookie value part of the mix. The cookie could be from another domain and only accessible through a javascript API on the browser.
lvh 14y ago
It seems like this relies on an attacker being able to compromise one machine, but not another. Given that these machines are supposed to be quite similar (they're both password databases running the same software), what makes that a reasonable assumption?
- zaphoyd 14y ago
  The article suggests that the two machines could be running different operating systems and be placed on different networks/locations to reduce the chances of a single attack compromising both systems.
  - cookingrobot 14y ago
    It seems really unlikely that any of these leaks has been due to a security flaw in the operating system. I'd think that even in this scheme if an admin account or authentication process is compromised, then the attacker's going to have access to both password stores.
    - dekz 14y ago
      Well, no, because it's a write only model. If the admin account becomes compromised there is no way to read the passwords back. That is of course unless you have root access to both machines, in which case the password can be salted + hashed and then split and stored.
ericcholis 14y ago
Let us not forget an important factor here, don't do things like hashing using SHA-1. While this system sounds awesome, researching common best practices for password storage takes about 2 minutes.
dmansen 14y ago
Why is something like bcrypt not adequate? The article seems to imply that bcrypt could be reversed, but I thought this wasn't the case (with a proper work factor).
- jmsduran 14y ago
  Bcrypt is a key lengthening algorithm for individual passwords. This article talks about a method that divides a password into pieces to store on physically different machines, that may reside in different parts of the world. I can see bcrypt and distributed credential protection complementing each other to form a rather robust security policy. But then again, I'm not a security expert.
- deleted 14y ago
  [deleted]
- ddlatham 14y ago
  Bcrypt slows down a brute force attack considerably, but cannot prevent one. If your password is one of the top N passwords in use, then a determined attacker can still break it. For example, if you set your work factor such that it takes 1 second to verify a password using bcrypt on login to your server, then if your password is in a dictionary of the top 100k passwords, an attacker could get to it within (about) a day using equivalent hardware. Using more specialized (or just more) hardware of course drives it further.
  - dmansen 14y ago
    Good point, I didn't think of that.
opyate 14y ago
Security by obscurity never works.
- bmohlenhoff 14y ago
  Security including obscurity works fine. There's nothing wrong with using it as a component, it just can't be the sole defense.
ZoFreX 14y ago
The number one problem with passwords is that most websites are not storing them using current state-of-the-art methods that are freely available. Whether or not this is an improvement, it doesn't solve the actual problem - developers aren't going to suddenly start using this if their current method is md5(password). That said, it does sound quite interesting from a crypto geek perspective.
- 7952 14y ago
  We always assume that users are going to make security mistakes and build around that. We should assume the same about developers and stop expecting them to build secure sites. That is how the web actually is already, and it is unlikely to change any time soon.
  - 0003 14y ago
    Has there been paper, or for that matter a blog-post with a napkin calculation, on the cost-benefit of a proper password/authorization system versus a non-robust system discounted for reputation loss / legal liability for system compromises? I did a few google queries but came up empty. I think this would make for a great PSA.
  - nathan_long 14y ago
    >> We always assume that users are going to make security mistakes and build around that. We should assume the same about developers and stop expecting them to build secure sites. I don't follow you. In the first sentence, the "we" is developers of web sites, right? Who is the "we" in the second half? Who are you suggesting should assume developers will make mistakes, and what can/should be done to mitigate that? One possible interpretation is that the second "we" is users, and as a user, yes, I do assume that sites will make mistakes. One reaction is not re-using passwords. But if the user and the site are both naive, I don't see who is left to keep the wolves out.
    - 7952 14y ago
      Sorry my comment was inarticulate. I am arguing for a collective sense of mistrust regardless of who you are.
huxley 14y ago
Mozilla also uses a 2 server approach for passwords on their web apps but instead of splitting the password, they introduce an initial HMAC hash stage using a salt that is stored on a web app machine and then rehash that with Bcrypt for storage in a database on a separate machine. "If an attacker steals one of our password databases, they would need to also separately attack one of our web servers to get file access in order to discover this local salt value. If they don’t manage to pull off two successful attacks, their stolen data is largely useless." http://blog.mozilla.org/webdev/2012/06/08/lets-talk-about-password-storage/ http://blog.mozilla.org/webdev/2012/06/08/lets-talk-about-pa... They have an implementation for Django (ignore the project name, it's a legacy name): https://github.com/fwenzel/django-sha2 https://github.com/fwenzel/django-sha2 Their implementation makes it trivially easy to expire HMAC keys and silently upgrade users to new HMAC keys.
rficcaglia 14y ago
Open source threshold crypto project http://www.utdallas.edu/~mxk093120/paillier/index.php?go=home http://www.utdallas.edu/~mxk093120/paillier/index.php?go=hom...
praptak 14y ago
"Breaking into bits" suggests something about this technique that is not accurate. It does not rely on splitting bits, as in computing n bits and sending each of the n/2 bit halves to different servers. It is closer to hiding one bit by flipping a coin and sending the bit xor-ed with the result to one server and the result of the flip to the other.
eridius 14y ago
These would have to happen in short order, too, because the system periodically refreshes which random half of the snippets of a password are stored on each server. How long would it take for one of the servers to see every piece of the password, on average? If it's not prohibitively long, and you can silently compromise the server, you could just wait. Alternatively, how does it decide to refresh, and how does it decide which pieces to redistribute? If there's some way to attack that mechanism, perhaps you could cause it to refresh faster, or maybe even control the distribution process.
- praptak 14y ago
  > How long would it take for one of the servers to see every piece of the password, on average? Strong secret sharing schemes are secure against this kind of attack. The schemes are designed so that you cannot infer any information about the original secret from any of the pieces. That holds even if you get a single piece from each of multiple independent "splits" of the same secret. Some examples of such schemes are on Wikipedia and they fall into the "simple but clever" category: http://en.wikipedia.org/wiki/Secret_sharing#Trivial_secret_sharing http://en.wikipedia.org/wiki/Secret_sharing#Trivial_secret_s...
rdtsc 14y ago
> attackers have a range of tools that can reverse this encryption if attacks have a whole range of tools to reverse the "encryption" it either means whoever was in charge of of security is stupid or their attackers have secret or magic weapons
kbs 14y ago
I'd added a link and some notes as a comment on a related post here: http://news.ycombinator.com/item?id=4636655 http://news.ycombinator.com/item?id=4636655 Here is a link to an article with a few more details about the technique being used. http://productsecurityblog.emc.com/2012/10/split-value-cryptographic-authentication-building-advanced-threat-resistant-software/ http://productsecurityblog.emc.com/2012/10/split-value-crypt...

45 points by iProject 14y ago

Assume some perfectly secure method of storing passwords existed. Attackers would be forced to shift to compromising them at the point of entry -- i.e. modify code or scrape memory to capture them at the point they are entered on the site. An improvement (they have to be in motion, not at rest), but not a panacea. The problem is passwords... yeah, easy to state, hard to fix.

circlingthesun 14y ago

This sounds a lot like the last level of capture the flag 2.

lucian1900 14y ago
And is also likely to suffer from vulnerabilities because of its complexity.
mguillemot 14y ago
The security flaw highlighted in Stripe CTF2 was that you could check the validity of each independant chunk independantly of the others, which meant reducing the search space for bruteforce attacks. From what I understand, the technique proposed here would mean you cannot say anything about the validity of just one chunk: each server apply some operation on the password it receives and the chunk it stores, and all these operations have to be combined to say if the password was valid or not. If it's not, you cannot know which chunk was invalid.
mattlong 14y ago
Referring to the Stripe CTF 2.0 [1]. [1] https://github.com/stripe-ctf/stripe-ctf-2.0/tree/master/levels/8 https://github.com/stripe-ctf/stripe-ctf-2.0/tree/master/lev...

stephengillie 14y ago

Instead of storing half of the bits on a server, why not store them on a smartcard, usb drive, or other physical device, to introduce 2-factor to this system?

7952 14y ago
Or even make a cookie value part of the mix. The cookie could be from another domain and only accessible through a javascript API on the browser.

lvh 14y ago

It seems like this relies on an attacker being able to compromise one machine, but not another. Given that these machines are supposed to be quite similar (they're both password databases running the same software), what makes that a reasonable assumption?

zaphoyd 14y ago
The article suggests that the two machines could be running different operating systems and be placed on different networks/locations to reduce the chances of a single attack compromising both systems.
- cookingrobot 14y ago
  It seems really unlikely that any of these leaks has been due to a security flaw in the operating system. I'd think that even in this scheme if an admin account or authentication process is compromised, then the attacker's going to have access to both password stores.
  - dekz 14y ago
    Well, no, because it's a write only model. If the admin account becomes compromised there is no way to read the passwords back. That is of course unless you have root access to both machines, in which case the password can be salted + hashed and then split and stored.

ericcholis 14y ago

Let us not forget an important factor here, don't do things like hashing using SHA-1. While this system sounds awesome, researching common best practices for password storage takes about 2 minutes.

dmansen 14y ago

Why is something like bcrypt not adequate? The article seems to imply that bcrypt could be reversed, but I thought this wasn't the case (with a proper work factor).

jmsduran 14y ago
Bcrypt is a key lengthening algorithm for individual passwords. This article talks about a method that divides a password into pieces to store on physically different machines, that may reside in different parts of the world. I can see bcrypt and distributed credential protection complementing each other to form a rather robust security policy. But then again, I'm not a security expert.
deleted 14y ago
[deleted]
ddlatham 14y ago
Bcrypt slows down a brute force attack considerably, but cannot prevent one. If your password is one of the top N passwords in use, then a determined attacker can still break it. For example, if you set your work factor such that it takes 1 second to verify a password using bcrypt on login to your server, then if your password is in a dictionary of the top 100k passwords, an attacker could get to it within (about) a day using equivalent hardware. Using more specialized (or just more) hardware of course drives it further.
- dmansen 14y ago
  Good point, I didn't think of that.

opyate 14y ago

Security by obscurity never works.

bmohlenhoff 14y ago
Security including obscurity works fine. There's nothing wrong with using it as a component, it just can't be the sole defense.

ZoFreX 14y ago

The number one problem with passwords is that most websites are not storing them using current state-of-the-art methods that are freely available. Whether or not this is an improvement, it doesn't solve the actual problem - developers aren't going to suddenly start using this if their current method is md5(password). That said, it does sound quite interesting from a crypto geek perspective.

7952 14y ago
We always assume that users are going to make security mistakes and build around that. We should assume the same about developers and stop expecting them to build secure sites. That is how the web actually is already, and it is unlikely to change any time soon.
- 0003 14y ago
  Has there been paper, or for that matter a blog-post with a napkin calculation, on the cost-benefit of a proper password/authorization system versus a non-robust system discounted for reputation loss / legal liability for system compromises? I did a few google queries but came up empty. I think this would make for a great PSA.
- nathan_long 14y ago
  >> We always assume that users are going to make security mistakes and build around that. We should assume the same about developers and stop expecting them to build secure sites. I don't follow you. In the first sentence, the "we" is developers of web sites, right? Who is the "we" in the second half? Who are you suggesting should assume developers will make mistakes, and what can/should be done to mitigate that? One possible interpretation is that the second "we" is users, and as a user, yes, I do assume that sites will make mistakes. One reaction is not re-using passwords. But if the user and the site are both naive, I don't see who is left to keep the wolves out.
  - 7952 14y ago
    Sorry my comment was inarticulate. I am arguing for a collective sense of mistrust regardless of who you are.

huxley 14y ago

Mozilla also uses a 2 server approach for passwords on their web apps but instead of splitting the password, they introduce an initial HMAC hash stage using a salt that is stored on a web app machine and then rehash that with Bcrypt for storage in a database on a separate machine. "If an attacker steals one of our password databases, they would need to also separately attack one of our web servers to get file access in order to discover this local salt value. If they don’t manage to pull off two successful attacks, their stolen data is largely useless." http://blog.mozilla.org/webdev/2012/06/08/lets-talk-about-password-storage/ http://blog.mozilla.org/webdev/2012/06/08/lets-talk-about-pa... They have an implementation for Django (ignore the project name, it's a legacy name): https://github.com/fwenzel/django-sha2 https://github.com/fwenzel/django-sha2 Their implementation makes it trivially easy to expire HMAC keys and silently upgrade users to new HMAC keys.

rficcaglia 14y ago

Open source threshold crypto project http://www.utdallas.edu/~mxk093120/paillier/index.php?go=home http://www.utdallas.edu/~mxk093120/paillier/index.php?go=hom...

praptak 14y ago

"Breaking into bits" suggests something about this technique that is not accurate. It does not rely on splitting bits, as in computing n bits and sending each of the n/2 bit halves to different servers. It is closer to hiding one bit by flipping a coin and sending the bit xor-ed with the result to one server and the result of the flip to the other.

eridius 14y ago

These would have to happen in short order, too, because the system periodically refreshes which random half of the snippets of a password are stored on each server. How long would it take for one of the servers to see every piece of the password, on average? If it's not prohibitively long, and you can silently compromise the server, you could just wait. Alternatively, how does it decide to refresh, and how does it decide which pieces to redistribute? If there's some way to attack that mechanism, perhaps you could cause it to refresh faster, or maybe even control the distribution process.

praptak 14y ago
> How long would it take for one of the servers to see every piece of the password, on average? Strong secret sharing schemes are secure against this kind of attack. The schemes are designed so that you cannot infer any information about the original secret from any of the pieces. That holds even if you get a single piece from each of multiple independent "splits" of the same secret. Some examples of such schemes are on Wikipedia and they fall into the "simple but clever" category: http://en.wikipedia.org/wiki/Secret_sharing#Trivial_secret_sharing http://en.wikipedia.org/wiki/Secret_sharing#Trivial_secret_s...

rdtsc 14y ago

> attackers have a range of tools that can reverse this encryption if attacks have a whole range of tools to reverse the "encryption" it either means whoever was in charge of of security is stupid or their attackers have secret or magic weapons

kbs 14y ago

I'd added a link and some notes as a comment on a related post here: http://news.ycombinator.com/item?id=4636655 http://news.ycombinator.com/item?id=4636655 Here is a link to an article with a few more details about the technique being used. http://productsecurityblog.emc.com/2012/10/split-value-cryptographic-authentication-building-advanced-threat-resistant-software/ http://productsecurityblog.emc.com/2012/10/split-value-crypt...