IERAE CTF 2024 [writeup]

初めに

こんにちは、大阪大学CTFサークルWani Hackaseのぐれいしゃです。
9/21（土）15:00 JST～9/22（日）15:00 JSTに開催されていたIERAE CTF 2024にWani Hackaseとして参加し、8位を取ることが出来ました！（といっても僕は1問解いた後は置物と化していました）

本記事ではcryptoのsplittingを解説します。
フィーリングに頼って解いた部分が大きいので、厳密な解法は他のつよつよCTFプレイヤーのwriteupを見てください。
本文中に誤りがあればご指摘いただけると幸いです

splitting[cry]

問題

Do you need to solve many ECDLPs?
$ nc 35.221.142.92 11119

challenge.sage

#!/usr/bin/env sage

from Crypto.Util.number import *
from os import getenv

FLAG = getenv("FLAG", "TEST{TEST_FLAG}").encode()
f = bytes_to_long(FLAG)

p = random_prime(2^128)
Fp = GF(p)
a, b = Fp.random_element(), Fp.random_element()
E = EllipticCurve(Fp, [a, b])

print(a)
print(b)
print(p)

gens = list(E.gens())
if len(gens) < 2:
    gens.append(ZZ(Fp.random_element()) * E.gens()[0])

res = []
while f > 0:
    r = Fp.random_element()
    res.append(ZZ(r) * gens[f & 1])
    f >>= 1

for R in res:
    print(R.xy())

状況整理

128ビットの素数$p$を位数とする有限体$F_p$と$F_p$上の楕円曲線$E: y^2 = x^3+ax+b$をランダムに設定し、パラメータ$a, b, p$を出力する。

次に、$E$の生成元をリストに格納するが、生成元の個数が1個の場合は、$F_p$のランダムな値を生成元に掛けた元を異なる生成元としてリストに格納する。
この時点で2つの生成元があるので、簡単のために$g_0, g_1$と呼ぶ。

その後、FLAGを2進数とみなしたときの下位ビットから順番に見て最上位ビットまで以下の処理を行う。
$F_p$のランダムな元$r_i$を取り、ビットが立っていれば$g_1$を$r_i$倍した点$P_i$を計算し、ビットが立っていなければ$g_0$を$r_i$倍した点$P_i$を計算する。計算した点$P_i$をリストに格納する。

最後に今まで計算した$P_i$を順に出力する。

試したこと・思考過程

$a, b, p$が与えられているので$E.gens()$で生成元を作る
→多くの場合で生成元の個数は1個だが、たまに2個になることがある
→生成元が2個の場合は$P_i$が$g_0, g_1$から生成されているかweil pairingを用いて判別できそう？（例：AlpacaHack Round3のA Dance of Add and Mulなど）
→大体判別出来るが、たまに$g_0$から生成されるかつ$g_1$から生成される点が存在する
→$g_0, g_1$の両方から生成可能な点の個数が少ないようなケースを大量に集めて復元したら良さそう

どのくらい集める必要がある？
→点の個数は全部で567個。2つの生成元から生成可能な点は大体200後半ぐらいだが、たまに100個ぐらいのときがあるので100個の場合を考える
→568ビットの内100ビットが間違っているとすると、あるビットが誤っている確率は$\frac{1}{5.68}$である
→100個の誤りを含んだビット列をn個用意する。あるビットに着目すると、n個中の半分以上が誤っている確率は$p = \sum_{i=\frac{n}{2}}^{n}{}_n C_i(\frac{1}{5.68})^i(\frac{4.68}{5.68})^{n-i}$
→568個のいずれのビットについても、誤っているのが$\frac{n}{2}$個未満である確率は$p' = (1-p)^{568}$
→これでnを色々試してみると$n = 24$の時に$p' = 0.846$となった
→そこそこ高確率であることと、100個以下のパターンがそんなに出ないことから$n = 24$で妥協

解法

生成元が2個のケースを大量に集めて、その中で両方の生成元から生成されうる点の個数が100個以下になる場合を探し、そのような場合を24個集めてFLAGを復元します。
上記の処理を実装したものが以下になります。

preprocess.sage

from Crypto.Util.number import *

# ファイルを指定するための値、後述するが手作業で0からインクリメントして400まで増やした
iterate = 400
num = str(iterate)
# パラメータと点の情報を読み込む
with open('genlen2_'+num+'.txt') as f:
    a = int(f.readline())
    b = int(f.readline())
    p = int(f.readline())
    points = [tuple(map(int, line.split())) for line in f]
    
E = EllipticCurve(GF(p), [a, b])
gens = list(E.gens())
print(f'len gens = {len(gens)}')
g0 = gens[0]
g1 = gens[1]
o1 = g0.order()
o2 = g1.order()

cnt = 0
bcnt = 0
fs = []
for x, y in points:
    P = E(x, y)
    try:
        e1 = P.weil_pairing(g0, g0.order())
    except:
        e1 = 0
        e2 = 1
    try:
        e2 = P.weil_pairing(g1, g1.order())
    except:
        e2 = 0
    if e1 == 1 and e2 != 1:
        fs.append(0)
    elif e1 != 1 and e2 == 1:
        fs.append(1)
    else:
        # g0からもg1からも生成される場合、ビットの誤りとしてカウント
        print(f'e1 = {e1}, e2 = {e2}')
        bcnt += 1
        fs.append(0)
    cnt += 1

fs = fs[::-1]
flag = 0
for f in fs:
    flag <<= 1
    flag += f

flag_len = len(points)
bin_flag = bin(flag)[2:].zfill(flag_len)
isWrite = True
# cipher_list.txtに誤りの数と復元されたFLAGを書き込む
with open('cipher_list.txt', 'a') as f:
    if isWrite:
        f.write('num: '+num+', '+'bcnt: '+str(bcnt)+', ')
        isWrite = False
    f.write(bin_flag + '\n')

solve.sage

from Crypto.Util.number import *

bs = []
with open('cipher_list.txt') as f:
    while True:
        line = f.readline()
        if not line: break
        num, bcnt, bits = line.split(', ')
        bcnt = int(bcnt.split(': ')[1])
        if bcnt <= 100:
            if len(bits) != 568:
                print(f'len(bits) = {len(bits)}')
                print(f'bits = {bits}')
            bs.append(bits)

print(f'len(bs) = {len(bs)}')
flag = ''
bit_len = len(bs[0])
assert bit_len == 568
print('bit_len:', bit_len)
for i in range(bit_len):
    one = 0
    zero = 0
    for b in bs:
        if b[i] == '1':
            one += 1
        else:
            zero += 1
    if one > zero:
        flag += '1'
    elif one < zero:
        flag += '0'
    else:
    # 同数となった場合は誤りが100個以下のケースの内、誤りが最小のものを採用
        if bs[-5][i] == '1':
            flag += '1'
        else:
            flag += '0'
        
flag = flag[:567]
# 'IERAE{'から始まるので置き換える
prefix = '10010010100010101010010010000010100010101111011'
prefix_len = len(prefix)
# '}'で終わるので置き換える
suffix = '01111101'
suffix_len = len(suffix)
flag = prefix + flag[prefix_len:-suffix_len] + suffix
flag = int(flag, 2)

flag = long_to_bytes(flag)

for i in range(len(flag)):
    # 印字可能な文字であるので0x7fでマスクする
    flag = flag[:i] + bytes([flag[i] & 0x7f]) + flag[i+1:]

print(flag)

生成元が2個の時のパラメータと点のデータを集めるスクリプトは省略します。
これらを実行することでFLAGを獲得しました。

謎

この解法でなんとか解くことが出来ましたが、本番中分からなかったことがいくつかありました。

• 何故g0からもg1からも生成される点があるのか
• preprocess.sageのiterateをforで変更しようとするとバグる

一番については後から調べて多分こうではないか？と思ったことがあるのでそれを書いておきます。
sagemathのgens()では生成元が2つある場合について次のような記述があります。

$E$上の点群は必ずしも生成元$P, Q$によって生成される点の集合の直積になるとは限らない、つまり、$\langle P \rangle \cap \langle Q \rangle \neq \emptyset$である可能性があります。（というか試したケース全てでそうでした）
gens()で返ってくる生成元の取り方が最適ではなかったため、こういうことがあったみたいです。

2番目については本当に謎で、preprocess.sageのiterate（ファイルを指定するための変数）をfor文で変更しようとしたら何故か$e(P, g_0), e(P, g_1)$が謎の数値になりました。プログラムが間違っているのかと思いましたが、手動でやると$e(P, g_0) = e(P, g_1) = 1$になり、自分の想定している挙動をしていました
本番中、このバグ（？）を直すことが出来なくて、ひたすら生成元が2になるパターンを収集→手作業でファイルを指定し直してpreprocess.sageを回すということを繰り返していました。
最初は単調作業で気が狂いそうだったので踊ったり筋トレしたりしていましたが、最後の方になると楽しくなってきてガチャ感覚で回していました。ちなみに100個以下のパターンを24個集めるのに400個のケースを集めました。
結局のところ、このバグと思わしき挙動がプログラムのミスなのかsagemathの仕様なのか、他の問題なのか分からず仕舞いでした。おそらく今後も分かることはないでしょう。
謎を謎のままにしておく勇気。

終わりに

今回のCTFでは頭を悩ませる問題が多く、取り組んでいて非常に楽しかったです。結局解けたのはeasyだけで、mediumは解くことが出来ませんでしたが、あとからwriteupを見てこんな方法があるのかと大変勉強になりました。
知識と技術をより蓄えて、次回こそはmediumを解くぞ～～！！
最後になりましたが、運営の皆さん、素晴らしいCTFをありがとうございました！！