4
$\begingroup$

Consider a function to create a tamperproof cookie as follows:

$$\text{cookie}(m, k) = m \| \text{hash}(m \oplus k)$$

where $m$ is a message provided by Alice, and k is a secret key known only to Bob. Bob receives m from Alice and returns the cookie to her. $\text{hash}(m \oplus k)$ functions as a MAC.

Why doesn't this properly authenticate the cookie? What's wrong with the MAC?

Improve this question
$\endgroup$
3
  • $\begingroup$ What if $m$ is really small? $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 27, 2019 at 4:01
  • 3
    $\begingroup$ I've edited your question. If the ^ is not $\oplus$ (x-or) please change it. $\endgroup$
    – kelalaka
    Commented Jan 27, 2019 at 7:08
  • 1
    $\begingroup$ @kelalaka Another good edit, consider yourself deputized :P I've changed the (then only) answer of Mikero according to your edits. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 27, 2019 at 21:35

2 Answers 2

Reset to default
4
$\begingroup$

To supplement the other answer, I will show that the proposed scheme cannot be shown secure assuming only collision resistance of the hash function. (I.e., the standard assumption on hash functions.)

Let $H' : \{0,1\}^* \to \{0,1\}^{\ell-1}$ be a collision resistant hash function. We construct another hash function $H : \{0,1\}^* \to \{0,1\}^{\ell}$ as follows: $$ H(x\|b) := H'(x)\|b,$$ where $b$ denotes the last bit of the input.

It is easy to see that $H$ must be collision resistant whenever $H'$ is collision resistant. This is because any collision in $H$ trivially (and by construction) must also yield a collision in $H'$.

If you, however, instantiate your proposed MAC construction with $H$, we end up with a scheme that is existentially forgeable under a known message attack. Suppose an adversary receives a message $m$ and a tag $t=H(k\oplus m)$.

Let $k = k'\|b_k$, $m=m'\|b_m$ $t=t'\|b_t$ where $b_k,b_m$ and $b_t$ are bits. Then by construction of $H$ we have

\begin{align*} t=&\ H\bigl((k'\|b_k) \oplus (m'\|b_m)\bigr)\\ =&\ H\bigl((k'\oplus m') \| (b_k\oplus b_m)\bigr)\\ =&\ H'(k'\oplus m')\|(b_k\oplus b_m). \end{align*}

This means, that the adversary can simply output $m^*=m'\|(b_m\oplus 1)$ and $t^*=t'\|(b_t\oplus 1)$ as a forgery. This will verify, since

\begin{align*} H(k\oplus m^*)=&\ H\bigl((k'\|b_k) \oplus (m'\|(b_m\oplus 1))\bigr)\\ =&\ H\bigl((k'\oplus m') \| (b_k\oplus b_m\oplus 1)\bigr)\\ =&\ t'\|(b_t\oplus 1). \end{align*}

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the response, but can you give me the gist of this in a less formal way? Crypto is not my strong suit. $\endgroup$
    – Justin
    Commented Jan 27, 2019 at 23:46
  • $\begingroup$ Say that the last bit of the message is also the last bit of the hash and it is not included in the rest of the hash calculation (this is a theoretical hash function, not one of the commonly used ones). Then if you capture the message and MAC then you can simply flip the last bit of the message as well as the last bit of the hash. Now this will be accepted because of how the hash is defined: the last bit of the hash simply is the last bit of the message. This is counter intuitive as it relies on the minimum theoretical requirements of hash functions rather than common well distributed hashes $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 28, 2019 at 1:30
  • $\begingroup$ (the key value will be the same, so XOR with the last bit of the key won't change the fact that you can simply flip the last bit of the hash) $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 28, 2019 at 1:32
1
$\begingroup$

Currently, it is not clear what should happen when $m$ and $k$ have different length. You should clarify what happens, even if it's just to say that $m$ and $k$ will always have the same length.

Regarding security, the function $m \mapsto H(k \oplus m)$ is actually a secure MAC when $H$ is a random oracle (and $m$ and $k$ always have the same length). But I doubt it is provably secure from any reasonable standard assumption on hash functions.

Besides, there are better (faster, more standard, with better basis for provable security) ways to do a MAC.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The problem I have with this answer is that for the construction to be secure that $k$ has to have a certain size (say, 128 bits). No such requirement is given for the message $m$. I would assume that a secure MAC would be able to protect messages of any size - the size of $k$ should not depend on the size of $m$, and vice versa. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 27, 2019 at 5:52
  • $\begingroup$ @MaartenBodewes It is pretty standard to consider MACs with message spaces other than $\{0,1\}^*$. Just consider any of the canonical information theoretically secure one time MACs, where the message space directly depends on the key size. $\endgroup$
    – Maeher
    Commented Jan 27, 2019 at 10:04
  • $\begingroup$ @Maeher I'm absolutely fine with considering those, but I would expect such restrictions to be in the specifications instead of just assuming they are there. And I would expect answers to pick up such vulnerabilities and specify how they can be mitigated. I'm not advising to use CBC-MAC either without indicating that it is insecure against length extension attacks. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 27, 2019 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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