zer0pts CTF 2022 開催記

　2022年3月19日〜20日にかけて、所属しているCTFチームzer0ptsで、zer0pts CTF 2022という大会を開催したのでその記録と反省です*1。提供した問題については別のエントリにまた書こうと思います。

諸情報

開催期間	2022-03-19 09:00:00 +09:00 〜 2022-03-20 21:00:00 +09:00 (36h)
登録チーム数	1034
1点以上獲得したチーム数	632
Welcome / Survey 以外の問題も通したチーム数	264

昨年のzer0pts CTF 2021と比べると登録チーム数や1点以上獲得したチーム数に関しては2/3程度になっていますが、Welcome/Survey 以外を通した（＝非自明な問題を解いた）チームは昨年より多くなっており、実質的な参加者は増えていそうです。登録チーム数の違いは、スコアサーバがいつから立っているか、というところで変わっていそうですね。今年は「どうせみんなギリギリまで登録しないでしょ」と言って結構ギリギリまでサーバを建てるのをサボったので、その影響かなと思っています。

個人的には去年と同等程度の盛り上がりを維持しつつ、去年と同じかそれ以上の歯ごたえのある問題を提供できたこと、さしたるインシデントもなく開催できたことに胸をなでおろしています。

インフラ

未だにかなりプリミティブなことをやっていて、ひたすらDroplet（AWSでいうEC2のDigital Ocean番）をぽこぽこたてて、それを使っています。セットアップは共通のAnsibleでやって、Dockerをインストールしたり、Special IPへのアクセスを禁じるiptablesを仕掛けたり。このiptablesは特定の参加者をbanする仕組みでもあるのですが、未だに使ったことはありません。今年はDropletを建てる部分をterraformでやることにして、ドメインとの紐付けやらなんやらをそっちで管理することにしたらちょっとだけ楽でした。

問題サーバはいくつかDropletを建てて、基本的にはその上でdocker-compose up -dをしてもらう、という運用を引き続きやっています。セットアップ用のAnsibleでファイルの配置や、tcpdumpの設定を事前に行っておき、起動だけは作問者におまかせする、という感じですね。dockerで環境を分けているので、負荷が許せばということでいくつかの問題は同じインスタンスに建てたりしています。1インスタンスに2〜3問が共存している感じ。基本的にはこれで全然問題なくて、インスタンスのスペックをフルに使えているかというとこれでもまだまだ、くらいですね。何かの拍子にどこかの問題で様子がおかしくなって、負荷が高まったりする（例えばプロセスが無限に増殖するとか）と他の問題が巻き添えになるので問題の負荷をどう読むか、共存をどの程度やるか、というのは難しいところです。このあたりもコンテナアプリケーションのホスト基盤みたいなものを用意すれば考えることが減るんですかね。いざというときに（インフラにそんなに詳しくない作問者でも）触って調査しに行けるような素朴さも維持していきたいので難しいところです。

スコアサーバも問題サーバと同様ただのDropletで動かしていて、落ちたら嫌だなと思って4vCPU 8GBメモリのそこそこリッチ（当社比）なインスタンスを建てましたが、メトリックの様子を見ているとこれの半分でもまだ余裕、1/4のサイズでピッタリくらいの負荷かな、という感じです。今回はけちってデータベースやRedisもマネージドサービスを使うのをやめて、一つのDropletの上で動かしていてましたが、登録チーム数が1000チーム数くらいのCTFならこれで十分ということがわかって良かったです*2。

kosenctfx

kosenctfxというのはここ1年半〜2年くらい、我々の開催するCTFで利用しているスコアサーバのことで、毎回フロントは書き変えたり書き直したり、バックエンドにも機能を追加したりしています*3。今年注力していたのは、スコアボードのstatic化の部分です。

CTFのスコアサーバはCTFの開催期間中はどんどんデータが更新されてfetchもmutateもたくさんする、バリバリのWebアプリケーションといった感じなのですが、一度CTFが終わった後は更新されるデータはなくすべてのデータがstaticになる、という性質を持っています。CTFの終了後もスコアサーバは公開し続けたいが、わざわざWebアプリケーションとしてホスティングすることはない、ということで毎年CTFの終了後にスコアサーバを書き換えてstatic化していたのですが*4、今年やっとNext.jsを使っている恩恵に預かって書き換えを最小化してstaticなスコアボードを生成できるようになりました。今ではグローバルに存在するisStaticModeという変数をtrueにしてからyarn build && yarn export をするだけでstaticなスコアサーバが生成できて非常に便利です*5。

TSG CTF 開催記 - 博多電光 をみるとTSGでは2019年時点でできていたということなのでかなり遅れをとっていますが、こんなに楽になるなら早くやっておけばよかったです。

追記

その後もう一つ修正が必要な点を見つけました。GitLab Pagesでホスティングしてみたところ https://2022.ctf.zer0pts.com/tasks のようなページに直接アクセスすると、 tasks/ ディレクトリが優先されて tasks.html は読んでくれないので 404 になってしまうんですね。これは next.config.js: exportPathMap | Next.js に従ってオプションを追加したあとでyarn exportをし直して解決しました

準備/作問

CTFの準備とは9割作問ですと毎日言ってますが、つまり作問の話です。今回のzer0pts CTFはかなり前、BSides Ahamedabad CTFの運営が終わってすぐですから昨年の11月にはやるぞという話が上がって準備を始めていましたが、結局過去一番の焦燥感でした。ptr-yudai, keymoonが精力的に活動していたpwnは十分な質と量が揃っていたのですが、他のカテゴリはcryptoが数問あるだけで、あとは焼け野原といった様相でした。

結局ptr-yudaiやkeymoonがwebやらmiscやらrevやらcryptoやらを作ってくれてギリギリ（本当にギリギリ）なんとかなったわけですが、今回はたまたまなんとかなったという感が否めません*6。zer0ptsはチームとしてはそこそこの人数を抱えていて、各分野に優秀な人材が揃っているはずなのですが、負荷がうまく分散されて十分早く問題が揃わないのは課題です。

しかしCTFの問題を作るのは非常に難しく一筋縄ではいかないものでコントロールはほとんど不可能という認識もあるし、CTFを開催するためにだれかがマネジメント業をするはめになるのも（それはきっと楽しくないので）避けたいとも思っています。難しいですね。結局解決策は自分がめっちゃ頑張ってcryptoを完璧に作って他のジャンルにも手を出すとかになってしまいそう。到底実現不可能なわけですが……

作問チェック不足

上記のような作問の遅れが何をもたらすかといえば、作問チェックの不足です。ギリギリにできた問題がチェックされないのもそうですが、十分余裕をもって作られたはずの問題も、チェックに回れる余裕のある人材の不足から、確認を経ず世にでてしまうということになってしまいました。なんとかならないか……

運営の様子

私、ptr-yudai、keymoonの3名がボイスチャットをつないで対応していたほか、作問者は質問の対応ができるように待機してくれていたようです。運営の様子と行っても問題が壊れていないか非想定解法で解かれていないかということを確認したり、まだ完成していない問題を急いで作ったり（！）、非想定解法で解かれてしまったのでリベンジ問題を準備したりといった様子でした。

開始から6時間と少しがたったあたりでやっと落ち着いて、boardgame arenaをしたり、discordに新しく追加されたsketch headsをやったりできるようになりました。しかし問題があって、3人だとイマイチ盛り上がりが足りないんですよね。その点、運営二日目にyoshikingが参加したときはもりあがりました。やっぱりhaxballやな……！

それにしてもCTF運営中に運営がボードゲームをしてるってあんまり想像できないですよね。しかしこれが楽しい。ちゃんとボードゲームを楽しめるように完璧に準備できるようになりたい。

まとめ

• 平穏無事にzer0pts CTF 2022を開催できてよかった
• 今年は問題の準備が特に遅れたのが課題です

参加してくださった皆様ありがとうございました。あとは皆様のwriteupとsurveyを見るのが楽しみです。よろしくおねがいします。

それでは次はCake CTF 2022（あれば）でお会いしましょう。zer0pts CTF 2023は、どうでしょうね。あると良いなと思っています

*1:余談だけど、CTFを開催した時のエントリのタイトルどうしてたっけなと思って自分のブログを遡ったら、「振り返り」と「開催記」が半々くらいでした

*2:このあたりは前回のBSides Ahmedabad CTFのときにコストかかるけどケチってもいいかな、ということを書いたらatpons先生に大丈夫でしょ、というお言葉を頂いて踏み切ることができました。ありがとう！

*3:例えば前回のCTFあたりからスコアの遷移のグラフがめっちゃ細かくなったりしてる

*4:https://2021.ctf.zer0pts.com や https://2021.cakectf.com のような感じ

*5:実際にはgetStaticPathsのfallbackがfalseじゃないとだめ、みたいなエラーを受けてそこは書き換えたりしました。SSR/SSGのこと何もわからず勘でやっている……

*6:ptr-yudaiがいるなら大丈夫という話もあります

BNFから文法に沿ったランダムな文字列を生成する試み

randexp.jsというライブラリがあって、これは与えられた正規表現に対して、その正規表現にマッチするような文字列を生成する。へーと思って実装を見てみたら素朴に作られていた。

あとで思い出して、じゃあBNFでやったらどうなのかというのを作ってみた。BNFというのは文法を定める言語のようなもので、Wikipedia曰く"文脈自由文法を定義するのに用いられるメタ言語" ということだった。文脈自由文法がどういう意味だったか全然憶えていないけど、この形式で言語の構文を書いておけば、lex/yaccみたいなのに簡単に落とし込めたり、愚直に再帰下降構文解析を書けば、文法に沿った言語をパースできるようになる。正規表現とは似て非なるもので、今回の目的だと正規表現が括弧のネストみたいなのをうまく表現できないのに比べて、BNFならわりと簡単に書ける、というような違いがある。

いまならPEGというもうちょっとBNFを便利に書いてもパーサは作れるよね、という感じの記法もあるけど、色々できるということは色々実装しないといけなくてややこしいということでもあるので、今回は素直にBNFを対象にした。

できたものがこちら

github.com

やることは簡単で、まずBNFをパースできるようにする。BNFは当然BNFを記述できるし、Wikipediaにそういう例があるから、それを見ながら再帰下降構文解析を書いて抽象構文木を作る。それができたら作った構文木を上から順に読み下しつつ、ルールに応じてランダムな文字を生成すればいい。ルールといっても、連接と選択と他のルールの参照くらいしかないから愚直にやっていい。

ここまで書いて、じゃあ適当な言語のBNFを拝借してなんか生成してみるか、と思ったけど愚直なBNFで定義された文法なんて都合よく転がっていなかった。EBNFならどうかとおもって反復とかもパースできるようにしたけど、結局共通のBNFで文法が定義なんてされていなくて丁寧な前処理が必要そうになって面倒になった。結局BNFで書かれたBNFの文法と、EBNFで書かれたEBNFの文法くらいしかサンプルがなくて悲しい感じになった。かろうじてbcは素直なBNFが提供されていて、かつトークンもそんなに複雑な感じではなかったので遊べる感じになっているが、トークンと構文は区別されているので、構文の間には適当に空白を入れないといけないが、トークンの間には入れることができず、それをBNF側でひとまとめに扱うのは無理なので結局 definex みたいなのが生成されてparsableではなくなってしまったりした。

それではランダムに生成したbcのプログラムでお別れです。これをJSとかTSで書くとか、wasm-friendlyな言語でwasmにコンパイルする前提で書くとかしていれば皆様にもお試しいただけたけど、今回はD言語で、しかも std をバリバリつかって書いてしまったのでブラウザに載せることはできませんでした。

while(h()!=sqrt(s(a(y)^-length(length(9.))))*--a[length((-B.D))])if(obase--g(B3B.D)-(sqrt(obase)^j--)>length(scale(w[ibase+=sqrt(scale--)]--)+sqrt(E1D.C)))for(-++i[7*sqrt(++d[--ibase+length(q())])]-k[length(++scale)]++;(--j[(ibase%=.5)]);sqrt(obase/=l()))break

;""
define w(f,a){
auto q[];
;

;;for(ibase++;c()-.0180>86F58B;-(-length(sqrt(0.3D2C31F+.4^-ibase/=B./A.01)))*B5.C6+sqrt(scale)%(v()-ibase))5.^--scale*h()}

今は再帰が深くなりすぎるとsegmentation faultする問題が知られていて、気が向いたらループに書き換えます

2021年印象に残ったCTFと暗号問題

はじめに

この記事は 2021年の CTF Crypto 問を振り返る | y011d4.log のリスペクト記事です。こちらの記事に挙げられている問題のどれも確かにと思わせられる、記憶に残る問題ではあったのですが、私が0から選んでみると少し違ったものが挙げられるかな、ということで書いてみようと思います。

おことわりとして、私はzer0ptsというチームでできるだけ開催されるCTFには参加していたつもりでしたが、見返してみるとさまざまな要因から参加できていないCTFも多くありました。全ての問題を精査したものではないということはご承知おきください*1。

DiceCTF 2021

個人的には今年No. 1くらいのCTFです。あのDiceGang*2が開催するCTFで、本当に多くのことを学べる暗号問題が出題されました。このCTFが年初にあったことで2021年のCrypto業界は大きく様変わりしたのではないかと思います。

benaloh

問題ソースコード

from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime, GCD

r = 17

def keygen():
    while True:
        p = getPrime(1024)
        a, b = divmod(p-1, r)
        if b == 0 and GCD(r, a) == 1:
            break
    while True:
        q = getPrime(1024)
        if GCD(r, q-1) == 1:
            break
    n = p*q
    phi = (p-1)*(q-1)//r
    y = 1
    while True:
        y = randrange(n)
        x = pow(y, phi, n)
        if x != 1:
            break
    log = {pow(x, i, n): i for i in range(r)}
    return (n, y), (n, phi, log)

def encrypt(data, pk):
    n, y = pk
    u = randrange(n)
    a = randrange(n)
    c = randrange(n)
    for m in data.hex():
        yield pow(y, int(m, 16), n) * pow(u, r, n) % n
        u = (a*u + c) % n

def decrypt(data, sk):
    n, phi, log = sk
    return bytes.fromhex(''.join(f'{log[pow(z, phi, n)]:x}' for z in data))

if __name__ == '__main__':
    from local import flag
    pk, sk = keygen()
    print(pk)
    for z in encrypt(flag, pk):
        print(z)

この問題について詳細な解説をすることは難しいのですが簡単に言うとbenaloh cryptosystemに手を加えた問題で、 という形式で暗号化されており、各と計算されています。今見れば「グレブナー基底とかで計算すれば一発では」と思うところではありますが、個人的には暗号問題におけるグレブナー基底の有用性を幅広く知らしめたのがこの問題という認識でいて、それゆえ非常に強く印象に残っています。

グレブナー基底はこれまでも一部のCryptoプレイヤーの間では常識のように用いられていたようですが、連立した多項式の解を求める操作は多くの場合グレブナー基底を使わずとも手で十分ということが多くあり必須ではなかったため、大衆に浸透するには至らないという状態であったのではないかと推測しています。一方この問題では線形合同法をベースとしてある程度複雑な式がネストしており、手で解くのはまず不可能ということでグレブナー基底が登場し、writeupなどからこのテクニックの存在が多くのプレイヤーに知れ渡りました。私もこの問題でグレブナー基底の有用性を認識し、BSides Ahmedabad CTF 2021のSSSS.RNGなどでグレブナー基底を用いる問題を出題しています。

plagiarism

問題ソースコード

Two agents, Blex and Kane, have simultaneously known very secret message and transmitted it to Center. You know following:
1) They used RSA with this public key
2) They sent exactly the same messages except the signatures (name appended, eg. "[message]Blex")
3) They did encryption this way:

m = int(message.encode("hex"), 16)
c = pow(m, e, N)

4) And here are cryptograms you have intercepted:

N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529

e = 1048577

ciphertext_Blex = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178

ciphertext_Kane = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472



Now tell me that secret message! (The answer for this task starts from 'dice{') 

DiceCTFは「存在するが広く知られていない知識」をうまく問題に落とし込むのが本当にうまく、このplagiarismもbenalohに引き続いてHalf-GCDというテクニックをCrypto界に浸透させた立役者的な問題であろうと思います。

この問題はどう見てもFranklin-Reiter's Related Message Attackではあるのですがe = 1048577と大きいことが特徴で、多項式のGCDをユークリッドの互助法的に愚直に求めようとしても計算が間に合いません。そこで登場するのがHalf-GCDです。詳細は各自でお調べいただきたいところですが、Half-GCDではGCDより計算量が多少改善され、eが大きい場合にも現実的な時間で解けるようになります。

もっとも、愚直なGCDに比べて計算量的な改善は多少の範疇にとどまりますので、計算資源を費やせばHalf-GCDを用いずともこの問題を解くことはできます。そういった力任せの解法が現実的に多く用いられた問題の例としてもこの問題は印象に残っています。

この問題でHalf-GCDの存在が広まって以降、多少の計算を要する多項式の問題が出題されるようになりました。具体的にはBSides Ahmedabad CTF 2021のECC-RSA 2などですね。

Union CTF

Union CTFはCr0wnというチームが主催するCTFだったと思います。この時期は justCTF 2020→Dice CTF→Union CTFと強いチームの開催する（初？）CTFが連続していて怒涛でしたね。Union CTFでは2問ほど印象深い問題がありますが、1問はこの後の番外編で紹介して、こちらでは普通に面白かった1問をご紹介します

neo-classical key exchange

問題ソースコード

import os
from hashlib import sha1
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

FLAG = b"union{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

def list_valid(l):
    x = l // 2
    checked = set([x])
    while x * x != l:
        x = (x + (l // x)) // 2
        if x in checked: return False
        checked.add(x)
    return True

def list_iter(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def list_mul(l1,l2,p):
    X, Y = len(l1), len(l2)
    Z = list_iter(X)
    assert X == Y
    assert list_valid(X)
    l3 = []
    for i in range(Z):
        for j in range(Z):
            prod_list = [x*y for x,y in zip(l1[Z*i:Z*(i+1)], l2[j::Z])]
            sum_list = sum(prod_list) % p
            l3.append(sum_list)
    return l3

def list_exp(l0, e, p):
    exp = bin(e)[3::]
    l = l0
    for i in exp:
        l = list_mul(l,l,p)
        if i == '1':
            l = list_mul(l,l0,p)
    return l

def gen_public_key(G,p):
    k = randint(2,p-1)
    B = list_exp(G,k,p)
    return B,k

def gen_shared_secret(M,k,p):
    S = list_exp(M,k,p)
    return S[0]

def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data

p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
G = [37474442957545178764106324981526765864975539603703225974060597893616967420393,59548952493843765553320545295586414418025029050337357927081996502641013504519, 31100206652551216470993800087401304955064478829626836705672452903908942403749, 13860314824542875724070123811379531915581644656235299920466618156218632047734, 20708638990322428536520731257757756431087939910637434308755686013682215836263, 24952549146521449536973107355293130621158296115716203042289903292398131137622, 10218366819256412940642638446599581386178890340698004603581416301746386415327, 2703573504536926632262901165642757957865606616503182053867895322013282739647, 15879294441389987904495146729489455626323759671332021432053969162532650514737, 30587605323370564700860148975988622662724284710157566957213620913591119857266, 36611042243620159284891739300872570923754844379301712429812256285632664939438, 58718914241625123259194313738101735115927103160409788235233580788592491022607, 18794394402264910240234942692440221176187631522440611503354694959423849000390, 37895552711677819212080891019935360298287165077162751096430149138287175198792, 42606523043195439411148917099933299291240308126833074779715029926129592539269, 58823705349101783144068766123926443603026261539055007453105405205925131925190, 5161282521824450434107880210047438744043346780853067016037814677431009278694, 3196376473514329905892186470188661558538142801087733055324234265182313048345, 37727162280974181457962922331112777744780166735208107725039910555667476286294, 43375207256050745127045919163601367018956550763591458462169205918826786898398, 21316240287865348172884609677159994196623096993962103476517743037154705924312, 7032356850437797415676110660436413346535063433156355547532408592015995190002, 3916163687745653495848908537554668396996224820204992858702838114767399600995, 13665661150287720594400034444826365313288645670526357669076978338398633256587,23887025917289715287437926862183042001010845671403682948840305587666551788353]
A,a = gen_public_key(G,p)
B,b = gen_public_key(G,p)
assert gen_shared_secret(A,b,p) == gen_shared_secret(B,a,p)

shared_secret = gen_shared_secret(B,a,p)
encrypted_flag = encrypt_flag(shared_secret)

print(f"Alice's public key: {A}") 
print(f"Bob's public key: {B}")
print(f"Encrypted flag: {encrypted_flag}")

ソースコードが多少複雑ですが*3、これは一般線形群上の離散対数問題が解けますか、という問題です。当然通常は解くことができないんですが、この問題で用いられている行列は対角化できないもので、このとき離散対数問題が解けてしまいます*4。世の中にはいろんな群があるけど、いろんな問題をその群で実現したときに特定のケースで脆弱になるね、というのは面白かったので印象に残っているし、ptr-yudaiが鮮やかな式変形で解法を導いていてすげーとなったのも憶えています。

m0leCon 2021

m0lecon、去年からいい問題が出ると思って注目しているんですが*5、あんまり世間で楽しみにされている様子は見ませんね……。

Giant log

問題ソースコード

import random
from secret import flag, fast_exp
import signal

p = 0x83f39daf527c6cf6360999dc47c4f0944ca1a67858a11bd915ee337f8897f36eff98355d7c35c2accdf4555b03a9552b4bf400915320ccd0ba60b0cb7fcad723
g = 0x15a5f7dec38869e064dd933e23c64f785492854fbe8a6e919d991472ec68edf035eef8c15660d1f059ca1600ee99c7f91a760817d7a3619a3e93dd0162f7474bbf


def test():
    for _ in range(10):
        x = random.randint(1, p)
        n = random.randint(1, 20)
        m = p**n
        assert pow(g, x, m) == fast_exp(x, n)

def chall():
    n = 1000
    x = random.randint(1, p**(n-1))
    y = fast_exp(x, n)
    return x, y


def stop(signum, stack):
    print("Too slow")
    exit(1)


def main():
    x, y = chall()
    timeout = 60
    print(hex(y))
    print("Now gimme x")
    signal.alarm(timeout)
    x_inp = int(input(), 16)
    if x == x_inp:
        print("Wow, impressive!")
        print(flag)
    else:
        print("Nope, sorry")


if __name__ == "__main__":
    signal.signal(signal.SIGALRM, stop)
    #test()
    main()

この問題は全然解けなかったんですが、要するにという離散対数問題で、これ解けるんですかすげーということで印象に残っています。また、この問題はこの後紹介するOMH 2021 CTFのTower of Powerという問題と同時期に出題されたのですが、こちらは似て非なる問題で同じようなタイミングで、これらの難題が別々に出題されたことの偶然もよく憶えています。ところでこれはなんで解けてるんですか？

OMH 2021 CTF

CONFidence CTFが名前を変えたんですかね、なんで名前変えたんだろう

Tower of Power

問題ソースコード

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
load('secret.sage')
M = x^127 + x^126 + x^125 + x^124 + x^122 + x^120 + x^118 + x^117 + x^115 + x^108 + x^107 + x^104 + x^103 + x^100 + x^99 + x^98 + x^96 + x^95 + x^94 + x^91 + x^88 + x^85 + x^83 + x^82 + x^81 + x^77 + x^74 + x^72 + x^70 + x^66 + x^65 + x^64 + x^57 + x^56 + x^55 + x^54 + x^50 + x^49 + x^48 + x^46 + x^44 + x^43 + x^37 + x^36 + x^34 + x^33 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^11 + x^10 + x^8 + x^7 + x^4 + x^2 + 1

K.<x> = GF(2^127, 'x', M)
z = x + 1

# for _ in range(n):
#     z = z**69
z = z**ZZ(pow(69, n, z.multiplicative_order()))

print(z)

aes = AES.new(long_to_bytes(n), AES.MODE_ECB)
print(aes.encrypt(flag.encode()).hex())

こちらもわけわかんない群の上でのちょっと大きい離散対数問題ということで、giant logと一緒に記憶に残っています。writeupはあるんですが、「magma使ったら解けたわ」ということで全然意味わからないです。何が起こっているのかわかった方はこっそり教えてください

Google Capture The Flag 2021

Google CTF、評判よかったり良くなかったりするんですよね。あとソースコードにライセンス埋めこんでるのはさすがというからしいですね

tiramisu

問題ソースコード（一部）

// Copyright 2021 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package server

import (
    "crypto-tiramisu/pb"
    "crypto/ecdsa"
    "fmt"
    "math/big"
)

const serverCurveId = pb.EcdhKey_SECP224R1

var flagCipherKdfInfo = []byte("Flag Cipher v1.0")
var flagMacKdfInfo = []byte("Flag MAC v1.0")
var flagFixedIV = []byte{0x73, 0x40, 0x76, 0xd5, 0x67, 0xe0, 0x9, 0x2a, 0xbc, 0xe1, 0x9, 0x15, 0x82, 0x55, 0x43, 0x7d}

var channelCipherKdfInfo = []byte("Channel Cipher v1.0")
var channelMacKdfInfo = []byte("Channel MAC v1.0")

type Server struct {
    flag          string
    encryptedFlag *pb.Ciphertext
    key           *ecdsa.PrivateKey
    channel       *AuthCipher
}

func buildFlagCipher(priv *ecdsa.PrivateKey) (*AuthCipher, error) {
    secret := make([]byte, priv.Params().BitSize/8)
    priv.D.FillBytes(secret)

    return newAuthCipher(secret, flagCipherKdfInfo, flagMacKdfInfo)
}

func NewServer(flag string, priv *pb.EcdhPrivateKey) (*Server, error) {
    // Load private key.
    if priv.Key.Curve != serverCurveId {
        return nil, fmt.Errorf("priv.Key.Curve != serverCurveId, want %d, got %d", serverCurveId, priv.Key.Curve)
    }
    key, err := proto2ecdsaPrivateKey(priv)
    if err != nil {
        return nil, fmt.Errorf("proto2ecdsaPrivateKey() = %v, want nil error", err)
    }

    // Private key sanity checks.
    x, y := key.ScalarBaseMult(key.D.Bytes())
    if x.Cmp(key.X) != 0 || y.Cmp(key.Y) != 0 {
        return nil, fmt.Errorf("input private key does not match public")
    }
    if !key.Curve.IsOnCurve(key.X, key.Y) {
        return nil, fmt.Errorf("input key not on curve X=%X, Y=%X", key.X, key.Y)
    }

    // Encrypt flag.
    flagCipher, err := buildFlagCipher(key)
    if err != nil {
        return nil, fmt.Errorf("deriveFlagKey()=%v, want nil error", err)
    }
    encryptedFlag, err := flagCipher.Encrypt(flagFixedIV, []byte(flag))
    if err != nil {
        return nil, fmt.Errorf("encryptFlag()=%v, want nil error", err)
    }

    return &Server{
        flag:          flag,
        encryptedFlag: encryptedFlag,
        key:           key,
    }, nil
}

func (server *Server) ServerHello() *pb.ServerHello {
    return &pb.ServerHello{
        Key: &pb.EcdhKey{
            Curve: serverCurveId,
            Public: &pb.Point{
                X: server.key.X.Bytes(),
                Y: server.key.Y.Bytes(),
            },
        },
        EncryptedFlag: server.encryptedFlag,
    }
}

func (server *Server) EstablishChannel(clientHello *pb.ClientHello) error {
    // Load peer key.ecnrypted
    peer, err := proto2ecdsaKey(clientHello.Key)
    if err != nil {
        return err
    }

    // Key sanity checks.
    if !peer.Curve.IsOnCurve(peer.X, peer.Y) {
        return fmt.Errorf("point (%X, %X) not on curve", peer.X, peer.Y)
    }

    // Compute shared secret.
    P := server.key.Params().P
    D := server.key.D.Bytes()
    sharedX, _ := server.key.ScalarMult(new(big.Int).Mod(peer.X, P), new(big.Int).Mod(peer.Y, P), D)

    masterSecret := make([]byte, server.key.Params().BitSize/8)
    sharedX.FillBytes(masterSecret)

    // Derive AES+MAC session keys.
    server.channel, err = newAuthCipher(masterSecret, channelCipherKdfInfo, channelMacKdfInfo)
    if err != nil {
        return fmt.Errorf("newAuthCipher()=%v, want nil error", err)
    }
    return nil
}

// Read and re-encrypt client's message.
func (server *Server) EchoSessionMessage(clientMsg *pb.SessionMessage) *pb.SessionMessage {
  data, err := server.channel.Decrypt(clientMsg.EncryptedData)
  if err != nil {
      return &pb.SessionMessage{}
  }

  iv := make([]byte, len(clientMsg.EncryptedData.Iv))
  copy(iv, clientMsg.EncryptedData.Iv)
  iv[0] ^= 1

  encryptedData, err := server.channel.Encrypt(iv, data)
  if err != nil {
      return &pb.SessionMessage{}
  }
  return &pb.SessionMessage{
      EncryptedData: encryptedData,
  }
}

これはCRTでsecp224r1ではInvalidCurveAttackになるようなsecp256r1上の点を生成してbruteforceでECDLPをとき、CRTでd復元する問題です。これをtiramisuするといいます。きれいな問題だなと思ったのでよく憶えています。あとprotobufが鬱陶しかったので憶えています……

DownUnderCTF 2021

josephがめちゃくちゃ頑張っていたCTFことDownUnderCTFです。joseph作のcryptoがひたすらよくできていました。

yadlp

問題ソースコード

def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)

def G_mul(A, k):
    out = (1, 0)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out

def rand_element():
    while True:
        x = randint(1, p-1)
        d = x^2 * (D + 1) - D
        if (x & 1 == d & 1) and kronecker(d, p) == 1:
            y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
            return (x, y)

D = 13337
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime

FLAG = open('flag.txt', 'rb').read().strip()
assert len(FLAG) % 8 == 0
M = [int.from_bytes(FLAG[i:i+8], 'big') for i in range(0, len(FLAG), 8)]

G = [rand_element() for _ in M]
c = (1, 0)
for m, gi in zip(M, G):
    c = G_add(c, G_mul(gi, m))

print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')

同じようなアイデアの問題を温めていたのでよく憶えています……

TSG CTF 2021

World No.1 CTFとの呼び声も高いTSG CTFです。keymoonさんが強かったのも憶えています。

This is DSA

問題ソースコード

# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os

alarm(15)

q = getPrime(256)
print(f'q = {q}')

p = int(input('p? '))
h = int(input('h? '))

g = pow(h, (p - 1) // q, p)
x = randrange(q)
y = pow(g, x, p)

print(f'g = {g}')
print(f'y = {y}')

dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')

print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))

dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")

https://github.com/tsg-ut/pycryptodome/tree/22388c5fec4607e8e255926c3e95724a2f070e76

感動しました！！！　最高の作問だと思います。Best Crypto Challenge 2021どころかBest Crypto Challenge Everかも

番外編

手前味噌なので番外編です。何がNOTなのかは知りません

Mordell Primes - Union CTF / NOT Mordell Primes - zer0pts CTF 2021

問題ソースコード - Mordell 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}')

問題ソースコード - NOT Mordell Primes

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


p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177

E = EllipticCurve(GF(p),[a,b])

P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
Q = k*P
R = (k+1)*P

p = int(Q[0])
q = int(R[0])

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}')

Union CTF 2021で出題されたMordell Primesは単調性を使って探索するだけの問題だったのですが割と苦戦した結果、DiceCTFで憶えたばかりのグレブナー基底などを試していたところ、別の問題が作れそう！　となってできたのがNOT Mordell Primesです。

これはなかなかいい問題ができたぞと思いながら、Union CTF 2021のDiscordを見に行くとhellmanがこんな投稿をしておりました😰

やべーーーと思いつつ、そのまま出したらhellmanが思いもよらない解き方をしていたので面白かったです

https://affine.group/writeup/2021-01-Zer0pts#not-mordell-primes

感想

ここで紹介できてない面白くて難しい問題も無限個あるんですよね。来年は一体どうなってしまうんだ

*1:参加しなかったCTFで後から見返して面白いと感じた問題もあったけど、こちらもリアルタイムな印象ではないので今回はパスとしてます

*2:defundしか認識していなかったけど、ちらっとみたらwillwamとかTuxとかも所属しているんですか？　デカすぎる

*3:よくないと思う……。問題のコンセプトがシンプルなのにソースコードが複雑になってしまうのは何故なんですかね

*4:ジョルダン標準形を考えるとλ^aとaλ^a-1が登場するので解けます

*5:後スコアボードで使われているCTFdのテーマが良い