AlpacaHack Round 12 (Crypto)

RSARSARSARSARSARSA
OTEC
Flag Sharing
Zero-sum game
全体を通しての感想

こんにちは。今日はAlpacaHack Round 12 (Crypto)でした。

AlpacaHackは6時間4問の個人戦CTFを不定期で開催しているCTFプラットフォームです。程よいボリュームであること、毎回良質な問題が提供されることから今一番贔屓にしています。

今回はyu212 さんによるCrypto回で、私はCTFではCryptoが特に好きなので参加して、4問中3問を解いて7位でした。目標は4時間*1で4問のつもりだったのに実際は3問と及ばず残念ですが、せっかくなのでwriteupです。今回は個人的にははじめて問題に取り組む中でAIサービスをうまく使うことができたので、何をAIに助けてもらったのか、なども記録します。

RSARSARSARSARSARSA

問題は非常にシンプルです。

from math import gcd
import os
from Crypto.Util.number import getPrime, bytes_to_long

e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")

m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)

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

RSAの問題で、以下の要素があります。

$e$ が小さいことで素朴に $e$ 乗根をとるアプローチや、 $e$ 乗を含む多項式の根を求めるアプローチを想像します。今回は平文が大きいので前者のアプローチは棄却しました。

一方、後者のアプローチは平文の構造がわかっていることもあり有力と感じました。 RSAで一部の値がわかっている時 - crypto-writeup-publicの「eが小さく、mの大部分がわかっている時」のアプローチですね。

素朴に平文をエミュレートしてやればよく、flagは未知部分を $x$ と置いてprefix*256^19 + x*256 + suffix と書けますから、あとはこれを1337回繰り返すようにして $e$ 乗すれば $c$ 相当の式になります。結局 $x$ に関する19次の式に落ち着くので、Coppersmith法で解けます。

こういう感じですね

f = open("output.txt")

n = int(f.readline().strip().split(" = ")[1])
e = int(f.readline().strip().split(" = ")[1])
c = int(f.readline().strip().split(" = ")[1])

prefix = int(b"Alpaca{".hex(), 16)
suffix = int(b"}".hex(), 16)

PR.<x> = PolynomialRing(Zmod(n))
f = 0
for _ in range(1337):
    f = f*256**26 + (prefix*256**19 + x*256 + suffix)
f = (f**e - c).monic()

roots = f.small_roots(X=256**18, beta=0.5)
flag = b"Alpaca{" + int(roots[0]).to_bytes(18, "big") + b"}"
print(flag)

……というのはCTF終了後だからいえることで、なんか競技中はバグらせまくって大苦戦しました。素朴に筋肉が衰えていたのだと思いますが……。

↑の方針を立てたは良いのですが、なんか実装をミスって $f$ が $19*1337$ 次になって困り果て、AIに聞きまくったところ、3回目くらいで以下のようなコードを出してくれました。式をmonicにして、Coppersmith法のパラメータを調整するところだけ人間がやったら解けるところまでできていたので、本番はそれで解きました。






long_flag_poly = prefix_val_part * (R**(unknown_len + len(suffix_bytes))) + \
                 x * (R**len(suffix_bytes)) + \
                 suffix_val_part



S = (pow(R, flag_len * 1337) - 1) // (pow(R, flag_len) - 1)


m_poly = long_flag_poly * S



f_poly = m_poly^e - c

まだ微妙にこの立式のことを理解してないのですが、やってることは同じなはず。なんか $S$ は等比数列の和らしいです。私がforでやってることを数学的にまとめるとこうなるんでしょうね。

OTEC

こちらもシンプルな問題です

import os
import signal
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

signal.alarm(60)

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}").encode()


G = secp256k1.G
a = secrets.randbelow(secp256k1.q)
A = a * G

print(f"{A.x = }")
print(f"{A.y = }")

x, y = map(int, input("B> ").split(","))
B = Point(x, y, secp256k1)

k0 = long_to_bytes((a * B).x, 32)
k1 = long_to_bytes((a * (B - A)).x, 32)

def encrypt(message, key):
    return AES.new(key, AES.MODE_ECB).encrypt(pad(message, 16))

print(encrypt(flag[0::3], k0).hex())
print(encrypt(flag[1::3], k1).hex())
print(encrypt(flag[2::3], bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))).hex())

楕円曲線を用いた紛失通信(Obilivious Transfer)が実装されています。紛失通信というのは送信者がn種類の値を暗号化して送り、受信者がそのうちのどれか1つのみを復号可能であって、送信者や他者からはどちらを復号できたかは不明、という性質をもつプロトコルです。そして、CTFでは大体受信者となって、なんとかしてすべての値を復号せよ、という問題が出題されます。

今回の問題では以下のような流れになっています。

送信者が $A = aG$ を計算して $A$ を渡してくれるので
受信者は適当に $b$ を決めて $B = bG$ を送ると
送信者が $aB$ , $a(B - A)$ を計算し、それぞれのx座標を $k_0, k_1$ として
$k_0, k_1$ および $k_0 \oplus k_1$ を鍵として3種類の暗号文を送る

とりあえずこういう問題がでたら、とりあえず素朴にやって値1つを復号できることを確認します。

今回の場合は本当に適当な $b$ を選ぶと、 $k_0$ の導出に使われる $aB$ は $aB = abG = baG = bA$ と変形できるので受信者側で計算できて、 $k_0$ で暗号化されている値が復号できます。一方このとき $k_1$ は $a(B - A) = abG - aA = baG - aA = bA - aA$ から算出されますが、 $a$ がわからないので $aA$ は計算できず求められません。

$k_1$ を求めたい場合は $B = A + G$ ということにすると $a(B - A) = a(A + G - A) = aG = A$ となって、 $A$ は受信者側わかります。このとき $aB = a(A + G) = aA + aG = aA + A$ で、やはり $aA$ が計算できず $k_0$ は求められません。

こうしてみるとなんとなく紛失通信っぽくなっていて、 $k_0, k_1$ を同時に求めることは不可能そうに見えます。フラグは通信を超えて固定なので2回通信すればそれぞれのケースで $k_0$ または $k_1$ がわかり、フラグ全体の2/3までは求められそうですが、困りました。

ここでXORの性質に思いを馳せると*2、 $k_0 \oplus k_1$ の値がわかるのは $k_0$ および $k_1$ の両方がわかっているときと、 $k_0 = k_1$ が満たされて $k_0 \oplus k_1 = 0$ となっているときです。 $k_0, k_1$ 同時にはわからないので、わからないにせよ $k_0 = k_1$ となるようなケースを作ることを目指します。

素朴に立式して $aB = a(B - A)$ です。これを整理すると $aB = aB - aA$ から $O = aA$ となって、これはこまりました。受信者が操作可能なのは $B$ だけなのに、式を整理すると $B$ は消えてしまいます。つまり $aB = a(B - A)$ となるケースは作れません。

ここでめげずに、 $k_0, k_1$ は楕円曲線上の点のx座標から計算されていることを思い出し、さらに $x(P) = x(-P)$ であることまで思い出すと*3、もう一つの式 $aB = -a(B - A)$ が立式できます。こちらは整理すると $2aB = aA$ となり、両辺を比較すると $B = \frac{1}{2}A$ とすれば $aB, a(B - A)$ のx座標が等しくなって、 $k_0 = k_1$ が実現できそうということがわかります。

ということで実装するとこうです。この問題ではAIに頼ることはありませんでした。自分で解けたので。


p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
q = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1
E.set_order(q)

from ptrlib import Socket
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES

def decrypt(message, key):
    return unpad(AES.new(key, AES.MODE_ECB).decrypt(message), 16)

HOST = "34.170.146.252"
PORT = 62340


sock = Socket(HOST, PORT)
Ax = int(sock.recvlineafter(" = ").strip().decode())
Ay = int(sock.recvlineafter(" = ").strip().decode())
A = E((Ax, Ay))

sock.sendlineafter("B> ", "{},{}".format(G.x(), G.y()))
k0 = long_to_bytes(int(A.x()), 32) 
print("k0 = {}".format(k0.hex()))

c0 = bytes.fromhex(sock.recvline().strip().decode())
m0 = decrypt(c0, k0)
sock.close()



sock = Socket(HOST, PORT)
Ax = int(sock.recvlineafter(" = ").strip().decode())
Ay = int(sock.recvlineafter(" = ").strip().decode())
A = E((Ax, Ay))
B = A+G

sock.sendlineafter("B> ", "{},{}".format(B.x(), B.y()))
k1 = long_to_bytes(int(A.x()), 32)  
print("k1 = {}".format(k1.hex()))

_ = sock.recvline()
c1 = bytes.fromhex(sock.recvline().strip().decode())
m1 = decrypt(c1, k1)
sock.close()


sock = Socket(HOST, PORT)
Ax = int(sock.recvlineafter(" = ").strip().decode())
Ay = int(sock.recvlineafter(" = ").strip().decode())
A = E((Ax, Ay))











r = (q+1) / K(2)
B = r*A
assert 2*B == A

sock.sendlineafter("B> ", "{},{}".format(B.x(), B.y()))
k2 = long_to_bytes(0, 32)  

_ = sock.recvline()
_ = sock.recvline()
c2 = bytes.fromhex(sock.recvline().strip().decode())
m2 = decrypt(c2, k2)
sock.close()

print(b"".join(bytes([a, b, c]) for a, b, c in zip(m0, m1 + b"\0", m2 + b"\0")))

こちらも非常にシンプルな問題です。

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

N = 10

def random_poly(t):
    return [secret] + [secrets.randbelow(p) for _ in range(t - 1)]

def evaluate(f, x):
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

p = getPrime(512)
flag = os.environ.get("FLAG", "Alpaca{************* REDACTED *************}")
assert len(flag) == 44 and flag.startswith("Alpaca{") and flag.endswith("}")
secret = bytes_to_long(flag.encode())

xs = [secrets.randbelow(p) for _ in range(N)]
f = random_poly(N)
shares = [evaluate(f, x) for x in xs]

print(f"{p = }")
print(f"{xs = }")

for i, share in enumerate(shares, 1):
    print(hex(share)[:-i] + "?" * i)

シャミアの秘密分散が(10, 10)で実装されていますが、シェアの一部が欠けています。どういう欠け方をしているかについては、こう↓です。末尾の4, 8, 12, 16, ..., 40ビットが欠けてます。

一見してなかなか大変そうな問題だと思ったのですが、問題のスクリプトをAIに投げてありえそうなアプローチを思いつくだけ列挙してと依頼したところ、LLLを利用する方法だけが提案されました。そこに表示されている式がなんとなくあってそうかつ取り組めそうだったので、この方針を採用しました。

LLLでやるときは、何らか既存の名前がついている問題((extended) Hidden Number ProblemやApproximate GCD)に当てはめてその問題用の格子を作るケースと、とにかく（不）等式を立式してInequality Solving with CVP - crypto-writeup-publicに解いてもらうケースがありますが、今回は後者でできそうでした。

Inequality Solving with CVPの使い方については上記のリンクや kurenaif さんによる以下の投稿を参考にしてください。

SECCON CTFの Tidal waveの author's writeupでも使用している Inequality Solving with CVPというライブラリの紹介です！
一見すごく難しそうに見えるのですが意外と簡単に使えるのでおすすめです！
upsolveでお試しください！https://t.co/mLnN0LnsLP pic.twitter.com/0hMY6vaqgq
— kurenaif🪄🗝 (@fwarashi) 2024年12月2日

さて、立てる不等式を考えていきます。今回のケースでは $p$ 上のある秘密の多項式 $f(x) = c_0 + c_1x + c_2x^2 + \dots + c_9x^9$ があって、ここに適当な値 $x_0, \dots, x_9$ を次々に当てはめてシェア $y_i = f(x_i)$ を計算しています。

未知数は $c_0, \dots, c_9$ 及び、 $f(x_i)$ を $\pmod p$ 上に収めるための適当な整数 $k_0, \dots, k_9$ です。 $y_i = f(x_i) - k_ip$ というイメージですね。計算結果は $y_i$ となってほしいですが、先述の通りシェア $y_i$ は最大40bit欠けていますから、ここを不等式として $f(x_i)$ の値がありうる $y_i$ の最小値と最大値の間に収まるようバウンドを設定します。

また、 $c_0, \dots, c_9$ については $0 \leq c_i \lt p$ という不等式も立ちますのでこれも入れておきます。特にフラグである $c_0$ は制約によって上限と下限がもっと狭められるので、それも設定します。

ということでこういう行列が作れました。

min_flag = int(("Alpaca{" + " "*(44 - 8) + "}").encode().hex(), 16)
max_flag = int(("Alpaca{" + "~"*(44 - 8) + "}").encode().hex(), 16)


M = matrix(ZZ, [
    [1 if i == j else 0 for i in range(N)] + [0] * N
    for j in range(N)
] + [
    [pow(xs[j], i, p) for i in range(N)] + [-p if i == j else 0 for i in range(N)]
    for j in range(N)
]).T
lb = [ min_flag ] + [0] * (N - 1) + ys
ub = [ max_flag ] + [p] * (N - 1) + [y + ((1 << 4*i) - 1) for i, y in enumerate(ys, 1)]

伝わってるか心配なので画像でも……

ソリューションスクリプト全体は以下のようになりました。コメントにあるように求まったフラグは微妙に壊れてたんですが、きれいに求める方法はわからなかったので手で推測して当てました。

import ast

N = 10

f = open("./output.txt")
p = ast.literal_eval(f.readline().strip().split(" = ")[1])
xs = ast.literal_eval(f.readline().strip().split(" = ")[1])
ys = []
for _ in range(N):
    y = ast.literal_eval(f.readline().strip().replace("?", "0"))
    ys.append(y)

min_flag = int(("Alpaca{" + " "*(44 - 8) + "}").encode().hex(), 16)
max_flag = int(("Alpaca{" + "~"*(44 - 8) + "}").encode().hex(), 16)


M = matrix(ZZ, [
    [1 if i == j else 0 for i in range(N)] + [0] * N
    for j in range(N)
] + [
    [pow(xs[j], i, p) for i in range(N)] + [-p if i == j else 0 for i in range(N)]
    for j in range(N)
])
lb = [ min_flag ] + [0] * (N - 1) + ys
ub = [ max_flag ] + [p] * (N - 1) + [y + ((1 << 4*i) - 1) for i, y in enumerate(ys, 1)]

for row in M.T:
    for x in row:
        print(Integer(x).nbits(), end="\t")
    print()

load("./rkm.sage")

_, _, sol = solve(M.T, lb, ub)

print(bytes.fromhex(hex(sol[0])[2:]))

AIに方針を教えてもらって自分で解法実装していい感じで解けたと思います。

Zero-sum game

解けませんでした。いくら「離散対数問題を解かないといけないからBSGSとか実装してもらえませんか」と言ってもAIがMeet-in-the-Middleの方針に固執したり、「Nimberで逆数を求める方法を教えて下さい」と言ったら $GF(2^{512})$ でinverseしたら良いと言われたのですが実験してみたらうまくいかずで、進み方がわからなかった。

そもそも計算量を落とすためにはもっと工夫する必要がありそうでしたが、私の知識もたりなかったし、AIもうまく方針をいろんな方面から立てるということができず歯が立たなかった印象です。素朴に離散対数問題が解けたら4回も入力する必要がないので、4回入力することでどういうことができると考えられるか、などの方面から考察をすすめる（あるいは考えさせる）などが必要だったなと思います。

全体を通しての感想

どの問題もとても好みでよかったです。良いセットだと思いました。Authorのyu212さんとAdminの皆様にあらためて感謝を。

個人的にはCTF関連の勘や筋力が衰えていて1問あたりにかける時間が長くなってしまって、自分と同じ3問を通したなか同点の群では最下位になってしまったので反省です。AIを利用して解けるようになったというところは良かったので、実装をバグらせたりしないようにするというのが頑張れるポイントだと思う。

一方、このくらいの難易度ならもっと他の人もバンバンといて自分の順位はもっと低いかなと思っていたところ、ゆっくりでもちゃんと解いたらある程度上位に入れたことは嬉しいです。再来週もAlpacaHackではRound 13(Crypto) が開催されるようなので、また自分を満足させる順位を取れるように頑張りたいところです。

alpacahack.com

RSARSARSARSARSARSA

OTEC

Flag Sharing

Zero-sum game

全体を通しての感想