주말에 많은 시간을 투자하지 않았다. 문제 다 훑고 스케쥴링 잘했으면 한두문제정도 더 풀 수 있었지 않았을까 하는 아쉬움이 남는다. 다음부터는 Niceness를 적절히 조절하자.

pain-plus-plus

deayzl님이 다 분석하시고, 쓰시던 코드에 붙어서 숟가락만 얹었다. (사실상 지분 Under 10%)
`std::_Rb_tree<char,std::pair<char const,int>,std::_Select1st<std::pair<char const,int>>,std::less,std::allocator<std::pair<char const,int>>>`를 사용해 Flag를 한 글자씩 비교한다.

(한 글자씩만 비교한다는 것) == (어디에 Breakpoint 걸어서 비교연산 따면 브포 가능) 이 대부분의 경우 성립한다. 이 문제의 경우
`std::_Rb_tree<char,std::pair<char const,int>,std::_Select1st<std::pair<char const,int>>,std::less,std::allocator<std::pair<char const,int>>>::_M_copy<false,std::_Rb_tree<char,std::pair<char const,int>,std::_Select1st<std::pair<char const,int>>,std::less,std::allocator<std::pair<char const,int>>>::_Alloc_node>()` 내부에서 비교를 진행하면 된다. 입력을 받은 char를 내부에서 RB Tree에 insert하기 위해 진행하는 비교이다. (미리 분석해주신 바에 따르면) `main_cold + 0x1C3` (`cmp dl, [rax + 0x20]`)에서 진행된다.

해당 지점에 Breakpoint를 걸고, 다음과 같이 `known + trial + '}'` 로 비교한다.

`trial`이 Flag의 string이 아닐 경우 RBtree를 Construction 하면서 `trial`이 (틀렸음을 검사하기 위한) 마지막 `$dl`이 되고, 틀린 답을 내놓고 Program terminate.
`trial`이 Flag의 string이 맞을 경우 '}'가 틀린 String이기에 마지막 `$dl`이 된다. (혹은 마지막 글자에서)

이를 바탕으로 gdbscript를 작성한다.

import gdb
import string

class PathBP(gdb.Breakpoint):
    def __init__(self, addr):
        super().__init__(addr)
        self.silent = True
        self.path = []

    def stop(self):
        char = int(gdb.newest_frame().read_register("rdx")) & 0xFF
        self.path.append(chr(char))
        return False


gdb.execute("file pain-plus-plus")

BP = PathBP("*0x5555555563f3")

known = ""

while True:
    for trial in string.digits + "_{" + string.ascii_letters:
        flag = known + trial + "}"
        BP.path.clear()
        gdb.execute(f"run <<< '{flag}' > /dev/null", to_string=True)

        if BP.path[-1] == "}":
            print(f"[!] Found {trial}")
            known += trial
            break
    else:
        print(known + "}")
        exit(0)

gdbscript가 돌아가는데 15분 내로 걸린다.

FLAG: `dice{would_you_like_to_try_the_windows_abi_next_time_685dfc4bc1a0}`

C++은 너무 이름이 길다. 템플릿과 싸우는 것은 길이가 짧기 힘든 듯 하다. 미리 분석을 다 끝내주신 deayzl님께 감사드립니다. 사실 gdbscript도 짜고 계셨는데 제 스크립트가 조금 더 빨리나와서 저는 한게 숟가락얹기밖에 없어요...

three

들어가기 앞서 생각의 흐름을 정리해보면 귀찮아서 Static analysis를 하지 않고 어떻게든 angr에 어거지로 얹을려고 했던 게 화근이었다.

~~게으른 청년.~~

결국 마지막에 static analysis로 복원된 코드를 (고통받으며) 해석했을 때 깔끔하게 떨어졌는데 그걸 진작에 안해서 시간을 많이 버린 것 같다.

ELF patching

문제의 로직은 처음에 그리 어려워 보이지 않았지만, ELF를 실행시키는 것 부터 고역이었다. 이런 안티디버깅 등등 ELF에 장난쳐놓은 것을 많이 접해 보지 못했었다. ELF에 장난쳐놨겠지! 하면서 `readelf ` 해서 무슨 섹션이 없어졌는지 살펴보려고 했다. 로딩을 해서 프로세스가 시작되고 어떤 System call이라도 불리면서 차근차근 따지기 위해 바로 `strace`를 찍어봤지만 아무것도 없었다.

갈피를 못잡다가 physicube선배님께서 답을 알려주셨다: 사실은 NixOS ELF였다. ELF를 읽고 해석할 인터프리터의 위치가 해당 NixOS는 좀 신기한(?) 경로에 박혀 있는데, 익히 일반적으로 Linux에서 사용하는 ELF interpreter (`ld-linux-x86-64.so`)의 시스템 경로와 다르기 때문에 프로그램이 말 그대로 "얹히지도 못하고" 죽어버렸던 것이다.

WSL에서 실행할 수 있게 패치해서 주셨다. `elfdiff`를 떠보면 다음과 같이 ELF interpreter 경로 `/lib64/ld-linux-x86-64.so.2` 로 Interpreter section을 덮은 것을 확인할 수 있다.

Patch 이후 실행이 된다.

Analysis

`main`을 Decompile했을 때 결과물은 다음과 같다.

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  _BYTE _0[256]; // [rsp+0h] [rbp+0h] BYREF
  __int128 vars100[2]; // [rsp+100h] [rbp+100h] BYREF
  char vars120; // [rsp+120h] [rbp+120h]
  char s[72]; // [rsp+130h] [rbp+130h] BYREF
  unsigned __int64 vars178; // [rsp+178h] [rbp+178h]

  vars178 = __readfsqword(0x28u);
  memset(_0, 0, sizeof(_0));
  __printf_chk(2LL, "flag: ", a3);
  fflush(stdout);
  vars120 = 0;
  memset(vars100, 0, sizeof(vars100));
  fgets(s, 64, stdin);
  if ( (unsigned int)__isoc99_sscanf(s, "dice{%32s%[}]", vars100, s) != 2 )
  {
    puts("invalid input");
    return 1LL;
  }
  if ( !(unsigned int)sub_401380(vars100, _0) )
  {
    puts("invalid characters");
    return 1LL;
  }
  if ( !(unsigned int)sub_401420(_0) )
  {
    puts("incorrect!");
    return 1LL;
  }
  puts("correct!");
  return 0LL;
}

32byte input을 포맷 안에 쏙 넣고, `sub_401380`이 검증 및 변환하는 것에 맞추어 `sub_401420`의 출력을 살펴보면 된다.

`sub_401380`

Decompile 결과는 다음과 같다. 편의를 위해 적절히 Typecasting 한 결과이다.

__int64 __fastcall sub_401380(char *src, int *dst)
{
  __int64 i; // rcx
  int v3; // edx
  int v4; // eax
  char v5; // al

  for ( i = 0LL; i != 32; ++i )
  {
    v5 = src[i];
    if ( !v5 )
      return 0LL;

    if ( (unsigned __int8)(v5 - 'a') <= 0x19u )
    {
      v3 = v5 - 'a';
    }
    else
    {
      if ( (unsigned __int8)(v5 - '0') > 9u )
        return 0LL;
      v3 = v5 - 22;
    }

    v4 = (dword_404020[i] + v3) % 36;
    dst[2 * i] = v4 / 6;
    dst[2 * i + 1] = v4 % 6;
  }
  return 1LL;
}

눈치가 빠르다면 `v3`이 `string.ascii_lowercase + string.digits` 에서 `v5` 의 index를 반환한다는 것을 알 수 있다. 이 값에 Offset을 더해 주고 (`dword_404020`), mod 36 값을 각각 `dst`에 (6으로 나눈 몫) 과 (6으로 나눈 나머지) 형태로 밀어 넣는다. Total length는 `32 * len([v4 / 6, v4 % 6]) * sizeof(int)` 으로 256byte의 array를 채운다.

`sub_401420`

이 부분을 해석하기 너무 귀찮아서 angr에 얹어서 시도했다. 코드는 다음과 같았으나, 해당 로직을 SMT Solver를 통해 돌리기 매우 어려워 보였는지 15분 남짓 돌아가다 Process Killed 당했다.

import angr
import claripy
import logging

logging.getLogger("angr").setLevel("INFO")
proj = angr.Project("./challenge2", auto_load_libs=False)

value_addr = 0x8000
value_answer = claripy.BVS(
    "value_answer", 8 * 4 * 32 * 2
)  # (32 chars for div, mod) * 4 byte/int * 8 bit/byte

init_state = proj.factory.call_state(
    0x401420,  # Calling logic
    value_addr,  # Somewhere store the value
    add_options={
        angr.options.ZERO_FILL_UNCONSTRAINED_REGISTERS,
        angr.options.ZERO_FILL_UNCONSTRAINED_MEMORY,
    },
)

init_state.memory.store(value_addr, value_answer)

for i in range(32 * 2):
    answer_int = init_state.mem[value_addr + 4 * i].int.resolved
    init_state.add_constraints(0 <= answer_int, answer_int < 6)

simgr = proj.factory.simgr(init_state)

simgr.explore(
    find=[0x40118D],  # `puts("correct")`
    avoid=[0x4015A0, 0x4011AB],  # [`xor eax, eax` before retn and `puts("incorrect")]
)

if len(simgr.found) != 0:
    found = simgr.found[0]
    print(found.solver.eval(value_answer, cast_to=bytes))

else:
    print("!No solution found!")

적당히 z3 얹으면 되겠지 + 아 분석 귀찮으니 angr로 슥 닦아야겠다! 라고 생각했지만 그리 호락호락하지 않았다. 결국 직접 하나하나 Static하게 보아야만 한다. Static하게 고통의 시간을 겪으면서 하나하나 해석한 결과이다. (Variable name & type casted)

_BOOL8 __fastcall sub_401420(int *mat)
{
  unsigned int R; // r15d
  unsigned int C; // ebp
  int v3; // eax
  int VisitCnt; // r8d
  int prev_dC; // r13d
  __int64 Prev_Group; // rbx
  int prev_dR; // r12d
  int Group; // eax
  int v9; // esi
  int v10; // ecx
  __int64 Value; // rax
  __int64 Left_Connect; // rsi
  __int64 Right_Connect; // rax
  int prev_VisitCnt; // [rsp+0h] [rbp-88h]
  int Continuous; // [rsp+4h] [rbp-84h]
  int Check[13]; // [rsp+10h] [rbp-78h] BYREF
  unsigned __int64 v18; // [rsp+48h] [rbp-40h]

  R = 0;
  C = 0;
  v18 = __readfsqword(0x28u);
  memset(Check, 0, sizeof(Check));
  v3 = sub_4012B0(0LL, 0LL);
  VisitCnt = 1;
  Continuous = 0;
  prev_dC = -1;
  Prev_Group = v3;
  prev_dR = 0;
  while ( 1 )
  {
    Value = mat[R + 8 * C];

    Left_Connect = Left[Value];
    Right_Connect = Right[Value];

    if ( dC[Left_Connect] + prev_dC || dR[Left_Connect] + prev_dR )
    {
      if ( prev_dC + dC[Right_Connect] || prev_dR + dR[Right_Connect] )
        return 0LL;

      prev_dR = dR[Left_Connect];
      prev_dC = dC[Left_Connect];
    }
    else
    {
      prev_dR = dR[Right_Connect];
      prev_dC = dC[Right_Connect];
    }

    prev_VisitCnt = VisitCnt;
    Group = sub_4012B0(C, R);                   // (R, C) -> [0, 12]
    if ( ((unsigned int)Prev_Group & Group) != -1 )
    {
      if ( Group == (_DWORD)Prev_Group )
      {
        if ( ++Continuous > 3 )
          return 0LL;
      }
      else
      {
        v9 = Check[Prev_Group];
        v10 = Continuous;
        Continuous = 1;
        if ( v9 < v10 )
          v9 = v10;
        Check[Prev_Group] = v9;
      }
    }
    C += prev_dC;
    R += prev_dR;

    if ( (unsigned int)(prev_VisitCnt - 1) > 62 )
      break;

    if ( !(R | C) )
      return 0LL;

    VisitCnt = prev_VisitCnt + 1;

    if ( (R | C) > 7 )
      return 0LL;
LABEL_13:
    Prev_Group = Group;
  }

  if ( prev_VisitCnt != 128 )
  {
    VisitCnt = prev_VisitCnt + 1;
    if ( (R | C) > 7 )
      return 0LL;
    goto LABEL_13;
  }

  return Check[0] == 3
      && Check[1] == 3
      && Check[2] == 3
      && Check[3] == 3
      && Check[4] == 3
      && Check[5] == 3
      && Check[6] == 3
      && Check[7] == 3
      && Check[8] == 3
      && Check[9] == 3
      && Check[10] == 3
      && Check[11] == 3
      && Check[12] == 3;
}

`sub_4012B0`

해당 함수 내에 있는 `sub_4012B0`을 먼저 잠깐 보고 오자. `sub_4012B0`은 다음과 같이 decompile된다.

~~(복기를 설날에 시골에서 쓰는 게으른 청년이라 Ghidra로 까서 조금 더럽다.)~~

uint sub_4012B0(char C,char R)

{
  ulong uVar1;

  uVar1 = 1L << (R + C * 8 & 0x3fU);
  if ((uVar1 & bitmap[0]) != 0) {
    return 0;
  }
  if ((uVar1 & bitmap[1]) != 0) {
    return 1;
  }
  if ((uVar1 & bitmap[2]) != 0) {
    return 2;
  }
  if ((uVar1 & bitmap[3]) != 0) {
    return 3;
  }
  if ((uVar1 & bitmap[4]) != 0) {
    return 4;
  }
  if ((uVar1 & bitmap[5]) != 0) {
    return 5;
  }
  if ((uVar1 & bitmap[6]) != 0) {
    return 6;
  }
  if ((uVar1 & bitmap[7]) == 0) {
    if ((uVar1 & bitmap[8]) != 0) {
      return 8;
    }
    if ((uVar1 & bitmap[9]) != 0) {
      return 9;
    }
    if ((uVar1 & bitmap[10]) != 0) {
      return 10;
    }
    if ((uVar1 & bitmap[11]) == 0) {
      return -(uint)((uVar1 & bitmap[12]) == 0) | 0xc;
    }
    return 0xb;
  }
  return 7;
}

`bitmap`의 값은 `0x4040A0`에 있으며, Python으로 해당 루틴을 재현하여 8*8 입력의 정의역을 다 넣어보면 다음과 같다.

from pwn import *
from itertools import product

chal = ELF("challenge2")
mat = [u64(chal.read(0x4040A0 + 8 * i, 8)) for i in range(13)]

def sub_4012B0(C: int, R: int):
    for idx, val in enumerate(mat):
        if (1 << ((R + 8 * C) & 0x3F)) & val:
            return idx
    else:
        return -1

for c in range(7, -1, -1):
    for r in range(8):
        print(f"{sub_4012B0(c, r):2d}", end=" ")
    print()

"""
 8  8  9  9 11 12 12 12 
 8  6  9 11 11 11 -1 12 
 8  6  9  9 10 10 10 10 
 6  6  6  7  7  7  7 -1 
-1  3  4  4  4  5  5  5 
-1  3  3  4  1  5  5  5 
-1  3  4  4  1  2  2  2 
 0  0  0  0  1  1  2  2
"""

Explanation

`Left` 와 `Right`, `dR`과 `dC` 는 다음과 같다.

Left  = [0, 0, 0, 1, 1, 2]
Right = [1, 2, 3, 2, 3, 3]

dR = [0, 1, 0, -1]
dC = [1, 0, -1, 0]

입력으로부터 `sub_401380` 을 거쳐 변환된 0~5의 값을 가지는 8*8 array의 element에 따라 다음과 같은 행동을 수행한다.

Value	0	1	2	3	4	5
Left_Conn.	0	0	0	1	1	2
Right_Conn.	1	2	3	2	3	3
(dC, dR) pairs	[0, 1] [1, 0]	[0, 1] [0, -1]	[0, 1] [-1, 0]	[1, 0] [0, -1]	[1, 0] [-1, 0]	[0, -1] [-1, 0]

입력 $_{4}C_{2}$ 가지에 따라 방향을 연결하며, `while(1)` 내 첫번째 2중 if문은 해당 연결이 모두 끊기지 않아야 함을 의미하고 있다.

이후, 두번째 `Continuous`를 검사하고 `Check`를 업데이트하면서, `Continuous > 3`, 즉 같은 Group을 4번 이상 가지게 되는 경우 == `sub_401380`에서 반환되는 값이 4회 이상 같아지는 경우 `return 0`으로 유효하지 않음을 의미한다.

초기의 `(R, C) == (0, 0)`, `(prev_dR, prev_dC) == (0, -1)` 이기 때문에 처음 경로의 시작은 (0, 0)에서 오른쪽 (C가 증가하는 방향) 으로 출발하는 것을 알 수 있다.

룰에 따르면, 연결이 끊기지 않기 위해 마지막에 다시 (0, 0)으로 돌아올때 위쪽 (R이 감소하는 방향)에서 내려와야 할 것이다.

`while(1)` 내의 `prev_VisitCnt > 63` 시 `break` 하고, 다시 이를 한번 더 돌려서 `while` 밖에서 `prev_VisitCnt != 128` 인 경우 다시 `while` 내부로 돌아가게 된다. 해당 Cycle을 2회 돌리게 된다.

Return value는 `Check` 의 모든 원소가 3이어야 1을 반환할 수 있다. 따라서 최소 한번 같은 Group을 3번 연속으로 방문해야 한다.

정리해보자면 다음과 같다.

(0, 0)에서 오른쪽으로 출발해 `sub_401380` 의 결과로 나오는 배열의 각 Element를 주변 2개의 element와 연결하되,
Element의 숫자는 4번 이상 연속으로 연결될 수 없으며,
적어도 한 번 Element의 숫자가 3번 연속으로 연결되어야 한다.
연결된 Path는 모든 칸을 폐곡선으로 연결해야 한다.

Puzzle(?) Solving

해당 로직을 모두 분석했을 때 시간이 02시여서 머리가 안돌아갔다. 이를 풀기 위해 z3이라던지 다른 방법을 얹는 것 보다 손으로 풀리는게 훨씬 빠르겠다고 생각했다. 집단지성의 힘을 빌렸다.

이거 올리고 한 30분 더 보다가 쓰러졌고, 다음날 아침에 일어났는데 boo 선배님께서 답을 찾아주셨다.

다음날 일어나자마자 바로 확인했고, 앞서 연결하는 방식에 따라 칸 내의 연결을 integer로 치환 (물론 손으로) 했다. `sub_401380`의 로직에 따라 그대로 역산하도록 Python code를 작성했다.

from pwn import *
import string

chal = ELF("challenge2")

mat = [
    3, 4, 5, 3, 5, 3, 4, 5,
    1, 3, 2, 1, 1, 0, 5, 1,
    1, 0, 4, 2, 0, 4, 2, 1,
    0, 4, 4, 4, 4, 5, 3, 2,
    3, 4, 4, 4, 4, 2, 0, 5,
    0, 5, 3, 4, 4, 4, 5, 1,
    3, 2, 0, 4, 4, 5, 1, 1,
    0, 4, 4, 4, 4, 2, 0, 2,
]

ofst = [u32(chal.read(0x404020 + 4 * x, 4)) for x in range(32)]

target = string.ascii_lowercase + string.digits

for i in range(0, len(mat), 2):
    x = (((mat[i] * 6 + mat[i + 1]) - ofst[i // 2]) % 36)
    print(target[x], end="")

# s0w3ne3daf1a97hat5th1r7y7wo6yte5

FLAG: `dice{s0w3ne3daf1a97hat5th1r7y7wo6yte5}`

처음부터 바로 Static하게 하나하나 해석해나갔다면 더욱 빨리 풀지 않았을까 싶다는 후회가 많이 들었다.

TMI 및 여담

자는 도중 해당 문제를 PPC에 내고 싶다는 poro의 사심 담긴 발언이 있었다. PPC 예상문제로 이걸 적절히 구현해보도록 하자. `#constructive` `#ad-hoc` 같은 더러운 태그는 다 붙을 것 같다.

'Writeups' 카테고리의 다른 글

[bi0sctf 2024] writeups (0)	2024.03.04
[insomnihack 2024] writeups (0)	2024.01.26
[securinetsCTF 2023] tomojiksi (0)	2024.01.16
[dreamhack.io] multipoint2 (0)	2024.01.11

Aplace.Log

[dicectf 2024] writeups

pain-plus-plus

three

ELF patching

Analysis

`sub_401380`

`sub_401420`

`sub_4012B0`

Explanation

Puzzle(?) Solving

TMI 및 여담

'Writeups' 카테고리의 다른 글

티스토리툴바

[dicectf 2024] writeups

pain-plus-plus

three

ELF patching

Analysis

`sub_401380`

`sub_401420`

`sub_4012B0`

Explanation

Puzzle(?) Solving

TMI 및 여담

'Writeups' 카테고리의 다른 글

'Writeups' Related Articles

티스토리툴바