patternMinor
Attack on hash functions that do not satisfy the one-way property
Viewed 0 times
thewayattackhashsatisfyonepropertythatfunctionsnot
Problem
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.
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.
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.
- 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.
Solution
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.
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.
Context
StackExchange Computer Science Q#1225, answer score: 7
Revisions (0)
No revisions yet.