corCTF 2021 Writeup

August 23, 2021

crypto fried_rice mystery_stream bank LCG_k babyrand babypad babyrsa

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!")

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

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

という流れになっています。我々が表面上でアクセスできるのは $d_p$ に関する値についてのみなので、 $d_p$ → $p, q$ → key の順に求めていきます。

$d_p$ の計算

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

$d_p$ の下位ビットから $i (0\le i < 512)$ 番目のビットを反転させると、 $g^{d_p}$ の値は、もともとの $d_p$ の $i$ 番目のビットが1ならば $g^{-2^i}$ 、0ならば $g^{2^i}$ 倍に変化します。なので20ビットずつ各ビットがもともとどちらの値だったかについて全探索すれば $d_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, q$ の計算

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

key の計算

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

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

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

このようにして連続する128ビットについて連立方程式が立てられ、線形計算で $k$ が求まります。注意点としては $p, 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.py の Gen でビット列を生成し、それを使ってフラグを含んだ平文を暗号化しています。

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

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

ではどう解いたかというとエスパーです。 poly を Gen の TAP と同じ式にし、 a を $2^{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, 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回署名をすることができます。

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

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

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

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

\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.

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

\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 + y$ という形にしたときの $x, y$ が求まるので、これをもう片方の式に代入し、2次方程式を解くことで $A, d$ が求まります。あとは $d$ を使って適当に署名を作るだけです。

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

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, b$ の上位ビット (512ビット中312ビット) が既知のとき ( $p \oplus x$ で求まる)、 $xa +b$ の値から $a, 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, e$ と、 $p, q$ の一部のビットが既知です。この問題も defund/coppersmith で $p, 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_;-;}

crypto fried_rice mystery_stream bank LCG_k babyrand babypad babyrsa