Equivalence of Secret IV and Secret Prefix MAC

Question

I read that the secret $IV$ and secret prefix $MAC$ methods are equivalent. Intuitively, this sounds reasonable because the $IV$ and the secret prefix are both the foundation of the inner state at the point of time when the actual message is hashed/compressed.

E.g. in "MDx-MAC and Building Fast MACs from Hash Functions" (link) by Preneel and Oorschot. Section 4.1 The Secret Prefix Method: "If the key consists of a complete block, this corresponds to a hash function with a secret IV."

With secret $IV$ $MAC$ I mean that the key is written into the $IV$ variables / the internal state before the message is hashed.

With secret prefix $MAC$ I consider the function $H(k\ ||\ m)$ where $H$ is a hash function, $k$ is the secret key, $m$ is the message and $||$ denotes concatenation.

I guess the security properties of these two schemes are indeed equivalent but how does this work in practice? For example some attacks against $MD4$ $MAC$s involve the work of offline $MD4$ computations. I can do that on messages with standard $MD4$ in the secret prefix $MAC$ setting (just leaving the unknown key out), but how can one do an offline computation when the secret $IV$ is unknown. How should the hash function be initialized and how (if at all) are the attacks applicable?

Examples of such attacks are:

New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5 (this targets $HMAC$ instead of secret prefix $MAC$, but I guess the attack is adaptable)

Password Recovery Attack on Authentication Protocol MD4(Password || Challenge) (... must leave out the reference here, due to missing repudiation)

Answer 1

There are a number of assumptions being made here, and I will make them explicit in case this was not what you had in mind.

The first assumption is that we are using a Merkle-Damgard hash. That is, given a compression function $C(h, m)$, we have (assuming a properly padded message) $$ H_{\text{IV}}(m_0 \| m_1\| \dots \| m_n) = C(C(C(C(\text{IV}, m_0), m_1), \dots), m_n). $$

The secret-prefix MAC is simply $H_{\text{IV}}(k \| m)$. I also assume that secret-prefix MAC uses the entire first block, that is, the secret key $k$ is the same size as $m_0$ above.

The secret-IV MAC sets the $\text{IV}$ to be the key: $H_{k}(m)$. But notice we can easily convert a secret prefix into a secret IV by setting $k' = C(\text{IV}, k)$. Therefore if you have a key-recovery attack on a secret-IV MAC, the process is exactly the same with secret-prefix, except the output you obtain is $C(\text{IV}, k)$ instead of $k$. Likewise, an attack on secret-prefix MAC is highly likely to target $C(\text{IV}, k)$ and not $k$ directly. To define the IV, you cannot use the standard APIs for hashing (e.g., md4_init(&ctx)), but will likely have to write your own code.

Recovering this secret IV, in either case, will allow you to forge any message and completely destroy the security of the MAC. In the secret-prefix case, however, recovering the IV does not immediately translate to recovering the original key.