Securing password digests, or how to protect lonely unemployed radio listeners

As we’re prone to say, “much ink has been spilt over the release of password digests” from LinkedIn and others. I’m, as is typical, profoundly disappointed in that amount of misinformation I’ve heard in security folks’ commentary on the problem and the underlying workings of digests, HMACs, and so forth. This blog entry represents a roll-up of a great discussion we had internally on our software security group mailing list.

A few caveats

1. We do not recommend only a digested password (salted or otherwise, MAC’d or not) as a best practice for password storage. Consider this work instructional only.
2. Hardening a salted hash introduces properties to a system which in turn require threat modeling for respective weaknesses. You may quickly find it’s turtles all the way down. 
3. Digested passwords, salted or otherwise, create a non-trivial maintenance problems (on compromise, rotation, etc.) for AuthN administrators because of their non-reversibility.
4. An app’s threat model may demand focus on many other aspects of AuthN design prior to password storage.

This entry treats the issue and its mitigation more thoroughly than press / blogs have for purposes of secure design instruction. Other entries leave developers with a lot of questions and opportunity to mess things up.

What we learned Storing passwords in the clear is unacceptable, as best practice states

This latest example reinforces what we know: Whether through injection or other means, attackers regularly succeed in bulk exfiltration of sensitive data.

Digesting stored passwords is not itself a best practice

This resonates immediately with many security practitioners. However, some organizations for which we do assessments still push back on this. Policy varies by organization, but if you’re committed to digesting with hashes, best practice entails:

• Use a digesting function currently not known to suffer from collisions.
• Use such functions securely so as not to weaken its attack resistance; Specifically, prevent length extension vulns, Salt(*1) data to be hashed (PW) to avoid duplicate detection, and avoid salt/src-data collisions.

Through this post, I present a solution that meets these requirements.

We now know, personally, how a stolen HASH(PW) *feels*: It violates user trust

The first thing we all did was (1) change our passwords and (2) tell everyone we know to reset THEIR passwords. I recently explained to a customer, “When an individual’s password is stolen, you’ve often compromised their credentials at several sites. How many people have a single password that they use for several ‘low risk’ sites? When we deploy an application, we have a (metaphorically) fiduciary responsibility to protect users’ credentials.”

Attackers can determine what HASH() scheme used from only digest data

We quickly knew we were dealing w/ SHA1() unsalted. After an assessment, some application owners will indicate “Even if they could steal our HASH(PW) database, they couldn’t apply a rainbow table because they wouldn’t know our protocol/scheme.”

Obscurity provides some value to raising the difficulty of reversal, as long as it doesn’t weaken the cryptographic properties of a solution. It doesn’t always take a cryptanalyst (or even a security consultant) long to figure these things out. Attackers of public systems, such as LinkedIn, have access to freely create their own account (or accounts). With this access an attacker can craft their own PW,HASH(PW) tuple by creating / hacking their own account. This means they have a ready-made test to help prove their hash scheme hypotheses.

Hash dictionaries exist online

If you’re having trouble with the previous step, Google the recovered hashes, and you’ll see hits for MD5 and SHA1. These dictionaries can be used to bootstrap a salt-specific rainbow table.

A bit of threat modeling

Before we proceed towards a solution, let’s define rules of engagement by considering a fixed set of threats and attack vectors we’ll protect against. (T = Threat, AV = Attack Vector)

[T1] – Internet-based attacker – Access to the app

1. [AV1] – Inject database, lift entire table of HASH(PW)
   • Studies show that the majority of password lifts also provide UNs
   • Attacker looks for DUPS in HASH(PW)
2. [AV2] – Observe single user’s HASH(PW), attempt to reverse
   • T1 can see the victim’s material AS WELL AS their own
3. [AV3] – Impersonate login by using hash attack
   • Presumes T1 access to surface where hash computed/present
   • Replay stolen from AV1 or AV2 or
   • until collides with what observed through AV1 or AV2
4. [AV4] – PRNG attacks
   • Attacks may DoS the app (not just random) by causing the PRNG to block on more entropy
   • Improper use of PRNG may lead to cryptanalysis or exploit

[T2] – LAN-based attacker, access to database

1. [AV1] – Pul export of material through load/reporting interfaces

These vectors will help us couch the remainder of the discussion.

How we fix it

I spent some time to hack up a prototype solution, in Java, and share it here because I can’t find a good (concrete) example without limitations with regard to my stated best practices above. Two things are interesting:

1. It’s just not that much code.
2. Even without rolling our own crypto, getting that code correct is surprisingly subtle.

Look at the solution’s simple form:

[STORED_FORM] = [SALT] + HASH ([SALT] + [PW])

Two issues remain: How do we:

1. Specify and scope the [SALT]?
2. Avoid hash() length extension attacks? (*2)

[SALT Spec]

Specifying a single salt at the scope of the whole password database provides **NO** security under T1.AV1, AV2, or AV3. This conclusion holds regardless of salt size. Why? Because T1.AV3 presumes access to a single salted hash, which gives away the prefix needed to compute your new app-specific rainbow table. Put another way: Using the same salt for all passwords defeats the salt’s only purpose (de-duping cipher-/digest-texts). See (*1).

***Also remember: in case (T1.AV2) (a threat gets access to a victim’s digest) they will have to create a custom rainbow table to break reverse the hash, but creating this rainbow table is NO more difficult than creating one for an unsalted hash (because the salt is known).

So, do we need to protect the storage of the salt? That is, do we need to store it in a separate database table, or outside the database entirely? This fret falls into the category of obscurity: an attempt to slow an attacker down. Again, see (*1). There are more elegant ways to protect a bulk digest lift (T1.AV1) from reversal anyways.

[hash() length extension attacks]
HASH() length extension attacks have been covered (*2). Summarizing, we need to make sure that attackers can’t craft a conforming hash along particular (often internal or MiM) surfaces (as described by T1.AV3). Various authors describe the generic fix to this as:

[DIGEST] = HASH([KEY] + HASH([KEY] + [PW]))

The easier form of this is simply:

[SALT][DIGEST] = HMAC([KEY] + [SALT] + [PW])

I have chosen the latter construct in my implementation.

There are subtle and interesting differences between a solid hmac() implementation and the form above it. For the purpose of this entry, let’s continue confident that the chosen hmac will in fact (1) provide an inner and outer hash() (2) that construction controls length attacks, and (3) that same construction is designed to leak no information about the key through the digest-text.

This selection also means our implementation does not have to chain hashes together (*3). While hash chaining is a kind of obscurity that will provide value without negatively affecting other cryptanalytic properties, it also has a performance impact. I vehemently resist such design additions where alternatives exist.

[Misc Design Properties]

In order to conform to best practice and resist all the stated attack vectors, the design need a few more pushes:

1. Use collision-resistant crypto functions.
   • HMAC() algorithm == SHA256
   • Salt PRNG == SHA1PRNG
2. Avoid salt/data collisions. The implementation fixes the salt size and uses a PRNG so that:saltX + dataX != saltY + dataY
   Some implementations will fail in the following way:
   SX = 123
   DX = 45
   SY = 12
   DY = 345
3. Reuse PRNGAs. Amit points out in (*4): watch for how greedily apps use randomness. Having chosen a largish SALT the design comes to rely on the SALT-size to ensure that creation of a comprehensive rainbow table (for ALL users) would be impossibly difficult. (Please refer to the “***Also Remember” above regarding targeted attack.) That implementation referenced below chose an arbitrary PRNG reset interval of 512 password creations. This may be too often, too infrequent, or just right. The answer depends on the emission rate of quality entropy from /dev/srand.Production software I’ve written has locked machines in test because they’re out of entropy (T1.AV4). This doesn’t just block crypto functions: I’ve seen it halt response to HTTP requests: not cool.
4. Follow Application Security Best Practices (hygiene).
   • Explicitly call out both algorithms and providers
   • Protect underlying digest representation (encapsulation, zeroing them out where possible, etc.)