Fireshell CTF 2019 Biggars writeup

gist.github.com

とにかく長大なパラメータを持つRSA。nは大きいが小さい素因数からなっていて、簡単に素因数分解できる。

>>> list(factor(n))
[(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]

3つ以上の素因数からなるRSAはMulti-prime RSAと言われる。この場合にもRSA暗号は成立する。オイラーのφ関数を一般化して、 と表されるとき、 である。あとはを計算して復号すれば良い

ただしこの問題の場合、が非常に大きいため、の計算はそのままでは非常に時間がかかる。そこでRSA-CRTの考え方を使い、中国剰余定理を用いてこの計算を高速化する。

import gmpy
from params import n, e, c

def chinese_remainder(ms, ns):
    assert(len(ms) == len(ns))

    n = 1
    for i in range(len(ms)):
        n = n * ns[i]

    r = 0
    for i in range(len(ms)):
        p = n / ns[i]
        r += ms[i] * gmpy.divm(1, p, ns[i]) * p
    try:
        return long(r % n)
    except:
        return int(r % n)

factors = [(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]


ms = []
ns = []
for p, k in factors:
    n = pow(p, k)
    phi = pow(p, k) - pow(p, k - 1)
    d = gmpy.divm(1, e, phi)
    m = pow(c, d, n)
    ms.append(m)
    ns.append(n)

m = chinese_remainder(ms, ns)
print(bytes.fromhex(hex(m)[2:]))

zer0pts CTF 2021 振り返り

大筋まとめ

zer0pts CTF 2021 は 成功と言ってよさそう。本番めちゃくちゃヤバいトラブルはなかったし、問題も安定してクオリティの高いものが提供できた。

諸情報

かつてない参加者数になったし、賞金もかつてない量になった。こんなに大規模なCTFの運営に携わることになるとは

Name	Value
開催期間	2021-03-06 09:00:00 +09:00 – 2021-03-07 21:00:00 +09:00
登録チーム数	1449
1点以上獲得したチーム数	951
Welcome / Survey 以外の問題も通したチーム数	259

正確な情報ではないけど、参加”者”数だと 3000〜4000 くらいだと思う

Top Teams

Name	Score
Super Guesser	5211
K-Students	5153
r00timentary	5153

スコアサーバ

• InterKosenCTF2020でも使ったkosenctfxをまた採用した
• かなり安定して動作していて、CTF終了直後にアクセスが集中してレスポンスが悪くなったとき以外は不調は見られなかった
  • このときはDB側が遅くなっていた
• 前回からいくつか改造した
  • RankingでのFirst - Third Bloodの表示やDiplomaなど
• Rankingページの描画が重たくなってしまったのは反省点
  • 全チームが何を解いたかを表示しているので描画がある程度遅くなるのは当然
  • さらにFirst - Third Bloodを表示するために各問題に対する正答を提出時刻でソートしているのでまあ遅い
    • これは途中でこの処理をWeb Workerに任せる用に変更したことで多少改善した
• 一部SQL文にtypoがあり、パスワードリセットが初期ではうまく動かなかった
  • テストを書こう
• DO の MySQL、初期状態では ANSI_QUOTES が有効になっていて、gormが発行するSQLと噛み合わないことがあった
• フラグがcase insensitiveに受け入れられていた
  • びっくりした。SQL側の設定だと思う。反省です
• フロントエンドは競技中に様々なマイナーバージョンアップが加わった
  • 正直必要ないと思ったが、なにやら必要だと思った人もいて、めちゃくちゃ小刻みにデプロイ要求をされてすごく疲弊した
  • CTFのスコアサーバがmobile friendlyである必要、あるのだろうか
    • 当然対応していたほうが良いに違いはないが、本番の真っ最中にこれをやるのはかなりRiskyだと思うが……

インフラ

• 基本的にDigitalOceanが提供するサービスでインフラ管理を行っていた
  • 3k CTF の prize として DigitalOcean の credit をもらっていたのでDOにしたが、そうでなければAWSなどを使っていたと思う。かゆいところに手が届かない
• スコアサーバ（API側）は最近登場したDigitalOcean App Platformというやつを利用した
  • herokuやFargateのようなPaaSで、Docker Imageからシュッとアプリケーションが立ち上がって便利だった
    • heroku触ったことないので嘘かも
  • アプリケーションのログをエクスポートできないのはめちゃくちゃ不便だった
    • あんまり関係ないけど、サーバのアクセスログものすごい勢いで流れていてコンピュータスゲーになった
• スコアサーバ（フロント側）はDigitalOcean Spacesを利用した
  • S3 のようなやつで、CloudFrontを噛ませなくても自由にドメインを決めてCertをつけてCDNがついてくる（Cache Purgeし放題っぽい？）は嬉しいけど、デフォルトルートという概念がなく、必ず index.html をつけてアクセスしないと403になるのがものすごくダサい。DOは早く対応してほしい
  • チーム内でもこれがめちゃくちゃ嫌だから他Platformにしてくれという声があったが、競技開始直前だったことや、すべてをDOで完結させる簡潔さを損ないたくないことからRejectした
  • 流石にこちらは終始安定して稼働していた
• 問題サーバは基本的に2GB Memory 2 shared vCPUs のインスタンスをカテゴリ毎に立てた
  • こちらもかなり安定して稼働していた
  • 結局問題がどれだけ安定して稼働するかによる
  • DigitalOceanはデフォルトでは3個までしかDropletを建てさせてくれないので、それ以上の数を立てたい場合（や、もうちょっと高級なインスタンスを使いたい場合）は事前に申請する必要がある。一回Rejectされたので焦ってSupport Ticketを切ってお願いしたら素早く対応してくれた
• 全体的にコストはかなり安く抑えられたと思う。全部合わせても$20から$30の間くらいではないだろうか
  • やっぱりDBが結構高くつくが、システムの要なのでこのくらいの出費は全然OKと思うのが良さそう
  • 結局CTF終了後1週間程度dropletsを立ち上げ続けていたので$50〜%60くらいになった
• 問題のデプロイや、IPのBanを自動化するCI/CDパイプラインを作成した
  • GitLab CI便利
  • Ansible 便利だけど遅いがち
    • Ansible の信用できるDocker ImageというのがPublicにはないので、毎度 pip install ansible をするような構成にしてみたが、これかなり遅くて実行時間の何割かを持っていっているのでやめるべきだった
  • push する度に何度もpublic keyを配布したりしていて、Ansibleの冪等性からはそれでもいいんだろうけどやっぱり遅いのでなにか実行を制御するしくみは欲しいと思った
  • 様々な理由でCI/CD パイプラインの実行時間を雑に消費した結果、開催当日の朝4時とかになってGitLabで使えるFreeの実行時間がなくなってしまい焦った
    • specific runnerを急いでデプロイした。簡単にできてすごい
• インフラは結局ほとんど一人で面倒を見ているが、実際は良くないんだろうなと思う
  • 私が寝ているときに問題が発生するとか、いくらでもあり得る
• Prometheus などを使った監視システムも作っていたが、採用やめた
  • あんまりちゃんとテストできていなかったので余計な不安を抱えたくない
  • しかし監視は重要なのでいつまでも目をそむけてはいられない
• 問題のConnection Check / Solvability Checkも仕組みをつくったりはしたが、あまり出来がよくなかったので採用しなかった
• このあたり本当にLMTはすごいなと思う

提供した問題

Authorごとの問題の提供数は以下の通り。うーんptr-yudai CTF！　作問能力どないなっとるんや

Author	Count(*)
16	ptr-yudai
5	theoldmoon0602
2	st98
2	mitsu
2	s1r1us
2	zer0pts
1	x0r19x91
1	(=^·u·^=)

• 提供した問題は全体的に評判が良くて何より
  • No guess をちゃんと達成しているのもよかった
• 当初48時間CTFの予定だったが問題数に不安があって36時間になった。最終的な問題の解かれ具合をみても36時間が適切だったと思う
  • そもそもCTFの48時間は長すぎるんだよな。しかしTimezone - Fairnessがほしければ48x 時間開催することになる
    • 結局時間に関係なく私生活をなげうってずっと取り組み続けた人が強いんだからTimezone - Fairnessとか気にしなくていいと個人的には思っている
  • 特にwebとrevの問題数に不安があった。webはまあいいとしてもrevの作問リソースがかなり厳しい
    • rev の面白い問題をどうやったら作れるのか、2, 3年考えているけどrevの問題とかないがちなのでわからない
  • 開催直前に問題が発覚して慌てて修正した問題や、今回は採用見送りになった問題がある
    • 慌てて修正した問題も個人的には次回に回したかった。まともにチェックできていないということで出題するのは怖い。一つの壊れた問題でCTF全体が壊れるので
    • CTF始まってから問題追加しようとする人がいたがやめて欲しい。Rejectするのも結構しんどい
      • あとでも言及すると思うけど、これまではかなり少人数で運営していたからコンセンサスを取ろうとする必要もなく目指す方向が一致していたが、だんだん人数が増えて、あと使ってる言語も違ったりしてそういうところで同じ意識を持つのが難しくなっている
• 全体的な難易度は去年より上がったという声が多かった
  • そんなに変えたつもりはないので勝手に評価基準がズレたっぽい。成長しているということだろうか
  • 難しい問題を提供したいんじゃなくて面白い問題を提供したい、と個人的には思っている。難易度偏重にならないように気をつけたい
• 事前に予想していたのとは全然違う解かれ具合になったりした
  • GuestFS:AFR はwarmupタグがついているにも関わらず15solves
  • その他にも事前に想定していた難易度とはSolve数が逆転している問題がいくつかあった
  • 結局、難易度の推定は難しいということ
• 質問をもらっても、基本的には"try harder", "no hint" と返すことになっていた
  • CTFは競技なので良いと思う。ただ、上手い質問の仕方というのはあったりするので、JOIやなんかのように事前に決められた答えが帰ってくる仕組みを作るのが良いんだろうな。そこまでするかどうかというのは置いておいて
• いくつかunintended solutionはあったが、許容範囲だと思う
  • PDF Generatorは基本的に全部unintended solutionで解かれていたのであとからNot PDF Generatorを提供した
    • 個人的にはこれも必要なかったと思っているが、あまり強く口を出せる領域でもない
• いくつかの問題ではアクセスが結構集中して、サーバが重たくなったりする時間があった
  • そういう懸念がある問題は基本的にPoW / CAPTCHAを入れるのが良いと思う。これは今後の問題チェック時の確認事項に追加しておきたい
    • そういうものを文書化しているわけではないが、そろそろ文書化するのが良さそう
    • PoWは嫌いな人もいるだろうが、必要なのだからしかたない。しかしPoWを提供する時はWorkerのサンプル実装は提供されるべき

その他

• Discordでnew challengeのアナウンスとsolve のアナウンスを入れていたが @everyone みたいなチーム名で登録して人々に迷惑をかける人がいた
  • これができるようにしていたのはまあこちらが悪い
  • 正直そんなことをする人がいるとは思ってなかったのでびっくりした。なんの利があったんだろう
  • それに乗っかる人もいた
• 自分の提供した問題で、提供した配布ファイルが古いもので解けないと言われて焦って配布ファイルを更新したが、更新した配布ファイルも古いままだったりした
  • 焦っていた……
• prize、急に増えてびっくりした。ありがたい
  • このあとprizeを配る作業がまだある。終わりまでしっかりやりたい

個人的なことの振り返り

• 楽しかった。CTF運営は最高の娯楽。やめられねぇぜ
  • 準備中 / 終わったあと / writeup と survey を読んでいるときがそれぞれめちゃくちゃ楽しい
  • 運営中は常に不安と戦いながら監視をしている
• 自分の立ち位置は、「作問者」「インフラ担当」「当日運営」だったと思う。いわゆる"admin"（ここではrng_58さんのような立ち位置を意味している）だったかはわからない
• 英語できないのでアナウンス業をptr-yudaiとかst98さんに丸投げしていたのは申し訳ないなと思っている
• 結局 Crypto しか提供できておらず、偏っていて良くないなと思っている
  • Cryptoにしても、もう一段階難しい問題が作れるようになりたい
    • input 増やしていかなければ
  • Web / Rev あたりの簡単だがちょっと頭を使うみたいな問題を作れるようになって、 Web 屋 Rev 屋に本質問題に注力してもらいたいな
• 当日は早起き & 夜ふかしでめちゃくちゃ疲れた
  • CTF運営は精神力も使うし体力も使う
• 運営中ptr-yudaiと通話をつないで喋っていたのは良かった
  • 楽しかったし情報の伝達が早いし意思決定もはやくなる

Union CTF 2021 writeup

Mordel Primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG

assert k < 2^128
assert FLAG.startswith(b'union{')

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
Q = k*P
R = (k+1)*P

p = Q[0].numerator()
q = R[0].numerator()

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

RSAの秘密鍵 を有理数体上の楕円曲線 上の2点のx座標の分子から生成しています。少し実験すると、有理数体上では が大きくなればなるほどその座標の値も大きくなっていることがわかります。これは結構なスピードで大きくなるので、の値を全探索すれば適切なが見つかりそうに思えます。

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)

N = ...
c = ...

for k in range(2, 1000):
    Q = k*P
    R = (k+1)*P

    M = Q[0].numerator() * R[0].numerator()
    if N == M:
        p, q = (Q[0].numerator(), R[0].numerator())
        break
else:
    quit()

e = 0x10001
N = p*q
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)

m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]))

感想

要素が無限にある有理数体上の楕円曲線なのだから、値がどんどん大きくなるのはそれはそうだよなぁと思った。そこにたどり着くまでに色々机上の空論をこねくり回してはうまく行かないと頭を抱えていましたが、実験するとすぐだったので実験は大事ですね。

committee

flag.txt というファイルだけが存在する git リポジトリと、そのコミットログが渡されます。リポジトリ自体のログは最初の2コミット分しか記録されていません。また、flag.txt の中身は union{*******3*********_************r****d**********} となっています。

...

commit cb18d2984f9e99e69044d18fd3786c2bf6425733
Author: Peter G. Anderson <pepega@legal.committee>
Date:   Tue Apr 14 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 32, 33, 34

commit dca4ca5150b82e541e2f5c42d00493ba8d4aa84a
Author: Christopher L. Hatch <crisscross.the.hatch@legal.committee>
Date:   Mon Mar 23 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 8, 31, 36

commit c3e6c8ea777d50595a8b288cbbbd7a675c43b5df
Author: Pamela W. Mathews <pammy.emm@legal.committee>
Date:   Fri Mar 13 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 18

commit 08e1f0dd3b9d710b1eea81f6b8f76c455f634e87
Author: Robert J. Lawful <boblaw@legal.committee>
Date:   Wed Mar 4 12:00:00 2020 +0000

    Initial formation of the flag-deciding committee.

与えられた情報から、この問題はコミットログを頼りにフラグのi文字目の値を探索し、ログに残されたコミットハッシュと一致しているかを調べていくことで解けそうです。このためには、gitのコミットハッシュがどのように決まるのかを知る必要があります。これには Gitのコミットハッシュ値は何を元にどうやって生成されているのか | メルカリエンジニアリング というブログ記事が参考になりました。 .git/objects 以下に存在するファイルと照らし合わせながら処理をかいて、最終的に次のようなプログラムで解くことができました。

import re
from datetime import datetime
import zlib
from hashlib import sha1
from typing import List
from ptrlib import brute_force_attack, brute_force_pattern

def get_indices(s: str):
    xs = re.findall(r"\d+", s)
    return [int(x) for x in xs]

class Commit():
    def __init__(self):
        self.binsha = b""
        self.author = ""
        self.date = 0
        self.message = ""

    def __repr__(self):
        return "commit {}\nAuthor: {}\nDate:   {}\n{}".format(self.binsha.hex(), self.author, datetime.fromtimestamp(self.date).strftime("%c +0000"), self.message)

    def get_hash(self, flag, parent):
        blob = "blob {}\0{}".format(len(flag), flag)

        treecontent = b"100644 flag.txt\0" + sha1(blob.encode()).digest()[:20]
        tree = b"tree " + str(len(treecontent)).encode() + b"\0" + treecontent
        treehash = sha1(tree).digest()[:20]

        obj = "tree {}\nparent {}\nauthor {} {} +0000\ncommitter {} {} +0000\n{}".format(treehash.hex(), parent.hex(), self.author, self.date, "Flag-deciding Committee <committee@legal.committee>", self.date, self.message)
        target = b"commit " + str(len(obj)).encode() + b"\0" + obj.encode()
        # return repr(target)
        return sha1(target).hexdigest()


with open("log.txt") as f:
    lines = f.read().strip().split("\n")
    commits = [] # type: List[Commit]
    commit = Commit()
    for i in range(len(lines)):
        if lines[i].startswith("commit "):
            if commit.binsha:
                commit.message = commit.message[:-1]
                commits.append(commit)
                commit = Commit()

            commit.binsha = bytes.fromhex(lines[i][len("commit "):])

        elif lines[i].startswith("Author: "):
            commit.author = lines[i][len("Author: "):]

        elif lines[i].startswith("Date:   "):
            commit.date = int(datetime.strptime(lines[i][len("Date:   "):], "%c %z").timestamp())

        else:
            commit.message += lines[i].lstrip() + "\n"
    commits.append(commit)

flagstr = "union{*******3*********_************r****d**********}\n"
offset = 5
commits = commits[:-2][::-1]
for i in range(1, len(commits)):
    indices = get_indices(commits[i].message)

    for b in brute_force_attack(len(indices)):
        p = brute_force_pattern(b)
        flag2 = list(flagstr)
        for j, k in enumerate(indices):
            flag2[offset + k] = p[j]

        h = commits[i].get_hash("".join(flag2), commits[i-1].binsha)
        if h == commits[i].binsha.hex():
            flagstr = "".join(flag2)
            print(flagstr)
            break
    else:
        raise Exception()

感想

gitのコミットハッシュに関する問題はどう出題したものかと思っていましたが、とてもきれいな出題がなされていてすごいと思いました。そして勉強になった。最初の2コミットが残されていて、自分の書いたプログラムが正しいかどうかをそれで検証できる用になっているのがとても親切だと思います