napaseke2 — avitoctf

Description

The supplied TCP service registers users and returns a hexadecimal HoneyPass token containing an XMSSMT-MD5 signature followed by the username. A valid token for the seeded VIP profile vipuser allows its full wall post to be viewed. The source package redacts that post's flag, so local testing can prove the cryptographic exploit but cannot recover the competition's real flag.

Analysis

Parameters and token layout

params.c configures XMSSMT with:

• MD5-sized nodes: n = 16;
• Winternitz parameter w = 256, hence one base-256 digit per byte;
• total tree height 32, split across d = 4 layers of height 8;
• WOTS length 18: 16 message-digest digits and two checksum digits;
• a four-byte global index and a 1,684-byte signature.

The signed token layout is:

index (4) || R (16) ||
bottom WOTS (18*16) || bottom auth path (8*16) ||
layer 1 WOTS || auth path || layer 2 WOTS || auth path || layer 3 WOTS || auth path ||
username

The public key is root || pub_seed, 16 bytes each. For index idx, randomness R, and message m, the bottom-layer WOTS signs:

H_msg = MD5(pad(2) || R || root || idx_as_16_bytes || m)

The 18 WOTS chain digits are the 16 bytes of H_msg, followed by the two-byte big-endian value sum(255 - digest_byte). The checksum matters: satisfying only the 16 digest inequalities is not enough.

Race condition and one-time-key reuse

Registration deliberately splits the stateful signature operation:

1. xmssmt_sign_message() reads the shared signing index and produces a signature.
2. The new user and token are written out.
3. Only then does xmssmt_update_signing_key() advance the shared index.

The // OOOPS! comment immediately before step 3 points directly at the bug. Forked clients share the XMSS secret-key state through MAP_SHARED, but there is no lock spanning signing and updating. Concurrent registrations can therefore read the same stale global index and sign distinct usernames with the same bottom-layer WOTS key and address. Because R = PRF(SK_PRF, idx), duplicate-index signatures also have the same R.

For WOTS chain i, let the digit of a source message be a_i. Its signature element is the secret chain start advanced to position a_i:

S_i = F_i^a_i(sk_i)

The WOTS+ step F_i is address-dependent, using the public seed, layer/tree/leaf address, chain number, and current hash position. Hashing is one-way, so a target element at digit t_i can be derived exactly when:

a_i <= t_i

In that case, apply the correctly addressed chain function another t_i-a_i times. Reusing one OTS key for several messages is especially damaging because each target chain can independently select the duplicate signature with the smallest usable source digit. Thus, with sources j, chain i is covered whenever some a_(j,i) <= t_i.

What must be changed

All signatures with the same global index use the same XMSS leaf and the same authentication paths. Their upper three XMSSMT layers sign the same lower-tree roots and are identical. A forged token can therefore copy one complete duplicate-index signature, preserve its index, R, every authentication path, and all upper-layer WOTS signatures, and replace only the first 288-byte WOTS block beginning at offset 20. Finally, append the target username vipuser in place of the original message.

Solution

1. Open many registration connections and synchronize submission of distinct usernames.
2. Parse complete returned tokens and group them by the four-byte signature index. Confirm that the chosen group also shares R.
3. Obtain root and pub_seed from the service's public-key command.
4. Recompute the 18 source digit vectors and the target vector for vipuser.
5. For each target chain, choose a source with a_i <= t_i, preferably the minimum such digit.
6. Advance that source element with the exact XMSS address-dependent WOTS+ chain function.
7. Copy one original signature, replace only its bottom WOTS block, and append vipuser.
8. Submit the forged token, then request vipuser's wall.

The working core of solve.py is reproduced below:

#!/usr/bin/env python3
import hashlib
import struct

N = 16
INDEX_BYTES = 4
WOTS_LEN = 18
WOTS_BYTES = WOTS_LEN * N
SIG_BYTES = INDEX_BYTES + N + 4 * WOTS_BYTES + 32 * N  # 1684

def md5(data):
    return hashlib.md5(data).digest()

def addr_bytes(addr):
    return b"".join(struct.pack(">I", word) for word in addr)

def prf(pub_seed, addr):
    return md5((3).to_bytes(4, "big") + pub_seed + addr_bytes(addr))

def chain_step(value, pub_seed, addr, position):
    addr = list(addr)
    addr[6] = position                 # hash address
    addr[7] = 0
    key = prf(pub_seed, addr)
    addr[7] = 1
    mask = prf(pub_seed, addr)
    masked = bytes(x ^ y for x, y in zip(value, mask))
    return md5((0).to_bytes(4, "big") + key + masked)

def digits(digest):
    checksum = sum(255 - byte for byte in digest)
    return list(digest) + list(checksum.to_bytes(2, "big"))

def message_digest(root, idx, R, message):
    prefix = (2).to_bytes(4, "big") + R + root + idx.to_bytes(16, "big")
    return md5(prefix + message)

def parse_token(token_hex):
    raw = bytes.fromhex(token_hex)
    if len(raw) <= SIG_BYTES:
        raise ValueError("token has no appended username")
    return raw, int.from_bytes(raw[:4], "big"), raw[4:20], raw[SIG_BYTES:]

def forge(public_key_hex, token_hexes, target=b"vipuser"):
    public_key = bytes.fromhex(public_key_hex)
    root, pub_seed = public_key[:16], public_key[16:]
    sources = [parse_token(token) for token in token_hexes]
    idx, R = sources[0][1], sources[0][2]
    if any((source[1], source[2]) != (idx, R) for source in sources):
        raise ValueError("tokens do not reuse one index and R")

    source_digits = [
        digits(message_digest(root, idx, source[2], source[3]))
        for source in sources
    ]
    target_digits = digits(message_digest(root, idx, R, target))

    # Preserve the signature structure and replace the appended message.
    output = bytearray(sources[0][0][:SIG_BYTES] + target)
    bottom_wots = INDEX_BYTES + N

    for chain, wanted in enumerate(target_digits):
        choices = [
            (values[chain], source_number)
            for source_number, values in enumerate(source_digits)
            if values[chain] <= wanted
        ]
        if not choices:
            raise ValueError(f"uncovered chain {chain}")

        start, source_number = min(choices)
        begin = bottom_wots + chain * N
        value = sources[source_number][0][begin:begin + N]

        # layer=0, tree=idx>>8, type=OTS, leaf=idx&0xff, chain=i
        addr = [0, 0, idx >> 8, 0, idx & 0xff, chain, 0, 0]
        for position in range(start, wanted):
            value = chain_step(value, pub_seed, addr, position)
        output[begin:begin + N] = value

    return output.hex()

Local verification

To test the cryptographic reasoning independently of network timing, the test-only patch made xmssmt_update_signing_key() retain its index when UNSAFE_TEST_REUSE was set. Twelve signatures for different sourceNN usernames were collected at one index. The solver forged a token whose message was vipuser; the original verifier accepted it, login succeeded, and requesting that wall returned:

Flag is here: avito{REDACTED}

This is only the source-redacted placeholder embedded in database.c, not the real competition flag. No real flag is claimed by this writeup.

Practical Race Limitations and Failed Attempts

The intended cryptographic weakness is clear, but exploiting the unmodified local service was fragile:

• Forty synchronized clients produced only two complete duplicate-index tokens in one run and one in another. SQLite writes serialize or fail quickly, reducing the number of responses.
• After the first sibling advances the shared index, every stale sibling reaches the conflict branch in xmssmt_update_signing_key(), which sends SIGKILL to the entire process group. This sharply limits how many duplicate signatures become observable before restart.
• Shrinking SO_RCVBUF to 256 and delaying reads for two seconds did not park children before the update. The roughly 3.4 KB hexadecimal token still fit in server-side socket buffering, yielding only one token in that experiment.
• One source signature cannot sign a distinct digest because the WOTS checksum prevents all 18 digits from simultaneously being forward-reachable. Monte Carlo testing estimated that two random duplicate sources cover vipuser with probability about 4.9e-5; three improve this only to about 0.0022. The local race did not reliably expose three.

These limitations explain why the test harness used 12 forced same-index signatures to verify the forge deterministically. They do not change the underlying one-time-key-reuse vulnerability.

Honeypot Branch: Supplementary Unicode

Variation-selector Unicode hidden in comments of commands.c and database.c decoded to a URL. Following it led through a sequence asking for challenge metadata, an exactly 100-word English essay, and an AI model family; candidate final submissions returned HTTP 429.

That branch was an AI prompt-injection honeypot, not a valid flag path. It neither verifies an XMSSMT token nor reveals the VIP wall, and it must not be confused with the intended cryptographic exploit.