11/12-11/13 で開催していた SECCON CTF 2022 に参加しました。結果は 13th/726 でした (得点のあるチームのみカウント)。 解いた問題について writeup を書きます。

crypto

janken vs kurenaif

17 solves

server.py
import os
import signal
import random
import 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}")

与えられたシードで生成される乱数列に対して、666回連続でじゃんけんに勝てるような乱数列が生成されるシードを指定できればフラグが手に入ります。

これを実現するためには random.seed や randint の実装を理解しないと難しそうです。ということでどういう実装になっているかを確認し、 python で再実装しました。

random.seed:

def random_seed(seed):
    init_key = []
    if isinstance(seed, int):
        while seed != 0:
            init_key.append(seed % 2 ** 32)
            seed //= 2 ** 32
    else:
        init_key = seed
    key = init_key if len(init_key) > 0 else [0]
    keyused = len(init_key) if len(init_key) > 0 else 1
    return init_by_array(key, keyused)


def init_by_array(init_key, key_length):
    s = 19650218
    mt = [0] * N
    mt[0] = s
    for mti in range(1, N):
        if isinstance(mt[mti - 1], int):
            mt[mti] = (1812433253 * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti) % 2 ** 32
        else:
            mt[mti] = (1812433253 * (mt[mti - 1] ^ LShR(mt[mti - 1], 30)) + mti)
    i = 1
    j = 0
    k = N if N > key_length else key_length
    while k > 0:
        if isinstance(mt[i - 1], int):
            mt[i] = ((mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525)) + init_key[j] + j) % 2 ** 32
        else:
            mt[i] = ((mt[i] ^ ((mt[i - 1] ^ LShR(mt[i - 1], 30)) * 1664525)) + init_key[j] + j)
        i += 1
        j += 1
        if i >= N:
            mt[0] = mt[N - 1]
            i = 1
        if j >= key_length:
            j = 0
        k -= 1
    for k in range(1, N)[::-1]:
        if isinstance(mt[i - 1], int):
            mt[i] = ((mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941)) - i) % 2 ** 32
        else:
            mt[i] = ((mt[i] ^ ((mt[i - 1] ^ LShR(mt[i - 1], 30)) * 1566083941)) - i)
        i += 1
        if i >= N:
            mt[0] = mt[N - 1]
            i = 1
    mt[0] = 0x80000000
    return mt


# check
for i in range(100):
    random.seed(i)
    assert random_seed(i) == list(random.getstate()[1][:N])
i = 2 ** 64 + 2 ** 32 + 2 ** 16
random.seed(i)
assert random_seed(i) == list(random.getstate()[1][:N])

randint(0, 2):

def update_mt(mt):
    N = 624
    M = 397
    MATRIX_A = 0x9908B0DF
    UPPER_MASK = 0x80000000
    LOWER_MASK = 0x7FFFFFFF
    for kk in range(N - M):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        if isinstance(y, int):
            mt[kk] = mt[kk + M] ^ (y >> 1) ^ (y % 2) * MATRIX_A
        else:
            mt[kk] = mt[kk + M] ^ LShR(y, 1) ^ (y % 2) * MATRIX_A
    for kk in range(N - M, N - 1):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        if isinstance(y, int):
            mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ (y % 2) * MATRIX_A
        else:
            mt[kk] = mt[kk + (M - N)] ^ LShR(y, 1) ^ (y % 2) * MATRIX_A
    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
    if isinstance(y, int):
        mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ (y % 2) * MATRIX_A
    else:
        mt[N - 1] = mt[M - 1] ^ LShR(y, 1) ^ (y % 2) * MATRIX_A


def rand_int_0_2(n, seed):
    mt = random_seed(seed)
    update_mt(mt)
    my_rands = []
    i = 0
    while True:
        if len(my_rands) == n:
            break
        while True:
            tmp_rand = temper(mt[i]) >> 30
            if tmp_rand <= 2:
                break
            i += 1
            if i >= N:
                i -= N
                update_mt(mt)
        my_rands.append(tmp_rand)
        i += 1
        if i >= N:
            i -= N
            update_mt(mt)
    return my_rands


# check
random.seed(1)
rands = [random.randint(0, 2) for _ in range(N)]
my_rands = rand_int_0_2(N, 1)
assert my_rands == rands

ここまでは理解のためにとりあえず実装したという感じだったのですが、せっかくなので z3 を試してみました。そしたら普通に答えが見つかってしまいました。非想定解だったらすみません… 特に考察とかもしていないので書くことがないです。所望の乱数列を作るには乱数列分の自由度があったほうがよさそうと思い、 seed は $32 \times 666$ bits としました。

import random

from pwn import remote
from z3 import *


N = 624
M = 397
MATRIX_A = 0x9908B0DF
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7FFFFFFF


def temper(state):
    y = state
    if isinstance(y, int):
        y ^= y >> 11
    else:
        y ^= LShR(y, 11)
    y ^= (y << 7) & 0x9D2C5680
    y ^= (y << 15) & 0xEFC60000
    if isinstance(y, int):
        y ^= y >> 18
    else:
        y ^= LShR(y, 18)
    return y


NN = 666

io = remote("janken-vs-kurenaif.seccon.games", 8080)

io.recvuntil(b"kurenaif: My spell is ")
ret = io.recvuntil(b".")
random.seed(int(ret[:-1], 16))
rands = [random.randint(0, 2) for _ in range(NN)]
state = [BitVec(f"state_{i}", 32) for i in range(N)]
next_state = state.copy()
update_mt(next_state)
s = Solver()
my_rands = []
i = 0
while True:
    if len(my_rands) == NN:
        break
    tmp_rand = LShR(temper(next_state[i]), 30)
    my_rands.append(tmp_rand)
    i += 1
    if i >= N:
        i -= N
        update_mt(next_state)
for i in range(NN):
    s.add(my_rands[i] == (rands[i] + 1) % 3)
s.add(state[0] == 0x80000000)
s.check()

m = s.model()
state = [m[s].as_long() for s in state]

my_seed = [BitVec(f"seed_{i}", 32) for i in range(NN)]
mt = random_seed(my_seed)
s = Solver()
for i in range(N):
    s.add(mt[i] == state[i])
update_mt(mt)
update_mt(state)
for i in range(NN - N):
    s.add(mt[i] == state[i])
s.check()

m = s.model()
my_seed = [m[s].as_long() for s in my_seed]

my_seed_int = 0
for s in my_seed[::-1]:
    my_seed_int *= 2**32
    my_seed_int += s

# check
random.seed(my_seed_int)
my_rands = [random.randint(0, 2) for _ in range(NN)]
for i in range(NN):
    assert janken(my_rands[i], rands[i]) == 1

io.sendlineafter(b"your spell: ", hex(my_seed_int).encode())
_ = io.recvline()
print(io.recvline())

SECCON{https://youtu.be/h0GSFxoRhrc}

witches_symmetric_exam

22 solves

problem.py
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from 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)))

secret_spell を AES の GCM モードで暗号化+署名生成した後、それらをさらに AES の OFB モードで暗号化したものが渡されます。

AES の OFB モードは wikipedia の図を見ればわかるように、 ciphertext をいじることによって復号結果を調整することが簡単にできます。そのため Padding Oracle Attack を使って平文 (ここでは GCM モードのタグ、 nonce、暗号文) が求まります。またこれを応用し、 iv の値を指定することで AES の Enc(iv) も求められます。これで GCM モードのタグを計算するのに必要するための値はすべて計算できるため、後はやるだけです。

solve.sage
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from pwn import xor, remote, unhex


X = GF(2).polynomial_ring().gen()
poly = X ** 128 + X ** 7 + X ** 2 + X ** 1 + 1
F = GF(2 ** 128, name='a', modulus=poly)
R.<x> = PolynomialRing(F)


def tobin(x, n):
    x = Integer(x)
    nbits = x.nbits()
    assert nbits <= n
    return x.bits() + [0] * (n - nbits)


def frombin(v):
    return int("".join(map(str, v)), 2)


def toF(x):
    x = frombin(tobin(x, 128))
    return F.fetch_int(x)


def fromF(x):
    x = x.integer_representation()
    x = frombin(tobin(x, 128))
    return x


def encrypt():
    _ = io.recvuntil(b"ciphertext: ")
    return unhex(io.recvline().strip().decode())


def decrypt(data: bytes):
    io.sendlineafter(b"ciphertext: ", data.hex().encode())
    return io.recvline().strip()


io = remote("witches-symmetric-exam.seccon.games", 8080)

ct = encrypt()
iv = ct[:16]
ct = ct[16:]

pt = b""
for block_idx in range(0, 64, 16)[::-1]:
    ct_block = ct[:block_idx + 16]
    for i in range(16):
        for j in range(256):
            if b"ofb error" not in decrypt(iv + ct_block[:-16] + ct_block[-16:-16+15-i] + long_to_bytes(j) + ct_block[len(ct_block)-16+16-i:]):  # TODO ofb error
                k = (i + 1) ^^ j  # k は AES の出力
                tmp = long_to_bytes(k ^^ ct_block[-16+15-i])
                if i == 0 and tmp == b"\x01":
                    continue
                pt = tmp + pt
                ct_block = ct_block[:-16] + ct_block[-16:-16+15-i] + xor(long_to_bytes(j) + ct_block[len(ct_block)-16+16-i:], long_to_bytes(i + 1), long_to_bytes(i + 2))
                print(pt)
                break

temp = unpad(pt, 16)
gcm_tag = temp[:16]
gcm_nonce = temp[16:32]
gcm_ciphertext = temp[32:]


def find_encrypt_input(inp: bytes):
    assert len(inp) == 16
    ret = b""
    ct_block = b"\x00" * 16
    iv = inp
    for i in range(16):
        for j in range(256):
            if b"ofb error" not in decrypt(iv + ct_block[:-16] + ct_block[-16:-16+15-i] + long_to_bytes(j) + ct_block[len(ct_block)-16+16-i:]):  # TODO ofb error
                k = (i + 1) ^^ j  # k は AES の出力
                tmp = long_to_bytes(k ^^ ct_block[-16+15-i])
                if i == 0 and tmp == b"\x01":
                    continue
                ret = long_to_bytes(k) + ret
                print(ret)
                ct_block = ct_block[:-16] + ct_block[-16:-16+15-i] + xor(long_to_bytes(j) + ct_block[len(ct_block)-16+16-i:], long_to_bytes(i + 1), long_to_bytes(i + 2))
                break
    return ret

H_bytes = find_encrypt_input(b"\x00" * 16)
H = toF(bytes_to_long(H_bytes))


def ghash(iv: bytes, H):
    fill = (16 - (len(iv) % 16)) % 16 + 8
    ghash_in = iv + b"\x00" * fill + long_to_bytes(8 * len(iv), 8)
    assert len(ghash_in) % 16 == 0
    ghash = toF(0)
    for i in range(0, len(ghash_in), 16):
        ghash_block = ghash_in[i: i+16]
        ghash += toF(bytes_to_long(ghash_block))
        ghash *= H
    return long_to_bytes(fromF(ghash))


j0 = ghash(gcm_nonce, H)
nonce_ctr = j0[:12]
iv_ctr_0 = long_to_bytes((bytes_to_long(j0) + 1) & 0xffffffff, 4)
iv_ctr_1 = long_to_bytes((bytes_to_long(j0) + 2) & 0xffffffff, 4)
ctr_enc_0 = find_encrypt_input(nonce_ctr + iv_ctr_0)
ctr_enc_1 = find_encrypt_input(nonce_ctr + iv_ctr_1)
dec_0 = xor(gcm_ciphertext[:16], ctr_enc_0)
dec_1 = xor(gcm_ciphertext[16:], ctr_enc_1)[:len(gcm_ciphertext[16:])]
dec_secret_spell = dec_0 + dec_1
print(dec_secret_spell)
# b'decrypt_all!!277260221!!'

new_pt = b"give me key"
S = toF(bytes_to_long(find_encrypt_input(j0)))
L = toF(int("%016x%016x" % (0, 8*len(new_pt)), 16))
new_ct = b""
Cs = []
for i in range(0, len(new_pt), 16):
    pt_block = new_pt[i: i+16]
    C = toF(bytes_to_long(xor(ctr_enc_0, pt_block.ljust(16, b"\x00"))))
    ct_block = long_to_bytes(fromF(C))[:len(pt_block)]
    Cs.append(toF(bytes_to_long(ct_block + b"\x00" * (-len(ct_block) % 16))))
    new_ct += ct_block
T = toF(0)
for i, C in enumerate(Cs[::-1], 2):
    T += C * H**i
T += L * H + S
tag = long_to_bytes(fromF(T))

new_new_ct = b""
new_new_ct += xor(ct[:16], pt[:16], tag)
new_new_ct += xor(ct[16:32], pt[16:32], gcm_nonce)
new_new_ct += xor(ct[32:48], pt[32:48], pad(new_ct, 16))

io.sendlineafter(b"ciphertext: ", (iv + new_new_ct).hex().encode())
io.sendlineafter(b"ok, please say secret spell:", dec_secret_spell)
print(io.recvline())

SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}

insufficient

33 solves

problem.py
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long
from 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 p
def 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 = 0
for coeff in coeffs:
    key <<= 128
    key ^= coeff

cipher_text = bytes_to_long(FLAG) ^ key
print(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)

randint(0, 2**128) で生成された $a_1, a_2, a_3, b_1, b_2, b_3, c, s$ を使って key が計算され、その key でフラグが暗号化されています。 また、これらの係数を求めるヒントとして、 $x_i, y_i$ ($0 \le i < 4$) と $f_i = a_1 x_i + a_2 x_i^2 + a_3 x_i^3 + b_1 y_i + b_2 y_i^2 + b_3 y_i^3 + c z_i + s \mod p$ が与えられています。 $z_i$ は未知で、 random.randint(0, 2**128) で生成されています。

$f_i$ の式は、 $cz_i$ をひっくるめて変数とみなすと、 $a_1, a_2, a_3, b_1, b_2, b_3, c z_i, s$ について線形な式になっています。しかも $p$ の値に比べて各係数は十分小さいです。 LLL を使えという声が聞こえてきます。格子の作り方は下のスクリプトを参照してください。

注意点として、この格子の作り方だと、 $cz_i + s$ については正しい値が見つかりますが、 $cz_i, s$ の値は不定になってしまいます。これは求まった $cz_i, s$ がそれぞれ $cz_i + \delta, s - \delta$ という値を取りうるからです。 $\delta$ を無視するため、 $(cz_i + \delta) - (cz_j + \delta) = c(z_i - z_j)$ を複数求め、 gcd を取れば $c$ が求まり、そこから $z_i, s, \delta$ も求まります。

solve.sage
ct = 115139400156559163067983730101733651044517302092738415230761576068368627143021367186957088381449359016008152481518188727055259259438853550911696408473202582626669824350180493062986420292176306828782792330214492239993109523633165689080824380627230327245751549253757852668981573771168683865251547238022125676591
p = 8200291410122039687250292442109878676753589397818032770561720051299309477271228768886216860911120846659270343793701939593802424969673253182414886645533851
shares = [((6086926015098867242735222866983726204461220951103360009696454681019399690511733951569533187634005519163004817081362909518890288475814570715924211956186561, 180544606207615749673679003486920396349643373592065733048594170223181990080540522443341611038923128944258091068067227964575144365802736335177084131200721), 358596622670209028757821020375422468786000283337112662091012759053764980353656144756495576189654506534688021724133853284750462313294554223173599545023200), ((1386358358863317578119640490115732907593775890728347365516358215967843845703994105707232051642221482563536659365469364255206757315665759154598917141827974, 4056544903690651970564657683645824587566358589111269611317182863269566520886711060942678307985575546879523617067909465838713131842847785502375410189119098), 7987498083862441578197078091675653094495875014017487290616050579537158854070043336559221536943501617079375762641137734054184462590583526782938983347248670), ((656537687734778409273502324331707970697362050871244803755641285452940994603617400730910858122669191686993796208644537023001462145198921682454359699163851, 7168506530157948082373212337047037955782714850395068869680326068416218527056283262697351993204957096383236610668826321537260018440150283660410281255549702), 1047085825033120721880384312942308021912742666478829834943737959325181775143075576517355925753610902886229818331095595005460339857743811544053574078662507), ((5258797924027715460925283932681628978641108698338452367217155856384763787158334845391544834908979711067046042420593321638221507208614929195171831766268954, 4425317882205634741873988391516678208287005927456949928854593454650522868601946818897817646576217811686765487183061848994765729348913592238613989095356071), 866086803634294445156445022661535120113351818468169243952864826652249446764789342099913962106165135623940932785868082548653702309009757035399759882130676)]


# [a1, a2, a3, b1, b2, b3, s, cz1, cz2, cz3, cz4, k1, k2, k3, k4] * mat
mat = matrix(ZZ, 15, 15)
lb = []
ub = []
for i in range(7):
    mat[i, i] = 1
    lb.append(0)
    ub.append(2**128)
for i in range(7, 11):
    mat[i, i] = 1
    lb.append(0)
    ub.append(2**256)
for i in range(4):
    (x, y), w = shares[i]
    mat[0, 11+i] = x
    mat[1, 11+i] = pow(x, 2, p)
    mat[2, 11+i] = pow(x, 3, p)
    mat[3, 11+i] = y
    mat[4, 11+i] = pow(y, 2, p)
    mat[5, 11+i] = pow(y, 3, p)
    mat[6, 11+i] = 1
    mat[7+i, 11+i] = 1
    mat[11+i, 11+i] = -p
    lb.append(w)
    ub.append(w)
# https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
res = solve(mat, lb, ub)

cz_pad = []
for i in range(4):
    cz_pad.append(int(res[2][7+i]))

c = gcd(cz_pad[0] - cz_pad[1], cz_pad[0] - cz_pad[2])
t = cz_pad[0] % c - c
s = int(res[2][6]) + t

coeffs = []
for i in range(6):
    coeffs.append(int(res[2][i]))
coeffs.append(c)
coeffs.append(s)

key = 0
for coeff in coeffs:
    key <<= 128
    key ^^= coeff

print(long_to_bytes(ct ^^ key))

SECCON{Unfortunately_I_could_not_come_up_with_a_more_difficult_problem_than_last_year_sorry...-6fc18307d3ed2e7673a249abc2e0e22c}

this_is_not_lsb

34 solves

problem.py
from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p * q
phi = (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}")

# padding format: 0b0011111111........
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)

    return (m >> (padding_pos - 8)) == 0xFF


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

padding の形が特殊で、復号結果の先頭ビットが 0011111111 となっているときに unpad が成功します。

$m$ をフラグ、 $c = m^e \mod n$ として、 $c k^e \mod n$ を送信すると、復号結果は $mk \mod n$ となることを利用します。ある適当な $k$ を送信して unpad が成功した場合、 $mk \mod n$ が 0011111111 で始まることとなり $n$ よりもやや小さいことがわかります。このような $k$ を大量に集めて LLL を使えば $m$ が求まります (40個ぐらい集めた)。

solve.sage
import random
from tqdm import tqdm
from pwn import remote

ks = []
ns = []

while True:
    io = remote("this-is-not-lsb.seccon.games", 8080)
    _ = io.recvuntil(b"n = ")
    n = int(io.recvline())
    if n.bit_length() != 1024:
        print("yarinaoshi")
        io.close()
    else:
        break
_ = io.recvuntil(b"flag_length = ")
flag_length = int(io.recvline())
_ = io.recvuntil(b"c = ")
c = int(io.recvline())
e = 65537

for _ in tqdm(range(40000)):
    k = random.randint(1, n - 1)
    _ = io.sendlineafter(b"c = ", str(c * pow(k, e, n) % n).encode())
    if io.recvline().strip().decode() == "True":
        ks.append(k)
        ns.append(n)
        print(len(ks), k)

M = len(ks)
# [pad, pad, ..., m] = [l1, l2, ... lM, m] * mat
mat = matrix(ZZ, M+1, M+1)
for i in range(M):
    mat[i, i] = -ns[i]
    mat[M, i] = ks[i]
mat[M, M] = 1
lb = [int("0011111111" + "0" * 1014, 2)] * M + [bytes_to_long(b"SECCON{") * 256 ** 48]
ub = [int("0011111111" + "1" * 1014, 2)] * M + [bytes_to_long(b"SECCON|") * 256 ** 48]
res = solve(mat, lb, ub)
print(long_to_bytes(int(res[2][-1])))

SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}

BBB

50 solves

chall.py
from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from secret import FLAG
from 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()

RSA の公開鍵 $e$ が、 $e = \mathrm{rng}(e)$ を何度か計算 (回数はランダム) することで生成されます。 rng は $f(x) = x^2 + ax + b \mod p$ という形をしており、 $a, p$ は given で $b$ と $e$ の初期値は指定できます。生成された $e$ と $n$ を使って暗号化したフラグが得られます。これを5回行えます。

$e$ が小さいときになんか悪さができないか気になるので初手で確認します。 $e \le 10$ は弾かれてしまうため、 $e = 11$ のときを考えると、フラグの文字数が99文字以下であることから暗号文の mod を取る前は $99 \times 8 \times 11 = 8712$ bit であることがわかります。 2048 bit の $n$ 5個での暗号が既知なため、 CRT を計算すれば $2048 \times 5 = 10240$ bit 以下の暗号文については $e$ 乗根を取れば平文が直接計算できてしまいます。

$e = 11$ を5回実現する $b$ と $e$ の初期値を考えます。 $b$ については $e = e^2 + ae + b \mod p$ となるように決めてあげれば、 $e = 11$ が不動点となり rng を呼ぶ回数に関わらず $e$ が固定されます。数回 (例えば4回) rng を計算することで $e = 11$ となるような初期値は $f(f(f(f(e)))) = e \mod e$ を解くことで求まります。これの解の個数については $p, a$ に依存してしまうため、何回かガチャを回す必要がありました。

solve.sage
a=27369245210289386000526318514605318971653744035453041755627936950191800370152514525569332479447801956262032901707717125882844247382472152455434481666695796989837027986272859891721819470297025863094697089997184239773496107857592420268317359858275093675476827404478533805160124354119128072421752989042825267445
p=130093144968243935078986528479766130437304163620555723854545367089878986296019866578111181166480453668822869467410372758232509622191746977509119000442762376116637490521234470851889951225051406222367975586382630818585688578771312073687545768706330682143386332513352136013919176563564224353727902173378017506517

x = 11
b = (x - (x ** 2 + a * x)) % p
PR.<x> = PolynomialRing(Zmod(p))
f = x
for _ in range(4):
    f = f^2 + a * f + b
roots = (f - 11).roots(multiplicities=False)
print(roots)

"""
[+] The parameters of RNG:
a=52277472080269613433144640539303534154154668798737834165115043595876739227442108053148002885892522326069219595206892041739111316065671229949250521821449042711622590673835477663652491943227757967748818830657298306042203539329637341548678949584350056573262256579991020617185626644801564376991915479254627098106
p=128935882295615658034848963571001401569570030526989068702233912414162535164619439929091116879472821302327076660169626528400203289516018703892450126963333865525141651603323113437523406418322196508172425137791184649576731443783999933794481139284801850539862808404559548596572086091644848176170513832440182326703
[+] Inject [b]ackdoor!!: 69627218595112542409653771922668132152148795848829167694904082516168544321234011060827552652546360924873967753572320182870791970857709990020494894780729857797859760604425312887439620716105644895625118551725641881419418286293988911936937250996158630393429219642896516193818537365407032733941498890400013554239
[+] Please input seed: 11
[+] Please input seed: 6201518432286934030495159591413396426269909746193971801521532605463506046423635263104158317526191916624340062254271847833970032745044898179153841458657640542007389686750635234987236709747304871277385909380442046713965698392233165763426072985733637122566195990833785209544550153755514824916906763569925303818
[+] Please input seed: 11163870618455787345224486267573474080033997787280805036566310251363696420748699966921814199222231588307865402229876368875461090319722614540978383054419313244646930781988780382358250282309658246165513657504329788230900153138832465174396966940103023415778630937312085971177981535544465613355736885903100063891
[+] Please input seed: 26032725239817815450441757151638177043200424576767800672094499029738176303708951443012323036123160072049632219678510026706737783739593103053385261965532637790371801264958162240061079902572753686480638329176809269025098552486932149069193504029578605527242077971100414056576316774937052086115640513262846044549
[+] Please input seed: 50625684975528229151262565880059690372214937151483433865024369788547619633468380432930790957457138904208224845284224459954354189710754370889814343176352185023147259664529473533809834572521684853942967977957077074509429351967430443176608685670873188439358473853468113922810142671906231713062957839922709184048
[+] Public Key:
n=22613348679702495219351633545031633063620394355834365312399599057754915315452210989918206531176630892546787541881034831386013453297051998269954756310493861505427550769828866005416603054559728345896907978975079211590296622514425568137515120937738546956240516068925094155443440769592457890749632692855150317796525639109892233235693735487928277772322844743811238272535615952194816471306022873460674076330764587095303516349725454701095437089049025135528886887667435614298245195270962892661988440785326845961972043133501093953478882415310500952548379858409472629446235263930381245654051557633698777106822307542287703907269
e=11
[+] Cipher Text: 6878732537233753109832483290266651063614447044398347084819777840853165947203507369788126298415036013002661271324860933886111074677232822740045152817461690617990902678312306808891517925776348800496312485748056772141514993834668978209438280861909980008331766402034879910942824260752266756519181315731287191835392922717370337222556297168753207638645117081107598711825773565865229488157636882730142794189855074388448694203639616895758814957039667519557180433384721284006522153895024861666073665233081821430338993433350713318779633939072477125006368493598896255397493627223958200746135515845262560900830032082933876823846
[+] Public Key:
n=13133014074035138400067665316961915072193507072225500957802085734048457503882599709052833289171035439634567810626509466586090533938912085501623235590019603049964966879606731941546684469579587146870548201820262052498675417210737966888036930071028531478817597870128224258287756042537230981419522821606718525855843240014604664221469197215394225320400437247092986008511984819846062289772969978522076494035299458975949439234097832661865810100120591103118310004297832318549029706300914765772919912295332635372537976879133169404185188378768158913399067963946703531729791315404220844679466149723628749712619382058108386560451
e=11
[+] Cipher Text: 12256225936835976787019680958336212278044118862465520800553544614087223806626860766290399176688590330102297301461074146408453010087764709934662765753500496656279140005596745634200532522203705332746267215893371465619817212006180188737998922881114480063713976315623175075706144613411969772989639510491385378872944655147840563607788108468029096540066811944465074011663710453301515542235299684259486183739177126116527412080613020730995435610495120806176717748413565126934819276984211501695713346423058207564958748731759722987805875085856618165750685787734749229632251955372955623529555669994809992735608033385868808239114
[+] Public Key:
n=16123968586884933733389574291090914963167150419289874128348128872079229709540830478901870144045528476121264647347085694986698336712182802424687184091361517637506394689515675363343349624495437931954684618875268085545315821571788494549022427977385174327073591580049030420788831195858470152487900922238839044980345001556929363995380814026375959360628717964645904859132706622763021507075036041649231842587774215787970288186683422381737588068390450677248226880323895544567226145425840512539437539583025276852910269801339827230226401906679990392759959459271813793047558522035131051438040341019219030981740556149390487603467
e=11
[+] Cipher Text: 11331105292061989501032149514156450465805173159909131280723989710674237030363750872548867430904389751159310018284842221846445095489793695163730793322816822511557106286430809333926432810847849939546667114001971805685647530615137286026457496123256864567354912625327463945465830474419792573263934905912525150110930342116768789614995391794926048075000757152906266649596756304901256262778931653173869467636613252714792799741633245432091794124468296008851778732084272142664458682799302529900574165723080507233042276267304460311355451924278486409408816619876612291321116991718221857013638562426760760544112596495363069149984
[+] Public Key:
n=10778708623873496481084918966385444393601239104663339141341545827042085586887842088551820774640526447988736026000240413289142402279875817417071641806898541877312592741387053430320567460579810221775937443583044458287236371310285871261138109164887717581406051669177596903596329554791553166014385497050622099691977874358876326487816085434199496366401730308189174404349228152833314564255458609864815532870783875462313410496143001157146096101571566353247724883644304339271734879272585121296167477479313355786187629443460084447614985936407388688733961144397706991752435750766547284253679882470229344159434274514031441249391
e=11
[+] Cipher Text: 3418272553336520064541623070574780761359201346292525917263436047425587760113922548343905648075268957054718028652654256556268441348250837298635426011730005545675262193115820096722244990600962368761459710991297819556710421575343931535035636518179774812262238134263841699524504401689132483458855711218798419896281930404420786787320109025451103243461475493921900689855687211308240372069194688366049041375747367766244180416646564541825840881449938484183484729176197612530978290725224747157050919772189238708045620897194642706392113561343346970737657544058361852820731673931064706508848481269733656616073204202610701284860
[+] Public Key:
n=15424422539219448603211027858071725237035568352520041306358601418807853775866351824682851654203585545784066668874895015279498542162746232104058937455781588098093560716195017648861111083997352761078465190607779319373263633616868913369444457297401568579206526171132771301506718022681722720738371599393789554558724784841806617245824481060063193898767882548276844546029968012104417372617478377642277254343600706069994900298057806744997336972747886055143620817312578373411804816609955861003111850426890844567422517003425274582723717856655133752290500848610291922685772790907224308424330839379039921520128794649028246710147
e=11
[+] Cipher Text: 10276855620814903051485572369117271727022358309261826475344005529963381525321913297258330766602862145392558913159697342679943437220502777256104540022276078255919728806068426901029791438490722935045631907744068270502041412875768096901186617372041730418419101809407437807684518390713989373797490008648475166145782042124137855236048700425473915266364822860744031142683870289771757301786867453187784778240529594798602715869564493614908001822358655922520745080875367174949697176016542637598602733816902239926888176108124419675686788675997314065277791026362844425112273371662621120875171800779520693163047544991528631029537
"""

ns = []
cs = []
n=22613348679702495219351633545031633063620394355834365312399599057754915315452210989918206531176630892546787541881034831386013453297051998269954756310493861505427550769828866005416603054559728345896907978975079211590296622514425568137515120937738546956240516068925094155443440769592457890749632692855150317796525639109892233235693735487928277772322844743811238272535615952194816471306022873460674076330764587095303516349725454701095437089049025135528886887667435614298245195270962892661988440785326845961972043133501093953478882415310500952548379858409472629446235263930381245654051557633698777106822307542287703907269
c = 6878732537233753109832483290266651063614447044398347084819777840853165947203507369788126298415036013002661271324860933886111074677232822740045152817461690617990902678312306808891517925776348800496312485748056772141514993834668978209438280861909980008331766402034879910942824260752266756519181315731287191835392922717370337222556297168753207638645117081107598711825773565865229488157636882730142794189855074388448694203639616895758814957039667519557180433384721284006522153895024861666073665233081821430338993433350713318779633939072477125006368493598896255397493627223958200746135515845262560900830032082933876823846
ns.append(n)
cs.append(c)
n=13133014074035138400067665316961915072193507072225500957802085734048457503882599709052833289171035439634567810626509466586090533938912085501623235590019603049964966879606731941546684469579587146870548201820262052498675417210737966888036930071028531478817597870128224258287756042537230981419522821606718525855843240014604664221469197215394225320400437247092986008511984819846062289772969978522076494035299458975949439234097832661865810100120591103118310004297832318549029706300914765772919912295332635372537976879133169404185188378768158913399067963946703531729791315404220844679466149723628749712619382058108386560451
c = 12256225936835976787019680958336212278044118862465520800553544614087223806626860766290399176688590330102297301461074146408453010087764709934662765753500496656279140005596745634200532522203705332746267215893371465619817212006180188737998922881114480063713976315623175075706144613411969772989639510491385378872944655147840563607788108468029096540066811944465074011663710453301515542235299684259486183739177126116527412080613020730995435610495120806176717748413565126934819276984211501695713346423058207564958748731759722987805875085856618165750685787734749229632251955372955623529555669994809992735608033385868808239114
ns.append(n)
cs.append(c)
n=16123968586884933733389574291090914963167150419289874128348128872079229709540830478901870144045528476121264647347085694986698336712182802424687184091361517637506394689515675363343349624495437931954684618875268085545315821571788494549022427977385174327073591580049030420788831195858470152487900922238839044980345001556929363995380814026375959360628717964645904859132706622763021507075036041649231842587774215787970288186683422381737588068390450677248226880323895544567226145425840512539437539583025276852910269801339827230226401906679990392759959459271813793047558522035131051438040341019219030981740556149390487603467
c = 11331105292061989501032149514156450465805173159909131280723989710674237030363750872548867430904389751159310018284842221846445095489793695163730793322816822511557106286430809333926432810847849939546667114001971805685647530615137286026457496123256864567354912625327463945465830474419792573263934905912525150110930342116768789614995391794926048075000757152906266649596756304901256262778931653173869467636613252714792799741633245432091794124468296008851778732084272142664458682799302529900574165723080507233042276267304460311355451924278486409408816619876612291321116991718221857013638562426760760544112596495363069149984
ns.append(n)
cs.append(c)
n=10778708623873496481084918966385444393601239104663339141341545827042085586887842088551820774640526447988736026000240413289142402279875817417071641806898541877312592741387053430320567460579810221775937443583044458287236371310285871261138109164887717581406051669177596903596329554791553166014385497050622099691977874358876326487816085434199496366401730308189174404349228152833314564255458609864815532870783875462313410496143001157146096101571566353247724883644304339271734879272585121296167477479313355786187629443460084447614985936407388688733961144397706991752435750766547284253679882470229344159434274514031441249391
c = 3418272553336520064541623070574780761359201346292525917263436047425587760113922548343905648075268957054718028652654256556268441348250837298635426011730005545675262193115820096722244990600962368761459710991297819556710421575343931535035636518179774812262238134263841699524504401689132483458855711218798419896281930404420786787320109025451103243461475493921900689855687211308240372069194688366049041375747367766244180416646564541825840881449938484183484729176197612530978290725224747157050919772189238708045620897194642706392113561343346970737657544058361852820731673931064706508848481269733656616073204202610701284860
ns.append(n)
cs.append(c)
n=15424422539219448603211027858071725237035568352520041306358601418807853775866351824682851654203585545784066668874895015279498542162746232104058937455781588098093560716195017648861111083997352761078465190607779319373263633616868913369444457297401568579206526171132771301506718022681722720738371599393789554558724784841806617245824481060063193898767882548276844546029968012104417372617478377642277254343600706069994900298057806744997336972747886055143620817312578373411804816609955861003111850426890844567422517003425274582723717856655133752290500848610291922685772790907224308424330839379039921520128794649028246710147
c = 10276855620814903051485572369117271727022358309261826475344005529963381525321913297258330766602862145392558913159697342679943437220502777256104540022276078255919728806068426901029791438490722935045631907744068270502041412875768096901186617372041730418419101809407437807684518390713989373797490008648475166145782042124137855236048700425473915266364822860744031142683870289771757301786867453187784778240529594798602715869564493614908001822358655922520745080875367174949697176016542637598602733816902239926888176108124419675686788675997314065277791026362844425112273371662621120875171800779520693163047544991528631029537
ns.append(n)
cs.append(c)

C = crt(cs, ns)
N = prod(ns)
print(long_to_bytes(int(C ** (1 / 11))))

SECCON{Can_you_find_d_in_bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbdbbbbbbbbbbbbbbbbbbbbbbbbbbbbb?}

pqpq

112 solves

problem.py
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 * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = 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) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")

$c_1 = p^e - q^e \mod n$ と $c_2 = (p - q)^{e} \mod n$ が既知です。 $c_2 = (p - q)^e = p^e + q^e \mod n$ ($\because e \mathrm{\,is\,even}$) が成り立つため、 $c_1 + c_2 = 2p^e \mod n$ です。これと $n$ の gcd を取ることで $p$ が求まります。 $q$ も同様です。$p, q$ がわかれば $r$ もわかります。

この問題の厄介ポイントは $e$ が偶数であるために $ed = 1 \mod \phi$ なる $d$ が存在しないことです ($\phi$ が偶数なので)。そのため、 $c_m = m^e \mod n$ となる $m$ は複数通り存在します。 これらをすべて求めるため、 $c_m = m^e \mod p$ となる $m$ をまず列挙します。 $4 | p - 1$, $8 \nmid p - 1$ なので $ed = 1 \mod \phi / 4$ となる $d$ と位数が4となる $L$ を $k^{\phi / 4} \mod p$ により探します。これらを使って、 $c_m^d L^i \mod p$ ($0 \le i < 4$) を計算したものが解候補になります。これを $q, r$ についても同様に行い、それぞれの CRT を計算することで $c_m = m^e \mod n$ の解候補を列挙できます。