2024MoveCTF

2024. 1. 28. 12:30

Checkin

    public entry fun get_flag(string: vector<u8>, ctx: &mut TxContext) {
        assert!(string == b"MoveBitCTF",ESTRING);
        event::emit(Flag {
            sender: tx_context::sender(ctx),
            flag: true,
        });
    }

Since get_flag is a entry function, we just call that fuction using sui-client.

sui client call \
--package 0xbef0fd782ca68ff089fba9c06ee4b6ceaf1b5aaaa8bae45e66fa25efd8a7fec4 \
--module checkin \
--function get_flag \
--args "MoveBitCTF" \
--gas-budget 100000000

dynamic_matrix_traversal

    fun up(m: u64, n: u64): u64 {
        let f: vector<vector<u64>> = vector::empty();
        let i: u64 = 0;
        while (i < m) {
            let row: vector<u64> = vector::empty();
            let j: u64 = 0;
            while (j < n) {
                if (j == 0 || i == 0) {
                    vector::push_back(&mut row, 1);
                } else {
                    let f1 = *vector::borrow(&f, i - 1);
                    let j1 = *vector::borrow(&row, j - 1);
                    let val = *vector::borrow(&f1, j) + j1;
                    vector::push_back(&mut row, val);
                };
                j = j + 1;
            };
            vector::push_back(&mut f, row);
            i = i + 1;
        };
        let fr = *vector::borrow(&f, m - 1);
        let result = *vector::borrow(&fr, n-1);
        result
    }

We have to find pairs of m and n such that up(m, n) is equal to 14365 and 2794155.

found_mn = []
def up(m, n):
    f = [[0 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if j == 0 or i == 0:
                f[i][j] = 1
            else:
                f[i][j] = f[i-1][j] + f[i][j-1]
    return f[m-1][n-1]

for m in range(1, 300):
    for n in range(1, 300):
        if len(found_mn) == 2:
            break
        if up(m, n) in [14365, 2794155]:
            found_mn.append((m, n))

print(found_mn)

subset

The subset problem is a well-known subject of crypto challenge. This problem could be solved by low-density attack. The subset1 and subset2 are easily solved through brute-force but subset3 isn't. So sage script is needed.

class HighDensityException(Exception):
    pass


class LOAttack:

    def __init__(self, array, target_sum, try_on_high_density=False):
        self.array = array
        self.n = len(self.array)
        self.target_sum = target_sum
        self.density = self._calc_density()
        self.try_on_high_density = try_on_high_density

    def _calc_density(self):
        return self.n / log(max(self.array), 2)

    def _check_ans(self, ans):
        calc_sum = sum(map(lambda x: x[0] * x[1], zip(self.array, ans)))
        return self.target_sum == calc_sum

    def solve(self):
        if self.density >= 0.6463 and not self.try_on_high_density:
            raise HighDensityException()

        # 1. Initialize Lattice
        L = Matrix(ZZ, self.n + 1, self.n + 1)
        N = ceil(self.n ^ 0.5 / 2)
        for i in range(self.n + 1):
            for j in range(self.n + 1):
                if j == self.n and i < self.n:
                    L[i, j] = N * self.array[i]
                elif j == self.n:
                    L[i, j] = N * self.target_sum
                elif i == j:
                    L[i, j] = 1
                else:
                    L[i, j] = 0

        # 2. LLL!
        B = L.LLL()

        # 3. Find answer
        for i in range(self.n + 1):
            if B[i, self.n] != 0:
                continue

            if all(-1 <= v <= 0 for v in B[i]):
                ans = [-B[i, j] for j in range(self.n)]
                if self._check_ans(ans):
                    return ans

        # Failed to find answer
        return None


class CJLOSSAttack:

    def __init__(self, array, target_sum, try_on_high_density=False):
        self.array = array
        self.n = len(self.array)
        self.target_sum = target_sum
        self.density = self._calc_density()
        self.try_on_high_density = try_on_high_density

    def _calc_density(self):
        return self.n / log(max(self.array), 2)

    def _check_ans(self, ans):
        calc_sum = sum(map(lambda x: x[0] * x[1], zip(self.array, ans)))
        return self.target_sum == calc_sum

    def solve(self):
        if self.density >= 0.9408 and not self.try_on_high_density:
            raise HighDensityException()

        # 1. Initialize Lattice
        L = Matrix(ZZ, self.n + 1, self.n + 1)
        N = ceil(self.n ^ 0.5 / 2)
        for i in range(self.n + 1):
            for j in range(self.n + 1):
                if j == self.n and i < self.n:
                    L[i, j] = 2 * N * self.array[i]
                elif j == self.n:
                    L[i, j] = 2 * N * self.target_sum
                elif i == j:
                    L[i, j] = 2
                elif i == self.n:
                    L[i, j] = 1
                else:
                    L[i, j] = 0

        # 2. LLL!
        B = L.LLL()


        # 3. Find answer
        for i in range(self.n + 1):
            if B[i, self.n] != 0:
                continue

            if all(v == -1 or v == 1 for v in B[i][:self.n]):
                ans = [ (-B[i, j] + 1) // 2 for j in range(self.n)]
                print(ans)
                if self._check_ans(ans):
                    return ans

        # Failed to find answer
        return None


# Example
if __name__ == "__main__":
    from sage.misc.prandom import randint
    import random

    arr = [730983191275949878802706287425, 738747747182330870358722868390, 680758618870742741205069880873, 736839950200009681117675478653, 821817898783913524938769447793, 1062662929594640521216588473346, 804078432654564652353003934418, 987354119502628442223858924307, 974121064863569224403070119631, 766517359152261667697388282513, 1115664590742545309936719501477, 1254953696369781959586392455121, 708965201854329468418120106125, 803407590419087414384275360152, 680994772249007776444211943134, 1209641410992728376967530103489, 1022807828605992586908433214193, 708760513774702586605766399361, 1146510154260900723919247238072, 1071639493717448858831225830703, 704595551001390485227577881300, 666267842956106233584633761922, 916484600070887410197321230180, 869547011380359879465486127051, 1146284238922586539801525899580, 960791406315307372223215677265, 846714517434965788941098273736, 943109174072029103168835446476, 1186748483275224241752870865835, 810729587696497173434925395865, 1081140748486010470135469081647, 1117896979087650487375387404086, 815335940196924955981808193550, 980088874723074134145795909695, 1040350471929604504671667297293, 694306413856033832104987821225, 1100701148915109260220219397362, 861206885233154419043148976517, 876554683816312162465230697586, 1076923686440478606439365136720, 1107602068170190810465822909560, 1100902219684950305811682891430, 1009332208289062882998661101012, 967609782575367058780528699819, 847083579140405861838133952519, 960959937086001625649028920079, 705904760596273528708773247739, 988488072940508411593301577206, 855813607361058850034718734435, 923433147009426548286155351544, 927267999331166226154541562801, 833421857490492247367663980146, 913726313126985248790906682414, 1152739002690744639089937932044, 758241923243582267541395815418, 826183630101084916296521382931, 871183653161711616458012031543, 1118876419859306653014740242503, 925209067093127804911661688602, 796047972746266882548343051358, 1105317347573296959936900839504, 1032520332923337088078820581073, 790503191621237284611596729403, 1093888060891270134787133219999, 1129244151204837429536515955111, 736340764546413369555890340882, 844331877762673816004189096610, 1216403448409604941009786692773, 1026707098397380044704009977063, 1162146257113640418035057534747, 1239108677717284719224289951413, 1179642728157883101738427519029, 1121726694197132350252978011382, 1166236995314127503915531123371, 1237380820841327126465021125310, 928563984604088646801945637827, 969172329973162874760566309613, 916791337778690807774047076043, 1187392146940862931565053344747, 1041354841046252194695344517944]
    target_sum = 9639405868465735216305592265916

    for _ in range(1000):
        new_arr = []
        cnt = 0
        out = []
        for a in arr:
            if random.random() < 0.1:
                out.append(cnt)
                cnt += 1
                continue
            else:
                cnt += 1
                new_arr.append(a)
        attack = CJLOSSAttack(new_arr, target_sum).solve()
        if attack is not None and sum(attack) == 10:
            print(new_arr)
            print(attack)
            print(out)

module My::my {
    use sui::event;
    use sui::tx_context;
    use std::vector;
    use subset::subset_sum;

    struct Flag has copy, drop {
        user: address
    }

    struct Status has store, drop {
        status1: bool,
        status2: bool,
        status3: bool,
        user: address
    }

    const SUBSET1: vector<u256> = vector<u256>[1, 2, 3, 4, 5];
    const SUBSET1_k: u256 = 3;
    const SUBSET1_SUM: u256 = 10;

    const SUBSET2: vector<u256> = vector<u256>[657114161599166, 910496114410022, 688072175280628, 979125688929861, 785338725553848, 887159728265050, 622841641193103, 725154659875148, 740423950361799, 1112663190822550, 922195312967936, 1042436852643560, 794233930466363, 1005209504277475, 1095553790921575, 1100234031975913, 1097338706315892, 685173186787942, 931084447948631, 1025208692464347, 823246835986875, 640705587553065, 1067772094848338, 608307547370178, 860527574463312, 745522896700102, 1107646656429468, 575719789023353, 1008988042757401, 563072788255737, 882855688862943, 974319745991702, 1004427379286462, 904504413493231, 1083652042079152, 1053694822809090, 702717128907262, 881540236795119, 992204188883575, 890965906483327];
    const SUBSET2_k: u256 = 5;
    const SUBSET2_SUM: u256 = 4178919802453692;

    const SUBSET3: vector<u256> = vector<u256>[730983191275949878802706287425, 738747747182330870358722868390, 680758618870742741205069880873, 736839950200009681117675478653, 821817898783913524938769447793, 1062662929594640521216588473346, 804078432654564652353003934418, 987354119502628442223858924307, 974121064863569224403070119631, 766517359152261667697388282513, 1115664590742545309936719501477, 1254953696369781959586392455121, 708965201854329468418120106125, 803407590419087414384275360152, 680994772249007776444211943134, 1209641410992728376967530103489, 1022807828605992586908433214193, 708760513774702586605766399361, 1146510154260900723919247238072, 1071639493717448858831225830703, 704595551001390485227577881300, 666267842956106233584633761922, 916484600070887410197321230180, 869547011380359879465486127051, 1146284238922586539801525899580, 960791406315307372223215677265, 846714517434965788941098273736, 943109174072029103168835446476, 1186748483275224241752870865835, 810729587696497173434925395865, 1081140748486010470135469081647, 1117896979087650487375387404086, 815335940196924955981808193550, 980088874723074134145795909695, 1040350471929604504671667297293, 694306413856033832104987821225, 1100701148915109260220219397362, 861206885233154419043148976517, 876554683816312162465230697586, 1076923686440478606439365136720, 1107602068170190810465822909560, 1100902219684950305811682891430, 1009332208289062882998661101012, 967609782575367058780528699819, 847083579140405861838133952519, 960959937086001625649028920079, 705904760596273528708773247739, 988488072940508411593301577206, 855813607361058850034718734435, 923433147009426548286155351544, 927267999331166226154541562801, 833421857490492247367663980146, 913726313126985248790906682414, 1152739002690744639089937932044, 758241923243582267541395815418, 826183630101084916296521382931, 871183653161711616458012031543, 1118876419859306653014740242503, 925209067093127804911661688602, 796047972746266882548343051358, 1105317347573296959936900839504, 1032520332923337088078820581073, 790503191621237284611596729403, 1093888060891270134787133219999, 1129244151204837429536515955111, 736340764546413369555890340882, 844331877762673816004189096610, 1216403448409604941009786692773, 1026707098397380044704009977063, 1162146257113640418035057534747, 1239108677717284719224289951413, 1179642728157883101738427519029, 1121726694197132350252978011382, 1166236995314127503915531123371, 1237380820841327126465021125310, 928563984604088646801945637827, 969172329973162874760566309613, 916791337778690807774047076043, 1187392146940862931565053344747, 1041354841046252194695344517944];
    const SUBSET3_k: u256 = 10;
    const SUBSET3_SUM: u256 = 9639405868465735216305592265916;

    public entry fun attack(ctx: &mut tx_context::TxContext) {
        let status = subset_sum::get_status(ctx);
        let sol1 = vector<u256>[0,1,1,0,1];
        let sol2 = 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, 0];
        let sol3 = 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_subset1(sol1, &mut status);
        subset_sum::solve_subset2(sol2, &mut status);
        subset_sum::solve_subset3(sol3, &mut status);
        subset_sum::get_flag(&status, ctx);
    }

    public fun get_status(ctx: &mut tx_context::TxContext): Status {
        Status {
            status1: false,
            status2: false,
            status3: false,
            user: tx_context::sender(ctx)
        }
    }


    public fun get_flag(status: &Status, ctx: &mut tx_context::TxContext) {
        let user = tx_context::sender(ctx);
        assert!(status.user == user, 0);
        assert!(status.status1 && status.status2 && status.status3, 0);
        event::emit(Flag { user: user });
    }

}

swap

If a user keep swapping alternately from A to B and from B to A, the user will have more coin than the vault.

vault_a = 100
vault_b = 100

my_a = 10
my_b = 10

# swap

for _ in range(2):
    delta = min(int(my_a * vault_b / vault_a), vault_b)
    vault_a += my_a
    vault_b -= delta
    my_a = 0
    my_b += delta

    delta = min(int(my_b * vault_a / vault_b), vault_a)
    vault_b += my_b
    vault_a -= delta
    my_b = 0
    my_a += delta

delta = int(my_a * vault_b / vault_a)
vault_a += my_a
vault_b -= delta
my_a = 0
my_b += delta

delta = int(45 * vault_a / vault_b)
vault_b += 45
vault_a -= delta
my_b -= 45
my_a += delta

print(my_a)
print(my_b)
print(vault_a)
print(vault_b)

module My::my {
    use sui::coin::{Self, Coin, TreasuryCap};
    use sui::tx_context::{Self, TxContext};
    use sui::transfer;
    use sui::object::{Self, UID};
    use std::option;
    use swap::vault::{Self, Vault};
    use swap::ctfa::{Self, MintA};
    use swap::ctfb::{Self, MintB};

    public entry fun attack1<A,B>(capa: MintA<A>, capb: MintB<B>, ctx: &mut TxContext) {
        vault::initialize<A,B>(capa, capb ,ctx);
    }



    public entry fun attack2<A,B>(vault: &mut Vault<A,B>, coina:Coin<A>, coinb:Coin<B>, ctx: &mut TxContext) {
        let coin_b = vault::swap_a_to_b<A,B>(vault, coina, ctx);
        coin::join<B>(&mut coin_b, coinb);
        let coin_a = vault::swap_b_to_a<A,B>(vault, coin_b, ctx);
        let coin_b = vault::swap_a_to_b<A,B>(vault, coin_a, ctx);
        let coin_a = vault::swap_b_to_a<A,B>(vault, coin_b, ctx);
        let coin_b = vault::swap_a_to_b<A,B>(vault, coin_a, ctx);
        let coin_bb = coin::split(&mut coin_b, 45, ctx);
        let coin_a = vault::swap_b_to_a<A,B>(vault, coin_bb, ctx);

        let (a, b, r) = vault::flash<A,B>(vault, 90, true, ctx);

        vault::get_flag<A,B>(vault, ctx);

        vault::repay_flash<A,B>(vault, a, b, r);

        transfer::public_transfer(coin_a, tx_context::sender(ctx));
        transfer::public_transfer(coin_b, tx_context::sender(ctx));
    }

}

otterhub

There are three private repos in otterhub.
In particular, it is necessary to focus on the Matryoshka repo, and it has three commits.

161,28,235,11,6,0,0,0,7,1,0,2,3,2,5,5,7,1,7,8,21,8,29,32,6,61,178,1,12,239,1,17,0,0,0,1,0,0,0,0,9,101,110,99,114,121,112,116,111,114,10,115,116,111,114,101,95,98,97,98,121,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,10,2,86,85,10,13,6,28,54,125,70,69,108,29,59,13,71,80,83,84,87,108,40,70,6,95,89,95,49,18,125,70,69,108,29,59,78,4,80,83,84,87,108,40,70,69,28,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,0,1,0,0,0,3,6,3,0,0,0,0,0,0,0,1,2,0
161,28,235,11,6,0,0,0,7,1,0,2,3,2,5,5,7,26,7,33,21,8,54,32,6,86,89,12,175,1,141,1,0,0,0,1,0,0,0,0,10,10,2,10,2,10,2,7,10,2,10,2,10,2,6,10,2,7,10,2,3,10,2,1,2,9,101,110,99,114,121,112,116,111,114,10,115,116,111,114,101,95,98,97,98,121,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,0,1,0,0,1,54,6,1,0,0,0,0,0,0,0,12,8,64,2,0,0,0,0,0,0,0,0,12,9,7,0,12,0,10,8,14,0,65,2,35,4,36,5,12,13,9,12,3,7,0,12,1,7,0,12,2,11,3,14,1,10,8,66,2,20,14,2,10,8,6,1,0,0,0,0,0,0,0,23,66,2,20,29,68,2,11,8,6,1,0,0,0,0,0,0,0,22,12,8,5,4,13,9,12,7,7,0,12,5,14,5,12,6,7,0,12,4,11,7,11,6,14,4,65,2,6,1,0,0,0,0,0,0,0,23,66,2,20,68,2,2,0
161,28,235,11,6,0,0,0,7,1,0,2,3,2,5,5,7,1,7,8,21,8,29,32,6,61,178,1,12,239,1,17,0,0,0,1,0,0,0,0,9,101,110,99,114,121,112,116,111,114,10,115,116,111,114,101,95,98,97,98,121,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,89,95,49,13,39,64,2,104,29,59,13,71,80,83,84,87,108,40,70,6,95,89,95,49,18,12,2,11,1,7,11,26,29,59,13,71,80,83,84,87,78,125,0,1,0,0,0,3,6,3,0,0,0,0,0,0,0,1,2,0

I noticed the above data are move bytecodes because 161, 28, 235, 11 is a move bytecode signature.

// Move bytecode v6
module 0.encryptor {


public store_baby() {
B0:
        0: LdU64(3)
        1: Pop
        2: Ret
}

Constants [
        0 => vector<u8>: "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" // interpreted as UTF8 string
        1 => vector<u8>: "
GPSTWl(F_Y_1}FEl;NPSTWl(FEXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" // interpreted as UTF8 string    
]
}

// Move bytecode v6
module 0.encryptor {


public store_baby() {
L0:     loc0: vector<u8>
L1:     loc1: vector<u8>
L2:     loc2: vector<u8>
L3:     loc3: &mut vector<u8>
L4:     loc4: vector<u8>
L5:     loc5: vector<u8>
L6:     loc6: &vector<u8>
L7:     loc7: &mut vector<u8>
L8:     loc8: u64
L9:     loc9: vector<u8>
B0:
        0: LdU64(1)
        1: StLoc[8](loc8: u64)
        2: VecPack(2, 0)
        3: StLoc[9](loc9: vector<u8>)
B1:
        4: LdConst[0](Vector(U8): 55585858..)
        5: StLoc[0](loc0: vector<u8>)
        6: CopyLoc[8](loc8: u64)
        7: ImmBorrowLoc[0](loc0: vector<u8>)
        8: VecLen(2)
        9: Lt
        10: BrFalse(36)
B2:
        11: Branch(12)
B3:
        12: MutBorrowLoc[9](loc9: vector<u8>)
        13: StLoc[3](loc3: &mut vector<u8>)
        14: LdConst[0](Vector(U8): 55585858..)
        15: StLoc[1](loc1: vector<u8>)
        16: LdConst[0](Vector(U8): 55585858..)
        17: StLoc[2](loc2: vector<u8>)
        18: MoveLoc[3](loc3: &mut vector<u8>)
        19: ImmBorrowLoc[1](loc1: vector<u8>)
        20: CopyLoc[8](loc8: u64)
        21: VecImmBorrow(2)
        22: ReadRef
        23: ImmBorrowLoc[2](loc2: vector<u8>)
        24: CopyLoc[8](loc8: u64)
        25: LdU64(1)
        26: Sub
        27: VecImmBorrow(2)
        28: ReadRef
        29: Xor
        30: VecPushBack(2)
        31: MoveLoc[8](loc8: u64)
        32: LdU64(1)
        33: Add
        34: StLoc[8](loc8: u64)
        35: Branch(4)
B4:
        36: MutBorrowLoc[9](loc9: vector<u8>)
        37: StLoc[7](loc7: &mut vector<u8>)
        38: LdConst[0](Vector(U8): 55585858..)
        39: StLoc[5](loc5: vector<u8>)
        40: ImmBorrowLoc[5](loc5: vector<u8>)
        41: StLoc[6](loc6: &vector<u8>)
        42: LdConst[0](Vector(U8): 55585858..)
        43: StLoc[4](loc4: vector<u8>)
        44: MoveLoc[7](loc7: &mut vector<u8>)
        45: MoveLoc[6](loc6: &vector<u8>)
        46: ImmBorrowLoc[4](loc4: vector<u8>)
        47: VecLen(2)
        48: LdU64(1)
        49: Sub
        50: VecImmBorrow(2)
        51: ReadRef
        52: VecPushBack(2)
        53: Ret
}

Constants [
        0 => vector<u8>: "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" // interpreted as UTF8 string
]
}

// Move bytecode v6
module 0.encryptor {


public store_baby() {
B0:
        0: LdU64(3)
        1: Pop
        2: Ret
}

Constants [
        0 => vector<u8>: "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" // interpreted as UTF8 string
GPSTWN}" // interpreted as UTF8 stringXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXY_1
]
}

The result of reversing follows as

module my::my {

    use std::vector;

    const FLAG: vector<u8> = vector<u8>[1];

    public fun store_baby() {
        let loc8 = 1;
        let loc9 = vector<u8>[];

        let loc0 = FLAG;
        while (loc8 < vector::length<u8>(&loc0)) {
            let loc3 = loc9;
            let loc1 = FLAG;
            let loc2 = FLAG;

            vector::push_back(&mut loc3, *vector::borrow<u8>(&loc1, loc8) ^ *vector::borrow<u8>(&loc2, loc8 - 1));
            loc8 = loc8 + 1;
        };

        let loc7 = loc9;
        let loc5 = FLAG;
        let loc6 = loc5;
        let loc4 = FLAG;

        vector::push_back(&mut loc7, *vector::borrow<u8>(&loc6, vector::length<u8>(&loc4)-1));

    }
}

I cons strings that are not redacted in the constants of the bytecodes.

data =  [161,28,235,11,6,0,0,0,7,1,0,2,3,2,5,5,7,1,7,8,21,8,29,32,6,61,178,1,12,239,1,17,0,0,0,1,0,0,0,0,9,101,110,99,114,121,112,116,111,114,10,115,116,111,114,101,95,98,97,98,121,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,10,2,86,85,10,13,6,28,54,125,70,69,108,29,59,13,71,80,83,84,87,108,40,70,6,95,89,95,49,18,125,70,69,108,29,59,78,4,80,83,84,87,108,40,70,69,28,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,0,1,0,0,0,3,6,3,0,0,0,0,0,0,0,1,2,0]
data2 = [161,28,235,11,6,0,0,0,7,1,0,2,3,2,5,5,7,26,7,33,21,8,54,32,6,86,89,12,175,1,141,1,0,0,0,1,0,0,0,0,10,10,2,10,2,10,2,7,10,2,10,2,10,2,6,10,2,7,10,2,3,10,2,1,2,9,101,110,99,114,121,112,116,111,114,10,115,116,111,114,101,95,98,97,98,121,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,0,1,0,0,1,54,6,1,0,0,0,0,0,0,0,12,8,64,2,0,0,0,0,0,0,0,0,12,9,7,0,12,0,10,8,14,0,65,2,35,4,36,5,12,13,9,12,3,7,0,12,1,7,0,12,2,11,3,14,1,10,8,66,2,20,14,2,10,8,6,1,0,0,0,0,0,0,0,23,66,2,20,29,68,2,11,8,6,1,0,0,0,0,0,0,0,22,12,8,5,4,13,9,12,7,7,0,12,5,14,5,12,6,7,0,12,4,11,7,11,6,14,4,65,2,6,1,0,0,0,0,0,0,0,23,66,2,20,68,2,2,0]
data3 = [161,28,235,11,6,0,0,0,7,1,0,2,3,2,5,5,7,1,7,8,21,8,29,32,6,61,178,1,12,239,1,17,0,0,0,1,0,0,0,0,9,101,110,99,114,121,112,116,111,114,10,115,116,111,114,101,95,98,97,98,121,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,10,2,86,85,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,88,89,95,49,13,39,64,2,104,29,59,13,71,80,83,84,87,108,40,70,6,95,89,95,49,18,12,2,11,1,7,11,26,29,59,13,71,80,83,84,87,78,125,0,1,0,0,0,3,6,3,0,0,0,0,0,0,0,1,2,0]


a = []
a = data[0x60:0xe5] + data3[0xe5:0x110]

ans = [a[-1]]

for i in range(1, len(a)):
    ans.append(a[-i] ^ ans[i - 1])
print(bytes(ans)[::-1])

zk2

pragma circom 2.1.0;

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;

    var e2=1;
    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * e2;
        e2 = e2+e2;
    }

    lc1 === in;
}

template LessThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;

    component n2b = Num2Bits(n+1);

    n2b.in <== in[0]+ (1<<n) - in[1];

    out <== 1-n2b.out[n];
}

template GreaterThan(n) {
    signal input in[2];
    signal output out;

    component lt = LessThan(n);

    lt.in[0] <== in[1];
    lt.in[1] <== in[0];
    lt.out ==> out;
}

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;
}


component main = ZK2();

According to https://docs.circom.io/circom-language/basic-operators/

Field Elements
A field element is a value in the domain of Z/pZ, where p is the prime number set by default to

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617.

As such, field elements are operated in arithmetic modulo p.

The circom language is parametric to this number, and it can be changed without affecting the rest of the language (using GLOBAL_FIELD_P).

The challenge requries us to solve 168700*x_square + delta_square === 1 + 168696 * x_square * delta_square
We can find a solution using sage script.

p=21888242871839275222246405745257275088548364400416034343698204186575808495617
F=GF(p)
x=F(255)
xs=x^2
ds=4*x^2/(168696*x^2-1)+1
d=ds.sqrt()
assert 168700*xs+ds==1+168696*xs*ds
print(d)

kitchen

This challenge consists of two stages: cook and recook. In order to retrieve the flag we need to solve them both.
To solve the cook stage we had to construct some structs and pass them over to the cook() function.

let olive_oil = Olive_oil{
    amount: 0x15a5,
};

let olive_oil2 = Olive_oil{
    amount: 0xb8a6,
};

let olive_oil3 = Olive_oil{
    amount: 0xf8c9,
};

let olive_oil4 = Olive_oil{
    amount: 0x46bb,
};

let yeast = Yeast{
    amount: 0x00bd,
};

let yeast2 = Yeast{
    amount: 0x9d99,
};

let yeast3 = Yeast{
    amount: 0x7eb7,
};

let flour = Flour{
    amount: 0x8ad7,
};

let flour2 = Flour{
    amount: 0x84fa,
};

let flour3 = Flour{
    amount: 0xf2b8,
};

let salt = Salt{
    amount: 0xc5f1,
};

let salt2 = Salt{
    amount: 0x22e1,
};

To solve the recook stage we had to create a dummy function which calls the recook() function with dummy parameters and the add a debug message to leak the value for the out parameter.

#[test]
fun dump_code_test(){
    let status = Status {
        status1: false,
        status2: false,
        user: @0x0,
    };
    let out: vector<u8> = vector::empty<u8>();
    recook(out, &mut status);
}

The code is [debug] 0x06d9b954eb6892f7c5eca184d00400bd81fc9d997eb705c7dc7acc198fb1966d8a03018bc5f1ecc6
After that we only had to call the get_flag() function.

easygame

We need to provide an array of numbers that concatenated to the list [1, 2, 4, 5, 1, 3, 6, 7, 1, 5] and ran through the rob() function returns the value 22. To discover the numbers, I ran a simple brute-force.

#[test]
fun test_rob() {
    let houses = vector::empty<u64>();
    vector::push_back(&mut houses, 1);
    vector::push_back(&mut houses, 2);
    vector::push_back(&mut houses, 4);
    vector::push_back(&mut houses, 5);
    vector::push_back(&mut houses, 1);
    vector::push_back(&mut houses, 3);
    vector::push_back(&mut houses, 6);
    vector::push_back(&mut houses, 7);

    debug::print(&rob(&houses));

    let i = 1;
    let found = 1;
    while(i < 6) {
        let j = 0;
        while(j < 6) {
            vector::push_back(&mut houses, i);
            vector::push_back(&mut houses, j);
            let amount_robbed = rob(&houses);
            debug::print(&i);
            debug::print(&j);
            debug::print(&amount_robbed);
            if(amount_robbed == 22){
                debug::print(&houses);
                found = 1;
                break;
            };
            let _a = vector::pop_back(&mut houses);
            let _b = vector::pop_back(&mut houses);
            j = j + 1;
        };
        if(found == 1){
            break;
        };
        i = i + 1;
    };
}

Running the test will print:

[debug] [ 1, 2, 4, 5, 1, 3, 6, 7, 1, 5 ]

zk1

In order to solve this challenge we had to provide a proof that we know two numbers, both greater than one, whose product equals the value 58567186824402957966382507182680956225095467533943200425018625513920465170743. We could easily determin the factors using: http://factordb.com/index.php?query=58567186824402957966382507182680956225095467533943200425018625513920465170743
Then, following the sui zk tutorial, we were able to generate a proof using the following script:

use ark_bn254::Bn254;
use ark_circom::CircomBuilder;
use ark_circom::CircomConfig;
use ark_serialize::{CanonicalSerialize, CanonicalDeserialize};
use ark_groth16::{Groth16, ProvingKey};
use ark_snark::SNARK;
use rand;
use std::fs::File;

fn main() {
    let cfg = CircomConfig::<Bn254>::new("zk1.wasm", "zk1.r1cs").unwrap();

    let mut builder = CircomBuilder::new(cfg);
    builder.push_input("a", 223960747878782291107008135733958922391 as u128);
    builder.push_input("b", 261506479948451388126301943086863538273 as u128);

    let circom = builder.setup();

    let mut rng = rand::thread_rng();
    let mut file = File::open("key.bin").unwrap();
    let params = ProvingKey::<Bn254>::deserialize_compressed(&mut file).unwrap();

    let circom = builder.build().unwrap();

    let inputs = circom.get_public_inputs().unwrap();

    let proof = Groth16::<Bn254>::prove(&params, circom, &mut rng).unwrap();

    let pvk = Groth16::<Bn254>::process_vk(&params.vk).unwrap();
    let verified = Groth16::<Bn254>::verify_with_processed_vk(&pvk, &inputs, &proof).unwrap();
    println!("{:?}", verified);
    println!("{:?}", inputs);
    println!("{:?}", proof);

    let mut proof_inputs_bytes = Vec::new();
    inputs.serialize_compressed(&mut proof_inputs_bytes).unwrap();

    let mut proof_points_bytes = Vec::new();
    proof.a.serialize_compressed(&mut proof_points_bytes).unwrap();
    proof.b.serialize_compressed(&mut proof_points_bytes).unwrap();
    proof.c.serialize_compressed(&mut proof_points_bytes).unwrap();

    println!("{:#?}", proof_inputs_bytes);
    println!("{:#?}", proof_points_bytes);
}

'writeups' 카테고리의 다른 글

DiceCTF 2024 Quals - floordrop(blockchain) (0)	2024.02.05
RealWorldCTF 2024 - blockchain(safebridge) (0)	2024.01.28
2023 X-mas CTF (web3 - alpha hunter) (0)	2023.12.31
0CTF/TCTF 2023 - misc(ctar) (0)	2023.12.11
GlacierCTF 2023 - smartcontract (0)	2023.11.26

gss1