SHC 2026: ZIPPER - Forging a Linear Hash via Matrix Inversion and gzip FEXTRA

Challenge Overview

Flag: dach2026{F3X7R4_15_pr377y_u53ful_4ec657bc16544419}

Guess a hash correctly 25 times in a row. For each round, server provides:

• A random ASCII target_message
• A random target_hash

We must respond with a base64-encoded file satisfying both:

1. gzip.decompress(file) == target_message
2. hash(file) == target_hash

The Hash Function

p = 0x1337   # 4919
Fp = GF(p)
I = matrix.random(Fp, 4)   # secret 4×4 matrix, fixed per process

def hash(message: bytes):
    m = pad(message, 25)
    # Split into 25-byte blocks, convert each to 4×4 matrix over GF(p)
    A = I
    for S in sections:
        A *= S
    # Serialize A back to 25 bytes

Hash = iterated matrix multiplication. Completely linear.

Vulnerabilities

1. The hash is not collision-resistant. Pure matrix multiplication over a finite field is invertible. Given any file and target hash, we can solve for a “bridging” matrix block.

2. The secret matrix I is recoverable. Send a probe input, read the hash from the error response, back-calculate I algebraically.

3. gzip trailing bytes (the misc component). Python 3.12’s gzip.decompress raises BadGzipFile on any non-null trailing bytes. We cannot simply append our matrix block after the compressed data.

Fix: Embed the matrix block inside the gzip FEXTRA field — opaque metadata that decompressors silently ignore.

Attack

File Structure

Block 0:  gzip header (10B) + extra_len (2B) + extra prefix (13B)
Block 1:  [OUR MATRIX BLOCK X — 25 bytes, inside extra field]
Block 2:  extra suffix (0xFF bytes) + start of compressed data
Block 3+: compressed data + CRC32 + size
Pad blk:  0x19 × 25 (auto-added by pad())

The prefix is exactly 13 bytes so Block 1 starts at a clean 25-byte boundary.

Solving for the Matrix Block

hash = I · S₀ · X · S₂ · ... · Sₙ · S_pad
     = L · X · R

X = L⁻¹ · A_target · R⁻¹

Encode X back into 25 bytes and embed at Block 1.

Recovering I

Send a known probe — parse hash from “Wrong hash: xxxx” error — compute:

I = A_response · (B · S_pad)⁻¹

Key Code

def forge_file(target_message, target_hash_hex, I):
    A_T = hashsum_to_matrix(bytes.fromhex(target_hash_hex))
    L, R = compute_LR(target_message, I)
    X = L.inverse() * A_T * R.inverse()
    gz = build_gzip_file(target_message, matrix_to_bytes(X))
    return base64.b64encode(gz).decode()

def recover_I(probe_hash_hex, probe_block):
    B     = bytes_to_matrix(probe_block)
    S_pad = bytes_to_matrix(bytes([25] * 25))
    A_resp = hashsum_to_matrix(bytes.fromhex(probe_hash_hex))
    return A_resp * (B * S_pad).inverse()

After recovering I, went 25/25. Flag retrieved.

Key Takeaways

The flag itself is the hint: F3X7R4 = FEXTRA.