Salt with your Fries?

Overview

When storing a password or other sensitive data, a salt is a must. This post deals with the nitty-gritty of salt generation.

If you're here for simple advice, use bcrypt with a nice wrapper which handles salt generation for you.

Properties of a Salt

A decent salt must satisfy two minimal requirements: 

• Unique
• Unpredictable 

Uniqueness is fairly obvious, if your password database uses a static salt for all passwords, then it only defeats pre-computed dictionaries and rainbow tables. It does not protect you after your database is leaked, and your attacker knows the salt -- they can simply re-compute the dictionary using the salt and often break many passwords this way. Having a different salt for each password will force the attacker to create a dictionary for every password in the database.

Unpredictability is not immediately obvious. However, take a well known open-source system that uses a sequential integer as the primary key in the database and it's salt. This clearly satisfies uniqueness. However, if an account (say, for example, admin) is always the first account on the system and therefore always uses the salt "1". An attacker can pre-compute their dictionary with salt "1", when the database is leaked, the attacker can simply look up the hash value in the dictionary and see the password.

This however, presents a major problem. If I can't predict the value of a salt, how can I be sure it will not collide & violate uniqueness? 

The first, naive solution, is to simply throw away colliding salts. However, once you have a certain number of passwords, you'll spend all your time generating salts. 

The better solution is to ignore collisions, but make them extremely unlikely. With sufficient randomness, we can also ensure that collisions happen extremely rarely, even in a system which uses sharding or other "splitting" methods. It is this solution that we will explore. 

Unique Violations

The primary strength of a salt lies with the fact that an attacker must attack each password individually, or for our purposes, almost individually.

If each password can be expected to share a salt with two or three other passwords, then this is quite bad, as the amount of passwords that an attacker can crack by trying the salts is non-zero.

Ideally, an adversary picking a salt at random from a leaked set of passwords should have a negligible chance of picking a salt which will have suffered a collision, hence attacking any single salt gives them a negligible chance of breaking more than one password with that salt.

A simple manipulation of the Birthday Paradox allows us to determine the minimum bit-length for any salt conforming to this requirement, the equation that derived is:

b = log₂(n² - n) - log₂(p) - 1

Where p is the probability we're looking for, n is the expected size of the password database and b is the bit-length of the salt.

So, for our requirement on a system that's expected to use 10,000 passwords, and have an attacker not expect to have more than one collision in that set would need p set to 10^-5.

b = log₂(10¹⁰ - 10⁵) - log₂(10^-5) - 1
b = 48.83

Or about 48-bits of entropy, minimum.  

Existing Standards

NIST and RSA both give recommendations on the minimum salt length to be used in any key derivation function. NIST (NIST-SP800-132) recommends 128-bits and RSA (PKCS #5 v2.1) recommends only 64-bits. 

Most BCrypt implementations, when asked to get a salt for themselves will return a 128-bit salt, which is more than enough, and happens to comply with NIST's recommendations.

It is probably the case that RSA's recommendations are not sufficient for use in large organisations.

Conclusions

Simply put, if in doubt, just use bcrypt.

However, for your organisation, you can easily calculate the minimum bit-length required to ensure the desired amount of salt collisions. I would always plonk myself down on the safe-side of town and go with NIST's recommendations of 128-bits.

You should always bear in mind that poor random number generation from your OS or other source can lead to more collisions. The post above assumes good, uniformly distributed salts.

Cracking Postgres Passwords

Overview

This article is a brief overview of using HashCat to recover a Postgres 8.4 password.

Hash Format

The format for Postgres is md5(secret || username) where || denotes string concatenation. 

HashCat

HashCat as a tool is more traditionally associated with oclHashCat-lite and oclHashCat-plus, which delegates the work to the GPU, significantly increasing the cracking speed.

At this point, I am using HashCat because of it's simplicity and flexibility in attack modes and hashing algorithms, however, most of what is written here could be translated for a suitably configured oclHashCat-lite and run on the GPU.

Retrieving the Hashes

In Postgres, if you have read access to pg_roles, you can simply use:

SELECT username,passwd FROM pg_roles;

This will show you a result like:

   usename   |               passwd                |
-------------+-------------------------------------+
 postgres    | md50f7e63611a98a9936285c7d609b044da |

The field "md50f7e63611a98a9936285c7d609b044da" is the md5 hash. Simply strip it down to just the hash (removing the "md5" from the front to), and that is what you're attacking.

Using HashCat

If you download HashCat from their site, you'll likely be able to follow these instructions exactly, but these instructions were written using HashCat v0.42.

First, you must make a hash file:

echo 0f7e63611a98a9936285c7d609b044da:postgres > hashfile

Then you may run HashCat:

./hashcat-cli32.bin -m 10 hashfile -a 3 ?a?a?a?a?a?a

The flags we're using are as follows:

• -m 10 : Use the hashing scheme md5(pass.salt)
• -a 3 : Use the brute-force attack mode.
• ?a?a?a?a?a?a?a : Search all passwords up to 7 characters from the character set [a-zA-Z0-9] + symbols.

Results?

Mine is still running vs. a password of my choosing, but after around 10 minutes, HashCat reported that it was now trying to crack all 6-character passwords and would take on the order of 16 hours to try them all.

HashCat's current status is that it's trying 12.22M words on my CPU every second. I'll update this blog when real results are found. I suspect at this rate, I'll give up after a couple of days, as all 7 character passwords will take on the order of 2 months.

Update

Having finished running HashCat on my machine with the above arguments, the search finished after a full 15 hours, however, it did not find the password, as it was longer than 6 chars. For this experiment, I mainly wanted to confirm that I could get HashCat to run and attempt to crack a password. The hash given above is for a *very* long password, that actually has more entropy than an MD5 hash!

Doing Passwords Wrong with PayPal

What They've Done Wrong

PayPal do a lot to argue that their system is secure, however, their outward-facing practices don't necessarily live up to their own hype. If you can't make a security conscious user feel secure about their password policy, how do you think that one might feel about them having my EMV card details?

Let's look at the problems with their passwords.

Minimum Length

PayPal's minimum length is too low at 8 chars. This gives the minimal password an entropy of approximately 38-bits. Most folks can brute-force that on their phone these days. Even DES thought that 56-bits was good enough in '77. Times have changed (no, they haven't gone backwards!)

Maximum Length

They enforce a maximum length which is too low (it exists!?): 20 chars. This gives the absolute maximum entropy of a password of around 132 bits. I like to make my passwords around 256 bits. It's 2013, let me make a passphrase that's more than 20 characters, it's not that big of a performance hit!

No Copy Paste

In my opinion, this is a huge sin. As a person who uses a password manager, I use an application to generate a very long (~257 bits of entropy), very random password. I then copy and paste this password (having never seen it) into the password field.

This allows me to easily avoid re-using passwords across multiple sites, and ensures that I always pick a strong password.

Allowing Bad Passwords

PayPal does not (client-side!) check if the password you have types is a bad password. In fact, it allows 'password' and '12345678' as passwords. Yes it labels these as "weak", but it doesn't prevent you using them.

Dense Strength Checker

The strength checker offers a false sense of security. I can make it claim an 8 character password is strong. It simply is not! Even the best 8 character password is at most 53-bits of entropy.

What They Should be Doing

• Minimum length: 12 chars
• No Maximum Length
• Allow Copy/Paste for users who use password managers (such as myself)
• DropBox keeps a list of really bad passwords, and warns against them by checking client-side.

How To Deal With This

you only (unfortunately) have two options:

• Complain to PayPal. I already have done, and I'll post the follow up.
• Leave PayPal.

If PayPal don't correct these simple issues, I will most likely be leaving PayPal, as I do not trust them with my details if they can't manage passwords correctly.

Shared-Secret Authentication

Overview

Authentication is difficult. Barring the issues of lost passwords, weak passwords, the philosophical concept of "identity", and a host of other issues, we'll be looking at performing authentication "correctly" for users.

Issues

Credential Leaks

This is a simple attack. An attacker somehow gets their grubby little mitts on a set of (username, secret) and the gig is up.

But even if you're storing a hash of the user's secret, there are still pit-falls.

Timing Attacks

Timing attacks are often overlooked, but they're usually only a problem for high-value targets. They almost always comprise a high level of knowledge about the internal system, but can be used to effectively do things like enumerate all of the usernames on your system.

This can be a problem, what if, like Facebook, your username is the user's email? This is bad, because it means that you are responsible for leaking the data to an attacker who may just add them to a spam list, or use it as another step in an attack on a user.

Online Brute-force Attacks

These are the simplest to imagine. Just start guessing the credentials and sending them to the server for authentication. You have to know nothing about the system to do this, with the exception of where it is.

These attacks can become more sophisticated, by using a botnet to distribute the authentication requests around the world, and by statistically guessing credentials. When combined with a timing attack to enumerate usernames and good statistical guessing of passwords, this actually becomes quite a formidable threat.

Replay Attacks

A replay attack is where an attacker captures a valid (usually encrypted) request to a system. The system doesn't distinguish one request from another, so when the attacker re-issues the request, the system gladly carries out the request again. This could be as simple as logging the user in, or moving money from one account to another.

Defences

Credential Leaks

These come in many forms. 

• You leak your database, and the shared-secrets (i.e. passwords) are not protected by a hash.
• You leak your database, and the shared-secrets are protected by a weak hash algorithm.
• The credentials passed in plain text over the wire on the way to your server.
• The credentials might be extracted from a "secure" tunnel. 

Given the broad nature of this issue, I will issue a few simple golden rules.

Ensure that any shared secrets are stored in your database using a strong hashing algorithm. I recommend scrypt and a reasonable password policy. With reasonable parameters, this ensures that any attacker has to spend a lot of cash to break an scrypt hashed password.  This covers the first two bullet points above.

And don't forget, that when hashing the password, you need to hash it with a salt which is cryptographically random and fairly big.

For the second two on a web application, always use SSL, and turn compression off. Do not store shared secrets on the client in cookies or anywhere else in the client. If you're not writing a web application, ensure that you use something equivalent to SSL on your connection between the server and the client. If you can't have this, you're going to need something other than shared-secrets for your authentication.

In general (for a web application) you want to ensure that your application is immune to XSS attacks, as it may actually be very easy for an attacker to use your site to send credentials elsewhere. This could be done by injecting a JavaScript keylogger into an otherwise perfectly valid page. If you're doing all this over SSL, then the subject of the attack will fully trust all of the script on the page to be from you, not an attacker, and will probably let the keylogger do it's business. Not cool.

Timing Attacks

This is quite feasible. Given a login procedure something along these lines:

1. Get the user's hash from the database. If there is no hash, return false.
2. Hash the given secret and compare it to the one in the database. Return the appropriate value.

Given that a good hash function should take ~100ms per password hash, an attacker can send hundreds of username guesses and random passwords down the wire. The attacker then measures the response time. The ones with a large response time are the ones which had their random passwords hashed, which means that a username was present.

There are several ways to defend, the most common is to attempt to engineer your solution to take the same amount of time regardless of the path it takes. This conflates your authentication code with code which tries to defeat a timing attack.

A better method is to leave your authentication code as-is, and wrap your authentication in an object which forces all requests to have the same average response time, regardless of whether or not the authentication was successful or not.

This has the benefit that, if your authentication process needs to query an external system, as well as internal systems, the external system need not be timing-attack resilient, and can be as simple as possible. It also keeps any code for checking locally-managed passwords simple.

The wrapper would simply keep a track of the average time that it took to perform a successful authentication. In the event that the authentication was unsuccessful, the wrapper would force the authentication to take the average time on total. Some code which has this idea can be found on my GitHub.

The source code above is in Java, and can be built using

ant dist

and run using

java -jar ./dist/lib/TimingAttack.jar

It will print out a series of authentication results and times to reach the result. You should see that the time on each should be (on average) the same, regardless of the result.

This doesn't protect against other side-channel attacks. If, for example, a malicious application was running on the same CPU as your application, there are a host of attacks (e.g. cache-miss side-channel attacks) that can leak information about what your application is doing. 

Online Brute-force Attacks

This is actually a very tough nut to crack. If we assume that the attacker is as sophisticated as possible; getting a botnet to do statistically very good guessing for them; then we have a serious problem on our hands.

The first way to help deal with this is to force (or encourage) your users to pick very strong, difficult to guess passwords.

The second way is to rate limit any guesses. In general, this is A Good Thing^TM as it prevents an attacker from using up system resources at an unreasonable rate, and thus protects against a simple denial of service attack.

The second way could be achieved by keeping a global (for Java, read Singleton) RateLimiter class which keeps a record of IPs and the most recent time they sent a request in. If it's been too recent, make them wait a long time.

An example of such a rate limiting can be found in the same GitHub repository as the previous example. It can be run in a very similar way, first build it:

ant dist

and run using

java -jar ./dist/lib/OnlineBruteForceAttack.jar

A potential modification would be to slow down the request for each user account individually, as opposed for each IP address. That way, each IP gets some number of guesses that get a reasonable response time for each user, thus helping any folks with NATs. However, this means that an attacker can DoS a user. Some combination of IP Address and account would be in order, but even that won't slow an attacker down much.


Replay Attacks

These are usually dealt with by correctly using SSL. SSL uses nonces (cryptographically strong random numbers) to ensure that two requests can be distinguished.

In a system which does not use SSL, you basically have to implement nonces yourself. This is not hard, but I won't cover it here. Basically you stick a random number into the request. If you've seen that number previously, discard it. If you didn't generate that number, discard it.

Conclusion

The "best" [Edit: shared-secret based] authentication system requires good passwords (for some value of good), hashes them with a really good hashing algorithm (my opinion is that a correctly-configured scrypt is the way forward), and defends against timing-attacks and simple brute-force attacks is the best.

However, you need to balance this against the needs of your user. How sensitive is the data you're storing? How well compartmentalised is your application? (i.e. can a compromise of one account lead to another user's data being exposed?) Do you have the time to implement all of this, or do you just want to scrypt the password and call it a day -- for now?

Either way, as I've mentioned before on this blog, I want shared-secret authentication to die.