corCTF 2021 Writeup

Mon Aug 23 2021

    8/21-8/23 で開催していた corCTF 2021 にチーム WreckTheLine で参加しました。結果は 5th/904 (得点のあるチームのみカウント) でした。 例のごとく Crypto ばかり解いてました。1問 (crypto/leave_it_to_chance) だけ解けなかったのが悔やまれますが、それ以外は全問解けました!個人的には苦手意識のある量子回路の問題を通せたのが嬉しかったです。 以下は solve 数50以下の問題についての writeup です。

    crypto

    fried_rice

    6 solves

    source.sage
    from random import shuffle, randrange, randint
    from os import urandom
    from Crypto.Util.number import getPrime, getStrongPrime, long_to_bytes
    from Crypto.Cipher import AES
    from Crypto.Util.Padding import pad
    from private import flag
    import sys
    
    class RNG:
        def __init__(self, seed, a, b):
            self.state = seed
            self.a = a
            self.b = b
            print('a:', a)
            print('b:', b)
    
        def nextbits(self, bitlen):
            out = 0
            for _ in range(bitlen):
                out <<= 1
                self.state = self.a * self.state + b
                bit = int(sum(self.state[i] for i in range(7)))
                out += bit
            return out
    
    def get_params(rng, bitlen):
        p = next_prime((1 << (bitlen - 1)) | rng.nextbits(bitlen))
        q = next_prime((1 << (bitlen - 1)) | rng.nextbits(bitlen))
        N = p * q
        return N, p, q
    
    LIMIT = 26
    P.<x> = PolynomialRing(GF(2))
    F.<x> = P.quo(x^128 + x^7 + x^2 + x + 1)
    key, a, b = [F.random_element() for _ in range(3)]
    bytekey = long_to_bytes(int(''.join(list(map(str, key.list()))), 2))
    iv = os.urandom(16)
    cipher = AES.new(bytekey, AES.MODE_CBC, IV=iv)
    rng = RNG(key, a, b)
    N, p, q = get_params(rng, 512)
    if randint(0, 1):
        p, q = q, p
    e = 65537
    d = inverse_mod(e, (p-1)*(q-1))
    dp = d % (p-1)
    r = getStrongPrime(1024)
    g = randrange(2, r)
    print('iv:', iv.hex())
    print('N:', N)
    print('e:', e)
    print('g:', g)
    print('r:', r)
    print('encrypted flag:', cipher.encrypt(pad(flag, 16)).hex())
    print()
    print("now, let's cook some fried rice!")
    for _ in range(LIMIT):
        sys.stdout.flush()
        m = int(input('add something in(in hex)> '), 16)
        dp ^^= m
        print('flip!', pow(g, dp, r))
    print("it's done. enjoy your fried rice!")

    このコードで行われていることは、

    • GF(2128)\mathrm{GF}(2^{128}) 上で key, a, b を生成。この key でフラグは暗号化される
    • key を初期状態 a, b をパラメータとした LCG でビット列を生成し、これらから p, q を生成
    • dpe1mod(p1)d_p \equiv e^{-1} \mod (p-1) に対して一部のビットを反転させ、 gdpmodrg^{d_p} \mod r を計算したものを返す

    という流れになっています。我々が表面上でアクセスできるのは dpd_p に関する値についてのみなので、 dpd_pp,qp, qkey の順に求めていきます。


    dpd_p の計算

    26回までビットの反転を試行することができます。 dpd_p は512ビット程度なので1回で20ビット程度求められる方針であれば良さそうです。

    dpd_p の下位ビットから i(0i<512)i (0\le i < 512) 番目のビットを反転させると、gdpg^{d_p} の値は、もともとの dpd_pii 番目のビットが1ならば g2ig^{-2^i}、0ならば g2ig^{2^i} 倍に変化します。なので20ビットずつ各ビットがもともとどちらの値だったかについて全探索すれば dpd_p が求まります。

    leak_dp.py
    from pwn import remote
    
    _r = remote("crypto.be.ax", 6003)
    a_str = _r.recvline().strip().decode()[3:]
    b_str = _r.recvline().strip().decode()[3:]
    iv = _r.recvline().strip().decode()[4:]
    N = int(_r.recvline().strip().decode()[3:])
    e = int(_r.recvline().strip().decode()[3:])
    g = int(_r.recvline().strip().decode()[3:])
    r = int(_r.recvline().strip().decode()[3:])
    ct = _r.recvline().strip().decode()[16:]
    assert len(ct) == 160
    
    M = 21
    
    _r.sendlineafter("> ", "00")
    base = int(_r.recvline().strip().decode()[6:])
    rets = []
    for start_idx in range(0, 512, M):
        m = 2**(start_idx+M)-2**(start_idx)
        _r.sendlineafter("> ", hex(m))
        ret = int(_r.recvline().strip().decode()[6:])
        rets.append(ret)
    
    dp_bits_rec = []
    for start_idx, ret in zip(range(0, 512, M), rets):
        print(start_idx)
        tmp_ans = ret
        for i in range(2**M):
            bits = []
            for _ in range(M):
                bits.append(i % 2)
                i //= 2
            diff = 0
            for idx, b in enumerate(bits):
                if b == 0:
                    diff += 2 ** (start_idx+idx)
                else:
                    diff -= 2 ** (start_idx+idx)
            tmp = base * pow(g, diff, r)
            if tmp == tmp_ans:
                dp_bits_rec += bits
                print("found!")
                base = tmp_ans
                break
        else:
            print("something went wrong...")
    dp_rec = int("".join(map(str, dp_bits_rec))[::-1], 2)

    p,qp, q の計算

    dpe1mod(p1)d_p e \equiv 1 \mod (p - 1) であることを利用します。 dpe1d_p e-1 を素因数分解し、素因数の積 +1 が NN を割り切れるような集合を探し出しました。コードは省略。


    key の計算

    p,qp, q が求まったので、 pp のビット列を生成するような key を逆算していきます。

    GF\mathrm{GF} 上の計算よくわかっていないのですが、 sagemath をいじっていたら .matrix() という method を発見しました。これは GF 上の a,ba, b について、 aa を matrix 表記、 bb を vector 表記することで abab の積計算を線形な計算に置き換えられていそうでした。

    例えばこの RNG で最初に生成されるビットは a*key+b の 0-6ビットの和となりますが、これは 0-6 番目までが1のベクトル l=(1,,1,0,,0)l = (1, \cdots, 1, 0, \cdots, 0) を使って、 l(AkT+bT)l(Ak^T + b^T) と表せます。ここで AAa の行列表記、 k,bk, b はそれぞれ key, b のベクトル表記です。次のビットは l(A2kT+AbT+bT)l(A^2k^T + Ab^T + b^T) と表せます。

    このようにして連続する128ビットについて連立方程式が立てられ、線形計算で kk が求まります。注意点としては p,qp, q はどちらが最初の512ビットかわからないことと、一番最初のビットは必ず1になっているのでこの計算には使わないようにすることですかね。

    (いろいろ試行錯誤していた流れがあり、↓のコードは結構汚いです…)

    solve.sage
    from binascii import unhexlify
    
    from Crypto.Cipher import AES
    from Crypto.Util.number import long_to_bytes
    
    
    x = GF(2).polynomial_ring().gen()
    F = GF(2 ** 128, name="A", modulus=x^128+x^7+x^2+x+1)
    
    
    def toF(x):
        return F.fetch_int(x)
    
    
    def fromF(x):
        x = x.integer_representation()
        return x
    
    
    def toV(n):
        vec = vector(F, 128)
        vec[:] = map(F, f"{n:0128b}"[::-1])
        return vec
    
    
    def fromV(vec):
        ret = 0
        for i in range(128):
            ret += int(vec[i]) * 2**i
        return ret
    
    
    def FtoV(f):
        return toV(fromF(f))
    
    
    def VtoF(v):
        return toF(fromV(v))
    
    
    ds = [b]
    for _ in range(500):
        ds.append(ds[-1] * a + b)
    d_bit_dict = {}
    for i in range(500):
        d = ds[i]
        d_bit_dict[i] = int(sum(map(int, bin(fromF(d) % 2**7)[2:])) % 2)
    
    p_bits = list(map(int, bin(p)[2:]))
    
    l = vector(F, 128)
    for i in range(7):
        l[i] = 1
    
    A = matrix(F, 128, 128)
    for i in range(2, 130):
        tmp = l * (a^(i)).matrix()
        A[i-2] = tmp
    B = vector(F, 128)
    for i in range(2, 130):
        B[i-2] = p_bits[i-1] ^^ d_bit_dict[i-1]
    key_vec_rec = A.solve_right(B)
    bytekey = long_to_bytes(int(''.join(list(map(str, key_vec_rec))), 2))
    cipher = AES.new(bytekey, AES.MODE_CBC, IV=unhexlify(iv))
    cipher.decrypt(unhexlify(ct))
    
    # p, q が入れ替わっていた場合、さらに512ビット分元に戻す必要がある
    key_vec_rec = A.solve_right(B)
    key_rec = VtoF(key_vec_rec)
    key_rec_saved = key_rec
    for i in range(512):
        key_rec = key_rec - b
        key_rec = key_rec / a
    key_vec_rec = FtoV(key_rec)
    bytekey = long_to_bytes(int(''.join(list(map(str, key_vec_rec))), 2))
    cipher = AES.new(bytekey, AES.MODE_CBC, IV=unhexlify(iv))
    cipher.decrypt(unhexlify(ct))

    corctf{4nd_a_l1ttl3_bit_0f_gr3en_0ni0ns_on_t0p_dcca3160ef8135ea}

    mystery_stream

    10 solves

    pub.sage
    R.<x> = PolynomialRing(GF(2), 'x')
    poly = [REDACTED]
    assert poly.degree() == 64
    M = [poly.list()[1:]]
    for i in range(63):
        M.append([1 if j == i else 0 for j in range(64)])
    M = Matrix(GF(2), M)
    A = M^[REDACTED]
    E, S = A.eigenspaces_right(format='galois')[0]
    assert E == 1
    keyvec = S.random_element()
    key = int(''.join([str(d) for d in keyvec]), 2)
    print(key)
    source.py
    from random import randrange
    from secrets import flag, key
    from Crypto.Util.number import long_to_bytes
    
    def bsum(state, taps, l):
        ret = 0
        for i in taps:
            ret ^= (state >> (l - i))
        return ret & 1
    
    class Gen:
        def __init__(self, key, slength):
            self.state = key
            self.slength = slength
            self.TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32, 
            33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64]
    
        def clock(self):
            out = bsum(self.state, self.TAPS, self.slength)
            self.state = (out << (self.slength - 1)) + (self.state >> 1)
            return out
    
    def insertflag(fn, flag):
        txt = b''
        with open(fn, 'rb') as f:
            txt = f.read()
        i = randrange(0, len(txt))
        txt = txt[:i] + flag + txt[i:]
        with open(fn, 'wb') as f:
            f.write(txt)
    
    def gf256_multiply(a,b):
      p = 0
      for _ in range(8):
        if b % 2:
          p ^= a
        check = a & 0x80
        a <<= 1
        if check == 0x80:
          a ^= 0x1b
        b >>= 1
      return p % 256
    
    def encrypt(fn, outf, cipher):
        pt = b''
        with open(fn, 'rb') as f:
            pt = f.read()
        ct = b''
        for byte in pt:
            genbyte = 0
            for i in range(8):
                genbyte = genbyte << 1
                genbyte += cipher.clock()
            ct += long_to_bytes(gf256_multiply(genbyte, byte))
        with open(outf, 'wb') as f:
            f.write(ct)
    
    insertflag('pt', flag)
    cipher = Gen(key, 64)
    encrypt('pt', 'ct', cipher)

    pub.sage で出力された key を初期状態として source.pyGen でビット列を生成し、それを使ってフラグを含んだ平文を暗号化しています。

    pub.sage を見ていきます。コードを読むと、ある poly で表された LFSR について、 key のビット列は aa (ここで A=MaA = M^a) だけシフトさせると元の値に戻るようになっていることがわかります。ただし polya も不明です。

    正直自分はこの情報だけでは問題が解けない気がしています… 例えば poly = x^64+x^7+x+1a=2^32-1 のときは key の可能性が8589934592通りもあって正しい key が求まるわけがないため、 polya には何かしらの制約が必要なんじゃないかなと思っています。 このような旨を admin に質問してみたのですが、もっと LFSR を観察してみて、的なことを言われたので、自分の知識が何かしら足りていない or 観察不足かもです。

    ではどう解いたかというとエスパーです。 polyGenTAP と同じ式にし、 a22n12^{2^n} - 1 の形で表される値に絞って探索させ、それぞれのパターンで生成される key を使って復号を試みてフラグが含まれているかを確認していきました。 CTF なのでヨシとします。

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    def bsum(state, taps, l):
        ret = 0
        for i in taps:
            ret ^^= (state >> (l - i))
        return ret & 1
    
    class Gen:
        def __init__(self, key, slength):
            self.state = key
            self.slength = slength
            self.TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32,
            33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64]
    
        def clock(self):
            out = bsum(self.state, self.TAPS, self.slength)
            self.state = (out << (self.slength - 1)) + (self.state >> 1)
            return out
    
    with open("./task/ct", "rb") as f:
        ct = f.read()
    
    X = GF(2).polynomial_ring().gen()
    F = GF(2 ** 8, name="A", modulus=X^8+X^4+X^3+X+1)
    PR.<x> = PolynomialRing(F)
    
    def toF(x):
        return F.fetch_int(x)
    
    def fromF(x):
        x = x.integer_representation()
        return x
    
    R.<x> = PolynomialRing(GF(2), 'x')
    TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32, 33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64]
    poly = 0
    for t in TAPS:
        poly += x^t
    M = [poly.list()[1:]]
    for i in range(63):
        M.append([1 if j == i else 0 for j in range(64)])
    M = Matrix(GF(2), M)
    for h in [4, 8, 16, 32, 64]:
        A = M^(2**h-1)
        E, S = A.eigenspaces_right(format='galois')[0]
        print(h, len(S))
        if E != 1:
            print(E)
            continue
        for keyvec in S[:100]:
            print(keyvec)
            key = int(''.join([str(d) for d in keyvec]), 2)
            cipher = Gen(key, 64)
            pt = b""
            for byte in ct:
                genbyte = 0
                for i in range(8):
                    genbyte = genbyte << 1
                    genbyte += cipher.clock()
                try:
                    pt += long_to_bytes(fromF(toF(byte) / toF(genbyte)))
                except ZeroDivisionError:
                    pt += b"\x00"
                    break
            if b"corctf" in pt:
                idx = pt.find(b"corctf")
                print(pt[idx: idx+100])

    corctf{p3ri0dic4lly_l00ping_on_4nd_on...}

    bank

    25 solves

    server.py
    import numpy as np
    import math, random
    
    flag = open('flag.txt').read()
    
    class Qubit:
        def __init__(self, vector):
            self.vec = vector
    
        def x(self):
            mat = np.array([[0, 1], [1, 0]])
            self.vec = mat.dot(self.vec)
    
        def y(self):
            mat = np.array([[0, -1j], [1j, 0]])
            self.vec = mat.dot(self.vec)
    
        def z(self):
            mat = np.array([[1, 0], [0, -1]])
            self.vec = mat.dot(self.vec)
    
        def h(self):
            mat = np.array([[1/math.sqrt(2), 1/math.sqrt(2)], [1/math.sqrt(2), -1/math.sqrt(2)]])
            self.vec = mat.dot(self.vec)
    
        def rotate(self, angle):
            mat = np.array([[1, 0], [0, np.exp(1j * angle)]])
            self.vec = mat.dot(self.vec)
    
        def measure(self, basis):
            if basis == '01':
                if random.random() < np.linalg.norm(self.vec[0]) ** 2:
                    self.vec = np.array([[1], [0]])
                    return '0'
                else:
                    self.vec = np.array([[0], [1]])
                    return '1'
            elif basis == '+-':
                pvec = np.array([[1/math.sqrt(2)], [1/math.sqrt(2)]])
                prob = np.linalg.norm(self.vec.T.dot(pvec)) ** 2
                if random.random() < prob:
                    self.vec = pvec
                    return '+'
                else:
                    self.vec = np.array([[1/math.sqrt(2)], [-1/math.sqrt(2)]])
                    return '-'
            else:
                raise ValueError('Invalid basis to measure on')
        
        @staticmethod
        def from_str(symbol):
            if symbol == '0':
                return Qubit(np.array([[1], [0]]))
            elif symbol == '1':
                return Qubit(np.array([[0], [1]]))
            elif symbol == '+':
                return Qubit(np.array([[1/math.sqrt(2)], [1/math.sqrt(2)]]))
            elif symbol == '-':
                return Qubit(np.array([[1/math.sqrt(2)], [-1/math.sqrt(2)]]))
            raise ValueError('Invalid symbol to construct qubit with')
    
    print('Welcome to the CoR bank!')
    print("We're currently running a special promotion where new accounts receive one free dollar. Terms and conditions apply.")
    choice = input('Would you like an account? (y/n) ')
    
    if choice.lower() == 'n':
        print('Well what did you connect for? Stop wasting my time')
        exit()
    elif choice.lower() != 'y':
        print('Bruh')
        exit()
    
    symbols = ['0', '1', '+', '-']
    bill = [random.choice(symbols) for _ in range(50)]
    qubits = [Qubit.from_str(s) for s in bill]
    
    print('New account made! Enjoy your $1.')
    print()
    
    while True:
        print('What would you like to do with your account?')
        print()
        print('1. Work with qubits')
        print('2. Buy flag')
        print('3. Quit')
    
        choice = input('> ')
        if choice == '1':
            idx = int(input('Please input the index of the qubit you wish to work with: '))
            while True:
                print('What operation would you like to perform?')
                print()
                print('1. Apply X gate')
                print('2. Apply Y gate')
                print('3. Apply Z gate')
                print('4. Apply Hadamard gate')
                print('5. Apply rotation gate')
                print('6. Measure qubit in 0/1 basis')
                print('7. Measure qubit in +/- basis')
                print('8. Verify qubit')
                print('9. Back')
                op = input('> ')
                if op == '1':
                    qubits[idx].x()
                elif op == '2':
                    qubits[idx].y()
                elif op == '3':
                    qubits[idx].z()
                elif op == '4':
                    qubits[idx].h()
                elif op == '5':
                    angle = float(input('Input angle to rotate by (in radians): '))
                    if np.isnan(angle) or np.isinf(angle):
                        print('Pepega')
                    else:
                        qubits[idx].rotate(angle)
                elif op == '6':
                    print('The qubit measured as', qubits[idx].measure('01'))
                elif op == '7':
                    print('The qubit measured as', qubits[idx].measure('+-'))
                elif op == '8':
                    actual = bill[idx]
                    if actual in '01':
                        measured = qubits[idx].measure('01')
                    else:
                        measured = qubits[idx].measure('+-')
                    if actual == measured:
                        print('Qubit successfully verified.')
                    else:
                        print('Incorrect qubit!')
                elif op == '9':
                    break
                else:
                    print('Invalid operation.')
                    exit()
        elif choice == '2':
            print('Flags cost $1.')
            qstr = input('Enter your bill: ')
            if qstr == ''.join(bill):
                print('Congratulations!', flag)
            else:
                print('Are you trying to scam me?')
                exit()
        else:
            print('Cya')
            exit()

    量子回路の問題。50個の qubit があり、それぞれ 01+- のどれかになっています。これを様々なゲートや観測を駆使して同定することができればフラグが入手できます。

    使えるゲートは X,Y,Z,H,RzX, Y, Z, H, R_z の5種類で、観測は 01 の基底か +- の基底かで行えますが、それに加えて正解の状態の基底 (正解が + なら +- の基底、正解が 0 なら 01 の基底) で観測が行えます。 この正解の状態の基底での観測は、 qubit がいかなる状態にあっても元の正解の基底に戻ります。そして観測後の状態が正解に一致しているかもわかるので、その観測後に適切なゲートを使えば正解の状態に必ず戻すことができます。これを利用しない手はないです。

    6 (01 基底での観測) → 8 (正解基底での観測) → [Incorrect qubit ならば] 2 (Y) という一連の処理を数回回すことを考えます。もし正解が 01 のいずれかならば、 01 基底での観測は必ず同じ値 (正解の値) を返します。一方で正解が +- のときは 0 1 が半々の確率で観測されます。これにより正解が 01+- か切り分けることができます。 01 の場合は正解も特定できます。 +- のときはこの一連の操作の後に +- の基底で観測を行えば正解がわかります。

    これで解けるはずで実際に socat で local にサーバーを動かして実験してみたら機能したのですが、 remote では動かなかったです… 精度の問題かなと考え、複素数を使っている Y ゲートを XZ に置き換えたら動きました。謎

    solve.py
    from collections import Counter
    
    from pwn import remote
    
    _r = remote("crypto.be.ax", 6005)
    _r.sendlineafter("(y/n) ", "y")
    ans = ""
    for idx in range(50):
        print(idx)
        cnt = Counter()
        _r.sendlineafter("> ", "1")
        _r.sendlineafter(": ", str(idx))
        for _ in range(7):
            # op == 6
            _r.sendlineafter("> ", "6")
            _r.recvuntil("The qubit measured as ")
            res = _r.recvline().strip().decode()
            cnt[res] += 1
            # op == 8
            _r.sendlineafter("> ", "8")
            ret = _r.recvline().strip().decode()
            if "success" in ret:
                continue
            else:
                # _r.sendlineafter("> ", "2")  # not work...
                _r.sendlineafter("> ", "1")
                _r.sendlineafter("> ", "3")
                continue
        print(cnt)
        if len(cnt) == 1:
            ans += cnt.most_common()[0][0]
        else:
            # op == 7
            _r.sendlineafter("> ", "7")
            _r.recvuntil("The qubit measured as ")
            res = _r.recvline().strip().decode()
            ans += res
        _r.sendlineafter("> ", "9")
        print(ans)
    _r.sendlineafter("> ", "2")
    _r.sendlineafter(": ", ans)
    print(_r.recvline())
    _r.close()

    corctf{4lw4ys_d3str0y_y0ur_f4k3s}

    LCG_k

    25 solves

    source.py
    from Crypto.Util.number import bytes_to_long, inverse
    from hashlib import sha256
    from secrets import randbelow
    from private import flag
    from fastecdsa.curve import P256
    
    G = P256.G
    N = P256.q
    
    class RNG:
        def __init__(self, seed, A, b, p):
            self.seed = seed
            self.A = A
            self.b = b
            self.p = p
    
        def gen(self):
            out = self.seed
            while True:
                out = (self.A*out + self.b) % self.p
                yield out
    
    def H(m):
        h = sha256()
        h.update(m)
        return bytes_to_long(h.digest())
    
    def sign(m):
        k = next(gen)
        r = int((k*G).x) % N
        s = ((H(m) + d*r)*inverse(k, N)) % N
        return r, s
    
    def verify(r, s, m):
        v1 = H(m)*inverse(s, N) % N
        v2 = r*inverse(s, N) % N
        V = v1*G + v2*pub
        return int(V.x) % N == r
    
    seed, A, b = randbelow(N), randbelow(N), randbelow(N)
    lcg = RNG(seed, A, b, N)
    gen = lcg.gen()
    d = randbelow(N)
    pub = d*G
    mymsg = b'i wish to know the ways of the world'
    
    print('public key:', pub)
    signed_hashes = []
    
    for _ in range(4):
        m = bytes.fromhex(input('give me something to sign, in hex>'))
        h = H(m)
        if m == mymsg or h in signed_hashes:
            print("i won't sign that.")
            exit()
        signed_hashes.append(h)
        r, s = sign(m)
        print('r:', str(r))
        print('s:', str(s))
    print('now, i want you to sign my message.')
    r = int(input('give me r>'))
    s = int(input('give me s>'))
    if verify(r, s, mymsg):
        print("nice. i'll give you the flag.")
        print(flag)
    else:
        print("no, that's wrong.")

    ECDSA の問題。 nonce の k が LCG で生成されています。4回署名をすることができます。

    式で書くと ki=H(mi)si1+dr0s01(0i<4)k_i = H(m_i) s_i^{-1} + dr_0 s_0^{-1} (0\le i<4), ki=Aki1+b(1i<4) k_i= Ak_{i-1} + b (1\le i < 4) となります。未知の値が ki(0i<4),d,A,bk_i (0\le i<4), d, A, b の7個、等式の数も7個なので連立して解くことができます。

    あとは solver に投げるだけかと思いきや、 sage 力が低すぎていい方法が見つかりませんでした… solve_mod も mod の数が大きすぎてエラーが…

    ということでまごころこもった手計算をしていきます。簡単のため、 ci=H(mi)si1,ei=risi1c_i = H(m_i) s_i^{-1}, e_i = r_i s_i^{-1} とおくと ki=ci+deik_i = c_i + de_i とかけます。

    まず LCG の関係性から kik_i を全て消去します。

    {c1+de1Ac0Ade0=bc2+de2Ac0Ade1=bc3+de3Ac0Ade2=b\left\{ \begin{align*} c_1 + d e_1 - Ac_0 - Ade_0 &= b \\ c_2 + d e_2 - Ac_0 - Ade_1 &= b \\ c_3 + d e_3 - Ac_0 - Ade_2 &= b \end{align*} \right.

    それぞれの式の差を取って bb を消去します。

    {c1c2+d(e1e2)A(c0c1)Ad(e0e1)=0c2c3+d(e2e3)A(c1c2)Ad(e1e2)=0\left\{ \begin{align*} c_1 - c_2 + d(e_1 - e_2) - A(c_0 - c_1) - Ad(e_0 - e_1) &= 0 \\ c_2 - c_3 + d(e_2 - e_3) - A(c_1 - c_2) - Ad(e_1 - e_2) &= 0 \\ \end{align*} \right.

    片方の式から d=Ax+yd = Ax + y という形にしたときの x,yx, y が求まるので、これをもう片方の式に代入し、2次方程式を解くことで A,dA, d が求まります。 あとは dd を使って適当に署名を作るだけです。

    こんな手計算二度とやりたくないのでいい方法を募集しております。

    solve.sage
    from hashlib import sha256
    
    from Crypto.Util.number import bytes_to_long, inverse
    from pwn import remote, context
    
    N = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    
    EC = EllipticCurve(GF(115792089210356248762697446949407573530086143415290314195533631308867097853951), [-3, 41058363725152142129326129780047268409114441015993725554835256314039467401291])
    G = EC(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109)
    
    mymsg = b"i wish to know the ways of the world"
    
    
    def H(m):
        h = sha256()
        h.update(m)
        return bytes_to_long(h.digest())
    
    
    signed_hashes = [H(b"\x00"), H(b"\x01"), H(b"\x02"), H(b"\x03")]
    
    _r = remote("crypto.be.ax", 6002)
    context.log_level = "DEBUG"
    
    pub_x = int(_r.recvline()[15:].strip().decode(), 16)
    pub_y = int(_r.recvline()[3:].strip().decode(), 16)
    
    rs = []
    ss = []
    for i in range(4):
        _r.sendlineafter("hex>", f"{i:02d}")
        r = int(_r.recvline().decode().strip()[3:])
        s = int(_r.recvline().decode().strip()[3:])
        rs.append(r)
        ss.append(s)
    
    cs = []
    es = []
    for r, s, h in zip(rs, ss, signed_hashes):
        cs.append(h * pow(s, -1, N))
        es.append(r * pow(s, -1, N))
    
    coeff_d = (es[1] - es[2]) ** 2 - (es[2] - es[3]) * (es[0] - es[1])
    coeff_d_inv = pow(coeff_d, -1, N)
    coeff_A = (cs[0] - cs[1]) * (es[1] - es[2]) - (cs[1] - cs[2]) * (es[0] - es[1])
    coeff_c = (cs[2] - cs[3]) * (es[0] - es[1]) - (cs[1] - cs[2]) * (es[1] - es[2])
    x = coeff_A * coeff_d_inv
    y = coeff_c * coeff_d_inv
    
    R = Integers(N)
    P.<A> = PolynomialRing(R)
    f = - x * (es[0] - es[1]) * A^2 + (x * (es[1] - es[2]) - (cs[0] - cs[1]) - y * (es[0] - es[1])) * A + cs[1] - cs[2] + y * (es[1] - es[2])
    roots = f.roots()
    d0 = roots[0][0] * x + y
    d1 = roots[1][0] * x + y
    d = d0 if int((int(d0) * G)[0]) == pub_x else d1
    k = 2
    r = int((k * G)[0])
    s = int((H(mymsg) + d * r) * pow(k, -1, N) % N)
    
    _r.sendlineafter("give me r>", str(r))
    _r.sendlineafter("give me s>", str(s))
    _r.recvline()
    print(_r.recvline())

    corctf{r3l4ted_n0nce5_4re_d4n6er0us_fde6ebafa842716a}

    babyrand

    29 solves

    script.py
    from random import randrange
    from Crypto.Util.number import getPrime, long_to_bytes
    from Crypto.Cipher import AES
    from Crypto.Util.Padding import pad
    from hashlib import sha256
    from os import urandom
    
    flag = open("flag.txt", "rb").read()
    
    def und():
      p = getPrime(512)
      x = randrange(p)
      a = p ^ x ^ randrange(2**200)
      b = p ^ x ^ randrange(2**200)
      return p, a, b, x
    
    p,a,b,x = und()
    
    iv = urandom(16)
    key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    
    print(f"c1 = {x}")
    print(f"c2 = {(x*a + b) % p}")
    print(f"p = {p}")
    print(f"iv = '{iv.hex()}'")
    print(f"ct = '{cipher.encrypt(pad(flag, 16)).hex()}'")

    a,ba, b の上位ビット (512ビット中312ビット) が既知のとき (pxp \oplus x で求まる)、 xa+bxa +b の値から a,ba, b の下位ビットを特定する問題。 素直に defund/coppersmith を使いましょう。

    solve.sage
    from binascii import unhexlify
    from hashlib import sha256
    
    from Crypto.Cipher import AES
    from Crypto.Util.number import getPrime, long_to_bytes
    
    c1 = 5365904711205493895182988721055598679508066289977091231731349423996531384326997250984304389796311073201846992254794801346573036775490182780952712232258774
    c2 = 2351499357088933835557969576916974229915931074692169825269157710226395480997304497294813272746195475744137017453323338362896396977337638862808560417575150
    p = 12118911800929768381158064532151564397584328623097191996086479213117076586014730135201334840794700976422626122702191630484231703678287738839516304757792517
    iv = 'eacdfb3c2cd33a8ce71dbd9a11be89ad'
    ct = [SNIPPED]
    
    x = c1
    p_x = p^^x
    
    a_sim = p_x//2**200 * 2**200
    b_sim = p_x//2**200 * 2**200
    
    R = Integers(p)
    P.<a_lsb, b_lsb> = PolynomialRing(R)
    f = x * (a_sim + a_lsb) + (b_sim + b_lsb) - int(c2)
    bounds = [2**200, 2**200]
    
    # https://github.com/defund/coppersmith/blob/master/coppersmith.sage
    small_roots(f, bounds, m=3, d=4)
    
    a_lsb = 273155639358510457723153959205563541338008752143905166225685
    b_lsb = 1403848689462465103080809107986474519812315038881484027853938
    a = a_sim + a_lsb
    b = b_sim + b_lsb
    
    key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, unhexlify(iv))
    cipher.decrypt(unhexlify(ct))

    corctf{c0ngr4tul4t10ns_y0u_4r3_n0w_p4rt_0f_th3_d3fund_f4n_club!}

    defund/coppersmith 使ったのバレてた。

    babypad

    35 solves

    server.py
    from Crypto.Cipher import AES
    from Crypto.Util import Counter
    from Crypto.Util.Padding import pad, unpad
    from Crypto.Util.number import bytes_to_long
    import os
    
    flag = open("/challenge/flag.txt").read().encode()
    key = os.urandom(16)
    
    def encrypt(pt):
      iv = os.urandom(16)
      ctr = Counter.new(128, initial_value=bytes_to_long(iv))
      cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
      return iv + cipher.encrypt(pad(pt, 16))
    
    def decrypt(ct):
      try:
        iv = ct[:16]
        ct = ct[16:]
        ctr = Counter.new(128, initial_value=bytes_to_long(iv))
        cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
        pt = cipher.decrypt(ct)
        unpad(pt, 16)
        return 1
      except Exception as e:
        return 0
    
    def main():
      print(encrypt(flag).hex())
      while True:
       try:
        print(decrypt(bytes.fromhex(input("> "))))
       except Exception as e:
        pass
    
    main()

    典型的な padding oracle attack の問題です。バグらせずに一発でソルバー書けたことなし。

    solve.py
    from binascii import unhexlify
    
    from Crypto.Cipher import AES
    from Crypto.Util import Counter
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    from pwn import remote
    
    
    def xor(a, b):
        return bytes([aa ^ bb for aa, bb in zip(a, b)])
    
    
    _r = remote("babypad.be.ax", 1337)
    ret = bytes.fromhex(_r.recvline().strip().decode())
    iv, ct = ret[:16], ret[16:]
    ct_saved = ct
    
    
    def decrypt(ct, verbose=False):
        _r.sendlineafter("> ", ct.hex())
        return int(_r.recvline())
    
    
    ct = ct_saved
    ans = b""
    for idx in range(16, 32)[::-1]:
        print(idx, ans)
        for c in range(0, 256):
            if idx == 31 and c == 0:
                continue
            tmp_ct = ct[:idx] + long_to_bytes(c^ct[idx]) + ct[idx+1:]
            result = decrypt(iv + tmp_ct)
            if not result:
                continue
            ans = long_to_bytes(c ^ ((32 - idx - 1) % 16 + 1)) + ans
            break
        else:
            raise RuntimeError
        ct = tmp_ct
        ct = ct[:idx] + xor(ct[idx:], len(ct[idx:])*long_to_bytes((32-idx)^(32-idx+1)))
    
    
    # 二回も同じようなことを書いているクソコード
    ct = ct_saved[:16]
    for idx in range(16)[::-1]:
        print(idx, ans)
        for c in range(0, 256):
            if idx == 15 and c == 0:
                continue
            tmp_ct = ct[:idx] + long_to_bytes(c^ct[idx]) + ct[idx+1:]
            result = decrypt(iv + tmp_ct)
            if not result:
                continue
            ans = long_to_bytes(c ^ ((16 - idx - 1) % 16 + 1)) + ans
            break
        else:
            raise RuntimeError
        ct = tmp_ct
        ct = ct[:idx] + xor(ct[idx:], len(ct[idx:])*long_to_bytes((16-idx)^(16-idx+1)))
    print(ans)

    corctf{CTR_p4dd1ng?n0_n33d!}

    babyrsa

    50 solves

    RSA の公開鍵 n,en, e と、 p,qp, q の一部のビットが既知です。この問題も defund/coppersmith で p,qp, q を求められます。

    solve.sage
    n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
    e = 0x10001
    ct = 2657054880167593054409755786316190176139048369036893368834913798649283717358246457720021168590230987384201961744917278479195838455294205306264398417522071058105245210332964380113841646083317786151272874874267948107036095666198197073147087762030842808562672646078089825632314457231611278451324232095496184838
    
    R = Integers(n)
    P.<p_unk, q_unk> = PolynomialRing(R)
    
    p = 108294440701045353595867242719660522374526250640690193563048263854806748525172379331 * 10^71 + p_unk * 10^30 + 341078269246532299656864881223
    q = 679098724593514422867704492870375465007225641192338424726642090768164214390632598250 * 10^70 + q_unk * 10^29 + 39563231146143146482074105407
    
    f = p * q
    
    # https://github.com/defund/coppersmith/blob/master/coppersmith.sage
    bounds = (2**136, 2**136)
    p_unk_, q_unk_ = small_roots(f, bounds, m=3, d=4)[0]
    
    p = 108294440701045353595867242719660522374526250640690193563048263854806748525172379331 * 10^71 + p_unk_ * 10^30 + 341078269246532299656864881223
    q = 679098724593514422867704492870375465007225641192338424726642090768164214390632598250 * 10^70 + q_unk_ * 10^29 + 39563231146143146482074105407
    assert p * q == n
    phi = (p - 1) * (q - 1)
    d = int(pow(e, -1, phi))
    print(bytes.fromhex(f"{int(pow(ct, d, n)):x}"))

    corctf{1_w4s_f0rc3d_t0_wr1t3_ch4ll5_4nd_1_h4d_n0_g00d_1d345_pl5_n0_bully_;-;}

      ;