Fixed-Point Hash — Davies-Meyer no-op blocks that let you insert or expand a message for free

A fixed point of a compression function is a (state, block) pair with f(h, b) = h: hashing that block leaves the chaining value unchanged, so the block can be inserted anywhere (or repeated any number of times) without touching the final digest.

The signal that gives it away

- The hash is built on Merkle–Damgård Construction — the digest IS the internal state with a Davies-Meyer compression function, H_i = E_{m_i}(H_{i-1}) ⊕ H_{i-1} — this is the shape MD5, SHA-1 and SHA-2 all use internally, and it's the specific structure fixed points exploit (Wikipedia's "One-way compression function" article documents this construction and the fixed-point property explicitly). - The challenge wants many preimages, or messages of different lengths that hash to the same digest, or hints at "repeated blocks", "expandable messages", "padding to a required length while keeping the tag valid". - It shows up combined with a length constraint: you can already forge a digest via Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone or a collision via Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions, but the verifier also checks the message's *length* (or you need the forged message to line up on a block boundary) — a fixed point is the tool that pads length without disturbing the hash. - You have (or can derive) the compression function's "decryption" direction — i.e. you can invert E_b for a chosen block b. This is realistic for MD5/SHA-family compression functions because their internal round transform is built from additions, rotations and XORs that are all invertible once the message block (the "key") is fixed — the compression function is only one-way with respect to the *state*, not to an attacker who controls the block and wants to invert the cipher step for that fixed block.

How it's exploited

1. Pick any block b. Compute h = E_b^{-1}(0). Then f(h, b) = E_b(h) ⊕ h = 0 ⊕ h = h — you've found a chaining value that b leaves unchanged. This is "free" in the sense that it costs one block-cipher inversion, not a birthday search. 2. Once a message reaches internal state h (at some block boundary), you can splice in k extra copies of b — or omit them — and every one of those choices reaches the same intermediate state h before continuing. That's what makes the message expandable: a family of messages of different lengths (differing by multiples of one block) that all collide on the chaining value right after the fixed-point segment. 3. Chain this with Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone when you need to hit *both* a target digest *and* a target total length: use length-extension to get the digest you want, then use fixed-point padding to stretch or shrink the message to the exact byte length the verifier expects, without changing the digest you just forged. 4. Chain this with Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions ideas when you need a large expandable range (Kelsey and Schneier's actual long-message second-preimage construction builds expandable messages from a *sequence* of multicollisions of geometrically increasing block-count, not a single fixed point — reach for the fixed-point trick first since it's cheaper, and only build the full Kelsey-Schneier ladder if you need to expand across a wide range of lengths). 5. In CTF practice you almost never need to reconstruct the block cipher's math by hand: recognizing "these particular blocks are a no-op at this state" is enough to know you can pad a forged message to whatever length the challenge demands while preserving a tag or digest you already control.

``python # schematic — the actual inversion is compression-function-specific def find_fixed_point(b): h = invert_Eb(b, 0) # h such that E_b(h) == 0 assert compress(h, b) == h return h ``

What does NOT work

- Treating a fixed point as a break of the hash itself. It doesn't give you a collision or a preimage on its own — it only gives you a no-op splice point. It becomes dangerous only combined with another primitive (length-extension for the digest, multicollisions for reach) — never mistake "I found a fixed point" for "I forged an arbitrary message." - Assuming you can target an arbitrary intermediate state. The direction is fixed-block-first: you pick b, then derive the one h it fixes — you cannot ask "give me a block that fixes *this specific* h I already need." If your forged message must pass through a particular state (e.g. one dictated by a secret prefix you don't fully control), a single fixed point won't get you there; you need the full expandable-message machinery instead. - Trying this on a sponge-based hash (SHA-3/Keccak). There is no Davies-Meyer feedforward and no small digest-sized state that "is" the output — see Sponge Construction — why length-extension does NOT work on SHA-3/Keccak. Fixed points and length-extension both fail there for the same structural reason. - Expecting this to be a practical standalone attack on real MD5/SHA-2. Public analysis (see the Wikipedia writeup) is explicit that fixed points against Davies-Meyer are a theoretical property, not a demonstrated practical break of collision resistance — no one has turned "I can find a fixed point" into a full collision on the real hash. Its practical payoff in CTFs is narrower and structural: padding/length games and the Kelsey-Schneier long-message second-preimage construction, not generic forgery. - Skipping straight to full Kelsey-Schneier machinery when a single fixed point would do. Their expandable-message construction (multiple stages of multicollisions of increasing size) is built for expanding across a *wide, unknown* range of lengths; if you only need to hit one specific target length, a single fixed-point splice is far cheaper to compute and reason about.

Related

Merkle–Damgård Construction — the digest IS the internal state Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone Sponge Construction — why length-extension does NOT work on SHA-3/Keccak Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling