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.

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

For the second one, would the answer be that an attacker can simply obtain the original message given a hash?

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.


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.