[crypto] DiceCTF 2026 - carry-the-flame 문제 풀이
1. 문제 개요
본 문제에서는 커스텀 SPN(Substitution-Permutation Network) 암호가 주어집니다.
SPN은 블록 암호를 만들 때 자주 쓰는 기본 구조인데 값을 뒤섞는 치환과 위치를 바꾸는 순열을 여러 번 반복해서 암호화하는 방식이라고 생각하면 되는데요,
문제에서 주어진 파라미터는 다음과 같습니다.
- 블록 크기: 40비트 (5바이트)
- 키 크기: 40비트 (5바이트), 연결마다 무작위로 생성
- S-box: AES S-box를 바이트 단위로 적용
- P-box: 길이 40의 단일 비트 순열
- 라운드 수: 1024
- 라운드 키 사용 방식: 모든 라운드에서 같은 키를 그대로 재사용
여기서 S-box는 입력값을 다른 값으로 치환해 비선형성을 넣는 장치이고 P-box는 비트들의 위치를 섞어서 정보가 퍼지게 만드는 장치입니다.
블록 암호에서는 보통 이 둘을 여러 라운드에 걸쳐 섞어 가며 씁니다.
서버에서는 다음 두 가지를 할 수 있습니다.
1. 원하는 평문을 넣어서 암호화해 볼 수 있음
2. 키를 추측해서 제출할 수 있음
우리는 현재 연결에서 쓰고 있는 키를 맞추면 됩니다.
## 2. 암호 구조
겉으로만 보면 꽤 그럴듯한 SPN처럼 보입니다. 그런데 자세히 보면 키 스케쥴이 안 보입니다.
키 스케줄은 "한 개의 마스터 키로부터 라운드마다 다른 키를 만들어 내는 과정"입니다.
보통 블록 암호는 라운드마다 조금씩 다른 키를 써서 구조가 반복되지 않게 막습니다. 그런데 이 문제에서는 그런 장치가 없습니다.
각 라운드에서는 항상 같은 함수가 적용됩니다.
F_K(x) = P(S(x ⊕ K))
1. 먼저 입력 x에 키 K를 XOR
2. 그 결과를 AES S-box로 바이트 단위 치환
3. 마지막으로 비트 순열 P를 적용
여기서:
- K는 40비트 라운드 키
- S는 바이트 단위 AES S-box
- P는 고정된 40비트 비트 순열
그리고 이 키가 1024개 라운드 내내 한 번도 바뀌지 않습니다. 그래서 전체 암호화는 사실상 다음 한 줄로 요약됩니다.
E = F_K^1024
즉 "같은 함수 F_K를 1024번 반복한 것"이 전부라는 뜻입니다.
이 한 가지 설계 때문에 이 암호는 두 방향에서 동시에 약점이 생깁니다.
- 구조적인 약점: 슬라이드 공격이 가능함
- 크기상의 약점: 키가 40비트라 브루트포스 가능
## 3. 핵심 취약점
이 문제의 본질은 모든 라운드가 완전히 똑같다는 점입니다.
반복형 블록 암호에서는 보통 라운드마다 키가 달라져야 합니다. 그래야 "한 라운드 더 간 상태"와 "그렇지 않은 상태" 사이에 일정한 관계가 생기지 않습니다.
그런데 여기서는 같은 변환을 1024번 되풀이합니다. 그러면 구조 안에 자기 유사성이 생기게 됩니다.
여기서 슬라이드 공격이 가능해집니다.
"어떤 입력이 다른 입력보다 정확히 한 라운드 앞선 상태라면?"이라는 관점으로 쌍을 찾는 방식이라고 보면 됩니다.
게다가 키 길이도 40비트밖에 안 됩니다. 구조적 약점을 전혀 이용하지 않더라도 GPU로 브루트포스를 시도할 만한 크기입니다.
결국 이 문제는 두 가지 풀이가 모두 성립합니다.
- 암호해석 쪽에서 보면 슬라이드 공격이 정석 풀이
- 실전 운영 쪽에서 보면 GPU 브루트포스가 더 빠른 풀이
## 4. 접근 1: 슬라이드 공격
먼저 출제 의도에 더 가까워 보이는 슬라이드 공격부터 보겠습니다.
암호화가 같은 함수 F_K의 반복이라면 "한 단계 밀린 관계"를 가진 입력 쌍이 존재할 수 있습니다. 예를 들어 어떤 평문 쌍 (P_i, P_j)가 다음 조건을 만족한다고 해 봅시다.
P_j = F_K(P_i)
즉, P_j는 P_i에 라운드 하나를 더 적용한 값이라는 뜻입니다.
그러면 대응되는 암호문도 같은 관계를 유지합니다.
C_j = F_K(C_i)
WHY? 전체 암호화가 같은 라운드 함수의 반복이기 때문입니다.
입력 쪽에서 한 라운드 앞서 있으면 출력 쪽에서도 한 라운드 앞선 상태가 그대로 유지됩니다.
이제 이 관계를 실제 계산에 쓸 수 있도록 다음 함수를 정의합니다.
D(x) = S^{-1}(P^{-1}(x))
여기서 S^{-1}와 P^{-1}는 각각 S-box와 P-box의 역연산입니다.
즉, D(x)는 "한 라운드에서 키 XOR만 빼고 나머지를 되돌리는 함수"라고 생각하면 됩니다.
그러면 슬라이드된 쌍 (i, j)에 대해 다음 식이 성립합니다.
P_i ⊕ C_i = D(P_j) ⊕ D(C_j)
이 식이 중요한 이유는, 직접 키를 모르는 상태에서도 비교 가능한 값들을 만들어 준다는 데 있습니다. 결국 공격 문제는 "이 값들이 우연히 맞아떨어지는 쌍을 찾는 문제"로 바뀝니다.
대략 N ≈ 2^20개의 평문/암호문 쌍을 모으면 생일 역설 수준의 충돌을 기대할 수 있습니다.
생일 역설은 "가능한 경우의 수가 충분히 크더라도 표본이 어느 정도 쌓이면 충돌이 생각보다 빨리 나온다"는 직관으로 이해하면 됩니다.
충돌을 하나 찾고 나면 후보 키는 다음처럼 계산할 수 있습니다.
K = P_i ⊕ D(P_j)
그리고 마지막으로 한 번 더 검산해 보면 이 키가 진짜인지 바로 확인할 수 있습니다.
## 5. 슬라이드 공격이 이론적으로 괜찮은 이유
이 공격이 말로만 가능한 게 아니라 실제로도 돌아가는 이유는 서버가 여러 블록을 한 번에 암호화해 준다는 점 때문입니다.
서버는 이어 붙인 hex 입력을 받아서 멀티블록 암호화를 해 줍니다. 덕분에 한 번 요청할 때 블록을 대량으로 묶어 보낼 수 있습니다. 이런 식의 배치 처리가 가능해야 네트워크 왕복 비용을 줄일 수 있습니다.
실제로는 한 번 질의에 대략 2000블록 정도를 담을 수 있었습니다. Write-up에서는 이를 이용해 증가형 hash join 비슷한 방식으로 후보를 관리했습니다.
- X_map: P_i ⊕ C_i를 키로 저장
- Y_map: D(P_i) ⊕ D(C_i)를 키로 저장
- 새 쌍이 들어올 때마다 두 맵을 양방향으로 확인하면서 일찍 충돌이 나는지 검사
여기서 hash join이라는 말이 조금 낯설 수 있는데 데이터베이스에서 두 집합의 공통 키를 빠르게 찾는 기법이라고 생각하면 됩니다. 이 문제에서는 그 아이디어를 충돌 탐색에 가져온 셈입니다.
두 관점 중 어느 쪽에서든 충돌이 하나 나오면 그 순간 슬라이드 쌍 후보를 얻고 후보 키까지 바로 계산할 수 있습니다.
즉 이론만 놓고 보면 슬라이드 공격은 깔끔한 해법입니다.
## 6. 시간 비용 문제
문제는 수식이 아니라 속도였습니다.
서버 쪽 암호화가 Python으로 돌아가고 있었고 블록 하나를 처리하는 데 약 24ms 정도가 걸렸습니다.
배치를 쓰더라도 생일 경계까지 가려면 대략 200만 블록 정도는 모아야 하는데 이걸 실서비스에서 긁어 오는 데는 몇 시간이 걸립니다.
즉 슬라이드 공격은 암호학적으로는 맞는 방향이지만 실제 운영 환경에서는 수집 시간이 너무 길었습니다.
그래서 실제 풀이에서는 좀 더 현실적인 쪽, 즉 브루트포스로 방향을 틀게 됩니다.
## 7. 여러 연결을 이용한 GPU 브루트포스
이제 두 번째 방법입니다. 이쪽은 구조를 깊게 파기보다 키 길이가 짧다는 사실을 정면으로 이용합니다.
브루트포스는 말 그대로 가능한 키를 전부 대입해 보는 방식입니다. 보통은 너무 오래 걸려서 비현실적이지만 키 공간이 충분히 작으면 상황이 달라집니다.
40비트 키 공간은 GPU로 충분히 노려볼 수 있습니다. 실제로 단일 RTX 2060에서 CUDA 구현이 대략 다음 정도의 속도를 냈습니다.
27M keys/s
여기서 중요한 최적화는 여러 연결을 동시에 여는 것이었습니다.
연결마다 서로 다른 랜덤 키가 생성되므로 후보 키 하나를 시험할 때 여러 목표 암호문에 한꺼번에 대조할 수 있습니다.
최종 설정은 다음과 같았습니다.
K = 6 connections
즉, 연결 6개를 동시에 잡아 두고 각 연결에서 얻은 암호문 6개를 한 번에 검사한 것입니다. 그러면 후보 키 하나당 맞을 가능성이 대략 6배쯤 늘어납니다.
## 8. GPU 풀이가 실제로 돌아간 방식
브루트포스 한 라운드는 대략 이렇게 진행됐습니다.
1. 연결 6개를 병렬로 엽니다.
2. ThreadPoolExecutor로 6개의 PoW를 동시에 풉니다.
3. 각 연결에서 E(0)을 질의해 목표 암호문 6개를 얻습니다.
4. 무작위 시작점에서 GPU 브루트포스 커널을 실행합니다.
5. 약 1000초 동안 6개 암호문을 상대로 후보 키를 검사합니다.
PoW는 서버가 접속자에게 먼저 내는 계산 문제입니다. 너무 쉽게 대량 접속하거나 자동화하지 못하게 하는 일종의 작업 증명 장치라고 보면 됩니다.
라운드 하나당 성공 확률은 대략 다음과 같습니다.
6 × 27 × 10^6 × 1000 / 2^40 ≈ 15%
그래서 기대 라운드 수는 대략 6번 정도였습니다.
그런데 실제로는 운이 꽤 좋았습니다. 첫 번째 라운드에서 GPU 탐색 약 30초 만에 정답 키가 나왔습니다.
관측된 출력은 다음과 같았습니다.
```text
[+] KEY FOUND: a5ad67b8ff (matches CT[5]=a99a292eee)
[+] Local verification passed!
[+] Server: flag: dice{t0g3th3r_br0k3n_4ab93cd2e17}
```
## 9. 핵심 파일
풀이에는 두 개의 주요 스크립트가 사용되었습니다.
### 9.1 GPU CUDA Brute Force
- shared memory에 올린 1280엔트리 SP lookup table을 쓰는 CUDA 커널
- 후보 키를 여러 목표 암호문에 동시에 대조하는 brute_multi 커널
- 커널 컴파일과 실행을 담당하는 CuPy
- 여러 연결의 PoW를 병렬로 푸는 ThreadPoolExecutor
여기서 CUDA는 NVIDIA GPU에서 병렬 계산을 돌리기 위한 기술이고 CuPy는 이런 GPU 계산을 Python에서 다루기 쉽게 해 주는 라이브러리입니다.
### 9.2 Slide Attack
들어 있는 내용은 다음과 같습니다.
- 증가형 hash join
- P_i ⊕ C_i를 키로 하는 X_map
- D(P_i) ⊕ D(C_i)를 키로 하는 Y_map
- 조기 종료를 위한 양방향 충돌 검사
- 서버 질의 횟수를 줄이기 위한 2000블록 단위 배치
정리하면, 하나는 "이 문제 구조가 왜 깨지는가"를 잘 보여 주는 풀이이고 다른 하나는 "그래서 실제 플래그는 어떻게 가장 빨리 따는가"에 초점을 맞춘 풀이였습니다.
## 10. 마무리
이 문제는 한 가지 이유로만 깨지는 문제가 아니라 서로 다른 두 약점이 동시에 드러난다는 점이 재밌습니다.
암호학 관점에서 보면, 1024라운드 동안 같은 라운드 키를 재사용한 순간 이미 슬라이드 공격에 취약해졌습니다. 이건 구조적으로 잘못된 설계입니다.
반면 실전 관점에서 보면, 40비트 키는 그냥 너무 짧습니다. 여러 연결을 동시에 잡고 GPU 브루트포스를 돌릴 수 있다면 복잡한 암호해석보다 훨씬 공격이 더 빨라질 수 있습니다.
그래서 이 문제는 두 가지 교훈을 함께 보여 줍니다.
- 같은 키드 라운드 함수를 반복하는 구조는 매우 위험하다
- 40비트 키는 더 이상 브루트포스에 대한 방어선이 되지 못한다
실제로도 이번 풀이에서는 슬라이드 공격으로 오랜 시간 데이터를 모으는 것보다 브루트포스가 훨씬 빨랐습니다. 그래서 최종적으로는 후자가 더 실용적인 해법이 됐습니다.
## 11. 최종 플래그
dice{t0g3th3r_br0k3n_4ab93cd2e17}