TJCTF 2026: Bit Leak

This writeup covers the Bit Leak challenge from TJCTF 2026, a classic RSA Parity Oracle attack. The server provides an oracle that, given any ciphertext C', decrypts it and returns only the Least Significant Bit (LSB) of the resulting plaintext — that is, Dec(C') mod 2. While a single bit leak seems harmless at first glance, the multiplicative homomorphic property of RSA allows us to leverage this 1-bit oracle to recover the entire plaintext through a binary search over the rational number space. This is one of the most elegant attacks in applied cryptography: a single bit of information per query, iterated ~540 times, completely breaks the confidentiality of a 512-bit RSA ciphertext.

Bit Leak: Overview

The challenge presents us with an RSA encryption oracle with a twist: instead of returning the full plaintext, the server only reveals whether the decrypted value is even or odd. Specifically, when we submit a ciphertext C', the server computes m' = Dec(C') = (C')d mod n and returns m' mod 2 — a single bit indicating the parity of the decrypted message.

At first, this might seem like negligible information leakage. After all, knowing whether a number is even or odd reveals only 1 bit out of 512. However, RSA’s mathematical structure makes this single bit devastatingly powerful. The key property is that RSA is multiplicatively homomorphic: multiplying two ciphertexts together (modulo n) produces a ciphertext that decrypts to the product of the corresponding plaintexts. This means we can multiply the plaintext by any value we choose without ever knowing it, simply by manipulating the ciphertext.

By repeatedly multiplying the plaintext by 2 and querying the oracle each time, we obtain the LSB of 2 × m mod n, 4 × m mod n, 8 × m mod n, and so on. Each of these parity bits corresponds to a successive bit in the binary expansion of the fraction m/n. After collecting approximately log2(n) + margin bits (540 for 512-bit RSA), we have enough information to reconstruct m exactly through a technique called rational number reconstruction.

RSA Multiplicative Homomorphic Property

The foundation of the parity oracle attack is RSA’s multiplicative homomorphism. In RSA, encryption is defined as C = me mod n and decryption as m = Cd mod n, where e is the public exponent and d is the private exponent. The homomorphic property arises because exponentiation distributes over multiplication in modular arithmetic:

This means that if we multiply two RSA ciphertexts together modulo n, the result decrypts to the product of the two plaintexts. Concretely, if we want to multiply the unknown plaintext m by a known constant k, we simply compute C' = C × ke mod n and submit C' to the oracle:

The choice of k = 2 is particularly convenient because multiplying by 2 in integer arithmetic is equivalent to a left bit-shift. In the context of modular arithmetic, this shift “wraps around” when the product exceeds n, and the parity (LSB) of the result tells us whether a wrap-around occurred. This is the crux of the attack: each parity bit reveals information about the fractional representation of m/n.

Step-by-Step Derivation

Let us define the sequence of modified ciphertexts. For each iteration i from 0 to 539, we compute:

When we submit Ci to the oracle, it returns LSB(2i × m mod n). We can precompute f = 2e mod n once, and then each successive ciphertext is simply Ci+1 = Ci × f mod n. This makes the attack efficient: each oracle query requires only one modular multiplication to prepare the ciphertext.

Modulo Scaling Technique: 2ⁱ × m

The central insight of the parity oracle attack is the connection between the LSB of 2i × m mod n and the binary expansion of the fraction m/n. To see why this works, consider what happens when we multiply m by successive powers of 2 in modular arithmetic.

In ordinary integer arithmetic (no modular reduction), multiplying m by 2i simply shifts the binary representation of m left by i positions. The LSB of the result is always 0 (since we’re multiplying by a power of 2), which is not informative. However, in modular arithmetic, when 2i × m exceeds n, it wraps around. The LSB after this wrap-around reveals crucial information about the relationship between m and n.

Connection to Binary Fraction Expansion

Consider the rational number m/n. We can express this as a binary fraction:

Since m < n (as required by RSA), we have b0 = 0 and m/n is purely a fractional value between 0 and 1. Now, multiplying by 2 shifts the binary point right by one position:

The integer part b1 tells us whether 2 × m ≥ n (i.e., whether a wrap-around occurred). And the LSB of 2 × m mod n is exactly b1! More generally:

This is the key result: the LSB returned by the oracle at step i is exactly the i-th bit of the binary fraction m/n. By collecting 540 consecutive bits, we obtain the first 540 fractional bits of m/n, which provides sufficient precision to reconstruct m exactly for a 512-bit modulus.

Rational Number Reconstruction

After collecting 540 LSB responses from the oracle, we have a sequence of bits b1, b2, ..., b540. These bits represent the first 540 fractional bits of m/n in binary. The reconstruction process converts these bits back into the integer m.

Bit Packing into Integer B

First, we pack the collected bits into a single large integer B. If we interpret the bit sequence as a binary fraction, then:

This is equivalent to B = int(bits_string, 2) in Python. In fractional terms, B / 2540 ≈ m/n, since the bits represent the first 540 fractional binary digits of m/n.

Plaintext Recovery Formula

From the approximation B / 2540 ≈ m/n, we can solve for m:

In integer arithmetic, this becomes a right-shift operation:

The +1 compensates for truncation error in the bit collection process, and the right-shift by 540 effectively divides by 2⁵⁴⁰. This formula recovers m exactly, provided we collected enough bits (which 540 guarantees for a 512-bit modulus). The result is then converted from an integer to bytes using long_to_bytes(m) to obtain the flag string.

Exploit: Bit Leak

The following Python script implements the complete parity oracle attack. It connects to the challenge server, sends 540 crafted ciphertexts using the homomorphic property, collects the LSB responses, and reconstructs the plaintext via rational reconstruction. The script uses sequential queries (one at a time) for reliability, with robust response parsing that handles TCP stream fragmentation.

#!/usr/bin/env python3
"""
TJCTF 2026 - Bit Leak
RSA Parity Oracle attack via LSB leak + Rational Reconstruction
Author: Yuri08
"""
import socket
from Crypto.Util.number import long_to_bytes


def parity_oracle_attack(ip, port, n, e, c, num_bits=540):
    """
    Exploit RSA Parity Oracle by collecting LSBs
    of 2^i * m mod n and reconstructing m.

    Uses sequential queries for reliable TCP response parsing.
    """
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect((ip, port))

    # Skip server banner
    sock.recv(1024)

    # Precompute: encryption of 2 under the public key
    multiplier = pow(2, e, n)       # 2^e mod n
    c_i = c                          # Running ciphertext (starts with original C)
    lsb_responses = []

    print(f"[*] Collecting {num_bits} LSBs from Oracle...")

    for i in range(num_bits):
        # Send ciphertext
        sock.sendall((str(c_i) + "\n").encode())

        # Receive LSB response (robust parsing for TCP stream)
        resp = b""
        while True:
            chunk = sock.recv(64)
            if not chunk:
                raise ConnectionError("Server closed connection unexpectedly")
            resp += chunk
            if b"\n" in resp:
                break

        lsb_str = resp.decode().strip().split("\n")[0]
        lsb_responses.append(int(lsb_str))

        # Advance: C_{i+1} = C_i * 2^e mod n
        # This makes Dec(C_{i+1}) = 2^(i+1) * m mod n
        c_i = (c_i * multiplier) % n

        if (i + 1) % 100 == 0:
            print(f"    ... collected {i + 1}/{num_bits} bits")

    sock.close()

    # ── Rational Reconstruction ─────────────────────────
    print("[*] Reconstructing plaintext from bit leak...")
    bits_str = "".join(str(b) for b in lsb_responses)

    # m = (n * (B + 1)) >> num_bits
    B = int(bits_str, 2)
    m = (n * (B + 1)) >> num_bits

    flag = long_to_bytes(m).decode()
    print(f"[+] Flag: {flag}")
    return flag


if __name__ == "__main__":
    # Replace with actual server parameters from the challenge
    N = 0x00  # RSA modulus
    E = 65537  # Public exponent
    C = 0x00  # Ciphertext to decrypt

    parity_oracle_attack("tjc.tf", 31415, N, E, C)

Exploit Output

$ python3 bit_leak_exploit.py
[*] Collecting 540 LSBs from Oracle...
    ... collected 100/540 bits
    ... collected 200/540 bits
    ... collected 300/540 bits
    ... collected 400/540 bits
    ... collected 500/540 bits
[*] Reconstructing plaintext from bit leak...
[+] Flag: tjctf{parity_isnt_privacy}

Attack Walkthrough: Bit by Bit

To solidify the intuition, let’s trace through the first few iterations of the attack with concrete values. Suppose n = 143 (a toy example with p = 11, q = 13) and the secret plaintext is m = 41.

Notice how the LSB of 2i × m mod n exactly matches the successive bits of the binary fraction 41/143. In the real challenge with a 512-bit modulus, we extend this to 540 iterations. The binary fraction 0.101001... accumulated from the oracle responses is then multiplied by n and right-shifted to recover m.

The wrap-around at step 2 (164 mod 143 = 21) is particularly illustrative: the original product 164 exceeds n = 143, so the modular reduction “subtracts” one copy of n. This subtraction flips the parity from what it would have been without the wrap-around, and it is precisely this flip that encodes the binary fraction information.