Dan Kaminsky's Blog

Just a small post, because Rob Graham asked.

The question is: What is the differential complexity increase offered by salting hashes in a password database?

The short answer, in bits, is: The square root base 2 log of the number of accounts the attacker is interested in cracking.

Rob wanted me to explain this in a bit more depth, and so I’m happy to. In theory, the basic properties of a cryptographic hash is that it’s infeasible to invert the hash back to the bitstream that forged it. This is used in password stores by taking the plaintext password provided by the user, hashing it, and comparing the hash from the database to the hash of the user provided plaintext. If they match, the user is authenticated. Even if the database is lost, the attack won’t be able to invert the database back to the passwords, and users are protected.

There are, of course, two attacks against this model. The first, surprisingly ignored, is that the plaintext password still passes through the web app front end before it is hash-compared against the value in the database. An attacker with sufficient access to dump the database often has sufficient access to get code running on either the server or client front ends (and you thought cross-site scripting was uninteresting!). Granted, this type of attack reduces exposed users from “everyone” to “everyone who logs in while the site is compromised”. That’d probably be more of an improvement, if we believed attackers were only interested in instantaneous smash-and-grabs and were unable to, or afraid of persisting their threats for long periods of time.

Heh.

The more traditional threat against password hashes is offline brute forcing. While hashes can’t be inverted, the advent of GPUs means they can be tested at the rate of hundreds of millions to billions per second. So, instead of solving the hard problem of figuring out what input created the given output, just try all the inputs until one happens to equal your desire.

How long will this take? Suppose we can test one billion hashes per second. That’s approximately 2^30, so we can say we can handle 30 bits of entropy per second. If we’re testing eight character passwords with the character set A through Z, a through z, and 0 through 9, that’s (26+26+10)^8, or 218,340,105,584,896 attempts. That’s roughly 2^48, or 48 bits of entropy. We can handle only 30 per second, and 48 – 30 == 18, so it will take approximately 2^18 seconds to run through the entire hash space — that’s 262,144 seconds, or 72 hours.

(Yes, I’m rounding extensively. The goal is to have a general feel for complexity, not to get too focused on the precise arithmetic.)

There are two important oversimplifications going on here. First, passwords selected by humans, even those that use those all important punctuation, numbers, and other forms of l33tsp33k, do not utilize these hardening factors particularly randomly. XKCD has made fun of this in the past. One of the real consequences of all these passwords drops is that we’re getting hard data on the types of password patterns people actually use. So groups like TeamHashCat are selecting their billion-hashes-per-second not in random order, but increasingly close to the likelihood that a given input will actually be somebody’s password.

So how does salting play into this?

There’s a much older optimization for password cracking, than selecting passwords based on complex models of what people use. An unsalted hash is the direct output of hash(password). If two people use the same password, they will have the same password hash. And thus, the work effort to crack passwords amortizes — the same operation to find out if Alice’s password is “abcd1234” also discloses whether Bob’s password is “abcd1234”. Salting changes this, by adding some sort of randomizer (possibly just “Alice” or “Bob”) to the hash function. That way, Alice’s password hash is the hash for “Aliceabcd1234”, while Bob’s password hash is the hash for “Bobabcd1234”. To crack both Alice and Bob’s passwords requires twice as much work.

That’s one extra bit.

And that then is how you back into the complexity increase of salting on password cracking. When you’re cracking an unsalted database of passwords, the more accounts you have, the more “bites at the apple” there are — each attempt may match any one of n hashes. Salting just removes the optimization. If you want to crack 256 accounts instead of 1, you need to work 256 times harder — that’s 2^8, or 8 bits. If you want to crack 1M accounts, you need to work a million times harder — that’s 2^20, or 20 bits.

Note however that the question is not how many accounts there are in total, but how many accounts you’re interested in. If only 256 of the 1M accounts are interesting, salting only wins you 8 bits.

A bigger deal, I think, is memory hardness. Password hash functions can and often are run in a loop, such that the hash function is actually run thousands of times in a serial fashion. This does win ~12 bits of security. However, the loops are still viable within the practical means by which attackers are getting billions of hashing operations per second, i.e. GPUs. GPUs have an architectural limit, however — they can be run out of memory. Requiring each hash process to spend 256M+ of RAM may practically eliminate GPUs from the hash-cracking game entirely, even if the number of interesting accounts is just one.

That’s not game-over for all attackers — million node botnets really do have a couple gigs of RAM available for each cracking process, after all — but it does reduce the population of attackers who get to play. That’s always nice. The best path for memory-hard hashes is Colin Percival’s scrypt, which I’ve been playing with lately inside of my cute (if ill-advised) Phidelius project. scrypt has an odd operational limitation (no libscrypt) but hopefully that can be resolved soon, and we can further refine best practices in this space.

Edit: Ah, some of my commenters have mentioned rainbow tables. These actually do change things slightly, though from an interesting direction. Unsalted password hashes are not merely shared across all accounts in a given database; they’re also shared across all accounts for that entire implementation, at least for each account someone is trying to crack. That means it’s possible to both pregenerate hashes (there’s no need to know a salt in advance, because there isn’t one) and to calculate more hashes for more time (since the work effort can be amortized not just cross-account, but cross-database).

It’s become a bit of a thing to just take password hashes and put them into Google. If they’re MD5, and they’re unhashed, a surprising amount of time you do get an answer. Moral of the story: Salting does keep you out of a hash dataset that may be 24+ bits (16M+) “cheaper” (less expensive per account) to attack than just your own.

Peter Maxwell also noted (read the comments) that it’s important to, say, not have a 16 bit salt. Really? Do people do that?