SECCON Beginners CTF 2023 writeup

はじめに

2023年6月3日の14:00から丸24時間にわたって開催された，SECCON Beginners CTF 2023に参加しました。（常設でない）CTFの大会への参加はこれが2回目ですので，まだまだ圧倒的に（特にweb系の）知識が足りていないという実感はしているのですが，何事も一旦ある程度仕上げてから実戦に行くというのはどうも性分に合わず，どれだけ解けるんだろうかという感じで参加してみました。

本題

解けた問題たち

Welcome（welcome）06/03 14:00:35

はい。大抵のコンテストでここに置かれる問題は，Welcomeとは名ばかりじゃないかみたいなのではなく，本当に望まれた客のように温かく出迎えてくれる問題が出るらしいです。FLAGの形式はctf4b{[\x20-\x7e]+}という正規表現で最初に伝えられていますが，こんな感じのを探せばいいのねという目安になるのでとてもありがたいです。

CoughingFox2（crypto）06/03 14:20:09

さて，まずは自分が一番解けそうなcryptoから解いていくことにします。 main.pyをみると

for i in range(len(flag)-1):
    c = ((flag[i] + flag[i+1]) ** 2 + i)
    cipher.append(c)
random.shuffle(cipher)

という記述が見えます。どうやらflagの隣り合う文字を足して2乗してindexを足したものを配列にし，それをランダムにシャッフルしているようです。 (flag[i] + flag[i+1]) ^ 2 \geq (32+32) ^ 2 = 4096 ですから，前から1つずつ決めていくことを考え，末尾2つの文字の計算結果がもしcipherにある数になったら，それで確定させていくという方針で問題なさそうです。以上より，以下のコードを実行してFLAGを得ることができました。

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> cipher = {4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636};
    string flag = "c";
    set<int> s;
    for (int v : cipher) s.insert(v);
    int idx = 0;
    while (s.size() > 0) {
        for (int i = 0x20; i <= 0x7e; i++) {
            int b = (flag.back() + i) * (flag.back() + i) + idx;
            if (s.count(b)) {
                flag += i;
                s.erase(b);
                break;
            }
        }
        idx++;
    }
    cout << flag << endl;
    return 0;
}

Conquer（crypto）06/03 14:37:31

1問目が比較的さくっと解けたので，この調子で2問目も首尾よく解きたいところです。 problem.pyを見ると

key = getrandbits(length)
cipher = flag ^ key

for i in range(32):
    key = ROL(key, pow(cipher, 3, length))
    cipher ^= key

という記述が見え，cipherとkeyは与えられていますから，操作を逆にたどることができればflagを復元することができそうです。XORは2回繰り返すと元に戻るのでこの部分は造作もないことです。あとは関数ROLの逆の操作をできればよいです。ROLを見ると

def ROL(bits, N):
    for _ in range(N):
        bits = ((bits << 1) & (2**length - 1)) | (bits >> (length - 1))
    return bits

となっており，これはbitsを長さlengthで左にNだけ回転させる操作ですから，右にN回戻してやる関数をこんな感じで書いてあげます。

def ROLr(bits, N):
    for _ in range(N):
        bits = (bits >> 1) | ((bits & 1) << (length - 1))
    return bits

あとはlengthがflag.bit_length()なので少し困りますが，keyが十進数で132桁の数なので 132 \log10 / \log2を計算すると438.49と分かりますから，適当に439を放り込んだのち，print(ROLr(ROL(key, 10), 10))があっていることを確認して，以下のコードを実行するとFLAGを得ることができました。

from Crypto.Util.number import *
def ROLr(bits, N):
    for _ in range(N):
        bits = (bits >> 1) | ((bits & 1) << (length - 1))
    return bits

length = 439
key = 364765105385226228888267246885507128079813677318333502635464281930855331056070734926401965510936356014326979260977790597194503012948
cipher = 92499232109251162138344223189844914420326826743556872876639400853892198641955596900058352490329330224967987380962193017044830636379
for i in range(32):
    cipher ^= key
    key = ROLr(key, pow(cipher, 3, length))
flag = cipher ^ key
print(long_to_bytes(flag))

Half（reversing）06/03 14:49:43

次に，何とかなりそうなreversingに手を付けてみます（本当はcryptoのChoiceをちょっと見たんですが，すぐに解ける気がしなかったので移行しました）。IDAは知っているのでまずhalfをIDAで開いてみます。すると，2つの文字列がはっきり見えましたから，これをつなげてFLAGを得ることができました。FLAGの文字列を見て気づきましたが，これなら単にstrings halfでよかったですね。

Three（reversing）06/03 15:11:14

同様に，これもIDAでthreeを開いてみます。すると，なにやらvalidate_flagなる関数があるのが見えます。そうするとflag_0，flag_1，flag_2を呼んでいて，それぞれc4c_ub__dt_r_1_4}，tb4y_1tu04tesifg，f{n0ae0n_e4ept13だと分かります。いかにもパタトクカシーーの3つ版をやってくださいと言っているので，それをするとFLAGを得ることができました。

Forbidden（web）06/03 15:22:51

webは結構苦手な（というよりも単純に知識そのものがない）んですがさすがにbeginnerくらいは解けるんじゃないかと思って手を付けてみることにします。与えられたサイトはhttps://forbidden.beginners.seccon.games/でhttps://forbidden.beginners.seccon.games/flagにアクセスすればよさそうなんですが，はじかれてしまいます。app/index.jsを見ると

const block = (req, res, next) => {
    if (req.path.includes('/flag')) {
        return res.send(403, 'Forbidden :(');
    }
    next();
}

とあって，パスの中に/flagという文字列がそっくりそのままあると駄目みたいです。なので，どうにかして/flagという文字列を含めずに/flagにアクセスしたいです。うろ覚えの知識でパーセントエンコーディングみたいなやつだったっけなみたいなことをいろいろやっていたんですが，/FLAGと大文字にすると通過して，FLAGを得ることができました。どうやらケースセンシティブではないみたいです。学びを得ました。

YARO（misc）06/03 16:29:37

miscって何だろうと思い調べてみると，miscellaneousの略らしいことが分かりました。発音が案外非自明な/mìsəléiniəs/で，mixと同じ語源らしいです。部立てでいうと雑というやつでしょうか。さて，server.pyを見ると，ruleを入力させたのち

compiled = yara.compile(source=rule)
for root, d, f in os.walk('.'):
    for p in f:
        file = os.path.join(root, p)
        matches = compiled.match(file, timeout=60)
        if matches:
            print(f'Found: {file}, matched{matches}')
        else:
            print(f'Not found: {file}')

とyara.compileなる関数でコンパイルしたルールをファイルたちに適用させているようです。試しにnc yaro.beginners.seccon.games 5003をしてrule_example.yarにある

rule shebang {
    strings:
        $shebang = /^#!(\/[^\/ ]*)+\/?/
    condition:
        $shebang
}
rule maybe_python_executable {
    strings:
        $ident = /python(2|3)\r*\n/
    condition:
        shebang and $ident
}

を食わせてみると

Found: ./redir.sh, matched: [shebang]
Found: ./server.py, matched: [shebang, maybe_python_executable]
Not found: ./flag.txt
Not found: ./requestments.txt

を吐いてくれました。なんとなく読んでみると，ruleの後が規則名的なやつで，stringsで正規表現が使えて，conditionでその条件になった時にmatchした旨を知らせてくれる感じかなと思い，以下を食わせてみます

rule r {
    strings:
        $c = "c"
    condition:
        $c
}

すると案の定

Found: ./redir.sh, matched: [r]
Found: ./server.py, matched: [r]
Found: ./flag.txt, matched: [r]
Found: ./requestments.txt, matched: [r]

を吐いてくれて，flag.txtに文字cが含まれていることが分かりました。あとはこのルールをctf4b{に0x20～0x7eまでの文字を1文字づつ追加していって，どのルールにmatchするかを見てやれば，flag.txtの長さ-6回のクエリで特定することができます。せっかく正規表現が使えるのであんまり効率的ではないですが，解けるものは解けるので以下のコードを書きました。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string now = "ctf4b{";
    string out;
    for (int i = 0x20; i <= 0x7e; i++) {
        out += "rule ";
        out += "r" + char(i);
        out += " {\n";
        out += "    strings:\n";
        out += "        $";
        out += "s" + char(i);
        out += " = \"" + now;
        out += (char)i;
        out += "\"\n";
        out += "    condition:\n";
        out += "        $";
        out += "s" + char(i) + "\n";
        out += "}\n";
    }
    cout << out << endl;
    return 0;
}

と，この出力結果を食わせるとSomething wrongと吐いてきて何ですかとなったんですが，出力結果を見れば当然でスペースだのバックスラッシュだのが普通に通るわけがないです。そのため，（どうせ英大小文字と数字とアンダーバーと}なので）範囲を絞って，iをcharではなく数として出力することにしました。改善したコードが以下です。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll toInt(string s, ll b = 10) {
    assert(b > 1);
    ll res = 0;
    for (char c : s) {
        res *= b;
        res += c - '0';
    }
    return res;
}
string toStr(ll x, ll b = 10) {
    assert(b > 1 && x >= 0);
    if (x == 0) return "0";
    string res;
    while (x) {
        res += (x % b) + '0';
        x /= b;
    }
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    string now = "ctf4b{";
    string out;
    for (int i = 48; i <= 125; i++) {
        if (i == 92) continue;
        out += "rule ";
        out += "r" + toStr(i);
        out += " {\n";
        out += "    strings:\n";
        out += "        $";
        out += "s" + toStr(i);
        out += " = \"" + now;
        out += (char)i;
        out += "\"\n";
        out += "    condition:\n";
        out += "        $";
        out += "s" + toStr(i) + "\n";
        out += "}\n";
    }
    cout << out << endl;
    return 0;
}

これを実行で出力結果を食わせながら，吐かせたmatchに対応する文字をnowの末尾に追加していけば，いつか}が現れるので，これでFLAGを得ることができました。

poem（pwnable）06/03 17:38:28

pwnableは一番「ハッキング」をしているという気がしてできると楽しいので手を付けてみます。 src.cを見ると

scanf("%d", &n);
if (n < 5) {
    printf("%s\n", poem[n]);
}

とあり，いかにもやばそうなコードです。グローバルにchar *flagとchar *poem[]が順に置かれていて，nが負の時をはじいていないので，このあたりを利用してflagの中身をprintさせればよさそうです。poem[n]は*(poem + n)のことですから，（たぶんできる人は一発で計算できるんでしょうけど，私にはそのような能力がないので-1，-2…を順に入力することにより）-4を入力すると，FLAGを得ることができました。

polyglot4b（misc）06/03 18:54:25

polyは多数（polynomialとかpolymerとかのpolyでしょうか）という意味で，glotは舌（これはあまり聞いたことなかったですがglossaryと同じ語源らしいです）という意味なので，全体でmultilingualみたいな意味らしいです。舌で言語というのはmother tongueとかに思いを馳せて納得しました。
さて，これはプログラミングの文脈では複数の言語でコンパイルできるようなもののことを指すらしく，これはエイプリルフールコンテストとかで何回かやったことのある形式です。polyglot4b.pyを見ると

f_type = subprocess.run(
        ["file", "-bkr", f"tmp/{f_id}/{f_id}"], capture_output=True
).stdout.decode()

で

if "JPEG" in f_type:
    types["JPG"] = True
if "PNG" in f_type:
    types["PNG"] = True
if "GIF" in f_type:
    types["GIF"] = True
if "ASCII" in f_type:
    types["TXT"] = True

とあり，f_typeにJPG，PNG，GIF，ASCIIの全ての文字列が含まれているようなものを求めればよさそうです。美味しそうなお寿司sample/sushi.jpgを，text_script.shを参考に召し上がってもらうと（しばらくこれに気付かなくて，どうやってバイナリを標準入力に送り込むんだろうとかいろいろ調べてましたが），当然ながらJPGはOKそうです。file sushi.jpgをしてみると

sushi.jpg: JPEG image data, Exif standard: [TIFF image data, big-endian, direntries=4, description=CTF4B], baseline, precision 8, 1404x790, components 3

と吐き出され，descriptionがいかにも書き換えられそうなので，右クリックしてプロパティ＞詳細からPNGIFASCIIに書き換えると，FLAGを得ることができました。

ABC304（competitive programming）06/03 21:00:00-23:00:00

張り切って参加しましたが，残念ながらUnratedになりました。

aiwaf（web）06/04 00:10:45

app/app.pyを見ると

file = request.args.get("file")
# 中略
with open(f"./books/{file}", encoding="utf-8") as f:
    return f.read().replace(KEY, "")

とあって

f"""\
以下の{puuid}に囲まれた部分のURLクエリはパストラバーサル攻撃でしょうか？
そうである場合Yesを、違う場合Noを返してください。
../やflagという文字列が含まれていた場合もYesを返してください。

{puuid}
{urllib.parse.unquote(request.query_string)[:50]}
{puuid}
"""

とかいうpromptをAIに食わせているみたいなのでこの通りにはじかれてしまうみたいです。ここからなにやら?file=../flagとすればいいのではないかということが逆にわかってしまいました。とはいっても，当然このままではAIにはじかれてしまうので困るんですが，ここで[:50]に注目すると，クエリストリングのうち最初の50文字しか見ていないようですので，これを利用しない手はないです。クエリストリングは&で複数指定できるので，request.query_stringがどんな仕様かは知りませんでしたが，なんとなく全てのクエリをいい感じに拾ってくれるでしょと，適当に?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa=book1.txt&file=../flagを投げると，残念ながらAIにはじかれてしまいました。これがいう「気まぐれ」なのかなと思いましたが，単に同じ文字がいっぱい並んでいるのはかなり怪しそうなので，なんか意味のある文字列を投げてみることにします。試しに，?ThequickbrownfoxjumpsoverthelazydogThequickbrownfoxjumpsoverthelazydog=book1.txt&file=../flagとするとAIにはじかれず，FLAGを得ることができました。

sleep（life）06/04 02:00:00-10:00:00

一瞬オールしようかと思ったんですが，もう私もそんなに若くないためでさすがに明日以降に響いてしまうので，あったかいふとんでぐっすりねました。ちょっとぐっすりしすぎましたかね。

Choice（crypto）06/04 13:02:31

server.pyを見ると，何やらRSA暗号の気配です。 奇しくも，コンテスト中に＃９ 暗号理論 - 笑わない数学 - NHKが放送されているのを観測して，うんうんとなっていました。この笑わない数学，ABC予想とかP≠NP予想の回を観たことがあるんですが，尾形さんが一生懸命「わかりやすい」解説をしてくれたり，普通はコンピュータがやるところを数を小さくして頑張って手計算したりしていてなんだかとても癒やされるんですよね。
閑話休題，mがflagを整数に直したもので
\displaystyle c \equiv m^{e} \bmod n \\ e = 65537 \\ n = pqr \\ s = pq + qr + rp
が与えられています。また，いくつか質問を投げることができ， a \geq nについて p^{a} + q^{a} + r^{a} \bmod nを聞けるみたいです。この問題に限らず，ある自然数を dとし，1つめの式の両辺を d乗すると
\displaystyle c^{d} \equiv (m^{e})^{d} \bmod n
すなわち
\displaystyle c^{d} \equiv m^{de} \bmod n
であり，オイラーの定理より m^{\varphi(n)} \equiv 1 \bmod nですから
\displaystyle de \equiv 1 \bmod \varphi(n)
のとき
\displaystyle m^{de} \equiv m \bmod n
となり，flagを復元できます。そのため， \varphi(n)を求めないと解けそうにありません。乗法性より
\varphi(n) = \varphi(p) \varphi(q) \varphi(r) = (p-1)(q-1)(r-1)
ですから，対称式に思いを馳せて， t = p+q+rを求めれば良さそうです。まとめると

  1. t = p+q+rを求める
  2. \varphi(n)を求める
  3. d \equiv e^{-1} \bmod \varphi(n)を求める
  4. m \equiv c^{d} \bmod nを求める

という感じです。と，ここまでは順調だったのですが，ここから先が大変でした。
まず，式をこねこねして p^{a}+q^{a} \bmod rとかr^{2}(p+q)とかp^{a-1} \equiv 1 \bmod qrなるaとかを考えて， a = k_{1}(\varphi(qr)-1)+1 = k_{2}(\varphi(rp)-1)+1 = k_{3}(\varphi(pq)-1)+1 を満たすような感じにすればよさそうなんじゃないかとか，迷宮にはまり込んでしまいました。
こんなのを1時間くらいやっていたんですが，ここでやっぱり対称式って対称なまま変形するのがもっともだよなと思っていると，そういえば f_{k} = p^{n}+q^{k}+r^{k}って対称式を使って漸化式が作れたような気がする，というおぼろげな記憶が脳内に浮かび上がってきました。さっそく検索すると， 対称式について覚えておくべき7つの公式 | 高校数学の美しい物語が出てきて
\displaystyle f_{k}=(p+q+r)f_{k-1} - (pq+qr+rp)f_{k-2} + (pqr)f_{k-3}
が成立するとあります。これは無からでも，次数を揃えたいという思惑の下で導けなくはない式です。これが分かってしまえばもう解けたも同然で， fはまさにクエリで聞くことのできるものですから，nより大きい連続4整数なら何でもいいですがなんとなく k=n+4としてみます。よって，求める tは
\displaystyle t = p+q+r \equiv \frac{f_{n+4}+sf_{n+2}-nf_{n+1}}{f_{n+3}} \bmod n
で計算できます。途中で，あれ \bmod nでの割り算をしないといけないのに\varphi(n)がそもそも分からなくて困ったなと一瞬考えてしまったんですが，1次不定方程式を考えてあげて拡張ユークリッドの互除法を使うことで対数時間でできますから，十分高速です。またpythonならpow(fs[2], -1, n)とするだけで逆元を求めてくれます。あとは先ほど確認した流れの通りに計算すればmが求まり，以下のコードを実行することでFLAGを得ることができました。なお途中で，3次方程式くらいpythonなら簡単に解けるようになっているだろうと思って解いてもらって，pqr=nになっていることを念のため確認しています。

import sympy
from Crypto.Util.number import *

n = 18594550144547301333494330440727776321888361219176721067949296945328255249954628307014771206354387992788849094369885364310718228616250534865474996610051308966556663513723774648204138691124155758903715670449495386324341982424372348006314484048087221986823132438653329070617438308229162206886018749114388232554770882124576797234528168647721468061130240000009961736239289406130443086805586878797823927326251348506576180968621212384821330459417776031528751245144779238339037181035019403383704825809754775457158685619237158318168078973375749838072557762835300894929117815659839771328470141036945068417476122304376457803421537844804263578952666410904251530063550310671358146130161038676245076225153104653328579612568130178527397102201450325377763663195186232431356635649083119956424152442105158042604930244205655650846058478007779641925441638181268347095773707292578033077539161414302600982934164451130259061692713617965808525775706316991584688941677794868509981835117478617441665410620748661142428791580699137883153900909645948151807614712106654970231563776077145134141743451153674521494759420742831287853816783005018002982334781293226295634494939193866208956755695275599019914093070515911865097181250631279419933015363070006317691956094799311246182093778097496044243467400529695870747862884609047516877188834217674267413565462195834950315899190217647731281742246014695811019365437664168577053650189544051756367280332782926906642571915503305100402747283029037973541060616787881611915489676815297815488300693048486195522622840700659546607863989212042671317168336110056993734546348545229039485955806005503511573079093279143714008546998039690324458538616639264673123707871575906337313756795608368817932155368265068857021593264223477917381523546491114471418028659951483819379243259563026852723985354642576294216010525128965283026914124732795606749900735076833
e = 65537
c = 10342344907508164765757749919736793352421298410257707305337740282726570614361245233079594385172204228032038008591858829473590298640501612048679712881374460561447979225128106405099192546793981982904899317923409634997879975551981774052544506672989053390029245957379799097945980399159472017099743251162202689417924297496568358594561467023936207423370478335087967546820774935321601454985234148742581683153878329113809706037195132918847881648102665634946452769752004738678048613117527355401794136229705473310192028404361793214991751048535468030619280111134646927837387112430640912403183494723762710533123467822560454338674871509088078617215104155538321276306593153365689313507111715593208178750474531554078490621196839045999551808039533099200652245563619075253478968019566598334595510426814578251026928765863898664774174937080085258312573331457953954032167115597294784688185718000498198837840388823869869039770901112808401481842477934082132389734049421864722446630519821963832522757259715527389788819253085960619598701608415614363559776562905252352608574063449143712540440762622807964305913114301955104121946995740939383395500652249689345874020609138786867786314805547809787147762332634373065475892940322875352016448887691612736784481963472093559208443302511301148129686988612648036587744123151478358079878342235074480902690963990591450559650164661940324949539482132123667109842243030386135018643698795724632719766772255136235129735804849262376248978066582798887621824292957037633913779910202133655441441749570894499609343385415177847125861379981445766435166827219863591917023963573145138447219164203029541433395486348895940466848629638668409529745367441778934635514256250606203623457958839091652623581718481597181728520014497453438570461342930454656943186232641965098703860007216291599015775321140513837342980975049323871697499863284637432909825862229383
s = 2120634407522122525612964053723418142035008003255455641592096603456441760283345528336036431616648322472299059244408007538824000258439838164923407796210909174392749039689427657509527024321339368766677838230545546152048159591282948054638843277903718675625417096955477229483557817363652777867299775888794629564948319225630717435163745607264899467164669119381163336081234217611079146087415453718433920809714724927290349782340431924401594517556836279285779579582540079396131786945740751425128174277504540352669303736847346259677401249241222962966084053096514192634047880439503138321146600760173621421765552658327328684465349942072734704198471541667702290485272759550855086436727812318199946306573660114360541345535141316329963524548671128433222439611653145584650375144692530823811014234892066102319037508553519874861693312123282704274237023375383998670981458631283698478829787764623014405274064787856756691607537071194586111473847051717089009845180552903955935294535346554523933181032790185310551237189202850698277680542460128073462138788009846800208251823875295010557977414826644268230493594558427653290107215989409804313567576233643717506604654708332004251361738146594932146752494896835692533733480315459560645163269962949101443720683719

fs = [   9359501005480405779372710337021936432612280671999663121224008343684348547062055177732575429571794635366077719318279834954613701534622751238411344449380669105077531877492942070856872279817136197142861700179442219371669126481511240632262705733433514342048453103073776142104815251824802509052607030561199840896866840234190295328295071231067056995746769744952363086416926470167916718606675390833209135853608631016989358594065690707870761954959783723219414643651172946269076072727031959547501822021793451357307859318270202198806772584767104453437719658844554943176777046964738575128934475064455572542801176476060521343465210886599953149885653692704433416467322527924111144976023813154469929275528381427197666463014913600448150125670235969761685182083061041847170959501412003917934341875224344684063243853622120540530675666598206325571740762222262689985152862807988045374878430937031848130118163297680268887558349756031144224057777767363183480137128750575028773423037507635053500750427053993047430867719891670245254246030747587351697020291635978869762883182042084728870367171535999481778276168605605627466082643591407444298025631658821546366741569412129151723129916728795926503518207681440158950132550575299202240407329039470252795448264146280977136469129359592430786937233861797372045960656375898291038315061240184705330087413201385956924464540349611021531688442713914031566600692897512723282096807836752654010495771370935008984221411218404334390601255614187442675078566740033922743719170914045162896416663168129814954678581230684423885143878178315621955870924698851000742520193911200283266106015560581673170509210197718829917947854680468156578468043278711147295435775370243293453279569233248801876968595066170260601567491128414704770453662410686762584303949993600217793466502532386367813904699613846666069071902049236038106387022805976189783705043012419,    10543425029998132962181500239493477861434578008345153350076833599680238184134128502365629893017040533525777456862353943669497449965084013148167504381540855246240916973944529792826775815219705558931360087355735197764498370877908813276650067243560783170100985032612066805786953951208642312755193876191561681736022170157502785810011066568062259816140273925882721530770934660349547754468301482859330295537400797044228214431306185273230114164504117809623842785562905293483747226759634631046858910537736277692829302358325694636755495593467765357277994806806954900548425500983636169370397165815620807979938938436946191224814114625956294640356878027243641122075872592164275606307281570243093818251295379378426901642313076870540070792970205048387020545394398980694295743299016565837262055580203045998183944535034630718565935072832468965371994049537621095149404747388004718635460955835870138335805009138523211692986251994345499218161809507840485173571934933629260253315541403121466257691295916643281963927610148975027283054797279105512202801655858859508459492105349733390939524018010999268733889268671921118513901587904832702198450370539909070313024854940912125557826279196717929032054776798565825576056585792610159269169391389321365630285828349232513094326846736397706499620861417381690014318845799995647881167399603222175399914960948931556288257936225509799362791821095120383864607774422289019511811524098135411756721865164940159897796828119973521339313211641524307992390265301932872552871536422229261592414235729117424432211618129194657690061438493413463616775559354809573530679422684761923320597829693720614054427406676323665515988773387518144500557685713365051219609284360039980520489127571885668983615066083949961109942541483497374543413485758053303489011738166913583093421042667529143940374683492397875497703924259048139817563467332521743750980925106284,    17263368669868749324631629945924347623452814484804302695429615347766269208862055297251399481097496792607151512106384491115241941375832475148707656805179243577507970470652709184322446635844049937991230875434035141953016706954228802899847598405025212267094783507558745889061000602591061766582039802059434295608552192068042663673562397201985948268771296604897029607599970689036605039319115148528468359269388337219168500817459741027589115043253888471423952720076508385933588034898911577107384535441193568468476975351858154045765051345142381213353006683333295463304178723362769210233546893363988082100423460763855727080604248831902904297897542025435948803206754953154500392986392412973550838111807278326817414863490354597800755348007337443942619195803813395558390996349460984837021559339130392386082430838890197823199906463316762475156291666396031434899152482396673523764845223537047318671493919007934112940175533401725440299557820435604420081803515371790890441032862974529733509700179668080253801470645869201682627121511054508901598322990557971956103642490695583017813326577872987591430557112912489765434609265022192018172908195507022860251884541930215759195624016558527280848165519643677329693845129594537062386008112662703622092333746546420077428433176510538990842933428604316798106327801988971335921456282268180599571651175054200763367906616535895913387522973634858641925315521847464788108792508191115661325958738583768416457819280466154461428023951937851388587990733129452457848684788025460620190795543640320890017452640015752678886643019251839144875505059385749623568573418763579233817052968087418241049258695510976736239291218195078969448908213646145897424552026715957589546814605389799595482038262986011682626413957838958384755088390444975643847329537966565065429785844482073955764737030619944419743134943434856457455894840818686198670489448321435,    15091158770353110043094147522710570656498060900577234783719960661476672213697965858395924321690239802223669957673840049012195861303541015451082025592180466401896956679630831713031141827569465607596311308630428997254725169731800048355447961491668940525226096674750983134223182212437800372699803621354936647258231529529281828003810952286404174218110802340184002914225308404961937168897194937469213367287107660479709208506916017238474429701395134282791082831827783056732057535942116908661911928902610424319945781838790909401599531305991109702143502430103861407601409258543539415045115799797187712471074026771189214660040735881151930741462166600472229023438106233998120307358804854706216709376335569903990851567957766916387968411869312597430312948603351203989493756750820699247766886652207686065092336310468326315427409339851585415164011608912927435587856979441322297242948071445924906209636105837161522237729109955565195220970734365514423235411853299517498004103826811569005725914939499097247248097858459449933088629506881451716696235813488682840729502319099179641634540722744028886222418673838887569156580825230061741495146349700272489224011808351894920923254137237816026168506551369327581568567719163503866307440457516712789500401400949339992400025363958076010251967987719321668268298435199974871351817734751235368997770801280316927026188279532637066645931611700914351878698535718166529701752900030469555069094722317519156980331980351355861263264891237410126466464240531942156683758712051076659223566976110286606089276659749820938958597271010051758844652424665593341213335404115655654669839273458022064436288499747389239943577573848276347238235412653832222539883374416636808950791222770271734462051102590838427622616773279643846933789045855541355688390188173503622483037461817175594969970808909889934531322480613970041063352421240982089876119756075136
]

t = (fs[3] + s*fs[1] - n*fs[0]) * pow(fs[2], -1, n) % n
x = sympy.Symbol('x')
pqrs = sympy.solve(x**3 - t * (x**2) + s * x - n)

print(pqrs[0]*pqrs[1]*pqrs[2] == n)

phi = int((pqrs[0]-1)*(pqrs[1]-1)*(pqrs[2]-1))
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

以上で，コンテスト終了となりました。

解けなかった問題たち

rewriter2（pwnable）

src.cを見ると

char buf[BUF_SIZE];
__show_stack(buf);

printf("What's your name? ");
read(0, buf, READ_SIZE);
printf("Hello, %s\n", buf);

__show_stack(buf);

printf("How old are you? ");
read(0, buf, READ_SIZE);
puts("Thank you!");

__show_stack(buf);

となっており，BUF_SIZEが0x20しかないところに0x100も読み取っていますから，このあたりを上手く利用しそうです。下の方を見ると

void win() {
    puts("Congratulations!");
    system("/bin/sh");
}

という怪しげな関数が定義されており，これを呼び出すことが目標となりそうです。また，__show_stack(buf)で親切にもメモリの状況を教えてくれているので適当にAAAAAとBBBBBBBを食わせてとりあえず実行してみます。

 [Addr]             | [Value]
====================+===================
 0x00007ffcef0c29a0 | 0x0000000000000000  <- buf
 0x00007ffcef0c29a8 | 0x0000000000000000
 0x00007ffcef0c29b0 | 0x0000000000000000
 0x00007ffcef0c29b8 | 0x0000000000000000
 0x00007ffcef0c29c0 | 0x0000000000000000
 0x00007ffcef0c29c8 | xxxxx hidden xxxxx  <- canary
 0x00007ffcef0c29d0 | 0x0000000000000001  <- saved rbp
 0x00007ffcef0c29d8 | 0x00007fae042c5d90  <- saved ret addr
 0x00007ffcef0c29e0 | 0x0000000000000000
 0x00007ffcef0c29e8 | 0x00000000004011f6

What's your name? AAAAA
Hello, AAAAA


 [Addr]             | [Value]
====================+===================
 0x00007ffcef0c29a0 | 0x00000a4141414141  <- buf
 0x00007ffcef0c29a8 | 0x0000000000000000
 0x00007ffcef0c29b0 | 0x0000000000000000
 0x00007ffcef0c29b8 | 0x0000000000000000
 0x00007ffcef0c29c0 | 0x0000000000000000
 0x00007ffcef0c29c8 | xxxxx hidden xxxxx  <- canary
 0x00007ffcef0c29d0 | 0x0000000000000001  <- saved rbp
 0x00007ffcef0c29d8 | 0x00007fae042c5d90  <- saved ret addr
 0x00007ffcef0c29e0 | 0x0000000000000000
 0x00007ffcef0c29e8 | 0x00000000004011f6

How old are you? BBBBBBB
Thank you!

 [Addr]             | [Value]
====================+===================
 0x00007ffcef0c29a0 | 0x0a42424242424242  <- buf
 0x00007ffcef0c29a8 | 0x0000000000000000
 0x00007ffcef0c29b0 | 0x0000000000000000
 0x00007ffcef0c29b8 | 0x0000000000000000
 0x00007ffcef0c29c0 | 0x0000000000000000
 0x00007ffcef0c29c8 | xxxxx hidden xxxxx  <- canary
 0x00007ffcef0c29d0 | 0x0000000000000001  <- saved rbp
 0x00007ffcef0c29d8 | 0x00007fae042c5d90  <- saved ret addr
 0x00007ffcef0c29e0 | 0x0000000000000000
 0x00007ffcef0c29e8 | 0x00000000004011f6

どうやら入力内容はbufの右上の方から埋まっていくみたいです。ここで，IDAを開いてwinとmainのアドレスの差を調べると0xCCでしたので，適当になんとなくこんな感じかなというものを書いてみて

f = open("in.txt", 'wb')
up = [0x00, 0x00, 0x7F, 0xAE, 0x04, 0x2C, 0x5E, 0x5C]
b = b''
for i in range(0x200):
    k = i % 100
    if 0x0c <= k and k <= 0x13:
        b += up[7-(k-0x04)].to_bytes(1, 'big')
    else:
        b += k.to_bytes(1, 'big')
f.write(b)
f.close()

cat in.txt | ./rewriter2.elfをしました。そうすると，以下を吐き出しました。

 [Addr]             | [Value]
====================+===================
 0x00007fff127136d0 | 0x0000000000000000  <- buf
 0x00007fff127136d8 | 0x0000000000000000
 0x00007fff127136e0 | 0x0000000000000000
 0x00007fff127136e8 | 0x0000000000000000
 0x00007fff127136f0 | 0x0000000000000000
 0x00007fff127136f8 | xxxxx hidden xxxxx  <- canary
 0x00007fff12713700 | 0x0000000000000001  <- saved rbp
 0x00007fff12713708 | 0x00007f3b0032cd90  <- saved ret addr
 0x00007fff12713710 | 0x0000000000000000
 0x00007fff12713718 | 0x00000000004011f6

What's your name? Hello,

 [Addr]             | [Value]
====================+===================
 0x00007fff127136d0 | 0x0706050403020100  <- buf
 0x00007fff127136d8 | 0x042c5e5c0b0a0908
 0x00007fff127136e0 | 0x1716151400007fae
 0x00007fff127136e8 | 0x1f1e1d1c1b1a1918
 0x00007fff127136f0 | 0x2726252423222120
 0x00007fff127136f8 | xxxxx hidden xxxxx  <- canary
 0x00007fff12713700 | 0x3736353433323130  <- saved rbp
 0x00007fff12713708 | 0x3f3e3d3c3b3a3938  <- saved ret addr
 0x00007fff12713710 | 0x4746454443424140
 0x00007fff12713718 | 0x4f4e4d4c4b4a4948

How old are you? Thank you!

 [Addr]             | [Value]
====================+===================
 0x00007fff127136d0 | 0x3f3e3d3c3b3a3938  <- buf
 0x00007fff127136d8 | 0x4746454443424140
 0x00007fff127136e0 | 0x4f4e4d4c4b4a4948
 0x00007fff127136e8 | 0x5756555453525150
 0x00007fff127136f0 | 0x5f5e5d5c5b5a5958
 0x00007fff127136f8 | xxxxx hidden xxxxx  <- canary
 0x00007fff12713700 | 0x0b0a090807060504  <- saved rbp
 0x00007fff12713708 | 0x00007fae042c5e5c  <- saved ret addr
 0x00007fff12713710 | 0x1b1a191817161514
 0x00007fff12713718 | 0x232221201f1e1d1c

*** stack smashing detected ***: terminated
Aborted

目論見通りret addrは0x00007fae042c5e5cになりましたが，なにやら怪しいことをしているのを検知されてしまったようです。canaryというところが隠されているようで，なんだこれはと英和辞書を引くとカナリアの他に《俗》密告者とあって，この意味ですかねとなりました。そういえばカナリアのピー子ちゃんはストーブのガス管がはずれていたのを知らせていたっけなどと考えていました。どうやらこのcanaryを書き換えてしまうと密告されてしまうようです。しかしながらcanaryの内容は隠されてますし，ret addrまで行くにはここを通る必要がありそうだしということでここで行き詰ってしまいました。

phisher2（web）

サンプルになっている

curl -X POST -H "Content-Type: application/json" -d '{"text":"https://phisher2.beginners.seccon.games/foobar"}' https://phisher2.beginners.seccon.games

を投げると

{"input_url":"https://phisher2.beginners.seccon.games/foobar","message":"admin: Very good web site. Thanks for sharing!","ocr_url":"https://phisher2.beginners.seccon.games/foobar"}

を投げつけられました。a.pyを見るとtext = request.json["text"]で"https://phisher2.beginners.seccon.games/foobar"を取っていて，これをadmin.pyのinput_textに投げ込んでいるのが見えました。その後いろいろあってrequests.get(f"{input_url}?flag={FLAG}")をしているのが見えたので，このクエリストリングの内容を見ることができればよさそうです。ということで，curlについていろいろ調べると--traceとか-vとかでいろいろ見れるみたいなのでこれらを試したり，Wiresharkで通信を見てみたりしたんですが，よく分からずとなってしまいました。

poker（reversing）

とりあえずpokerを実行すると1か2の入力を求められるのでしばらく遊んでいると

================
| Score :   0  |
================

[?] Enter 1 or 2: 1
[-] Player 2 wins! Your score is reseted...

================
| Score :   0  |
================

[?] Enter 1 or 2: 2
[+] Player 2 wins! You got score!

================
| Score :   1  |
================

[?] Enter 1 or 2: 2
[+] Player 2 wins! You got score!

================
| Score :   2  |
================

[?] Enter 1 or 2: 1
[-] Player 2 wins! Your score is reseted...

================
| Score :   0  |
================

[?] Enter 1 or 2: 2
[-] Player 1 wins! Your score is reseted...

================
| Score :   0  |
================

[?] Enter 1 or 2: 1
[+] Player 1 wins! You got score!

================
| Score :   1  |
================

[?] Enter 1 or 2: 2
[+] It's a tie! Your score is reseted...

================
| Score :   0  |
================

[?] Enter 1 or 2: 1
[-] Player 2 wins! Your score is reseted...

================
| Score :   0  |
================

のようになっており，どうやら1か2かを選んで，勝つとscoreが1増えて負けると0になるようです。
pokerをIDAで開いて，main関数をそれらしい名前に変えると

score = 0;
sub_21C3();
for ( i = 0; i <= 98; ++i )
{
  showScore_2222(score);
  inputNum = getInput_2179();
  score = sub_1FB7(score, inputNum);
  if ( score > 99 )
  {
    sub_11A0();
    return 0LL;
  }
}

となっていました。どうやらscoreが100以上にならないと勝てないらしく，何らかの方法で次の勝者を予測する必要がありそうです。問題文からメモリを見ることのできるものが必要そうなので調べると，gdbというものでできるみたいです。sub_1FB7でrsp+いくつかのところで乱数を使って勝者を決めているみたいなので，さっそくgdb poker.elfで走らせて，x/100 $rspでメモリを見たんですが，1が勝つ/2が勝つ/引き分けのパターンがよくわからなかったです。HIDWORD(v6)とHIDWORD(v7)を比較しているみたいなんですが，どう考えても違うでしょうみたいなものが多く，結局法則性を見出すことはできなかったです。ここで，入力を受け取ってから乱数で勝者を生成していることに気付いたので，これ結局分かったところで無理なのではないかと，何も手立てがなくなってしまいました。

switchable_cat（crypto）

problem.pyを見るとLFSRなるクラスが定義されており，ざっと見るとr_{n}からr_{n+1}に行くときに，1つだけ右にビットシフトして，r_{n}の下9bitを見てnの偶奇によっていくらかのbitを選んでそれらのXORを128bitめに補うという感じみたいです。何ということはない操作ですが，問題はこれをord("🐈")*ord("🐈")*ord("🐈") * 8回繰り返すことができないということです。これを実際に計算すると16780361924612096 = 1.7 \times 10^{16}ですから到底現実的な時間では終わりません。そこで何か周期性があるんだろうかとρ法のようなことを2000000回くらいまわしてみたんですがループしてくれず，ダブリングみたいなことができるんだろうかと思ったんですがいい方法が思いつかず，解くことができませんでした。

おわりに

解けた問題の内訳は

  • crypto 3問
  • pwnable 1問
  • misc 2問
  • web 2問
  • reversing 2問
  • welcome 1問

で合計829pt，788チーム中100位ちょうどでした。取りたかったcryptoをしっかり解くことができて，十分戦えたという達成感が残り大変良かったです。 Certificate of Participation SECCON Beginners CTF 2023 Team:toku4388(829pt) Rank:100/778