PBKDF2: Password Based Key Derivation

PBKDF2 takes as input a password, a salt, an integer defining how many “iterations” of the hash function to undergo, and an integer describing the desired key length for the output.

The byte array corresponding to the output string above is suitable for use as an AES key. Note that by increasing the number of iterations (times we run through the HMAC), we intentionally make the resulting output more computationally expensive. This property is desirable as it slows down the ability for an attacker to brute force through the key space of the original password (though it does nothing to prevent the attacker from brute forcing the key output itself). This is useful because 256 bits with a high entropy is much more useful for security purposes than a short passphrase!

One popular use case of PBKDF2 is as a means of hashing a password in order to avoid storing a plaintext password in a database. By iterating through the hashing procedure many times, it becomes slower for an attacker to brute force against either your live system or a database dump. Additionally, PBKDF2 utilizes salting, which protects against rainbow table attacks and protects users who have made the poor decision to reuse their password on multiple sites. PBKDF2 is not a perfect solution however. By intentionally slowing down the ability to compute a hash, it doesn’t only affect an attacker – choosing PBKDF2 means willfully wasting CPU cycles. While the reward may be worth the cost on a PC, PBKDF2 should be used very judiciously in the mobile arena where wasting CPU cycles wastes battery. Interestingly, Android devices rely on PBKDF2 for decrypting the device with the user supplied PIN on first boot. Additionally, PBKDF2 is not resistant to ASICs or FPGAs – purpose-built hardware designed to do a particular task especially efficiently in hardware. x86 architecture by its very design is built to be general purpose, but an attacker with enough spending power can throw hardware at the problem!

Another popular way PBKDF2 is used is as a means of turning a user supplied password into a symmetric key suitable for use with the AES algorithm. This relies on the fact that AES can use any value as its input that meets certain length and entropy requirements and that PBKDF2 can produce a hash of any length which meets those requirements for entropy. This property is extremely handy for tools such as password vaults. By leveraging PBKDF2 with the user’s password at login time, a provider is able to ensure that its software can ONLY decrypt sensitive information while the user is logged in. This makes database dumps, authenticated attacks, and even buffer overflow attacks against the application itself useless to the attacker. However, this approach too has some downsides to consider. First and foremost, browser-based SSO such as SAML breaks this scheme, since SAML relies on trusted text and does not have a user input their password to the relying party application at all! (This is possible to overcome via having the PBKDF2 input come over as a SAML attribute in the assertion). Additionally, when the user changes their password, the application would have to hook into this event by decrypting everything encrypted with the old password and encrypting it with the new password instead – that’s quite a lot of overhead, and can result in a password changing experience taking minutes to hours. Not good!

In order to get around hour+ long password reset times, one common practice is to PBKDF2’s output as a symmetric key which in turn decrypts another symmetric key. This prevents the need to rekey everything which exists in the system (since it was encrypted by a key that does not need to change). This approach retains the ability for an application to only have access to those fields during a user session however! This is accomplished by hooking into the user-change password, but only performing a single re-encryption operation – that of the user’s main symmetric key!

PBKDF2 is an especially interesting practical application of cryptographic concepts as it relies on the interplay between hashing, encryption, salting, message authentication codes, and key derivation. It is also commonly used in order to achieve a specific goal. What applications can you think of for PBKDF2?