Hash functions and what they are for

A hash fingerprints a message but cannot identify its sender

A message can change in transit. A fingerprint lets the receiver detect a change, even one bit. A hash function is that fingerprint: a function that takes an input of any length and always produces an output of the same fixed length. Two different inputs almost never produce the same fingerprint, so comparing fingerprints is a cheap way to check whether the underlying message is still the one that was sent.

Formula

Hash function

$$h = H(M)$$

$M$

the input message, of variable length

$H$

the hash function

$h$

the hash value, digest or checksum: fixed-size regardless of the length of M

A handful of hash functions are in wide use: CRC (CRC-16, CRC-32), MD5, SHA-1, SHA-2, SHA-3, and RIPEMD160. CRC is not a cryptographic hash function. It was built to catch accidental transmission errors, not to resist someone deliberately trying to forge a matching checksum. MD5 and SHA-1 were designed for cryptographic use, but both have since been found insufficient: practical collision attacks exist against both.

Because the input space (every possible message) is far larger than the output space (a fixed number of bits), collisions, two different inputs producing the same hash, always exist. A “good” hash function does not avoid this. It just spreads its outputs evenly across the output space, so that outputs look random and finding a collision on purpose stays computationally infeasible.

The basic use of a hash for integrity works like this: the sender computes $h = H(M)$ over the message, then can separately encrypt the message for confidentiality, and sends both the (possibly encrypted) message and its hash. The receiver decrypts if needed, recomputes the hash over the received message, and compares it to the one that was sent. A match means the message travelled unchanged.

For this to hold, two conditions have to be true:

1. An attacker must not be able to recover the original message from its hash alone, since a hash function is one-way, not an encryption scheme.
2. An attacker must not be able to find a different plaintext with the same hash. If they could, they could substitute a forged message and the hash comparison would still pass.

Padding records the original message length

Before hashing, the variable-length input is padded to an exact multiple of the hash function’s fixed block size. The padding includes the original message’s length in bits. That length field is a deliberate security measure: it makes it harder for an attacker to construct a different message that produces the same hash, since the forged message would also need to match the original’s exact bit length.

Protecting the digest prevents an attacker replacing both values

Cryptographic hash functions are the building block behind three applications.

Message authentication. The output is called a message digest here. The naive scheme above, send $m$ and $h(m)$, checks integrity but nothing about who sent it. Since computing $h$ needs no secret, anyone, including an attacker, can do it.

An attacker (call them Darth) sitting between Alice and Bob intercepts Alice’s message, replaces it with a message of their own choosing, and recomputes the hash to match. Bob receives the altered message and the new hash, and since he cannot tell that either value differs from what Alice originally sent, the substitution goes undetected. This is a person-in-the-middle attack on origin authentication, closely related to but distinct from plain integrity.

The fix is to protect the digest itself with something the attacker does not have. A Message Authentication Code (MAC), also called a keyed hash function, binds the hash to a secret key shared by sender and receiver. A digital signature binds it to the sender’s private key instead. See MACs and HMAC and digital signatures.

Digital signatures work similarly to MACs but use public-key cryptography instead of a shared secret: the sender encrypts the message’s hash with their own private key, and anyone holding the corresponding public key can verify it. Forging a signature would require the sender’s private key, which only the sender has.

Other applications of cryptographic hash functions, beyond message authentication and digital signatures, include one-way password files, intrusion detection, virus detection, and pseudorandom number generation.

Pitfall

A hash function on its own gives integrity only. It never gives confidentiality (it does not hide the message, it fingerprints it) and it never gives origin authentication on its own (anyone can compute a hash, so a hash alone cannot prove who computed it). Both of those need a MAC or a signature on top, which is exactly why the next two topics exist.

Exam detail

Two conditions define a cryptographic hash function, as opposed to a hash function in general: an attacker must not be able to recover the message from its hash, and an attacker must not be able to find a different message with the same hash. CRC satisfies neither by design; MD5 and SHA-1 were built to satisfy both but have since failed the second one in practice.

Recall

A message and its plain, unprotected hash are sent together. Why does this still fail to authenticate the sender, even though it does catch accidental corruption?

Computing a hash requires no secret. An attacker can replace the message with one of their own choosing and recompute a matching hash, so the receiver’s comparison still passes. Catching corruption only needs the hash to change when the message changes; proving who sent it needs the hash itself to be something the attacker cannot forge, which requires a shared secret key (a MAC) or the sender’s private key (a signature).