Suppose that Alice wants to send a message to Bob and wants to make sure that Bob knows he has received the correct message.

She sends the pair $(x,h(x))$ for some hash function (preimage resistant, second preimage resistant and collision resistant). Bob receives a pair $(x',y')$ he calculates $h(x')$ and if he has $y'$, he concludes that the message has not been tampered with.

But the attacker could also change $y'$. So is the hash of $x$ actually sent by another means?


2 Answers 2


The goal of a MDC is to provide integrity guarantees. That is, given the value $h(x)$, it should be possible to check whether $x$ has been tampered with. The attack scenario you are describing requires authenticity guarantees, i.e., you want to be able to detect whether the tuple is actually from Alice. To achieve this, there are many possible solutions. One simple example would be to require an additional signature from Alice on the tuple (this is for the setting where Bob will need to verify the authenticity and the integrity of the tuple). In case you only require private verification, i.e., Alice stores the data somewhere and when retrieving them again wants to verify authenticity and integrity, you could simply use a message authentication code (MAC).

To your question: in many practical scenarios the hash is delivered by some other means. Yet, in many cases you also have no (cryptographic) authenticity guarantees. Take, for example, the hashes which are provided when you download files. In case you are using plain HTTP you also only can verify whether the downloaded file fits the hash, but you can not verify whether the page you are viewing is actually the page it should be.


The difference can be phrased as a difference of threat models.

  1. In the independent random error channel, every bit independently has probability $p$ of being transmitted as is, and probability $q = 1 - p$ of being flipped. There's a disinterested monkey on the channel flipping a coin weighted by $p$ to decide whether to flip each bit. In this channel, if you affix $h(x)$ for some random $t$-bit function $h$, then for any error $e$ in $x$, there is only a $2^{-t}$ probability that $h(x) = h(x + e)$ and thus that $h$ will fail to detect the modification. (Exercise for the reader: What if a bit is flipped in $h(x)$ rather than in $x$?) You can use this with $p$ and $q$ to pick the number $t$ of bits in the tag to use to force the probability of an undetected error below a threshold you care about.

    Thus a random function $h$ serves as a naive checksum, and in practice we just pick a function like SHA3-256 for $h$ under the conjecture that it looks an awful lot like a random $h$. You could do much better against this adversary by using, e.g., a CRC, which guarantees detection of at least 1-bit errors, and, depending on the message and CRC size, can guarantee detection of even larger errors.

  2. In the adversarial channel, an actively malicious adversary is intercepting the message and tampering with it. This adversary is not only smarter than the independent random bit-flipping monkey, but actually knows everything about your protocol except possibly some secrets at the end points. Your adversary knows that messages are of the form $(x, h(x))$, and actively seeks to sabotage them. So the knowledgeable adversary will stop the message $(x, h(x))$ in its tracks, pick an evil message $x' \ne x$, and pass on $(x', h(x'))$, and immediately win the game.

    This happened because your protocol involved no secrets at the end points, so the adversary is not missing any information about how to impersonate any participants in the protocol as far as the other participants can tell.

    (a) Suppose the sender and receiver, Alice and Bob, share a secret key $k$ not known to the adversary. Then they can use a message authentication code $H_k(x)$ instead of a fixed random function $h(x)$. Without $k$, the adversary can't compute $H_k(x)$, but Alice can compute $a = H_k(x)$ to send alongside $x$, and on receipt of $(x', a')$, Bob can compute $H_k(x')$ and reject as a forgery if it's not $a'$.

    (b) If, instead, Alice has a private signing key and Bob knows her corresponding public verification key, Alice can affix a signature to the message which Bob can verify.

    Either way, there has to be some secret information that the adversary does not know by which one participant of the protocol can distinguish another from the adversary.


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.