hkdf-sha256

2022-11-18 · 7 min read

• #crypto
• #rust
• #tls

• HKDF: HMAC-based Key Derivation Function.
• We'll use a specific hash function (SHA-256) for simplified analysis. You can use any cryptographic hash function, but some constants will need to change to accomodate the different digest block size.
• Why this page: I keep forgetting perf-relevant details like ideal salt / IKM sizes, or HKDF salt/PRK caching. Seeing all the details laid out flat, with strong types, makes this all clear. As an example, you can save 60-70% on key derivation time if you reuse the intermediate derived Prk when deriving multiple secrets from one common input secret.

usage #

// SALT is usually a static, constant value used for domain
// separation.
//
// Using a unique salt for your application improves the security
// bounds on the HKDF. Intuitively, you get a unique PRF just for
// your application, rather than a shared PRF used by all the other
// default-config'ed users of HKDF-SHA256.
//
// A constant salt is useful for performance since we can
// pre-compute the salted `hkdf::Salt` state.
//
// I also like to pre-hash the salt, since it guarantees the value
// is shorter than the hmac `2 * sha256::BLOCKSIZE` key size
// threshold, which mandates an extra hash if exceeded. If your
// language supports it, you can even compute this at compile time.
let salt: &[u8] = sha256::digest(b"MY-DOMAIN-SEPARATION-VALUE");

// IKM is the input secret
let ikm: &[u8] = b"MY-SECRET-KEY-MATERIAL";
// For most cases, think of `infos` as a unqiue label for the
// child-secret. You can also bind higher-level application data
// like negotiated protocol versions or public keys or other
// session-specific data here.
let infos: &[&[u8]] = &[b"file key"];
// The length of the output secret. Note that there is a maximum
// output length of `255 * BLOCKSIZE` bytes.
let output_secret_len: usize = 32;

// If you just need to derive a few child secrets, just use the
// one-line convenience method:
let secret = hkdf::derive(salt, ikm, infos, output_secret_len);

// Otherwise, at a minimum, consider caching or pre-computing the
// salted HKDF(s) used in your application.
//
// You can then reuse the salted_hkdf multiple times, even with
// different root secrets (IKMs).
let salted_hkdf = hkdf::Salt::new(salt);
let secret1 = salted_hkdf
	.extract(ikm1)
	.expand(infos, secret_len);
let secret2 = salted_hkdf
	.extract(ikm2)
	.expand(infos, secret_len);

// If you use a single input key/secret to derive many child
// secrets, reuse the extracted PRK instead of rederiving it each
// time:
let prk = salted_hkdf.extract(ikm);
let secret1 = prk.expand(&[b"file key"] /* infos */, secret_len);
let secret2 = prk.expand(&[b"noise key"] /* infos */, secret_len);

definitions #

SHA256 #

mod sha256 {
	const BLOCK_SIZE: usize = 32;
	const INTERNAL_BLOCK_SIZE: usize = 64;

	/// A finalized SHA-256 hash digest. 32 bytes. 256 bits.
	struct Hash([u8; BLOCK_SIZE]);

	/// An intermediate SHA-256 digest state.
	struct Context { /* .. */ }

	impl Context {
		fn new() -> Self { /* .. */ }
		fn update(&mut input: &[u8]) { /* .. */ }
		fn finish(self) -> sha256::Hash;
	}

	/// A convenience function to easily digest many inputs in
	/// one line.
	fn digest(inputs: &[&[u8]]) -> sha256::Hash {
		let mut ctx = sha256::Context::new();
		for input in inputs {
			ctx.update(input);
		}
		ctx.finish()
	}
}

HMAC-SHA256 #

mod hmac {
	/// A keyed HMAC PRF. Normally this would be used to compute
	/// MAC tags for message authentication, but HKDFs use this
	/// a bit differently.
	struct Context {
		// IPAD := [0x36; 32]
		// inner(x) := H(K xor IPAD || x)
		inner: sha256::Context,
		// OPAD := [0x5c; 32]
		// outer(x) := H(K xor OPAD || x)
		outer: sha256::Context,
	}

	impl Context {
		/// Create a new keyed HMAC context for digesting multiple
		/// inputs.
		fn new(key: &[u8]) -> Self {
			// Keys longer than the internal block size (64 bytes)
			// must be pre-hashed to make them smaller.
			let key_hash: sha256::Hash;
			let key = if key.len() > 64 {
				key_hash = sha256::digest(&[key]);
				key_hash.0.as_slice()
			} else {
				key
			};

			// zero-pad key to the internal block size (64 bytes).
			let mut padded_key = [0u8; 64];
			padded_key[..key.len()].copy_from_slice(key);

			// ikey := [ key_i ^ 0x36 ]_{i in 0..64}
			let mut ikey = [0x36_u8; 64];
			for (ikey_i, key_i) in ikey.iter_mut().zip(&padded_key) {
				*ikey_i ^= key_i;
			}

			// okey := [ key_i ^ 0x5c ]_{i in 0..64}
			let mut okey = [0x5c_u8; 64];
			for (okey_i, key_i) in okey.iter_mut().zip(&padded_key) {
				*okey_i ^= key_i;
			}

			let mut hmac_key = Self {
				inner: sha256::Context::new(),
				outer: sha256::Context::new(),
			};

			hmac_key.inner.update(&ikey);
			hmac_key.outer.update(&okey);
			hmac_key
		}

		fn update(&mut self, input: &[u8]) {
			self.inner.update(input);
		}

		fn finish(mut self) -> sha256::Hash {
			let inner_output = self.inner.finish();
			self.outer.update(&inner_output);
			self.outer.finish()
		}
	}

	/// A convenience function for easily HMAC'ing multiple
	/// inputs in one line.
	fn digest(key: &[u8], inputs: &[&[u8]]) -> sha256::Hash {
		let mut ctx = hmac::Context::new(key);
		for input in inputs {
			ctx.update(input);
		}
		ctx.sign()
	}
}

• Useful perf tips:
  • You can avoid an extra Hash(key) when doing an HMAC so long as the key is no longer than the internal hash block size (e.g., 64 bytes for SHA-256).
  • If a key is fixed for multiple HMAC invocations, you can compute the hmac::Context once and reuse it for multiple hmac::Context::sign's, avoiding at least 2 hashes and some padding+XORs.

HKDF-SHA256 #

• Extract a PRK (Pseudo-Random Key) from IKM (input key material) and domain separator (called salt).
• Expand a PRK and label or context into secrets of varying sizes.

mod hkdf {
	/// A domain-separated (salted) HKDF context ready to expand
	/// into an `hkdf::Prk` using some IKM (Input Key Material).
	///
	/// `Salt` is (relatively) expensive to construct, so it's
	/// good to compute once and reuse.
	///
	/// `Salt` contains an `hmac::Context`, domain-separated by
	/// `salt_value`.
	///
	/// `Salt.0 := HMAC(salt_value, ___)`
	struct Salt(hmac::Context);

	impl Salt {
		fn new(salt_value: &[u8]) -> Self {
			Self(hmac::Context::new(salt_value))
		}

		/// HKDF-extract a new PRK (keyed HMAC context) from some
		/// IKM (Input Key Material).
		fn extract(&self, ikm: &[u8]) -> hkdf::Prk {
			let mut salt_ctx = self.0.clone();
			salt_ctx.update(ikm);
			let prk = salt_ctx.finish().0;
			hkdf::Prk(hmac::Context::new(&prk))
		}
	}

	/// A domain-separated and "extracted" Pseudo-Random Key
	/// ready to now "expand" into many different child secrets
	/// of varying lengths.
	///
	/// `Prk` is (relatively) expensive to construct, so it's
	/// good to compute once and reuse.
	///
	/// `PRK.0 := HMAC(HMAC(salt, ikm), ___)`
	struct Prk(hmac::Context);

	impl Prk {
		/// HKDF-expand a new secret of `out_len` bytes from a
		/// `Prk`, using `infos` for domain separation or
		/// application specific context.
		///
		/// For example, from a single root secret, you might
		/// derive many subkeys simply by using different `infos`
		/// labels, like "cert key" or "sealing key" or "btc key
		/// 54".
		///
		/// HKDF-SHA256 has a max output secret limit of
		/// `255 * 32 == 8160` bytes.
		fn expand(&self, infos: &[&[u8]], out_len: usize) -> Vec<u8> {
			// N is the number of sha256-block-sized blocks we need
			// to derive in order to cover the desired output length
			// `out_len`.
			//
			// N := ceil(out_len / sha256::BLOCK_SIZE)
			//   := (out_len.saturating_sub(1) / sha256::BLOCK_SIZE) + 1
			let n = (out_len.saturating_sub(1) / 32) + 1;
			let n = u8::try_from(n).expect("out_len is too large");

			// T      := T(1) || T(2) || .. || T(N)
			// T(0)   := b"" (empty byte string)
			// T(i) := hmac::digest(prk, T(i-1) || infos || [ i ])

			let mut out = Vec::with_capacity(len);
			// T(i-1)
			let mut t_im1 = [0u8; 32];

			for i in 1..=n {
				// T(i) := hmac::digest(prk, T(i-1) || infos || [ i ])
				let mut t_i = {
					let mut ctx = self.0.clone();
					if i != 1 {
						ctx.update(&t_im1);
					}
					for info in infos {
						ctx.update(info);
					}
					ctx.update(&[i]);
					ctx.finish().0
				};
				t_im1 = t_i;

				if i < n {
					out.extend_from_slice(&t_i[..]);
				} else {
					// the last block will need to be truncated if
					// `out_len` isn't a multiple of the block size.
					let l = 32 - (((n as usize) * 32) - out_len);
					out.extend_from_slice(&t_i[..l]);
				}
			}

			out
		}
	}

	/// A convenience function to derive a secret of size `out_len`
	/// from `ikm` (Input Key Material)
	fn derive(
		salt: &[u8],
		ikm: &[u8],
		infos: &[&[u8]],
		out_len: usize,
	) -> Vec<u8> {
		let salt = hkdf::Salt::new(salt);
		let prk = salt.extract(ikm);
		prk.expand(infos, out_len)
	}
}

• Useful perf tips:
  • The salted HKDF function can be cached. If you find yourself deriving secrets from multiple different IKMs, this trick may be useful.
  • The extracted PRK can be cached. If you find yourself deriving many different secrets from one root secret, this trick may be useful. I've found this trick in particular can save between 60-70% on key derivation time.

RFCs #

• RFC 2104: HMAC: Keyed-Hashing for Message Authentication
• RFC 5869: HKDF: HMAC-based Extract-and-Expand Key Derivation Function