bit-leak

Platform: tjctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-05-15 | Status: Solved Techniques: binary_search_interval_narrowing, chosen_ciphertext_multiplication, rsa_lsb_oracle_attack

Summary

Task: RSA parity oracle — server decrypts chosen ciphertexts and returns only the LSB (even/odd). Solution: exploit RSA multiplicative homomorphism to perform binary search on plaintext via repeated multiplication by 2^e mod n, recovering the exact message in ~512 queries.

bit-leak — TJCTF 2026

Description

our security monitor only ever tips us off about the parity of RSA decryptions. turns out "even or odd" isn't much of a secret. can you recover the message one bit at a time?

The server generates RSA with two 256-bit primes (512-bit modulus), e=65537. It encrypts the flag and provides n, e, and the ciphertext. The user gets up to 2100 parity oracle queries: send any ciphertext, receive pow(ciphertext, d, n) & 1 — the least significant bit (parity) of the decrypted value.

Analysis

This is a classic RSA LSB (Parity) Oracle scenario. The key insight is that RSA's multiplicative homomorphism allows us to manipulate the underlying plaintext without knowing it:

RSA Homomorphism: Given ciphertext c = m^e mod n, if we compute c' = c * 2^e mod n, then decrypting c' yields 2m mod n.

Parity reveals range information: Since n is odd (product of two odd primes):

• If 2m mod n is even → 2m < n → m < n/2
• If 2m mod n is odd → 2m ≥ n (reduction happened) → m ≥ n/2

Each query eliminates half the candidate range, giving us a binary search over [0, n).

Query budget: With a 512-bit modulus, we need exactly 512 queries. The server allows 2100, giving ample margin.

Precision: Floating-point arithmetic would lose precision over 512 iterations. The solve script tracks bounds as integer numerators with a shared power-of-2 denominator (lower_num/2^k, upper_num/2^k), maintaining exact arithmetic throughout.

Solution

Step-by-step

1. Connect to the server and parse n, e, and ciphertext
2. Precompute the multiplier: multiplier = pow(2, e, n) — this is 2^e mod n
3. Initialize bounds: lower = 0, upper = n (conceptually)
4. For each of 512 iterations:
   • Multiply the working ciphertext by multiplier mod n (equivalent to multiplying the plaintext by 2)
   • Send the modified ciphertext to the oracle
   • If LSB = 0 (even): plaintext is in the lower half → update upper bound
   • If LSB = 1 (odd): plaintext is in the upper half → update lower bound
5. Recover the plaintext from the converged bounds
6. Verify by re-encrypting: pow(m, e, n) == c

Server source (key oracle logic)

 python read-only • copy allowed Copy
# server.py - RSA setup
p = generate_prime(256)
q = generate_prime(256)
n = p * q
e = 65537
d = modinv(e, (p-1)*(q-1))
ciphertext = pow(bytes_to_long(flag), e, n)

# Oracle: user sends candidate ciphertext, gets LSB of decryption
parity = pow(candidate, d, n) & 1
print(f"lsb = {parity}")

Solve script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
RSA LSB (Parity) Oracle Attack
TJCTF 2026 - bit-leak
"""
from pwn import *
import re

HOST = "tjc.tf"
PORT = 31001

def main():
    r = remote(HOST, PORT)
    
    data = r.recvuntil(b"parity queries.")
    data_str = data.decode()
    
    n = int(re.search(r'n = (\d+)', data_str).group(1))
    e = int(re.search(r'e = (\d+)', data_str).group(1))
    c = int(re.search(r'ciphertext = (\d+)', data_str).group(1))
    
    log.info(f"n = {n}")
    log.info(f"e = {e}")
    log.info(f"c = {c}")
    
    num_bits = n.bit_length()
    
    # Track bounds as integers: actual_lower = lower_num * n / 2^denom_power
    lower_num = 0
    upper_num = 1
    denom_power = 0
    
    multiplier = pow(2, e, n)
    current_c = c
    
    log.info(f"Starting LSB Oracle Attack ({num_bits} iterations)")
    
    for i in range(num_bits):
        # Multiply ciphertext by 2^e mod n → plaintext becomes 2*m mod n
        current_c = (current_c * multiplier) % n
        
        r.recvuntil(b"> ")
        r.sendline(b"1")
        r.recvuntil(b"ciphertext = ")
        r.sendline(str(current_c).encode())
        
        resp = r.recvline().decode().strip()
        lsb = int(resp.split("=")[1].strip())
        
        # Double both bounds (shift denominator)
        lower_num *= 2
        upper_num *= 2
        denom_power += 1
        
        if lsb == 0:
            # 2^k * m mod n is even → m < midpoint
            upper_num = (lower_num + upper_num) // 2
        else:
            # 2^k * m mod n is odd → m >= midpoint
            lower_num = (lower_num + upper_num) // 2
        
        if (i + 1) % 64 == 0:
            log.info(f"Progress: {i + 1}/{num_bits} bits")
    
    # Recover plaintext from converged bounds
    for label, base in [("upper", (upper_num * n) >> denom_power), 
                         ("lower", (lower_num * n) >> denom_power)]:
        for delta in range(-5, 6):
            candidate = base + delta
            if candidate <= 0:
                continue
            try:
                flag_bytes = candidate.to_bytes((candidate.bit_length() + 7) // 8, 'big')
                flag_str = flag_bytes.decode('ascii', errors='replace')
                if 'tjctf{' in flag_str:
                    log.success(f"[{label}+{delta}] FLAG: {flag_str}")
                    # Verify by re-encrypting
                    verify_c = pow(candidate, e, n)
                    if verify_c == c:
                        log.success(f"VERIFIED! m encrypts to c correctly")
            except:
                pass
    
    r.close()

if __name__ == "__main__":
    main()

Why integer arithmetic matters

After k iterations, the bounds are fractions with denominator 2^k. With k = 512, floating-point (64-bit double, ~53 bits of mantissa) would lose all precision after ~53 iterations. The script avoids this by tracking lower_num and upper_num as arbitrary-precision Python integers, only converting to the actual plaintext value at the very end via (bound * n) >> denom_power.

Why the small delta search

Due to integer division rounding over 512 steps, the final bounds may be off by a few units. The script checks base ± 5 for both the upper and lower bound, verifying each candidate by re-encryption (pow(m, e, n) == c).