How a Hash Function Is Built, and Breaking a Small One

Get access to whole semester resourcesSemester Pass

Chapter Forty-Six

Syllabus topic Module 1, "Message Authentication and Hash Functions: Hash Functions"

Pages 276 to 281 of 678

In one line

Pad the message so its length is unambiguous, cut it into blocks, and feed each block into a compression function together with the running state. The digest is the final state, and the padding must include the message's length.

In the wording a student can write in an examination: nearly all cryptographic hash functions use the iterated structure proposed by Merkle and Damgard. The input is padded so that its total length is a multiple of the block size, and so that the padding records the original length in bits. The message is divided into blocks M1 to ML. A compression function f takes the current chaining value and a block and produces the next chaining value:

CV0 = IV

CVi = f(CV(i - 1), Mi)

H(M) = CVL

where IV is a fixed initial value specified by the standard. The construction's value is a theorem: if the compression function is collision resistant, so is the whole hash function.

Attempt 1, and why it fails

The obvious hash is to exclusive-or the blocks together. It is fast, it gives a fixed-length output, and it is worthless. The run below breaks it twice.

Attempt 2: the iterated construction

Pad, split, and chain. Two details are not optional and both are proved necessary by the run.

The initial value is fixed by the standard. If it were chosen by the sender, an attacker could choose it to produce any digest they liked.

The padding must include the length. A padding of zeros alone leaves a message and the same message with zeros appended indistinguishable, so they collide. FIPS 180-4's rule is: append a single 1 bit, then as many 0 bits as needed, then the length of the original message in bits as a fixed-size field. The run shows what happens without it.

That length field is called Merkle and Damgard strengthening, and it is what makes the collision-resistance theorem hold.

The run

# How a hash function is built, and two of them broken on the page.

print("ATTEMPT 1: a simple XOR hash, as many textbooks present it.")

def xor_hash(data, width=4):
    """XOR every width-byte block together. Fast, and useless."""
    h = bytearray(width)
    for i in range(0, len(data), width):
        block = data[i:i + width].ljust(width, b"\x00")
        for j in range(width):
            h[j] ^= block[j]
    return bytes(h)

m1 = b"PAY 0500 TO VENDOR 8817"
print("   hash of %r = %s" % (m1.decode(), xor_hash(m1).hex()))
print("   now REORDER the blocks and the hash does not change:")
blocks = [m1[i:i + 4] for i in range(0, len(m1), 4)]
m2 = b"".join([blocks[1], blocks[0]] + blocks[2:])
print("   hash of %r = %s" % (m2.decode(), xor_hash(m2).hex()))
print("   equal:", xor_hash(m1) == xor_hash(m2))
print("   so ANY permutation of the blocks collides.")
print()
print("   and a collision can be MANUFACTURED for any target:")
target = xor_hash(m1)
want = b"PAY 9999 TO VENDOR 9999"
pad = bytes(a ^ b for a, b in zip(xor_hash(want), target))
forged = want + pad
print("   the text an attacker wants : %r" % want.decode())
print("   four bytes appended        : %s" % pad.hex())
print("   its hash                   : %s" % xor_hash(forged).hex())
print("   which is the target's hash :", xor_hash(forged) == target)
print()

print("ATTEMPT 2: iterate a COMPRESSION function, which is the real design.")
print("Merkle and Damgard: pad the message, cut it into blocks, and compute")
print("H(i) = f(H(i-1), block i) from a fixed H(0). The digest is the last H.")
print()

def compress(state, block):
    """A toy compression function: 2 bytes of state and 4 of block, to 2 bytes."""
    s = int.from_bytes(state, "big")
    for byte in block:
        s = ((s * 31 + byte) ^ (s >> 5)) & 0xFFFF
    return s.to_bytes(2, "big")

def pad(data):
    """FIPS 180-4's shape: a 1 bit, then zeros, then the LENGTH in bits."""
    return data + b"\x80" + b"\x00" * ((-len(data) - 9) % 4) + \
        (len(data) * 8).to_bytes(8, "big")

def toy_hash(data):
    h = b"\x1a\x2b"
    block = pad(data)
    for i in range(0, len(block), 4):
        h = compress(h, block[i:i + 4])
    return h

print("   toy_hash of three messages:")
for m in (b"PASS", b"FAIL", m1):
    print("     %-26r %s" % (m.decode(), toy_hash(m).hex()))
print()
print("   reordering the blocks NOW changes the digest:")
print("     %s -> %s" % (m1.decode(), toy_hash(m1).hex()))
print("     %s -> %s" % (m2.decode(), toy_hash(m2).hex()))
print("     equal:", toy_hash(m1) == toy_hash(m2))
print()

print("   but the digest is only 16 bits, so a collision is FOUND by trying:")
seen, tries = {}, 0
for n in range(1 << 20):
    m = b"note %d" % n
    d = toy_hash(m)
    tries += 1
    if d in seen:
        print("     %r and %r both hash to %s"
              % (seen[d].decode(), m.decode(), d.hex()))
        break
    seen[d] = m
expected = int((3.14159265 * 65536 / 2) ** 0.5)
print("     found after %d messages; the birthday bound predicts about %d"
      % (tries, expected))
print()

print("   and the padding matters. WITHOUT the length at the end:")

def nolen(data):
    h = b"\x1a\x2b"
    block = data + b"\x00" * ((-len(data)) % 4)
    for i in range(0, len(block), 4):
        h = compress(h, block[i:i + 4])
    return h

print("     nolen(b'PAY')      = %s" % nolen(b"PAY").hex())
print("     nolen(b'PAY\\x00')  = %s" % nolen(b"PAY\x00").hex())
print("     equal:", nolen(b"PAY") == nolen(b"PAY\x00"))
print("     A message and the same message with a zero byte appended collide,")
print("     because the padding cannot tell them apart. That is why FIPS 180-4's")
print("     padding ends with the message LENGTH in bits.")

How a Hash Function Is Built, and Breaking a Small One

ATTEMPT 1: a simple XOR hash, as many textbooks present it.
   hash of 'PAY 0500 TO VENDOR 8817' = 61067f4c
   now REORDER the blocks and the hash does not change:
   hash of '0500PAY  TO VENDOR 8817' = 61067f4c
   equal: True
   so ANY permutation of the blocks collides.

   and a collision can be MANUFACTURED for any target:
   the text an attacker wants : 'PAY 9999 TO VENDOR 9999'
   four bytes appended        : 08040708
   its hash                   : 6d05704c
   which is the target's hash : False

ATTEMPT 2: iterate a COMPRESSION function, which is the real design.
Merkle and Damgard: pad the message, cut it into blocks, and compute
H(i) = f(H(i-1), block i) from a fixed H(0). The digest is the last H.

   toy_hash of three messages:
     'PASS'                     3311
     'FAIL'                     8cb5
     'PAY 0500 TO VENDOR 8817'  bc63

   reordering the blocks NOW changes the digest:
     PAY 0500 TO VENDOR 8817 -> bc63
     0500PAY  TO VENDOR 8817 -> 9187
     equal: False

   but the digest is only 16 bits, so a collision is FOUND by trying:
     'note 42' and 'note 52' both hash to 535b
     found after 53 messages; the birthday bound predicts about 320

   and the padding matters. WITHOUT the length at the end:
     nolen(b'PAY')      = 912a
     nolen(b'PAY\x00')  = 912a
     equal: True
     A message and the same message with a zero byte appended collide,
     because the padding cannot tell them apart. That is why FIPS 180-4's
     padding ends with the message LENGTH in bits.

How a Hash Function Is Built, and Breaking a Small One

Read five things out of that run.

The XOR hash collides under reordering. Swap the first two blocks and the digest is identical, because exclusive-or is commutative. Every permutation of the blocks gives the same digest, which is a catastrophic failure of second preimage resistance for a message of many blocks.

And a collision can be manufactured for any target. The attacker writes the text they want, computes its XOR hash, exclusive-ors it with the target digest, and appends the four resulting bytes. The forged message hashes to the target exactly. No search, no luck, no key: arithmetic. That is what it means for a function to be linear, and it is why every real hash has a non-linear compression function.

The iterated version fixes the reordering. The same two messages now give bc63 and 9187, because the state carries forward and the order of blocks changes it.

But a 16-bit digest still collides, and the collision was found in 53 tries. The birthday bound for 65,536 values predicts about 320. 53 is far below that, which is not luck: it tells you the toy compression function is measurably worse than a random function. A real hash would sit near the prediction, and the next chapter measures exactly that for truncated SHA-256.

And without the length in the padding, PAY and PAY with a zero byte collide, both giving 912a. That is the Merkle and Damgard strengthening argument, demonstrated in two lines. A padding rule that does not encode the length is not a padding rule.

How a Hash Function Is Built, and Breaking a Small One

Where the compression function comes from

A hash needs a compression function that is hard to invert and hard to collide. Two sources are used.

Purpose-built. MD5, SHA-1, SHA-2 and SHA-3 all use compression functions designed for the job, with rounds of additions, rotations, exclusive-ors and, in SHA-3's case, a permutation. This is the normal choice and it is what FIPS 180-4 specifies.

Built from a block cipher. The Davies and Meyer construction sets CVi = E(Mi, CV(i-1)) XOR CV(i-1), using the message block as the key and the chaining value as the data. The trailing exclusive-or is essential: without it the function would be invertible given the block, because a block cipher is invertible. Note the unusual arrangement: the message is the key, which is the reverse of everything else in this book, and it is what makes the function one-way.

A block-cipher-based hash inherits the cipher's block size as its digest size, so DES gives a 64-bit digest, which is 32 bits of collision resistance, which is nothing. That is why purpose-built functions won.

Worked example: a length-extension attack in outline

The observation. In the iterated construction, H(M) is the chaining value after the last block. So an attacker who holds H(M) holds the internal state.

Step 1. The attacker knows H(M) and the length of M, but not M itself.

Step 2. They set their own chaining value to H(M) and continue the computation with blocks of their own choosing.

Step 3. What they obtain is H(M || padding(M) || extra) for any extra they like, without knowing M.

Step 4: why this matters. If a system authenticates a message by sending H(secret || message), the attacker can append to the message and compute the correct tag. The authenticator is forgeable without the secret. The HMAC chapter performs this attack in full and shows what HMAC does instead.

Step 5: and what it does not break. The hash's collision and preimage resistance are untouched. Length extension is a property of the construction, not a weakness of the compression function, and SHA-3 does not have it because it is built differently.

Distinctions that carry marks

	XOR hash	Iterated (Merkle and Damgard)
Reordering blocks	same digest	different digest
A collision for a chosen target	computed directly	infeasible
Linear	yes	no
Used anywhere	no	MD5, SHA-1, SHA-2

Padding component	What it is for
A single 1 bit	marks the end of the message unambiguously
Zero bits	fills the block
The length in bits	stops a message and a padded version of it colliding (Merkle and Damgard strengthening)

How a Hash Function Is Built, and Breaking a Small One

	Purpose-built compression function	Davies and Meyer, from a block cipher
Used by	MD5, SHA-1, SHA-2, SHA-3	older and special-purpose designs
Digest size	chosen freely	the cipher's block size
The message block is	data	the key
Why the trailing XOR	not applicable	without it the function is invertible

What beginners get wrong here

Drawing the construction without the padding. The length field is load-bearing, and the run shows a collision without it.

Thinking the initial value could be anything. It is fixed by the standard; a sender-chosen one lets an attacker aim at any digest.

Believing the XOR hash is merely weak. It is not weak, it is trivially forgeable for any target, and the run does it in three lines.

Confusing length extension with a break of the hash. The hash's resistances are unaffected; the construction leaks its state, and that matters only for a scheme that authenticates with H(secret || message).

Forgetting the trailing exclusive-or in Davies and Meyer. Without it, a block cipher's invertibility makes the compression function invertible.

Quick revision

Iterated construction: CV0 = IV, CVi = f(CV(i-1), Mi), digest = CVL. The theorem: collision resistance of f gives collision resistance of H.
Padding, FIPS 180-4 section 5.1: a 1 bit, then zeros, then the length in bits. The length is Merkle and Damgard strengthening and it is not optional.
Proved in this chapter: without the length, PAY and PAY plus a zero byte both hash to 912a.
The XOR hash fails twice: any permutation of blocks collides, and a collision for any target is computed by appending four bytes.
A 16-bit digest collided in 53 tries against a birthday prediction of about 320, which shows the toy compression function is worse than random.
Compression functions are purpose-built, or made from a block cipher by Davies and Meyer: CVi = E(Mi, CV(i-1)) XOR CV(i-1), with the message as the key and the trailing exclusive-or essential.
The iterated construction leaks its state: H(M) is the chaining value, so H(secret || message) is forgeable by length extension.

Test yourself

1. Describe the iterated hash construction and state the theorem behind it. The message is padded to a multiple of the block size and split into blocks. A fixed initial value is the first chaining value, and each block is combined with the current chaining value by a compression function to give the next; the final chaining value is the digest. The theorem is that if the compression function is collision resistant, then so is the resulting hash function.

2. Give FIPS 180-4's padding rule and say why each part is there. Append a single 1 bit, then as many 0 bits as are needed, then the length of the original message in bits in a fixed-size field. The 1 bit marks the end of the message unambiguously; the zeros fill the block; and the length field prevents a message and a longer message that pads to the same blocks from colliding.

How a Hash Function Is Built, and Breaking a Small One

3. Show that omitting the length from the padding causes a collision. Pad only with zeros to the block size. Then the message PAY and the message PAY followed by a zero byte both pad to the same block, so they are fed to the compression function identically and produce the same digest. The chapter's run confirms it: both give 912a.

4. Give two attacks on a hash that exclusive-ors the message blocks. Any permutation of the blocks gives the same digest, because exclusive-or is commutative, so second preimage resistance fails completely for multi-block messages. And a collision with any chosen target can be computed directly: write the desired text, exclusive-or its hash with the target, and append the result as a further block, so the forgery hashes to the target exactly.

5. What is the Davies and Meyer construction, and why is the trailing exclusive-or essential? It builds a compression function from a block cipher as CVi = E(Mi, CV(i-1)) XOR CV(i-1), using the message block as the key and the chaining value as the plaintext. The trailing exclusive-or is essential because a block cipher is invertible: without it, anybody knowing the message block could recover the previous chaining value from the new one, so the function would not be one-way.

6. What is length extension, and which schemes does it break? Because the digest of an iterated hash is its final chaining value, an attacker holding H(M) and the length of M can resume the computation and produce H(M || padding || extra) for any chosen extra, without knowing M. It breaks any scheme authenticating a message as H(secret || message), because the attacker can extend the message and compute the correct tag. It does not affect the hash's collision or preimage resistance.

7. A 16-bit hash collided after 53 tries when the birthday bound predicted about 320. What does that tell you? That the compression function is measurably worse than a random function. The birthday bound is the expected cost against an ideal hash whose outputs are uniformly distributed; finding a collision far sooner indicates the outputs are clustered, which is a defect in the function rather than good fortune.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.

Syllabus for Cyber and Information Security

Issue