blog > SECCON CTF 2022 Crypto Writeups
2022 Nov 13ctfcrypto

# SECCON CTF 2022 Crypto Writeups

Changelog (last updated 2022-11-20)

Update 2022-11-20: Added inequality-CVP solution for this_is_not_lsb along with some typos.

## janken vs kurenaif

By theoremoon

Do you know about the crypto witch? And about a her special cast too?

nc janken-vs-kurenaif.seccon.games 8080

Attachments: server.py

17 solves, 221 points

Challenge problem.py
PYTHON
import osimport signalimport randomimport secrets
FLAG = os.getenv("FLAG", "fake{cast a special spell}")

def janken(a, b):    return (a - b + 3) % 3

signal.alarm(1000)print("kurenaif: Hi, I'm a crypto witch. Let's a spell battle with me.")
witch_spell = secrets.token_hex(16)witch_rand = random.Random()witch_rand.seed(int(witch_spell, 16))print(f"kurenaif: My spell is {witch_spell}. What about your spell?")
your_spell = input("your spell: ")your_random = random.Random()your_random.seed(int(your_spell, 16))
for _ in range(666):    witch_hand = witch_rand.randint(0, 2)    your_hand = your_random.randint(0, 2)
if janken(your_hand, witch_hand) != 1:        print("kurenaif: Could you come here the day before yesterday?")        quit()
print("kurenaif: Amazing! Your spell is very powerful!!")print(f"kurenaif: OK. The flag is here. {FLAG}")

The challenge server seeds a python PRNG witch_rand and publishes the key, then asks for a user seed for another PRNG your_random. The two PRNGs then play rock-paper-scissors against each other. Our PRNG needs to play winning moves 666 times in a row to get the flag.

Since we know the witch_rand seed, first predict the 666 witch_rand results by making a copy of the PRNG on our local machine and then calculate what are the winning hands that your_random needs to produce.

Simulate PRNG locally
PYTHON
import randomfrom pwn import *
context.log_level = "error"
r = remote("janken-vs-kurenaif.seccon.games", 8080)r.recvuntil(b"My spell is ")witch_spell = r.recvuntil(b".")[:-1].decode()
witch_rand = random.Random()witch_rand.seed(int(witch_spell, 16))
witch_hands = []your_hands = []
for _ in range(666):    witch_hand = witch_rand.randint(0, 2)    your_hand = (witch_hand + 1) % 3
witch_hands.append(witch_hand)    your_hands.append(your_hand)
print(f"{witch_hands[:10] = }")print(f"{your_hands[:10]  = }")
OUTPUT
witch_hands[:10] = [2, 1, 1, 2, 1, 0, 1, 2, 0, 2]your_hands[:10]  = [0, 2, 2, 0, 2, 1, 2, 0, 1, 0]

To understand more about how the rock-paper-scissors plays are generated, we can read the CPython random.py source code. The call stack looks like:

Random.getrandbits(2) generates a 32 bit output from the PRNG and only returns the highest 2 bits, while Random._randbelow_with_getrandbits(3) will keep generating until Random.getrandbits(2) returns something strictly less than 3. To produce the winning your_random hands, we want to find a seed that will generate the right values in the highest 2 bits of each PRNG output.

Since we know our desired PRNG outputs, a symbolic Mersenne Twister cracker can be used to obtain a valid PRNG state that produces these outputs. Modifications to this reference implementation were made to recover the PRNG state immediately after seeding instead of the state after the outputs are generated.

Solve for PRNG state
PYTHON
# !wget https://raw.githubusercontent.com/icemonster/symbolic_mersenne_cracker/main/main.py -O untwister.pyfrom untwister import Untwister as _Untwisterimport logginglogging.disable()
# Superclass Untwister to obtain PRNG state after seeding# instead of PRNG state after outputs generatedclass Untwister(_Untwister):    def __init__(self):        super().__init__()        self.first_MT = self.MT
# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L201        # Index is 624 after seeding        self.index = 624
def get_random(self):        # https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L232        # First MT state is set to 0x80000000 after seeding        self.solver.add(self.first_MT[0] == 0x80000000)
print(self.solver.check())        model = self.solver.model()        state = [            model[x].as_long() if model[x] is not None else 0            for x in self.first_MT        ]
result_state = (3, tuple(state+[624]), None)        rand = random.Random()        rand.setstate(result_state)        return rand
ut = Untwister()for your_hand in your_hands:    res = bin(your_hand)[2:].zfill(2) + "?" * 30    ut.submit(res)ut_rand = ut.get_random()ut_rand_state = ut_rand.getstate()[1][:-1]
# sanity checkfor your_hand in your_hands:    assert your_hand == ut_rand.randint(0, 2)
OUTPUT
sat

Though we have a valid PRNG state that can generate winning outputs, we need to send the server a seed value that will create this state. We can study how PRNG seeding works again with some source code review:

For seeds that are python long arbitrary precision integers, the C function init_by_array(init_key) accepts the long represented as an array of 32-bit unsigned integers init_key with the least significant 32-bit integer coming first, then loops through them with some XORs and multiplications to create the initial PRNG state. We can re-implement init_by_array(init_key) in python and use z3 to solve for a valid init_key that is 624 32-bit unsigned integers long and produces the desired PRNG state. Finally we can submit this seed to the challenge server to get flag.

Solve for PRNG seed
PYTHON
from z3 import *
prng_N = 624
def u32(x):    return x & 0xffffffff
# Note that LShR is used instead of ">>" operator# unsigned 32 bit integers use logical bitshift, not arithmetic bitshift.
# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L186def init_genrand(s):    mt = [0 for _ in range(prng_N)]
mt[0] = BitVecVal(s, 32)    mti = 1    while mti < prng_N:        mt[mti] = u32(            1812433253 * (mt[mti-1] ^ LShR(mt[mti-1], 30)) + mti            # 1812433253 * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti        )        mti += 1    return mt, mti
# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L209def init_by_array(init_key):    key_length = len(init_key)    mt, mti = init_genrand(19650218)
i, j = 1, 0    k = prng_N if prng_N > key_length else key_length    while k:        mt[i] = u32(            (mt[i] ^ ((mt[i-1] ^ LShR(mt[i-1], 30)) * 1664525)) + init_key[j] + j        )        i, j = i + 1, j + 1        if i >= prng_N:            mt[0] = mt[prng_N-1]            i = 1        if j >= key_length:            j = 0        k -= 1
k = prng_N - 1    while k:        mt[i] = u32(            (mt[i] ^ ((mt[i-1] ^ LShR(mt[i-1], 30)) * 1566083941)) - i        )        i += 1        if i >= prng_N:            mt[0] = mt[prng_N-1]            i = 1        k -= 1
mt[0] = 0x80000000;
return mt
seed_vars = [    BitVec(f"seed_{i}", 32) for i in range(624)]seed_rand_state = init_by_array(seed_vars)
s = Solver()for a, b in zip(seed_rand_state, ut_rand_state):    s.add(a == b)print(s.check())
model = s.model()seed_init_key = [    model[x].as_long() if model[x] is not None else 0    for x in seed_vars]print(f"{seed_init_key[:10] = }")
OUTPUT
satseed_init_key[:10] = [2785066542, 4109823319, 1943818831, 195508595, 4046365112, 359652855, 2071527069, 3612262978, 2265693527, 3400945710]
Convert seed and claim flag
PYTHON
seed_rand_seed = sum([x * (2 ** (idx * 32))for idx, x in enumerate(seed_init_key)])print("seed_rand_seed =", str(seed_rand_seed)[:50], "...")
seed_rand = random.Random()seed_rand.seed(seed_rand_seed)
# sanity checkassert seed_rand.getstate()[1][:-1] == ut_rand_statefor your_hand in your_hands:    assert your_hand == seed_rand.randint(0, 2)
r.sendline(f"{hex(seed_rand_seed)[2:]}".encode())print(r.recvall().decode())
OUTPUT
seed_rand_seed = 47391526757246540556852465962283917972958287802376 ... What about your spell?your spell: kurenaif: Amazing! Your spell is very powerful!!kurenaif: OK. The flag is here. SECCON{https://youtu.be/h0GSFxoRhrc}

## witches_symmetric_exam

By kurenaif

crypto witch made a exam. The exam has to communicate with witch and saying secret spell correctly. Have fun ;)

nc witches-symmetric-exam.seccon.games 8080

Attachments: problem.py

22 solves, 197 points

Challenge problem.py
PYTHON
from Crypto.Cipher import AESfrom Crypto.Random import get_random_bytesfrom Crypto.Util.Padding import pad, unpadfrom flag import flag, secret_spell
key = get_random_bytes(16)nonce = get_random_bytes(16)

def encrypt():    data = secret_spell    gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)    gcm_ciphertext, gcm_tag = gcm_cipher.encrypt_and_digest(data)
ofb_input = pad(gcm_tag + gcm_cipher.nonce + gcm_ciphertext, 16)
ofb_iv = get_random_bytes(16)    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)    ciphertext = ofb_cipher.encrypt(ofb_input)    return ofb_iv + ciphertext

def decrypt(data):    ofb_iv = data[:16]    ofb_ciphertext = data[16:]    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)
try:        m = ofb_cipher.decrypt(ofb_ciphertext)        temp = unpad(m, 16)    except:        return b"ofb error"
try:        gcm_tag = temp[:16]        gcm_nonce = temp[16:32]        gcm_ciphertext = temp[32:]        gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=gcm_nonce)
plaintext = gcm_cipher.decrypt_and_verify(gcm_ciphertext, gcm_tag)    except:        return b"gcm error"
if b"give me key" == plaintext:        your_spell = input("ok, please say secret spell:").encode()        if your_spell == secret_spell:            return flag        else:            return b"Try Harder"
return b"ok"

print(f"ciphertext: {encrypt().hex()}")while True:    c = input("ciphertext: ")    print(decrypt(bytes.fromhex(c)))

The server uses two AES-OFB and AES-GCM ciphers in series with the same key to encrypt some secret text and users can query decryption on some data. Different output is returned if padding errors or GCM tag verification errors are found, which points towards an AES padding oracle.

Get parameters
PYTHON
from pwn import *
context.log_level = "error"
r = remote("witches-symmetric-exam.seccon.games", 8080)r.recvuntil(b"ciphertext: ")enc = bytes.fromhex(r.recvline().decode())print(f"{len(enc)  = }")print(f"{enc.hex() = }")
OUTPUT
len(enc)  = 80enc.hex() = 'eba5836c9b1b7892a39cd7031fd5d89d0f8b66e0e00447aec9d9ffcceaa11b6a3b95fc35580fc578b90b186a8948391beca9c91e538a8d4d3d53eb3dd8404c27f2b8eafa5add251eb1bfd41a32aa38fd'

AES-OFB decrypts one block of ciphertext ct with initiation vector iv by doing pt = unpad(enc<key>(iv) ^ ct) and prouduces different results if unpad succeeds or fails. This is effectively an AES-ECB encryption oracle as we can adjust the tail bytes of ct until unpad succeeds, thus finding enc<key>(iv) = expected_padding ^ ct.

Decryption oracle routines
PYTHON
def bxor(*args):    if len(args) == 1:        return args[0]    a, b = args[0], args[1:]    return bytes([i ^ j for i, j in zip(a, bxor(*b))])
def query(xs):    r.sendline("\n".join([x.hex() for x in xs]).encode())    ress = []    for _ in xs:        r.recvuntil(b"ciphertext: ")        res = r.recv(5).strip().decode()        if "b'ofb" in res:            ress.append("pad")        elif "b'gcm" in res:            ress.append("gcm")        elif "o', p" in res:            ress.append("spell")        elif "b'ok'" in res:            ress.append("ok")        else:            raise ValueError(res)    return ress
def leak_enc(pln):    enc = [0 for _ in range(16)]
for pos in range(16):        print(".", end="", flush=True)        expected_padding = ([0] * 16 + [pos+1] * (pos+1))[-16:]
found = []        probe = [0] * 16
xs = []        for i in range(256):            probe[15-pos] = i            try_block_ofb = pln + bxor(enc, expected_padding, probe)            xs.append(try_block_ofb)        ress = query(xs)        for i, res in enumerate(ress):            if res == "gcm":                found.append(i)        if len(found) != 1:            raise ValueError("???", pos, found)
enc[15-pos] = found[0]    print()
return bytes(enc)

To decrypt the OFB phase, leak enc<key>(iv), then enc<key>(enc<key>(iv)) and so on to get the whole AES-OFB cipher stream that the plaintext is XOR-ed with. We can verify that the decryption is correct by checking for valid padding on gcm_enc.

Decrypt OFB
PYTHON
from Crypto.Util.Padding import unpad
ofb_iv = enc[:16]ofb_enc = enc[16:]
print(f"{ofb_iv.hex()     = }")
ofb_stream = ofb_ivfor block in range(4):    ofb_stream += leak_enc(ofb_stream[-16:])ofb_stream = ofb_stream[16:]
print(f"{ofb_stream.hex() = }")
ofb_dec = bxor(ofb_enc, ofb_stream)gcm_tag, gcm_nonce, gcm_enc = ofb_dec[:16], ofb_dec[16:32], unpad(ofb_dec[32:], 16)
print(f"{gcm_tag.hex()    = }")print(f"{gcm_nonce.hex()  = }")print(f"{gcm_enc.hex()    = }")
OUTPUT
ofb_iv.hex()     = 'eba5836c9b1b7892a39cd7031fd5d89d'................................................................ofb_stream.hex() = '23fdad43a2f057a7d2b7796e90bc05c2e60823306dfb1f139117cc63738a05f2c6e2511b07e4ed91f2841066f453217886601ef80387309bb9b7dc123aa230f5'gcm_tag.hex()    = '2c76cba342f410091b6e86a27a1d1ea8'gcm_nonce.hex()  = 'dd9ddf0535f4da6b281cd409fac23ce9'gcm_enc.hex()    = '2a4b9805546e60dccfd7fb5b2c136d5f74d8f402595a1585'

It turns out that this encryption oracle is also sufficient to break AES-GCM encryption and decryption because internally these operations only require AES-ECB encryption!

We can derive the parameters h0 and j0 of the AES-GCM cipher using the encryption oracle. These parameters are used to calculate the nonce for the internal AES-CTR cipher stream and are also used for the AES-GCM tag generation. Referring to pycryptodome source helped a lot for this step.

GCM parameters
PYTHON
from Crypto.Util.number import long_to_bytes, bytes_to_longfrom Crypto.Cipher._mode_gcm import _GHASH as GHASH, _ghash_clmul as ghash_c
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L223-L226h0 = leak_enc(b"\x00" * 16)print(f"{h0.hex() = }")
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L232-L236nonce = gcm_noncefill = (16 - (len(nonce) % 16)) % 16 + 8ghash_in = (nonce + b'\x00' * fill + long_to_bytes(8 * len(nonce), 8))j0 = GHASH(h0, ghash_c).update(ghash_in).digest()print(f"{j0.hex() = }")
OUTPUT
................h0.hex() = 'dee52a0c81a9ed9e2645c2453ea2131b'j0.hex() = '991ef958aa7192caa6b5b2f7754743f5'

We can obtain the internal AES-CTR cipher stream by simulating the counter increment and leaking enc<key>(j0+1) and enc<key>(j0+2). We can then decrypt the secret_spell string by XOR-ing with this cipher stream.

Decrypt GCM
PYTHON
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L239-L245# nonce_ctr = j0[:12]# iv_ctr = (bytes_to_long(j0) + 1) & 0xFFFFFFFF# nonce_iv_bytes = nonce_ctr + bytes.fromhex(hex(iv_ctr)[2:].zfill(8))block_one_ctr = bytes.fromhex(hex(int(j0.hex(), 16) + 1)[2:])block_two_ctr = bytes.fromhex(hex(int(j0.hex(), 16) + 2)[2:])
gcm_stream = leak_enc(block_one_ctr) + leak_enc(block_two_ctr)gcm_pln = bxor(gcm_stream, gcm_enc)secret_spell = gcm_plnprint(f"{secret_spell = }")
OUTPUT
................................secret_spell = b'decrypt_all!!277260221!!'

Finally to claim the flag we need to encrypt and sign the message "give me key". We can reuse the previous nonces and IVs which means the cipher streams stay the same, so encryption will just involve XOR-ing the message with streams in the right order. A valid tag can be generated by processing the GHASH locally and XOR-ing with enc<key>(j0). This lets us claim the flag.

Claim flag
PYTHON
from Crypto.Util.Padding import pad
signer = GHASH(h0, ghash_c)token_dec = b"give me key"
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L372-L379# > encrypt and digest > encrypttoken_enc = bxor(token_dec, gcm_stream)msg_len = len(token_enc)# signer.update(token_enc) # defer to later for block alignment
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L459-L462# > encrypt and digest > digestsigner.update(token_enc + b"\x00" * (16 - msg_len))signer.update(long_to_bytes(8 * 0, 8) + long_to_bytes(8 * msg_len, 8))tag_dec = signer.digest()
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L465# > encrypt and digest > digest > self._tag_cipher.encryptj0_stream = leak_enc(j0)tag_enc = bxor(tag_dec, j0_stream)
print(f"{tag_enc.hex() = }")
r.sendline(payload.hex().encode())r.sendline(secret_spell)flag = r.recvuntil(b"}").decode().strip()print(flag)
OUTPUT
................tag_enc.hex() = '76c2626da50248e3cc8dea847f7dc442'payload.hex() = 'eba5836c9b1b7892a39cd7031fd5d89d553fcf2e07f21f441e3a93eaefc1c1803b95fc35580fc578b90b186a8948391befa5dc090a979c32375afe63f156247d'error'ciphertext: ok, please say secret spell:b'SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}

## insufficient

By Xornet

SUGOI SECRET SHARING SCHEME with insufficient shares

Attachments: dist.tar.gz

33 solves, 164 points

Challenge problem.py
PYTHON
from random import randintfrom Crypto.Util.number import getPrime, bytes_to_longfrom secret import FLAG

# f(x,y,z) = a1*x + a2*x^2 + a3*x^3#          + b1*y + b2*y^2 + b3*y^3#          + c*z + s mod pdef calc_f(coeffs, x, y, z, p):    ret = 0    ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]    ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]    ret += z * coeffs[6]    ret += coeffs[7]
return ret % p

p = getPrime(512)

# [a1, a2, a3, b1, b2, b3, c, s]coeffs = [randint(0, 2**128) for _ in range(8)]
key = 0for coeff in coeffs:    key <<= 128    key ^= coeff
cipher_text = bytes_to_long(FLAG) ^ keyprint(cipher_text)
shares = []for _ in range(4):    x = randint(0, p)    y = randint(0, p)    z = randint(0, 2**128)
w = calc_f(coeffs, x, y, z, p)    packed_share = ((x,y), w)    shares.append(packed_share)
print(p)print(shares)

128-bit coeffs $a_1$ to $a_3$ / $b_1$ to $b_3$ / $c$ / $s$ are generated on the server and are kept secret and are needed to recover the flag. A 512-bit prime $p$ is published and 4 shares are calculated where $x, y < p$ and $z < 2^{128}$. We are given $x$, $y$ and the result of calc_f $w$ for each share.

PYTHON
# challenge problem.py
# f(x,y,z) = a1*x + a2*x^2 + a3*x^3#          + b1*y + b2*y^2 + b3*y^3#          + c*z + s mod pdef calc_f(coeffs, x, y, z, p):    ret = 0    ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]    ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]    ret += z * coeffs[6]    ret += coeffs[7]
return ret % p
Expand parameters
PYTHON
ct = 115139400156559163067983730101733651044517302092738415230761576068368627143021367186957088381449359016008152481518188727055259259438853550911696408473202582626669824350180493062986420292176306828782792330214492239993109523633165689080824380627230327245751549253757852668981573771168683865251547238022125676591p = 8200291410122039687250292442109878676753589397818032770561720051299309477271228768886216860911120846659270343793701939593802424969673253182414886645533851shares = [    ((6086926015098867242735222866983726204461220951103360009696454681019399690511733951569533187634005519163004817081362909518890288475814570715924211956186561, 180544606207615749673679003486920396349643373592065733048594170223181990080540522443341611038923128944258091068067227964575144365802736335177084131200721), 358596622670209028757821020375422468786000283337112662091012759053764980353656144756495576189654506534688021724133853284750462313294554223173599545023200),    ((1386358358863317578119640490115732907593775890728347365516358215967843845703994105707232051642221482563536659365469364255206757315665759154598917141827974, 4056544903690651970564657683645824587566358589111269611317182863269566520886711060942678307985575546879523617067909465838713131842847785502375410189119098), 7987498083862441578197078091675653094495875014017487290616050579537158854070043336559221536943501617079375762641137734054184462590583526782938983347248670),    ((656537687734778409273502324331707970697362050871244803755641285452940994603617400730910858122669191686993796208644537023001462145198921682454359699163851, 7168506530157948082373212337047037955782714850395068869680326068416218527056283262697351993204957096383236610668826321537260018440150283660410281255549702), 1047085825033120721880384312942308021912742666478829834943737959325181775143075576517355925753610902886229818331095595005460339857743811544053574078662507),    ((5258797924027715460925283932681628978641108698338452367217155856384763787158334845391544834908979711067046042420593321638221507208614929195171831766268954, 4425317882205634741873988391516678208287005927456949928854593454650522868601946818897817646576217811686765487183061848994765729348913592238613989095356071), 866086803634294445156445022661535120113351818468169243952864826652249446764789342099913962106165135623940932785868082548653702309009757035399759882130676)]
F = Zmod(p)
share_xxxyyy = [    [ ZZ(i) for i in [F(x), F(x) ^ 2, F(x) ^ 3, F(y), F(y) ^ 2, F(y) ^ 3]]    for (x, y), _ in shares]share_w = [w for _, w in shares]

Since we know $x$ and $y$, we can calculate the corresponding $x^2$/$x^3$/$y^2$/$y^3$ values and try to model this as a closest vector problem:

$\mathbf{B} = \begin{bmatrix} x_0 & \cdots & x_3 & 2^{128} & \\ \vdots & \ddots & \vdots & & \ddots \\ y^3_0 & \cdots & y^3_3 & & & 2^{128} \\ p & & \\ & \ddots & \\ & & p \\ \end{bmatrix} \\[8pt] \textbf{x} = \begin{pmatrix} a_1 & \cdots & b_3 & - \lfloor \frac{w_0}{p} \rfloor & \cdots & - \lfloor \frac{w_3}{p} \rfloor \\ \end{pmatrix} \\[4pt] \textbf{u} = \begin{pmatrix} w_0 - cz_0 - s & \cdots & w_3 - cz_3 - s & 2^{128} a_1 & \cdots & 2^{128} b_3 \\ \end{pmatrix} \\[4pt] \textbf{t} = \begin{pmatrix} w_0 & \cdots & w_3 & 2^{255} & \cdots & 2^{255} \\ \end{pmatrix} \\[4pt] \mathbf{x} \mathbf{B} = \textbf{u} \approx \textbf{t}$

A factor of $2^{128}$ is added to the part of the lattice generating $a_1$ to $b_3$ to make their residuals in the same order of magnitude as the expected 256-bit residuals of $cz+s$.

For a closest vector $\textbf{u}$ generated by $\mathbf{B}$ to reference vector $\textbf{t}$, $\textbf{u}$ differs from $\textbf{t}$ in $w_0$ to $w_3$ by its $cz+s$ term, while the later terms will be near to $2^{128} a_1$ to $2^{128} b_3$. $c$ and $s$ can then be recovered by taking the GCD of differences between residues, obtaining all the data required to recover the flag.

Solve CVP
PYTHON
# https://jgeralnik.github.io/writeups/2021/08/12/Lattices/def closest_vector(B, target):    # Babai's Nearest Plane algorithm    M = B.LLL()    G = M.gram_schmidt()[0]    small = target    for _ in range(1):        for i in reversed(range(M.nrows())):            c = ((small * G[i]) / (G[i] * G[i])).round()            small -= M[i] * c    return target - small
r, c = 11, 11
two_127 = 2 ^ 127two_128 = 2 ^ 128large = 2 ^ 1024
mat = [    [0 for _ in range(c)]    for _ in range(r)]vec = [ 0 for _ in range(c) ]
for coeff_i in range(6):    for share_i in range(4):        mat[coeff_i][share_i] = share_xxxyyy[share_i][coeff_i]    mat[coeff_i][4 + coeff_i] = two_128    vec[coeff_i] = two_127 * two_128
for share_i in range(4):    mat[6 + share_i][share_i] = p    mat[10][share_i] = - shares[share_i][1]
mat[10][10] = largevec[10] = large
mat = Matrix(ZZ, mat)vec = vector(vec)
cv = closest_vector(mat, vec)assert cv[10] == large
for idx, cvi in enumerate(cv):    print(f"cv[{idx}] = {cvi}")
OUTPUT
cv[0] = -73127182509659574936304130186390232855613411712618127387302114362808513444038cv[1] = -21323554641234012731873431347941675841849210679985598800027345190229736374864cv[2] = -95332596761823814479686618419564498660798012792472282519243854651578178909353cv[3] = -65202559187559307765157064732030011588113460469631415668829640873318085305823cv[4] = 108872274582080884429104542718114951764799087578511053878950064648738360524800cv[5] = 51808446279407138673963965459500483574659336067433398358542736292199876526080cv[6] = 46874495483872404296318603859111203660545082957551217054277798423995804024832cv[7] = 114770789402085722865307263932237123446182777168313585667126867879815270105088cv[8] = 51217024666795342916098068957979173083931580539085821138892284370538977034240cv[9] = 9527304801756674193386489592332566492258743922045146824371698689838183088128cv[10] = 179769313486231590772930519078902473361797[...]10684586298239947245938479716304835356329624224137216
Calculate coeffs
PYTHON
coeffs_6 = [    i // two_128    for i in cv[4:10]]
czs = [    (w - sum([a * b for a, b in zip(xxxyyyy, coeffs_6)])) % p    for xxxyyyy, w in zip(share_xxxyyy, share_w)]c6 = gcd(czs[1] - czs[0], czs[2] - czs[0])c7 = czs[0] % c6
coeffs = [*coeffs_6, c6, c7]for idx, coeff_i in enumerate(coeffs):    print(f"coeffs[{idx}] = {coeff_i}")
OUTPUT
coeffs[0] = 319946859331022505606006682830489529550coeffs[1] = 152251339815807627609342474617581741055coeffs[2] = 137751761597342098624908697775689190697coeffs[3] = 337281036453915579622200616302875159873coeffs[4] = 150513307904359194457545638585602396040coeffs[5] = 27998232432567560780529247469815955088coeffs[6] = 285109170934241472003856820431690507519coeffs[7] = 86246982746739283466217140132251503442
Claim flag
PYTHON
key = 0for coeff in coeffs:    key <<= 128    key = key ^^ coeffflag = ct ^^ key
bytes.fromhex(hex(flag)[2:])
OUTPUT
b'SECCON{Unfortunately_I_could_not_come_up_with_a_more_difficult_problem_than_last_year_sorry...-6fc18307d3ed2e7673a249abc2e0e22c}'

## this_is_not_lsb

By kurenaif

Tired of difficult problems? Ok, I give you a simple LSB Padding Oracle problem. Ah, my magic has exploded... Sorry

nc this-is-not-lsb.seccon.games 8080

Attachments: problem.py

34 solves, 162 points

Challenge problem.py
PYTHON
from Crypto.Util.number import *from flag import flag
p = getStrongPrime(512)q = getStrongPrime(512)e = 65537n = p * qphi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(f"n = {n}")print(f"e = {e}")print(f"flag_length = {flag.bit_length()}")
# Oops! encrypt without padding!c = pow(flag, e, n)print(f"c = {c}")
return (m >> (padding_pos - 8)) == 0xFF

while True:    c = int(input("c = "))    print(check_padding(c))

The server gives us a RSA public key parameters and the encryption c of flag without padding, and a decryption oracle which reveals if the decryption is between 0b0011111111000... and 0b0011111111111...; let us call this $\text{dec}_L$ and $\text{dec}_U$. Because of RSA homomorpism where multiplication of ciphertexts is equivalent to multiplication plaintexts, we can make queries in the form $c \cdot k^e \bmod n$ which will decrypt to $\text{flag} \cdot k \bmod n$ and tells us if this decryption result is in the oracle's interval.

From the the SECCON{... flag format and the server output revealing that the flag is 439 bits long, we can assume these are the top bytes of the flag and pad the rest to narrow down the interval of possible flag values; let us call these bounds $\text{flag}_L$ and $\text{flag}_U$.

We then binary search on the possible values of $\text{flag}$ by calculating a mid-point $\text{flag}_M = \frac{\text{flag}_L + \text{flag}_U}{2}$ and querying the decryption of $c \cdot \lfloor \frac{\text{dec}_L}{\text{flag}_M} \rfloor ^e$. This will decrypt to $\text{flag} \cdot \lfloor \frac{\text{dec}_L}{\text{flag}_M} \rfloor$1 and from the oracle output we can gain useful information about the value of $\text{flag}$:2

• When the oracle returns True, $\text{flag} \cdot \lfloor \frac{\text{dec}_L}{\text{flag}_M} \rfloor > \text{dec}_L$ and therefore $\text{flag} > \text{flag}_M$
• When the oracle returns False, $\text{flag} \cdot \lfloor \frac{\text{dec}_L}{\text{flag}_M} \rfloor < \text{dec}_L$ and therefore $\text{flag} < \text{flag}_M$

This also requires $\text{flag} \cdot \lfloor \frac{\text{dec}_L}{\text{flag}_M} \rfloor < \text{dec}_U$ but using known flag prefix this will always be true. A linear search for a good starting $\text{flag}_M$ can be done if we don't have known flag prefix.

With this information, we can narrow down the range of possible $\text{flag}$ after each query, essentially binary searching for the flag.

Exploit code
PYTHON
from pwn import *
context.log_level = "error"
# ====== Get parameters ======
r = remote("this-is-not-lsb.seccon.games", 8080)r.recvuntil(b"n = ")n = int(r.recvline().strip().decode())r.recvuntil(b"e = ")e = int(r.recvline().strip().decode())r.recvuntil(b"flag_length = ")flag_length = int(r.recvline().strip().decode())r.recvuntil(b"c = ")c = int(r.recvline().strip().decode())
print(f"{n           = }")print(f"{e           = }")print(f"{flag_length = }")print(f"{c           = }")
def query(k):    y = (pow(k, e, n) * c) % n    r.recvuntil(b"c = ")    r.sendline(f"{y}".encode())    res = r.recvline().decode().strip()    if res == "True":        return True    elif res == "False":        return False    else:        raise ValueError(res)
dec_lb = int("0011111111".ljust(n.bit_length(), "0"), 2)dec_ub = int("0011111111".ljust(n.bit_length(), "1"), 2)flag_lb = int((b"SECCON{"+ b"\x00" * 48).hex(), 16)flag_ub = int((b"SECCON{"+ b"\xff" * 48).hex(), 16)
# ====== Binary search ======
while flag_ub - flag_lb > 10:    flag_md = (flag_lb + flag_ub) // 2    coef = dec_lb // flag_md    if query(coef):        print("-", end="", flush=True)        flag_lb = flag_md    else:        print("+", end="", flush=True)        flag_ub = flag_mdprint()flag = bytes.fromhex(hex(flag_lb)[2:])print(f"{flag = }")
OUTPUT
n           = 13843646552185108127[...]578679382305964423040143e           = 65537flag_length = 439c           = 83362066469299840911[...]29224401955722779580980+-+-+---+--++-+-+-++--+++-++++--++[...]-++--+++--++-+-++-++++-+----flag = b'SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!w'

### Alternative solution with Inequality-CVP

Consider what happens if several $k$ are randomly generated and $c \cdot k^e \bmod n$ is queried until the oracle returns True. This means that we have some found $k_i$ where $\text{dec}_L < \text{flag} \cdot k_i \bmod n < \text{dec}_U$, where after some rearranging we have $\text{dec}_L < \text{flag} \cdot k_i - a_i \cdot n < \text{dec}_U$. With enough random $k_i$, we can model this as a closest vector problem for solving inequalities.

$\mathbf{B} = \begin{bmatrix} k_0 & \cdots & k_{49} & z \\ n \\ & \ddots \\ & & n \\ \end{bmatrix} \\[8pt] \textbf{x} = \begin{pmatrix} \text{flag} & -a_0 & \cdots & -a_{49} \\ \end{pmatrix} \\[4pt] \textbf{u} = \begin{pmatrix} \text{flag} \cdot k_0 - a_0 \cdot n & \cdots & \text{flag} \cdot k_{49} - a_{49} \cdot n & z \cdot \text{flag} \\ \end{pmatrix} \\[4pt] \textbf{t} = \begin{pmatrix} \frac{\text{dec}_L + \text{dec}_U}{2} & \cdots & \frac{\text{dec}_L + \text{dec}_U}{2} & z \cdot \frac{\text{flag}_L + \text{flag}_U}{2} \\ \end{pmatrix} \\[4pt] \mathbf{x} \mathbf{B} = \textbf{u} \approx \textbf{t}$

We might not know the exact value of $c \cdot k \bmod n$, but guessing that they are around $\frac{\text{dec}_L + \text{dec}_U}{2}$ is sufficient to help solve for $\text{flag}$. We also introduce a scaling term $z = \lfloor \frac{\text{dec}_U - \text{dec}_L}{\text{flag}_U - \text{flag}_L} \rfloor$ which will ensure the residues of the $| z \cdot \text{flag} - z \cdot \frac{\text{flag}_L + \text{flag}_U}{2} |$ term will be in the same magnitude as the resides from other terms. For more information about this trick, take a look at rkm0959's work on inequality CVP.

Since 10 bytes are fixed by the padding oracle, a random $k$ has a $1$ in $2^{10}$ chance of its decryption falling in the appropriate range for the oracle to return True, which means to obtain $50$ valid $k$ we can expect it to take $50 \cdot 2^{10} = 51 \, 200$ queries which can be done within the time limit.

Exploit code
SAGE
from pwn import *
# https://jgeralnik.github.io/writeups/2021/08/12/Lattices/def closest_vector(B, target):    # Babai's Nearest Plane algorithm    M = B.LLL()    G = M.gram_schmidt()[0]    small = target    for _ in range(1):        for i in reversed(range(M.nrows())):            c = ((small * G[i]) / (G[i] * G[i])).round()            small -= M[i] * c    return target - small
context.log_level = "error"
# ====== Get parameters ======
r = remote("this-is-not-lsb.seccon.games", 8080)r.recvuntil(b"n = ")n = int(r.recvline().strip().decode())r.recvuntil(b"e = ")e = int(r.recvline().strip().decode())r.recvuntil(b"flag_length = ")flag_length = int(r.recvline().strip().decode())r.recvuntil(b"c = ")c = int(r.recvline().strip().decode())
print(f"{n           = }")print(f"{e           = }")print(f"{flag_length = }")print(f"{c           = }")
def query_many(ks):    reqs = [        (c * pow(k, e, n)) % n        for k in ks    ]    req = "\n".join([        str(i)        for i in reqs    ])    r.sendline(req.encode())    ress = [        [r.recvuntil(b"c = "), r.recvline().decode()[0] == "T"][1]        for _ in ks    ]    return ress
dec_lb = int("0011111111".ljust(n.bit_length(), "0"), 2)dec_ub = int("0011111111".ljust(n.bit_length(), "1"), 2)flag_lb = int((b"SECCON{"+ b"\x00" * 48).hex(), 16)flag_ub = int((b"SECCON{"+ b"\xff" * 48).hex(), 16)
# ====== Farm for valid k ======
n_samples = 50samples = []while len(samples) < n_samples:    ks = [randint(2, n) for _ in range(512)]    ress = query_many(ks)    for k, res in zip(ks, ress):        if res:            samples.append(k)            print(".", end="", flush=True)print()n_samples = len(samples)print(f"{n_samples = }")
# ====== Inequality-CVP ======
rows, cols = n_samples + 1, n_samples + 1mat = [    [0 for _ in range(cols)]    for _ in range(rows)]
k_flag_midpoint = (dec_lb + dec_ub) // 2k_flag_range = dec_ub - dec_lb
flag_midpoint = (flag_lb + flag_ub) // 2flag_range = flag_ub - flag_lb
flag_scale = k_flag_range // flag_range
mat[0][-1] = flag_scalefor idx, s in enumerate(samples):    mat[0][idx] = s    mat[1+idx][idx] = n
vec = [k_flag_midpoint] * n_samples + [flag_midpoint * flag_scale]
mat = Matrix(ZZ, mat)vec = vector(vec)
cv = closest_vector(mat, vec)flag = cv[-1] // flag_scaleflag_bytes = bytes.fromhex(hex(flag)[2:])print(f"{flag_bytes = }")
OUTPUT
n           = 12274371278327362987[...]800083923786587181356777e           = 65537flag_length = 439c           = 56926305483733870652[...]67041160004687782469777............................................................n_samples = 51flag_bytes = b'SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}'

Also see SekaiCTF EZMaze and DUCTF rsa interval oracle which has similar themes on binary search / inequality solving.

# BBB

By Xornet

Sometimes I can't distinguish between "b" and "d"

nc BBB.seccon.games 8080

Attachments: dist.tar.gz

50 solves, 136 points

Challenge chall.py
PYTHON
from Crypto.Util.number import bytes_to_long, getPrimefrom random import randintfrom math import gcdfrom secret import FLAGfrom os import urandom

assert len(FLAG) < 100

def generate_key(rng, seed):    e = rng(seed)    while True:        for _ in range(randint(10,100)):            e = rng(e)        p = getPrime(1024)        q = getPrime(1024)        phi = (p-1)*(q-1)        if gcd(e, phi) == 1:            break
n = p*q    return (n, e)

def generate_params():    p = getPrime(1024)    a = randint(0, p-1)
return (p,a)

def main():    p,a = generate_params()    print("[+] The parameters of RNG:")    print(f"{a=}")    print(f"{p=}")    b = int(input("[+] Inject [b]ackdoor!!: "))    rng = lambda x: (x**2 + a*x + b) % p
keys = []    seeds = []    for i in range(5):        seed = int(input("[+] Please input seed: "))        seed %= p        if seed in seeds:            print("[!] Same seeds are not allowed!!")            exit()        seeds.append(seed)        n, e = generate_key(rng, seed)        if e <= 10:            print("[!] e is so small!!")            exit()
keys.append((n,e))
flag = bytes_to_long(FLAG + urandom(16))    for n,e in keys:        c = pow(flag, e, n)        print("[+] Public Key:")        print(f"{n=}")        print(f"{e=}")        print("[+] Cipher Text:", c)

if __name__ == "__main__":    main()

The server encrypts the flag with 5 RSA keypairs with e that is determined by the function $\text{rng}(x) = x^2 + ax + b \bmod p$. The key generation procedure does seed = rng(seed) a random number of times and the end result is the e parameter for the RSA key.

The prime $p$ and random $a$ are generated by the server, but we have control over the parameter b and 5 initial values of seed.

Since the padded length of FLAG is at most 928 bits long, 5 pairs of 2048-bit RSA key and an e=11 is vulnerable to Hastad's broadcast attack since $928 \cdot 11 = 10208 < 5 \cdot 2048 = 10240$. The issue now is how to select b and 5 seed to get e=11 multiple times.

The first observation is that we want the function to be "stable" around seed=11; after reaching seed=11 any further operations of seed = rng(11) should not change seed. This implies that $\text{rng}(11) = 11 = (11)^2 + a \cdot 11 + b \bmod p$, and with this we can solve for the value of $b$.

We can now send the first seed as 11, but are there other values where $\text{rng}(\text{seed}) = 11$? This is a quadratic equation which can have 2 roots, of which one will be 11 and the other can be some large number. Since this equation is in a prime ring modulo $p$, we can easily solve for this other root $s\prime$ where $\text{rng}(s\prime) = 11$ to get a second possible seed value. To generate more possible seeds, we can solve for more seeds $s\prime\prime$ where $\text{rng}(s\prime\prime) = s\prime$ and so on until we get enough seeds for 5 keypairs.

Finally, we can submit these 5 seeds and regenerate $\text{flag}^{11}$ over the integers using the Chinese Remainder Theorem, then get flag using integer roots.

Exploit code
SAGE
# ====== Get parameters ======
from pwn import *
context.log_level = "error"
r = remote("BBB.seccon.games", 8080)r.recvuntil(b"a=")a = int(r.recvline().decode().strip())r.recvuntil(b"p=")p = int(r.recvline().decode().strip())
print(f"{a = }")print(f"{p = }")
# ====== Calculate b ======
F = Zmod(p)R.<x> = PolynomialRing(F, "x")
e = 11eq = e ^ 2 + a * e + x - eb = -eq.coefficients()[0]
print(f"{b = }")print(f"{(x ^ 2 + a * x + b).subs(x=11) = }")
# ====== Find other roots ======
good_roots = [e]search_roots = [e]
while search_roots and len(good_roots) < 5:    root = search_roots.pop()    eq = (x ^ 2 + a * x + b - root)    for new_root, _ in eq.roots():        if new_root in good_roots:            continue        print(f"rng({new_root}) = {root}")        good_roots.append(new_root)        search_roots.append(new_root)
print(f"{len(good_roots) = }")assert len(good_roots) >= 5
# ====== Claim flag ======
r.recvuntil(b"[+] Inject [b]ackdoor!!: ")r.sendline(f"{b}".encode())
for root in good_roots[:5]:    r.recvuntil(b"[+] Please input seed: ")    r.sendline(f"{root}".encode())
encs = []for _ in good_roots[:5]:    r.recvuntil(b"n=")    n = int(r.recvline().decode().strip())    r.recvuntil(b"e=")    e = int(r.recvline().decode().strip())    r.recvuntil(b"[+] Cipher Text: ")    c = int(r.recvline().decode().strip())    encs.append((n, e, c))
flag_e11 = CRT_list([i[2] for i in encs], [i[0] for i in encs])flag_int = flag_e11.nth_root(11)flag = bytes.fromhex(hex(int(flag_int))[2:])print(f"{flag = }")
OUTPUT
a = 58565556875033097418[...]43915055492039312594008p = 10838179308804807042[...]624848130251995513098473b = 60696329029243509419[...]6023171099540640056640(x ** Integer(2) + a * x + b).subs(x=Integer(11)) = 11rng(49816236213014973005[...]80933074759956200504454) = 11rng(41590708505742891949[...]60452743016290828808379) = 49816236213014973005[...]80933074759956200504454rng(82255277072720810564[...]0480331743665371696086) = 49816236213014973005[...]80933074759956200504454rng(86352831126465586764[...]90103301110960958533298) = 82255277072720810564[...]0480331743665371696086rng(71845198174597456665[...]15677903900990755069640) = 82255277072720810564[...]0480331743665371696086len(good_roots) = 6flag = b'SECCON{Can_you_find_d_in_bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbdbbbbbbbbbbbbbbbbbbbbbbbbbbbbb?}c\x1au\xc2Z\xec\xa0?>N=}\x1dj\xe1|'

## pqpq

By kurenaif

Warm your hands first. It's not obvious, right?

Attachments: output.txt problem.py

112 solves, 96 points

Challenge problem.py
PYTHON
from Crypto.Util.number import *from Crypto.Random import *from flag import flag
p = getPrime(512)q = getPrime(512)r = getPrime(512)n = p * q * re = 2 * 65537
assert n.bit_length() // 8 - len(flag) > 0padding = get_random_bytes(n.bit_length() // 8 - len(flag))m = bytes_to_long(padding + flag)
assert m < n
c1p = pow(p, e, n)c1q = pow(q, e, n)cm = pow(m, e, n)c1 = (c1p - c1q) % nc2 = pow(p - q, e, n)
print(f"e = {e}")print(f"n = {n}")# p^e - q^e mod nprint(f"c1 = {c1}")# (p-q)^e mod nprint(f"c2 = {c2}")# m^e mod nprint(f"cm = {cm}")

This is a case of multi-prime RSA with abnormal exponent $e=65537 \cdot 2$.

We can recover $p$, $q$ and $r$ by manipulating leaked values $c_1$ and $c_2$:

\begin{align*} & \text{All equations} \bmod n = pqr & \\ c_1 &= p^e - q^e & (1) \\ c_2 &= (p - q)^e & (2) \\ &= p^e - p^{e-1}q + \cdots - pq^{e-1} + q^e & \text{Expand} \\ c_1 + c_2 &= (p^e - q^e) + (p^e - p^{e-1}q + \cdots - pq^{e-1} + q^e) & (1) + (2) \\ &= (p^e + p^e - p^{e-1}q + \cdots - pq^{e-1}) + (q^e - q^e) & \text{Rearrange} \\ &= p (p^{e-1} + p^{e-1} - p^{e-2}q + \cdots - q^{e-1}) & \text{Factor} \\ &= k_1 p & (3) \\ c_1 - c_2 &= (p^e - q^e) - (p^e - p^{e-1}q + \cdots - pq^{e-1} + q^e) & (1) - (2) \\ &= (p^e - p^e) + (- q^e + p^{e-1}q - \cdots + pq^{e-1} - q^e) & \text{Rearrange} \\ &= q(-q^{e-1} + p^{e-1} - \cdots + pq^{e-2} - q^{e-1}) & \text{Factor} \\ &= k_2 q & (4) \\ \gcd(c_1 + c_2, n) &= \gcd(k_1 p, pqr) & \text{From} (3) \\ &= p & \\ \gcd(c_1 - c_2, n) &= \gcd(k_2 q, pqr) & \text{From} (4) \\ &= q & \\ r &= \frac{n}{pq} \\ \end{align*}

A RSA decryption key $d$ to match $e=65537 \cdot 2$ cannot be calculated since $e$ is even and therefore not is not coprime to $\phi(n)$. However, since we know the values of $p$, $q$ and $r$, we can calculate the 8 possible values of $\sqrt{c} = m^{65537} \mod n$ and proceed as if $e=65537$ instead.

Exploit code
SAGE
# ====== Parameters ======
e = 131074n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866
# ====== Recover key ======
p = gcd(c1 + c2, n)print(f"{p = }")q = gcd(c1 - c2, n)print(f"{q = }")
r = n // p // qprint(f"{r = }")
assert p * q * r == n
phi = (p-1) * (q-1) * (r-1)ee = e // 2dd = ZZ(Zmod(phi)(ee) ^ -1)print(f"{dd = }")
# ====== Manual square root then decrypt ======
from itertools import product
for rp, rq, rr in product(*[Zmod(m)(cm).sqrt(all=True) for m in [p, q, r]]):    cmm = CRT_list([ZZ(rp), ZZ(rq), ZZ(rr)], [p, q, r])    pt = Zmod(n)(cmm) ^ dd    print(bytes.fromhex(hex(pt)[2:].zfill(512))[-50:])
OUTPUT
p = 75724277866950572706[...]00576592403320929717q = 86092588964302105865[...]07084038768336538857r = 90182518745618504676[...]46165598701061994853dd = 570020870802724838415597134387[...]230025007541067468855040422529b"\xfd6\x86\xff$b#Ea2E\xb3!\xf8\xd3~\xc1N\x17\x87'\n\xc6b\xdbY\xca\xe7#\x9e\xd0\x96\x97'[\x18\xe0\xed\x17:\xbcb\xae[p6Ww\x11\xf7"b'\x1e\x8d\xedm\tb\xd8\x15R\xd5\xb8\x9a\x95\xc9\x0eo\xd4\t\xc4\x12/\x06\xcc\xa5[\xa8\x17\x844\t\x8f=\x9b($\x886\x90\\|\x81\x81\x06\xb2!+\x03w\x1c('b'\x8b(T\xdb\xc4\x8d\xad|\x14\x00\x93y\xe1j\x9d\xa0\x19\x04\xdd"\xdb\'\xe0(\xd1\xa0y\x0e\xcb1\x9b}\x9a\x13\n\xf9\xbe\xf3\x95<\xa9\x15\xb9~\xa8\t\xc3\xccW\x14'b'\xe0\x82\xee\xdf)\xaf\xba\xb8\x9e^/\xa4\$\x81\xbf\x8e\xadR>#\xa8\x9a\xa3\xd6\x1a\xee\xd8-\xb0\xf7\x8e:\x8d\x9bi\xfa\xed9\xd1\xe2\x93\xaa\xf8\xef>\x8fJ\x8b\xe8\xb4'b'\xeby\xdd\x8bV.\xec\xda\xc8\xe7\xa7\x19\x0c7Ys\xd1\x1c\rf\x91\xee\x9e\xbf\x1c\x11\x15Py\xad=\xaf\x82\xdd\x00s:#6\xb9F\xde\x1f\xf6\xdb\xdf\xda\xb4\x8f\xdd'b'@\xd4w\x8e\xbbP\xfa\x17SECCON{being_able_to_s0lve_this_1s_great!}'b'\xadn\xde\xfdv{\xcf~\x14p\x1e"\x9a\xf0\n\x92\xaad\x87x\x0b\x82u\xef\xdbW\xd5\xf9\xf6\x9b<\xacuPE\xe5\xf0\xcc\xac\x1fY\x08\x123\xf9D!\xc9\\i'b'\xce\xc6Ek[|\x84N\x06\x13\x91\n\x0e\xc0E\x83\xbd 4\x03\x13~|2[\xa6"\x97\x07\x05\xfbSyQ\x0fUFo\xf1a\x1e&j\x8a\xaa8\xcd\xc9f\x9a'

1. We can ignore the $\text{mod}$ here because it will always be less than $n$.
2. Ignoring some off by one errors and the case where $\text{flag} = \text{flag}_M$.