NaPaseke

Platform: Avitoctf | Category: Cryptography | Type: Challenge | Difficulty: Easy | OS: NA | Author: D3v0o0Nu11 | Date: 2026-07-18 | Status: Solved Techniques: chosen_message_signature_forgery, wots_chain_splicing

Summary

Task: Forge an XMSSMT-MD5 authentication token for beekeeping expert kopatych and recover a hidden post. Solution: Reuse chosen-message WOTS chain elements from repeated index-0 signatures and splice a valid target signature.

Recon

Port scan

 bash read-only • copy allowed Copy
nmap -p- -sV -sC <TARGET> --min-rate 1000 -Pn

Enumeration highlights

• Event: avitoctf | ID: 20260718_avitoctf_napaseke
• Tags: md5, wots, pqc, xmssmt, one_time_signature_reuse
• Indicators: XMSS index remains 0 across sequential signatures, xmssmt_update_signing_key has no caller, same R and bottom WOTS key are reused
• Source: 20260718_avitoctf_napaseke.md

Foothold

Vulnerability / Misconfiguration

1. chosen_message_signature_forgery
2. wots_chain_splicing

 bash read-only • copy allowed Copy
<command>

Exploitation

• See original writeup content for detailed exploitation.

Privilege Escalation

Enumeration

 bash read-only • copy allowed Copy
sudo -l
find / -perm -4000 2>/dev/null
getcap -r / 2>/dev/null
cat /etc/crontab
ps aux

Exploitation

1. N/A for challenge-type writeup; see exploitation above.
2. Flag obtained via challenge solve.

 bash read-only • copy allowed Copy
<command>

Flags

Key Takeaways / Lessons

• chosen_message_signature_forgery
• wots_chain_splicing
• Tags: md5, wots, pqc, xmssmt, one_time_signature_reuse

Original Writeup

<details><summary>Click to expand original content</summary>

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

 text read-only • copy allowed Copy
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

 text read-only • copy allowed Copy
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:

 text read-only • copy allowed Copy
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:

 python read-only • copy allowed Copy
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:

 bash read-only • copy allowed Copy
python3 solve.py --host HOST --port 30012 --invite INVITE_CODE --target kopatych

The important remote output was:

 text read-only • copy allowed Copy
[*] 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.

</details>

---

signed by XESXOR