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 mathbinparallel S_{ab})$$ where $h$ is a hash function and $parallel$ denotes concatenation.
- 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.
- 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.
- 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.
Asked By : sam
Answered By : Ran G.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1225 Ask a Question Download Related Notes/Documents
