TON CTF 2024 Writeup(中文)
这篇文章是我和Leo一起参加 TON CTF 2024 比赛的解题记录。TON CTF 由 TON Foundation 赞助，Tonbit 和 TONX Studio 组织，比赛涵盖了多个与 TON 区块链相关的挑战，全部使用 Tact 语言编写。Tact 是一种高层语言，编译为 Func，再编译为 Fift，最终生成适用于 TON 虚拟机的字节码。这次比赛让我更加深入了解了 TON 生态系统的独特性和它的编程模型。
这是我第一次参与CTF相关的比赛，整个体验既紧张刺激又令人难忘。比赛仅持续一天，共有8道题目。我和我的队友 Leo 共同完成了这次挑战，并最终取得了第四名的成绩。你可以在这个仓库中查看每道题目的详细介绍：TonCTF-Challenges。
Airdrop
分数：100
Airdrop 题目的目标是消耗合约的初始供应量 30,000 个代币。合约允许用户领取 1 个代币，但漏洞出现在存入和取出功能的实现上。因为合约没有严格检查传入的金额是否为正数，这使得我们可以利用负值来操纵合约的余额。
解题步骤： 我们首先构建一条带有负数金额的消息，并将其发送给合约，借此绕过了合约的余额检查，从而减少了合约的供应量，最终达成目标。核心代码如下：
airdrop.send(provider.sender(),{ value: toNano("0.1") },{ $$type: "UserStake", amount: -30000n })
这段代码的作用是构造一个包含负值金额的消息，调用的是UserStake 消息。通过将一个负数金额传入合约中，导致合约错误地减少其总供应量。
Random
分数：100
Random 题目要求我们猜测一个幸运数字，猜对后合约会将标志位设置为 1，表示解题成功。合约使用当前时间和用户地址的哈希值来生成随机数，但由于哈希生成的范围较小（0-99），这使得我们可以通过暴力猜测的方法解决这个问题。
解题步骤： 我们编写了一个简单的脚本，通过不断发送不同的数字来猜测幸运数字，直到匹配上合约生成的值，从而成功通过挑战。
Eccs
分数：100
Eccs 题目涉及椭圆曲线离散对数问题（ECDLP）。合约实现了标准的椭圆曲线加法和乘法运算，目标是通过给定的曲线点来计算出乘法因子。
解题步骤： 我们假设 k 的范围比较小,试试暴力破解,当然也可以使用SageMath来求解
p = 738077334260605249
a = 1
b = 2
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
self.is_infinity = (x is None and y is None)
def is_at_infinity(self):
return self.is_infinity
def __eq__(self, other):
if self.is_at_infinity() and other.is_at_infinity():
return True
return self.x == other.x and self.y == other.y
def __str__(self):
if self.is_at_infinity():
return "Point at infinity"
return f"({self.x}, {self.y})"
O = Point(None, None)
def point_add(P, Q):
if P.is_at_infinity():
return Q
if Q.is_at_infinity():
return P
if P.x == Q.x and (P.y + Q.y) % p == 0:
return O
if P == Q:
lam = (3 * P.x * P.x + a) * pow(2 * P.y, -1, p) % p
else:
lam = (Q.y - P.y) * pow(Q.x - P.x, -1, p) % p
x_r = (lam * lam - P.x - Q.x) % p
y_r = (lam * (P.x - x_r) - P.y) % p
return Point(x_r, y_r)
def scalar_mult(k, P):
R = O
N = P
while k > 0:
if k % 2 == 1:
R = point_add(R, N)
N = point_add(N, N)
k = k // 2
return R
P1 = Point(627636259244800403, 317346088871876181)
P2 = Point(456557409365020317, 354112687690635257)
def brute_force_k(max_range):
for k in range(1, max_range):
R = scalar_mult(k, P1)
if R == P2:
print(f"k: {k}")
return k
if k % 100000 == 0:
print(f"try k = {k}")
print("not found k")
return None
max_range = 1000000
k = brute_force_k(max_range)
运行完等待一会儿得到结果 844279
Dex
分数：200
Dex 题目结合了 DeFi 交换中的舍入误差漏洞和 TON 区块链的一些独特特性。合约在交换过程中错误地对 out_amount 进行了向上取整，从而导致了可以利用的漏洞。
解题步骤： 我们首先利用舍入误差进行套利，但这还不足以完全解题。为了进一步降低合约余额，我们需要附加一笔足够大的 TON 余额，绕过提现时的余额检查，并在操作完成后收回这部分 TON，从而成功减少合约的余额，最终解题。
Puzzle
分数：200
Puzzle 题目是一个涉及多个变量的位操作题目，但合约中的位移操作并未正确生效，这使得我们可以通过调整变量值来满足合约的目标条件。
解题步骤： 我们可以编写一个深度优先搜索（DFS）算法，通过递归的方式尝试每个操作组合，找到使得变量之和等于目标值的方案。以下是实现代码：
class PuzzleSolver:
def __init__(self):
self.a = 100
self.b = 100
self.c = 100
self.d = 100
self.e = 100
self.f = 100
self.pc = 0
self.target = 638
self.max_steps = 13
self.solved = False
self.operations = []
def operate1(self):
self.a -= 3
self.d += 4
self.f -= 3
self.pc += 1
self.operations.append('operate1')
def operate2(self):
self.a += 3
self.c += 1
self.d //= 2
self.f *= 4
self.pc += 1
self.operations.append('operate2')
def operate3(self):
self.a *= 4
self.b -= 2
self.d += 3
self.pc += 1
self.operations.append('operate3')
def operate4(self):
self.a += 5
self.c -= 1
self.d += 4
self.f += 1
self.pc += 1
self.operations.append('operate4')
def operate5(self):
self.a -= 4
self.c += 2
self.d -= 5
self.f += 3
self.pc += 1
self.operations.append('operate5')
def operate6(self):
self.a *= 2
self.b += 6
self.c *= 8
self.e += 4
self.pc += 1
self.operations.append('operate6')
def operate7(self):
self.a -= 1
self.b //= 8
self.c *= 4
self.d += 1
self.e -= 5
self.f += 2
self.pc += 1
self.operations.append('operate7')
def check_solution(self):
return (self.a + self.b + self.c + self.d + self.e + self.f == self.target) and (self.pc <= self.max_steps)
def dfs(self, depth=0):
if self.check_solution():
self.solved = True
print("Solution found with operations:", self.operations)
return
if depth == self.max_steps or self.solved:
return
# Try each operation recursively
backup = (self.a, self.b, self.c, self.d, self.e, self.f, self.pc, list(self.operations))
for operate in [self.operate1, self.operate2, self.operate3, self.operate4, self.operate5, self.operate6, self.operate7]:
operate()
self.dfs(depth + 1)
self.a, self.b, self.c, self.d, self.e, self.f, self.pc, self.operations = backup
solver = PuzzleSolver()
solver.dfs()
print("Solved:", solver.solved)
这段代码通过深度优先搜索尝试每个可能的操作组合，直到找到满足条件的解
MerkleAirdrop
分数：300
MerkleAirdrop 题目涉及使用默克尔树进行空投验证。合约的漏洞在于其 verify 函数使用了非标准的节点计算方法，这使得我们能够伪造有效的证明来绕过验证。
解题步骤：
观察合约init函数，其中merkleRoot的计算逻辑是从y0 = sha256('EQ...NM0'+'614')开始，利用nodes的三个整数（记为n0 n1 n2）依次迭代三轮
y_(i+1) = sha256(string(diff(y_i, n_i)))，取最后y3值。
再观察Claim消息处理逻辑，容易发现只要把y0替换成sha256(<recepient>+'10000')，用自定的nodes经过类似逻辑算出相同的merkleRoot即成功。
显然关键在于y3 = sha256(string(diff(y2, n2)))这步中diff(y2, n2)必须和init中计算的值一样，为此先算出参考值d，再选取<recepient>和n0 n1，算出y2的值后使n2 = (y2 > d) ? (y2 - d) : (y2 + d)即可。
Ecc
分数：300
Ecc 题目与 Eccs 类似，也涉及椭圆曲线的加法和乘法运算，但难度更高，需要解决两个点之间的离散对数问题。此题的关键在于理解曲线的斜率计算方法，并利用它来找到正确的乘法因子。
解题步骤： 尝试使用Baby-step Giant-step 算法进行暴力破解。
import math
# Prime modulus for the elliptic curve
p = 769908256801249
def invMod(x, p):
# Calculate modular inverse
return pow(x % p, -1, p)
def point_add(P, Q):
x1, y1 = P
x2, y2 = Q
if (x1 == 0 and y1 == 0):
return (x2 % p, y2 % p)
if (x2 == 0 and y2 == 0):
return (x1 % p, y1 % p)
if x1 == x2 and y1 == y2:
numerator = (3 * x1 * x2 + 4 * x1 + 1) % p
denominator = (y1 + y2) % p
if denominator == 0:
return (0, 0)
m = (numerator * invMod(denominator, p)) % p
else:
numerator = (y2 - y1) % p
denominator = (x2 - x1) % p
if denominator == 0:
return (0, 0)
m = (numerator * invMod(denominator, p)) % p
x3 = (m * m - x1 - x2 - 2) % p
y3 = (m * (x1 - x3) - y1) % p
return (x3 % p, y3 % p)
def point_neg(P):
# Negate a point
x, y = P
return (x % p, (-y) % p)
def point_sub(P, Q):
# Point subtraction P - Q
return point_add(P, point_neg(Q))
def scalar_mul(P, n):
# Scalar multiplication
R = (0, 0)
Q = P
while n > 0:
if n % 2 == 1:
R = point_add(R, Q)
Q = point_add(Q, Q)
n = n // 2
return R
def BSGS(P, Q, m):
# Baby-step Giant-step algorithm
print("Starting Baby-step Giant-step algorithm")
# Precompute Baby steps
baby_steps = {}
R = (0, 0)
print("Calculating Baby steps...")
for j in range(m):
if R not in baby_steps:
baby_steps[R] = j
R = point_add(R, P)
if j % (m // 10) == 0 and j > 0:
print(f"Baby steps progress: {j}/{m}")
# Calculate s = m * P
s = scalar_mul(P, m)
# Giant steps
print("Calculating Giant steps...")
R = Q
for i in range(m):
if R in baby_steps:
j = baby_steps[R]
k = i * m + j
print(f"Solution found: k = {k}")
return k
R = point_sub(R, s)
if i % (m // 10) == 0 and i > 0:
print(f"Giant steps progress: {i}/{m}")
print("No solution found. Please increase the value of m and try again.")
return None
# Given points
p1 = (232682398601200, 266866051136644)
p2 = (565954914175128, 196353530004690)
# Set the value of m, can be adjusted based on memory and time constraints
m = 2 ** 25 # Approximately 1,048,576
k = BSGS(p1, p2, m)
if k is not None:
print(f"Found k: {k}")
# Verify the result
check = scalar_mul(p1, k)
if check == p2:
print("Verification successful, the value of k is correct.")
else:
print("Verification failed, the value of k is incorrect.")
else:
print("Unable to find the value of k. Please try increasing the value of m.")
Found k: 45514416202853
Curve
分数：200
Curve 题目涉及一个数学难题，即在给定的曲线上解决离散对数问题。该曲线的行为在合约中定义，重点是理解点加法的实现和如何通过点的关系来求解离散对数。
解题步骤：
观察合约add函数的实现，化简后发现它定义的点运算满足（模 $p$ 下）
$$x_{P_{1}+P_2}=x_{P_1}+x_{P_2}-x_{P_0}$$
选取基点 $G$ 显然有
$$x_{k\cdot G}=k\cdot x_G-(k-1)\cdot x_{P_0}$$
即
$$k=(x_{k\cdot G}-x_{P_0})(x_G-x_{P_0})^{-1}$$
代入zero.x、p1.x、p2.x和p解出k即可。