TL;DR

This challenge involved exploiting a vulnerability in an RSA implementation where the creator leaked more than half of the XOR of the prime factors. The solution reconstructs the prime factors bit-by-bit using a recursive approach that:

1. Starts with the most significant bits
2. Uses the leaked XOR bits to constrain possibilities
3. Prunes invalid paths via product bounds
4. Switches to Coppersmith’s method for remaining bits
5. Decrypts the flag with the recovered private key

Challenge Overview

The challenge provides this RSA implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from Crypto.Util import number
flag = b"REDACTED"
bits = 1024
p = number.getPrime(bits)
q = number.getPrime(bits)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = number.inverse(e, phi)
extra = 75
c = pow(int.from_bytes(flag, 'big'), e, n)
print(f"n: {hex(n)}")
print(f"e: {hex(e)}")
print(f"c: {hex(c)}")
print(f"partial p^q: {hex((p^q) >> (bits // 2 - extra))}")

This looks like standard RSA encryption, but there’s a critical information leak:

$${\tt partial\ p\oplus q} = (p \oplus q) \gg (\text{bits} // 2 - \text{extra})$$

Task Analysis

What do we know?

Key Insight: The XOR constraint dramatically reduces the search space. For each bit position, if we know \( p_i \oplus q_i \), we only have 2 possibilities instead of 4:

This is much better than trying all 4 combinations!

Exploitation

Algorithm Overview

Our recursive algorithm works from MSB to LSB:

1. Start at the most significant bit
2. For each bit position, try both possibilities allowed by \( p \oplus q \)
3. Prune invalid candidates using product bounds
4. Once XOR bits are exhausted, use Coppersmith’s method for remaining bits
5. Recover the private key and decrypt

Product Bounds Pruning

For partially reconstructed \( p_{\text{high}} \) and \( q_{\text{high}} \), if we’ve decided \( k \) bits, the remaining \( m \) bits form unknown parts.

The minimum product (all remaining bits 0): $$p_{\min} \cdot q_{\min} = (p_{\text{high}} \ll m) \cdot (q_{\text{high}} \ll m)$$

The maximum product (all remaining bits 1): $$p_{\max} \cdot q_{\max} = ((p_{\text{high}} « m) + 2^m - 1) \cdot ((q_{\text{high}} « m) + 2^m - 1)$$

Pruning rule: If \( n \) is outside \( [p_{\min}, p_{\max}] \), this branch cannot produce the target modulus and can be skipped!

┌─────────────────────────┐
│ Bit-by-bit recursion    │
├─────────────────────────┤
│ k = 1023 (MSB)          │
│ Try 2 possibilities     │
│ ├─ Check bounds         │
│ ├─ If valid: recurse    │
│ └─ If invalid: skip     │
│                         │
│ ...repeat down to LSB   │
│                         │
│ k < 512 - 75            │
│ └─ Call Coppersmith     │
└─────────────────────────┘

Complete Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

from Crypto.Util.number import *
from sage.all import *
import sys
load('coppersmith.sage')

b = 1024
xor = 0x64...
n = 0x46...
e = 0x10001
c = 0x38...

def find(k, p_high, q_high):
    """
    Recursively recover p and q bit by bit from MSB to LSB

    Args:
        k: Current bit position (starts at NBITS-1, decreases)
        p_high: Recovered bits of p so far
        q_high: Recovered bits of q so far
    """
    l = p_high.bit_length()

    if k < b//2 - 75:
        l = 512 - 75
        R = 2**l
        x, y = var('x y')
        p_ = p_high * R + x
        q_ = q_high * R + y
        f = (p_ * q_ - n).expand()
        PR = PolynomialRing(Zmod(n), names=('x', 'y'))
        f = PR(f)
        try:
            x, y = small_roots(f, [R, R], m=3, d=4)[0]
            P = int(p_high * R + x)
            Q = int(q_high * R + y)
            if n % P == 0:
                phi = (P - 1) * (Q - 1)
                d = inverse(e, phi)
                m = pow(c, d, n)
                print(long_to_bytes(m))
                sys.exit(0)
        except:
            pass
        return

    xor_k = (xor >> (k - b//2 + 75)) & 1

    possibilities = [(0, 0), (1, 1)] if xor_k == 0 else [(0, 1), (1, 0)]

    for p_k, q_k in possibilities:
        p_high_new = (p_high << 1) | p_k
        q_high_new = (q_high << 1) | q_k

        m = NBITS - k
        shift = NBITS - m
        min_prod = (p_high_new << shift) * (q_high_new << shift)
        max_prod = (((p_high_new << shift) + (1 << shift) - 1) *
                    ((q_high_new << shift) + (1 << shift) - 1))

        if min_prod <= n <= max_prod:
            find(k - 1, p_high_new, q_high_new)

NBITS = b
find(NBITS - 1, 0, 0)

Behind the Math

Why XOR Information is Powerful

For each bit position \( i \):

$$p_i \oplus q_i = \begin{cases} 0 & \text{if } p_i = q_i \ 1 & \text{if } p_i \neq q_i \end{cases}$$

This transforms a combinatorial search problem (try all \( 2^{1024} \) candidates) into a constraint satisfaction problem (only 2 valid choices per bit).

Product Bounds as a Pruning Heuristic

The modulus \( n = p \cdot q \) is a strict constraint. For fixed MSBs:

$$p = p_{\text{high}} \cdot 2^m + p_{\text{low}}$$ $$q = q_{\text{high}} \cdot 2^m + q_{\text{low}}$$

where \( 0 \leq p_{\text{low}}, q_{\text{low}} < 2^m \).

Therefore: $$n = (p_{\text{high}} \cdot 2^m + p_{\text{low}}) \cdot (q_{\text{high}} \cdot 2^m + q_{\text{low}})$$

The product ranges from: $$(p_{\text{high}} \cdot 2^m) \cdot (q_{\text{high}} \cdot 2^m)$$

to: $$((p_{\text{high}} + 1) \cdot 2^m - 1) \cdot ((q_{\text{high}} + 1) \cdot 2^m - 1)$$

If \( n \) is outside this range, no valid \( p_{\text{low}}, q_{\text{low}} \) exist. Pruning is safe!

Coppersmith’s Method for the Tail

Once we’ve fixed ~575 MSBs via the XOR constraint, we need to find the remaining ~449 bits. These form a “small” root:

$$f(x, y) = (p_{\text{high}} \cdot R + x) \cdot (q_{\text{high}} \cdot R + y) - n$$

where \( R = 2^{449} \) and \( x, y < R \).

Coppersmith’s theorem guarantees we can find this small root using lattice reduction (LLL algorithm), provided:

$$X \cdot Y < n^{1/(d+1)}$$

where \( d \) is the polynomial degree and \( X, Y \) are the bounds on roots.

Exploitation Timeline

┌────────────┐
│   Start    │
└─────┬──────┘
      │
      ├─ Parse leaked XOR (575 MSBs)
      ├─ Parse modulus n
      └─ Start recursive search from MSB
      │
      ├─ [~5 mins] Try bit combinations with bounds checking
      ├─ Most branches pruned early
      ├─ Explore ~10,000 valid paths to LSB
      │
      └─ [~5 mins] Hit base case, call Coppersmith
         │
         ├─ Solve \\( f(x,y) = p_{\text{high}} \cdot R + x \\)
         ├─ Recover p and q
         └─ Compute \\( d = e^{-1} \pmod{\phi(n)} \\)
         │
         └─ [~1 sec] Decrypt: \\( m = c^d \pmod{n} \\)
            │
            └─ Flag: UMASS{i_will_make_a_solve_script}

Total runtime: ~10 minutes

Conclusions

References

• Integer factorization with additional knowledge of \( p \oplus q \)
• XOR Factor Implementation
• Coppersmith’s Attack on RSA
• Coppersmith, D. “Small solutions to polynomial equations, and low exponent RSA vulnerabilities.” Journal of Cryptology 10.4 (1997): 233-260.