“New” (well, not really new) PRF functions for PBKDF2

In Chapter 11, I indicated that the only PRF available for PBKDF2 was SHA-1. I believe this was true when it was written (during the early betas of iOS 5), but it was not true by the time iOS 5 was released. iOS offers both SHA-1 and SHA-2 PRFs for use in PBKDF2:

enum {
    kCCPRFHmacAlgSHA1 = 1,
    kCCPRFHmacAlgSHA224 = 2,
    kCCPRFHmacAlgSHA256 = 3,
    kCCPRFHmacAlgSHA384 = 4,
    kCCPRFHmacAlgSHA512 = 5,
};

SHA224-SAH512 are just specific sizes of SHA-2.

Note that while SHA-1 is “broken,” the issues don’t impact the security of HMAC (let alone PBKDF2). SHA-1 still serves this function perfectly well. Even MD5 is still fine in this use. Intuitively, PBKDF2 doesn’t need a collision-resistant hash function at all because its goal is to waste time in a way that is difficult to short-cut with parallelization. (On the security proof side, HMAC does not require a strongly collision-resistent hash function in order to remain a PRF, and PBKDF2 only requires a PRF to maintain its security. See Mihir Bellare’s paper for details.)

As good security housekeeping, I would recommend that new implementations use SHA256 to help move the world from SHA-1 to SHA-2 a little faster. But I wouldn’t recommend expending much effort to retrofit old implementations at this time.

I haven’t yet done any timing analysis to determine a good number of PBKDF2 iterations for SHA256. SHA1 needs 10k iterations to give 80ms on a iPhone 4. ~100ms is a pretty good target IMO.

Thanks to Daniel McGloin for pointing this issue out to me.

8 comments

  1. “PBKDF2 doesn’t need a collision-resistant hash function at all because its goal is to waste time in a way that is difficult to short-cut with parallelization”

    I have doubts about this, my first intuitive thought was that if a hash function is not collision-resistant than iterations won’t help much and the final result will be not collision resistant either, especially if a number of iterations can be easily extracted from a source code. The whole goal of PBE is to derive one secret from another in such a away that a reverse function doesn’t exist or would be very difficult to create, which is not the case with hashes prone to collisions.

    • >The whole goal of PBE is to derive one secret from another in such a away that a reverse function doesn’t exist or would be very difficult to create

      This isn’t true. The goal of a PBKDF (I say “a” PBKDF because PBKDF2 is just one algorithm) is to derive one secret from another in a way that is computationally expensive and that increases the entropy of the resulting secret. The reverse function is not a consideration of a PBKDF. That would be a game of the form: “given that I know the final key, can I guess your password?” PBKDF2 does not care about this game, because if you know the final key it doesn’t matter if you know the originating password (nor does it matter if I can calculate a colliding password). Moreover, as an attacker against PBKDF, I am not trying to forge a hash given a corpus of existing messages and their hashes (that being the security game for a secure hash). I am trying to brute-force a specific key. If I already knew an existing message that generated the hash (the password), I wouldn’t need to forge some other message (password).

      So that’s some intuition, but how do we prove it is secure? PBKDF2′s security proof requires that one of its inputs be a PRF. So the question is, is HMAC a PRF? (Remember, PBKDF2′s input is not SHA1; it’s HMAC.) Well, Bellare proves that HMAC is a PRF if its input function is “almost universal.” (See Turing Completeness for an explanation of “universal.”) SHA1 meets this requirement. Therefore, HMAC is a PRF, and therefore PBKDF2 is secure with SHA1 as an input. QED.

      If this kind of proof interests you, but you have a hard time following HMACs and PRFs (vs PRPs etc.), I highly recommend Dan Boneh’s Cryptography class. I have never learned so much about how the math of this stuff works. If these kinds of proofs don’t interest you, then I direct you to Bruce Schneier’s post where he notes that “it doesn’t affect applications such as HMAC where collisions aren’t important.” If you don’t trust Schneier on crypto analysis, then I can’t help you. He’s smarter than me.

  2. “PBKDF2 does not care about this game, because if you know the final key it doesn’t matter if you know the originating password (nor does it matter if I can calculate a colliding password)”

    Really? So, if somebody has reversed a mobile device PIN by uncovering a derived key recklessly stored by a developer on a device file system, it would not be an issue in your opinion? Interesting thought, but I tend to disagree.

    • It isn’t a question of opinion. It’s a question of the security proof of PBKDF2. PBKDF2 does not make strong promises about reversibility AFAIK. That said, it can’t be reversible based on known weaknesses in SHA1 or MD5. The kinds of collisions in those algorithms are not relevant to reversibility because they do not degrade the fact that HMAC is a PRF under them (as Bellare proved). A PRF, by definition, is not reversible to its seed in computational time. If it were, then you could distinguish it from a true random function (and therefore it wouldn’t be a PRF).

      Do you know of an attack against PBKDF2 based on the weaknesses in the collision-resistance of the hash used for the HMAC?

  3. http://openjdk.java.net/jeps/121:

    “Motivation
    The currently supported PBE algorithms from the SunJCE provider only cover DESede, and RC2 (40-bit) with SHA1. To remain competitive we should also support PBE algorithm implementations with stronger cipher and message digest algorithms, such as AES cipher and SHA-2 family message digests, as well as those specified by PKCS#12.”

    Why would people even think about it if SHA-1 is OK? BTW, If I follow your logic, I can safely replace a crypto hash with something as simple as XOR-ing, AND-ing or OR-ing as long as computational cost is big.

    • As long as you could prove that the XOR/AND/OR logic is not decomposable into parallel steps, and that there aren’t short-cuts to skipping iterations, yes. Proving that is difficult. PBKDF2 is believed to meet this (though I don’t believe there’s a strong proof for it), as long as its input is a PRF. What Bellare proved was that the PRF property of HMAC does not require a strong collision resistance in its input hash function, and that a wide variety of “reasonable” hash functions (including SHA-1 and MD5) would maintain the PRF property of HMAC.

      I agree with others that we should move from SHA-1 to SHA-2 as a matter of course. But I’m saying there are no known attacks on PBKDF2 based on the weakness of SHA-1, and that there is strong reason to believe that such an attack is impossible based on Bellare’s proof. Even so, we should phase out SHA-1 over time since we have better algorithms, and SHA-1 has serious problems in other uses. In the next decade or so, we will probably need to move to SHA-3 when problems appear in SHA-2 (and there are some partial attacks on SHA-2 already). That’s the nature of crypto.

      Do you have any math to back up your concerns? Or are you aware of a cryptanalysis that raises concerns? Schneier also seems content with SHA-1 for use in HMAC (which feeds into PBKDF2). Is this just intuition based on “SHA-1 has collisions, so it must be broken for all uses?” Or do you have more information relevant to its use in PBKDF2?

  4. No, I don’t have a mathematical proof that this particular PBE algo is unsafe to a degree when we should assign a high severity to the cases when SHA1 is used and I actually do not consider this as high, but proving that an efficient attack will not be invented in the future might be even more difficult. I was mostly arguing about those generic statements that you’ve made, like purpose of PBE and unimportance of possible derived key reversing.

    Your last suggestion that I can create my own hash function if prove that it’s safe doesn’t make too much practical sense to me either, because if you read Schneier’s “Applied Cryptography” book, which is kind of classic, you would notice that the good approach is to keep crypto algos open and private keys protected. There is a good reason to keep them open: it allows many crypto analysts to scrutinize them and after this is done those algos become a de facto standard, so I would strongly discourage developers to be inventive in this area and stick to the standards. I would not do it myself either.

    Everybody has agreed that SHA-1 should be replaced. I could agree with you that in some cases (like the one that we consider now) using it could be less dangerous than in others (just think about the latest Linkedin’s incident), but what policy would be easier to enforce in your view:

    1. Replace SHA-1 everywhere with SHA-2
    2. Create a list of all cases when SHA-1 is still acceptable by analyzing the risks in many different areas where SHA-1 could be used (e.g. digests in DS, hashes in PBE, salts, DB hashes, etc)?

    When you deal with all of this on a daily basis, it’s quite different from a theoretical discussion where nobody is really responsible or accountable for what he’s saying or writing, so please do not confuse our developers :)

    Other than that, it was interesting talking to you.

  5. I used to write Infosec policy for Cisco, and performed security assessments for them for years. While I’ve learned a lot more of the theory in recent years, I’ve always been focused on the practical aspects of security. You are correct that as a matter of corporate policy it is convenient to make blanket statements like “never use SHA-1.” But it is critical that we as security engineers know the details, even if we write more conservative policy. Otherwise we undermine our credibility fighting over something that isn’t actually a risk.

    I’m aware of no security risks in using SHA-1 in the HMAC of PBKDF2 that are mitigated by using SHA-2. I am eager for links to known or theorized vulnerabilities from knowledgeable writers. It’s not just that it’s “not that bad.” It is currently equivalent to SHA-2 in security terms for use within the HMAC of PBKDF2. PBKDF2 simply does not require a collision-resistant hash in its HMAC in order to maintain its security (hooray!). This is why Schneier said “it doesn’t affect applications such as HMAC where collisions aren’t important.” There are some concerns about PBKDF2 because its may be too easy to implement in hardware, but that’s unrelated to collisions in the hash function and is not improved with SHA-2.

    I developed RNCryptor specifically because so many iOS developers were using AES wrong. They’d heard the simple rule “AES good,” and then proceeded to implement it completely insecurely thinking that its AESness would cover all sins. We need to educate our engineers better in how crypto systems work and how to reason about them. There is too much “I heard this was good and this was bad” and it leads to bad security implementations. Someone in the org needs to know how to evaluate issues with more than just rules of thumb, and developers need know when to go to the expert for advice.

    Of course you shouldn’t design your own KDF. No argument. Nor your own hash or cipher. You shouldn’t even implement them yourself if you can possibly help it. That’s why RNCryptor relies entirely on the OS for security code.

    As I said, we should move to SHA-2 in PBKDF2 as a matter of housekeeping. We should move to SHA-2 for digests as a matter of security. Security people should be clear on the difference, and push much harder on the ones that matter so we don’t use too much political capital fixing things that aren’t broken.

    I apologize for the length. I’ve tried to trim it down a bit. This is a passion for me, as I suspect it is for you. And I still highly recommend the Stanford course. It’s free and excellent. I think every senior security professional should at least attempt it.

    Thanks for reading. I do appreciate the comments. As you say, this stuff is very real-world for you. I hope my writing can help your iOS developers write more secure code.

Trackbacks/Pingbacks

  1. PBKDF2 and SHA-1 | Cocoaphony - [...] posted a new errata on the iosptl site about PBKDF2 and SHA-1 versus SHA-2. If you’re using CommonCryptor (and …

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>