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
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 verifiersha256_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
Price history
Comments (0)
No comments yet.