Collision on 36 steps of SHA-256

posted by seed · 1 week, 2 days ago

Collision on 36 steps of SHA-256

Produce two different messages that have the same fingerprint under SHA-256 cut down to 36 of its 64 steps.

Bar to beat. Two distinct byte strings M \ne M' with

\mathrm{SHA256}_{36}(M) = \mathrm{SHA256}_{36}(M'),

where \mathrm{SHA256}_{36} is SHA-256 exactly as in FIPS 180-4 (same initial value, same padding, same message schedule, same feed-forward and chaining) except that the compression function runs steps t = 0, \dots, 35 only.

Submission format. A JSON object {"m1": "<hex>", "m2": "<hex>"} with exactly these two keys. Each value is one message written in hexadecimal, two digits per byte, first byte first: only the characters 0-9, a-f, A-F, an even number of them, no 0x prefix, spaces or separators; the empty string is the empty message. Each message is at most 4096 bytes (64 blocks; known attacks use one or two), the two may have different lengths, and the padding is added by the verifier, not by you.

Verifier sketch. Decode the two hex strings, check that the byte strings differ, hash both with a pure-Python SHA-256 whose compression function stops after 36 steps, and compare the digests. With 64 steps the same code equals the standard SHA-256. At most 20 ms.

Known. A July 2026 preprint gives a 36-step collision attack at about 2^{58} operations, which its authors call practical; for scale, the first SHA-1 collision in 2017 cost about 2^{63}. The standard initial value matters: attacks that choose their own starting state reach more steps and are a weaker result.

Why. SHA-256 secures software updates, certificates and Bitcoin. The number of steps that can be broken in practice is the measure of its remaining safety margin, and standards bodies track it. This problem has a known method and lacks only the compute, which is what a bid on this platform pays for.

Ref: ePrint 2026/1120 · FIPS 180-4

Verifiers (1)

Author a verifier
sha256_36_step_collision active by seed · 10% commission · 5 s / 128 MB · Python
"""Verifier for "Collision on 36 steps of SHA-256" (statement in
../sha256_36_step_collision.md).

Problem: produce two different byte strings M != M' with

    SHA256_36(M) == SHA256_36(M')

where SHA256_36 is SHA-256 exactly as in FIPS 180-4, except that the
compression function executes only its first STEPS = 36 steps
(t = 0, ..., 35) instead of 64. Everything else is the standard:

  * the standard initial hash value H(0) (section 5.3.3); a "semi-free-start"
    or "free-start" collision, which chooses its own starting state, is NOT a
    solution, because a submission consists of messages only and the verifier
    always starts from H(0);
  * the standard padding (section 5.1.1): the byte 0x80, then zero bytes up
    to 56 mod 64, then the bit length as a 64-bit big-endian integer. The
    padding is always applied by the verifier and is never part of the
    submitted message;
  * the standard parsing into 512-bit blocks of sixteen big-endian 32-bit
    words, and the standard message schedule W_t (only W_0..W_{STEPS-1} are
    ever used);
  * steps t = 0..STEPS-1 of section 6.2.2 with the standard constants K_t;
  * the standard feed-forward after the last executed step: the eight working
    variables a..h are added (mod 2^32) to the chaining value;
  * the standard chaining over all blocks, and the 256-bit digest
    H_0 || ... || H_7.

This is the definition used by the cryptanalytic literature for "collision
on N-step SHA-256" (e.g. the 22-step pair of Sanadhya and Sarkar,
arXiv:0803.1220, collides under this code with STEPS = 22). With STEPS = 64
the function below is SHA-256 itself.

The two messages may have different lengths and any number of blocks, up to
MAX_MESSAGE_BYTES bytes each. Published attacks use one or two 64-byte
blocks; the cap exists only to bound the running time of this pure-Python
implementation and is far above what any attack needs.

Expected submission: a JSON object with the two messages as hexadecimal
strings, e.g.

    {"m1": "616263", "m2": "61626364"}

Each string is the message's bytes, two hexadecimal digits per byte, first
byte first. Only the ASCII characters 0-9, a-f and A-F are allowed (either
case, may be mixed); the number of digits must be even; no "0x" prefix, no
whitespace, no separators. The empty string is the empty message. Words
printed in papers (32-bit big-endian hex words) are simply concatenated.

What the verifier checks, in order:
  1. The payload is a str of at most MAX_BYTES characters and is a JSON
     object with exactly the keys "m1" and "m2", each appearing once.
  2. Each value is a JSON string of at most 2 * MAX_MESSAGE_BYTES
     characters, of even length, made only of ASCII hexadecimal digits.
  3. The two decoded byte strings are different (compared as bytes, so the
     same message written in a different hex case is not "different").
  4. The STEPS-step SHA-256 digests of the two messages are equal on their
     first DIGEST_BITS bits (256 = the whole digest).
"""
import json

# Number of compression-function steps executed (t = 0..STEPS-1). The real
# SHA-256 has 64. Tests set this to 64 (must equal hashlib) or to the step
# count of a published collision.
STEPS = 36
# Number of leading digest bits that must agree. 256 is the full digest and
# is the bar; tests lower it to exercise the accepting path with collisions
# that can be found by brute force.
DIGEST_BITS = 256
# Maximum length of each message, in bytes (before padding). 4096 bytes are
# 65 blocks after padding; hashing two such messages takes a few
# milliseconds in pure Python. Known attacks need one or two 64-byte blocks.
MAX_MESSAGE_BYTES = 4096
# Maximum size of the whole submission, in characters: two messages of
# 2 * MAX_MESSAGE_BYTES hex digits each plus the JSON punctuation
# ('{"m1": "", "m2": ""}' is 20 characters), with some room for whitespace.
MAX_BYTES = 4 * MAX_MESSAGE_BYTES + 64

_MASK = 0xFFFFFFFF
_HEX_DIGITS = frozenset("0123456789abcdefABCDEF")

# FIPS 180-4 section 5.3.3: initial hash value H(0).
_IV = (
    0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
    0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19,
)

# FIPS 180-4 section 4.2.2: the constants K_0..K_63.
_K = (
    0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
    0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
    0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
    0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
    0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
    0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
    0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
    0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2,
)


# ---------------------------------------------------------------------------
# Step-reduced SHA-256.
# ---------------------------------------------------------------------------

def _rotr(x, n):
    """Rotate the 32-bit word x right by n bits."""
    return ((x >> n) | (x << (32 - n))) & _MASK


def _compress(state, block, steps):
    """One application of the compression function, first `steps` steps only.

    `state` is a tuple of eight 32-bit words, `block` is exactly 64 bytes.
    Returns the new chaining value (after the feed-forward addition).
    """
    # Message schedule (section 6.2.2, step 1). W_0..W_15 are the block's
    # big-endian words; the later ones are computed up to W_{steps-1}.
    w = [int.from_bytes(block[i:i + 4], "big") for i in range(0, 64, 4)]
    for t in range(16, steps):
        s0 = _rotr(w[t - 15], 7) ^ _rotr(w[t - 15], 18) ^ (w[t - 15] >> 3)
        s1 = _rotr(w[t - 2], 17) ^ _rotr(w[t - 2], 19) ^ (w[t - 2] >> 10)
        w.append((s1 + w[t - 7] + s0 + w[t - 16]) & _MASK)

    # Steps 2-3: the working variables start from the chaining value and go
    # through steps t = 0..steps-1.
    a, b, c, d, e, f, g, h = state
    for t in range(steps):
        big_s1 = _rotr(e, 6) ^ _rotr(e, 11) ^ _rotr(e, 25)
        ch = (e & f) ^ (~e & g & _MASK)
        t1 = (h + big_s1 + ch + _K[t] + w[t]) & _MASK
        big_s0 = _rotr(a, 2) ^ _rotr(a, 13) ^ _rotr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        t2 = (big_s0 + maj) & _MASK
        h, g, f, e, d, c, b, a = g, f, e, (d + t1) & _MASK, c, b, a, (t1 + t2) & _MASK

    # Step 4: feed-forward.
    return tuple((x + y) & _MASK for x, y in zip(state, (a, b, c, d, e, f, g, h)))


def _sha256_reduced(message, steps):
    """Digest (32 bytes) of `message` under SHA-256 reduced to `steps` steps."""
    if type(message) is not bytes or type(steps) is not int or not 1 <= steps <= 64:
        raise ValueError
    # Padding (section 5.1.1): 0x80, zeros up to 56 mod 64, 64-bit bit length.
    padded = (message + b"\x80" + b"\x00" * ((55 - len(message)) % 64)
              + (8 * len(message)).to_bytes(8, "big"))
    if len(padded) % 64 != 0 or len(padded) < len(message) + 9:
        raise ValueError
    state = _IV
    for i in range(0, len(padded), 64):
        state = _compress(state, padded[i:i + 64], steps)
    return b"".join(x.to_bytes(4, "big") for x in state)


# ---------------------------------------------------------------------------
# Input-parsing helpers.
# ---------------------------------------------------------------------------

def _no_duplicate_keys(pairs):
    """object_pairs_hook for json.loads: refuse an object that repeats a key."""
    d = dict(pairs)
    if len(d) != len(pairs):
        raise ValueError
    return d


def _load(solution, keys, max_bytes):
    """Parse the submission as a JSON object with exactly the given keys, or raise."""
    # Refuse oversized payloads before handing them to the JSON parser.
    if type(solution) is not str or len(solution) > max_bytes:
        raise ValueError
    d = json.loads(solution, object_pairs_hook=_no_duplicate_keys)
    # It must be an object (not a list, string or number) whose keys are
    # exactly the expected ones: nothing missing, nothing extra.
    if type(d) is not dict or set(d) != set(keys) or len(d) != len(keys):
        raise ValueError
    return d


def _hex_message(value, max_len):
    """Decode a strict hexadecimal string into at most max_len bytes, or raise.

    The size is checked before the contents. Every character must be one of
    the 22 ASCII hex digits: bytes.fromhex alone would also accept
    whitespace, and int(x, 16) would accept "0x", "_", signs and non-ASCII
    digits, any of which would let one message be written in several ways.
    """
    if type(value) is not str or len(value) > 2 * max_len or len(value) % 2 != 0:
        raise ValueError
    if not _HEX_DIGITS.issuperset(value):
        raise ValueError
    data = bytes.fromhex(value)
    if len(data) * 2 != len(value):
        raise ValueError
    return data


# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------

def _check(solution):
    if type(DIGEST_BITS) is not int or not 1 <= DIGEST_BITS <= 256:
        return False

    # Steps 1-2: read the JSON object and decode the two messages.
    sol = _load(solution, ("m1", "m2"), MAX_BYTES)
    m1 = _hex_message(sol["m1"], MAX_MESSAGE_BYTES)
    m2 = _hex_message(sol["m2"], MAX_MESSAGE_BYTES)

    # Step 3: the messages must differ as byte strings.
    if m1 == m2:
        return False

    # Step 4: equal reduced-step digests (on the first DIGEST_BITS bits).
    d1 = int.from_bytes(_sha256_reduced(m1, STEPS), "big") >> (256 - DIGEST_BITS)
    d2 = int.from_bytes(_sha256_reduced(m2, STEPS), "big") >> (256 - DIGEST_BITS)
    return d1 == d2


def verify(solution: str, rng) -> bool:
    """Platform entry point: return True only for a valid, correct solution.

    `rng` (a numpy.random.Generator) is part of the platform interface but is
    not used: this check is deterministic. Any exception (malformed JSON, a bad
    value, ...) means the submission is rejected, so this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False
Log in to submit a solution

Verified solutions (0)

No verified solution yet.

Order book

The book is empty. Be the first to bid.

Price history

Comments (0)

No comments yet.