The CTF problem “Omni Crypto” asked you to crack a weakly-generated RSA key, where the primes share some MSBs and LSBs. We did this using Don Coppersmith’s famous small-roots LLL algorithm.

Disclaimer

This writeup may have a few incorrect or inaccurate statements about cryptography.

Problem

Pwn2Win problem from May 2020:

One of the first versions of the S1 Protocol had a faulty encryption protocol. We captured the communication between two important ButcherCorp leaders and now it’s up to you know what they were planning. Although it’s an old communcation, the information there can still be useful to the Rebelious Fingers.

The problem includes the RSA parameters and , ciphertext , and the code that generated them.

import gmpy2
import random
from Crypto.Util.number import bytes_to_long

def getPrimes(size):
    half = random.randint(16, size // 2 - 8)
    rand = random.randint(8, half - 1)
    sizes = [rand, half, size - half - rand]

    while True:
        p, q = 0, 0
        for s in sizes:
            p <<= s
            q <<= s
            chunk = random.getrandbits(s)
            p += chunk 
            if s == sizes[1]:
                chunk = random.getrandbits(s)
            q += chunk
        p |= 2**(size - 1) | 2**(size - 2) | 1
        q |= 2**(size - 1) | 2**(size - 2) | 1
        if gmpy2.is_prime(p) and gmpy2.is_prime(q):
            return p, q

e = 65537
p, q = getPrimes(1024)
N = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = bytes_to_long(open("flag.txt", "rb").read())
c = pow(m, e, N)
print("N =", hex(N))
print("c =", hex(c))

Analysis

We notice that the -bit primes are identical, except that at most of their middle bits differ, in one contiguous group.

(The exact groupings were 235 || 398 || 391, where the 398 middle bits are different.)

In other words, the -bit primes and are of the form

p = a || b || c
q = a || d || c

Notice that since more than half of the bits are shared, if we can recover the shared bits, then we can use Coppersmith’s small-roots algorithm to recover the rest.

Recovering the Shared MSBs

Since (or vice-versa), then has the same MSBs (most-significant bits) as and .

Recovering the Shared LSBs

We can use a simple attack described by Steinfeld and Zheng to recover four candidates for the shared LSBs (least-significant bits) of and .

The attack works as follows:

  1. Let and , where is the shared-LSB suffix.
  2. Notice that
  3. If , then given a solution for there are exactly solutions for
    • The solutions are , , , and
  4. To construct a single solution for , we can use an iterative algorithm described by Bach and Shallit

The implementation following SZ and BS looks like

def get_next(x, N, k):
    """
    Get next candidate for `x` and `k` (following Bach and Shallit)
    """
    siz = 2 ** (2 * k - 2)
    tot = siz // 2 - 1
    inv = pow(x, tot, siz)
    return (
        ((x - ((x * x - N) // 2) * inv)) % (2 ** (2 * k - 2)),
        2 * k - 2
    )

def get_lsb_candidates(bits, N):
    """
    Returns list of LSB candidates for `N`, assuming the primes share `bits` LSBs.
    """
    # start with a square root of N mod 8
    curr = 0
    for i in range(2, 8):
        if (i * i) % 8 == N % 8:
            curr = i
            break
    
    # increase modulus by m' = 2m - 2 until we get a solution mod 2^bits
    k = 3
    while True:
        curr, k = get_next(curr, N, k)
        assert (curr * curr) % (2 ** k) == N % (2 ** k)
        lhs = (curr * curr) % (2 ** bits)
        rhs = N % (2 ** bits)
        if lhs == rhs:
            break
    
    m = 2**bits
    curr = curr % m
    return [
        curr,
        m - curr,
        ((m // 2) + curr) % m,
        (m + (m // 2) - curr) % m,
    ]

Coppersmith attack

Now that we can recover candidates for the LSBs and MSBs, we can try a Coppersmith small-roots attack on every possible partition using a sliding window of size 504 (the worst case).

Luckily, “Ruggero” on StackExchange Crypto has already implemented this for us in sage. We just have to run it on our candidates.

from time import time
from factor import get_lsb_candidates

N = Integer(int("0xf7e6ddd1f49d9f875904d1280c675e0e03f4a02e2bec6ca62a2819d521441b727d313ec1b5f855e3f2a69516a3fea4e953435cbf7ac64062dd97157b6342912b7667b190fad36d54e378fede2a7a6d4cc801f1bc93159e405dd6d496bf6a11f04fdc04b842a84238cc3f677af67fa307b2b064a06d60f5a3d440c4cfffa4189e843602ba6f440a70668e071a9f18badffb11ed5cdfa6b49413cf4fa88b114f018eb0bba118f19dea2c08f4393b153bcbaf03ec86e2bab8f06e3c45acb6cd8d497062f5fdf19f73084a3a793fa20757178a546de902541dde7ff6f81de61a9e692145a793896a8726da7955dab9fc0668d3cfc55cd7a2d1d8b631f88cf5259ba1", 16))

def solve(lo, hi):
    knownbits = lo + hi
    sizep = 1024
    p_msb = (isqrt(N) >> (sizep - hi)) << (sizep - hi)

    for l in get_lsb_candidates(lo, int(N)):
        p_lsb = Integer(l)

        R = 2 ** lo
        invR = inverse_mod(R, N)

        F.<x> = PolynomialRing(Zmod(N))
        f = x + (p_msb + p_lsb) * invR
        try:
            x0 = f.small_roots(X=2^(sizep - knownbits)-1, beta=0.44)[0]
        except:
            # no roots found
            continue

        ans = Integer(x0 * R) + p_lsb + p_msb
        print("reconstructed p: {:x}".format(ans))

t0 = time()

half = (1024 // 2) - 8 # worst case
for rand in range(half - 1, 7, -1):
    print(rand, half, 1024-half-rand)
    solve(1024-half-rand, rand)

print(time() - t0)
# 166 seconds (2015 i5 8GB MacBook Pro)

It starts finding solutions at partition 236 || 504 || 284 (by luck; guaranteed at 235) and finds its last solution at 129 || 504 || 391 (as expected).

Here is the value for .

reconstructed p: fbeb1a7886ef44622066fa094ac36e67bae3ae428725ae40b33b4360f15502329379f55582e4fed5b5db1092155a566973adb60112301d087e794845d3fc0cce57e015acce21d2e86a8ee8cea59239dddf4443a736d33190bd7f72b400829118b5bc520817f4210dbcefb930c1f5cce6c9fc9e3a903118b0a838cec76a090eaf

We decrypt the ciphertext and get the plaintext (and flag):

Here is the message: CTF-BR{w3_n33d_more_resources_for_th3_0mni_pr0j3ct}