//Boring Signing

>TL;DR

• Custom RSA signer multiplies three 1024-bit primes and leaks the modulus in Base85 every run.

• The buggy Base85 decoder pads the final chunk with actual bytes ('u' == 84) instead of zeroes, so we can overflow by one byte when the requested length is not a multiple of four.

• Choosing a signing message whose last encoded byte we control lets us flip the most significant byte of N, occasionally turning the product of three primes into a prime modulus.

• Once N is prime, the RSA private exponent collapses to $d \equiv e^{-1} \pmod{N-1}$, so we can sign the forbidden 64-byte target directly.

• A short pwntools script loops until it finds a prime mutation, replays the safe input to keep the corrupted modulus, computes the forged signature, and leaks both local and remote flags.

>Challenge Overview

The binary performs up to 21 operations:

1. Print the 3072-bit modulus N encoded in Base85.

2. Offer Sign(0) or Verify(1).

3. For signing, read 64 bytes from Base85, hash with SHA-256, and return a CRT-based RSA signature unless the message matches the secret target string.

4. For verification, accept a 384-byte signature in Base85, hash the fixed target, and check the RSA verify equation. If it matches, print the flag.

The entire attack surface sits in input_b85 inside base85.c.

>Vulnerability: Padding Bug → One-Byte Overflow

input_b85 expects to decode fixed-length binary buffers but never accounts for the case where the caller’s size is not divisible by four. When n % 4 ≠ 0, the function still reads five Base85 characters and converts them to four output bytes before returning. That means the caller’s buffer is partially overwritten past its intended boundary.

For the signing route, input_b85(v.msg, 64) behaves correctly because 64 % 4 == 0. The interesting call is at the top of chall.c:

keygen(v.N, v.prime, 1024 * 3);

printf("N = "); print_b85(v.N, sizeof(v.N));

v.N is 384 bytes, which is divisible by four, so no bug there. However, when we later request another signing operation, input_b85 reuses the static struct:

struct variable {

    uint8_t msg[64];

    uint8_t N[384];

    ...

} v;

Because the overflowed write lands immediately after msg, the extra byte actually flips v.N[0], i.e., the most significant byte of the modulus stored in RAM. Each time we control the final Base85 chunk we mutate that top byte, effectively selecting a different modulus for the next operations inside the same run.

>Exploit Strategy

1. Decode leaks: The program prints N in Base85 at startup. Decode it to raw bytes so we know the honest triple-prime modulus.

2. Search for prime mutation: Brute force all 256 options for the top byte. For each candidate, treat candidate || N[1:] as the new modulus and test primality with Miller–Rabin. When it becomes prime and gcd(e, N-1)=1, the private exponent is simply d = e^{-1} mod (N-1).

3. Trigger overflow: Send a harmless message consisting of 64 zero bytes (encoded into 80 Base85 chars). Overwrite the final encoded byte with the winning candidate and feed it into a Sign(0) menu choice. The CRT signing routine now works modulo our crafted prime N'.

4. Forge target signature: Hash the forbidden 64-byte target locally with SHA-256, compute sig = hash^d mod N', encode it with Base85, and submit through Verify(1).

5. Automate retries: Because a prime mutation occurs roughly once per 256 runs, loop until success both locally and remotely.

>Local Exploit Walkthrough

• Recompile/inspect the binary with ./chall_debug to confirm the overflow by hand.

• Confirm the struct layout via gdb: msg sits directly in front of N, so a single extra byte from the decoder changes N[0].

• Write helper routines for Base85 encode/decode so we can reinterpret the leaked modulus and craft arbitrary payloads.

• Implement primality and GCD checks to pre-compute a workable top byte without touching the live process.

• Craft a stable base_payload = b85_encode(\x00 * 64) and patch the very last character per candidate search.

• Once a prime is found, send Sign(0) to lock the byte into memory, then immediately forge the target signature and call Verify(1).

Running python3 solve.py locally prints the fake flag bundled with the challenge binary (W1{fake_flag}), proving the exploit chain.

>Remote Solve

The same script works against the remote host with --remote challenge.cnsc.com.vn 31638. The only tweak was to make prompt parsing tolerant of \r\n variations by waiting for the substring "base85" instead of the exact "base85:\n". Average success took ~5–10 attempts. The remote instance returned the real flag:

>Solver Script

Path: attachment/src/solve.py

#!/usr/bin/env python3

from pwn import process, remote

import argparse

import hashlib

import math

import secrets

  

ALPHABET = b"!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstu"

INV = [0] * 256

for idx, ch in enumerate(ALPHABET):

    INV[ch] = idx

  

TARGET = b"1_d4r3_y0u_70_519n_7h15_3x4c7_51x7y_f0ur_by73_57r1n9_w17h_my_k3y"

E = 0x10001

  
  

def b85_decode(text: bytes) -> bytes:

    assert len(text) % 5 == 0

    out = bytearray()

    for i in range(0, len(text), 5):

        chunk = 0

        for c in text[i : i + 5]:

            chunk = chunk * 85 + INV[c]

        out.extend(chunk.to_bytes(4, "big"))

    return bytes(out)

  
  

def b85_encode(raw: bytes) -> bytes:

    assert len(raw) % 4 == 0

    out = bytearray()

    for i in range(0, len(raw), 4):

        chunk = int.from_bytes(raw[i : i + 4], "big")

        digits = []

        for _ in range(5):

            digits.append(chunk % 85)

            chunk //= 85

        for digit in reversed(digits):

            out.append(ALPHABET[digit])

    return bytes(out)

  
  

def miller_rabin(n: int, rounds: int = 16) -> bool:

    if n < 2:

        return False

    if n % 2 == 0:

        return n == 2

  

    small_primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for p in small_primes:

        if n % p == 0:

            return False

  

    d = n - 1

    s = 0

    while d % 2 == 0:

        d //= 2

        s += 1

  

    for _ in range(rounds):

        a = secrets.randbelow(n - 3) + 2

        x = pow(a, d, n)

        if x in (1, n - 1):

            continue

        for __ in range(s - 1):

            x = pow(x, 2, n)

            if x == n - 1:

                break

        else:

            return False

    return True

  
  

def find_prime_candidate(n_bytes: bytes):

    for cand in range(256):

        mutated = bytes([cand]) + n_bytes[1:]

        n_int = int.from_bytes(mutated, "big")

        if n_int % 2 == 0:

            continue

        if math.gcd(E, n_int - 1) != 1:

            continue

        if miller_rabin(n_int):

            return cand, mutated, n_int

    return None

  
  

def set_modulus_byte(p, base_payload: bytes, candidate: int):

    payload = bytearray(base_payload)

    payload[-1] = candidate

    p.sendline(b"0")

    p.recvuntil(b"base85")

    p.recvline()

    p.send(bytes(payload) + b"\n")

    p.recvline()  # "sig = ..."

    p.recvuntil(b"Sign(0) or Verify(1): ")

  
  

def forge_signature(p, mutated_n: int, target_hash: bytes):

    phi = mutated_n - 1

    d = pow(E, -1, phi)

    msg_int = int.from_bytes(target_hash, "big")

    sig_int = pow(msg_int, d, mutated_n)

    sig_bytes = sig_int.to_bytes(384, "big")

    sig_b85 = b85_encode(sig_bytes)

  

    p.sendline(b"1")

    p.recvuntil(b"base85")

    p.recvline()

    p.send(sig_b85 + b"\n")

    line = p.recvline().decode().strip()

    print(line)

    return line

  
  

def main():

    parser = argparse.ArgumentParser(description="Exploit for Boring Signing challenge")

    parser.add_argument("--remote", nargs=2, metavar=("HOST", "PORT"), help="run against remote instance")

    parser.add_argument("--binary", default="./chall_debug", help="local binary path")

    args = parser.parse_args()

  

    base_payload = b85_encode(b"\x00" * 64)

    assert len(base_payload) == 80

    target_hash = hashlib.sha256(TARGET).digest()

  

    attempt = 1

    while True:

        print(f"[+] Attempt {attempt}")

        attempt += 1

        if args.remote:

            host, port = args.remote

            p = remote(host, int(port))

        else:

            p = process(args.binary)

        line = p.recvline().strip().decode()

        if not line.startswith("N = "):

            raise RuntimeError("Unexpected banner")

        n_text = line[4:].encode()

        n_bytes = b85_decode(n_text)

  

        cand_info = find_prime_candidate(n_bytes)

        if not cand_info:

            print("[-] No prime candidate, restarting")

            p.close()

            continue

  

        candidate, mutated_bytes, mutated_int = cand_info

        print(f"[+] Found prime candidate byte 0x{candidate:02x}")

  

        p.recvuntil(b"Sign(0) or Verify(1): ")

        set_modulus_byte(p, base_payload, candidate)

  

        result = forge_signature(p, mutated_int, target_hash)

        p.close()

        if result and result != "Wrong !":

            print("[+] Success")

            break

  
  

if __name__ == "__main__":

    main()

>Takeaways

1. Padding matters: Even a one-byte overflow in a helper routine can completely compromise cryptographic protocols.

2. Assume shared structs: When reusable buffers sit back-to-back, decoder bugs can silently corrupt critical values.

3. CRT shortcuts: If you can coerce RSA CRT code to work modulo a prime, the private key is trivial to recompute from the public modulus alone.

4. Automate retries: Non-deterministic bugs (like hitting a prime by chance) are best solved with small helper scripts that loop until success.