kurenaif 2000 subscribers challenge writeup

強いCTFerかつVTuberのkurenaif先生が2000subscriber記念に問題を提供されていたので取り組みました。面白かったです。

kurenaif先生のチャンネルはこちら

www.youtube.com

問題はこちら

github.com

383bitの平文を40bit程度のを用いたRSAで400回暗号化しています。40bitの素因数分解は簡単なので、暗号文を復号すればいいと思いきや、なので復号に成功したとしても全体がわかるわけではありません。このような場合の対応として、各暗号文を復号して400個のを得て中国剰余定理に従って上のを求めるテクがあります。

しかしここで問題を難しくしているのが、公開鍵です。です。はが素数であることから偶数×偶数＝偶数であり、はまず間違いなく満たされません。

このとき、暗号文のe乗根は一意に定まらず、複数個存在します。が5を素因数に含んでいないケースだけを考えても、各暗号文ごとに少なくとも個程度のe乗根が存在して、そのうちを満たすものは一つだけです。各暗号文についてe乗根全体を探索するのは明らかに不可能です。

そこでe乗根の数を減らすことを考えます。まず、ではなく、について考えます。これで組み合わせの個数が減ることはありませんが、問題を解くのに不便な素因数を除外して考えることができるようになります。

問題を解くのに不便な素因数とは何でしょう。例えばが5を素因数に含むケースは今回はスキップしてしまうことでを公開鍵とした暗号文についてだけ考えればよくなります。

また、のとき、この剰余の法のもとでの乗根の数は2個に限定されます（どうやって証明するのかわからなかった）。この性質を使うことで、という暗号文についての答えの候補を2個に絞ることができます。

はおよそ20bitですから、20個ほどの組を集めれば通りの全探索での候補が列挙でき、そのなかにフラグがあることを期待できます。

実際には22個の組をつかってやりました。

import ast
with open("output.txt") as f:
    f.readline()
    e = ast.literal_eval(f.readline().strip().split("= ")[1])
    ns = ast.literal_eval(f.readline().strip().split("= ")[1])
    cs = ast.literal_eval(f.readline().strip().split("= ")[1])

e1 = 5^4
e2 = 2^5

xs = []
mods = []
cnt = 0
for i in range(len(ns)):
    for p, _ in factor(ns[i]):
        if p % 4 == 3 and (p-1) % 5 != 0:
            dp = int(pow(e1, -1, p-1))
            xs.append(pow(cs[i], dp, p))
            mods.append(p)

roots = []
for i in range(len(xs)):
    r1, r2 = GF(mods[i])(xs[i]).nth_root(32, all=True)
    roots.append((int(r1), int(r2)))

T = 22
from tqdm import tqdm
from itertools import product
print(2^T)
for pat in tqdm(product([0, 1], repeat=T)):
    rs = []
    for i in range(T):
        rs.append(roots[i][pat[i]])
    x = CRT_list(rs, mods[:T])
    x = int(x)
    if x.bit_length() == 383:
        print(x.to_bytes((383 + 7) // 8, "big"))

kurenaif先生、登録者数2000人突破おめでとうございます。これからもますますのご活躍を期待しています。

Approximate GCDとして解く問題 - RCTF 2021 Uncommon Factor 2 / Midnightsun CTF 2021 Finals Flåarb.tar.xz writeup

時期が近くて解法が近いので2件writeupです

RCTF 2021 Uncommon Factor 2

from multiprocessing import Pool

size = 2^7

flag = open("flag.txt", "rb").read()
assert len(flag) == 22
assert flag[:5] == b"flag{"
assert flag[-1:] == b"}"
seed = flag[5:-1] # 128 bit
seed = (int.from_bytes(seed,'big')<<104) + (randint(0,2^80)<<(128+104)) # 312 bit
ub = seed + 2^104
lb = seed

threads = 64

def f(i):
    p = random_prime(ub, lbound=lb, proof=False)
    q = random_prime(2**200, proof=False)
    N = p*q
    return N

def reseed(i):
    set_random_seed()

pool = Pool(processes=threads)
pool.map(reseed,range(size))
lN = pool.map(f,range(size))
pool.close()
pool.join()

lN.sort()
with open("lN.bin","wb") as f:
    for n in lN:
        f.write(int(n).to_bytes(512//8,"big"))

512bitの合成数が128個与えられます。それぞれという形式になっています。多少開いていみるととかけます。

が比較的小さければからを求める問題はApproximate GCD Problemとして知られており、簡単なインスタンスは次のような格子のLLLで解けます。確かにこの基底で解かれそうなことはわかるのですが、どうやってこの格子を思いつけば良いのかが未だにわかっていません。

from ptrlib import chunks

with open("lN.bin", "rb") as f:
    data = f.read()

ns = chunks(data, 512 // 8)
ns = [int.from_bytes(n, "big") for n in ns]

ns = list(set(ns))
print("[+] done {}".format(len(ns)))

K = 2^(104 + 128)

M = matrix.identity(len(ns)) * - ns[0]
M[0,0] = K
for i in range(1, len(ns)):
  M[0,i] = ns[i]

t1 = cputime()
print("[+] {}x{} LLL...".format(M.nrows(), M.ncols()))
L = M.LLL()
t2 = cputime()
print("[+] done in {}".format(t2 - t1))

v = Matrix(ZZ, L[0])
v = v * M^(-1)

q = int(v[0,0])
print(ns[0] % q)
print(ns[0] // q)

Midnightsun CTF 2021 Finals Flåarb.tar.xz

なんでこんな問題名なんだろう

次のようなファイルが与えられます（長い数値は省略しています）。どうしてこんな形式にしたんだろう。そういえばMidnightsunのCrypto問題は毎回こういう形式ですね。

sage: p1 = random_prime(2^2048) 
....: p2 = next_prime(0xcafebabe * p1 + randint(0, 2^1024)) 
....:  
....: q1 = random_prime(2^512) 
....: q2 = random_prime(2^512) 
....:  
....: n1 = ZZ(p1 * q1) 
....: n2 = ZZ(p2 * q2)                                                                                                                                                                                                                                                                                                                                             
sage: c1 = pow(int.from_bytes(flag, byteorder='little'), 2^16 + 1, n1) 
....: c2 = pow(int.from_bytes(flag, byteorder='little'), 2^16 + 1, n2)                                                                                                                                                                                                                                                                                             
sage: n1                                                                                                                                                                                                                                                                                                                                                           
...
sage: n2                                                                                                                                                                                                                                                                                                                                                           
...
sage: c1                                                                                                                                                                                                                                                                                                                                                           
...
sage: c2                                                                                                                                                                                                                                                                                                                                                           
...

つまり という形式のRSAで、がかなり小さいです。 と近似できるので、こちらもApproximate GCDとして解くことができます。

n2_ = n2 // 0xcafebabe

for i in range(512):
  K = 2^(1024 + i)

  M = Matrix([
      [K, 0, n1],
      [0, K, -n2_],
  ])
  L = M.LLL()

  for row in L:
      # ys = [abs(x) for x in row]
      zs = [abs(x//K) for x in row]
      for q in zs:
        for n in [n1, n2]:
          g = (gcd(n, q))
          if g != 1:
            print(g, q)

しかしこの問題の想定解は連分数展開らしいです。どうやって思いつくんだろう

CakeCTF 2021振り返り

去年まではptr-yudai, yoshikingと共にInterKosenCTFを開催していたが、”Kosen”と名前に入っていると誤解を生むだろうということで同じ面子で名前を変えてCakeCTFを開催した。また今年からは”初心者向け”というのももう嘘になってきているだろう、ということで”CTFの”初心者〜向け、つまりCTF初心者からCTF中級者、上級者にもそれなりに楽しんでもらえるようなCTFを目指すことにした。ちなみになぜCakeなのか、ということについてはyoshikingがその秘密の鍵を握っている。

スコアサーバ・インフラについて

今年もスコアサーバや問題のインフラについては私が一手に担っていた。これはあまり良くない状態で、インフラの様子を見れる人は複数いたほうが良い。なにせ36時間のCTFを開催しようというのだから、どうしても睡眠は必要になる。私が休憩しているタイミングでなにか問題が発生したときにどうするのか、というリスクが拭えない。理想を言えば3人しか居ないのだから全員がインフラの状態について把握していることが望ましい。一応メモは残すようにしているからそれを手がかりに対応することはできるだろうが、それにはインフラ周辺の知識が必要になる。この運営のためだけにインフラの知識を身につけることを二人に要求するのも酷なので、何も起こらないだろうと思ってリスクは受け入れている。

実際に何も起こらなかったかといえばそんなことはなく、コンテスタント向けに提供しているAPIにフラグが含まれているという過去類を見ないレベルの失敗が競技の開始直後に発覚した。これについては即座にサーバを停止させ、修正をデプロイして漏れたフラグの問題を更新して再開するという対応を取った*1。開始直後に気がつけたことは幸いで、コンテスタントへの影響が小さく抑えられたほか運営が全員揃っていたので、各自の問題のフラグを可能な限り高速に更新することができた。

なぜこのような問題が起きたのかについて考える。今回も前回のInterKosenCTF・zer0pts CTFに引き続いてkosenctfxを使用したのだが、今回のためにいくらか変更を施していた。変更の一つにスコアの遷移をsubmissionごとに細かく記録するというものがあるのだが、これを効率的に行うためにいくらかデータの持ち方を変更した。そこでadminとcontestantでデータを出し分けている箇所が失われてしまった。これを防ぐにはテストを書きましょうだとか、QAをやりましょうという話になる。テストは書きましょう。はい、すみません……。一応開催の1〜2週間ほど前にはプライベートでスコアサーバを建てて動作確認をするようにしているし、動作確認をお願いしているが、今回はほとんどこれまでのkosenctfxと同じものだったこともあって確認がおざなりになってしまったことは否めない。

スコアサーバ・インフラについて2

今回もこれまでと同様にインフラの構築にはDigital Oceanを利用した。AWSやGCPのほうが明らかにかゆいところに手が届くので、特に理由がなければそちらを利用するのが良いと思うが、CTFをやっているとDOのCreditが賞品になっていることが時々あってCreditが貯まるのでそれらを無駄にしない意味でDigitalOceanを使っている。DOはSpacesのDefault Indexがないのと最近ログインが（特にウィンドウサイズの小さいときに）やりにくくなったのと、デフォルトのDropletの最大数の制限が最悪です。

Creditが余り気味ということもあって多少贅沢に、今回はスコアサーバ用にメモリ4GB・2Core CPUのインスタンス（$20 / month)を採用したところ、参加者数がそれほど多くないこともあってリソースは余り倒しだった。常時メモリ使用量は400M / 4G程度で、2コアあるCPUはせいぜい5%程度しか稼働しておらず、計算資源がもったいないほどだった。安定をとってCTFの開催中はMySQLとRedisはマネージドのものを使っているのだが、わざわざ高いCreditを消費してまでマネージドのものを使わず、Dockerなどでホストしてもよかったかもしれない。

問題サーバは pwn, web, misc(rev), othersの4つを建てた。それぞれメモリ2GB・2Core CPUのインスタンス（$15 / month）で建てたがこれらもかなりリソースに余裕があり、すべてを一つのインスタンスで賄える程度だった。CTFの参加者や問題の負荷を事前に読み切るのは難しいためこれを節約するのは難しいが、オートスケールにうまく対応させて問題をデプロイできるようになればこのあたりの心配や無駄は無くせるかもしれない。

運営にかかった総費用はあとで書きます。

2021/09/06、スコアサーバや問題サーバをすべて停止した。準備（デプロイ練習など）・事前のスコアサーバ公開・競技用の問題サーバ、競技後の縮小した問題サーバ等合わせておよそ $40 ほどがかかかった。主に長時間稼働・比較的大きいインスタンスを利用していたスコアサーバと、DBサーバにかかる費用だった。

スコアサーバについて3

今回はスコアサーバのフロント側に特に手を入れた。CakeCTFという名前でCTFを開催するからにはそれらしいものを提供するべきだと考えたからだ。これまでのkosenctfxのフロントはVue.jsで書かれていたが、今回はNextjsを使った。Nextjsのようなフレームワークを使ったほうが開催後のデータの静的化に便利だと考えたからだが、結局SSRをうまく使いこなせなかったのでこれはあまり意味がなかった あとからサイトを全静的化するときに全部SSGでできて便利だった。またルーティングの都合上、next exportによる静的ファイルの生成とホストではうまく動かなかったのでnext startでnodeインスタンスを建てる必要が生じてしまった。topを見ているとこのnodeのVIRTの値が70Gとかになっていて結構不穏だった。実際になにか問題になることはなかったが。

それよりも今回のスコアサーバで大事だったのはデザインだろう。アンケートの集計をみていてもデザインについてお褒めの言葉をいただくことがあった。今回のデザインについては全く良いものが思いつかなかったので某所で相談したところデザインに自信のある数名がこぞって案を出してくれたので、その中でもっともスコアサーバで使いやすくまたCakeCTFのイメージにあっていたchigeくんのものを採用させてもらった。非常に優れたデザインで、CTFの世界観が補強されたと思う。ありがたい。

スポンサーについて

prizeやインフラ周りでの費用を3人ですべて負担するのは難しいがCTFの勝者にはprizeがあってほしいという願いから心苦しくもCTFの開催を応援してくれる個人からの寄付を募ったところ、5名からおよそ9万円程度の援助が得られた。正直にいってこれほどの額が集まるとは思わず多少持て余し気味ではあるが*2、おかげでDOのCredit切れに怯えることなくインフラに投資できたし、prizeを豪華にすることもできる。本当にありがとうございます。prizeを送っても余った分については次回以降のCTFのprize等の補助にあてることにする予定でいる。また、今回スポンサーしていただいた皆様にも心ばかりのお礼としてsponsor prizeをお返しする予定でいる。

スポンサーについては今回はtwitterのDMという形で募集した。クラウドファンディングのプラットフォームを使うという選択肢もあったと思うが、大げさに感じてやらなかった。やるとどのような面倒が生じてどのような利益があるのか調べるべきだったとは思うが、次また似たような機会にどうするかは考えていない。

作問について

毎度のことながら作問は難しい。今年もまたptr-yudaiの一人舞台になってしまった感がある。ptr-yudaiの作問能力が高く、私とyoshikingがそれに及ばない以上仕方のないことではあるが、それにしてもこんなに差がつくと厳しい。私はcryptoの問題はいくつか作れるが、以前まで問題を提供できたreversingやwebに関してはまったく問題が作れなくなってしまった。自分のcryptoのレベル感で考えてしまうのだが、reversingやwebのスキルはその域に到底達していないため満足のいく問題を作れない。

また、問題のチェックも難しくなっている。ptr-yudaiの作る問題がたくさんある・良くできていてチェックするのが大変ということもあるし、Crypto以外は本当に初心者なので全然わからないということもある。流石に低難易度帯はカバーしていて大丈夫だろうということになっているが、高難易度の問題は取り組んで素人にもわかるような自明非想定解法があるわけではなく想定解法が納得感のあるものであることを確認するのがせいぜいになっているし、そもそも確認できていない問題もある。

どういう問題が初心者向けの良問かわからなくなっている

どういう問題がいい問題なのかどんどんわからなくなっていく。昨年よりもいい問題を提供したいけど、昨年よりも初心者の気持ちを忘れている。どういう問題に楽しく取り組んでいたのか忘れていくし、あのとき楽しく解いていた問題も思い返してみれば良い問題とは言い難く、比較対象がなかったからそれを面白いと感じていたんだなということがあったりする。去年よりも問題を面白いと感じるハードルは上がっているし、より難しい問題を面白く感じる傾向は必ずあって、去年なら満足していた問題に満足できず出題できなかったりする。

それでもまあ一応開催に漕ぎ着けることはできるんだけど、自分の中の達成感や満足感が足りない気がする。以前はもっとギリギリで取り組んだし終わった後燃え尽きていた気がするけど、今回はかなりふわふわとした状態で準備して開催してしまった。問題の質は上がっているはずだと思うが、難易度の推定や事前の問題のチェックはかなり甘くなっていると思う。

難易度について

Surveyやtwitterをみていると（特にtwitterで多かったが）「初心者向けと言っているのに難しすぎる」という意見が多かったので述べておくと「初心者〜のCTFプレイヤーに楽しんでもらえるCTF」を目指して開催しており、warmup問題やその他のいくつかの問題はCTF初級プレイヤーが十分解けるレベルの歯ごたえのある問題になっていたと思っているし*3、スコアボード上位のチームにとっても取り組みがいのある骨のある問題が待ち構えていたはずと思っている。

もし今回のCTFでまったく何も解けずに歯がたたなかったというなら*4、CTFの開催側が最低限想定したいCTF的なスキルが十分身についていないということなので常設CTFに取り組んだり最近充実してきたCTF関連の入門書を読んだりして勉強されると良いと思う。あるいはそれらは解けたが、その上で優しくないと言っているのであればあなたはもう十分な実力をもったCTFプレイヤーであり、これまでよりは手荒い歓迎を受けることになることを自覚したほうが良いだろうと思う。

難易度について 2

先程もすこし書いたが、難易度感の把握がバグってきている。当初はParty Ticketはwarmupの次に簡単な問題の予定だったし*5、ziperatopsがこんなに解かれないとは思っていなかった。問題の解かれる傾向というのを把握するのは本当に難しいので、せいぜいwarmupかどうかくらいしか判断ができない。その証左とも言うべく、今回lunaticの判定にしたTogether as OneはParty Ticketに比べてかなり解かれていた。こんなときDynamic Scoringは便利と思いつつ、これが積み重なってCTF全体の難易度感を見誤るかもしれないと考えると恐ろしい。人数が少ないのでなんとかギリギリでバランスが取れている。

提供した問題について

少ししか作っていませんが、作った問題のwriteup（※あれば）とコメントを少し。また問題一覧は既に公開しています。

github.com

nostrings

revのwarmupを任されたのでつくりました。ptr-yudaiがちゃんとチェックしてくれてフラグが一意に定まらない部分があることを教えてくれました。意外とangrを弾くらしくて偉い

discrete log

もっと難しい問題を作るべくこねくり回していたら簡単になりました。surveyを見たところ思いの外好評でよかったです。多分既出だと思う

hackmd.io

break a leg

yoshikingが考えてくれたwarmupがもう一捻りできそうだったので捻るかかりをやりました。

hackmd.io

telepathy

流石に既出だしSurveyでもどちらかというと評判が悪かったと思います。解法のRange Requestからオレンジレンジ→以心伝心でtelepathyになりました

matrix cipher

一番最初にリポジトリにpushされた問題ですが、没にしていたものをサルベージしました。没にした理由は問題として工夫がない・解法への道筋が明らかでないということでしたが、まあこのCTFなら出してよかろうということになりました

hackmd.io

Party Ticket

ななどなどなど、好きな漫画です。最初はgeneralized hastad's broadcast attackやるだけだからeasy、とか言っていました。流石にそんなことはなかった。アイデア自体はPlaid CTF 2017のmulticastと同じらしいです。

hackmd.io

前回のSurveyを受けて

前回のSurveyであがった要望に答えたり答えていなかったりしています

• スコアサーバーで解いた問題と解いてない問題が区別しにくい
  • 今回はかなり視認性が上がっていたと思います。色覚異常の方への配慮はできていません。ごめんなさい
• 問題が落ちているログは別のチャンネルにしてほしかった
  • そもそも問題が落ちてるかどうかを参加者にお知らせしなくなりました。インフラ後回しにしがち
• ○○に関する問題を出してほしい
  • 出しました。いかがでしたか

今回のSurveyを受けて

Surveyで頂いたコメントのうち、個人的に気になったものについてお返事を書いていきます。Surveyのコメントは原意を損なわない程度に修正しています

• スコアボードのケーキが可愛かった
  • ありがとうございます / Chigeくんありがとう
• ランキングページのグラフに（上位でなくても）自チームが出るのが良かった
  • ありがとうございます
• second, third blood用のアイコンもあると良い
  • 良い記号を思いつきませんでした
• CTFtimeに載せてもよいのでは
  • 前身となったInterKosenCTFではメインのターゲットである日本の参加者が萎縮しないように、カジュアルさを演出するためにと思いCTFtimeに登録していませんでしたが、今日ではターゲット層もCTFプレイヤーとしているし、CTFの数が増えて開催が被るようになってきたので、ロックを取る意味でもCTFTimeに登録することを検討しようと思います
  • 一方でCTFtimeに載っているようなCTFで、例えば今回のparty ticketやmatrix cipherのような手垢のついた問題を出すべきではないという思いもあります
• 配布ファイルが変わっていることに気がつくのが遅れたので @everyone でアナウンスしてほしい
  • 運営みんな欲しい情報は自分で探しに行きがちなので @everyone 嫌いなんですよね。しかしこれは重要ということもあるので今後の判断材料に加えさせていただきます
• 楽しかったです / 次回も楽しみにしています
  • ありがとうございます / 次回があるかどうか、あったとしてどのような形になるかは完全に未定ですが、楽しみにしてくださっている方がいらっしゃることは憶えておきます

*1:落ち着いて考えるとサーバを落とさずとも、スコアサーバにCTFの公開設定があるのでそちらを使えばよかった

*2:大人の資金力を舐めていた

*3:かと言ってこれらが上位プレイヤーにとってつまらなくなってしまわないよう調整したつもり

*4:特にtelepathy, break a legあたりはCTF的な知識を知らなくても解ける問題のはず

*5:あとから簡単な問題が追加されて押し上げられたり、もっと難しそうな問題は別のCTFへ回ったりした