처음에 괄호 안에 괄호가 들어있는 형태랑 닫힌 괄호 옆에 새로운 괄호가 있는 경우를 판단하는게 너무 어려웠다.그래서 보니까 일단 열린 괄호가 '(' 면 2를 곱해놓고 '[' 면 3을 곱해놓은 다음에, 스택에 문자를 넣는다.그리고 열린 괄호가 계속 나올때 까지 해당 괄호에 해당하는 숫자를 계속 곱하다가, 닫는 괄호가 나올 때가 중요한데, 한번 닫는 괄호가 나오면 지금까지 열린 괄호 만큼 곱해준걸 ans변수에 더한다. (이러면 이전 괄호 개수만큼 값을 고려할 수 있음)
그리고 닫는 만큼 계속 나눠주다가 다시 열린게 나오면 반복... 그 외에 경우는 모두 괄호쌍이 맞지 않으니까 ans = 0 넣어놓고 탈출하면 된다. 그리고 저 과정을 거쳐도 스택이 모두 안 비어질때가 있는데 그 땐 올바르지 않으니까 empty인지 체크하고 0 넣어주면 된다.
문제에서 주어진 코드이다. read_member 함수를 통해서 구조체에 입력을 할 수 있고, status의 값에 따라서 throw 함수 포인터를 실행할 지 안 할지 결정할 수 있다.
취약점은 쉽게 보이고, throw 를 원하는 함수로 덮을 수 있고 첫 번째 인자를 4바이트, 두 번째 인자를 8바이트로 세팅할 수 있다.
여기서 가장 걸리는 점이 출제자가 세팅한 CFI 매크로 인데, 함수를 실행하기 전에 이 매크로에서 함수의 시작 부분이 endbr64 옵코드로 시작하지 않으면 바로 trap을 먹여버린다. 그래서 이동할 때 무조건 endbr64 가 존재하는 함수로 이동시켜 줘야 trap이 안 걸리고 정상적으로 실행 된다.
내가 맨 처음에 시도한건 __libc_write 를 덮고, 첫 번째 인자는 1로, 두 번째 인자를 got로 세팅해서 libc 를 leak 하는거였는데,로컬은 되는데 리모트가 안돼서 삽질을 겁나게 했다,,, 나중에 들어보니까 gdb를 깔면 오차가 생길 수 있어서 그렇다고 한다.
아무튼 그래서 다른 방법은 __libc_write가 아닌 warnx 를 덮는거였다. warn는 무조건 exit를 하는 줄 알고 그냥 넘어갔는데, warn 자체는 printf만 하고 exit를 하지 않는다. 그래서 warn 첫 번째 인자에 got를 넣어주면 libc 출력이 된다. 확률은 1/16 이다. (1.5바이트만 일정하고 0.5 바이트는 랜덤)
그래서 libc 출력이 되면 다시 한 번 점프 뛸 곳을 정해야 하는데, atexit 함수의 첫 번째 인자에 원하는 함수 주소를 넣으면 그 쪽으로 jmp를 뛴다. 그래서 atexit에 main을 넣고 다시 main으로 돌아와서 gets 함수로 bss에 /bin/sh\x00 을 넣고 system 함수 인자로 bss 주소를 넣어주면 풀린다.
무조건 워게임만 많이 푼다고 실력이 잘 느는게 아니라 이미 어느정도 문제를 풀어서 기초를 쌓았으면 바로 최신 CTF 문제들을 업솔빙해서 동향을 파악하는게 더 좋다고 느꼈다. 그래서 가급적이면 최근 (2020~) 문제들을 모아서 풀아보려고 CTF 문제 리스트를 정리하려고 한당.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
static int menu(void);
static int getnline(char *buf, int size);
static int getint(void);
#define write_str(s) write(STDOUT_FILENO, s, sizeof(s)-1)
int main(void){
FILE *fp;
alarm(60);
write_str("Play with FILE structure\n");
if(!(fp = fopen("/dev/null", "r"))){
write_str("Open error");
return -1;
}
fp->_wide_data = NULL;
for(;;){
switch(menu()){
case 0:
goto END;
case 1:
fflush(fp);
break;
case 2:
{
unsigned char ofs;
write_str("offset: ");
if((ofs = getint()) & 0x80)
ofs |= 0x40;
write_str("value: ");
((char*)fp)[ofs] = getint();
}
break;
}
write_str("Done.\n");
}
END:
write_str("Bye!");
_exit(0);
}
static int menu(void){
write_str("\nMENU\n"
"1. Flush\n"
"2. Trick\n"
"0. Exit\n"
"> ");
return getint();
}
static int getnline(char *buf, int size){
int len;
if(size <= 0 || (len = read(STDIN_FILENO, buf, size-1)) <= 0)
return -1;
if(buf[len-1]=='\n')
len--;
buf[len] = '\0';
return len;
}
static int getint(void){
char buf[0x10] = {};
getnline(buf, sizeof(buf));
return atoi(buf);
}
2번 메뉴에서 FILE* 로 선언된 변수 안에 오프셋으로 값을 조작 할 수 있고 이를 통해 _IO_FILE 구조체에 있는 값을 아무거나 덮을 수 있다.
그리고 1번 메뉴에서 그 fp를 fflush 한다. 여기 까지 오면 fflush 를 어떻게 잘 해야겠다는 생각을 할 수 있다. 여기서 특이한 점은 _wide_data 를 지우기 때문에 해당 멤버 관련된 여러 파일 스트림 함수 (_IO_wfile_...) 를 통한 임의 코드 실행이 불가능 하므로, 다른 공격 벡터를 생각 해야한다.
즉 위 글에서 핵심은 _IO_write_base와 _IO_write_ptr을 libc 가 존재하는 영역으로 세팅해서 출력 과정에 libc 가 leak 되는 것이다. 하지만 문제에서의 fp는 /dev/null 을 open 하고 있기 때문에 _IO_write_base와 같은 영역에 아무 주소도 세팅 되어있지 않다.
그래서 먼저 저 영역에 알맞은 주소를 세팅해야 한다. 여러 함수를 살펴본 결과, _IO_doallocbuf 라는 함수는 인자에 File Stream Structure를 넣으면 _IO_buf_base 와 _IO_buf_end 가 힙 주소로 세팅된다.
그리고 해당 멤버를 _IO_write_base와 _IO_write_ptr 에 옮겨야한다. 이걸 해주는 함수는 _IO_new_file_overflow 이다.
자세한건 해당 코드를 직접 뜯으면 되는데, _IO_buf_base 와 _IO_buf_end에 들어 있는 값을 _IO_write_base 와 같은 멤버 들로 모두 옮겨준다. 그럼 이제 모든 변수가 세팅 됐으므로, flag만 잘 세팅해주고 _IO_new_do_write 같은 출력 함수를 사용하도록 해주면 된다.
이건 원래 fflush 함수가 어떤걸 호출하는지 보면, _IO_new_file_sync 를 호출하게 된다. 안에 들어가면 _IO_do_flush 를 호출하고 이는 _IO_do_write를 호출하고 우리가 변수를 잘 세팅했다는 가정하에 heap에 깔린 주소를 출력하게 된다.
heap을 보면 libc가 역시 깔려 있고 libc leak을 한 뒤에 다시 _IO_write_base, _IO_write_ptr 을 main_arena+96, main_arena+96+8 로 세팅하면 힙 주소가 세팅 된다.
이제 원하는 함수를 어떻게 호출할지 생각해보자. 이건 구글을 뒤져가면서 찾았는데 _IO_obstack 관련 함수를 쓰면 된다.
두 가지 함수가 존재한다. _IO_obstack_overflow와 _IO_obstack_xsputn 이 있는데 두 함수 모두 매크로를 따라 분석해보면
함수 포인터가 존재하고 인자도 존재한다. 이를 조작해주면 된다. 관련 문서는 찾아보면 많으니 찾아보시길..핵심만 첨부하겠다.
# define CALL_FREEFUN(h, old_chunk) \
do { \
if ((h)->use_extra_arg) \
(*(h)->freefun)((h)->extra_arg, (old_chunk)); \
else \
(*(void (*)(void *))(h)->freefun)((old_chunk)); \
} while (0)
위에서 접근하는 변수는 모두 obstack struct의 멤버이고 이를 수행하기 위해 힙에 fake obstack을 만들어 주면 된다.
#include <stdio.h>
#include <unistd.h>
int main() {
char name[0x30], country[0x20];
/* Ask name (accept whitespace) */
puts("Hello! What is your name?");
scanf("%[^\n]s", name);
printf("Nice to meet you, %s!\n", name);
/* Ask country */
puts("Which country do you live in?");
scanf("%s", country);
printf("Wow, %s is such a nice country!\n", country);
/* Painful goodbye */
puts("It was nice meeting you. Goodbye!");
return 0;
}
__attribute__((constructor))
void setup(void) {
setbuf(stdin, NULL);
setbuf(stdout, NULL);
alarm(180);
}
SECCON이 코 앞이라 작년 문제를 풀어보고있다. 코드만 보면 취약점이 보이는 아주 간단한 문젠데 걸리는 포인트는
scanf는 문자열을 입력하면 끝에 null byte가 무조건 붙기 때문에 printf 를 통한 leak이 불가능 하다.
하지만 %[^\n]s 는 문자열을 입력할 뗴 \n 전 까지 입력 받기때문에, 아무 것도 입력하지 않고 엔터 한 번만 누르면 (개행 문자만 넣으면) 아무 것도 입력되지 않아 null byte가 포함 되지 않고 stack에 존재하는 값을 leak 할 수 있다.
삽질을 조금 했는데, ubuntu 22.04.와 ubuntu 20.04의 스택 환경이 많이 다르기 때문에 22.04에선 leak이 안되고 20.04 에선 leak이 된다. 그래서 문제에서 주어진 환경인 20.04 대로 환경을 구성해서 푸는 것이 좋다.
이를 통해 libc leak이 가능하고 버퍼오버플로우를 통해 ret에 oneshot 가젯을 덮어주면 풀린다.
코드는 위와 같다. qemu 문제는 처음이라 관련 write-up 을 뒤져가면서 함수를 어떻게 호출해야 하는지 공부했다.
간략하게 말하면 두 가지 방식이 존재하는데, 첫 번째로 MMIO를 통해서 메모리를 레지스터처럼 쓰는 방법을 이용해서 일정 오프셋을 넣어주면 그 오프셋에 해당하는 함수가 실행된다.
두 번째로 in out 과 같이 디바이스에서 열어놓은 포트를 통해 통신하여 데이터를 I/O 해주는 방법이 있다.
이 문제에선 MMIO 방식으로 데이터를 I/O 하기 때문에, 일정한 오프셋을 더해서 원하는 기능을 호출해주면 된다.
통신하는 방법은 여러가지 있는데, 가장 많이 쓰는 방법은 /sys/devices/pci0000:00/0000:00:??.0/resource0 파일을 open 해주면, 이 때 반환된 파일 디스크립터를 통해 디바이스 메모리에 접근할 수 있다. 이제 이걸 통해서 공격을 수행하면 된다.
여기서 알아야 할 함수는 cpu_physical_memory_rw 이다. 첫 번째 인자는 qemu 외부에서 실제 주소가 들어가고, (physical memory) 두 번쨰 인자는 qemu 내부에서 사용하는 주소들이 들어간다. 세 번째 인자는 입/출력을 할 버퍼의 길이를 지정해주고, 네 번째에선 모드를 지정한다.
네 번째 인자가 0이면 write를 하게 되면서, maria->buff[maria->state.off]에 있는 내용을 BUFF_SIZE 만큼 maria->state.src에 넣게된다.
네 번째 인자가 1이면 read를 하게 되면서, maria->state.src에 있는 내용을 BUFF_SIZE 만큼 maria->buff[maria->state.off] 에 복사하게 된다.
여기서 가장 먼저 발생할 수 있는 취약점은, 언뜻보면 maria->off가 uint8_t type으로, 0xff 까지만 쓸 수 있으니 oob가 안 나지 않을까 하고 생각할 수 있는데, off가 0xff까지만 사용할 수 있더라도, BUFF_SIZE는 무조건 0x2000을 사용하기 때문에, read를 사용하면 buff 뒤에 있는 값들까지 모두 읽을 수 있고, 이는 중요한 정보를 많이 담고 있기에 크리티컬하다.
read를 이용해서 maria->buff[maria->state.off] 를 0x2000 만큼 maria->state.src에 전달하면 된다. 근데 이때 state.src는 physical address로 전달해야해서 이런걸 변환해주는 함수를 찾아서 템플릿으로 넣어두고 사용하면 된다. 대회 때 여기서 디게 많이 헷갈렸는데, physical address 로 전달하게 되면 알아서 내부에서 virtual address로 바뀌어서 우리가 아는 주소에 실제 값들이 들어가게 된다. 이게 엄청 헷갈려서 몇 시간 잡아먹었음. 기초 운영체제 지식같은데 기초가 중요한 것 같다.
그러면 이제 qemu base 주소와, maria 주소를 알아서 write 함수를 이용해 fake maria state struct를 만들어 주면되는데, 이 때 사용하는 흔한 벡터가 mmio 내부엔 ops 라고 해서 함수포인터들을 저장해놓은 포인터가 존재한다. 이 때 fake vtable 을 만들어서 이 포인터의 주소를 ops에 덮어주면 우리가 원하는 함수포인터들을 사용할 수 있다.
보통 ROP를 이용하여 푸는데 익스코드를 보니까 디게 복잡했다. 그래서 다른 풀이를 봤는데 mprotect를 이용해서 간단하게 RWX 권한을 메모리에 줄 수 있고 해당 주소를 실행해서 플래그를 읽을 수 있다.
#include <bits/stdc++.h>
using namespace std;
int N, T[1500001], P[1500001];
int dp[1500001];
int ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> T[i] >> P[i];
dp[i] = P[i];
}
for(int i = N; i > 0; i--) {
if(T[i] + i > N + 1) dp[i] = dp[i + 1];
else dp[i] = max(dp[i+1], P[i] + dp[i+T[i]]);
}
cout << dp[1];
}
$O(N)$ 에 하는 방법을 찾으면 둘 다 똑같이 풀 수 있다.
$D[i]$ 를 $i$일 까지 일 했을 때 얻을 수 있는 최대 이득이라고 하면, 현재 $i$ 일의 일을 안 할수도 있고 할 수도 있기 때문에, 이걸 케이스로 두 가지로 나눠 max를 따져 보면 된다. 안 하면 다음 날짜인 $D[i+1]$ 을 보면 되고, 일을 하면 $D[i+T[i]] + P[i]$ 를 보면 되기 때문에, 두 값에 대해 max를 취하면 된다. 이걸 역순으로 보면 $D[i]$ 에 대해서 풀 수 있다.
그리고 퇴사1 에선 N의 범위가 작아 dfs로 풀 수 있는데, 퇴사2에선 범위가 커지기 때문에 메모이제이션을 적용하여 dfs에서 쓴 재귀식을 그대로 사용할 수 있다.