12月に解いたSECCON CTF 2020の問題を解説する

この記事はDeNA 21 新卒 Advent Calendar 2020の20日目の記事です。記事の内容は個人の見解であり、所属する組織を代表するものではありません。

前書き

DeNAの記事に限った話では無いですが、Qiita記事はやはり仕事に近い内容としてWeb技術に関するものがほとんどだなぁと思いました。勿論仕事に関連する記事は書きやすいですし、僕自身も研究に近い内容であるパケットキャプチャーの基礎的な内容の怪しい記事をDeNA 21 新卒 Advent Calendarにて載せています。

なら、折角なのでより得意・より異端な方へ。DeNA Advent CalendarにCTF(Capture The Flag)の問題解説をひたすら載せてみましょう、となりました。12月の初めからSECCON CTF 2020の問題を解き始め、記事投稿日までに解いた問題の解説をします。10月辺りにあったコンテストということもあり、既に他の人のwriteupは整っていると思います。多少予備知識の説明も行うつもりでいますが、分かり辛かった場合はそちらを参照してもらうとヒントが拾えたりするかと。

対象読者

• セキュリティに興味はある。敷居が高いからつらい
• 攻撃手法の概念は知っている（バッファオーバーフローとか）。「では、実際にそのコード書けますか？」と言われて手が止まる人
• 見出し見ると分かりますがCrypto（暗号）とRev（リバースエンジニアリング）しか出来ていないです。WebのXSSやSQLiに興味があったり、Pwnに興味のある人はごめんなさい...（Webは問題を解く環境を作れなかったのです。この後頑張ります）

Crypto

暗号の問題が出題されるジャンルです。RSAや楕円曲線暗号をメインとしながら幅広い方式から出題されます。

予備知識

この後の問題解説を読むにあたって最低限持っている必要があると思うポイントです。実際に解く際には問題を解いて身に付く直感的な部分があったりするのですが、その辺りはどうしようもないものとしています。

かなりざっくり説明しているため、詳しく知りたい方は別途検索をかけていただけますと幸いです。

RSAの原理

シンプルなこともあり、最も有名（だと僕は思っています）な暗号方式です。

• 複合する人しか知らない情報（秘密鍵）: 大きな素数$p$,$q$、$\phi=(p-1)(q-1)$と互いに素な数$e$と$ed\equiv 1(\mod\phi)$となる$d$
• みんな知っている情報（公開鍵）: $N=pq$、$e$
• 平文（暗号化前のメッセージ）を暗号化する方法: $m\equiv c^e(\mod N)$
• 暗号文$m$を復号して$c$に戻す方法: $c\equiv m^d(\mod N)$

この暗号方式は、$N$を素因数分解出来ないことが暗号の強さになっています。

楕円曲線暗号の原理

RSAよりも短く同等の安全性を確保出来ます。

• $y^2\equiv x^3 + ax + b(\mod N)$という式を作成するため、$N$、$a$、$b$を定義する。これを満たす$(x,y)\in\mathbb{N}^2$は有限である。
• 加法を「2点を結ぶ直線（2点が同一の場合は接線）と上の式のもう1つの交点」と定義する（細かい数式を後で扱いますが、知らなくてもいいでしょう）
• $P=(x,y)$としたときに、$P$を$s$回足し合わせた$Q=(X,Y)=sP$と$P$から$s$を求めるのは難しいです。ここに楕円曲線暗号の強さがあります。

This is RSA

前提知識: RSAの基礎

require 'openssl'

def get_prime
  i = OpenSSL::BN.rand(512).to_s
  i = i.unpack1('H*')
  i = i.hex
  OpenSSL::BN.new(i).prime? ? i : get_prime
end

p = get_prime
q = get_prime
n = p * q
e = 65537
m = File.read('flag.txt').unpack1('H*').hex
c = m.pow(e, n)

puts "N = #{n}"
puts "c = #{c}"

かなりシンプルなRSAの問題。ぱっと見全く問題ないようにも見えます。ただ、get_prime関数の中をちゃんと考えると、unpack1('H*')とi.hexって要らなくないですか？となります。乱数を取って、それが素数ならそれを返す、だけで十分なはずです。ということで、この2命令について細かく調べていきます。ここで行われているのは以下のような操作です。

1. unpack1('H*')により数字を「文字列として見て」、各文字を16進数文字列に変換する。例えば$334$をこれにかけると333334になります。
2. hexにより文字列を「16進数として」数値に変換します。上の例だと$3,355,444$になります。

つまり、pとqは以下の形になっていることが分かります。

\sum_{i=0}^{128}16^{2i+1}\times3 + 16^{2i}\times ({\rm random})

ところで、$N=p\times q$ですよね。$p$と$q$の未知の数について16進数の桁ごとに連立方程式立てたら解けそうじゃないですか？例えば、各それぞれの一番小さい桁は未知数ですが、$N$の下2桁で判明します。

以下のコードでそれを行っていますが、$p$と$q$が分かれば、後は$d$を求めて復号します。

from output import *

print("N=", N)

p = 0
q = 0
base = 1
while True:
    ok = False
    for i in range(10):
        for j in range(10):
            pValue = p + base * (i + 48)
            qValue = q + base * (j + 48)
            if (N - pValue * qValue) % (base * 256) == 0:
                p = pValue
                q = qValue
                ok = True
                break
        if ok:
            break
    if p * q == N:
        break
    base *= 256
    assert p * q < N

assert p * q == N
print("p=", p)
print("q=", q)

def extgcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b, a, x, y, u, v = a, r, u, v, m, n
        g = b
    return x, y, g

e = 65537
d, _, g = extgcd(e, (p - 1) * (q - 1))
assert g == 1
d = (d + (p - 1) * (q - 1)) % ((p - 1) * (q - 1))
assert (e * d) % ((p - 1) * (q - 1)) == 1
print("d=", d)

m = pow(c, d, N)
mArray = []
while m:
    mArray.append(m % 256)
    m //= 256
mArray.reverse()
print(''.join(list(map(chr, mArray))))

koharu

前提知識: sageがある程度使えること。後で知りましたがGoldwasser–Micali cryptosystemという名称らしいです。知っていると早そう。

while True:
    p = random_prime(1<<64)
    if is_prime((p+1) // 2):
        break

with open("flag.txt", "rb") as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")


PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break

while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break

NP = p**P.degree()
NQ = p**Q.degree()

while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break

PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1

print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)

未知の情報は$128$次多項式の$P$と$Q$。多分これが分かっていると、最後の$c$を生成するランダムなアルゴリズムに対して一意に復元する手法が存在するのでしょうか？

と$R$の選定基準と最後$c$に追加されていくコードを考えると、$c^{(NP-1)(NQ-1)/2}(\mod PQ)$をすると多項式が1になるか否かで復元が出来そうな気がします。ところで$NP$と$NQ$は未知です。どうしましょうか。

$PQ=NP\times NQ$って高々long longの128次多項式なんですよね。因数分解出来そうじゃないですか？と雑に因数分解すると64次元の多項式2つに分解することが出来ます。じゃあ復元しましょう！

と思ったら復元できませんでした。全部1になっちゃったんですよね。多分復元式として上に挙げたものが、$R$も消してしまっているようです。なら$R$の条件に忠実に。$c^{(NP-1)/2}(\mod P)$と$c^{(NQ-1)/2}(\mod Q)$はいずれも$S^2$の部分は消えてしまっていると考えられるので、$R$が含まれていない場合のみ$1$になるはずです。

# output.txtの中身をペースト
PR.<x> = PolynomialRing(GF(p))

fac = list(PQ.factor())

P = fac[0][0]
Q = fac[1][0]

NP = p ** P.degree()
NQ = p ** Q.degree()

flag = 0
base = 0

for cVal in c:
  if power_mod(cVal, (NP - 1) // 2, P) == 1 and power_mod(cVal, (NQ - 1) // 2, Q) == 1:
    flag = flag | (1 << base)
  base += 1

print(int(flag).to_bytes(64, 'big'))

sharsable

前提知識: RSAの原理、格子の基礎

from Crypto.Util.number import getPrime, GCD
from flag import FLAG
import random

def egcd(a, b):
    r0, r1 = a, b
    s0, s1 = 1, 0
    t0, t1 = 0, 1
    while r1 > 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return s0, t0

def generateKey():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p-1)*(q-1)

    while True:
        d1 = getPrime(int(n.bit_length()*0.16))
        e1 = random.randint(1, phi)
        ed1 = e1 * d1 % phi

        d2 = getPrime(int(n.bit_length()*0.16))
        e2, k = egcd(d2, phi)
        e2 = e2 * (phi + 1 - ed1) % phi
        ed2 = e2 * d2 % phi

        if GCD(e1, e2) > 10:
            break

    assert((ed1 + ed2) % phi == 1)

    return (n, (e1, d1), (e2, d2))

n, A, B = generateKey()
M = int.from_bytes(FLAG, 'big')
C1 = pow(M, A[0], n)
C2 = pow(M, B[0], n)
assert(pow(C1, A[1], n) * pow(C2, B[1], n) % n == M)

import json
print(json.dumps({
    "n": n,
    "A": (A[0], C1),
    "B": (B[0], C2),
    #"d": (A[1], B[1]), # for debug
    }))

ぱっと見普通のRSAっぽく見えますが、$e_1,e_2$がかなり特徴的。多分これ紙の上で頑張って計算しなきゃいけないゲームです...
既知の情報は$e_1,e_2,C_1,C_2,N$ですね。ただ、普通のRSAと異なり「片方の$d$が求まれば復元可能」ではないです。$e_1$と$d_1$は完全にバラバラに決められていたりするので。復元のためには$d_1$と$d_2$の両方を知るか上手くやるかして、$e_1d_1+e_2d_2\equiv 1(\mod \phi)$を利用して解く必要があります。

さて、ここでRSAの脆弱性の話ですが、この問題には以下の2つの脆弱性がある可能性があります。

• 同じ$N$について複数の$e$を用いていること。$e_1$と$e_2$が互いに素であった場合、$e_1d'_1+e_2d'_2=1$となるような$d'_1,d'_2$を用いて復号が可能です（実際にはgcdのアルゴリズムのように計算すると思いますが）
  • しかしこの問題では、それを回避するために$\gcd (e_1, e_2)>10$という条件を置いています。実際に計算したところ$g=11$でした。逆に言ってしまうと、$M^{11}(\mod N)$までは求めることが出来てしまうため、頑張れば出来そうな気も...？（しません）
• $d$が小さいこと。通常のRSAにおいては$d$が小さいと$\frac{k}{d}$が$\frac{e}{N}$の主成分近似になるという性質を利用して、連分数分解をすることで$d$が求まります。ただし、今回は$d$が2つあるのが難点です。しかも$d_1, d_2, e_1$をランダムに決めて$e_2$で調整かましている仕様。

以降writeup見ながらの回答になりますが、結論から言うと2つ目の脆弱性を利用します。$e_1d_1+e_2d_2\equiv 1(\mod\phi)$を変形し、

e_1d_1+e_2d_2=1+k\phi, k\in\mathbb{Z} \\
e_1d_1+e_2d_2=1+k(n-p-q+1) \\
e_1d_1+e_2d_2\equiv 1-k(p+q-1)\ (\mod n) \\

$e_1$は求め方がrandint(1, phi)より$e_1\simeq\frac{\phi}{2}=\frac{n-p-q+1}{2}\sim n^{0.5}(\mod n)$。これは$e_2$も調整こそかけていますが同じです。$d_1,d_2\sim n^{0.16}$より$k\sim n^{0.16}$っぽいです。$d_1,d_2,k$が比較的小さい模様。

欲しいのは$e_1d_1+e_2d_2+nk\sim -n^{0.66}$を満たす$d_1,d_2,k\in\mathbb{Z}$の組み合わせを得ることです。では、以下の格子の問題に帰着しましょう。（後ろ2要素はLLLで事故らないよう、$n^{0.5}$をかけることで大きさの調整をしています）

• 用意するベクトル: $b_1=[e_1, n^{0.5}, 0], b_2=[e_2, 0, n^{0.5}], b_3=[n, 0, 0]$
• 目的となるベクトル: $a=[-n^{0.66}, n^{0.66}, n^{0.66}]$

この$d_1b_1+d_2b_2+kb_3=a$を解くことで目的となる$d_1,d_2$を知ることが出来ます。$[b_1,b_2,b_3]$をLLLで簡約化した時点で$d_1,d_2$が表に出てくるっぽいです。

import json
import math

content = None
with open("output", "r") as f:
    content = json.loads(f.read())

N = content["n"]
e1, c1 = content["A"]
e2, c2 = content["B"]
squaredN = int(N**0.5)

B = Matrix(ZZ, [[e1, squaredN, 0], [e2, 0, squaredN], [-N, 0, 0]])
L = B.LLL()

for l in L:
  d1 = int(abs(l[1]) // squaredN)
  d2 = int(abs(l[2]) // squaredN)

  test = pow(2, e1*d1+e2*d2, N)
  if test == 2:
    R = IntegerModRing(N)
    m1 = IntegerMod(R, c1) ** d1
    m2 = IntegerMod(R, c2) ** d2
    flag = m1 * m2
    print(int(flag).to_bytes(32, 'big'))

また少し格子に詳しくなれた気がします。

urara

前提知識: 楕円曲線とRSA

from flag import flag

p = random_prime(1 << 1024)
q = random_prime(1 << 1024)
n = p * q

print("n =", n)

# ---

x = int.from_bytes(flag, "big")
y = randint(0, n-1)

a = randint(0, n-1)
b = (y^2 - (x^3 + a*x)) % n

EC = EllipticCurve(Zmod(n), [a, b])

P = EC((x, y))
Q = 2 * P

print("a, b =", [a, b])
print("Q =", Q.xy())

# ---

m = int.from_bytes(flag, "big")
t = randint(0, n-1)

c = power_mod(m + t, 65537, n)
print("t =", t)
print("c =", c)

同一の$n$について、同一の平文を楕円曲線とRSAでそれぞれ暗号化したものが与えられる問題。楕円曲線側は至って普通です。RSA側は適当な数$t$が加算されています。

取り敢えずやりたくなることとして、楕円曲線の2倍公式から復元する式を作りたくなります。$P=(x,y),2P=(X,Y)$としたとき、
$$X=\frac{(3x^2+a)^2}{4y^2}-2x$$と楕円曲線自身の式$$y^2\equiv x^3+ax+b(\mod n)$$から$y^2$を消して整理すると、
$$x^4 - 4Xx^3 - 2ax^2 - (4aX+8b)x+a^2-4Xb\equiv 0(\mod n)$$が算出できます。が、ここからどうするの...次数が比較的小さい多項式なので、Coppersmith's Attackが使えそうな感じはしますが、それだとRSAのある意味とは...？となるので多分違います。

以降作問者writeupを見ています。RSAの式は多項式に展開することが出来ます（そのための$t$だったのか...！）。また、上で導出した式とRSAの$(x+t)^e-c\equiv 0(\mod n)$はともに$x=m$（$m$はflag）で成り立つようになっているので、両辺は$(x-m)$で割り切れるはずです。ということで、gcdをするといい感じになりそうですね！？

自分のsagemath力が低く、デフォルトの多項式gcdが使えなさそうなため、雑に割る操作を繰り返してしまっています。一回行うごとに次数が1つずつ落ちていくのでまぁ次数が小さいから手作業でもいいか...という感じです。最後にちゃんと負符号をつけないと解く方程式が変わるので要注意。

from output import *

PR.<x> = PolynomialRing(Zmod(n))
f = x^4 - 4 * Q[0] * x^3 - 2 * a * x^2 - (4 * a * Q[0] + 8 * b) * x + a ^ 2 - 4 * Q[0] * b
g = ((x + t) ^ 65537 - c) % f

F = f % g
G = g % F
R = IntegerModRing(n)
flag = R(-G[0]) / R(G[1])
print(int(flag).to_bytes(64, 'big'))

最後の「$x=m$が両方の多項式で成り立つのでgcdできる」というテクはかなり汎用性が高いので、覚えておきます。多分他の問題でも使えることでしょう。

Reversing

SCSBX:Reversing

前提知識: アセンブリの基礎（x64が何となく読めれば十分。これを解説するとそれだけで1記事書けるのでごめんなさい...）、ソースコードをざっくり読む能力

Open Sourceの独自stack based VMで動作する作られたプログラムが与えられるので解析してね、という問題です。ポイントなのは「このVMを自分の環境でビルド出来る」という点です。つまり、構文解析の箇所に自由にデバッグコードを差し込んだり、雑に実行箇所を外してdisassemblerにすることも出来ます。このVMはstack basedということもあり、「pushを除く全命令が1byteのみで指定できる」というのは中々面白い仕様です。その代わり、処理そのものはPietとかWhitespace、Starryと同様の面倒さが...

ということで、まずは各命令毎に処理が分かれる箇所で「どの命令を実行しているか/その時のpcが何か」だけ出力してもらって、実際の処理もコメントアウトしてしまいましょう。内部でpcのインクリメントだけが行われるので、結果的にdisassemblerの完成です。走らせると250行程度のアセンブリが出力されます。と言ってもこの段階ではobjdumpで見れるような関数とかも何も無いので、これを読んでいく必要があります。概要の把握に必要なところだけ雑にidaっぽくグラフに落とし込んだのがこちら（解説で分かりやすいのでやってますが、CTF中にこれやるのはやった後復元スクリプトを0から書く必要があるので非推奨です）

取り敢えず画像左のpc=0x1ddとなる箇所に行けばいいと目標が決まります。一番最初の分岐で右側に飛ばされ、何度かループを回った後左側へ。左側でも何度かループを回った後に最後の審判が下されるようです。

0x135での処理を見ていきましょう。この際、折角ソースコードがあるので、PCが一定範囲内にあるときは毎回stack出力をする、みたいなことをすると比較的見やすくなります。このブロックでの処理をまとめると、「入力を行った0xdead000aを0xdead004a以降の領域と比較（4byte毎swap有）、差分を全部orして0ならOK」です。0xdead004a==0xdead000a + 64以降の値は一番最初、上の画像のreadよりも前の初期化段階で埋め込んでいます。ざっくりこのような感じ。XXの領域は最終的には入力に使われます。

0xdead0000: cd 5b d3 06  46 4c 41 47  3a 20 XX XX  XX XX XX XX
0xdead004a: 23 12 76 46  c5 a5 be 54  f6 e8 22 7a  c9 93 b4 5d
0xdead005a: 5e 17 5d 05  33 cd 2f 02  e6 6b c4 42  e8 a0 10 6d
0xdead006a: 78 c2 f4 53  2a ec 79 72  39 fb 91 54  1f 42 ac 49
0xdead007a: 37 3a ab 49  12 58 85 47  05 bb 18 57  5b fb 40 05

では、これを入力に与えればいいのでは？と思いますが、もう1歩必要です。コード全体右側のブロックでの操作をざっくりと見ると0xdead000aをちゃんと使っていて、0x0f3の領域でよく分からないけどどこかにstoreをしているという現象が起きています。ということで、右側の処理もちゃんと見てみましょう。デバッグしていると、4+4byte毎に以下の処理を行っています。（以下の疑似コードでは基準アドレスとしてxを使用しています）

v = [x]
v2 = [x+4]
3.times {
    [0xdead0000] = ([0xdead0000]*1919-810)%0x305eb3ea
    tmp = v2
    v2 = (~([0xdead0000] ^ v2)) ^ v
    v = tmp
}
[x] = v
[x+4] = v2

ところで、[0xdead0000]が乱数器として使われていますが、これは予め計算することで毎回の値を厳密に求めることが出来ます。そう考えると、v2 = (~(x ^ v2)) ^ vとなり、0xdead004a以降の領域==変換後こうなっていなくてはならない状態から逆算が可能です。一応、逆算じゃなくても8文字なので、使わない領域も考えてギリギリ全探索が成立する...？という感じです。C++を使用しているのは、乱数生成器がオーバーフローするためです。32bit unsignedということを把握していれば別言語でも問題ないはず。

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

typedef unsigned int u32;

int main() {
  u32 r_base = 0x06d35bcd;
  vector<u32> r(24);
  for (int i = 23; i >= 0; i--) {
    r_base = (r_base * 1919 - 810) % 0x305eb3ea;
    r[i] = r_base;
  }

  vector<u32> mem = {0x46761223, 0x54bea5c5, 0x7a22e8f6, 0x5db493c9,
        0x055d175e, 0x022fcd33, 0x42c46be6, 0x6d10a0e8,
        0x53f4c278, 0x7279ec2a, 0x5491fb39, 0x49ac421f,
        0x49ab3a37, 0x47855812, 0x5718bb05, 0x0540fb5b};

  for (int i = 7; i >= 0; i--) {
    u32 v = mem[2 * (7 - i)];
    u32 v2 = mem[2 * (7 - i) + 1];
    for (int j = 2; j >= 0; j--) {
      u32 nv = v2;
      u32 nv2 = (~(r[3 * i + j] ^ v2)) ^ v;
      v = nv;
      v2 = nv2;
    }
    mem[2 * (7 - i)] = v;
    mem[2 * (7 - i) + 1] = v2;
  }

  for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 4; j++) {
      char c = (mem[i] >> (8 * j)) & 0xff;
      printf("%c", c);
    }
  }
  cout << endl;
}

fixer

前提知識: Python力

pycが渡されます。どう解析するんですか！？とちょっと検索すると記事が見つかります。

これを動かすのですが、上手く動きません。marshalが正しく読み込めていないことは分かっていて、もう少し詳しく調べてみると、ある記事が見つかります。気になったのはpycのフォーマットで、試したコードではbytecodesは13byte以降、記事のbytecodesは9bytes以降でした。なら、seek付ければ行ける？ということでseek(8)で調整をしてみます。同じようなエラーが生えました。分からん。

可能性として、pycの作り方によってheaderデータが変わるのかもしれません。本当はPythonのソースコードを読むべきではあるのですが、時間短縮のため、適当に4bytes毎ずらしていきます。最初はmagic bytesなのは確定、恐らくその次に作成日時も入ると思うので、8から適当にずらします。16で動きました。結局何が追加で入っていたのでしょうか...

かなり復元しやすいコードだったため、pythonコードに落とせる範囲で落とし込みます。

import re
s = input()
if not re.match('^SECCON{([A-Z]+)}$', s):
    print('invalid flag')
else:
    # lambda関数を使ってsからTrue/Falseに変換
    f = lambda x: ???
    if f(s):
        print('correct')
    else:
        print('wrong')

このlambda関数がシンプルなら解読できそうなんですが、少なくとも内部でもlambdaを使っていそうで、かなり複雑そうです。正直読める気がしません。一応「文字列を何か変換して、結果13611142019359843741091679554812914051545792465993098606064046040462991と一致していたらOK」っぽい雰囲気はします（それっぽい定数の読み込みはこれだけなので）。

それが分かったところで他の情報が無いとどうしようもないので、lambda関数呼び出し==CALL_FUNCTIONを検出してみましょう。settraceという関数を使用することで、lambda関数の呼び出しを検知することが出来ます（参考）

trace.py

import sys

def trace(frame, event, arg):
    f_name = frame.f_code.co_name
    if event == 'call':
        if f_name == '<lambda>':
            print('call', f_name)
        return trace
    elif event == 'return':
        if f_name == '<lambda>':
            print('return', f_name, arg)

sys.settrace(trace)

import fixer

かなり無駄な出力が多いですが、一番最後(tailが有効なレベル)に数字がreturnされ、その後Falseになっていることが分かります。この値が上の長い数値と比較されているのではないか？と推測が付きます。入力を雑に変えてみて、この値がどのように変化していくか見ていきます。

• SECCON{AAAA}に対して17040900、SECCON{AAAB}に対して152837644、SECCON{AAAC}に対して577202469が比較に使われていそうな数字です。特に線形では無いですが、文字コード番号を増やすと増えるみたいですかね？
• SECCON{AAAA}は同じく17040900、SECCON{BAAA}に対して17040908、SECCON{CAAA}に対して17040933。傾向は同じですが、露骨にその上がり具合が小さいです。2文字目、3文字目でも検証しましたが、後ろほど変化量は大きいみたいです。
• SECCON{AAAA}は17040900、SECCON{AAAAA}は4379511301と文字数が増えると段違いに増えます。試しにSECCON{AAAAA}の1つ前と思われるSECCON{ZZZZ}についても調べると3322975500とAAAAAよりも小さい値が出てきました。

さて、これらの情報が分かったので、恐らく中の文字列は以下のルールに基づいて探索をすることで求めることが出来ます。長いので以降x=13611142019359843741091679554812914051545792465993098606064046040462991とします。

1. SECCON{AA...A}と中のAの数をxを超えない範囲で増やせるだけ増やす
2. SECCON{AA...B}、SECCON{AA...C}と一番後ろの文字を同じくxを超えない範囲で可能な限り上げていく
3. 2の操作を後ろから2番目、3番目、...と繰り返していく

現在のtraceスクリプトを自分の環境でtailしたところ、下から5行目が例の数値なので、traceスクリプトを改良しつつsubprocessを利用して何度も走らせ、探索を行いましょう。

trace.py

import sys

def trace(frame, event, arg):
    f_name = frame.f_code.co_name
    if event == 'call':
        return trace
    elif event == 'return':
        if f_name == '<lambda>':
            print(arg)

sys.settrace(trace)

import fixer

solver.py

import subprocess

res = ['A']
target = 13611142019359843741091679554812914051545792465993098606064046040462991

def try_fixer(s):
    print('try', s)
    flag = ('SECCON{' + s + '}').encode('utf-8')
    p = subprocess.run(['python3.9', 'trace.py', '|', 'tail'], input=flag, stdout=subprocess.PIPE)
    output = p.stdout.decode('utf-8').split('\n')[-5]
    num = int(output)
    return target >= num

# step 1. 桁数合わせ
while try_fixer(''.join(res + ['A'])):
    res.append('A')

# step 2. 後ろから増やしていく
for i in reversed(range(len(res))):
    while True:
        if res[i] == 'Z':
            break
        res[i] = chr(ord(res[i]) + 1)
        if try_fixer(''.join(res)):
            continue
        else:
            res[i] = chr(ord(res[i]) - 1)
            break

print('SECCON{' + ''.join(res) + '}')

で動かしたのですが、後ろ2桁辺りで狂ったのか、頭ほとんどがZになってしまいました...targetとの差分を取って出力してみると、どうやら「A→Zとなるごとに値が大きくなる」という仮定は嘘のようです。では、似たような仮定を立てます。

• 手順2での桁合わせはtarget-(実行結果)が非負かつ最小となるような値を採用する。これは以下の仮定が成り立てばよい。
  • 手順1での'A'の列と正解の桁数が異ならない('A'が全体の中で最小であれば確実に成立する)
  • 'A'~'Z'の中に、値に対して負の効果を付与しない(未検証)

このようにしてsolver.pyを改良しましょう。

solver.py

import subprocess

res = ['A']
target = 13611142019359843741091679554812914051545792465993098606064046040462991

def try_fixer(s):
    flag = ('SECCON{' + s + '}').encode('utf-8')
    p = subprocess.run(['python3.9', 'trace.py'], input=flag, stdout=subprocess.PIPE)
    output = p.stdout.decode('utf-8').split('\n')[-5]
    num = int(output)
    print('try', s, target - num)
    return target - num

# step 1. 桁数合わせ
while try_fixer(''.join(res + ['A'])) >= 0:
    res.append('A')

# step 2. 後ろから変えていく
for i in reversed(range(len(res))):
    min_v = float('inf')
    min_c = 'A'
    for j in range(26):
        res[i] = chr(ord('A') + j)
        val = try_fixer(''.join(res))
        if val < 0:
            continue
        if min_v > val:
            min_v, min_c = val, chr(ord('A') + j)
    res[i] = min_c

print('SECCON{' + ''.join(res) + '}')

これは正しく動作しました！

終わりに

CTF、正直敷居は高いと思います。未だに自分もpwnのヒープ周りの勉強が全く足りてないです。ただ、実際に「身近だけど知らない技術」について問題という形式で触れることが出来るというのはいいことだと思っています。

自分は必ずしもコンテスト中に問題が解ける必要は無いと思っています。当然問題が解けないこともあって（むしろそちらの方が多いです）、その問題のwriteupを見て知見を得ることで成長していくことに大きな意味があると思っています。ので、是非（問題解けなくてもいいので）CTFやってみましょう！

宣伝

この記事を読んで「面白かった」「学びがあった」と思っていただけた方、よろしければ LGTM、Twitter や Facebook、はてなブックマークにてコメントをお願いします！

また DeNA 公式 Twitter アカウント @DeNAxTech では、 Blog 記事だけでなく色々な勉強会での登壇資料も発信しています。ぜひフォローして下さい！
Follow @DeNAxTech