CakeCTF 2023 : Cake Puzzle

roaris commented 1 month ago

https://alpacahack.com/challenges/cake-puzzle

roaris commented 1 month ago

$ file chal
chal: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=4c2b97895e9493536557f72e973e5ed194a49854, for GNU/Linux 3.2.0, not stripped

$ ./chal
> test
> testtest
> ^C

roaris commented 1 month ago

main関数 q関数の戻り値が0になるとwin関数が呼ばれる win関数 flag.txtの内容を出力している

roaris commented 1 month ago

main関数で、入力文字列はrbp-0x70に格納されている movzx eax, [rbp+var70]; movsx eax, al;を見ると、入力文字列として期待しているのは1バイトであると分かる入力文字列はe関数に渡される

roaris commented 1 month ago

e関数の内容はGhidraで見た方が分かりやすい入力文字列として期待しているのはU, R, D, Lのいずれかである

void e(char param_1)

{
  int local_10;
  int local_c;

  s(&local_c,&local_10);
  if (param_1 == 'U') {
    if (local_c != 0) {
      f(M + ((long)local_c * 4 + (long)local_10) * 4,
        M + ((long)(local_c + -1) * 4 + (long)local_10) * 4);
    }
  }
  else if (param_1 < 'V') {
    if (param_1 == 'R') {
      if (local_10 != 3) {
        f(M + ((long)local_c * 4 + (long)local_10) * 4,
          M + ((long)local_c * 4 + (long)(local_10 + 1)) * 4);
      }
    }
    else if (param_1 < 'S') {
      if (param_1 == 'D') {
        if (local_c != 3) {
          f(M + ((long)local_c * 4 + (long)local_10) * 4,
            M + ((long)(local_c + 1) * 4 + (long)local_10) * 4);
        }
      }
      else if ((param_1 == 'L') && (local_10 != 0)) {
        f(M + ((long)local_c * 4 + (long)local_10) * 4,
          M + ((long)local_c * 4 + (long)(local_10 + -1)) * 4);
      }
    }
  }
  return;
}

s関数引数で与えたメモリアドレスに0~3の値を格納している

void s(int *param_1,int *param_2)

{
  int local_10;
  int local_c;

  for (local_c = 0; local_c < 4; local_c = local_c + 1) {
    for (local_10 = 0; local_10 < 4; local_10 = local_10 + 1) {
      if (*(int *)(M + ((long)local_c * 4 + (long)local_10) * 4) == 0) {
        *param_1 = local_c;
        *param_2 = local_10;
      }
    }
  }
  return;
}

f関数メモリアドレスに格納された値を交換している

void f(uint *param_1,uint *param_2)

{
  *param_1 = *param_1 ^ *param_2;
  *param_2 = *param_2 ^ *param_1;
  *param_1 = *param_1 ^ *param_2;
  return;
}

q関数メモリアドレスAに格納された値 <= メモリアドレスBに格納された値なら、1が返る

undefined8 q(void)

{
  int local_10;
  int local_c;

  local_c = 0;
  do {
    if (2 < local_c) {
      return 0;
    }
    for (local_10 = 0; local_10 < 3; local_10 = local_10 + 1) {
      if (*(int *)(M + ((long)local_c * 4 + (long)(local_10 + 1)) * 4) <=
          *(int *)(M + ((long)local_c * 4 + (long)local_10) * 4)) {
        return 1;
      }
      if (*(int *)(M + ((long)(local_c + 1) * 4 + (long)local_10) * 4) <=
          *(int *)(M + ((long)local_c * 4 + (long)local_10) * 4)) {
        return 1;
      }
    }
    local_c = local_c + 1;
  } while( true );
}

roaris commented 1 month ago

Mを起点として、どのような値が格納されているか確認する Hex Viewで、4バイト整数に変換すると良い

プログラムにすると、以下のようになる

M = [
    0x445856DB,
    0x4C230304,
    0x0022449F,
    0x671A96B7,
    0x6C5644F7,
    0x7FF46287,
    0x6EE9C829,
    0x5CDA2E72,
    0x00000000,
    0x698E88C9,
    0x33E65A4F,
    0x50CC5C54,
    0x1349831A,
    0x53C88F74,
    0x25858AB9,
    0x72F976D8
]

roaris commented 1 month ago

入力文字列がU, R, D, Lなので、Mを4x4で考えると見通しが良いことに気付いた

M = [
    [0x445856DB, 0x4C230304, 0x0022449F, 0x671A96B7],
    [0x6C5644F7, 0x7FF46287, 0x6EE9C829, 0x5CDA2E72],
    [0x00000000, 0x698E88C9, 0x33E65A4F, 0x50CC5C54],
    [0x1349831A, 0x53C88F74, 0x25858AB9, 0x72F976D8],
]

s関数は、Mの中の0の位置を見つける関数で、e関数は0を上下左右に移動させる関数である gdbでも確認した

$ gdb -q chal
Reading symbols from chal...
(No debugging symbols found in chal)
gdb-peda$ b q
Breakpoint 1 at 0x11b9
gdb-peda$ r
Starting program: /home/roaris/alpacahack/cake-puzzle/chal
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Warning: 'set logging off', an alias for the command 'set logging enabled', is deprecated.
Use 'set logging enabled off'.

Warning: 'set logging on', an alias for the command 'set logging enabled', is deprecated.
Use 'set logging enabled on'.
[----------------------------------registers-----------------------------------]
RAX: 0x0
RBX: 0x7fffffffe078 --> 0x7fffffffe319 ("/home/roaris/alpacahack/cake-puzzle/chal")
RCX: 0x7ffff7e9e2c7 (<__GI_alarm+7>:    cmp    rax,0xfffffffffffff001)
RDX: 0x7fffffffe088 --> 0x7fffffffe342 ("HOSTTYPE=x86_64")
RSI: 0x7fffffffe078 --> 0x7fffffffe319 ("/home/roaris/alpacahack/cake-puzzle/chal")
RDI: 0x3e8
RBP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RSP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RIP: 0x5555555551b9 (<q+4>:     mov    DWORD PTR [rbp-0x4],0x0)
R8 : 0x5555555556b0 (<__libc_csu_fini>: ret)
R9 : 0x7ffff7fcfb10 (<_dl_fini>:        push   r15)
R10: 0x7ffff7de55a8 --> 0x10001200006809
R11: 0x206
R12: 0x0
R13: 0x7fffffffe088 --> 0x7fffffffe342 ("HOSTTYPE=x86_64")
R14: 0x0
R15: 0x7ffff7ffd000 --> 0x7ffff7ffe2d0 --> 0x555555554000 --> 0x10102464c457f
EFLAGS: 0x217 (CARRY PARITY ADJUST zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x5555555551b0 <frame_dummy>:        jmp    0x555555555130 <register_tm_clones>
   0x5555555551b5 <q>:  push   rbp
   0x5555555551b6 <q+1>:        mov    rbp,rsp
=> 0x5555555551b9 <q+4>:        mov    DWORD PTR [rbp-0x4],0x0
   0x5555555551c0 <q+11>:       jmp    0x555555555290 <q+219>
   0x5555555551c5 <q+16>:       mov    DWORD PTR [rbp-0x8],0x0
   0x5555555551cc <q+23>:       jmp    0x555555555282 <q+205>
   0x5555555551d1 <q+28>:       mov    eax,DWORD PTR [rbp-0x8]
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
0008| 0x7fffffffdee8 --> 0x5555555555e6 (<main+28>:     test   eax,eax)
0016| 0x7fffffffdef0 --> 0x1000000
0024| 0x7fffffffdef8 --> 0x40 ('@')
0032| 0x7fffffffdf00 --> 0x0
0040| 0x7fffffffdf08 --> 0x0
0048| 0x7fffffffdf10 --> 0x0
0056| 0x7fffffffdf18 --> 0x0
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x00005555555551b9 in q ()
gdb-peda$ x/16wx 0x555555558080
0x555555558080 <M>:     0x445856db      0x4c230304      0x0022449f      0x671a96b7
0x555555558090 <M+16>:  0x6c5644f7      0x7ff46287      0x6ee9c829      0x5cda2e72
0x5555555580a0 <M+32>:  0x00000000      0x698e88c9      0x33e65a4f      0x50cc5c54
0x5555555580b0 <M+48>:  0x1349831a      0x53c88f74      0x25858ab9      0x72f976d8
gdb-peda$ c
Continuing.
> U
[----------------------------------registers-----------------------------------]
RAX: 0x0
RBX: 0x7fffffffe078 --> 0x7fffffffe319 ("/home/roaris/alpacahack/cake-puzzle/chal")
RCX: 0x20 (' ')
RDX: 0x6c5644f7
RSI: 0x555555558090 --> 0x7ff4628700000000
RDI: 0x5555555580a0 --> 0x698e88c96c5644f7
RBP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RSP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RIP: 0x5555555551b9 (<q+4>:     mov    DWORD PTR [rbp-0x4],0x0)
R8 : 0x1
R9 : 0x7ffff7f9eaa0 --> 0xfbad2288
R10: 0x0
R11: 0x7ffff7f9f580 --> 0x7ffff7f9b820 --> 0x7ffff7f625f7 --> 0x5a5400544d470043 ('C')
R12: 0x0
R13: 0x7fffffffe088 --> 0x7fffffffe342 ("HOSTTYPE=x86_64")
R14: 0x0
R15: 0x7ffff7ffd000 --> 0x7ffff7ffe2d0 --> 0x555555554000 --> 0x10102464c457f
EFLAGS: 0x202 (carry parity adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x5555555551b0 <frame_dummy>:        jmp    0x555555555130 <register_tm_clones>
   0x5555555551b5 <q>:  push   rbp
   0x5555555551b6 <q+1>:        mov    rbp,rsp
=> 0x5555555551b9 <q+4>:        mov    DWORD PTR [rbp-0x4],0x0
   0x5555555551c0 <q+11>:       jmp    0x555555555290 <q+219>
   0x5555555551c5 <q+16>:       mov    DWORD PTR [rbp-0x8],0x0
   0x5555555551cc <q+23>:       jmp    0x555555555282 <q+205>
   0x5555555551d1 <q+28>:       mov    eax,DWORD PTR [rbp-0x8]
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
0008| 0x7fffffffdee8 --> 0x5555555555e6 (<main+28>:     test   eax,eax)
0016| 0x7fffffffdef0 --> 0x1000055
0024| 0x7fffffffdef8 --> 0x40 ('@')
0032| 0x7fffffffdf00 --> 0x0
0040| 0x7fffffffdf08 --> 0x0
0048| 0x7fffffffdf10 --> 0x0
0056| 0x7fffffffdf18 --> 0x0
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x00005555555551b9 in q ()
gdb-peda$ x/16wx 0x555555558080
0x555555558080 <M>:     0x445856db      0x4c230304      0x0022449f      0x671a96b7
0x555555558090 <M+16>:  0x00000000      0x7ff46287      0x6ee9c829      0x5cda2e72
0x5555555580a0 <M+32>:  0x6c5644f7      0x698e88c9      0x33e65a4f      0x50cc5c54
0x5555555580b0 <M+48>:  0x1349831a      0x53c88f74      0x25858ab9      0x72f976d8
gdb-peda$ c
Continuing.
> R
[----------------------------------registers-----------------------------------]
RAX: 0x0
RBX: 0x7fffffffe078 --> 0x7fffffffe319 ("/home/roaris/alpacahack/cake-puzzle/chal")
RCX: 0x10
RDX: 0x7ff46287
RSI: 0x555555558094 --> 0x6ee9c82900000000
RDI: 0x555555558090 --> 0x7ff46287
RBP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RSP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RIP: 0x5555555551b9 (<q+4>:     mov    DWORD PTR [rbp-0x4],0x0)
R8 : 0x2
R9 : 0x7ffff7f9eaa0 --> 0xfbad2288
R10: 0x0
R11: 0x7ffff7f9f580 --> 0x7ffff7f9b820 --> 0x7ffff7f625f7 --> 0x5a5400544d470043 ('C')
R12: 0x0
R13: 0x7fffffffe088 --> 0x7fffffffe342 ("HOSTTYPE=x86_64")
R14: 0x0
R15: 0x7ffff7ffd000 --> 0x7ffff7ffe2d0 --> 0x555555554000 --> 0x10102464c457f
EFLAGS: 0x206 (carry PARITY adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x5555555551b0 <frame_dummy>:        jmp    0x555555555130 <register_tm_clones>
   0x5555555551b5 <q>:  push   rbp
   0x5555555551b6 <q+1>:        mov    rbp,rsp
=> 0x5555555551b9 <q+4>:        mov    DWORD PTR [rbp-0x4],0x0
   0x5555555551c0 <q+11>:       jmp    0x555555555290 <q+219>
   0x5555555551c5 <q+16>:       mov    DWORD PTR [rbp-0x8],0x0
   0x5555555551cc <q+23>:       jmp    0x555555555282 <q+205>
   0x5555555551d1 <q+28>:       mov    eax,DWORD PTR [rbp-0x8]
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
0008| 0x7fffffffdee8 --> 0x5555555555e6 (<main+28>:     test   eax,eax)
0016| 0x7fffffffdef0 --> 0x1000052
0024| 0x7fffffffdef8 --> 0x40 ('@')
0032| 0x7fffffffdf00 --> 0x0
0040| 0x7fffffffdf08 --> 0x0
0048| 0x7fffffffdf10 --> 0x0
0056| 0x7fffffffdf18 --> 0x0
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x00005555555551b9 in q ()
gdb-peda$ x/16wx 0x555555558080
0x555555558080 <M>:     0x445856db      0x4c230304      0x0022449f      0x671a96b7
0x555555558090 <M+16>:  0x7ff46287      0x00000000      0x6ee9c829      0x5cda2e72
0x5555555580a0 <M+32>:  0x6c5644f7      0x698e88c9      0x33e65a4f      0x50cc5c54
0x5555555580b0 <M+48>:  0x1349831a      0x53c88f74      0x25858ab9      0x72f976d8
gdb-peda$ c
Continuing.
> R
[----------------------------------registers-----------------------------------]
RAX: 0x0
RBX: 0x7fffffffe078 --> 0x7fffffffe319 ("/home/roaris/alpacahack/cake-puzzle/chal")
RCX: 0x14
RDX: 0x6ee9c829
RSI: 0x555555558098 --> 0x5cda2e7200000000
RDI: 0x555555558094 --> 0x6ee9c829
RBP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RSP: 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
RIP: 0x5555555551b9 (<q+4>:     mov    DWORD PTR [rbp-0x4],0x0)
R8 : 0x2
R9 : 0x7ffff7f9eaa0 --> 0xfbad2288
R10: 0x0
R11: 0x7ffff7f9f580 --> 0x7ffff7f9b820 --> 0x7ffff7f625f7 --> 0x5a5400544d470043 ('C')
R12: 0x0
R13: 0x7fffffffe088 --> 0x7fffffffe342 ("HOSTTYPE=x86_64")
R14: 0x0
R15: 0x7ffff7ffd000 --> 0x7ffff7ffe2d0 --> 0x555555554000 --> 0x10102464c457f
EFLAGS: 0x202 (carry parity adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x5555555551b0 <frame_dummy>:        jmp    0x555555555130 <register_tm_clones>
   0x5555555551b5 <q>:  push   rbp
   0x5555555551b6 <q+1>:        mov    rbp,rsp
=> 0x5555555551b9 <q+4>:        mov    DWORD PTR [rbp-0x4],0x0
   0x5555555551c0 <q+11>:       jmp    0x555555555290 <q+219>
   0x5555555551c5 <q+16>:       mov    DWORD PTR [rbp-0x8],0x0
   0x5555555551cc <q+23>:       jmp    0x555555555282 <q+205>
   0x5555555551d1 <q+28>:       mov    eax,DWORD PTR [rbp-0x8]
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffdee0 --> 0x7fffffffdf60 --> 0x1
0008| 0x7fffffffdee8 --> 0x5555555555e6 (<main+28>:     test   eax,eax)
0016| 0x7fffffffdef0 --> 0x1000052
0024| 0x7fffffffdef8 --> 0x40 ('@')
0032| 0x7fffffffdf00 --> 0x0
0040| 0x7fffffffdf08 --> 0x0
0048| 0x7fffffffdf10 --> 0x0
0056| 0x7fffffffdf18 --> 0x0
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x00005555555551b9 in q ()
gdb-peda$ x/16wx 0x555555558080
0x555555558080 <M>:     0x445856db      0x4c230304      0x0022449f      0x671a96b7
0x555555558090 <M+16>:  0x7ff46287      0x6ee9c829      0x00000000      0x5cda2e72
0x5555555580a0 <M+32>:  0x6c5644f7      0x698e88c9      0x33e65a4f      0x50cc5c54
0x5555555580b0 <M+48>:  0x1349831a      0x53c88f74      0x25858ab9      0x72f976d8

q関数では、各行、各列毎にソートされているかを確認している

roaris commented 1 month ago

制約の緩い15パズルを解くという問題 https://github.com/MilanPecov/15-Puzzle-Solvers を使ったしかし、このライブラリの終了状態は[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]であるなので、ライブラリを改造する必要がある

solver.pyで、解が見つかるか判定している部分をコメントアウト

class PuzzleSolver:
    """
    Executes different puzzle solver strategies (algorithms) and prints the solution and the performance
    """

    def __init__(self, strategy):
        self._strategy = strategy
        self.puzzle_validation_service = PuzzleValidationService()

    def run(self):
        # if not self.puzzle_validation_service.is_solvable(self._strategy.start):
        #     raise RuntimeError('This puzzle is not solvable')
        self._strategy.solve_puzzle()

astar.pyで、終了状態に到達したかの判定部分を変更

def is_end(self, node):
        for i in range(3):
            for j in range(3):
                if node[i][j] > node[i + 1][j]:
                    return False

                if node[i][j] > node[i][j + 1]:
                    return False

        return True

def solve_puzzle(self) -> List[Puzzle]:
    initial_heuristic = getattr(self.puzzle_heuristic_service, self.heuristic_function)(self.start.position)
    queue = [[initial_heuristic, self.start]]
    expanded = set()
    num_expanded_nodes = 0

    while queue and not self.should_stop:
        current_index = min(range(len(queue)), key=lambda i: queue[i][0])
        current_path = queue.pop(current_index)
        current_heuristic, current_node = current_path[0], current_path[-1]

        # if current_node.position == self.end_position:
        if self.is_end(current_node.position):

以下のコードで解いた

from fifteen_puzzle_solvers.domain import Puzzle
from fifteen_puzzle_solvers.services.algorithms import AStar
from fifteen_puzzle_solvers.services.solver import PuzzleSolver

M = [
    [0x445856DB, 0x4C230304, 0x0022449F, 0x671A96B7],
    [0x6C5644F7, 0x7FF46287, 0x6EE9C829, 0x5CDA2E72],
    [0x00000000, 0x698E88C9, 0x33E65A4F, 0x50CC5C54],
    [0x1349831A, 0x53C88F74, 0x25858AB9, 0x72F976D8],
]

l = []

for i in range(4):
    for j in range(4):
        l.append(M[i][j])

l.sort()
idx = {}

for i in range(16):
    idx[l[i]] = i

for i in range(4):
    for j in range(4):
        M[i][j] = idx[M[i][j]]

puzzle = Puzzle(M)
puzzle_solver = PuzzleSolver(AStar(puzzle))
puzzle_solver.run()
path = puzzle_solver.get_solution()
ope = ''

for i in range(len(path) - 1):
    x1, y1 = path[i].find_empty_tile()
    x2, y2 = path[i + 1].find_empty_tile()

    if x1 - 1 == x2:
        ope += 'U'
    elif x1 + 1 == x2:
        ope += 'D'
    elif y1 - 1 == y2:
        ope += 'L'
    else:
        ope += 'R'

from pwn import *

is_local = False

if is_local:
    io = process('./chal')
else:
    io = remote('34.170.146.252', 64930)

for o in ope:
    io.recvuntil(b'> ')
    io.sendline(bytes(o, 'ascii'))

print(io.recvall())

roaris / ctf-log

CakeCTF 2023 : Cake Puzzle #77