Why passwords have never been weaker—and crackers have never been stronger | Hacker News Reader

Why passwords have never been weaker—and crackers have never been stronger

arstechnica.com

115 pointse1ven74 comments

The question about password strength is meaningless without looking at the attack. A 4-digit PIN with a 3 attempt lock-out (and no further information) is more secure than a 10 character password encrypted with MD5.

There will be people who say that it would all be fine if they just used bcrypt, but the fundamental problem is that if you don't use different passwords on every site, you're hugely at risk.

Consider a situation where you've given your "trusted" password to a site that you know does all the right hashing with password storage. Your super password is 20 characters of alphanums with specials and you're feeling pretty smug. You now hear that the site was hacked, but you're not worried as all they can get is the hash and let them just try brute-force, right?

Wrong. They hacked the site. They changed the login form and grabbed your password in plaintext. A hack means that they compromise part of the infrastructure. At this time it's sufficient to just grab database data. Changing presented HTML is possibly a little harder as it needs to stay up for longer, but if someone has access to the database, they probably have access to a whole lot more. This is why lastpass.com is less secure than storing your password database yourself.

TL;DR: make your passwords different.

This. I'm surprised more sites don't utilize a lockout. Even with a 10 or 50 attempt lockout (for a website not PIN) is still better than giving an attacker unlimited attempts.

Lock-outs are tricky to manage. I can flood 50 login requests and have the legitimate user quickly locked out. CAPTCHAs can help but they're annoying and it's cheap to pay people to solve them if necessary.

Forcing a CAPTCHA for a new IP address or when a "you-have-logged-on-from-this-browser-before" cookie added to a lock-out would definitely be an improvement.

Paying people to read the CAPTCHAs would not help you much with a naive brute force attack. Assuming you can break 1 CAPTCHA/second, you could hypothetically try 86400 passwords/day. Breaking a 6 character password would then take you 52^6/86400 = 228826.5 days ~= 627 years. But I bet you'd run out of money earlier! Of course, it's a different story if the CAPTCHA can be OCRed.

The problem that I've seen with lockouts is that they become a route for denial of service attacks.

If lists of usernames/emails are available elsewhere for users of the site - a NastyPerson can reasonably quickly lock your entire user base out of the system (either deliberately, or by a poorly coded password attacking bot).

If you have per-IP lockouts then you're still open to bot-nets and the problem doesn't get much better.

What seems to work best is to slow logins down rather than lock them out completely. Still lets users in, but slows down bulk attacks enough so that the risk is low.

And having nice metrics / reporting tools so that you can spot attacks as they're happening and make appropriate case-by-case responses.

The goal of the attack may be to lockout the accounts, not guess the passwords. That's often overlooked.

Well, there are 2 probable states:

1) Username is not known. No reason the attacker would know this short of a leak / social profile with identical username. In this case, submitting random usernames and getting a hit should trigger a lockout and corresponding alert.

2) Username is known through system compromise. In this case, the account should be locked out and a new password generated just in case.

So I don't really see causing a deliberate account lockout as a primary attack vector other than trying to exploit weaknesses in password reset processes across multiple sites (like what happened to Dan Harmon).

Therefore, I would say that having a lockout mechanism is better than not having one.

I don't need to compromise HackerNews to see your username. Many sites fall into that same category - anything with a social element, comments, profile pages.

You're assuming that the lockout is aimed at an individual. In my experience it's aimed at the site. They're trying to lock out N% of users. In which case going for common names, email addresses, etc. will get you a surprisingly large chunk of the user base.

And that's ignoring the many sites where usernames are public, or easily accessible by a "normal" user that can be used to scrape them for the DOS/password bot.

Therefore, I would say that having a lockout mechanism is better than not having one.

Since I've seen DOS attacks that use them - I'd tend to disagree :-)

Unless you're in an environment that makes them effective.

For example my bank uses a lockout - but it has a private customer number that's not visible to others, along with a separate password and a 8 digit PIN (of which it only asks for three random digits). It's only when two of the three bits of information are correct that the lockout count starts - making bulk lockouts for the site pretty much impossible. So there it's an effective tool to prevent password cracking.

A 4-digit pin with lockout and an MD5 hash are equally insecure in different ways. The lockout scares me when we acknowledge anyone can be social-engineered into giving up any credential, and anyone can forget a credential no matter how simple.

But yeah, at the end of the day, someone who spends a lot of time making cryptographically secure passwords and rotates them every six months is probably less secure on the balance than someone who uses 4-digit pins they rotate every three months.

Here's my crazy crackpot theory for solving the password problem.

Users should have a handful of passwords, in the old security-level style; everyday sites use a short simple password, email a level up, banking a level up again.

But the passwords should not be entered directly into sites. Instead, they should be hashed by a browser feature / plugin, roughly equivalent to bcrypt(password + user-specific-salt + site DNS name). The output of this process is what gets provided to sites. Not all sites will accept the full entropy of bcrypt or similar, so there needs to be a central registry tracking acceptable mappings from the output of bcrypt to the input of a site's password. There's also an issue around sites that share accounts across different top-level DNS names - Amazon in particular - that can also be handled by the same central registry technique.

This way, there is no list of passwords to worry about backing up, losing or handing over to third parties - everyone should be able to remember two or three passwords. There is no Javascript vulnerability like you see with bookmarklets for things like SuperGenPass. Every website sees a unique and specific password, even if the same underlying password is used by different people.

The only thing you need to worry about is your browser getting completely owned, so that the memory space of its extension mechanism is accessed by remote websites. But if the attacker has that level of control, it's not unreasonable to think he has control over a third party password manager too.

What it doesn't do well is revocation and renewal of a password. It also has a single point of failure - if someone somehow gets access to your underlying password, and knows the mechanism and salt, they can open a whole lot of boxes. This, of course, is why I'm a crackpot: I can live with that.

http://passwordmaker.org/

But you still need to realize that this won't last forever. You can crack an application's hashing algo (and know what hash or field they're using for the salt) because 50% of its users picked crappy passwords. Then if you're really dedicated you can work on the double hashed passwords, knowing that most people use the domain as the salt for browser-side hashing... Also a pre-hashed password has to be pretty easy to spot in a list once you've cracked the server-hash.

Scary stuff...

That looks like they're using unsalted SHA-256 as a password derivation function? And they reimplemented every cryptographic primitive themselves?

I'll pass.

Not sure where you got that idea, but the Passwordmaker Pro chrome extension I'm using, let's me specify a different salt (domain of the site is the default), let's me pick the hashing algo, the length of the hash, the modifier, characters to use, etc.

You might want to look at it again.

let's me pick the hashing algo,

All of the choices are hash functions designed to be fast (like SHA-256, the default), which you do not want for password derivation because being fast to compute means easy to brute-force. You can test billions of digests per second with a PC graphics card.

let's me specify a different salt (domain of the site is the default)

Then every user shares the same salt for a given site, which largely defeats the purpose of salting (to prevent rainbow tables).

Yeah the salt default being an issue, is what I said in my initial post. I'm going to go out on a limb and say that doing the following will make you one of the hardest passwords to crack during the event of a weak hashing leak like the linkedin fiasco.

1. Install and use the Passwordmaker Pro extension. https://chrome.google.com/webstore/detail/ocjkdaaapapjpmipmh... 2. Change the default password length to say 40 characters. 3. Add a modifier like bOoo7&jd8$02jf 4. Change whatever other defaults you want. 5. Use a master password that's at least 10 characters long.

BTW it would be easy enough to fork this extension and provide a little more security if you wanted. https://github.com/bitboxer/chrome-passwordmaker/

It's not a crackpot theory, it's awesome - Stanford Password Hash

https://www.pwdhash.com/

"he recovered a 13-character password that he had spent several months trying to crack." -> "The technique is simple enough to do, although it increases the number of required guesses dramatically—from about 26 million, assuming the dictionary Redman uses most often, to about 676 million." -> "8.2 billion Average passwords combinations per second able to be tried by a PC running a single AMD Radeon HD7970 GPU."

Do the math. 676 million should have taken less than a tenth of a second. Unless some rather major details are missing...

I think it took him several months of figuring out the right technique to crack the password (it's not the actual computation time).

26 million squared is 676 trillion, which would take about a day at 8 billion / sec.

nice catch.

From the article:

> An updated version of LAN Manager known as NTLM was introduced with Windows NT 3.1. It lowered the susceptibility of Windows passwords to rainbow table attacks, but didn't eliminate the risk. To this day, the authentication system still doesn't apply cryptographic "salt" to passwords to render such attacks infeasible.

Is this true? Do WinNT-derived systems _still_ not use password salting? If that is the case, my opinion of Windows's security just dropped quite a bit. I know security can exist without salting, and I've not done any in-depth Windows development, but from experience w/backend dev and Linux dev it seems like it'd be pretty cheap to add . . .

The LM hash hasn't been stored by default for years now: http://en.wikipedia.org/wiki/LM_hash.

The problem wasn't the difficulty of adding a better hash algorithm. The lousy hash was kept around to maintain compatibility with network clients that didn't support the new algorithms.

The gist of the article is sites ought to be using BCrypt for hashing passwords and users should be using password manager apps for storing strong passwords (not "password123").

Being the second in command of a development team I made the decision to change ALL our authentication to bcrypt a week into the job overnight (luckily we where storing password encrypted in way I could retrieve all the passwords), had to hack into the database server though. The result was an angry customer service department, and the realization that our security was complete shit. I also ended up working with the IT guys to secure our networks. The real result is that now we don't get huge security meltdowns every couple of months. I got a bonus for the initiative... Oh and the customer service guys still hate me :D

The more I read about this, the more I think that 2-factor authentication is the future, whether it's using robocalls / texted codes sent to mobile phones, or just a security token. It's easier to just add one of the 3 types of authentication* to the mix rather than wrapping yet another layer of complexity around a single one of them.

* (what you have, what you are, what you know)

As far as personal security tokens go, I recently came across the YubiKey, which provides 2-factor auth using OTPs. It looks very promising, but I haven't used it myself, so I can't provide any anecdata on it.

Google authenticator is great; can be used on many sites (gmail, last pass, aws) and is based on an open standard that is to implement on your own servers.

Duo Security, from some of the Open{BSD,SSH} guys, offers a nice two-factor auth layer that's pluggable into any web or online service; push notifications, SMS, or voice. Similar to Google Authenticator except that Duo isn't limited to Google supported services (although they did take an investment from Google Ventures).

I have been reading the list of 2 factor at lastpass [1] and in addition to mentioning the yubikey, it talks about the grid multifactor [2] - probably about on par with what was used in WW2 but it seems extremely simple, low tech solution to multifactor that doesn't require computers, phones or electronics - solving that problem of 'something you know' + 'something you have'

[1] http://helpdesk.lastpass.com/security-options/

[2] http://helpdesk.lastpass.com/security-options/grid-multifact...

Sounds like you're referring to a one-time pad[1], which is what that grid looks like. Google's 2-factor auth has a simpler version of this -- they just give you 10 or so one-time passwords. I like the grid; it seems to have a much longer potential "lifetime" of use.

[1]: http://en.wikipedia.org/wiki/One-time_pad

I hope not. Two-factor auth ties you down to a cellphone (or physical token) while giving you only marginal improvement in real-life usage scenarios. (You are not going to enter a new token every time you check your email or Facebook.) We have higher-level problems with authentication that need to be solved.

I never said I liked it, I just thought that's where we might be headed. =/

As far as that goes, Google's 2-factor auth mitigates this a bit, with its "keep this auth instance valid for X days" option. (They also have a new "permanently auth this computer by adding it to a trusted list" option, which IMO defeats the point.)

More and more I feel like passwords are a fundamentally broken system. We need a better system of locks and keys.

What is is, I don't know. I just know that it's not "passwords".

Especially when there are still sites that limit you to like 8 characters out of a highly restricted set. Usually of course these are banks.

I m in favor of things like browserid, provide a centralized point of failure. It's futile to assume that because people can have different passwords they will have them. Most people use 1-3 passwords, and it sucks whenever you have to learn a new one.

Hypothetical question - say I'm an idiot and I already have a database full of md5-hashed passwords. What do I do now?

The best I've been able to come up with is bcrypting the md5's. But unfortunately, while bcrypt^-1(ALL STRINGS) is hard to compute, it's not clear that bcrypt^-1(range(md5)) is. I see no compelling reason why it wouldn't be, but I don't know enough about the subject to offer a strong claim.

Can any experts offer advice on this?

(I'd also replace the `bcrypt . md5` password with a regular bcrypt one after the user authenticates.)

Add a new bcrypted password column.

Alter authentication so that it uses bcrypt column if populated.

Alter registration/password changes so that it populates bcrypt by default.

As old users log in (and you therefore have access to their plain text password and know that it's valid) populate the bcrypt with the correct hash.

After a period of N weeks when you've basically migrated all of your active users, do a forced password reset on the rest.

Kill the MD5 column.

Done :)

As I said: "I'd also replace the `bcrypt . md5` password with a regular bcrypt one after the user authenticates."

The question is what to do to protect passwords starting today?

Apologies. I'm an idiot who can't read a question :-)

bcrypting the md5s sounds like a good approach.

bcrypting your md5 hashes is much better than having the md5 hashes around for various reasons. The major reason is that there are many md5 rainbow tables, and if your md5 hashes ever leak out, a huge number of your passwords will be known almost immediately. bcrypt+md5 rainbow tables are much less common.

If you can, also add a user-specific salt (username is the obvious choice).

In theory cracking bcrypt+md5 is easier than plain bcrypt, because users could have passwords with greater than 128 bits of entropy. However, the vast majority of users won't, and generating a 128-bit rainbow table isn't practical.

...bcrypt+md5 rainbow tables...

I don't think this is possible, since bcrypt has a built in salt.

Does the fact that you bcrypt and md5 undo this salt? I.e., is bcrypt(md5(password), salt1) == bcrypt(md5(password), salt2)?

No, certainly not, as bcrypt doesn't "know" it is getting md5, there is nothing wrong with passwords being hexadecimal strings. Sorry, I miswrote there.

Since MD5 hashes and bcrypt hashes are recognisably different: when the user next successfully logs in, check if they have an MD5 hash; if they do, use the password they just submitted (that you know is correct) to generate a bcrypt hash and then update your password database with that.

If you have a large number of inactive users, this might not be as effective (you'll still be left with lots of MD5 hashes in the event of a dump) but for other sites it can be quite useful.

You can also use the same strategy to increase the work rate of your bcrypt hashes in the future.

What kind of database are we talking about? The kind of database where you can't reset users' passwords?

Someone asked a question similar to yours a while ago. Maybe the answers may be of help: http://news.ycombinator.com/item?id=4076257.

I guess you could run bcrypt on all your database's md5 hashes and do something like:

    if entered_password.md5.bcrypt == stored_password:
        stored_password = entered_password.bcrypt
        login()

That way, you will only have to store the bcrypted md5 hashes, until the next time someone tries to log on - assuming that's the kind of back-end you have.

If inverting bcrypt(md5(.)) was easy then you'd have a preimage attack on md5: given your value md5(x), compute a bcrypt digest of that and attack that instead. (Which is not exactly the same as inverting bcrypt(md5(.)) given a dictionary of likely inputs, though.)

Anyway, if there's any input set X for which bcrypt(X) can be inverted more efficiently than brute force, then you could say that bcrypt is flawed. If that set is the random-looking hashes of user passwords, instead of a carefully constructed one designed to attack bcrypt, then you can safely say bcrypt is catastrophically broken.

Anyway, if there's any input set X for which bcrypt(X) can be inverted more efficiently than brute force,

Here is one:

    [ (bcrypt x salt) | x <- dictionary, salt <- all_bcrypt_salts ]

Now I do think it's unlikely that range(md5) is a good domain on which to attack bcrypt, but I also recognize I'm not smart enough to be sure.

I don't get what you're saying here. Is your input set a bunch of outputs of bcrypt? Is your input set `dictionary`? Either way, how can you invert the output of bcrypt more efficiently than brute force?

In my particular example, you need only brute force it over a dictionary, which is not that hard to do (even for bcrypt). That's because the input set for bcrypt is being artificially constrained.

My concern is that artificially constraining the input set to range(md5) might similarly make brute forcing (or other attacks) easier.

"The whole password-cracking scene has changed drastically. In the last couple years. You can look online and you can generally find passwords for just about everyone at some point. I've found my own username and passwords on several different sites. If you think every single website you have an account on is secure and has never been hacked, you're a much more optimistic person than I am."

This guy is realistic. And he is right. I started revoking access for my google account from a lot of websites.

BTW I've seen a blog post that a guy was able to access his stackoverflow account by getting the session cookies (which was very easy, the parameter names, etc) just by using a cookie chrome extension.

This guy is totally right.

"If you think every single website you have an account on is secure and has never been hacked, you're a much more optimistic person than I am."

This reminds me: I need to go through my 1Password DB and change all the passwords. This is a PITA but I only do it quarterly, and 1Password syncs nicely to my phone and iPad, so it's not the end of the world.

It would be a huge help if there was a standardized web API for changing passwords on a site. I don't know how many sites you need to change passwords for; I've got several hundred, all unique, and I certainly don't change them quarterly.

(It would also help attackers, of course - they could instantly lock owners out of whole heaps of accounts once they got a password that got reused. On balance, though, I think the benefits would be positive, since a motivated hacker can already lock people out of high-value accounts, and the drudgery factor of changing passwords regularly is very high.)

This would be nice. Even better would be to do away with passwords entirely in favor of email + physical token. There's no getting away from the fact that crackers will always get access to a certain number of passwords; properly incentivizing people to pick excellent passwords seems like a fool's errand. Cue xkcd here. I hold out some hope that Apple (my computing vendor of choice) will roll 1Password-like functionality into the OS (both of them). Only a default-secure system will get the general public into a more secure state -- how long has the computer industry tried to strong-arm people into strong passwords, only to be defeated by 12password12 &c.? It's not that users are stupid, it's that the technology to secure computers is an utter failure.

Well, there's the Keychain. But its password generation is hidden deep in the program, not right there when you're asked to create one. And it doesn't synch to anything, not even iOS devices, so it's pretty much useless for generating passwords that are, say, 2k of line noise.

It would be totally awesome if Apple acquihired 1PW or LastPass or somesuch, and set things up so that it's always right three, helpfully offering a new super-entropic password whenever you're joining a new site.

This is why websites should start to adopt solutions like Rublon (www.rublon.com).

7 reasons why you should add Rublon to your website http://blog.rublon.com/2012/why-add-rublon/

I'm the inventor of this technology. Sorry if this looks like advertising, but I think that the problem with passwords nowadays is huge nowadays and has to be solved. BTW: We're releasing a new Android app in a few hours.

The real solution is to switch to public keys. No more shared secrets - you just prove your identity by using your private key to sign an authentication challenge.

I lost my private key. Now what?

I'm using my friend's laptop; I don't have my private key with me. Now what?

I'm travelling and forgot to bring my private key with me. Now what?

(Similar questions apply to password managers as well, but I'm curious as to what the problems/solutions are for PKI.)

I believe, in an ideal world you'd have your private key stored safely on a private webserver, or maybe your mobile phone.

you mean the mobile phone who's data can be accessed remotely by apple, google, htc and god knows who else?

In an ideal world, we wouldn't need to worry about unauthorized access. Unfortunately, that world doesn't exist.

But I sincerely hope a requirement for me to use the internet doesn't demand we have a private server instance or a smartphone of any variety (my Nokia candy bar variant serves me just fine).

I can think of many problems we'd need to account for (lack of internet, dead/lost phone, corruption, older folks, etc).

You know, sometimes the simplest problems are the hardest to solve. You'd think right? "What's the best way to know if this guy is who he is claiming to be?"

1. Shared secret/Password - He tells me something during registration and then I use that information to verify if he's saying the same thing when he want access the site.

2. PKI - Describes itself.

3. Something he claimed to have during sign-up, so let me check if he has it now.

The problem is, every system is going to have a point of failure/point of absolute control. This is because, you want someone to be able to reset their password/public key/auth token if they forget/misplace/get stolen. Sure, things would be a lot easier if you left the liability on the user, by explicitly stating that if Acts of God (legal term) happen to him, you are not liable. But in this day and age where I see every service tending towards dummifying and hand-holding, I don't see this approach being popular at all.

In the above approach, by pushing all liability onto the user, you tell him that HE and ONLY HE is responsible towards the safe storage of his credential. It's not like in real-life, people can't come up with a gun pointed at you and tell you to give up your auth token, assuming they MitM'ed your password.

I'm not sure we really disagree, if I understand your response correctly. I _do_ think there can be improvement (and, probably, should).

My main objection was calling for using a device that is expensive, requires special/additional phone plans, and doesn't _really_ solve the problem (especially for most of the global population). I have a rather diverse set of friends by age, income and technical experience - and smartphones aren't the majority.

You are correct. I am not in disagreement with you. We definitely need a way to authenticate people. But like I said, authenticating systems need to be fool-proof enough to not allow false positives yet flexible enough to allow people to screw up and get a fresh start without wiping all their data. These two goals, by definition are the equivalent of trying to look towards the left and right at the same time.

I like this idea. But as a novice, how would you, say sign in to gmail? Would you download a file, sign it, and upload it again? That seems quite time consuming as compared to current day password.

I'd really wish some sites would not force me to change the password every other month or every time I clear my cookies or use a different IP: every time, I have to use a simpler password because I just can't come up with a better one without having to write it down somewhere...

3-5 tries with a half hour lockout with an email alert seems like a good solution to me...

Definitely annoying to have to reset pw frequently but the shorter passwords part can be avoided by using a secure pw db like keepass (keepassX on Mac). Storing the db file on dropbox makes it very convenient. Throwaway pw aside, you really only need to remember 3 pws: db, dropbox, and main email (for convenience). I have many passwords I've never even seen thanks to keepassX.

If it doesn't work easily on a mobile device, it might as well not exist.

Keepass has mobile applications that synchronize easily via webdav or Dropbox.

Unfortunately, you can't create new records from the mobile device with Keepass (at least, with the app I'm using; there are others). My technique is to not create high-value accounts from my mobile and for low-value accounts, I'm OK with just using a semi-secure, temporary password that I update when I'm back in front of the desktop.

Unfortunately, you can't create new records from the mobile device with Keepass

Perhaps pwSafe is the app you need? Works beautifully on iOS and syncs with Dropbox and/or iCloud too!

https://play.google.com/store/apps/details?id=com.android.ke...

Works just fine with version 1.x files

I don't write down passwords, I write down password hints. For example, "b + 7 + z" could equal baby753zyxw. A single letter can signify a word/string, and a single number can signify a larger number. I have about 20 strings memorized than I combine in various ways.

The article talks about brute forcing hashes. This is why a good login system will rehash the password multiple times to exponentially increase the length of time it would take to brute force the passwords.

Accounts could still be cherry picked but it would stop blanket brute forces. This is why BCrypt is good.

How does re-hashing exponentially increase the amount of time brute forcing takes. The time it takes to do N iterations of a hash is N times as long as 1 iteration, so the amount of time it takes to make M guesses is still just N times as long.

Why aren't security experts and hackers mixing and matching the characters that make up the password? I.e. instead of super!!!think3rs, try Supr3Think0rz. Is the added required processing too large of a trade off?

I don't know what the best practices are, but some crackers definitely do do that. And yes, the added processing is generally too large for non-cracking applications.

Reply on news.ycombinator.com