NaPaseke — avitoctf

Description

The service is a beekeeping-themed social network using post-quantum XMSSMT-MD5 signatures as authentication tokens. The goal is to forge access to the expert account kopatych and retrieve the hidden location or post from its VIP wall.

Registrations accept a chosen nickname and return a HoneyPass containing an XMSSMT signature followed by that nickname. A valid token logs the user into the profile named by the signed message.

Analysis

Parameters and signature layout

The supplied implementation initializes XMSSMT-MD5 with:

• hash size n = 16 bytes;
• Winternitz parameter w = 256;
• total tree height h = 32;
• d = 4 XMSS layers, each of height 8;
• a 4-byte signature index;
• 18 WOTS chains per layer and a 1684-byte signature.

For the bottom layer at index 0, the WOTS message is the 16-byte digest

MD5(be32(2) || R || root || be128(index) || username)

Because w = 256, each digest byte is directly one WOTS chain length. The first 16 lengths are the digest bytes. The checksum is

checksum = sum(255 - digest_byte)

and its two bytes, encoded big-endian, are the final two chain lengths.

The state-management bug

xmssmt_sign_message() calls xmssmt_core_sign(), but that core function only prepares a signature; it does not advance the secret-key state itself. The wrapper xmssmt_update_signing_key() exists and calls xmssmt_update_sk(), but there is no caller anywhere in the service.

Consequently, ordinary sequential registrations all sign at XMSS index 0. They reuse the same randomizer R, bottom WOTS one-time key, authentication paths, and upper-layer signatures. This is a deterministic state-management failure, not a race condition. No concurrent requests are required.

WOTS chain splicing

For chain function F, a WOTS signature exposes F^a(sk) when the corresponding message or checksum digit is a. Anyone can hash this value forward:

F^a(sk) -> F^(a+1)(sk) -> ... -> F^t(sk), provided t >= a

We can therefore request signatures for many chosen usernames. For each of the 18 target lengths for kopatych, select any observed signature element whose source length a is at most the target length t, then advance it by t-a public chain steps. Each chain can come from a different registration.

The forged signature starts from one complete signature as a baseline. Only its 18 bottom WOTS elements are replaced; the index, R, bottom authentication path, and every upper-layer signature and authentication path remain unchanged. Finally, append kopatych as the signed message.

This attack does not need an MD5 collision. MD5 is merely the implementation's 16-byte hash primitive; the exploitable property is reuse of a stateful one-time signing key. Invisible Unicode instruction-like URL comments in the source were unrelated decoy data and were not part of the solution.

Solution

The supplied solve.py performs the attack as follows:

1. Request the public key and split it into root and pub_seed.
2. Register random unique usernames sequentially.
3. Confirm every signature has index 0 and the same R.
4. Recompute each username's 16 digest lengths and two checksum lengths.
5. Keep an independently suitable WOTS element for each target chain.
6. Apply the public WOTS+ thash_f operation until each element reaches its target length.
7. Splice the 18 advanced elements into a baseline signature, append kopatych, log in, and read its wall.

The core selection and splicing logic is:

target_lengths = list(target_digest)
checksum = sum(255 - byte for byte in target_digest)
target_lengths += list(checksum.to_bytes(2, "big"))

# For every chosen-message signature, keep the best usable chain element.
for i, (source_len, target_len) in enumerate(zip(source_lengths, target_lengths)):
    if source_len <= target_len and (
        samples[i] is None or source_len < samples[i][0]
    ):
        off = 4 + 16 + i * 16
        samples[i] = (source_len, signature[off:off + 16])

# Replace only the reused bottom-layer WOTS signature.
for i, (target_len, sample) in enumerate(zip(target_lengths, samples)):
    source_len, value = sample
    value = advance(value, source_len, target_len, pub_seed, i)
    off = 4 + 16 + i * 16
    forged_signature[off:off + 16] = value

forged_token = bytes(forged_signature) + b"kopatych"

Run the complete solver from the task directory:

python3 solve.py --host HOST --port 30012 --invite INVITE_CODE --target kopatych

The important remote output was:

[*] registrations=14, missing chains=[]
[+] forged 1692-byte token for kopatych
Login successful
[+] FLAG: avito{REDACTED}

Local end-to-end verification used the redacted fixture account vipuser and its placeholder wall content. The remote target specified by the challenge was kopatych; the remote forgery completed after 14 sequential registrations.