HMAC data and key swap

au flag

In some contexts (HKDF (RFC-5869 sec 2.2) and Bitcoin's BIP32 (master key generation)), I have seen the key and the data swapped for HMAC. E.g., let HMAC be a function $h:\{0,1\}^c \times \{0,1\}^b \to \{0,1\}^c$ (usual notation) defined for a key $k$ and data $m$ as $h(k, m)$. Well, some people let $k$ be a fixed public value (for instance, Bitcoin seed), and encode secret bytes in $m$.

I understand why they would want to do this, for instance, the input material (that can be a secret key) can have any prescribed length $c$. I assume they do not expect integrity, they only want randomness.

I would expect security (or at least integrity) to depend on the secrecy of $k$ and properties on the underlying hash function. Indeed, using the results of Bellare's "New Proofs for NMAC and HMAC" 1, we do have a PRF as soon as the compression function of the hash function is a PRF, and if implementors did the right thing, this actually does not depend on the secrecy of $k$.

But it looks to me that the proof assumes a uniformly random, secret key. Does the PRF proof still hold if we reveal $k$ to the attacker?

(Note: This would be obvious if $k$ and $m$ played symmetrical roles in the HMAC construction - this is also not the case.)

kelalaka avatar
in flag
If I've understood your question correctly; If you fix the key of HMAC you select a PRF from the HMAC family. Now you have a PRF to use.
tr flag

I will only address the HKDF part.

HKDF was introduced in the following paper:

In this context, HMAC is used for two somewhat distinct purposes: 1) randomness extraction and 2) variable (input/output) length PRF.

The key-swap happens for randomness extraction. The situation here is that we are given a keying material $IKM$ that is not (pseudo)uniform random and want to create a key $PRK$ that is pseudorandom (i.e., computationally indistinguishable from random).

As you noted, HMAC is also shown to be a PRF. However, we cannot rely on PRF security to argue the security of $PRK$. But the paper argues that this use of HMAC is suitable for providing a computation randomness extractor (see section 6).

Speaking of PRFs, an interesting thing to note is that some security proofs, like TLS, actually rely on the so-called PRF-ODH assumption( When applied to the use of HKDF in TLS: recall that the two parties exchange DH shares $(g^x, g^y)$; the (on variant of the) assumption roughly says that: the function $F(K, X) = HMAC (X, K) $ is a PRF under the assumption that the underlying compression function is a random oracle; even if the attacker was given access to an oracle $\mathcal{O}(T,v) = F (T^x, v) $. (Omitted here: restrictions on values of $(T,x)$ and the maximal number of queries).

Note here that the function $F$ above has keyspace $\langle G \rangle$, the group used for the DH exchange. So we are dealing with a uniform random key on the keyspace in the context of PRF-ODH.

P.S: consider reading this answer as well


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.