[🥉 Bronze 3] 원형 리스트 인코더를 블랙박스로 뒤집다 — DreamHack tiny-ouroboroi 풀이

2026-07-13·1분 읽기·

[🥉 Bronze 3] 원형 리스트 인코더를 블랙박스로 뒤집다 — DreamHack tiny-ouroboroi 풀이

입력 각 글자를 그 글자값 길이의 원형 연결리스트로 만들어 회전·토글한 뒤 비트를 모아 한 바이트씩 출력하는 인코더 문제. 출력의 각 바이트가 오직 그 자리 글자와 위치에만 의존하므로, 함수를 다 역산할 필요 없이 후보 글자를 통째로 넣어 위치별 매핑을 만들면 플래그가 복원된다.

문제: 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
radare2 main 루프 — 글자마다 리스트 생성·회전 함수를 부르고 홀수 인덱스면 토글 함수를 추가로 호출
radare2 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)
solve.py 실행 화면 — 위치별 인코더 매핑을 그대로 뒤집어 output.bin 68바이트를 역산했고, 물음표 하나 없이 완성된 DH 형식 플래그가 한 줄로 출력된다
solve.py 실행 화면 — 위치별 인코더 매핑을 그대로 뒤집어 output.bin 68바이트를 역산했고, 물음표 하나 없이 완성된 DH 형식 플래그가 한 줄로 출력된다

물음표 하나 없이 플래그가 복원된다. 복원한 문자열을 다시 인코더에 넣어 출력이 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())
verify.py 실행 화면 — 복원한 플래그를 원래 인코더로 다시 돌린 결과가 output.bin 68바이트와 바이트 단위로 완전히 같아 True 가 찍혔다
verify.py 실행 화면 — 복원한 플래그를 원래 인코더로 다시 돌린 결과가 output.bin 68바이트와 바이트 단위로 완전히 같아 True 가 찍혔다

재인코딩 결과가 output.bin과 정확히 같다. 복원이 맞다.

FLAG: DH{bac93c27e6c3578afd93d2eec7edb24e61da8e9c99567ecec9e7f554093b0cdc}



📝 결론

인코더가 손에 있으면 수식을 안 풀어도 된다.

원형 리스트, 회전, 비트 토글까지 얽혀 있어 정방향 함수를 손으로 역산하려면 성가시다. 하지만 변환이 위치별로 독립이고 인코더를 직접 돌릴 수 있으면, "이 자리에서 이 글자는 무슨 바이트가 되나"를 물어보는 것으로 충분하다. 블랙박스 질의 몇 번이 복잡한 대수 역산을 대신한다.

독립성이 공격의 문이다.

이 인코더의 약점은 자리끼리 섞이지 않는다는 것이다. 각 출력 바이트가 한 글자에만 달려 있으니, 전체를 한 번에 풀지 않고 68개의 작은 문제로 쪼개 각각 전수조사할 수 있었다. 자리 사이에 확산(diffusion)이 없으면, 아무리 한 자리를 복잡하게 만들어도 전체는 그 복잡도의 합에 그친다.

이 글이 도움이 됐나요?

Comments

댓글

0개

댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)

댓글 불러오는 중…

Related

관련 글

3개
[🥉 Bronze 2] Duff's device로 펼친 위치별 XOR 되돌리기 — DreamHack legacyopt 풀이
blog

[🥉 Bronze 2] Duff's device로 펼친 위치별 XOR 되돌리기 — DreamHack legacyopt 풀이

입력을 Duff's device로 펼친 루프에서 위치별 상수와 XOR해 hex로 출력하는 인코더 문제. 각 출력 바이트가 그 자리 입력에만 달려 있어, 같은 길이의 알려진 입력을 한 번 넣어 위치별 XOR 상수를 캐낸 뒤 주어진 출력에 그대로 적용하면 플래그가 복원된다. 재인코딩이 원본과 일치함까지 확인했다.
#dreamhack#ctf#reversing+4
2026-07-14#dreamhack +4
[🥉 Bronze 3] XOR·덧셈·비트회전을 거꾸로 되짚다 — DreamHack nub_rev01 풀이
blog

[🥉 Bronze 3] XOR·덧셈·비트회전을 거꾸로 되짚다 — DreamHack nub_rev01 풀이

입력 한 글자씩 XOR·덧셈·비트회전을 걸어 스택에 박힌 상수와 비교하는 리버싱 크랙미. 세 연산이 모두 가역이라, 비교 대상(target)에서 역순으로 회전을 풀고 덧셈을 빼고 XOR를 되돌리면 정답 입력이 그대로 복원된다. 복원한 문자열을 바이너리에 넣어 Correct로 확인했다.
#dreamhack#ctf#reversing+4
2026-07-14#dreamhack +4
[🥉 Bronze 4] 입력을 XOR해 비교하는 검사식 뒤집기 — DreamHack Happy New Year! 풀이
blog

[🥉 Bronze 4] 입력을 XOR해 비교하는 검사식 뒤집기 — DreamHack Happy New Year! 풀이

59자 입력을 코드에 박힌 상수 버퍼로 XOR한 뒤 고정 문자열과 strcmp하는 리버싱 문제. 비교식을 뒤집으면 정답 입력 = buf ^ s2 이고, 그 입력이 그대로 플래그 본문이 된다. 상수 버퍼를 재구성해 XOR 한 번으로 새해 인사 문장을 복원했다.
#dreamhack#ctf#reversing+3
2026-07-13#dreamhack +4