Boolean Predictor

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: binary_search, multiplicative_property, rsa_lsb_oracle_attack

Summary

Walkthrough of the CUSTOM Crypto Boolean Predictor. Task: RSA parity oracle that reveals if decrypted message is even/odd. Solution: LSB oracle attack using multiplicative property of RSA to perform binary search and recover the plaintext in log2(n) qu

Description

"Этот нострадамус явно знает больше, чем вы, однако на любой вопрос он способен говорить только да или нет."

(This nostradamus clearly knows more than you, but to any question he can only say yes or no.)

The server provides:

• Endpoint /public_key — returns the RSA public key (n, e) and the encrypted flag
• Endpoint /oracle — accepts a ciphertext and returns whether the decrypted message is even

Analysis

Server Source Code

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
from flask import Flask, request, jsonify
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

def parity_oracle(ciphertext):
    m = pow(ciphertext, PRIVATE_KEY.d, PRIVATE_KEY.n)
    return m % 2 == 0  # LSB leak!

@app.route('/oracle', methods=['GET'])
def oracle():
    ciphertext = int(request.args.get('ciphertext', '0'))
    is_even = parity_oracle(ciphertext)
    return jsonify({"even": is_even})

Vulnerability: RSA LSB Oracle Attack

The server reveals the least significant bit (LSB) of the decrypted message through the parity check. This is a classic RSA attack. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key RSA properties:

1. Multiplicativity: Dec(c₁ × c₂) = Dec(c₁) × Dec(c₂) mod n

2. Multiplication by 2: If we multiply the ciphertext by 2^e mod n, the decrypted value becomes 2m mod n

3. Range determination: Since n is odd (product of two primes):

   • If 2m mod n is even → 2m < n → m < n/2
   • If 2m mod n is odd → 2m ≥ n → m ≥ n/2

Binary Search Algorithm

On each iteration, we narrow the range of possible m values by half:

Iteration 1: c' = c × 2^e mod n
  - oracle(c') = even  → m ∈ [0, n/2)
  - oracle(c') = odd   → m ∈ [n/2, n)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Iteration 2: c' = c × 4^e mod n  
  - Narrow the range by half again

...

Iteration 2048: Exact value of m

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
RSA LSB (Parity) Oracle Attack
Duckerz CTF - Boolean Predictor

The attack uses LSB leakage for binary search of the plaintext.
Requires log2(n) ≈ 2048 queries to the oracle.
"""
import requests
from Crypto.Util.number import long_to_bytes

BASE_URL = "http://tasks.duckerz.ru:30014"

def get_public_key():
    """Get public key and encrypted flag"""
    resp = requests.get(f"{BASE_URL}/public_key")
    data = resp.json()
    return int(data["n"]), int(data["e"]), int(data["ciphertext"])
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def query_oracle(ciphertext):
    """Query the parity oracle"""
    resp = requests.get(f"{BASE_URL}/oracle", params={"ciphertext": str(ciphertext)})
    return resp.json()["even"]

def lsb_oracle_attack(n, e, c):
    """
    LSB Oracle Attack using fractions for precision.
    
    We maintain bounds as fractions: lower_num/2^k and upper_num/2^k
    where k = denom_power (denominator power).
    """
    num_bits = n.bit_length()
    
    # Bounds as numerators of fractions with common denominator 2^denom_power
    lower_num, upper_num = 0, 1  # [0, 1] * n
    denom_power = 0
    
    # Multiplier for "multiply by 2" in encrypted form
    multiplier = pow(2, e, n)
    current_c = c
    
    print(f"[*] Starting LSB Oracle Attack ({num_bits} iterations)")
    
    for i in range(num_bits):
        # c' = c × 2^e mod n → Dec(c') = 2m mod n
        current_c = (current_c * multiplier) % n
        is_even = query_oracle(current_c)
        
        # Double the precision of bounds
        lower_num *= 2
        upper_num *= 2
        denom_power += 1
        
        if is_even:
            # 2m mod n is even → 2m < n → m < n/2 (in current range)
            upper_num = (lower_num + upper_num) // 2
        else:
            # 2m mod n is odd → 2m ≥ n → m ≥ n/2 (in current range)
            lower_num = (lower_num + upper_num) // 2
        
        if (i + 1) % 256 == 0:
            print(f"[*] Progress: {i + 1}/{num_bits} bits")
    
    # Calculate m = upper_num * n / 2^denom_power
    m = (upper_num * n) >> denom_power
    return m
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def main():
    print("[*] Fetching public key and ciphertext...")
    n, e, c = get_public_key()
    print(f"[+] n = {n}")
    print(f"[+] e = {e}")
    print(f"[+] c = {c}")
    
    print("\n[*] Performing LSB Oracle Attack...")
    m = lsb_oracle_attack(n, e, c)
    
    flag = long_to_bytes(m)
    print(f"\n[+] Recovered message: {flag}")
    print(f"[+] Flag: {flag.decode()}")

if __name__ == "__main__":
    main()

Running the Exploit

 bash read-only • copy allowed Copy
$ python3 solve.py
[*] Fetching public key and ciphertext...
[+] n = <2048-bit number>
[+] e = 65537
[+] c = <encrypted flag>
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

[*] Starting LSB Oracle Attack (2048 iterations)
[*] Progress: 256/2048 bits
[*] Progress: 512/2048 bits
[*] Progress: 768/2048 bits
[*] Progress: 1024/2048 bits
[*] Progress: 1280/2048 bits
[*] Progress: 1536/2048 bits
[*] Progress: 1792/2048 bits
[*] Progress: 2048/2048 bits

[+] Flag: DUCKERZ{REDACTED}

Mathematical Justification

Why Does This Work?

Let m be the original message, n be the RSA modulus.

Step 1: Query c × 2^e mod n

• Decrypts to 2m mod n
• If 2m < n: result is 2m (even)
• If 2m ≥ n: result is 2m - n (odd, since n is odd) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step k: Query c × 2^(ke) mod n

• Decrypts to 2^k × m mod n
• Each response bit narrows the range of m by half

After log₂(n) iterations, the range narrows to a single value.

Complexity

• Oracle queries: O(log n) ≈ 2048 for 2048-bit RSA
• Time: Depends on network latency, typically 1-5 minutes

Defense

• Use RSA-OAEP padding (rejects modified ciphertexts)
• Do not provide oracles that reveal information about the decrypted text
• Limit the number of requests to the decryption API ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

References

• Twenty Years of Attacks on the RSA Cryptosystem
• Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1
• CTF Wiki - RSA Oracle Attack ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering binary_search, multiplicative_property, rsa_lsb_oracle_attack was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-01-09 • CUSTOM • Boolean Predictor • Difficulty: Medium