今週土日に開催されていたTSG CTF 2021に出たので自分が解いた問題のWriteupを書きます。

ちなみに3位でした、やったね。チームメイトの皆さんありがとうございました。

他のチームメイトのWriteupはこちら

Beginner's Rev 2021 §

引数に32文字の文字列を与えるよくあるCrackme。check()という関数に引数に与えた文字列のポインタが渡されており、Ghidraで見ると次のようになっている(一部変数をrenameしています)。

ulong check(long param_1)

{
  __pid_t pid;
  int __fd;
  int depth;
  int iVar1;
  uint uVar2;
  long in_FS_OFFSET;
  undefined local_34;
  byte local_33;
  long local_30;
  
  uVar2 = 0;
  iVar1 = 0;
  depth = 0;
  local_30 = *(long *)(in_FS_OFFSET + 0x28);
  do {
    pid = fork();
    iVar1 = iVar1 + 1;
    if (pid == 0) {
      iVar1 = 0;
      uVar2 = uVar2 | 1 << ((byte)depth & 0x1f);
      __fd = open("/dev/null",1);
      dup2(__fd,1);
    }
    depth = depth + 1;
  } while (depth != 5);
  depth = iVar1 + -1;
  __fd = is_correct((ulong)(uint)(int)*(char *)(param_1 + (int)uVar2),(ulong)uVar2);
  _uVar2 = (ulong)(__fd == 0);
  uVar2 = (uint)(__fd == 0);
  if (iVar1 != 0) {
    do {
      depth = depth + -1;
      wait(&local_34);
      uVar2 = (uint)_uVar2 | (uint)local_33;
      _uVar2 = (ulong)uVar2;
    } while (depth != -1);
  }
  if (uVar2 == 0) {
    puts("correct");
  }
  else {
    puts("wrong");
  }
  if (local_30 == *(long *)(in_FS_OFFSET + 0x28)) {
    return (ulong)uVar2;
  }
                    /* WARNING: Subroutine does not return */
  __stack_chk_fail();
}

雑に観察した程度だが、何やら子プロセスの生成を一定の深さになるまで繰り返し(多分32個)、対応したインデックスの文字が合っているかをis_correct()関数でチェックしているように思える。ちなみにis_correct()関数は静的解析したら一生を終えるぐらいには面倒そうだったのでそっ閉じした。

ご丁寧にもあっていれば"Correct"、誤っていれば"wrong"と主力されるので、1文字ずつ与える文字列を確定させていくことが出来そうなのだが、各子プロセスでは標準出力が/dev/nullになっているので目視で確認する事は出来ない。

そこでstraceの力を借りる。標準出力が捨てられていてもwriteシステムコールは呼ばれているはずなので"Correct"か"wrong"をwriteしているシステムコールを探せば対応する文字が合っているかが分かる。また、straceは-fオプションでforkしたプロセスのシステムコールまで捕捉してくれる。

いつものように頭から確定させようと思ったが、考えられる全文字を試しても"correct"が現れない。上記コードをよく見ると中盤でwait()で子プロセスの様子を待っていることから子プロセスで判定した文字が正解でないと自信も正解でないとGuessして下から確定させた。

もちろんこれを全部手動でやるのは骨が折れるので面倒なことをやらされる係ことPythonに投げた。

import subprocess
from string import ascii_letters, digits, punctuation


letters = ascii_letters + digits + punctuation
print(letters)
# TSGCTF{y0u_kN0w_m@ny_g0od_t0015}


def exploit():
    known = b""
    length = 32 - len(known)
    for i in range(length - 1, -1, -1):
        print(i)
        flag = bytearray(b"X" * (i+1) + known)
        for c in letters:
            flag[i] = ord(c)
            cmd = ["strace", "-f", "-o", "output.txt", "./beginners_rev", flag.decode()]
            res = subprocess.run(cmd, stdout=subprocess.DEVNULL)
            output_res = open("output.txt").read()
            cnt = output_res.count("correct")
            if cnt > 31 - i:
                print("[Found]:", i, c)
                known = c.encode() + known
                break

    print(flag.decode())


if __name__ == "__main__":
    exploit()

Flag: TSGCTF{y0u_kN0w_m@ny_g0od_t0015}

静的解析と動的解析のどちらも要求されてレベル感もちょうどよく、今回のCTFで見た中でかなり好きな問題です。

Minimalist's Private §

次のようなスクリプトとその実行結果が渡される。

from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d

class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d

        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1, self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)

        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

    def encrypt(self, msg):
        return pow(msg, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

flag = open('flag.txt', 'rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)

rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)

print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')

注目すべきは$L$という秘密のパラメータでこいつは$N$未満の任意整数$a$に対して$a^L \equiv 1 \mod N$となっている(正確では任意ではなくランダムに選んだ100個だが十分な数である)。という事は多分こいつはカーマイケル関数$\lambda(N) = \mathrm{lcm}(p-1, q-1) = \frac{(p-1)(q-1)}{\mathrm{gcd}(p-1, q-1)}$の倍数だと思われる。

ここで$L^2 \leq 10000N$が成り立っているので、$p-1,q-1$の最大公約数を$g \coloneqq \mathrm{gcd}(p-1)(q-1)$とおき、$L \coloneqq C \lambda(N) \ C \in \mathrm{Z}$とおくと次のような不等式が成り立つ。

$$ \begin{aligned} C^2 \frac{(p-1)^2(q-1)^2}{g^2} &\leq 10000pq \cr \frac{(p-1)(q-1)}{g^2} &\leq 10000 \cr \frac{p-1}{g}\frac{q-1}{g} &\leq 10000 \end{aligned} $$

正確には1行目から2行目の変形は厳密ではない、$p,q$が大きい数なので多分成り立つという仮定で変形した。

ここで$g$が$p-1,q-1$の最大公約数なので$k_p \coloneqq \frac{p-1}{g}, \ k_q \coloneqq \frac{q-1}{g}$とおくと$k_p,k_q$は互いに素で$k_pk_q \leq 10000$が成り立つ。

このような条件を満たす$k_p, k_q$はそこまで多くない(だいたい6万個とちょっと)。これである程度$g$の候補は絞れた事になる。

これらの数値を用いると$N = pq = (k_pg+1)(k_qg + 1) = k_pk_qg^2 + (k_p+k_q)g + 1$が成立する。これは$g$についての2次方程式であり、$g$は整数解の1つである。

ということはこの2次方程式が整数解を持つかどうかを各$k_p,k_q$で判定して、整数解を持つなら$p,q$を求めて$N$が素因数分解されるかどうかを調べればいい。整数解を持つかどうかの判定は判別式が整数になるかどうかを確認した。

このような$k_p,k_q$は対称性を除けば1つに定まり、無事に素因数分解出来た。

使用コードは次の通り

from Crypto.Util.number import long_to_bytes, GCD
from math import isqrt
from xcrypto.rsa import dec_pq


def get_params():
    N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
    c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

    return (N, e), c


def search_k():
    ret = []
    for kp in range(1, 10001):
        for kq in range(1, 10000 // kp + 1):
            if GCD(kp, kq) == 1:
                ret.append((kp,kq))

    return ret


def exploit():
    (N, e), ct = get_params()
    k_cand = search_k()
    print(len(k_cand))
    for kp, kq in k_cand:
        a = kp*kq
        b = kp + kq
        c = -(N - 1)
        D = b**2 - 4*a*c
        sqrtD = isqrt(D)
        if sqrtD**2 != D:
            continue
        for sig in [-1, 1]:
            g = None
            nume = -b + sig * sqrtD
            denom = 2*a
            if nume % denom == 0:
                g = nume // denom

            if g is not None:
                p = g*kp + 1
                q = g*kq + 1
                flag = dec_pq(ct, p, q, e)
                print(long_to_bytes(flag))



if __name__ == "__main__":
    exploit()

Flag: TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}

Baba is Flag §

フラグを提出したのは別のチームメイトですが、解法の半分ぐらいを考えた+自分で解けるスクリプトを書いたので書きます。

次のようなスクリプトが与えられる。

require 'openssl'
require 'digest'

STDOUT.sync = true

class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end

class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end

  def inv(x)
    x.pow(@n - 2, @n)
  end

  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy

    # We all like hacks, ain't we?
    # s = (z + x * @d) * inv(k) % @n
    s = (z + @d) * inv(k) % @n

    return x, s
  end

  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex

    # ditto
    # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy

    return x == x2
  end
end

ecdsa = ECDSA.new

5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS

  print 'choice? '

  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i

    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end

puts 'You is defeat.'

ECDSAで使われている$x$が$s$の計算で用いられていない。この事実によって署名の検証は$\frac{z}{s}G + \frac{Q}{s}$のx座標と等しい数字を与えたかどうかになる。

という事はもし$Q$がわかっていれば(通常のECDSAであれば分かっている)、任意$z$に対して適当な$s$を持ってきて右辺を計算することで署名を生成出来てしまう。

この事実をチームメイトから言われてから、与えられた'Baba'の署名$r,s$から、$sP - zG = Q$である事に気付いて共有したら解いてくれた。ここで$P$はx座標が$r$である点であり、署名に使われたnonce$k$を用いると$P = kG$を満たす。なお、該当する点は2つ存在するので外したらもう片方を試せば良い。

使用コードは次の通り

from pwn import remote
from hashlib import sha256
from Crypto.Util.number import long_to_bytes, bytes_to_long


def create_conn():
    host = "34.146.212.53"
    port = 65434
    return remote(host, port)


def get_params():
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    a= 0
    b = 7
    order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
    G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

    return (p, a, b, order), G


def exploit():
    (p, a, b, order), G = get_params()
    curve = EllipticCurve(GF(p), [a, b])
    assert order == curve.order()
    sc = create_conn()
    sigs = []
    for _ in range(1):
        sc.recvuntil(b"choice? ")
        sc.sendline(str(1).encode())
        sc.recvuntil(b"x = ")
        x = int(sc.recvline())
        sc.recvuntil(b"s = ")
        s = int(sc.recvline())
        sigs.append((x,s))

    print(sigs)

    x,s = sigs[0]
    inv_s = inverse_mod(s, order)
    G = curve(G)
    P = curve.lift_x(GF(p)(x))
    z = bytes_to_long(sha256(b"Baba").digest())
    Q = s*P - z * G

    _z = bytes_to_long(sha256(b"Flag").digest())
    rhs = _z * inv_s * G + inv_s * Q
    _x, _y = rhs.xy()
    print(_x, s)

    sc.recvuntil(b"choice? ")
    sc.sendline(str(2).encode())
    sc.recvuntil(b"know? ")
    sc.sendline(b"Flag")
    sc.recvuntil(b"x? ")
    sc.sendline(str(_x).encode())
    sc.recvuntil(b"s? ")
    sc.sendline(str(s).encode())

    sc.interactive()



if __name__ == "__main__":
    exploit()

Flag: TSGCTF{HACKER_IS_YOU._POINT_IS_MOVE._POINT_ON_CURVE_IS_HACKED._YOU_IS_WIN.}

kの作り方が異常な上にやや短いのでBiased Nonce Attackを疑い、ずっとそれを試したせいで簡単な解法を見逃してしまった。ちなみに続編のFlag is WinではBiased Nonce Attackが想定解らしいのですが解けませんでした、格子錬成力が足りない。

[Misc] Baba is Flag §

CTF終了後に運営のmoraさんがこんなツイートをしていたので、皆さんもBaba is Youを起動してカスタムレベルを有効にしてプレイしましょう。もちろんCTFプレイヤーの皆さんなら既に購入していますよね?していないなら今直ぐ購入しましょう。

(解けたので500点くれませんか?順位も変動しないし...)

Others §

フラグは提出していないし貢献度も微妙でしたが、ある程度考えた問題について大雑把に書いておきます。

This is DSA §

通常のDSAでは$p-1 | q$が成り立っているが、その制約を外したらどうなる?という問題。pycryptodomeの該当チェックを削除してこれが用いられている。

実はpycryptodomeのDSAの$p,q$のチェックではコメントアウトで「$p,q$は素数」と書いているにも関わらず、$q$が素数なら$p$が合成数であってもチェックを通過する。

該当箇所はこの辺りから。

ちなみに本家pycryptodomeを見に行ったら直ってなかった。((key.p - 1) % key.q) != 0エラーのお陰で多分影響は無いんだと思う、多分。

って思ったら作問者のhakatashiさんがプルリクを出してました。以前送ったのと合わせてmergeされてほしいです。

というわけで$p = q^2C$のような$p$を提出すれば$\phi(p) = q(q-1)C'$のようになって$p$の法の下では乗法の位数が$q$であるものが存在し、それを$g$として提出すればその下のチェックも通る。

このようにして作られた$p,q,g$でも$g$の位数が$q$の位数である事に苦しんで離散対数問題を上手く解くことが出来ず悩んでいたが、上記の事実をまとめて投げたら、kurenaif大先生が任意署名の片割れ$r$が1になる事に気付いて解いていた。

kurenaifさんのWriteup Streamはページ上部にリンクを載せたのでそちらからどうぞ。