A Key Derivation Function (KDF) is a function that takes a secret input of possibly non-uniform distribution (like a password, or the result of a Diffie-Hellman key exchange) and generates one or more keys which are uniform random and pairwise independent. But these are not guarantees - typically if you can break some trusted cryptographic primitive, you can break the KDF. For instance, if you can easily invert SHA-1, then you could break a KDF based on SHA-1 by taking one of the resulting derived keys, inverting it to get the master key, and then rederiving the rest of keys. The hope is that inverting SHA-1 is hard to do.
Botan's interface to KDFs is a simple functional interface: you pass it the master key and other parameters, along with the desired length of the output, and it will return it.
While working on a little something, I started writing an implementation of PBKDF2 in Python, but realized that someone had probably already done that for me. And indeed I found an implementation, which in addition to looking quite sound and well written (and under a BSD license), showed me a design concept that I quite honestly had never considered, which was having the KDFs be set once and then streaming the output, just like a file:
>>> import PBKDF2
>>> prf = PBKDF2.PBKDF2("secret key", "salt")
>>> prf.read(32).encode("hex")
'0a86360e7c28c9cdde8576385d754fe16e1de3839ce653a5c4e14790e930d13b'
>>> prf.read(32).encode("hex")
'2f54a2fde841900e538fa13834132d3d2fd39b525657f158fa0bbf1660ada490'
>>> prf.read(32).encode("hex")
'2f6565581e6815ecba9baae2944eb171bfe47c196f7d27e74d8ce3b35d1791fa'
This also neatly handles the problem of IEEE 1363's KDF1, which is a very simple KDF that is limited to the output length of the hash (16 bytes for MD5, 20 for SHA-1, 32 for SHA-256): it can simply return an empty value when "EOF" is reached.
This could also be applied to random number generators, and with the right design one could even provide to a function either (say) a KDF or a filesystem object pointing to a file full of random bytes, and have it do the right thing in either case. However C++'s iostreams is sufficiently baroque that this part may not be worth the effort.
Abstractly, one could represent all of these cases with
std::tr1::function<maybe_a<byte> ()>, where
maybe_a<> is a template class I have not yet written
(but is basically the same as Haskell's Maybe).
But without pattern
matching using it would be kind of a pain, so it would probably be
simpler to just define it as returning a byte or throwing an
exception. Throwing an exception to represent what is basically EOF is
pretty inelegant, but I'm not seeing good alternatives given the
language support (or lack thereof) that is available.
Posted 2008/05/14 in devnotes; no comments
< Botan 1.7 Progress Report: Removing Shared State, Telegraphic Version | Mailing List Downtime >