Slashdot Mirror
NYU Group Says Its Scheme Makes Cracking Individual Passwords Impossible
An anonymous reader writes "Researchers at New York University have devised a new scheme called PolyPassHash for storing password hash data so that passwords cannot be individually cracked by an attacker. Instead of a password hash being stored directly in the database, the information is used to encode a share in a Shamir Secret Store (technical details PDF). This means that a password cannot be validated without recovering a threshold of shares, thus an attacker must crack groups of passwords together. The solution is fast, easy to implement (with C and Python implementations available), requires no changes to clients, and makes a huge difference in practice. To put the security difference into perspective, three random 6 character passwords that are stored using standard salted secure hashes can be cracked by a laptop in an hour. With a PolyPassHash store, it would take every computer on the planet longer to crack these passwords than the universe is estimated to exist. With this new technique, HoneyWords, and hardware solutions all available, does an organization have any excuse if their password database is disclosed and user passwords are cracked?."
Maybe I should look at this implementation for my upcoming MMO, which will likely go live somewhere in 2030 :)
...gis sdrawkcab (usually not responding to ACs; don't bother posting as AC)
To be useful, the system still needs to be able to tell whether a single user password is correct (and needs to do so reasonably efficiently). So if someone has a 6 character password (which is dumb) you can just try all possible passwords (there isn't that many possible 6 realistic character passwords). Either lots of them work (which would a problem) or you found the password. And it didn't take all the computers in the universe forever to do so.
Maybe this is a great system, but the hyperbole in the summary is ridiculous.
Let's not stir that bag of worms...
Security isn't about safety. The vast majority of passwords are for identification, rather than security. And the ones that are for security, are for a "reasonable" amount of security. The biggest point is to make breaking it an obviously-intentional exercise -- because that can be made illegal. It's not about stopping criminals. It's about defining criminals.
So go ahead and make your twitter account password super-secure so that no one can ever hack in. And then go home to your cylinder lock, easily pickable, next to the big glass window. Then tell us how safe you are -- remembering that whether or not you keep your twitter password on a sticky note, and whether or not your desktop e-mail is accessible within your home without a password, your children and your wife, and your dog are sleeping behind not such password.
And any locksmith can break into any car, as a ten-second paid-for emergency service. And so can anyone who's watched them do it.
Stop trying to feel safe. Just feel safe. It's a lot easier, cheaper, and much more valid.
Did you leave your oven on?
The problem is a human one, however.
Yes, this makes it harder should someone get to your stored hashes. But it doesn't make it any more secure if people continue to use "123ABC" as a password. Which they will do since that's an easy thing to remember.
So it turns out their system, after a reboot, can't just validate a single user (I guess that was a crazy assumption on my part) - it has to have logins from a number of users before it can authenticate anyone. And if you don't want the system breakable by someone just creating a bunch of accounts (eg. normal users on a public website), these prime logins have to be more "special accounts".
Practically, if you need some special logins after every reboot in order for the system to come online, you're going to have to have multiple people assigned this job. Or one person with N passwords he logs in with. In which case, why not just give that guy a one time pad sort of thing that he primes each server with? I mean, these passwords are going to be unrecoverable and encrypted with, effectively, an unchanging key. So... uh, we have ways to do that.
Oh wait, there's an extension that gets around this, and has the property of "the server can check and eliminate most wrong passwords right after reboot". I'm sure a lot of bosses will like that - it'll reject most wrong passwords. Great.
It's a clever idea, but I think there's some real hard sell problems there.
Let's not stir that bag of worms...
This scheme fails in practice (another over-hyped idea that fails to deliver as has gotten so common these days): It requires a number n of users to log-in before any password can be checked! That is right, the first n-1 have to wait until n are there, because before n good (!) passwords are available to the server, it cannot verify even one.
You must have skipped reading TFA. The "different" logins can be administrative passwords, so that whenever a login is attempted, the user passwords is only one of multiple passwords, where the other passwords can be administrative passwords. The point is to make the password file, when stolen, be safer. If you do not have aceess to the administrative passwords, the cracking of the passwords from the stolen file gets too computationally intensive.
The article says: "if an attacker can read memory on a running server, they can steal passwords unencrypted regardless of the technique that is used".
The article concludes that al we're trying to do is to resist passwords stored on-disk. Congrats. So here's my fix-all solution. When the server is booted, it loads all of the passwords into memory, and then physically disconnects the disk. And we're done. You know, except for the whole entire memory space.
This is just another one of those "make this link in the chain even stronger because once someone broke through it" forgetting that there are dozens of other weaker links that simply have yet to be targetted.
...it would take every computer on the planet longer to crack these passwords than the universe is estimated to exist.
Let's hope they're not creationists.
That problem is already solved. It is called SRP With SRP, even if the attacker has full access to the host, they cannot reverse engineer the passphrase.
To put the security difference into perspective, three random 6 character passwords that are stored using standard salted secure hashes can be cracked by a laptop in an hour.
Really? Okay, here are three NONrandom 6 character passwords that are stored using standard salted secure hashes:
a44a6d60ebc202a7d296d82a7eac5748b7a93474c996e533795d769b297e613c
5529ce75d4bf3bc7b488c8591906cc39bf5ac90feeeb9fbc278b0f98e03cafc6
9de700d2bc4fa3ed30a3459a9cffd7785c10f465c5b9cfb4a83d417e9347f0f9
Start your laptops, gentlemen. I'll even give you a hint. The first password is 123456. The second is abcdef.
While I'm not necessarily all that impressed by this, your specific criticism doesn't seem to be valid. It appears that n accounts are pre-created with null information and assigned out as needed. When those are about to get used up another n are created. There would appear to be a possible attack on a new account by creating lots of dummy accounts to have a big chunk of the password space under your control, but that seems like a pretty uncommon circumstance.
What I like about it is that it seems to protect stupid users from themselves. All the salt in the world doesn't do much for people who just use "password" for their password. It will still fall in the blink of an eye. We often seem to have the opinion that they deserve it for choosing a poor password, but it's still a compromised account.
The threat model is very limited to "attacker got the password hashes", but that is a common threat currently. If you're going to pick one, that's not a bad choice. It's biggest issue may be if tomorrows threat model is significantly different.
Is this really different than a "secret salt" that someone has to load into the server upon reboot?
Instead of requiring N correct passwords to let the server build up its Shamir Secret Store data structure that lets it validate passwords, why not just have an admin type in the secret salt that is hashed with each password?
Without that secret salt, the password file is useless. The secret salt can be protected by N passwords (or maybe it's a hash of those N passwords) just like the Shamir Secret Store data, the only difference is that instead of the server computing it the secret data, the administrator(s) types it in directly. If someone can compromise the server to get the secret salt (or can social engineer the administrator password(s), they can also get to the Shamir Secret Store data, so it doesn't seem any less secure.
Crypto is being supplanted by a lack of rights.
Ob. XKCD:
http://xkcd.com/538/
Now a days you don't have to worry so much about some criminal beating you with a wrench, however you do have to worry about the NSA going to everywhere you actually store information online and forcing them to give the information over "voluntarily" by creating laws under some pretense and threatening legal repercussions, or by just doing it illegally anyway using the usual scare tactics. The same can happen to you personally, and they can pretty much throw you in jail for an infinite amount of time until you produce the password in question anyway.
Anyway criminals are NOT brute forcing huge lists of passwords in the first place. They either take advantage of terrible security in the first place (Hey lets store all the passwords in an unencrypted text file which anyone can access if they know where to look!), software vulnerabilities (Hey your password is super safe, too bad there is that gaping security flaw that lets people bypass passwords altogether!), or social engineering (Hey sure I will give out your password, I'm an IT guy that gets paid 10$ an hour and I really don't give a shit anyway).
So while in an interesting sort of puzzle way this is neat, the actual protections it will afford you is probably very little.
There's no requirement for "special" accounts, though that could be used.
The other option is to just allow your regular users logging in after a reboot to hit the threshold. This would be good for a busy site, where 1,000 users try to log in sooner than an admin can be alerted. That brings up the question of how you authenticate those first N users. The solution is the paper allows a weak authentication before the threshold is hit, so the server could allow "slightly wrong" passwords for the first 30-60 seconds after it starts up.
Good luck contacting the administrators every time you have to reboot any of the servers, especially if it's night in their time zone.
Did you leave your oven on?
You bastard. Did you have to do that?
More music, fewer hits
Is this really different than a "secret salt" [or key] that someone has to load into the server upon reboot?
It's a way to require a quorum of administrators to load the key.
why not just have an admin type in the secret salt that is hashed with each password?
Because then you have to social engineer one administrator. With PolyPassHash, you have to social engineer n administrators.
Get them to write their passwords on a post-it(tm) note and stick it to the server.
Do I have to do all the thinking around here?
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
That completely breaks security, as these passwords have to come from some place and are vulnerable there. Or it means that a large number of people (remember that it requires n users for a security-factor of n?) have to log-in (or rather attempt to) manually.
Sorry, but you do not understand the security and attacker models at work here at all. Sure, this thing looks like a good idea, but only as long as you ignore reality. And BTW, whenever has a server password-list stolen from a not-running server or at boot-time?
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
So this system would work for a web-server where a bunch of people are logging in all the time. It passes test #1: It can be implemented.
However, the security that this system imparts would only help for the first few (N - 1, depending on how many blocks are required to overlap) passwords. Once you have those first few passwords this system provides zero benefit, since you can use the passwords you know as keys to crack any future ones. If users can make user accounts then all you need to do is make N - 1 user accounts and you have completely defeated this system.
So this system creates a HUGE new constraint on your user management system: No accounts can ever be issued to any parties outside of your home trusted zone. I suppose there might be one situation in which this solution might be useful: classified government work. In all other situations this solution is worthless.