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

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

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

Table of Contents §

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}')

注目すべきはという秘密のパラメータでこいつは未満の任意整数に対してとなっている(正確では任意ではなくランダムに選んだ100個だが十分な数である)。という事は多分こいつはカーマイケル関数の倍数だと思われる。

ここでが成り立っているので、の最大公約数をとおき、とおくと次のような不等式が成り立つ。

$$ \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行目の変形は厳密ではない、が大きい数なので多分成り立つという仮定で変形した。

ここでの最大公約数なのでとおくとは互いに素でが成り立つ。

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

これらの数値を用いるとが成立する。これはについての2次方程式であり、は整数解の1つである。

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

このようなは対称性を除けば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座標と等しい数字を与えたかどうかになる。

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

この事実をチームメイトから言われてから、与えられた'Baba'の署名から、である事に気付いて共有したら解いてくれた。ここではx座標がである点であり、署名に使われたnonceを用いるとを満たす。なお、該当する点は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ではが成り立っているが、その制約を外したらどうなる?という問題。pycryptodomeの該当チェックを削除してこれが用いられている。

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

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

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

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

というわけでのようなを提出すればのようになっての法の下では乗法の位数がであるものが存在し、それをとして提出すればその下のチェックも通る。

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

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

Beginner's Crypto 2021 §

※元々ここには別解と称した何かがあったのですが、指数法則を間違えていることが判明したのでコメントアウトしました。困惑させてしまった方にはこの場を借りてお詫び申し上げます。

感想 §

去年はPwnを1つ解いて1つ助言を与えた程度でしたが、今回は2つ解いて1つ助言与えたのでそれなりに貢献出来たかなと思います(ところでPwnはいつ再開するんですか?すいません...)。

と、思ったらWeb、Misc、Pwnのチームメイト各位が低Solvesの問題を埋めていたし、Cryptoも一番難しいThis is DSAはkurenaifさんが通してくれたのでまだまだ精進が足りない事を実感しました。

最後にTSGの皆様、今年も高クオリティでTSGらしい(上手く形容し辛いがそのようなものを感じる)問題を提供していただきありがとうございました、今年はBeginnerタグがしっかりBeginnerとして機能していたらしく(但しWebを除く)、年々大衆向けに進化している様子も見られますが、来年以降も変わらないスタイルでCTFを開催していただけますと幸いです。