문제: DreamHack — tiny-ouroboroi 분류: Reversing 난이도: 🥉 Bronze 3 FLAG:
DH{bac93c27e6c3578afd93d2eec7edb24e61da8e9c99567ecec9e7f554093b0cdc}
이름의 우로보로스(자기 꼬리를 무는 뱀)가 그대로 힌트다. 입력을 받아 글자마다 원형 연결리스트를 만들어 이리저리 굴린 뒤, 그 결과를 바이트로 뽑아내는 인코더다. output.bin이 플래그를 이 인코더로 돌린 결과이고, 우리는 그걸 거꾸로 되짚어야 한다.

문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | tiny-ouroboroi |
| 난이도 | 🥉 Bronze 3 |
| 분류 | Reversing (x86-64 ELF, PIE, stripped) |
| 제공 파일 | main, output.bin (68바이트) |
| 핵심 기법 | 위치별 독립 인코더를 블랙박스 전수조사로 역산 |
인코더가 로컬에서 돌아가므로, 내부를 다 뜯지 않고도 입출력만으로 뒤집을 수 있다.
🔬 정찰 — 글자 하나가 원형 리스트 하나
main을 radare2로 보면, 입력을 scanf("%s")로 받아 글자마다 같은 처리를 반복한다.
r2 -q -A -e log.quiet=true -c "pd 20 @ 0x13a0" main
각 글자 s[i]에 대해 네 개의 헬퍼 함수가 순서대로 불린다. 정리하면 이렇다.
- 리스트 생성: 글자값
s[i]만큼의 노드를 가진 원형 연결리스트를 만든다(각 노드에 0/1 비트 하나).'A'(65)면 65개짜리 원이다. - 회전: 리스트의 머리를 인덱스
i만큼 앞으로 돌린다. - 토글(홀수 자리만):
i가 홀수면 모든 노드의 비트를 뒤집는다(0↔1). - 출력: 원을 한 바퀴 돌며 비트를
shl·or로 모아 한 바이트로 만들어 출력한다.
비교(strcmp)나 정답 판정이 없다. 이 프로그램은 검사기가 아니라 인코더이고, output.bin(68바이트)은 플래그(68글자)를 이 인코더에 넣은 결과다.
💣 핵심 — 각 바이트는 그 자리 글자에만 달렸다
인코딩을 자세히 뜯어 각 함수를 수식으로 역산할 수도 있지만, 더 빠른 길이 있다. 출력의 i번째 바이트는 오직 입력의 i번째 글자와 위치 i 로만 결정된다. 리스트는 글자마다 따로 만들어지고, 회전량과 토글 여부도 그 자리의 인덱스 i로만 정해지기 때문이다. 자리끼리 서로 영향을 주지 않는다.
output[i] = f(s[i], i)그러면 함수 f를 몰라도 된다. 인코더가 로컬에서 돌아가니, 궁금한 값을 직접 물어보면 된다. 어떤 후보 글자 c를 68번 반복해 입력으로 넣으면, 출력은 [f(c, 0), f(c, 1), …, f(c, 67)]이 통째로 나온다. 즉 한 번 실행으로 모든 위치에 대한 c의 인코딩을 얻는다.
printable 글자마다 한 번씩(약 95회) 돌려 "이 위치에서 이 바이트를 만드는 글자" 표를 채운 뒤, output.bin의 각 바이트를 그 표에서 찾으면 플래그가 자리별로 복원된다.
🎯 풀이 — 후보를 통째로 넣어 매핑
각 후보 글자를 68번 반복해 인코더에 넣고, 위치별로 출력바이트 → 글자 매핑을 만든다.
# solve.py
import subprocess
target = open("output.bin", "rb").read()
L = len(target) # 68
mp = [dict() for _ in range(L)]
for c in range(0x21, 0x7f): # 공백 제외 printable
out = subprocess.run(["./main"], input=bytes([c])*L + b"\n",
capture_output=True).stdout
if len(out) < L: continue
for i in range(L):
mp[i].setdefault(out[i], chr(c)) # 위치 i 에서 이 바이트를 만드는 글자
flag = "".join(mp[i].get(target[i], "?") for i in range(L))
print("FLAG:", flag)
물음표 하나 없이 플래그가 복원된다. 복원한 문자열을 다시 인코더에 넣어 출력이 output.bin과 바이트 단위로 일치하는지 확인하면 확실하다.
# verify.py
import subprocess
flag = "DH{bac93c27e6c3578afd93d2eec7edb24e61da8e9c99567ecec9e7f554093b0cdc}"
out = subprocess.run(["./main"], input=flag.encode() + b"\n", capture_output=True).stdout
print("re-encode == output.bin :", out == open("output.bin","rb").read())
재인코딩 결과가 output.bin과 정확히 같다. 복원이 맞다.
FLAG: DH{bac93c27e6c3578afd93d2eec7edb24e61da8e9c99567ecec9e7f554093b0cdc}
📝 결론
인코더가 손에 있으면 수식을 안 풀어도 된다.
원형 리스트, 회전, 비트 토글까지 얽혀 있어 정방향 함수를 손으로 역산하려면 성가시다. 하지만 변환이 위치별로 독립이고 인코더를 직접 돌릴 수 있으면, "이 자리에서 이 글자는 무슨 바이트가 되나"를 물어보는 것으로 충분하다. 블랙박스 질의 몇 번이 복잡한 대수 역산을 대신한다.
독립성이 공격의 문이다.
이 인코더의 약점은 자리끼리 섞이지 않는다는 것이다. 각 출력 바이트가 한 글자에만 달려 있으니, 전체를 한 번에 풀지 않고 68개의 작은 문제로 쪼개 각각 전수조사할 수 있었다. 자리 사이에 확산(diffusion)이 없으면, 아무리 한 자리를 복잡하게 만들어도 전체는 그 복잡도의 합에 그친다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…