[Purple Pill Challenge 2023] Secure House / Ladybug

Tags: #cryptography #ctf

2023-10-13

Secure House (aka. Ladybug) was a cryptography challenge from this year’s Purple Pill Challenge. It featured a casino in which users had to guess a random number in order to win coins. Once a certain coin threshold was met, the flag would be printed. The challenge source code is available here.

TL;DR

  • Copy paste Hellman’s writeup and pray.
  • Spend 2 x 4 coins to get two successive outputs from the QCG.
  • Use the two successive outputs to construct a bivariate polynomial.
  • Use the Coppersmith method to recover the internal state of the QCG.

Source code analysis

The PRNG class used by the casino is a truncated Quadratic Congruential Generator (QCG), a quadratic version of the more common truncated LCG. The “public parameters” (the coefficients and modulus) of the QCG are known however the outputs are truncated so we can’t clone the QCG just yet, we need to recover its internal state first.

class RNG:
    def __init__(self, seed):
        self.p = getStrongPrime(512)
        self.a = random.getrandbits(512)
        self.state = int.from_bytes(seed, "big") # seed = os.urandom(64)

    def _next(self):

        # y ≡ a * x**2 + b * x + c mod p
        # here a = 1, b = 0 and c = self.a  
        self.state = (self.state**2 + self.a) % self.p
        return self.state >> 170

Recovering the internal state

We only have enough coins to get two successive outputs from the casino but luckily, that’s all we need. With these two outputs, we can construct the following bivariate polynomial and use the Coppersmith method to find its roots.

Let v0, v1 be two successive untruncated outputs from a QCG (partially known),
let w0, w1 be two successive truncated outputs from a QCG (known) and
let x, y be the truncated parts of the two successive outputs (unknown).

    v1              = v0                ** 2 + a                     mod p
<=> w1 * 2**170 + y = (w0 * 2**170 + x) ** 2 + a                     mod p
<=> 0               = (w0 * 2**170 + x) ** 2 + a - (w1 * 2**170 + y) mod p

    f(x, y) = (w0 * 2**170 + x) ** 2 + a - (w1 * 2**170 + y) mod p

We can now use the Coppersmith method to recover the internal state using only two successive outputs.

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer zeroes of univariate or bivariate polynomials modulo a given integer. The method uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to find a polynomial that has the same zeroes as the target polynomial but smaller coefficients.

source: wikipedia.org

paper : iacr.org

Solve script

# https://github.com/defund/coppersmith
load("coppersmith.sage")
from Crypto.Util.number import getStrongPrime
import random, sys, os


def recover_ver1(w0, w1):
    x, y = PolynomialRing(GF(p), names="x, y").gens()
    t = 170
    pol = (w0 * 2**t + x) ** 2 + a - (w1 * 2**t + y)
    rs = small_roots(pol, [2**t, 2**t])

    x, y = rs[0]

    v0 = int(w0 * 2**t + x)
    v1 = int(w1 * 2**t + y)
    print("found", v0 >> 170, v1 >> 170)

    assert (v0**2 + a) % p == v1
    return v0, v1


class RNG:
    def __init__(self, p, a, state):
        self.p = p
        self.a = a
        self.state = state

    def _next(self):
        self.state = (self.state**2 + self.a) % self.p
        return self.state >> 170


import pwn

r = pwn.process(['python3', 'ladybug.py'])
# r = pwn.remote("34.244.254.13", int(50003)) # force conversion back to `int` because sage converts
                                              # it to an `Integer` and pwntools doesn't like that

r.recvuntil(b"Here are the public parameters:\n")
p = int(r.recvline().split(b"=")[1], 16)
a = int(r.recvline().split(b"=")[1], 16)
print(f"{p=}\n{a=}")


r.recvuntil(b"Place your code:")
r.sendline(b"1")

r.recvuntil(b"Place your code:")
r.sendline(b"0")

r.recvuntil(b"incorrect, the code was: ")
w0 = int(r.recvline(), 16)

r.recvuntil(b"Place your code:")
r.sendline(b"1")

r.recvuntil(b"Place your code:")
r.sendline(b"0")

r.recvuntil(b"incorrect, the code was: ")
w1 = int(r.recvline(), 16)
print(f"{w0=}\n{w1=}")

v0, v1 = recover_ver1(w0, w1)
print(f"{v0=}\n{v1=}")

rng = RNG(p, a, v1)


pwn.context.log_level = "DEBUG"
wallet = 2
while True:
    r.recvuntil(b"Place your code:")
    r.sendline(str(wallet).encode())

    wallet += wallet

    r.recvuntil(b"Place your code:")
    r.sendline(str(rng._next()).encode())

"""
$ sage solve_ladybug.sage
Warning: _curses.error: setupterm: could not find terminfo database

Terminal features will not be available.  Consider setting TERM variable to your current terminal name (or xterm).
[x] Starting local process '/usr/bin/python3'
[+] Starting local process '/usr/bin/python3': pid 12931
p=12771292853306526506787788802340370258039409172428666046049257006083628377988862516348073006911006392580677143571944081110213301732849858459169257704234461
a=9621293285970202238494936054757102668784792487656806225178547117477705481283836518047881821136975976100661711831223469017631289909739275582762479686388525
w0=4298212147235055985990196656744326163844736213018715123392002284809939325576611980514307572277766439325
w1=1338286151676289990634361351744970333939535747610667459781390041682876403342628559136791796081165467956
found 4298212147235055985990196656744326163844736213018715123392002284809939325576611980514307572277766439325 1338286151676289990634361351744970333939535747610667459781390041682876403342628559136791796081165467956
v0=6432608348958320936847286025861069814775702819493104930548698831621815212545075873503556571706211700204059990551644064114492791034237903970430959024850700
v1=2002849179537583010181219660053107796930513959674018967329887200307020741746687036190556672361624519829399124618229726717959710093614790532650415742777495
[DEBUG] Sent 0x2 bytes:
    b'2\n'
[DEBUG] Received 0x11 bytes:
    b'Place your code: '
[DEBUG] Sent 0x68 bytes:
    b'6237838323068092919278024011688669693547822960552905052009175484733210725364871613866603506790259067479\n'
[DEBUG] Received 0xa7 bytes:
    b'You got it right, the code was: 0x2c8fa204a57bafa339ce1b9d0c81bc27df5c295329fe462b0d9e07e47fab2448e4cd9adcefbd48a9558a57\n'
    b'\n'
    b'Your current wallet is 4$.\n'
    b'\n'
    b'Place your code: '

[...]

[DEBUG] Sent 0x1b bytes:
    b'77371252455336267181195264\n'
[DEBUG] Received 0x11 bytes:
    b'Place your code: '
[DEBUG] Sent 0x68 bytes:
    b'5428385041472041766883739904160605946823744693825724284686431407339846067465886091772817435238610610871\n'
[DEBUG] Received 0xee bytes:
    b'You got it right, the code was: 0x26c7523074d08696aa382a01ac862a55e9fabb6f1888ac64d9144360f95dbda339d0fa1712e8370ab5aab7\n'
    b'\n'
    b'Your current wallet is 154742504910672534362390528$.\n'
    b'\n'
    b'Welcome! You have access to secret house: PPC2023{debug_flag}\n'
0
[*] Process '/usr/bin/python3' stopped with exit code 0 (pid 13057)
"""