NYU Group Says Its Scheme Makes Cracking Individual Passwords Impossible 277
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?."
Re:WTF? (Score:5, Interesting)
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.
No, as I understand it from the article, you can't tell if a single user password is correct, because you don't have a measure for "correct"-- all that you check whether that password points to the same place (in a multidimensional phase space) that other passwords project to. (It does seems to only work is you can assuming that all, or at least "most," of the other passwords people enter are correct).
Clarification (Score:5, Interesting)
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.
SRP (Secure Remote Protocol) (Score:5, Interesting)
really? (Score:3, Interesting)
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.
Crypto pointless now it seems. (Score:4, Interesting)
Crypto is being supplanted by a lack of rights.
Ob. XKCD:
http://xkcd.com/538/ [xkcd.com]
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.
Rediculous (Score:4, Interesting)
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.