Writeup by bylal for easy-bingo

crypto rsa hash-collision

December 21, 2025

Table of contents

Description

The bingo challenge is a cryptography task that requires providing a valid RSA signature for a message with a specific prefix: “Get Flag.”.

Upon connection, the server provides the public RSA parameters $N$ and $e$, along with three parameters ($hash_p$, $\alpha$, and $\beta$) for a custom hashing mechanism. The goal is to find a message $M$ and a signature $S$ such that $S^e \equiv H(M) \pmod N$.

Analysis

The Verification Bypass

The core of the challenge lies in the relationship between the custom hash $H(M)$ and the RSA signature verification equation: $$S^e \equiv H(M) \pmod N$$

In many custom hash implementations used in CTF challenges, there exists a mathematical “null point” where the hash output simplifies to a trivial value. Based on the parameters provided ($hash_p$, $\alpha$, and $\beta$), the hash function $H(M)$ is designed such that if the message $M$ is a multiple of $(hash_p - 1)^2$, the internal state of the hash collapses, resulting in: $$H(M) = 1$$

The Trivial Signature

When $H(M) = 1$, the RSA equation becomes: $$S^e \equiv 1 \pmod N$$

Since $1$ raised to any power $e$ is always $1$ (i.e., $1^e \equiv 1 \pmod N$), we do not need the private key to sign the message. We simply need to provide $S = 1$.

Thought Process

To solve this, we must satisfy the server’s prefix constraint while forcing the hash to 1.

1. Identifying the Target Multiple

We define $L = hash_p - 1$. Our target is to create a message $M$ such that $M$ is a multiple of $L^2$. $$M \equiv 0 \pmod{L^2}$$

2. Satisfying the Prefix Constraint

The server requires $M$ to start with the bytes Get Flag.. We can represent this prefix as a large integer $P$. To maintain this prefix while ensuring $M$ is a multiple of $L^2$, we:

  • Append a large amount of “padding” to $P$ (e.g., 300 bytes) to create a lower bound.
  • Calculate the smallest integer $k$ such that $k \cdot L^2$ is greater than or equal to this padded value.
  • Verify that the resulting $M = k \cdot L^2$ still starts with the desired prefix bytes.

Solution

  1. Retrieve Parameters: Connect to the service and parse $N$, $e$, $hash_p$, $\alpha$, and $\beta$.
  2. Calculate $M$:
    • Let $mod_target = (hash_p - 1)^2$.
    • Convert Get Flag. to integer $P$.
    • Find the smallest $k$ where $k \cdot mod_target \ge P \cdot 256^{300}$.
  3. Submit:
    • Send the hexadecimal representation of $M = k \cdot mod_target$.
    • Send the signature $S = 1$.

The server verifies the prefix, computes $H(M) = 1$, and confirms that $1^e \equiv 1 \pmod N$, ultimately granting the flag.

Conclusion

The challenge demonstrates that custom hash functions often introduce vulnerabilities if they are not cryptographically secure against pre-image attacks. By forcing the hash output to a fixed point of the RSA function (in this case, 1), the entire security of the signature scheme is bypassed.

Code Implementation

Here is a Python script that implements the solution:

from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes

def solve():
    # Connect to the challenge instance
    # Replace with actual host/port from the challenge (or docker)
    io = remote('35.194.98.181', 10961)

    # Parse parameters from the server
    io.recvuntil(b"N = ")
    N = int(io.recvline().strip())
    io.recvuntil(b"e = ")
    e = int(io.recvline().strip())
    io.recvuntil(b"hash_p = ")
    hash_p = int(io.recvline().strip())
    io.recvuntil(b"alpha = ")
    alpha = int(io.recvline().strip())
    io.recvuntil(b"beta = ")
    beta = int(io.recvline().strip())

    L = hash_p - 1
    mod_target = L * L

    # Target prefix
    prefix = b"Get Flag."
    P = bytes_to_long(prefix)

    # We need M = k * (L^2) such that M starts with 'Get Flag.'
    # We use a large padding (e.g., 300 bytes) to ensure we can find such a k
    padding_bytes = 300
    lower_bound = P * (256 ** padding_bytes)

    # Find the smallest k such that k * L^2 >= lower_bound
    k = (lower_bound + mod_target - 1) // mod_target
    M_int = k * mod_target
    M_bytes = long_to_bytes(M_int)

    # Safety check: ensure the prefix is correct
    if not M_bytes.startswith(prefix):
        print("[-] Prefix mismatch. Adjusting padding...")
        # If it doesn't match, it's likely due to byte alignment;
        # normally k calculation ensures it starts with P.
        return

    # If H = 1, then signature = 1 is always valid for RSA
    message_hex = M_bytes.hex()
    signature = 1

    print(f"[+] Sending message starting with: {M_bytes[:10]}")
    io.sendlineafter(b"input message (hex): ", message_hex.encode())
    io.sendlineafter(b"input signature (int): ", str(signature).encode())

    # Get the flag
    result = io.recvall().decode()
    print(result)

if __name__ == "__main__":
    solve()