Is this function a secure MAC?

Consider the following function:
$$f_k(mm')=\operatorname{HMAC}_{\operatorname{HMAC}_k(m)}(mm')$$

Can I use $$f$$ as a secure MAC?

• Given that HMAC is a PRF, I'm reasonably sure that $f$ is also a PRF and therfore a secure MAC. Though I'm too tired to do the proof today. – SEJPM Nov 7 '19 at 20:14
• This is roughly an instance of the cascade construction. See cseweb.ucsd.edu/~mihir/papers/cascade.html and cr.yp.to/papers.html#xsalsa for analysis. – Squeamish Ossifrage Nov 7 '19 at 20:51
• @SqueamishOssifrage the papers you have referred are very complex. Could you provide a simple proof? I think I can claim that if f is not PRF, then there is a distinguisher ${\cal D}$ that can distinguish a random number from $f$ with probability better than random guess and then I show that having such a distinguisher enables us to create a distinguisher for HMAC with the same probability which is not correct. – Reza Nov 7 '19 at 21:29
• The short answer is that if the distinguishing advantage against your HMAC (under whatever hash function you've chosen) is at most $\varepsilon$, then the distinguishing advantage of any $q$-query adversary against your 2-level cascade composition is at most $\varepsilon + q\varepsilon$. Maybe at some point I will be inclined to elaborate in a full answer but that point is not right now. – Squeamish Ossifrage Nov 7 '19 at 21:40

If you look at $$k' = \operatorname{HMAC}_k(m)$$ as a key derivation function then you'd expect that $$\operatorname{HMAC}_{k'}(mm')$$ is secure, even if $$m$$ is also used to derive $$k'$$. So from a purely functional point of view then yes, this should be secure.
Also from a functional view I would wonder why there is a repetition of $$m$$, because as it is used to derive key $$k'$$ it is already included in the calculation of the MAC value, and repeating it is therefore moot; the repetition of $$m$$ doesn't do anything for security. You could just use $$m$$ for the KDF alone, so then the outer HMAC is just $$\operatorname{HMAC}_{k'}(m')$$
Finally, the presumption is of course that $$k$$ has enough bits to be used as a HMAC key; generally the same size key as the hash output is recommended.
I don't see any reason why $$f_k(mm')=\operatorname{HMAC}_k(\operatorname{enc}(m,m'))$$ would not work, where $$\operatorname{enc}$$ is a canonical encoding function. This is a more efficient MAC if $$m$$ is large.