Cross-posted @ kevinliu.me/posts/cryptoverse/

Another win for Maple Bacon!

A Tale of Two Systems

It’s impossible to get a secure cryptosystem by combining two insecure cryptosystems.

This challenge is split into two stages independent from each other.

Stage 1

NBITS = 1024

def system_one(m: bytes):
    a, b = [getRandomNBitInteger(NBITS) for _ in range(2)]
    p = getPrime(2 * NBITS)
    q = getPrime(NBITS // 2)
    g = inverse(a, p) * q % p

    ct = (b * g + bytes_to_long(m)) % p

    print(f"p = {p}")
    print(f"g = {g}")
    print(f"ct = {ct}\n")

At first, this system doesn’t seem solvable because $a$ and $b$ are randomly generated and used in the encryption process. However, since we know the relative sizes of the parameters, we can apply some ✨ lattice magic ✨ to recover $a$ and $b$, and subsequently $m$.

First, the sizes of the internal variables are bounded by:

• $a$ - 1024 bits
• $b$ - 1024 bits
• $p$ - 2048 bits
• $q$ - 512 bits
• $g$ - 2048 bits
• $ct$ - 2048 bits

From the encryption process, we have that:

Thus, there exists some integer $k$ such that $ga = pk + q$.

Since $ga$ is 3072 bits and $p$ is 2048 bits, $k$ will be around 1024 bits.

Now, consider the lattice:

Notice that we can express the vector $(q, a-k)$ as a linear combination of the rows of the lattice:

Since $q$ is 512 bits while $a$ and $k$ are 1024 bits, this vector is “small” compared to the original rows with 2048 bit numbers. So, we can apply LLL and hope that the small basis vector is $(q, a-k)$:

m = Matrix([[p, 1], [g, 1]])
print(m.LLL())

Now that we have $q$ and $a$ from the lattice reduction, we can decrypt the message.

Observe that:

However, since $p$ is 2048-bit and $bg$ and $am$ are both around ~1500 bits,

From this, recovering $m$ is easy:

m = Matrix([[p, 1], [g, 1]])
m = m.LLL()
q = m[0][0]
a = inverse(g, p) * q % p
temp = a * ct % p
m = temp * inverse(a, q) % q
print(long_to_bytes(m))

Flag: cvctf{n0_On3_1S_u53l355_1n_7h15_w0r1d_...

Stage 2

def system_two(m: bytes):
    p, q = [getPrime(NBITS // 2) for _ in range(2)]
    n = p * q
    e = 0x10001
    ct = pow(bytes_to_long(m), e, n)

    print(f"n = {n}")
    print(f"e = {e}")
    print(f"ct = {ct}")
    
    # what if q is reversed?
    q = int('0b' + ''.join(reversed(bin(q)[2:])), 2)
    hint = p + q - 2 * (p & q)
    print(f"hint = {hint}")

First, let’s make sense of the hint: what does x + y - 2 * (x & y) represent for two arbitrary integers $x$ and $y$?

Let’s say $a_i$ represents the $i$th bit of a number $a$. Working in binary, $(x \& y)_i$ is 1 if and only if $x_i = y_i = 1$. When we add $x$ and $y$ in those positions, the sum of $1+1$ in binary will carry over to the next position. But this is perfectly cancelled out when we subtract $(x \& y)$ shifted to the left by 1.

In other words, if $x_i = y_i = 0$ or if $x_i=y_i=1$, then the corresponding bit $(x \& y)_i$ is 0. This is just the XOR operation between $x$ and $y$!

Our goal is to factor $n$, and we currently know:

• $n = pq$
• $p \oplus rev(q)$

Similar: XORSA

A similar problem appeared in PlaidCTF, where $p \oplus q$ was given. The central idea of one solution is to find the bits of $p$ and $q$ one by one.

Starting from the lowest bit, there are always two possibilities for $(p, q)$ since we know $(p \oplus q)$. We can try both of these possibilities recursively, for a naive solution of $2^k$ where $k$ is the number of bits in $n$. But, we can prune the majority of the search space by checking that \(p_0 \cdot q_0 \equiv n \mod 2^l\)

for our current $p_0$ and $q_0$ (lower bits of $p$ and $q$). This optimization is enough to solve the XORSA challenge.

Back on track

Let’s apply a similar idea to our problem, but instead of starting only from the lower bits, we recurse over the lower and higher bits simultaneously.

Specifically, we can guess the highest bits of $rev(q)$ and the highest bits of $p$. At the same time, we can guess the lowest bits of $rev(q)$ and the lowest bits of $p$. Note that the highest bits of $rev(q)$ are the lowest bits of $q$, and vice versa.

To optimize this brute force, at each step we prune over the lower bits by checking that:

Additionally, we prune over the top bits:

• If we set the remaining bits of $p_{high}$ and $q_{high}$ to $1$, the product $p_{high}q_{high}$ must be greater than $n$
• If we set the remaining bits of $p_{high}$ and $q_{high}$ to $0$, the product $p_{high}q_{high}$ must be less than $n$.

The final solve script:

n = 153342396916538105228389...
e = 65537
ct = 1073382308863262771844706024...
# p xor (reverse q)
xor = 35510848380770904338319...
NBITS = 512

# q = highQ || lowQ and p = highP || lowP, where all high/low have idx bits
def find(idx, lowP, highP, lowQ, highQ):

    if idx == NBITS:
        assert highP * highQ == n
        print("FOUND!")
        print(highP)
        print(highQ)
        exit()


    highX = (xor >> (NBITS - 1 -idx)) & 1
    lowX = (xor >> idx) & 1

    possibleLow = []
    possibleHigh = []
    
    # find possible (highP, lowQ) pairs from the MSB of the XOR
    if highX == 1:
        possibleHigh.append(((highP << 1) | 1, lowQ))
        possibleHigh.append((highP << 1, lowQ + (1 << idx)))
    else:
        possibleHigh.append((highP << 1, lowQ))
        possibleHigh.append(((highP << 1) | 1, lowQ + (1 << idx)))
    
    # find possible (lowP, highQ) pairs from the LSB of the XOR
    if lowX == 1:
        possibleLow.append((lowP, (highQ << 1) | 1))
        possibleLow.append((lowP + (1 << idx), highQ << 1))
    else:
        possibleLow.append((lowP, highQ << 1))
        possibleLow.append((lowP + (1 << idx), (highQ << 1) | 1))


    for highP, lowQ in possibleHigh:
        for lowP, highQ in possibleLow:
            # prune lower bits
            if lowP * lowQ % (1 << (idx + 1)) != n % (1 << (idx + 1)):
                continue
            
            pad = NBITS-1-idx

            # check upper bit bounds
            if (highP << pad) * (highQ << pad) > n:
                continue

            if ((highP << pad) + (1 << pad) - 1) * ((highQ << pad) + (1 << pad) - 1) < n:
                continue

            find(idx+1, lowP, highP, lowQ, highQ)

find(0, 0, 0, 0, 0)

Partial flag: _wH0_l16h73N5_tHe_BurD3nS_0F_4n07h3R.-_-}

Final flag: cvctf{n0_On3_1S_u53l355_1n_7h15_w0r1d_..._wH0_l16h73N5_tHe_BurD3nS_0F_4n07h3R.-_-}