# Attack on hash functions that do not satisfy the one-way property

I am revising for a computer security course and I am stuck on one of the past questions. Here is it:

Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to authenticate that the message has come from her. She proposes to send a single message with two pieces: $$A \to B: \quad M, h(M \mathbin\parallel S_{ab})$$ where $h$ is a hash function and $\parallel$ denotes concatenation.

1. Explain carefully what Bob does to check that the message has come from Alice, and why (apart from properties of $h$) he may believe this.
2. Suppose that $h$ does not satisfy the one-way property and it is possible to generate pre-images. Explain what an attacker can do and how.
3. If generating pre-images is comparatively time-consuming, suggest a simple countermeasure to improve the protocol without changing $h$.

I think I know the first one. Bob needs to take a hash of the received message along with his shared key and compare that hash with the hash received from Alice, if they match then this should prove Alice sent it.

I am not sure about the second two questions though. For the second one, would the answer be that an attacker can simply obtain the original message given a hash? I'm not sure how that would be done though.

• Please give attribution for the image. Also, please consider copying the text so that it can be properly searched. – Raphael Apr 11 '12 at 20:13

Well, the message $M$ is already given to the adversary (it is sent to Bob over an insecure channel), so he needs not find it. To break the scheme he needs to send a new pair $M^*, h(M^*\|S_{ab})$ such that Bob will accept $M^* \ne M$ as the message sent by Alice.
For the second question: If it is easy to generate pre-images of $h$, the adversary might be able to learn the secret key $S_{ab}$ from $h(M\| S_{ab})$ thus breaking the scheme.
(Note this might not be trivial. The inverting process might output $M_1, S_1$ such that $h(M\|S_{ab})=h(M_1\|S_1)$, but this is not useful for the adversary.. Furthermore, if the adversary try again to invert $h$, he might get the same pre-image.)
For the third question: Now we assume inverting $h$ takes a lot of time, so let's make the adversary's life harder by requiring him to invert it many times in order to break the scheme. For instance, use the hash $k$ times $h(h(h(....h(M\|S_{ab})..))$. Other solutions exist as well.