PwnCollege - RE - Optimizing for Space

Posted on In Views: Disqus:

Optimizing for Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// ...
int main(int argc, char **argv, char **envp)
{
    struct cimg cimg = { 0 };
    int won = 1;

    if (argc > 1)
    {
        if (strcmp(argv[1]+strlen(argv[1])-5, ".cimg"))
        {
            printf("ERROR: Invalid file extension!");
            exit(-1);
        }
        dup2(open(argv[1], O_RDONLY), 0);
    }

    read_exact(0, &cimg.header, sizeof(cimg.header), "ERROR: Failed to read header!", -1);

    if (cimg.header.magic_number != 1198345851)
    {
        puts("ERROR: Invalid magic number!");
        exit(-1);
    }

    if (won) win();

        case 55369:
            handle_55369(&cimg);
            break;
        case 52965:
            handle_52965(&cimg);
            break;
        default:
            fprintf(stderr, "ERROR: invalid directive_code %ux\n", directive_code);
            exit(-1);
        }
    }
    display(&cimg, NULL);

    if (cimg.num_pixels != sizeof(desired_output)/sizeof(term_pixel_t))
    {
        won = 0;
    }
    for (int i = 0; i < cimg.num_pixels && i < sizeof(desired_output)/sizeof(term_pixel_t); i++)
    {
        if (cimg.framebuffer[i].str.c != ((term_pixel_t*)&desired_output)[i].str.c)
        {
            won = 0;
        }
        if (
            cimg.framebuffer[i].str.c != ' ' &&
            cimg.framebuffer[i].str.c != '\n' &&
            memcmp(cimg.framebuffer[i].data, ((term_pixel_t*)&desired_output)[i].data, sizeof(term_pixel_t))
        )
        {
            won = 0;
        }
    }

    if (total_data > 1337) won = 0;

    if (won) win();
}

notice

1
2
3
4
5
6
if (cimg.framebuffer[i].str.c != ' ' &&
    cimg.framebuffer[i].str.c != '\n' &&
    memcmp(cimg.framebuffer[i].data, ((term_pixel_t*)&desired_output)[i].data, sizeof(term_pixel_t)))
{
    won = 0;
}

desired_output 中当前位置的字符是一个空格时触发短路不会去执行 memcmp 对比 4 字节的 RGB 数据。

  1. handle_55369 (全屏覆盖指令) pass
1
2
0x004016ff      movzx ebp, byte [rdi + 6]  ; 直接读取全局 width
0x00401703      movzx edx, byte [rdi + 7]  ; 直接读取全局 height

直接用全局的宽和高，要求一次性塞入整张图片的像素流。

  1. handle_52965 (局部区块覆盖指令)
1
2
3
4
5
0x004018a8      call sym.read_exact ; 读 base_x
0x004018c4      call sym.read_exact ; 读 base_y
0x004018e0      call sym.read_exact ; 读 width
0x004018fc      call sym.read_exact ; 读 height
0x00401945      call sym.read_exact ; 读 w * h * 4 个字节的 RGB 数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
       ;-- handle_52965:
       0x0040186c      f30f1efa       endbr64
       0x00401870      4157           push r15
       0x00401872      4183c8ff       or r8d, 0xffffffff          ; -1
       0x00401876      ba01000000     mov edx, 1
       0x0040187b      488d0df108..   lea rcx, str.ERROR:_Failed_to_read_base_x_    ; 0x402173 ; "ERROR: Failed to read &base_x!"
       0x00401882      4156           push r14
       0x00401884      4155           push r13
       0x00401886      4154           push r12
       0x00401888      4989fc         mov r12, rdi
       0x0040188b      31ff           xor edi, edi
       0x0040188d      55             push rbp
       0x0040188e      53             push rbx
       0x0040188f      4883ec38       sub rsp, 0x38
       0x00401893      64488b0425..   mov rax, qword fs:[0x28]
       0x0040189c      4889442428     mov qword [rsp + 0x28], rax
       0x004018a1      31c0           xor eax, eax
       0x004018a3      488d74240d     lea rsi, [rsp + 0xd]
       0x004018a8      e8defdffff     call sym.read_exact         ;[1]
       0x004018ad      4183c8ff       or r8d, 0xffffffff          ; -1
       0x004018b1      31ff           xor edi, edi
       0x004018b3      488d74240e     lea rsi, [rsp + 0xe]
       0x004018b8      488d0dd308..   lea rcx, str.ERROR:_Failed_to_read_base_y_    ; 0x402192 ; "ERROR: Failed to read &base_y!"
       0x004018bf      ba01000000     mov edx, 1
       0x004018c4      e8c2fdffff     call sym.read_exact         ;[1]
       0x004018c9      4183c8ff       or r8d, 0xffffffff          ; -1
       0x004018cd      31ff           xor edi, edi
       0x004018cf      488d74240b     lea rsi, [rsp + 0xb]
       0x004018d4      488d0dd608..   lea rcx, str.ERROR:_Failed_to_read_width_    ; 0x4021b1 ; "ERROR: Failed to read &width!"
       0x004018db      ba01000000     mov edx, 1
       0x004018e0      e8a6fdffff     call sym.read_exact         ;[1]
       0x004018e5      31ff           xor edi, edi
       0x004018e7      4183c8ff       or r8d, 0xffffffff          ; -1
       0x004018eb      ba01000000     mov edx, 1
       0x004018f0      488d74240c     lea rsi, [rsp + 0xc]
       0x004018f5      488d0dd308..   lea rcx, str.ERROR:_Failed_to_read_height_    ; 0x4021cf ; "ERROR: Failed to read &height!"
       0x004018fc      e88afdffff     call sym.read_exact         ;[1]
       0x00401901      0fb65c240b     movzx ebx, byte [rsp + 0xb]
       0x00401906      0fb654240c     movzx edx, byte [rsp + 0xc]
       0x0040190b      0fafda         imul ebx, edx
       0x0040190e      4863db         movsxd rbx, ebx
       0x00401911      48c1e302       shl rbx, 2
       0x00401915      4889df         mov rdi, rbx
       0x00401918      e8e3f8ffff     call sym.imp.malloc         ;[2]
       0x0040191d      4885c0         test rax, rax
   ┌─< 0x00401920      750e           jne 0x401930
   │   0x00401922      488d3daa07..   lea rdi, str.ERROR:_Failed_to_allocate_memory_for_the_image_data_    ; 0x4020d3 ; "ERROR: Failed to allocate memory for the image data!"
   │   0x00401929      e842f8ffff     call sym.imp.puts           ;[3]
  ┌──< 0x0040192e      eb58           jmp 0x401988
  │└─> 0x00401930      89da           mov edx, ebx
  │    0x00401932      4889c6         mov rsi, rax
  │    0x00401935      4183c8ff       or r8d, 0xffffffff          ; -1
  │    0x00401939      31ff           xor edi, edi
  │    0x0040193b      488d0dc607..   lea rcx, str.ERROR:_Failed_to_read_data_    ; 0x402108 ; "ERROR: Failed to read data!"
  │    0x00401942      4889c5         mov rbp, rax
  │    0x00401945      e841fdffff     call sym.read_exact         ;[1]
  │    0x0040194a      0fb644240c     movzx eax, byte [rsp + 0xc]
  │    0x0040194f      0fb654240b     movzx edx, byte [rsp + 0xb]
  │    0x00401954      0fafd0         imul edx, eax
  │    0x00401957      31c0           xor eax, eax
  │┌─> 0x00401959      39c2           cmp edx, eax
 ┌───< 0x0040195b      7e33           jle 0x401990
 ││╎   0x0040195d      0fb64c8503     movzx ecx, byte [rbp + rax*4 + 3]
 ││╎   0x00401962      48ffc0         inc rax
 ││╎   0x00401965      8d71e0         lea esi, [rcx - 0x20]
 ││╎   0x00401968      4080fe5e       cmp sil, 0x5e               ; '^' ; 94
 ││└─< 0x0040196c      76eb           jbe 0x401959
 ││    0x0040196e      488b3debd1..   mov rdi, qword [obj.stderr]    ; obj.stderr__GLIBC_2.2.5
 ││                                                               ; [0x40eb60:8]=0
 ││    0x00401975      488d15a807..   lea rdx, str.ERROR:_Invalid_character_0x_x_in_the_image_data__n    ; str.ERROR:_Invalid_character_0x_x_in_the_image_data__n
 ││                                                               ; 0x402124 ; "ERROR: Invalid character 0x%x in the image data!\n"
 ││    0x0040197c      be01000000     mov esi, 1
 ││    0x00401981      31c0           xor eax, eax
 ││    0x00401983      e8c8f8ffff     call sym.imp.__fprintf_chk  ;[4]
 │└──> 0x00401988      83cfff         or edi, 0xffffffff          ; -1
 │     0x0040198b      e8b0f8ffff     call sym.imp.exit           ;[5]
 └───> 0x00401990      4531ed         xor r13d, r13d
       0x00401993      4c8d7c240f     lea r15, [rsp + 0xf]
   ┌─> 0x00401998      0fb644240c     movzx eax, byte [rsp + 0xc]
   ╎   0x0040199d      4439e8         cmp eax, r13d
  ┌──< 0x004019a0      0f8ea7000000   jle 0x401a4d
  │╎   0x004019a6      4531f6         xor r14d, r14d
 ┌───> 0x004019a9      0fb64c240b     movzx ecx, byte [rsp + 0xb]
 ╎│╎   0x004019ae      4439f1         cmp ecx, r14d
┌────< 0x004019b1      0f8e8e000000   jle 0x401a45
│╎│╎   0x004019b7      0fb644240d     movzx eax, byte [rsp + 0xd]
│╎│╎   0x004019bc      0fb65c240e     movzx ebx, byte [rsp + 0xe]
│╎│╎   0x004019c1      410fafcd       imul ecx, r13d
│╎│╎   0x004019c5      4c89ff         mov rdi, r15
│╎│╎   0x004019c8      410fb6742406   movzx esi, byte [r12 + 6]
│╎│╎   0x004019ce      4c8d058107..   lea r8, str.e_38_2__03d__03d__03dm_ce_0m    ; 0x402156
│╎│╎   0x004019d5      4401f0         add eax, r14d
│╎│╎   0x004019d8      4401eb         add ebx, r13d
│╎│╎   0x004019db      99             cdq
│╎│╎   0x004019dc      0fafde         imul ebx, esi
│╎│╎   0x004019df      4401f1         add ecx, r14d
│╎│╎   0x004019e2      41ffc6         inc r14d
│╎│╎   0x004019e5      f7fe           idiv esi
│╎│╎   0x004019e7      4863c9         movsxd rcx, ecx
│╎│╎   0x004019ea      be19000000     mov esi, 0x19               ; 25
│╎│╎   0x004019ef      488d448d00     lea rax, [rbp + rcx*4]
│╎│╎   0x004019f4      b919000000     mov ecx, 0x19               ; 25
│╎│╎   0x004019f9      01d3           add ebx, edx
│╎│╎   0x004019fb      52             push rdx
│╎│╎   0x004019fc      0fb65003       movzx edx, byte [rax + 3]
│╎│╎   0x00401a00      52             push rdx
│╎│╎   0x00401a01      0fb65002       movzx edx, byte [rax + 2]
│╎│╎   0x00401a05      52             push rdx
│╎│╎   0x00401a06      0fb65001       movzx edx, byte [rax + 1]
│╎│╎   0x00401a0a      52             push rdx
│╎│╎   0x00401a0b      440fb608       movzx r9d, byte [rax]
│╎│╎   0x00401a0f      ba01000000     mov edx, 1
│╎│╎   0x00401a14      31c0           xor eax, eax
│╎│╎   0x00401a16      e835f7ffff     call sym.imp.__snprintf_chk ;[6]
│╎│╎   0x00401a1b      89d8           mov eax, ebx
│╎│╎   0x00401a1d      31d2           xor edx, edx
│╎│╎   0x00401a1f      410f1007       movups xmm0, xmmword [r15]
│╎│╎   0x00401a23      41f774240c     div dword [r12 + 0xc]
│╎│╎   0x00401a28      4883c420       add rsp, 0x20
│╎│╎   0x00401a2c      486bd218       imul rdx, rdx, 0x18
│╎│╎   0x00401a30      4903542410     add rdx, qword [r12 + 0x10]
│╎│╎   0x00401a35      0f1102         movups xmmword [rdx], xmm0
│╎│╎   0x00401a38      498b4710       mov rax, qword [r15 + 0x10]
│╎│╎   0x00401a3c      48894210       mov qword [rdx + 0x10], rax
│└───< 0x00401a40      e964ffffff     jmp 0x4019a9
└────> 0x00401a45      41ffc5         inc r13d
  │└─< 0x00401a48      e94bffffff     jmp 0x401998
  └──> 0x00401a4d      488b442428     mov rax, qword [rsp + 0x28]
       0x00401a52      6448330425..   xor rax, qword fs:[0x28]
   ┌─< 0x00401a5b      7405           je 0x401a62
   │   0x00401a5d      e82ef7ffff     call sym.imp.__stack_chk_fail ;[7]
   └─> 0x00401a62      4883c438       add rsp, 0x38
  1. Overhead (指令头开销): * 指令代码：假设 2 bytes (比如 0xCEE5 对应 52965)
  • base_x: 1 byte
  • base_y: 1 byte
  • width: 1 byte
  • height: 1 byte
  • Total Overhead ≈ 6 bytes
  1. Payload (像素数据开销):
  • 每个像素 4 bytes (W × H × 4)

所以，一个区块的总字节数计算公式为：

Cost = 6 + 4 × W × H

假设有两个孤立的像素点，中间隔了 k 个空白（背景）像素。

  • 如果不合并（打两个补丁）： Cost = (6 + 4 × 1) × 2 = 20 bytes。
  • 如果合并成一个大矩形： Cost = 6 + 4 × (2 + k) = 14 + 4k bytes。

我们让 14 + 4k < 20，解得 k < 1.5。

只有当两个有效像素之间最多只隔了 1 个空白像素时，把它们框在一起。

带权重 Set Cover 算法：

  1. 提取前景： 遍历 desired_output，把所有非 ' ' 和非 '\n' 的像素坐标抓出来。
  2. 生成候选框： 找出所有能框住至少一个前景像素的矩形。
  3. 计算净收益 (Net Profit)： 对于每个候选矩形，它的存在意义是帮你省掉了“将这些前景像素单独画出来”的 Overhead。

Profit = (覆盖的前景像素数量 × 6) − (包含的空白像素数量 × 4) − 6

  1. 贪心选择： 每次选出 Profit 最高的矩形，将其加入 payload 列表，并从目标集合中剔除已覆盖的像素，直到所有前景像素都被覆盖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
import struct

from pwn import *

def extract_pixels_from_elf(binary_path, num_pixels):
    elf = ELF(binary_path, checksec=False)
    try:
        addr = elf.symbols["desired_output"]
    except KeyError:
        addr = 0x404020

    raw = elf.read(addr, num_pixels * 24)
    pixels = []
    for i in range(num_pixels):
        chunk = raw[i * 24 : (i + 1) * 24]
        try:
            r = int(chunk[7:10])
            g = int(chunk[11:14])
            b = int(chunk[15:18])
            c = chunk[19]
            pixels.append((r, g, b, c))
        except ValueError:
            pass
    return pixels


def build_payload():
    binary_path = "/challenge/cimg"
    num_pixels = 1824
    width = 76
    height = 24

    pixels = extract_pixels_from_elf(binary_path, num_pixels)
    if len(pixels) != num_pixels:
        log.error("Failed to extract full image.")
        return

    # 1. 提取所有前景像素
    fg_pixels = set()
    for y in range(height):
        for x in range(width):
            p = pixels[y * width + x]
            if p[3] not in (32, 10):  # 过滤空格和换行 32 -> 0x20, 10 -> 0x0a
                fg_pixels.add((x, y))

    log.info(f"Targeting {len(fg_pixels)} foreground pixels.")

    # 2. 生成所有有价值的候选框 (Candidate Rectangles)
    candidates = []
    for x1 in range(width):
        for y1 in range(height):
            for x2 in range(x1, width):
                for y2 in range(y1, height):
                    # 快速找出框内的前景像素
                    cov = {
                        (x, y)
                        for x in range(x1, x2 + 1)
                        for y in range(y1, y2 + 1)
                        if (x, y) in fg_pixels
                    }
                    if not cov:
                        continue

                    cost = 6 + 4 * (x2 - x1 + 1) * (y2 - y1 + 1)
                    # 核心过滤：如果平均成本 > 10 (即不如单独 1x1 划算)，直接抛弃
                    if cost <= 10 * len(cov):
                        candidates.append(
                            {
                                "rect": (x1, y1, x2 - x1 + 1, y2 - y1 + 1),
                                "cost": cost,
                                "cov": cov,
                            }
                        )

    # 3. 策略A: 基于性价比 (Cost / Covered) 的贪心算法
    uncovered_a = set(fg_pixels)
    blocks_a = []
    size_a = 12
    while uncovered_a:
        best_cand = None
        best_ratio = float("inf")
        for c in candidates:
            cov_now = c["cov"].intersection(uncovered_a)
            if not cov_now:
                continue
            ratio = c["cost"] / len(cov_now)
            if ratio < best_ratio or (
                ratio == best_ratio
                and len(cov_now)
                > (len(best_cand["cov"].intersection(uncovered_a)) if best_cand else 0)
            ):
                best_ratio = ratio
                best_cand = c

        assert best_cand is not None, "Failed to find best candidate"
        blocks_a.append(best_cand["rect"])
        uncovered_a -= best_cand["cov"]
        size_a += best_cand["cost"]

    # 4. 策略B: 基于绝对收益 (Profit) 的贪心算法 (作为 baseline 对照)
    uncovered_b = set(fg_pixels)
    blocks_b = []
    size_b = 12
    while uncovered_b:
        best_cand = None
        best_profit = -float("inf")
        for c in candidates:
            cov_now = c["cov"].intersection(uncovered_b)
            if not cov_now:
                continue
            profit = len(cov_now) * 10 - c["cost"]
            if profit > best_profit or (
                profit == best_profit
                and len(cov_now)
                > (len(best_cand["cov"].intersection(uncovered_b)) if best_cand else 0)
            ):
                best_profit = profit
                best_cand = c

        assert best_cand is not None, "Failed to find best candidate"
        blocks_b.append(best_cand["rect"])
        uncovered_b -= best_cand["cov"]
        size_b += best_cand["cost"]

    log.info(f"Strategy A (Ratio) estimated size: {size_a} bytes")
    log.info(f"Strategy B (Profit) estimated size: {size_b} bytes")

    best_blocks = blocks_a if size_a < size_b else blocks_b
    log.success(
        f"The minimal set of {len(best_blocks)} blocks."
    )

    # 5. 组装 Payload
    directives_payload = bytearray()
    SUB_BLOCK_OPCODE = 52965

    for x, y, w, h in best_blocks:
        directives_payload += struct.pack("<H", SUB_BLOCK_OPCODE)
        directives_payload += struct.pack("<BBBB", x, y, w, h)
        for dy in range(h):
            for dx in range(w):
                p = pixels[(y + dy) * width + x + dx]
                directives_payload += struct.pack("<BBBB", p[0], p[1], p[2], p[3])

    total_size = len(directives_payload) + 12

    if total_size > 1337:
        log.error(
            f"Still too bloated. Over by {total_size - 1337} bytes."
        )
        return

    magic = b"cIMG"
    version = 3
    file_header = struct.pack(
        "<4sHBBI", magic, version, width, height, len(best_blocks)
    )

    payload = file_header + directives_payload
    file_name = "payload.cimg"
    with open(file_name, "wb") as f:
        f.write(payload)

    log.success(f"Final size: {total_size} bytes.")
    p = process([binary_path, file_name])
    print(p.recvall().decode(errors="ignore"))

if __name__ == "__main__":
    build_payload()