guest - flak

bcrypt_pbkdf - bcrypt kdf key derivation function

A long time ago, OpenBSD added bcrypt, a function to securely (slowly) hash a password. Sometime later, a similar but more general standardized password -> hash function was developed, PKCS #5 PBKDF2. How that winner of a name caught on but bcrypt didn’t is a mystery to me.

Eventually PBKDF2 found its way into OpenBSD (as pkcs5_pbkdf2) to support WPA wireless networks. When softraid crypto support was added, that code was convenient to reuse. Although the standard supports using different hash functions, the OpenBSD implementation only uses SHA1, as required by WPA. This is unfortunate since SHA1 is really not a very good choice for a slow, difficult to crack hash function.

To remedy this, we add another KDF function, bcrypt_pbkdf. It uses a custom version of bcrypt (bhash?), tweaked to make it more suitable as a key derivation function.


The original bcrypt generates 192 bit hashes by repeatedly rekeying a blowfish cipher, and then encrypting a 192 bit long magic string. The result of that encryption is the hash. bhash changes the length of the magic string to 256 bits, which is a better match for AES (to name one example). We can actually generate any length, but we throw less work away by making the hash size an even divisor of the key size.

The original difficulty parameter for bcrypt is the log2 number of times to rekey the cipher. bhash fixes this number at 64, and instead relies on the PBKDF2 rounds parameter to control difficulty.

almost pbkdf2

We then take this bhash function and loop it as per PBKDF2, feeding its output back into itself.

The OpenBSD implementation of bcrypt_pbkdf technically deviates from the standard in one respect. Instead of outputting the key material linearly as it is generated, if multiple cycles are required to generate all the requested key material, we mix it. Doing it the plain way exposes naive consumers to a potential flaw when using a single password to generate multiple keys. The attacker can (sometimes) simply perform the first cycle and check the result, creating asymmetric good guy vs bad guy required efforts. By mixing the output bytes together, we require the attacker to perform all of the work without taking any shortcuts.


bcrypt_pbkdf isn’t used yet, but should become the default for new softraid installs soon. Turns out softraid is taking a little longer, but the code is used in the new ssh key format and signify. Turns out soon was very optimistic for softraid, but it’s finally done.

The code lives in CVS.


I am aware of scrypt.

Posted 2013-06-03 21:40:44 by tedu Updated: 2016-09-19 17:56:19
Tagged: openbsd programming security