TON CTF 2024 Writeup
This article is a write-up of the TON CTF 2024 competition that I participated in with Leo. The TON CTF was sponsored by the TON Foundation and organized by Tonbit and TONX Studio. The competition encompassed multiple challenges related to the TON blockchain, all written in the Tact language. Tact is a high-level language that compiles to Func, which is then compiled to Fift, ultimately generating bytecode suitable for the TON virtual machine. This competition allowed me to gain a deeper understanding of the uniqueness of the TON ecosystem and its programming model.
This was my first time participating in a CTF-related competition, and the entire experience was both thrilling and unforgettable. The competition lasted only one day and consisted of 8 challenges. My teammate Leo and I completed this challenge together, ultimately achieving fourth place. You can view detailed descriptions of each challenge in this repository: TonCTF-Challenges.
Airdrop
Score: 100 The objective of the Airdrop challenge was to deplete the contract’s initial supply of 30,000 tokens. The contract allowed users to claim 1 token, but the vulnerability appeared in the implementation of the deposit and withdrawal functions. Because the contract didn’t strictly check if the input amount was positive, we could exploit negative values to manipulate the contract’s balance.
Solution Steps: We first constructed a message with a negative amount and sent it to the contract, thereby bypassing the contract’s balance check and reducing the contract’s supply, ultimately achieving the goal. The core code is as follows:
airdrop.send(provider.sender(),{ value: toNano("0.1") },{ $$type: "UserStake", amount: -30000n })
This code’s purpose is to construct a message containing a negative amount, calling the UserStake message. By passing a negative amount into the contract, it causes the contract to erroneously decrease its total supply.
Random
Score: 100 The Random challenge required us to guess a lucky number. If guessed correctly, the contract would set a flag to 1, indicating successful completion of the challenge. The contract used the current time and the user’s address hash to generate a random number, but due to the small range of the hash generation (0-99), we were able to solve this problem using a brute-force guessing method.
Solution Steps: We wrote a simple script that continuously sent different numbers to guess the lucky number until it matched the value generated by the contract, thus successfully passing the challenge.
Eccs
Score: 100 The Eccs challenge involved the Elliptic Curve Discrete Logarithm Problem (ECDLP). The contract implemented standard elliptic curve addition and multiplication operations, with the goal of calculating the multiplication factor given a specific curve point.
Solution Steps: We assumed that the range of k was relatively small and tried a brute-force approach. Alternatively, we could have used SageMath to solve it.
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)
After running, we wait a while and get the result 844279
Dex
Score: 200
The Dex challenge combined rounding error vulnerabilities in DeFi exchanges with some unique features of the TON blockchain. The contract incorrectly rounded up the out_amount during the exchange process, leading to an exploitable vulnerability.
Solution Steps: We first exploited the rounding error for arbitrage, but this alone was not enough to fully solve the challenge. To further reduce the contract balance, we needed to attach a sufficiently large TON balance to bypass the balance check during withdrawal, and then recover this part of TON after the operation, thereby successfully reducing the contract’s balance and ultimately solving the challenge.
Puzzle
Score: 200 The Puzzle challenge was a bit manipulation problem involving multiple variables, but the bitwise operations in the contract were not functioning correctly. This allowed us to solve the problem by adjusting the variable values to meet the contract’s target conditions.
Solution Steps: We can write a Depth-First Search (DFS) algorithm that recursively tries each combination of operations to find a solution where the sum of the variables equals the target value. Here’s the implementation code:
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)
This code uses depth-first search to try every possible combination of operations until it finds a solution that satisfies the conditions.
MerkleAirdrop
Score: 300
The MerkleAirdrop challenge involved using a Merkle tree for airdrop verification. The vulnerability in the contract was in its verify function, which used a non-standard method for node calculation. This allowed us to forge valid proofs to bypass the verification.
Solution Steps:
Observing the contract’s init function, the merkleRoot calculation logic starts from y0 = sha256('EQ...NM0'+'614'), then iterates three rounds using three integers from nodes (denoted as n0, n1, n2):
y_(i+1) = sha256(string(diff(y_i, n_i))), taking the final y3 value.
Further observing the Claim message handling logic, it’s easy to see that we can succeed by replacing y0 with sha256(<recipient>+'10000') and using custom nodes to calculate the same merkleRoot through similar logic.
Clearly, the key lies in the step y3 = sha256(string(diff(y2, n2))) where diff(y2, n2) must be the same as the value calculated in init. To achieve this, first calculate the reference value d, then choose <recipient> and n0, n1, calculate the value of y2, and make n2 = (y2 > d) ? (y2 - d) : (y2 + d).
Ecc
Score: 300 The Ecc challenge was similar to Eccs, also involving elliptic curve addition and multiplication operations, but with higher difficulty, requiring solving the discrete logarithm problem between two points. The key to this challenge was understanding the slope calculation method of the curve and using it to find the correct multiplication factor.
Solution Steps: Attempt to use the Baby-step Giant-step algorithm for brute-force cracking.
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
Score: 200 The Curve challenge involved a mathematical problem, specifically solving the discrete logarithm problem on a given curve. The curve’s behavior was defined in the contract, with the focus on understanding the implementation of point addition and how to solve the discrete logarithm through the relationship between points.
Solution Steps:
Observing the implementation of the contract’s add function, after simplification, we find that the defined point operation satisfies (under modulo $p$)
$$x_{P_{1}+P_2}=x_{P_1}+x_{P_2}-x_{P_0}$$
Selecting the base point $G$, we obviously have $$x_{k\cdot G}=k\cdot x_G-(k-1)\cdot x_{P_0}$$
That is, $$k=(x_{k\cdot G}-x_{P_0})(x_G-x_{P_0})^{-1}$$
Substitute zero.x, p1.x, p2.x, and p to solve for k.