2026 18th CODEGATE CTF 문제 풀이

0. 개요

문제 이름 : Ghost
문제 유형 : Crypto
환경 :
- 해시 구조 : Davies-Meyer
- 블록 암호: 커스텀 Feistel (64-bit)
- oracle 제공: round core 출력
목표 :
- 서로 다른 두 입력 m₁, m₂에 대해 동일한 해시 값을 만드는 충돌 생성

1. 전체 구조 분석

1-1. 해시 구조

해시는 Davies-Meyer 구조를 사용한다.

DM(iv, m) = E(iv, m) ⊕ iv

따라서 충돌 조건은 다음과 같이 단순화된다.

DM(iv, m1) = DM(iv, m2)
→ E(iv, m1) = E(iv, m2)

결국 블록 암호 출력 충돌 문제

1-2. 문제 정의

문제는 다음가 같이 정리된다. 같은 입력(iv)에 대해 동일한 암호 출력이 나오도록 두 메시지를 찾는 문제

2. 암호 구조 분석

2-1. 전체 구조

블록 암호는 다음과 같은 Feistel 구조를 가진다.

블록 : 64-bit (32bit x 2)
라운드 : 32
키 : 8 x 32bit

2-2. 라운드 키 스케줄

k0 k1 k2 k3 k4 k5 k6 k7
k0 k1 k2 k3 k4 k5 k6 k7
k0 k1 k2 k3 k4 k5 k6 k7
k7 k6 k5 k4 k3 k2 k1 k0

반복 및 마지막 역순 구조

2-3. 라운드 함수

F(r, k) = ROTL( SBOX(r + k), 11 )

구성:

32-bit 덧셈
SBOX (4-bit x 8개)
rotate

3. 취약점 분석

3-1. oracle 제공

서버는 다음 oracle을 제공한다.

query(right, subkey) -> round output

3-2. 의미

이 oracle 을 이용하면:

특정 입력에 대한 SBOX 결과 관찰 가능
rotation 제거 가능

SBOX를 직접 복구할 수 있다.

4. SBOX 복구

4-1. 구조

SBOX : 4-bit -> 4-bit
개수 : 8개

총 경우의 수는 8 x 16 = 128 이다.

4-2. 복구 방법

for i in range(8):
for n in range(16):
y = query(0, n << (4*i))
z = rotr(y, 11)
sboxes[i][n] = (z >> (4*i)) & 0xF

4-3. 결과

전체 SBOW 완전 복원

5. 문제 핵심

5-1. 중요한 관찰

SBOX를 알게되면

F 함수 완전히 재현 가능
F 역함수 구성 가능

5-2. 의미

암호를 black-box가 아니라 white-box로 변환

5-3. 아이디어

암호를 깨는 것이 아니라 출력을 원하는 값으로 맞춘다.

6. 공격 시나리오

6-1. 목표

E(iv, m1) = E(iv, m2)

6-2. 출력 구조 설계

다음과 같은 구조를 정의한다.

(A, 0, 0, 0, 0, 0, A, 0)

Feistel 대칭성 이용

6-3. 라운드 역산

각 라운드에 대해 F(r, k) = target 를 만족하도록 k를 계산

6-4. 역함수 적용

k = inv_sbox( ROTR(target, 11) ) - r

각 라운드 키를 직접 구성 가능

6-5. parameterization

출력 값을 변수 t로 둔다.
A = t, 하나의 t -> 하나의 key 생성

6-6. 충돌 탐색

for t in range(2^16):
key = build_key(t)
enc = encrypt(iv, key)

if enc in seen:
collision

Birthday principle 적용

7. 결과.

충돌 발견:

t1 = 1, t2 = 5

7-1. 메시지

m1 = 159eaf6a89d3f60e154eaf6a89d3f60e154eaf6a89d3f60e159eaf6a89d3f60f
m2 = 15deaf6a89d3f60a154eaf6a89d3f60a154eaf6a89d3f60a15deaf6a89d3f60f

8. 전체 공격 흐름 정리

전체 과정은 다음과 같다.

oracle을 이용해 SBOX 복구
라운드 함수 F 완전 재현
역함수 구성
원하는 출력 구조 설계
각 라운드 key 역산
parameter t 기반 key 생성
birthday 탐색으로 충돌 발견
m1, m2 생성 → 조건 만족

9. 포인트

이 문제의 포인트는 다음과 같다.

oracle -> 내부 구조 완전 복구
SBOX -> 암호 전체를 풀어버린다.
Feistel 대칭성 -> 출력 설계 가능
brute-force가 아니라 구조적 공격

10. 정리

oracle을 이용해 SBOX를 복구하고, 라운드 함수를 역으로 구성하여
동일한 출력이 나오도록 메시지를 설계해 Davies-Meyer 해시 충돌을 만드는 문제

11. 최종 플래그

codegate2026{9a907c6a23bea7b6233ef362173739ef98b656049ce5c58361660b10cce4475d31a6779b31b2d