2
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ Where did you read this? Because in the current state this question does not make much sense to me. I'm not saying that you are incorrect or wrong in any way, it could just be me not understanding what's going on, hence a request for clarification. $\endgroup$ – Maarten Bodewes Nov 22 '16 at 18:07
  • $\begingroup$ Just updated the question. I hope it is more clear now. $\endgroup$ – firefexx Nov 23 '16 at 12:10
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer, it explains parts of the relationship between the secret-prefix and the secret-IV. In fact, you pointed out how one could use an attack against secret-IV MAC to attack a secret-prefix MAC (guess this still requires inverting the compression function). But originally, my question targeted the other way around. Most attacks seem to aim against secret-prefix MAC and I was wondering how to use this to attack secret-IV MAC. $\endgroup$ – firefexx Nov 23 '16 at 14:23
  • $\begingroup$ What attacks are you thinking of? Note that the MD4 password recovery attack you linked to violates our assumptions: the key (password) and the message share the same block, and this gives more power to the attacker. The NMAC attack you link to looks like a secret-IV recovery to me, but I only skimmed it. $\endgroup$ – Samuel Neves Nov 23 '16 at 14:36
  • $\begingroup$ Ok, you are right. It seems a concrete answer depends on a concrete attack. I had the hope there is a more general relation. Maybe I will post a further comment or a new more specific question when I have something more specific in mind. $\endgroup$ – firefexx Nov 23 '16 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.