Home > Security > Salt The Fries: Some Notes On Password Complexity

Salt The Fries: Some Notes On Password Complexity

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?

Categories: Security
  1. January 5, 2012 at 4:07 am

    What Dan said. The big problem is that rainbow tables are waaaay to effective now. From Linux Pro Magazine Nov 2011 http://www.linuxpromagazine.com/Issues/2011/132/Security-Lessons-Password-Storage/%28kategorie%29/0 but basically using chains you can actually store passwords made up with 94 different characters (a-z, A-Z, 0-9, `~!@#$%^&*()-_=+[{]}\|;:'”,/?, in other words every key on a standard US 104 keyboard) in about 14 TB or so.

  2. Benson
    January 5, 2012 at 4:40 am

    Great post! You did seem to omit the part where proper salting does a decent job of protecting against rainbow tables.

  3. January 5, 2012 at 5:53 am

    There’s a corollary here – the entropy of the salt is important.

    Assume:

    i. the password-derivation-function (PDF) with salt are protecting a large password set (it’s a subtle point but does require to be “large” set for this argument to make sense);

    ii. the mean entropy of the passwords is low, say in the order of 30bits;

    iii. the PDF is time-bound but not memory-bound;

    iv. the salt is unique per password and contains a maximum n bits of entropy, or perhaps more simply is n bits long and random, or for that matter is selected from a predictable set of values of size max 2^n.

    Under those assumptions and for low n, it is fairly obvious that an attacker would be best pre-computing a “rainbow table”. The reason this is so is because for low n, say 16 bits, the attacker can compute off-line a 2^(30+16) table which is roughly 70Tb worth of storage; when the attacker decides it is time to compromise the password database the only task they are left with is a search of the rainbow table, which if some sorting logic is added is linear/logarithmic time complexity for each password tried against. Assuming a normal distribution in the entropy of the passwords, the probability of success for each password is roughly 0.5. In other words, for a low entropy salt, the attacker can compute the rainbow table at their leisure before compromising the password database, an added benefit if time between compromise and any misuse is critical.

    Obviously, if the *minimum* password entropy is guaranteed to be much larger then we have a problem but in most password databases you will find a selection of users manage to pick surprisingly poor passwords.

    So, in a standard situation, with a run-of-the-mill PDF (i.e. not Colin Percival’s scrypt) then salt entropy is actually important. Hence why it should usually be drawn from /dev/random and of decent length (probably at least 64bits).

  4. January 5, 2012 at 4:13 pm

    I was all set to disagree with you, Peter, but you’re entirely correct. If the salt has low entropy _and_ can collide (meaning, not just the username), then yes. You could potentially rainbow table the salt.

    Does anyone use 16 bit random salts?

    • Darth Null
      January 5, 2012 at 5:23 pm

      Crypt() uses 12-bit random salts.

      And, yes, salts that small can certainly be worked into a rainbow table :). It’s roughly analogous (in the crypt example) to adding two more letters to the password.

      There’s probably some decent metric one could devise to find a good recommended salt length. Certainly, 64 bits (as suggested by Peter) would add a pretty big hurdle…

  5. January 5, 2012 at 6:34 pm

    To reap some benefit from using rainbow-tables, there’s actually no need for collisions, assuming the conditions I’d laid out.

    The gain is that:

    i. the attacker can compute the table off-line well before an attack, which is a substantial advantage when time-constraints between compromise of a target system and use of the information are concerned;

    ii. the table is potentially reusable if two different victims use same password database structure.

    If the attacker does indeed have collisions in the salts then that is also, obviously, advantageous although requires a password set with more values than there are possible salts really. i.e. large.

    Perhaps more practically, I don’t know of any widely used system that employs 16-bit salts 🙂 Although, I’ve see a fair number of “roll your own” systems where people have used your illustration above of the username as a salt (which is in a practical sense far less than 16bits) and in one case a sequential counter (worse).

  6. January 5, 2012 at 6:37 pm

    Technically, there is a collision, between precalculated values and the target account database.

    I think usernames have more than 16 bit of native entropy. Quite a bit more than 65K people in the world.

    • January 5, 2012 at 11:43 pm

      “Technically, there is a collision, between precalculated values and the target account database.”

      Yeah, ok. I thought you meant a collision in the salt values.

      “I think usernames have more than 16 bit of native entropy. Quite a bit more than 65K people in the world.”

      Well, this is a double-edged sword of a question. From one perspective, a username must be unique on a given system so if the username is used as the salt then you are guaranteed they will not collide on the same password set. The actual number of unique salts will be exactly the number of users, however a blinded attacker must guess this so their success will have an upper-bound of the size of the intersection of the set of real usernames and the set of guessed ones.

      That is however not the full story. To construct a (useful) rainbow-table in this very specific scenario, an attacker will not need to guess all the usernames only a proportion enough to make his effort worthwhile. In other words, if the attacker compromises a password set with 50k users, it may be that only 1k users are sufficient for a good pay-off.

      I would posit that in almost all practical cases, the attacker could make a useful set of usernames (salts): usernames are rarely randomised, normally limited in length, usually lowercase alpha-numeric+numbers and often easily guessable.

      Many companies or academic institutions use a consistent naming scheme and advertise staff directories, so in that scenario the attacker can choose exactly how many salts he/she wishes to use in their rainbow table with the guarantee they are all valid salts. This is of significant utility to the attacker, as they can finely tune the number of candidate salts to optimise the maximum number of hashes calculated against each salt (they can also choose more high-valued targets).

      There may be far more than 2^16 people in the word, but we are hardly named uniquely. A slightly trite example is the data for new baby first names in Scotland last year (yes, I’m a bit of a softie at heart):

      http://www.gro-scotland.gov.uk/statistics/theme/vital-events/births/popular-names/2010/detailed-tables.html

      there are around 8200 unique names in that set for around 54k babies. If one makes the sensible decision of discarding all names from the list that are used only once then it leaves 2507 names – significantly smaller than the 54k new children. Granted, that is a small sample set and only considers first names, but the principle will scale and as these scenarios scale the results approach their statistical approximation rather than exhibiting quantised effects, hence why requirement i. in my first comment is often important in these discussions.

      Anyway, even if an attacker has to guess at usernames, they can be harvested online or gained from previous corpora, sorted by relative frequency and then the n most frequent used as candidate salts, depending on the desired size of rainbow-table the attacker requires. It is exactly the same principle used when picking most ilkely passwords for a rainbow-table.

      Hence why it is far better for a system designer to use a random salt of decent length, to avoid all this unnecessary mess, lest they are forced to spend an afternoon with me talking at them.

      On an even more irritating note, the issue of salts, password entropy and hashing take on a whole new level of annoyance when they are used in whatever new-fangled notion a software engineer has decided to use for stateless session cookies. I’ve counted about six times when I’ve noticed services I *used* to use employ some impenetrably stupid design (and yes, I did inform them, and no, they didn’t listen). Turns out combining transit of secrets along with storage was too much for them, even when the bods at Cambridge design and publish something sensible ( http://www.lightbluetouchpaper.org/2008/04/25/wordpress-25-cookie-integrity-protection-vulnerability/ )

  7. January 6, 2012 at 11:21 pm

    What about using “bcrypt” instead of the standard hash functions?

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

    • January 10, 2012 at 3:54 am

      I’m more of a fan of scrypt, but I should take another look at bcrypt.

  8. January 12, 2012 at 8:28 am

    Kurt,

    You should mention 95 (including space) and not 94 which roughly gives a keyspace of ≈ 2 ^ 52.5741. Also, I don’t know how you derived your RT numbers at 14T for length 8. Even in classic RT tables with 16 bytes per chain, assuming perfect tables, you would need a very short chain length for such storage requirements and the I/O time would outweigh the savings in shorter chain length.

    Take a look at my project’s tables for 99.9% success rate for ntlm or md5 that are around 1.1T for each set (www.freerainbowtables.com) and available for free. project-rainbowcrack.com offers 96.8% success rate tables for these keyspaces for $1200 USD each (you mention they are free for some reason). Our RTI2 format is prefix indexed on disk both for space savings and for faster attack times *and* included in that disk space use number. You should also visit cryptohaze.com which has only focused on the GPU side instead of straddling CPU and GPU like PRC and FRT have done.

    FRT’s original goal was to convince people to minimally salt hashes but even Sony cannot be bothered to even salt hashes. As you point out weak passwords even with salts are trivial attacks. The real answer is of course password stretching techniques like PBKDF, bcrypt, etc. First, though maybe we can convince Sony to salt their hashes.

  9. Michael
    January 16, 2012 at 1:51 pm

    I have an idea, potentially stupid idea. If so please tell me why exactly it is stupid.

    Usually (most tutorials on the web) salt is simply appended to the password before hashing. Sometimes there are several iterations of appending salt to hash and hashing again. There is little branching here.

    I heard that GPUs are good for massively parallel computations with minimal branches, CPU is good for serial computation with branches. Therefore GPU is good at calculating hashes. That’s what I heard on “the internets” without really writing GPU code.

    Do common implementations use salt in ways smarter than simply appending?

    For example insert the salt into the password in the middle with the insertion position dependent on hash from previous iteration. Or maybe even simpler – bytewise merge of hashed salt with hash from previous iteration. This operation is cheap for CPU. Is it still cheap for GPU? It is known that GPU is bad at some computational tasks, can we apply salt to password in such GPU-unfriendly way?

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: