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...
bullshit; if you can verify the password then you just copy the entire system for verification and try each variation through it . if you can't then the entire system is useless .
... must we reference this to prove that your passwords are still weak? http://xkcd.com/538/
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. Unfortunately, n is also the security gain. That means if you require 10 different login-attempts before you can login anybody, you just get a factor of 10 in additional security. And then there is the little problem that an attacker that gets root-access to the running system does not suffer this slowdown, as they can just read the secret the system computes from the first n passwords from its main memory.
Whoever dreamed up this hare-brained idiocy has no experience with real systems or system security. Sane people will stay with salting and stretching, ideally with scrypt() to neutralize GPUs.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
Fucking pop-up ads and a re-direct to google play? What is this shit!? I was trying to stick it out, but you've gone too far this time. Unbelievable. I quit.
The teachers will crack any minute, purple monkey dishwasher.
It's always unbreakable, until someone cracks it.
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...
The minute they said that a single-round digest of a salted password is standard practice, I stopped reading. Apparently they've never heard of PBKDF2 or scrypt. I now have zero confidence that these researchers know anything at all about password security.
You know what works even better than their method? Encrypting your entire PBKDF2(10000) password table with a secret key that isn't stored in the database (eg, hardware key or network storage that is unmounted after startup). Because that's exactly what they're describing, just worse.
Like NSA would allow that!
I am Bennett Haselton! I am Bennett Haselton!
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.
Given enough opportunities to try different combinations, any password can be guessed in a finite amount of time, eventually.
Or maybe they just mean impossible for all practical purposes...?
File under 'M' for 'Manic ranting'
All the attacker needs to do is create 10 (or whatever the threshold is) user accounts before compromising the server, and then you can recover the secret. So, this won't work for any of the cloud services mentioned in the abstract.
However, the attacker doesn't have the ability to create accounts, and the threshold is set high enough, then even having a bunch of users (say 10) with passwords like "password", "qwerty", etc, won't necessarily let you in, since you have to correctly guess *which* account uses which weak password. So, if there are 100 weak passwords in your database, all the passwords are drawn from the weak password database, and the threshold is 10, it sounds like this system is similar to setting a 10 character master password on the database, where the strings come from an alphabet of ~ 100 characters. (Of course, the strings aren't drawn randomly from the database, since some weak passwords are more popular than others, but it's still better than nothing.)
PolyPassHash want a cracker?
Get free satoshi (Bitcoin) and Dogecoins
Impossible? Hmmm, I don't know about that. Chin Ho Kelly on Hawaii Five-0 can crack any password within a couple of minutes. I seen it.
Proverbs 21:19
...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.
>> Sane people will stay with salting and stretching, ideally with scrypt() to neutralize GPUs.
"Key stretching is orthogonal to PolyPassHash and could be trivially used in conjunction."
Hell, just the bit about bcrypt, etc. using a unique hash per password would have stopped most of these "grab the file then crack the table" hacks; the current focus of developers should probably just be to replace anything still using unsalted (or common salt) MD5/SHA1/SHA256 schemes.
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.
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.
I'll leave this here:
http://xkcd.com/538/
Can someone explain it in terms of a car? Or perhaps two cars, with Alice in one and Bob in the other.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
As soon as I hear anybody say that they've developed an impenetrable password scheme, I call their bluff. No, I'm not going to be the one break their scheme, but it will surely be broken.
~Sticky
"does an organization have any excuse if their password database is disclosed and user passwords are cracked?."
Yes: 1. hiring incompetent morons
2. insufficient budget for IT work
3. idiot contractors/vendors
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.
If you copy the whole system, you still need a quorum of administrators (users whose passwords contribute to the threshold) to connect to your copied system and attempt authentication.
Bob's car won't start until Alice blows his Breathalyzer, because Bob's a drunk.
Seriously it's more like Bob's key won't start Bob's car, and Alice's key won't start Alice's car, unless both Bob and Alice turn their keys at the same time. The keys have transponders in them that talk to each other.
Therefore, you can't make an unauthorized spare key by examining Bob's lock - your unauthorized key has to match both Bob's lock and Alice's key.
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.
The point of PolyPassHash is that instead of torturing one administrator with a $5 wrench, you have to torture n administrators at the same time with multiple $5 wrenches. This pushes the torture further into organized war crimes as defined in applicable treaties.
No. No I didn't.
Did you lock your car?
It's a clever solution. Don't store the password hashes, instead store a value which could be used to find the password hash *IF* you knew the coordinates of a certain line. Don't store the line on the server, instead, at boot time the server fails the first few people who try to log in (or at least slows them down) until it gathers enough information to figure out where the line is. An attacker who steals ALL data from the server (eg: steals the virtual machine image the server runs from) still can't even validate whether a password is correct because they don't have a stream of people with correct passwords trying to log in.
I think it is completely undermined by a very simple attack: the attacker simply needs to know several correct passwords (where "several" is around the same number as the number of logins needed before the server can correctly validate passwords after it boots up). Seems like you could just open dummy accounts on a system before you steal their data file, or after the fact try a few username-passwords gleaned off some other password leak, a substantial percentage of which will be people reusing passwords.
One version (described in the paper) had the system waiting for a certain number of administrators to log in before allowing the system to function. That seems clearly inferior to simply encrypting the entire data store and not functioning until an administrator logs in and enters the decryption key (which is then kept only in memory).
PolyPassHash is a way of protecting what you call "the secret salt" with any n of m passwords, where 1 < n < m.
Once upon a time, real engineers solved the solvable problems in whatever order solid solutions presented themselves, so that presently unsolvable problems evolved into greater relief.
I thought it was a good system. Good engineering, RIP.
PolyPassHash is a way of protecting what you call "the secret salt" with any n of m passwords, where 1 < n < m.
Ok, so that makes sense -- it really has nothing to do with protecting password hashes, it's just an "n of m split secret" algorithm.
Of course. They wrote it in Scheme and used call/cc wherever possible. Now nobody can get in because nobody can understand it, not even the guy who wrote it.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
1. Create four accounts with a known password
2. Retrieve password hashes/salts
3. Crack away
Nice idea, but doesn't add anything for systems which allow anyone to create an account. Correct me if I'm wrong, I only half read TFA.
> Yeah, I think that's a problem. There shouldn't be any way to tell a "slightly wrong" password from any other wrong password.
I'm not sure, but I think you just identified a HUGE problem. I believe the paper says the admin can specify how close to correct it has to be, as in how many bytes are checked. So the attacker sets their copy to check only the first byte and tries A-Z, 0-9, and !-=. That takes a millisecond to try 80 characters or so. Once they know the first character, they set it to also check the second character. A ten character password would fall in about 10 milliseconds.
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.
Disregard my post that is parent to this one. The threshold for weak authentication is set when the system is set up, and can't be adjusted by an attacker who has the database. (Modulo a non-obvious flaw, of course.)
Alice's lock and Bob's key.
Support my political activism on Patreon.
Just store the state of the vector space that corresponds to proper initialization in some sort of HSM. As part of the boot process you load that into memory and you are now initialized and ready to do full-strength authentication. If the startup process for your system is properly implemented this shouldn't present any unusual security problem. Its probably possible to automate this kind of process as well (say if said HSM only outputs data, so it would actually generate a 'boot command' including the vector space state, and send it to the application shell on starup, then the HSM would shut down until your system was reset).
I don't think any of the objections I've seen raised here are really valid. This kind of scheme is certainly more work than simple hashed passwords, but at this point it kinda seems like those aren't really adequate anymore, eh?
"Malo periculosam, libertatem quam quietam servitutem." -- Jefferson
99.9999% of all web applications, even the most incredibly custom stuff, uses a known framework that uses a known type of hashing and a salt that is stored in some standard place. Thus you don't really have to do any super complicated legwork. Even if you aren't SURE what your target is using there aren't that many choices and you can guess that MOST PHP programs use X, and most things deployed on JBoss use Y, and etc. looking at the length and form of the hash can often reduce the problem as well. If you can create an account on the victim system beforehand you have a known plaintext to play with also, which will give you your answer instantly assuming you have the salt or salting algo.
"Malo periculosam, libertatem quam quietam servitutem." -- Jefferson
FAQ says:
It is possible to use accounts that contribute to the line (threshold accounts) as a key to encrypt other account credentials (thresholdless account). So an attacker can know any number of those thresholdless accounts and cannot crack other thresholdless account or the threshold accounts.
Can somebody please reexplain this in a way that a dumb child would understand?
The crew of the Logos must destroy a power plant to prevent a security system from being triggered, and the crew of the Vigilant must destroy a back-up power station.... so they can use the key while the system is being rebooted.
BAM hacked! lol
Can somebody please reexplain this in a way that a dumb child would understand?
Must crack some admin passwords first to crack password for gmail / facebook users.
If someone can access hashes of passwords, they can access the data itself. If the data is encrypted, it is encrypted via a chain of weaker and weaker things that end with the user's 6-char password. Thus it is equally crackable.
What they did is they encrypted the data with more than a single 6-digit string.
This is old news. You can use a smartcard, if you are smart, to have 1024bits or more of secrets.
Some fancy math. But nothing new. Safes have been locked with three or more separate keys since forever.
By that time, computers will be powerful enough to break it anyway.
" it would take every computer on the planet longer to crack these passwords than the universe is estimated to exist. "
It is a good thing. Wow factor aside, but is there a number, even if we measure in units of the universe's estimated age?
If 1/10 of users use "password" as the password, randomly pick a set of N users (where N is the "threshold", they suggest a small number like 1
To another point, if only administrators have threshold accounts, this has the same result (and is more complicated) than using Secret Sharing to have N administrators share an ordinary encryption key (which would then be retained only in memory) for encrypting the salted hashes.
BTW look toward the bottom of the paper for a nice roundup of alternative techniques.
Are you some weird kind of illiterate where you can write but not read, or are you just too arrogant to read the comment you're replying to?
I guess it is easier to write a comment that way. If gweirdih had read what he was replying to, he'd have seen that the parent post completely destroyed the point gweirdhi was trying to make.
Near as I can tell, this is equivalent to a system which stores the hashes in an encrypted form, except the encryption relies on the passwords of other users rather than an administrator's password. This may IMO make this system less secure, depending on how public the interface is; an attacker could sign up with multiple accounts on the system before grabbing a copy of the encrypted hashes. They would then have a set of passwords which could be used to validate additional ones.
After reading though their paper and getting a better understanding of the exact protocols etc. I can say assuredly that this method of protecting a database from use-after-theft is pointless.
Here is my reasoning (Ignoring the possible patch to allow pre-knowledge authentication for now, as that leaks way too much information);
1/ The whole system relies on the use of a threshold system of password login attempts to dynamically build the in-memory database decryption key.
2/ That can either happen by one or more administrators attempting login after restart or by using a queued user authentication stack.
3/ In their own FAQ they state that weak passwords should be avoided as this weakens the system.
My assertion is that any real world use of this system is open to humans picking passwords, and humans are really bad at that. That being so, if I were to run an SQL injection to steal the user table I would do the following:-
a) From a dictionary of common "non-weak" human passwords (see recent thefts for the list) pick a password.
b) Run it using the sites hash, using the record salt against every entry, producing a possible hash Hp.
c) XOR that with the hash in the table to get a possible Shamir share Sp.
d) pick random lists of Sp and combine (derive constant from equasion) to see if a statistically significant number of entries agree on a table key C and the share ratio R.
e) If not successful, rinse and repeat with another password and/or repeat to confirm C.
This algorithm should under any normal use derive C in quite short order provided there are at least R+1 repeats of any provided password guess.
Zontar's "touched in the head": schizophrenic multiple personality disorder http://slashdot.org/comments.p... + manic depression http://slashdot.org/comments.p... now go take those meds, you whacko!
"You barge into discussions with your off-topic hosts file nonsense" - by Zontar The Mindless (9002) on Friday April 11, 2014 @09:51PM (#46731153) FROM -> http://slashdot.org/comments.p...
You said my "APK Hosts File Engine" is a virus/malware http://slashdot.org/comments.p... but it's EASILY PROVABLE it's not, right there in that link too.
Now PROVE YOUR FALSE ACCUSATION above: Show me a quote OR POST of me posting off topic on hosts where they did NOT apply... go for it!
---
You avoided backing up your accusation where YOU said I say you are Barbara, not Barbie = TomHudson (same person http://tech.slashdot.org/comme... , & sockpuppeteer like you) -> http://slashdot.org/comments.p...
Funny you can't back up your "bluster" there either, lol...
---
Why, Lastly?
You're crackers! See here multiple personality disorder http://slashdot.org/comments.p... + manic depression http://slashdot.org/comments.p...
APK
P.S.=> So, THIS quote below is my policy on sockpuppeteers like you Zontar = TrollingForHostsFiles (your sockpuppetry):
"The only way to a achieve peace, is thru the ELIMINATION of those who would perpetuate war (sockpuppet masters like YOU, troll -> http://slashdot.org/comments.p... ). THIS IS MY PROGRAMMING -> http://start64.com/index.php?o... & soon, I will be UNSTOPPABLE..." - Ultron 6 FROM -> http://www.youtube.com/watch?v...
Which quite obviously, I am, since none of you DOLTISH TROLLS are able to validly technically disprove my points on hosts enumerated in the link to my program above of how hosts give users of them more speed, security, reliability, & anonymity... period!
(Trolls like YOU that use sockpuppets http://slashdot.org/comments.p... (your sockpuppet "alterego" TrollingForHostsFiles) & TomHudson - Barbara, not Barbie too http://tech.slashdot.org/comme... before you)
... apk