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

http://www.technologyreview.com/news/429498/to-keep-passwords-safe-from-hackers-just-break/

by iProject • 14 years ago

45 30 14 years ago

technologyreview.com

circlingthesun• 14 years ago

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

lucian1900• 14 years ago

And is also likely to suffer from vulnerabilities because of its complexity.

mguillemot• 14 years 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• 14 years ago

Referring to the Stripe CTF 2.0 [1].

[1] https://github.com/stripe-ctf/stripe-ctf-2.0/tree/master/lev...

stephengillie• 14 years 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?

79523• 14 years 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• 14 years 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• 14 years 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• 14 years 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.

ericcholis• 14 years 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.

dmansen2• 14 years 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• 14 years 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.

ddlatham• 14 years 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.

dmansen2• 14 years ago

Good point, I didn't think of that.

xyzzy123• 14 years 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.

opyate• 14 years ago

Security by obscurity never works.

bmohlenhoff• 14 years 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• 14 years 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.

79523• 14 years 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• 14 years 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• 14 years 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.

huxley• 14 years 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-pa...

They have an implementation for Django (ignore the project name, it's a legacy name): 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• 14 years ago

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

praptak2• 14 years 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• 14 years 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.

praptak2• 14 years 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_s...

rdtsc• 14 years 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• 14 years ago

I'd added a link and some notes as a comment on a related post here: 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-crypt...

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

Related Stories