m0unt41n - m

Overview

This challenge provides a small Python service.

The service asks for an integer m and then returns:

(m ^ randval) % FLAG

The flag is 44 digits long and is used directly inside the calculation.

To run the challenge locally, I first created a Python virtual environment and installed the required dependency:

sudo apt install python3-venv python3-pip
python3 -m venv venv
source venv/bin/activate
pip install pycryptodome
python3 chal.py

After starting the challenge, the program prints:

You provide an integer 'm', and we return the result of (m ^ randval) % FLAG.
The FLAG is 44-digits long. Good luck!
Type 'exit' to quit anytime.

Some manual tests looked like this:

Enter an integer m: 1
Result: (m ^ randval) % FLAG = 1

Enter an integer m: 2
Result: (m ^ randval) % FLAG = 1248998864894437397402509868276212092985339

Enter an integer m: 3
Result: (m ^ randval) % FLAG = 1239849368078290557990493755785720078720794

Enter an integer m: 4
Result: (m ^ randval) % FLAG = 8714198503583603080625689869919297549352586

Enter an integer m: -1
Result: (m ^ randval) % FLAG = 1

Enter an integer m: -2
Result: (m ^ randval) % FLAG = 1248998864894437397402509868276212092985339

Enter an integer m: 0
Result: (m ^ randval) % FLAG = 0

At first, this looks like an XOR challenge because of the ^ symbol in the output.

However, the source code shows that the service is not using XOR.

---

Step 1: Inspecting the Source Code

The relevant part of the challenge source is:

from os import environ
from secrets import randbelow

from Crypto.Util.number import bytes_to_long

FLAG = bytes_to_long(environ.get("FLAG", "stairctf{redacted}").encode())


def main():
    randval = randbelow(FLAG)
    print(
        "You provide an integer 'm', and we return the result of (m ^ randval) % FLAG."
    )
    print(f"The FLAG is {len(str(FLAG))}-digits long. Good luck!")
    print("Type 'exit' to quit anytime.\n")

    while True:
        try:
            user_input = input("Enter an integer m: ")
            if user_input.lower() == "exit":
                print("Goodbye!")
                break

            m = int(user_input)

            result = pow(m, randval, FLAG)
            print(f"Result: (m ^ randval) % FLAG = {result}\n")
        except ValueError:
            print(
                "Invalid input. Please enter a valid integer or type 'exit' to quit.\n"
            )


if __name__ == "__main__":
    main()

The important line is:

result = pow(m, randval, FLAG)

In Python, pow(m, randval, FLAG) calculates:

m^randval mod FLAG

So the printed expression is misleading.

The actual oracle is:

O(m) = m^randval mod FLAG

Where:

randval = random value generated once when the process starts
FLAG    = hidden modulus

The goal is to recover the hidden FLAG.

---

Step 2: Understanding the Weakness

The issue is that the flag is used as the modulus.

The service lets us query many values of:

m^randval mod FLAG

Because the same randval is reused during one connection, the oracle has a useful multiplicative property.

For two chosen values a and b:

O(a) = a^randval mod FLAG
O(b) = b^randval mod FLAG

Multiplying both oracle outputs gives:

O(a) * O(b) ≡ a^randval * b^randval mod FLAG

This can be rewritten as:

O(a) * O(b) ≡ (a*b)^randval mod FLAG

But (a*b)^randval mod FLAG is exactly the oracle output for a*b:

O(a*b) = (a*b)^randval mod FLAG

Therefore:

O(a) * O(b) ≡ O(a*b) mod FLAG

So the difference must be divisible by FLAG:

O(a) * O(b) - O(a*b) = k * FLAG

This means every pair gives us a multiple of the hidden flag integer.

With enough pairs, we can recover the common factor by calculating the greatest common divisor:

FLAG = gcd(
    O(a1) * O(b1) - O(a1*b1),
    O(a2) * O(b2) - O(a2*b2),
    O(a3) * O(b3) - O(a3*b3),
    ...
)

This is the core of the attack.

---

Step 3: Testing the Relation Locally

From the local test output, we know for example:

O(2) = 1248998864894437397402509868276212092985339
O(4) = 8714198503583603080625689869919297549352586

Using the pair (2, 2) gives:

O(2) * O(2) - O(4)

This value must be divisible by the hidden FLAG.

One pair is usually not enough, because the result can still contain an additional unknown multiplier. Therefore, I collected several such values and calculated the gcd.

Useful pairs are:

(2, 3)
(2, 5)
(3, 5)
(2, 7)
(5, 7)
(2, 11)
(3, 11)
(7, 11)

Each pair gives one multiple of the hidden modulus.

After enough pairs, the gcd collapses to the actual flag integer.

---

Step 4: Connecting to the Remote Service

The remote service is reached with:

ncat --ssl d72274ab-712c-4c70-a4aa-5fe732ba2ac4.library.m0unt41n.ch 31337

The --ssl part is important as I hade some issues with my script at first.

A normal Python socket does not work because the service expects a TLS connection.

This would fail:

socket.create_connection((HOST, PORT))

The socket has to be wrapped with SSL:

context = ssl._create_unverified_context()
s = context.wrap_socket(raw, server_hostname=HOST)

This behaves like ncat --ssl.

---

Step 5: Exploit Script

The final exploit connects to the remote service over SSL, queries several values, calculates the modular differences, and then takes the gcd.

#!/usr/bin/env python3
import socket
import ssl
import re
from math import gcd

HOST = "d72274ab-712c-4c70-a4aa-5fe732ba2ac4.library.m0unt41n.ch"
PORT = 31337

def long_to_bytes(n):
    return n.to_bytes((n.bit_length() + 7) // 8, "big")

def recv_until(sock, marker):
    data = b""

    while marker not in data:
        chunk = sock.recv(4096)

        if not chunk:
            raise EOFError(data.decode(errors="replace"))

        data += chunk

    return data

def query(sock, m):
    sock.sendall(str(m).encode() + b"\n")

    data = recv_until(sock, b"Enter an integer m:")

    match = re.search(rb"Result:.*?=\s*(\d+)", data)

    if not match:
        print(data.decode(errors="replace"))
        raise ValueError("Could not parse result")

    return int(match.group(1))

def connect_ssl():
    raw = socket.create_connection((HOST, PORT), timeout=10)

    # Similar to ncat --ssl.
    # Certificate verification is disabled because this is a CTF service.
    context = ssl._create_unverified_context()

    return context.wrap_socket(raw, server_hostname=HOST)

with connect_ssl() as s:
    banner = recv_until(s, b"Enter an integer m:")
    print(banner.decode(errors="replace"))

    m = re.search(rb"FLAG is (\d+)-digits", banner)
    target_digits = int(m.group(1)) if m else 44

    cache = {}

    def O(x):
        if x not in cache:
            cache[x] = query(s, x)
            print(f"O({x}) = {cache[x]}")
        return cache[x]

    pairs = [
        (2, 3),
        (2, 5),
        (3, 5),
        (2, 7),
        (5, 7),
        (2, 11),
        (3, 11),
        (7, 11),
        (2, 13),
        (5, 13),
        (11, 13),
        (2, 17),
        (3, 17),
        (5, 17),
        (13, 17),
        (2, 19),
        (3, 19),
    ]

    g = 0

    for a, b in pairs:
        diff = abs(O(a) * O(b) - O(a * b))

        if diff != 0:
            g = gcd(g, diff)

        print(f"[+] pair ({a}, {b}) -> gcd = {g}")
        print(f"[+] gcd digits = {len(str(g))}")

        if len(str(g)) == target_digits:
            candidate = long_to_bytes(g)

            print("[+] Candidate integer:")
            print(g)

            print("[+] Candidate bytes:")
            print(candidate)

            try:
                print("[+] Candidate decoded:")
                print(candidate.decode())
            except UnicodeDecodeError:
                pass

            break

---

Step 6: Running the Exploit

Running the script against the remote service:

python3 exploit.py

The script prints the queried oracle values and updates the gcd after every pair.

The recovered integer can be converted back to bytes because the challenge originally converted the flag with:

FLAG = bytes_to_long(environ.get("FLAG", "stairctf{redacted}").encode())

So reversing it with long_to_bytes() gives the flag string.

---

Why This Works

The service leaks arithmetic relations modulo the secret value.

The secret flag is used as the modulus, and the user can freely query modular exponentiation results.

Because the exponent randval stays the same for the whole connection, the following relation always holds:

O(a) * O(b) ≡ O(a*b) mod FLAG

Therefore:

FLAG | (O(a) * O(b) - O(a*b))

Every chosen pair leaks a multiple of the flag. Taking the gcd of several leaked multiples removes the random multipliers and leaves the hidden modulus.

This is a classic hidden-modulus recovery issue.

---

Vulnerability Summary

The vulnerability is caused by using the secret flag as a modulus in an exposed arithmetic oracle.

The challenge tries to hide the flag behind modular exponentiation:

result = pow(m, randval, FLAG)

However, because the attacker can choose m and the same exponent is reused, the oracle leaks enough modular structure to recover FLAG.

The misleading output string:

(m ^ randval) % FLAG

also makes the challenge look like XOR at first, but the actual implementation is modular exponentiation.

A secure implementation should never use a secret value directly as a modulus in an attacker-controlled oracle. If modular arithmetic is required, the modulus should be public and the secret should not be recoverable through algebraic relations. Reusing the same hidden exponent also makes the oracle much easier to exploit.