[Incognito CTF 2023] 괴도가 훔쳐간 DB 풀이

2023년 11월 24~25일에 열린 Incognito CTF 2023 의 Forensic 카테고리 문제 괴도가 훔쳐간 DB 풀이다. SQLite 파일에서 지워진 레코드를 복구해야 하는 문제로, DB 뷰어로는 보이지 않는 데이터를 헥스 에디터로 페이지 구조를 직접 파싱해서 찾아야 했다.

문제

괴도키드가 중요한 DB를 훔쳐가서 데이터가 일부 삭제되었다. 복구를 하자.

Timezone : KST

flag : INCO{유저명_비밀번호_YYYY-MM-DD HH:MM:SS_복구한 이미지에 표시된 글자}

어떤 레코드가 사라졌나

먼저 DB Browser for SQLite 로 db 파일을 열어보았다.

id 4번 레코드만 비어 있다.

id가 4번인 행만 없다. 즉 복구해야 할 레코드는 4번이다. 하지만 뷰어로는 여기까지가 끝이므로, 이제부터는 파일을 HxD 로 직접 열어 SQLite 포맷을 손으로 따라가야 한다.

헤더와 페이지 크기

데이터베이스 헤더.

SQLite 데이터베이스 헤더의 offset 0x10 부터 2바이트가 페이지 크기 를 의미한다.

• page size = 0x1000 (big endian)

즉 N번 페이지의 파일 오프셋은 (N - 1) * 0x1000 이다. 이후 모든 계산이 이 식을 따라간다.

스키마 테이블에서 루트 페이지 찾기

헤더 아래로 쭉 내려가면 스키마 테이블(sqlite_master)이 나온다.

스키마 테이블에 저장된 CREATE TABLE 쿼리문.

스키마 테이블의 쿼리문 앞에는 해당 테이블의 루트 페이지 번호 가 붙어 있다.

• 0x02 ⇒ (2 - 1) * 0x1000 = 0x1000 에 위치

루트 페이지 파싱

0x1000 에 위치한 루트 페이지의 헤더.

페이지 헤더를 하나씩 읽어보면 다음과 같다.

오프셋	값	의미
0x00	0x05	internal page
0x03 (2바이트)	0x00 02	페이지 내 cell 개수 = 2
0x05 (2바이트)	0x0F F6	첫 cell의 offset = 0x0FF6
0x08 (4바이트)	0x00 00 00 2F	right child page = 0x2F ⇒ 0x2E000
0x0C ~	—	페이지 내부 cell의 offset 배열

여기서 이상한 점 이 하나 보였다. cell 개수는 2인데 offset 배열에는 값이 3개 들어 있다. 삭제된 데이터가 그 세 번째 자리에 남아 있는 게 아닐까 하고 의심하게 되는 지점이다.

cell을 따라가 보기

offset 배열에 0FFB, 0FF6, 0FF1 세 개가 들어 있다.

각 offset에 해당하는 cell을 하나씩 찾아갔다.

0FFB → 0x00 00 00 19 (= 0x18000)

leaf 페이지, 페이지 내 record 1개, offset 07D0.

0FF6 → 0x00 00 00 1A (= 0x19000)

leaf 페이지, 페이지 내 record 1개, offset 045A.

0FF1 → 0x00 00 00 05 (= 0x4000)

이쪽은 leaf 페이지가 아니었다.

0FFB 와 0FF6 이 가리키는 페이지는 0D 로 시작하므로 leaf 페이지가 맞지만, 0FF1 이 가리키는 곳에는 의미 없는 값이 들어 있었다. 이 페이지에는 손실된 정보가 있어 보이지 않았다.

살아 있는 레코드 확인

트리를 따라가며 남아 있는 레코드들을 확인했다.

0x19 번 페이지에는 John의 정보가 있었다.

0x1A 번 페이지에는 Jane의 정보가 있었다.

루트 페이지의 right child page(0x2F ⇒ 0x2E000)도 확인했다.

leaf 페이지, 페이지 내 record 2개, offset 01DC·0669.

Michael과 David의 정보.

여기까지 John, Jane, Michael, David — 뷰어에서 보이던 레코드가 전부다. 손실된 4번 레코드는 트리 어디에도 붙어 있지 않았다.

트리에서 떨어져 나간 고아 페이지 찾기

레코드가 삭제되어도 페이지 자체는 파일에 그대로 남아 있는 경우가 많다. 그래서 leaf 페이지 시그니처인 0D 로 시작하는 페이지 를 파일 전체에서 검색했다.

트리에서 참조되지 않는 leaf 페이지가 하나 더 있었다.

해당 위치로 이동해 보았다.

record 2개가 들어 있다.

Michael과 Emily의 정보.

찾았다. 손실된 record는 {04, Emily, letmein, timestamp, 사진} 이다. 유저명은 Emily, 비밀번호는 letmein.

timestamp 복구

2022-04-04 04:04:04.

문제에서 요구한 KST 기준 timestamp는 2022-04-04 04:04:04 이다.

사진 복구 — 페이지 체인 따라가기

남은 건 레코드에 들어 있던 사진이다. 헤더를 보니 JFIF/JPEG 였다.

문제는 이미지가 한 페이지에 다 들어가지 않는다는 점이다. 일단 페이지 끝까지만 잘라서 열어보니 이미지가 중간부터 깨져 보였고, JPEG footer(FF D9)에 해당하는 부분을 찾아 그냥 이어 붙여도 이미지가 열리지 않았다.

그래서 다른 레코드의 사진이 어떤 방식으로 이어져 있는지 를 먼저 파악하기로 했다. DB에서 정상적으로 다운로드되는 사진과 파일 상의 바이트를 비교해보니, 각 페이지의 마지막 4바이트가 다음 페이지의 번호 를 가리키고 있었다. SQLite의 오버플로우 페이지 체인이다.

이 규칙대로 페이지를 이어 붙여 나갔는데, 어느 지점부터 이미지가 다시 깨졌다. 그래서 반대로 JPEG footer 쪽에서부터 거꾸로 올라오며 붙는 구간을 맞춰 나갔다. 그렇게 아래에서부터 올라가다 보니 0x2E000 페이지(Michael, David가 들어 있던 페이지)를 만나게 되어, 그 직전 페이지까지만 이어 붙였다.

완전하지는 않지만 글자는 읽을 수 있었다 — CR3_den_tial.

이미지 전체를 온전히 복구하지는 못했지만, 문제에서 요구한 이미지에 표시된 글자 는 CR3_den_tial 까지 읽어낼 수 있었다.

flag

INCO{Emily_letmein_2022-04-04 04:04:04_CR3_den_tial}

정리

• SQLite에서 레코드가 삭제되어도 페이지는 파일에 그대로 남아 있고, 단지 B-tree에서 참조가 끊길 뿐이다. leaf 페이지 시그니처(0D)로 파일 전체를 훑으면 이런 고아 페이지를 찾을 수 있다.
• 루트 페이지의 cell 개수와 cell offset 배열의 길이가 맞지 않는 것 이 삭제의 첫 단서였다.
• 한 페이지에 들어가지 않는 BLOB은 오버플로우 페이지 체인 으로 흩어지고, 각 페이지 끝의 4바이트가 다음 페이지를 가리킨다. 정상 레코드와 비교해 이 규칙을 알아낸 것이 사진 복구의 핵심이었다.

나중에 알게 된 내용

풀이 당시에는 물음표로 남겨두고 넘어갔던 부분들이 있는데, 이후 SQLite 파일 포맷을 더 공부하면서 대부분 설명이 됐다. 당시 기록은 위에 그대로 두고, 여기에 따로 정리한다.

고아 페이지는 왜 생기나 — freelist

SQLite는 레코드나 페이지가 삭제돼도 파일을 줄이지 않는다(VACUUM 전까지는). 대신 빈 페이지를 freelist 라는 연결 리스트에 매달아 두었다가 나중에 재사용한다.

• 데이터베이스 헤더 offset 0x20 의 4바이트가 첫 freelist trunk 페이지 번호, 0x24 의 4바이트가 freelist 페이지 개수 다.
• trunk 페이지는 빈 leaf 페이지들의 번호 목록을 담고, 다음 trunk 페이지를 가리킨다.

이 풀이에서 찾은 "트리에서 참조되지 않는 0D 페이지"가 바로 이렇게 freelist로 넘어간 페이지다. freelist에 들어가도 페이지 내용은 지워지지 않기 때문에 레코드가 그대로 남아 있었던 것이다. 즉 0D 시그니처로 파일 전체를 훑는 대신, 헤더의 freelist 포인터를 따라갔어도 같은 페이지에 도달할 수 있었다.

0FF1의 "의미 없는 값"의 정체

루트 페이지에서 cell 개수(2)보다 offset 배열의 항목(3)이 많았던 것은, 셀이 삭제될 때 cell pointer 배열의 마지막 항목이 즉시 0으로 덮이지 않고 잔류 했기 때문이다. 헤더의 cell count만 줄어들고 포인터 바이트는 쓰레기로 남는다 — 삭제 흔적을 찾는 입장에서는 오히려 고마운 잔재다. 다만 그 포인터가 가리키던 자식 페이지는 이미 freelist로 넘어가 trunk 페이지 등으로 재사용됐을 수 있고, 0FF1 끝의 값이 leaf 헤더처럼 보이지 않았던 것도 그래서였을 가능성이 크다.

이미지가 끝까지 복구되지 않은 이유

오버플로우 체인의 중간 페이지 일부가 freelist로 회수된 뒤 다른 용도로 재사용되면서 원래 내용을 잃었기 때문 으로 보인다. 체인을 따라가다 갑자기 이미지가 깨진 지점, 그리고 거꾸로 올라가다 0x2E000(살아 있는 leaf 페이지)을 만난 것 모두 — 체인 중간이 다른 페이지로 덮였다는 정황과 일치한다. 삭제된 BLOB의 오버플로우 체인은 이렇게 부분적으로만 살아남는 경우가 흔하고, 그래서 JPEG처럼 구조가 있는 포맷은 살아남은 조각을 footer 쪽에서부터 역방향으로 맞춰보는 접근이 실전에서도 유효하다.