ふるつき

v(*'='*)v かに

CakeCTF 2022 開催記

年に2度ある人生最大の娯楽ことCTF開催のうちの一回、CakeCTFの運営を今年もやりました。開催記を書こうとしていたのですが、どうにもまとまりがなくしっくり来なかったので、時系列に出来事や感情をまとめていきます。

ちなみにCakeCTFというのは去年から開催しているインディーズのCTFで、前身としてInterKosenCTFというのがあったんですが、運営が高専とはなんら関係なくなったのと名前がダサかったのとでリニューアルしてこういう名前になっています。InterKosenCTFから数えると4年目、5回目の開催ということになるようでした。最近は私と、ptr-yudai、yoshikingの3人で運営しています。

巷で開催されるガチCTFというよりは、カジュアルに問題を解く楽しさを味わってもらうワイワイCTFを標榜しています。

スコアサーバはこちら https://2022.cakectf.com

出題した問題はすでにGitHubに上がっています

github.com

時系列

2022/3/23

Discordのログによるとこの日にとりあえずやるかという話になったようでした。以前から当然のようにやるものという認識は共通してあったと思いますが、CakeCTFとは別で主催しているCTFであるzer0pts CTFの運営が一段落したことで、次なるCTFの運営に視線を定めたというところでしょうか

2022/5/20 - Cryptoの問題が出揃う

まじかっていう感じですが、4月中旬くらいからptr-yudaiがどんどん問題を作りはじめて、それに引きずられるようにしてcryptoの問題も作り始めていて、5月20日には今回のCakeCTF 2022で出題した暗号問題4問がすべて作られていたようでした。その間にptr-yudaiはもっとめちゃめちゃ問題を作っていた気がする…

2022/6/1 - ctftime.org に登録する

CTFTime というサイトがあって、世界で開催されるCTFの情報が集約されたりCTFでの成果に応じてチームにレーティングがついて順位付けされたりします*1。ほとんどのプレイヤーはCTFの開催情報を知るのにこのサイトを利用しています。これまでのCakeCTF（やInterKosenCTF）では、ある程度ローカル指向なCTFであることやCTFTimeのレーティングを気にせず問題を解く純粋な楽しみを追求してほしいことからCTFTimeへの情報の登録を行っていませんでした。

しかし去年のCTFTimeのアップデートで、CTFのレーティングウェイトを0にしてCasual CTFとして登録できる機能が実装されたため、今年はカジュアルCTFとして登録してみました*2。

そのための申請をこのあたりでやったようですね。昨今は様々なCTFが開催されていて、土日の予定埋まりがちなので、先手先手をうってCTFtimeに登録しておかないとブッキングなどの危険性があると思っていた気がします。結局BalsnCTFとかぶったわけですが……。ちなみに今回はCTFtime上は初のCakeCTFだったので、CakeCTFというCTFを作る作業とCakeCTF 2022というイベントを作る作業の2段階があり、どちらもCTFtimeの管理者のapproveが必要なのですが、イベントの申請が受け付けられるのに時間がかかって、結局eventが作られたのは2022/6/15だったようです

ctftime.orgのイベント作成ページにcasual eventの選択肢がある様子

ちなみに、暗号の問題はこの時点でptr-yudaiが一通りチェックしてくれてます

2022/7/1

この頃は暗号以外の問題を作ろうとしているものの、勘が失われていてどういう問題が面白いのかわからずめちゃめちゃ困っていました。

2022/7/11

毎回CTFがあるごとに自作のCTFのスコアサーバのkosenctfxというやつを便利にする作業をやっているのですが、今年はタスクのインスタンスを立ち上げる機能をつくっていました。結局作りきれてないんですけど。素朴に競技者がリクエストしたらDockerをランダムなポートで立ち上げてそのインスタンスのIPとポートがスコアサーバに通知される、という仕組みを作っていたのですが、環境を分けたくて作っているのに、nmapとかで発見されてしまうような仕組みでは意味がないということが明らかになって没にしてます。いわゆるバーチャルホストとかで内部的にリダイレクトする仕組みとかにすると良いんですかね……

その他にもちょこちょこkosenctfxにてをいれていまいした。今年は元気がなかったので上記以外はあんまり大きい変更はしようとしてないですが、zer0pts CTFとCakeCTFで毎回少しずつサーバの様子に合わせてフロントエンドを書き直していたのが大変だったので、フロントエンドのロジック部分を切り出して、zer0pts CTFのテーマとCakeCTFのテーマを切り替えやすくしたりしていました。なんかあとから考えるとこういうのContext Providerでやれば良い気がするけど、思いついたのがimport先のパスをtsconfig.jsonで切り替える方法だったのでそういう感じになってます。

2022/7/30

あまりに私とyoshikingが作問チェックをやらないので、土曜日に作問チェックの会をやりました。yoshikingはなぜか来なかったので結局ひとりでptr-yudaiの作った問題を解いていましたが、全部で3問かそこらくらいまで解いて力尽きていました。それを考えるとCakeCTF 2022の問題セットで10問とか解いてる人はすごいですね……

2022/8/3 - Google CTF Sponsorship

なんか去年はフォームが閉じていたような気がするのですが、申請するとCTF Eventように$500のGCPのクーポンを発行してくれるGoogle CTF Sponsorshipという制度があったので応募してみました。なんか公式に紹介されているページとかを見たことがなくて、口伝みたいな感じになっていますが、応募は https://goo.gle/ctfsponsorship からできます。

応募フォームをみると、どのくらいCTFに参加していますか、とか去年の問題を公開していますか？　という設問があり、CTFコミュニティに貢献するようなCTFかどうかが問われているような感じがして非常に好感の持てるフォームでした。

我々はそういった活動の推進に一役買っているくらいの自負があったので心配していなかったのですが後日無事審査に通ったという連絡があり、GCPのクーポンコードとCTFのインフラを構築するときの心得や、「なんか大量のアクセスが想定されてもっとクーポンいるようなら言ってください」とか「サポートに連絡するときは〜ということを伝えるとこちらにエスカレーションされます」といったTipsがとても丁寧に書かれていて好感度MAXでした。ありがとう

Google CTF Sponsorshipに通ったからにはGCPを使ってインフラを構築していたのですが、なれないプラットフォームだからかめちゃめちゃ苦戦しました……。理想を言えばスコアサーバはCloud Runに置いて前段にロードバランサを置く……とかだと思うんですが、証明書の発行がよくわからなくて諦めました。

あと配布ファイルとかを置くためにCloud Storageを使おうとしたけどスコアサーバにはS3用の実装しかなくて、互換性あるだろうからいけるやろと思って突貫したら、なんかPresigned URLの扱いがうまくイカなかったのでここだけ諦めてDigitalOcean Spaceを使ったりしました。なんなのか……

ということで基本的に全部Compute Engineの上に置いてdocker-composeで起動する素朴な感じになりました。無念……

2022/8/27

このあたりではptr-yudaiがすでにWeb問題を4つ揃えていて、その作問チェックをしていたようですが、Image Surfingに挑んで撃沈していました。

2022/8/28

焼肉に行った。帰ったあと、スコアサーバをpublishしました

スコアサーバのpublish後の面白い、というかどうすべきか困る話がひとつあったので書いておくと、「ウチが普段使っているチーム名がすでにとられていて困っているので、そのチームを削除してくれないか」という依頼が来ました。基本的にCTFのチーム名というのは登録の早いものがちなので、殆どないとはいえ自分の使いたかったチーム名がすでに使われている、ということはありえることです。今回のケースはすでに取られていると思ったものの、それはそのチームの別の人が先んじて登録していただけだったので特に問題にはなりませんでしたが、本当に全く関係ない人が偶然に、あるいは故意に既存の（ある程度の活動実績のある）チーム名でチームを作っていた場合はどうするのが良いのでしょうか*3。

2022/9/1

問題をホストするためのサーバを立てたりしていました

2022/9/3 - CTF開始

朝はデータベースを1分ごとにダンプするcronとかをかいてました。実験で1分にしていて、あとで5分とかにしようとしていたのをわすれていた。でも大したサイズのないDBなので毎分ダンプしても全然ディスク的には余裕です。

そして14時になってCTFが始まりました。なんかfrozen cakeという問題のフラグを提出しようとすると502応答が返される、という不具合報告が複数来てこまりました。実際には特定の問題のフラグを提出しようとしたときではなくて、間違ったフラグを提出しようとしたときのエラー処理をミスって起こる502で、偶然frozen cakeの答えの設定が間違っていて最序盤にはそういうふうに見えたということのようでした。リファクタリングのときにミスっていたことがわかったのでhotfixしました。

その後は落ち着いてきたのでptr-yudaiと将棋をやったりしました。ぼこぼこにされた。 ずっと座っていると疲れたので横になると、ptr-yudaiが気を利かせてくれてそこで通話を終了して私は一旦昼寝しました。 その後10時くらいに復帰してあとは夜通し起きていた。

2022/9/4 - CTF終了

9時位に寝て12時位に起きました。そのまま14時になり、夜ふかしで口内炎ができた以外は特に何もなくCTFが終了しました。良かったです。

終わったあとはCTFtimeにスコアボードを提出して、人々のwriteupを眺めたり、kurenaif先生のwriteup streamを見たりしていたら時間が急速に過ぎていって終わりました。終わりです。

最終的にこんな感じになりました。去年に比べて参加チーム数が倍以上ですが、CTFtimeに登録したのが大きいんだと思います

CakeCTF 2022
開催期間 2022-09-03 14:00:00 +09:00 – 2022-09-04 14:00:00 +09:00 (24h)
登録チーム数 1103
1点以上獲得したチーム数 713
Welcome / Survey 以外の問題も通したチーム数 327

問題について

時系列のところで明らかですが、今年はCryptoの問題を私が全部作って、それ以外は全部ptr-yudaiが作りました。結果として競技中のptr-yudaiはヒントを求めるDMの嵐に呑まれて大変だったようです。負担を分散したい。

それは置いておいて、作った問題に限ると次のような分布になっていて割と悪くない難易度分布になったかなと思います。hi yoshikingはこの2, 3倍は解かれる想定でした。そうなっていたら完璧でしたね

問題名 Solve数
frozen cake 132
brand new crypto 46
hi yoshiking 10
Rock Door 9

以下簡単な問題の説明と簡易writeupとか感想とかです

frozen cake

warmup問題ですが、ptr-yudai曰く「brand new cryptoのほうが簡単」とのことでした。RSAなのですが m^p \mod n, m^q \mod n, m^n \mod n, nだけが渡されているという一風変わった感じの問題です。意外と見たことないけど解けないのかなと思ってやってみたらすんなり解けたので出題しました。

しかし今思い返すと、warmupでRSAの乗法準同型性に関する知識とフェルマーの小定理を要求していてなかなかハードですね。とはいえCTFの暗号分野では基礎となるような数学の知識ですので、CTFの問題としてはこのくらいは出題したいところです。これが解けたらある程度のCryptoに関する実力がありますと言って良いんじゃないかと思います。

ちなみに問題名のfrozen cakeは適当でなんの由来もないです。warmupで温まってほしいからとりあえず冷えたケーキを出しておきました。

brand new crypto

RSA2問目です。 as + bt \equiv 0 \mod \phi(n), a + b \equiv 1 \mod phi(n)となるような a, b, s, tがあって暗号化は (mr^s, mr^t) \mod n、復号は (mr^s)^a * (mr^t)^b \equiv m^{a+b}r^{as + bt} \equiv m \mod nとなるようなプロトコルで平文が暗号化されていますが、暗号化が1バイトごとなので平文を総当りすれば良いです

なんか雑な暗号方式を自作したら大体脆弱だろうと思ってガチャガチャやっていたら暗号方式っぽいものはできたけど、意外とそのままでは解けなかったのでbyte by byteで暗号化するといういつものやつをやりました。いかにも何かありそうな方式なのでもうちょっとうまく料理したかったですね

そして今配布ファイルを見返すとassertが入ってるけど、これは実験の名残で本番では消すつもりだったのを忘れていた…まあいいか

hi yoshiking

rubyのAES-GCMです。問題がrubyで書いてあるとき、理由があってそうしている場合とそうでもない場合があって、今回は理由があります。AES GCMとかで検索するだけでいくらでも出てきますが、rubyを含むいくらかの言語ではGCMのタグが16バイトじゃないときも受け入れてしまうんですよね。これを利用してtagを1バイトずつ全探索するだけの問題です。有名事実だが問題になってないやつだと思っていたのでこの機会に消費してしまおうと思って問題にしました

予想より全然解かれてなくてびっくりしてる。これはなんかsolve数があったらもっとみんな取り組んですぐ解いたろうなと思います

Rock Door

今回のボス問題です。DSAですが kや r, xの導出にsha256を使っていて、この剰余の法に比べて小さいことを利用してLLLすると解けます。Coppersmith's methodでは解けないと思いますがなんでそうなのかはちゃんと追ってません。なんかBoundが違うのかな……

Thue's Lemmaが割と好きなんですけど問題にしにくくて、それベースでなにかないかと思って作ったのがこれです。 rを渡さないとかこすっからいことをやっているのが不満ですが、式変形してLLLする問題としてはなかなかおもしろく作れたんじゃないかと思ってます

Surveyについて

全部読んでいます。特に記名で書いてもらっているものは顔（アイコン）を想像しながら一語一語噛み締めています。丁寧に書いてもらってありがとうございます。さっと目についたものにお返事します

  • 問題のダイアログの表示位置がよくない
    • すみません。ちゃんとドッグフーディングしてないのがバレる。私も不便だと思ったので改善します。
  • 簡単な問題であっても、やるだけになっておらず、何かしらのひらめきを要するようになっているのが良い
    • ありがとうございます。まさにそのような問題を目指しています
  • 3ヶ月ごとに開いてほしい
    • ptr-yudaiがどれだけ作問できるかによりそうです。私は無理なので。あと運営は準備の時間と体力を激使うのでそのあたりもなんとかしたいですね
  • スマホからだとちゃんと表示されない
    • すみません。全然需要を把握してなくて一切対応しようとしてませんでした。需要があることがわかったのでなんとかするかもしれませんし、余力がなければ後回しにします
  • また開催してください
    • ありがとうございます。がんばります

Surveyはいつでも募集してるのでなにか思いつき次第また書いてくださると嬉しいです。次にCTFを開催する前とかに見直しているので大体1年くらいは書き込むチャンスがあります

その他

どこかには書きたかったけどやっぱりどこにも入れられなかった話を書きます

みんなつよい

これはスコアボードの上位20チームのスクリーンショットです。日本のCTFだとか、カジュアルでレーティングがついてないとか、裏でBalsnCTFがあってデカいチームはみんなそっちをやってるとかはありそうですが、それでも上位にこれだけ日本のCTFチームやCTFプレイヤーがいると嬉しくなりますね。私もこのなかでワイワイ鎬を削りたい

そしてスコアボード全体で見ると日本の国旗がおもったよりたくさんあって、私が把握しているよりも遥かに色んな人がCTFをやっているということもわかり、嬉しいですね。

スコアサーバの更新

ところで、スコアサーバのフロントエンドはNextjsってやつで書いていて、基本的にSSRを使うようにしています。CTF開催後にはこれをSSGにすると静的サイトができて便利なんですよね。それで困っているのがフロントエンドの更新時のダウンタイムです。基本的にフロントエンドの更新はgit pull && docker-compose -f docker-compose.prod.yml up --build -d みたいな原始的な感じでやっているんですが、nextjsのビルドはコンテナの立ち上げ後にやっているので、next buildが走っている間はリクエストを捌けなくてダウンタイムが発生しちゃうんですよね。どうするのがよいのか…

図

図です。スコアサーバ公開からCTF開始までの一週間はなだらかに登録チーム数が増え、CTFの開始と同時に傾向が変化して面白いですね

Welcome, Survey以外の問題の解かれ方のグラフです。あんまり言えることはない気がしますが、難易度の逆転みたいな現象はあまり起きていなさそうです

ケーキ

CakeCTFという名前、かなり良いと思っていて、参加者の方やタイムラインで顔見知りの方がCakeCTFにちなんでケーキの写真を上げてくれたりしています。勝手にそういうツイートを集めて盛り上がっている感じを出しておきます

おわりに

やっぱCTFの運営は楽しいけど……ptr-yudaiが大体全部やってる気もするし元気を取り戻してもっと作問と作問チェックをやるのが今後の目標です

それでは、（あれば）CakeCTF 2023で、そして（運営の元気があれば）zer0pts CTF 2023でもお会いしましょう。バイバイ

*1:私はこのレーティングあんまりうまいこと動いてないと思っていて嫌いですが……

*2:去年のCakeCTFの直後くらいで、某所でなぜCTFTimeに登録しないのですか？　といわれてレーティングを気にせず楽しんでほしいから、と返した直後に実行されたのでCakeCTFのために実装された機能だと密かに思っています。ちなみに他のCTFで使われているところを見たことがない

*3:zer0ptsは故意の被害にあったことがあって、そのときは運営に言ったらなんの確認もなくチーム名を融通してもらえたのでびっくりしました

Google CTF 2022 quals writeup - Maybe Someday

Google Capture The Flag 2022 の qualification roundのMaybe Somedayという問題のwriteupです。それなりに難しかったと思うけど、終わってみると 35 solves でこれは解かれすぎではという印象を受けます。世界にはたくさん強いCTFプレイヤーがいるんだなあ

問題概要

大体こういう感じです。ソースコード全文はgoogle ctfの問題リポジトリ に上がっています。

def challenge(p):
    secret = os.urandom(2)
    secret = hashlib.sha512(secret).hexdigest().encode()

    c0 = p.encrypt(secret)
    print(f'{c0 = }')

    cs = [int(input()) for _ in range(20)]
    for c in cs:
        try:
            p.fast_decrypt(c)
            print('😀')
        except:
            print('😡')

    guess = input().encode()

    if guess != secret: raise Exception('incorrect guess!')

def main():
    p = Paillier()
    n, g = p.public_key()
    print(f'{n = }')
    print(f'{g = }')

    try:
        for _ in range(16):
            challenge(p)
            print('💡')
        print(f'🏁 {flag}')
    except:
        print('👋')
  • 2バイトの平文をあれやこれやしたあとに c_0という暗号文をもらえて、その暗号文の元の平文を16回連続で当てられたらフラグをもらえます。
  • 手がかりとして、Paillier暗号の復号オラクルがもらえます。平文はPKCS#1 v1.5 形式でパディングされるという前提があり、復号時にこの形式に沿っているかどうか、ということがオラクルからわかります
    • このパディング形式では、平文plaintext をパディングすると 00 02 random 00 plaintext という形式になるように random が埋められます（randomにはヌルバイト00は含まないように構成します）

考察

  • 当然与えられた c_0を復号オラクルにそのまま投げても必ずパディングのチェックに成功するのでなんの情報も得られません
  • パディングが不正になるのは復号後の平文が00 02 から始まらないか、randomとplaintext を区別するような00 がないときです
  • 今回の平文はhexdigestであることがわかっているので、plaintextの各バイトは'0'から'f'までのいずれか、すなわち 30 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66 のいずれかになり、00は必ず含まれません
  • paillier暗号には加法準同型性があり、平文 mの暗号文 cが与えられた際に、任意の xを持ってきて m + xを暗号化した暗号文 c'を自由に作ることができます

解法

  • paillier暗号の加法準同型性を用いて、与えられた c_0は00 02 random 00 plaintextという平文を暗号化したものであったところを c'_0として00 02 random ff plaintextに対する暗号文にすることができます
    • 当然これは00を含まない平文に復号されるので必ずパディングのチェックでエラーになります
  • 更に c'_0の平文から適当な値alphaを引いた平文 00 02 random ff (plaintext - alpha) に復号される暗号文 c''_0も構成できます
    • このときは plaintext - alpha に 00 となるような値があるかどうかで、復号に成功するかどうかが変わります
  • ここで例えば平文が '1234512345' という文字列だった場合、バイト列では 31 32 33 34 35 31 32 33 34 35となります。ここからalphaとして30 00 30 00 30 00 30 00 30*1を引いたとすると c''_0を復号した平文は00 31 02 33 04 30 01 32 03 34 となり、00 が含まれるのでパディングのチェックを通過します
  • 一方平文が 'abcdeabcde' という文字列だった場合、バイト列では 61 62 63 64 65 61 62 63 64 65となります。ここからalphaとして同じく30 00 30 00 30 00 30 00 30を引いたときは30 62 32 63 34 60 31 62 33 64となって00は含まれないので、パディングのチェックで不正となります

以上のことを考えると、 c''_0がパディングのチェックを通過するかどうかということは、もともとの平分の狙った範囲に特定の文字が存在するかというオラクルになることがわかります。平文の候補は 2^{16}通りしかないので、このオラクルをうまくつかって候補を絞り込めば平文が一意に定められそうです

exploit

今回は先頭10バイト*2に'0'を含む|含まない、'1'を含む|含まない……という分岐を構成して候補を絞り込みました。ちょっと運要素があって16回連続で成功するときとしないときがありますが、分の悪い勝負ではないです

ソースコード汚すぎてびっくり

from ptrlib import Socket
from Crypto.Util.number import inverse
from itertools import product
import hashlib


table = []
for b in product(list(range(256)), repeat=2):
    table.append(hashlib.sha512(bytes(b)).hexdigest())

size = 10
basenum = int("3000" * size, 16)
basealp = int("6100" * size, 16)
one = int("0100" * size, 16)

sock = Socket("nc maybe-someday.2022.ctfcompetition.com 1337")

n = int(sock.recvlineafter("n = "))
g = int(sock.recvlineafter("g = "))


for stage in range(16):
    print("stage: {}".format(stage + 1))
    c0 = int(sock.recvlineafter("c0 = "))


    # fill 0
    c1 = c0 * pow(g, 0xff << 1024, n**2) % (n**2)


    cs = []
    for i in range(20):
        if i <= 9:
            cs.append(c1 * inverse(pow(g, (basenum + one * i) << (1024 - size*8*2), n**2), n**2) % (n**2))
        elif i <= 0xf:
            cs.append(c1 * inverse(pow(g, (basealp + one * (i - 10)) << (1024 - size*8*2), n**2), n**2) % (n**2))
        else:
            cs.append(c1 * inverse(pow(g, (basenum + one * (i - 16)) << (1024 - size*8*2 - 8), n**2), n**2) % (n**2))

    for c in cs:
        sock.sendline(str(c))

    isin = [0 for _ in range(20)]
    for i, c in enumerate(cs):
        if '😀' in sock.recvline().decode():
            isin[i] = 1

    for h in table:
        head = h[:2*size][::2]
        head2 = h[:2*size+1][1::2]
        match = True
        for i in range(16):
            if isin[i] == 1:
                if hex(i)[2:] not in head:
                    match = False
                    break
            else:
                if hex(i)[2:] in head:
                    match = False
                    break

        for i in range(4):
            if isin[i+0x10] == 1:
                if hex(i)[2:] not in head2:
                    match = False
                    break
            else:
                if hex(i)[2:] in head2:
                    match = False
                    break

        if match:
            sock.sendline(h)
            line = sock.recvline().decode()
            if '💡' in line:
                break
            else:
                print(line)
                raise ValueError("bad luck")
    else:
        raise ValueError("not found")

sock.interactive()

*1:繰り下がりを考えたくないので1文字空きにしています

*2:1バイト空きなので20バイトのうち奇数バイト

ACTF 2022 writeup

zer0pts で ACTF に出たのでwriteupです。真面目に取り組んで8位でした。簡単な前2問はよくできていて面白かったです。後ろ2問は特にcrypto的に面白いことがない割に取り組むのが大変でした

Impossible RSA

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

e = 65537
flag = b'ACTF{...}'

while True:
    p = getPrime(1024)
    q = inverse(e, p)
    if not isPrime(q):
        continue
    n = p * q;
    public = RSA.construct((n, e))
    with open("public.pem", "wb") as file:
        file.write(public.exportKey('PEM'))
    with open("flag", "wb") as file:
        file.write(long_to_bytes(pow(bytes_to_long(flag), e, n)))
    break

あまりにきれいな問題設定に、これ既出じゃないのかという驚きが。

RSAで q = e^{-1} \mod pです。つまり適当な正整数 k \lt eをもってきて eq = 1 + kpがなりたつので、 en = peq = p(1 + kp) = p + kp^2です。 kを全探索すれば未知数は pだけなので、二次方程式を解けばよいです。

from Crypto.Util.number import getPrime, inverse, isPrime, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from tqdm import tqdm
from gmpy2 import iroot

key = RSA.import_key(open("public.pem").read())

n = key.n
e = key.e


for k in tqdm(range(1, e)):
    a = k
    b = 1
    c = -n*e

    x, ok = iroot(b**2 - 4*a*c, 2)
    if not ok:
        continue

    if (b + x) % (2*a) == 0:
        p = int(abs((b + x) // (2*a)))
        break

    if (b - x) % (2*a) == 0:
        p = int(abs((b - x) // (2*a)))
        break

q = n // p
d = pow(e, -1, (p-1)*(q-1))

c = bytes_to_long(open("flag", "rb").read())
m = pow(c, d, n)

print(long_to_bytes(m))

RSA Leak

from sage.all import *
from secret import flag
from Crypto.Util.number import bytes_to_long


def leak(a, b):
    p = random_prime(pow(2, 64))
    q = random_prime(pow(2, 64))
    n = p*q
    e = 65537
    print(n)
    print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


def gen_key():
    a = randrange(0, pow(2,256))
    b = randrange(0, pow(2,256))
    p = pow(a, 4)
    q = pow(b, 4)
    rp = randrange(0, pow(2,24))
    rq = randrange(0, pow(2,24))
    pp = next_prime(p+rp)
    qq = next_prime(q+rq)
    if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
        n = pp*qq
        rp = pp-p
        rq = qq-q
        return n, rp, rq
    
n, rp, rq = gen_key()
e = 65537
c = pow(bytes_to_long(flag), e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("=======leak=======")
leak(rp, rq)

'''
n = ...
e = 65537
c = ...
=======leak=======
122146249659110799196678177080657779971
90846368443479079691227824315092288065
'''

p = a^4 + r_p, q = b^4 + r_q という[RSA] で、[$ n, e, c]の他に n_2, leak = r_p^e + r_q^e + 0xdeadbeef \mod n_2がもらえる。 n_2は十分小さいので素因数分解でき、 r_p, r_qは24bit程度なので全探索できます。 r_pが決まれば自動的に r_qが決まりますが、 n_2が64bitくらいなので、適当にやると r_qも64bitくらいになるところ、正しい r_pを選べていると r_qが24bit程度になるはずなのでわかります。

また、 n \approx a^4b^4 なので n^{1/4} = abがなりたちます。これで n = (a^4 + r_p)(b^4 + r_q), ab = a*bという2式があって、未知数が a, bの2つなので連立方程式を立てれば解けます

from tqdm import tqdm
from sympy.solvers import solve
from sympy import symbols
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes


n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840

ab, _ = iroot(n, 4)
a, b = symbols("a, b", integer=True)

n2 = 122146249659110799196678177080657779971
leak = 90846368443479079691227824315092288065

p2 = 8949458376079230661
q2 = 13648451618657980711

d2 = pow(e, -1, (p2-1)*(q2-1))
x = leak - 0xdeadbeef

for rp in tqdm(range(0, 2**24)):
    rq = pow(x - pow(rp, e, n2), d2, n2)
    if rq < 2**24:
        print((rp, rq))

        y = n - (ab**4 + rp*rq)
        solutions = solve([a**4*rq + b**4*rp - y, ab - a*b])
        for sol in solutions:
            print(sol)
            a_ = int(sol[a])

            p = a_**4 + rp
            q = n // p

            d = pow(e, -1, (p-1)*(q-1))
            m = pow(c, d, n)
            print(long_to_bytes(m))

secure connection

力尽きてきた。bluetoothかなにかの通信が実装されていて、パケットのダンプもあるけど一部データがXXに置き換わったりしてます。 CRCがついてるのでこれに合うようにXXの部分を全探索して、shared numeric keyが24bit 程度しかないので全探索！

retros

Revするとこういう感じのVMであることがわかります

"""
VM:
    regs:
        0: pc
        1: memptr
        2: memptr
        3: value
        4: value
        5: global
        6: flag
    mem[32]: shuffled 32 values
    global: number
"""

pc = 0
ptr1 = 1
ptr2 = 2
val1 = 3
val2 = 4
glob = 5
flag = 6


def check_and_halt():
    """
    print flag if mem is sorted
    """
    return [0]


def add_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [1, idx]


def sub_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [2, idx]


def mv_from_mem(reg, ptr):
    """
    reg = mem[ptr]
    """
    assert reg in [3, 4]  # general register
    assert ptr in [1, 2]  # mem ptr register
    return [3, reg, ptr]


def mv_to_mem(ptr, reg):
    """
    mem[ptr] = reg
    """
    assert ptr in [1, 2]
    assert reg in [3, 4]
    return [4, ptr, reg]


def set_g(val):
    """
    global = val
    """
    assert 0 <= val < 256
    return [5, val >> 4, val & 0x0f]


def set_g_if(val):
    """
    if flag == 1:
        global = val
    """
    assert 0 <= val < 256
    return [6, val >> 4, val & 0x0f]


def memcmp():
    """
    if mem[ptr1] >= mem[ptr2]:
        flag = 1
    """
    return [7]


def cmp_ge(reg):
    """
    if reg >= global
     flag = 1
    """
    assert reg in [0, 1, 2, 3, 4, 5, 6]
    return [8, reg]


def mv_to_g(reg):
    """
    global = reg
    """
    return [9, reg]

31バイト以内でバイトコードを組み立てて送りつけて、32要素のメモリをソートしてcheck_and_haltを呼べばフラグが手に入ります。crypto要素はバイトコードはAES CBCで暗号化したものを送りつけないと行けないけど、鍵は知らないのでpadding oracle encryption attackを使ってオラクルを頼りに暗号文を構築するところで、あとはrev + miscです。

謎の31バイト制限&10000ステップ制限、貧弱なバイトコード、readlineの実装のせいで暗号化したバイトコードに0x0aは含められないなど様々な制約を突破するとフラグが手に入ります。このあたりのバイトコード組み立てとかの詳しいことは id:keymoon が書いてくれるはず。私はRevとpadding oracleしたのと、0x0aが含められなくて困るけどpadding oracle encryptionの最後のブロックは自由度があるのでそこをガチャすればいいって言うかかりをやりました

↓こういう感じで解ける

import random
from ptrlib import Process
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

"""
VM:
    regs:
        0: pc
        1: memptr
        2: memptr
        3: value
        4: value
        5: global
        6: flag
    mem[32]: shuffled 32 values
    global: number
"""

pc = 0
ptr1 = 1
ptr2 = 2
val1 = 3
val2 = 4
glob = 5
flag = 6


def check_and_halt():
    """
    print flag if mem is sorted
    """
    return [0]


def add_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [1, idx]


def sub_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [2, idx]


def mv_from_mem(reg, ptr):
    """
    reg = mem[ptr]
    """
    assert reg in [3, 4]  # general register
    assert ptr in [1, 2]  # mem ptr register
    return [3, reg, ptr]


def mv_to_mem(ptr, reg):
    """
    mem[ptr] = reg
    """
    assert ptr in [1, 2]
    assert reg in [3, 4]
    return [4, ptr, reg]


def set_g(val):
    """
    global = val
    """
    assert 0 <= val < 256
    return [5, val >> 4, val & 0x0f]


def set_g_if(val):
    """
    if flag == 1:
        global = val
    """
    assert 0 <= val < 256
    return [6, val >> 4, val & 0x0f]


def memcmp():
    """
    if mem[ptr1] >= mem[ptr2]:
        flag = 1
    """
    return [7]


def cmp_ge(reg):
    """
    if reg >= global
     flag = 1
    """
    assert reg in [0, 1, 2, 3, 4, 5, 6]
    return [8, reg]


def mv_to_g(reg):
    """
    global = reg
    """
    return [9, reg]

instructions = []
jump_marker = {}


def jump1(name1):
    # 3: set_g
    # 2: add_g
    return [name1, None, None, None, None]  # placeholder


def jump(name1, name2):
    # 3: set_g
    # 3: set_g_if
    # 2: add_g/sub_g
    return [name2, None, None, name1, None, None, None, None]  # placeholder


def mark(name):
    jump_marker[name] = (len(instructions)) * 4



mark("outer_loop_begin")
# ptr1 += 1
instructions += set_g(1)
instructions += add_g(ptr1)

# ptr2 = 0
instructions += mv_to_g(ptr2)
instructions += sub_g(ptr2)

# flag = ptr1 >= 32
instructions += set_g(32)
instructions += cmp_ge(ptr1)
instructions += jump("check", "inner_loop_begin")

mark("inner_loop_begin")
# flag = mem[ptr1] >= mem[ptr2]
instructions += memcmp()
instructions += jump("inner_loop_end", "swap")

mark("swap")
instructions += mv_from_mem(val1, ptr1)
instructions += mv_from_mem(val2, ptr2)
instructions += mv_to_mem(ptr1, val2)
instructions += mv_to_mem(ptr2, val1)

mark("inner_loop_end")
# flag = ptr2 >= 31
# ptr2 += 1
# if (flag) break;
# else      continue;
instructions += set_g(1)
instructions += add_g(ptr2)

instructions += mv_to_g(ptr1)
instructions += cmp_ge(ptr2)
instructions += jump("outer_loop_begin", "inner_loop_begin")

mark("check")
instructions += check_and_halt()

g_if_ind = set()
# encode instructions
is_jump_forward = False
for i in range(len(instructions)):
    if isinstance(instructions[i], str):
        name = instructions[i]
        jump_to = jump_marker[name]
        if i+3 < jump_to:
            is_jump_forward = True
        else:
            is_jump_forward = False

        if isinstance(instructions[i+3], str):
            g_if_ind.add(i + 3)

        if i in g_if_ind:
            a, b, c = set_g_if(abs(jump_to - (i+5) * 4))
            instructions[i+0] = a
            instructions[i+1] = b
            instructions[i+2] = c
        else:
            a, b, c = set_g(abs(jump_to - (i+8) * 4))
            instructions[i+0] = a
            instructions[i+1] = b
            instructions[i+2] = c

    elif instructions[i] is None:
        if is_jump_forward:
            a, b = add_g(pc)
            instructions[i+0] = a
            instructions[i+1] = b
        else:
            a, b = sub_g(pc)
            instructions[i+0] = a
            instructions[i+1] = b

print(len(instructions), instructions)

i = 0
remain_insns = list(instructions)
res = ""
insts = [(1, "check"), (2, "add_g"), (2, "sub_g"), (3, "mv_from_mem"), (3, "mv_to_mem"), (3, "set_g"), (3, "set_g_if"), (1, "memcmp"), (2, "cmp_ge"), (2, "mv_to_g")]
while len(remain_insns) != 0:
    l, name = insts[remain_insns[0]]
    ops = remain_insns[:l]
    args = ops[1:]
    remain_insns = remain_insns[l:]
    
    op =   (str(ops[0])).rjust(3)
    arg0 = (str(ops[1]) if 2 <= l else "").rjust(3)
    arg1 = (str(ops[2]) if 3 <= l else "").rjust(3)

    if name in ["set_g", "set_g_if"]:
        disasm = f'{name}({ops[1] * 0x10 + ops[2]})'.ljust(18) + f'# {ops[1]}, {ops[2]}'
    else:
        disasm = f'{name}({", ".join(map(str, args))})'
    res += f'{str(i).rjust(3)}: {op} {arg0} {arg1} | {disasm}\n'
    i += l * 4

print(res)

if len(instructions) % 2 == 1:
    instructions.append(0)
payload = []
for i in range(0, len(instructions), 2):
    payload.append((instructions[i] << 4) | instructions[i+1])

if payload[-1] != 0:
    payload.append(0)
print(len(payload), payload)
assert 16 < len(payload) < 32
payload = pad(bytes(payload), 16)

# on remote, encode payload by using padding oracle encryption attack
iv = b"\0"*16
key = b"A" * 16
with open("./key", "wb") as f:
    f.write(key)

"""
aes = AES.new(mode=AES.MODE_CBC, key=key, iv=iv)
ticket = aes.encrypt(payload)

sock = Process("./retros")

input("WAIT> ")
sock.sendline(ticket)
sock.sendlineafter("fortune: ", b"\0"*0x10)
sock.interactive()
"""

import pwn, subprocess

LOCAL = False

# if LOCAL: io = pwn.process('./retros')
if LOCAL: io = pwn.remote("localhost", 8003)
else: io = pwn.remote('123.60.146.157', 9999)

if not LOCAL:
    print(io.recvline())
    dat = io.recvline().split(b'`')[1].decode().split()[2]
    print(dat)
    dat = subprocess.check_output(['hashcash','-mb26',dat])
    print(dat)
    dat = dat.decode().split(' ')[-1].strip()
    print(dat)
    io.sendline(dat)
    print(io.recvline())
    print(io.recvline())

def _do_oracle(ct2, token, j):
    if j < 0:
        return token, False
    
    candidate = []
    last_byte = None
    xval = ([0] * 16 + [16 - j] * (16 - j))[-16:]
    for i in range(256):
        token[j] = i
        send_token = pwn.xor(token, xval)
        if b'\n' in send_token:
            candidate.append(i)
            continue
        io.sendline(send_token + ct2)
        io.sendline(b'\x00' * 16)
    for i in range(256):
        if i in candidate: continue
        r = io.recvline()
        if b'not complete' in r:
            print(j, i, token)
            last_byte = i
    if last_byte is not None:
        token[j] = last_byte
        res, _ = _do_oracle(ct2, bytearray(token), j - 1)
        return res, True

    assert 1 <= len(candidate)
    print(f'[+] {j=} {token[j + 1]=} {len(candidate)=}')
    for i in candidate:
        token[j] = i
        res, confidence = _do_oracle(ct2, bytearray(token), j - 1)
        print(res)
        if confidence:
            print(f'[+] discoverd! {res=}, {confidence=}')
            return res, True
    return res, confidence

def do_oracle(ct2):
    token = bytearray(b'\x00' * 16)
    j = 15
    res, _ = _do_oracle(ct2, token, j)
    return res

init_ct2 = b'superneko'.ljust(16, b'\x00')

ct2 = do_oracle(init_ct2)
print(f'{ct2=}')
ct2 = pwn.xor(ct2, payload[16:])
ct3 = do_oracle(ct2)
print(f'{ct3=}')
ct3 = pwn.xor(ct3, payload[:16])

io.send(ct2 + init_ct2 + b'\n' + ct3 + b'\n')

io.interactive()