[🥈 Silver 1] 키스트림 1비트로 되돌린 SNOW 3G — DreamHack snow 풀이

문제: DreamHack — snow 분류: reversing 난이도: 🥈 Silver 1 FLAG: DH{F805042AC5E59FD07ABEF1E9B2EF}

문제 설명은 딱 한 줄, "눈이 띠용~" 이다. 힌트도 없고 첨부는 prob 하나뿐이다. 우선 어떤 파일인지부터 봤다.

file prob && readelf -h -d prob | grep -E "Type:|Entry|NEEDED|BIND_NOW|FLAGS" && objdump -T prob | grep -E "strcpy|memcmp|strlen|printf"

file 과 readelf 로 확인한 prob 의 기본 정보 — 스트립트된 PIE ELF 이고 import 는 strcpy strlen printf memcmp 뿐이다

제목이 눈(snow)이라 첫인상은 크리스마스 농담 같았는데, 실제로는 이름이 그대로 답이었다.

문제 개요

항목	내용
문제명	snow
난이도	🥈 Silver 1
분류	reversing
제공 파일	`prob` (x86-64 PIE ELF, stripped, 16,568 bytes)
서버	없음 — 오프라인 문제
핵심 기법	SNOW 3G 재구현 + 자기참조 IV 를 8비트 탐색으로 접기

흐름은 이렇다. 바이너리는 32글자짜리 인자를 받아 어떤 변환을 거친 뒤 .data 에 박힌 32바이트와 memcmp 한다.

그 변환에 쓰이는 난수는 3GPP 표준 스트림 암호 SNOW 3G 의 키스트림이고, 키는 소스에 박혀 있다.

문제는 IV 가 우리 입력의 앞 16바이트라는 것. 복원하려는 값이 자기 자신의 암호화에 관여한다.

🧩 배경 — LFSR 하나로 난수를 만든다는 것

스트림 암호는 키와 IV 로 긴 난수열(키스트림)을 뽑아 평문에 XOR 하는 방식이다. 그 난수열의 뼈대로 가장 오래 쓰인 게 선형 되먹임 시프트 레지스터(LFSR)다.

레지스터를 한 칸씩 밀면서, 밀려나는 자리에는 정해진 몇 개 자리를 XOR 한 값을 채워 넣는다. 그림으로 보면 한눈에 들어온다.

Wikimedia Commons 의 16비트 피보나치 LFSR 도식 — 11 13 14 16번 탭을 XOR 해 왼쪽 끝으로 되먹인다

출처: Wikimedia Commons, KCAuXy4p, CC0

LFSR 만 쓰면 주기는 길지만 선형이라 그대로는 안전하지 않다. 그래서 SNOW 계열은 LFSR 위에 비선형 유한상태기계(FSM)를 얹는다.

LFSR 은 32비트 워드 16개(s0~s15)로 되어 있고, FSM 은 32비트 레지스터 세 개(R1, R2, R3)를 굴린다. SNOW 3G 는 이 구조로 3GPP 의 UEA2/UIA2 — LTE 의 암호화·무결성 알고리즘 — 에 들어가 있는 표준이다.

이 문제의 바이너리가 통째로 그 구조다.

직접 그린 SNOW 3G 구조도 — LFSR 16워드에서 s0 s2 s11 을 되먹이고 FSM 이 s5 와 s15 를 받아 z 를 낸다

여기서 우리가 쓸 출력은 맨 왼쪽 상자다. 32비트 워드 z 가 나오는데, 문제는 그 중 최하위 1비트만 쓴다. 이 낭비가 곧 풀이의 열쇠였다.

🔬 정찰 — 심볼이 하나도 없다

file 결과대로 stripped PIE 다. import 목록이 짧아서 오히려 얘기가 빨랐다. strcpy, strlen, printf, puts, memcmp, exit, __stack_chk_fail. 파일 입출력도 네트워크도 없다. 인자 하나 받아서 계산하고 비교하는 게 전부라는 뜻이다.

문자열을 보면 더 분명해진다.

strings -a -t x prob | grep -E "Merr|y-Ch|rist|mas|usage:|length of|Correct|Wrong"

strings 출력 — mas! rist y-Ch Merr 네 조각이 0x1af2 부터 7바이트 간격으로 이어져 나온다

usage: %s <string>, length of string must be 32., Correct!, Wrong... 은 예상대로다.

눈에 걸리는 건 위쪽 네 줄이다. mas!, rist, y-Ch, Merr. 붙여 읽으면 Merry-Christmas! 이고, 조각이 딱 4바이트씩 끊겨 있다.

그리고 오프셋이 .rodata(0x2000대)가 아니라 .text 한복판인 0x1af2 부터 7바이트 간격이다. mov DWORD PTR [rbp-N], imm32 명령의 즉치값 자리라는 뜻이다. 문자열 상수가 아니라 코드에 박힌 32비트 정수 네 개다.

32비트 워드 네 개 = 128비트. 그리고 문제 이름은 snow. 이쯤에서 SNOW 3G 를 의심하고 디스어셈블로 들어갔다.

🧱 갈루아체 곱셈 — 가장 안쪽부터

objdump 로 훑으면 함수 경계가 endbr64 + push rbp 로 깔끔하게 잡힌다. 가장 안쪽에 있는 0x1209 부터 봤다.

주석을 얹기 위해 치환 규칙을 파일로 만들어 뒀다. --cmd 안에 sed 's|...|...|' 를 인라인으로 넣으면 따옴표가 깨지므로 -f 로 부르는 편이 안전하다.

# annot_mulx.sed
s|(c1 e8 07.*shr +eax,0x7)$|\1        <-- V 의 최상위 비트를 뽑는다|
s|(83 e0 01.*and +eax,0x1)$|\1        <-- MSB 만 남긴다|
s|(83 7d fc 01.*cmp +DWORD PTR \[rbp-0x4\],0x1)$|\1   <-- MSB 가 1이면 감산이 필요|
s|(01 c0.*add +eax,eax)$|\1        <-- V << 1|
s|(33 45 e8.*xor +eax,DWORD PTR \[rbp-0x18\])$|\1   <-- ^ c : 기약다항식으로 접는다|

objdump -d -M intel --start-address=0x1209 --stop-address=0x1240 prob | sed -E -f annot_mulx.sed

objdump 로 뽑은 0x1209 함수 — 최상위 비트를 검사해 왼쪽 시프트 후 조건부로 상수를 XOR 하는 MULx 다

읽어 보면 이런 함수다.

uint8_t MULx(uint8_t V, uint8_t c) {
    if (V & 0x80) return ((V << 1) & 0xff) ^ c;
    else          return  (V << 1) & 0xff;
}

GF(2^8) 에서 x 를 곱하는 연산, 흔히 xtime 이라 부르는 것이다. 다만 기약다항식 상수 c 가 하드코딩이 아니라 인자로 들어온다. AES 구현이라면 0x1b 가 코드에 박혀 있었을 텐데 그렇지 않다는 게 첫 번째 단서였다.

바로 뒤 0x1240 은 이 함수를 i 번 재귀 호출한다. i == 0 이면 그대로 반환하고, 아니면 MULx(MULxPOW(V, i-1, c), c). SNOW 3G 명세의 MULxPOW(V, i, c) 그대로다.

이 두 함수가 아래 나오는 모든 것의 부품이 된다.

💣 상자 두 개 — S1 과 S2

0x128b 과 0x1530 은 구조가 똑같고 참조하는 테이블과 상수만 다르다. 32비트 워드를 바이트 넷으로 쪼개고, 각 바이트로 256엔트리 테이블을 조회한 뒤, 결과 넷을 GF 곱셈과 XOR 로 섞어 다시 32비트로 합친다.

첫 번째 행이 어떻게 만들어지는지 보자.

objdump -d -M intel --start-address=0x12c9 --stop-address=0x135b prob | sed -E -f annot_s1.sed

objdump 로 본 S1 의 첫 행 계산 — 0x4020 테이블을 네 번 조회하고 0x1b 로 MULx 를 두 번 부른다

정리하면 r0 = 2·T[b0] ^ T[b1] ^ T[b2] ^ 3·T[b3] 이다. 나머지 세 행도 같은 계수를 한 칸씩 돌려 쓴다.

▶🐛 삽질 1 — 이걸 AES MixColumns 로 읽었다

계수가 2와 3으로만 이루어진 4x4 순환행렬에 테이블이 AES S-box라면, 반사적으로 MixColumns를 떠올리게 된다. 실제로 나도 처음엔 "AES 라운드 하나를 손으로 편 것"으로 읽었다.

그런데 AES MixColumns 의 첫 행은 (2, 3, 1, 1) 이다. 여기 나온 건 (2, 1, 1, 3) 이다. 둘은 서로 전치 관계라서 겉보기 인상이 거의 같고, 그래서 더 헷갈린다.

계수만 AES 쪽으로 바꿔 두고 똑같은 탐색을 돌려 봤다.

# sapjil_mixcolumns.py — 계수를 AES MixColumns 로 바꿨을 때
class MixColumnsBox(Snow3G):
    def _box(self, w, T, c):
        w0, w1, w2, w3 = (w >> 24) & 0xFF, (w >> 16) & 0xFF, (w >> 8) & 0xFF, w & 0xFF
        t0, t1, t2, t3 = T[w0], T[w1], T[w2], T[w3]
        m = lambda v: self.MULx(v, c)
        # AES MixColumns: 각 행이 (2,3,1,1) 을 한 칸씩 돌려 쓴다
        r0 = m(t0) ^ (m(t1) ^ t1) ^ t2 ^ t3
        r1 = t0 ^ m(t1) ^ (m(t2) ^ t2) ^ t3
        r2 = t0 ^ t1 ^ m(t2) ^ (m(t3) ^ t3)
        r3 = (m(t0) ^ t0) ^ t1 ^ t2 ^ m(t3)
        return ((r0 << 24) | (r1 << 16) | (r2 << 8) | r3) & snow3g.M32

python3 sapjil_mixcolumns.py

MixColumns 계수로 바꿔 돌린 결과 — 256가지 가정 중 자기무모순으로 살아남는 후보가 하나도 없다

후보 0개. 이 문제는 답이 맞았는지 틀렸는지를 알려 주는 신호가 마지막 memcmp 하나뿐이라, 중간에 한 글자라도 어긋나면 이렇게 전멸한다. 부분점수가 없다는 게 오히려 다행이었다 — 애매하게 반쯤 맞아 헤매는 일은 없다.

두 상자가 참조하는 테이블은 .data 에 그대로 있다. .data 는 vaddr 0x4000 이 파일 오프셋 0x3000 이라 계산이 간단하다.

# dump_tables.py — .data 에서 SR/SQ 테이블과 memcmp 정답 32바이트를 꺼낸다
import struct
 
BIN = "prob"
DELTA = 0x1000  # vaddr -> file offset
 
data = open(BIN, "rb").read()
 
 
def dwords(vaddr, n):
    off = vaddr - DELTA
    return list(struct.unpack_from("<%dI" % n, data, off))
 
 
SR = dwords(0x4020, 256)   # S1 이 참조하는 테이블
SQ = dwords(0x4420, 256)   # S2 가 참조하는 테이블
TARGET = data[0x4820 - DELTA: 0x4820 - DELTA + 32]
 
print("SR[0:16]  =", " ".join("%02x" % v for v in SR[:16]))
print("SQ[0:16]  =", " ".join("%02x" % v for v in SQ[:16]))
print("SR 최대값 =", hex(max(SR)), "/ SQ 최대값 =", hex(max(SQ)))
print("SR 은 순열인가:", sorted(SR) == list(range(256)))
print("SQ 은 순열인가:", sorted(SQ) == list(range(256)))
# AES S-box 첫 줄과 대조 (63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76)
aes = [0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5,
       0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76]
print("SR == AES S-box 첫 16개:", SR[:16] == aes)
print()
print("TARGET(32B) =", TARGET.hex())
print("TARGET ascii =", "".join(chr(c) if 32 <= c < 127 else "." for c in TARGET))

python3 dump_tables.py

dump_tables.py 출력 — 0x4020 은 AES S-box 와 완전히 일치하고 0x4420 은 25 24 73 67 로 시작하는 다른 순열이다

0x4020 은 AES S-box 다. 0x4420 은 25 24 73 67 d7 ae 5c 30 ... 으로 시작하는 또 다른 256 순열인데, 이게 SNOW 3G 명세의 SQ 박스다. 두 상자가 각각 c = 0x1b 와 c = 0x69 를 쓰는 것까지 명세와 같다.

그리고 0x4820 의 32바이트가 memcmp 상대, 즉 우리가 도달해야 할 목표다. ASCII 로는 아무 의미가 없다.

🧭 alpha 곱셈 — 지문은 여기 있었다

여기까지도 "AES 부품을 쓰는 뭔가"일 뿐이다. 결정타는 0x1845 였다.

objdump -d -M intel --start-address=0x1855 --stop-address=0x18bc prob | sed -E -f annot_alpha.sed

objdump 로 본 MULalpha — 같은 입력에 대해 지수 23 245 48 239 로 MULxPOW 를 네 번 부르고 c 는 0xa9 로 고정이다

MULxPOW(c, 23, 0xa9), MULxPOW(c, 245, 0xa9), MULxPOW(c, 48, 0xa9), MULxPOW(c, 239, 0xa9).

이 네 숫자 조합은 다른 데서 나올 수가 없다. SNOW 3G 명세의 MULalpha 그대로다. 바로 아래 0x18bc 는 16, 39, 6, 64 를 쓰는데 그건 DIValpha 다.

여기서부터는 명세를 옆에 두고 대조하는 작업이 됐다. 0x17d3 은 FSM 클럭이다.

F  = (s15 + R1) ^ R2;      // 32비트 덧셈은 mod 2^32
r  = R2 + (R3 ^ s5);
R3 = S2(R2);
R2 = S1(R1);
R1 = r;
return F;

0x1933 은 LFSR 클럭인데, 첫 인자가 0x69(문자 'i') 냐 0x6b(문자 'k') 냐로 초기화 모드와 키스트림 모드를 가른다.

v = (s0 << 8) ^ MULalpha(s0 >> 24) ^ s2 ^ (s11 >> 8) ^ DIValpha(s11 & 0xff);
if (mode == 'i') v ^= F;
for (i = 0; i < 15; i++) s[i] = s[i+1];
s15 = v;

명세와 한 글자도 다르지 않다. 문제 이름 snow 는 농담이 아니라 그냥 정답 표기였다.

🔑 키와 IV — 여기가 급소다

이제 앞에서 본 Merry-Christmas! 조각이 어디로 들어가는지 볼 차례다.

objdump -d -M intel --start-address=0x1aef --stop-address=0x1b6c prob | sed -E -f annot_init.sed

objdump 로 본 Initialize — 키 네 워드가 즉치값으로 박히고 IV 는 입력 버퍼의 0 4 8 12 오프셋에서 읽힌다

키는 k[0]=0x2173616d, k[1]=0x74736972, k[2]=0x68432d79, k[3]=0x7272654d 로 고정이다. 리틀엔디언 바이트로 펴면 mas! rist y-Ch Merr 이고, 워드를 뒤에서부터 읽으면 Merry-Christmas! 가 된다.

IV 는 다르다. rbp-0x38 에 들어온 포인터 — 즉 사용자 입력 버퍼 — 에서 0, 4, 8, 12 오프셋의 32비트를 그대로 읽는다.

정리하면 LFSR 초기 상태는 이렇게 채워진다. F 는 0xffffffff 다.

슬롯	값	슬롯	값
s15	`k[3] ^ IV[0]`	s7	`k[3]`
s14	`k[2]`	s6	`k[2]`
s13	`k[1]`	s5	`k[1]`
s12	`k[0] ^ IV[1]`	s4	`k[0]`
s11	`k[3] ^ F`	s3	`k[3] ^ F`
s10	`k[2] ^ F ^ IV[2]`	s2	`k[2] ^ F`
s9	`k[1] ^ F ^ IV[3]`	s1	`k[1] ^ F`
s8	`k[0] ^ F`	s0	`k[0] ^ F`

그다음 32라운드를 초기화 모드로 돌리고, 마지막에 ClockFSM() 을 한 번 더 부르고 반환값을 버린다. 0x1c22 의 그 한 줄이 있고 없고로 이후 모든 키스트림이 달라진다.

▶🐛 삽질 2 — 명세 감각대로 두면 안 되는 두 자리

표준 문서를 옆에 두고 옮기다 보면 손이 먼저 나가는 자리가 있다. 두 개를 실제로 틀리게 만들어 돌려 봤다.

하나는 위에서 말한 초기화 꼬리의 ClockFSM() 이다. 32라운드로 끝났다고 생각하기 쉽다.

다른 하나는 IV 워드의 바이트 순서다. 명세에서 IV 는 IV[0] 이 최상위인 것처럼 표기되는데, 이 바이너리는 mov eax, DWORD PTR [rax] 로 그냥 읽는다. x86 이니 리틀엔디언이다. 빅엔디언으로 조립하면 조용히 다른 값이 된다.

# sapjil_variants.py — 초기화 꼬리를 빼거나 IV 를 빅엔디언으로 읽으면
def main():
    _, _, TARGET = load_tables("prob")
    for name, cls, be in (("binary ", Snow3G, False),
                          ("no_tail", NoTailFSM, False),
                          ("be_iv  ", Snow3G, True)):
        surv, printable = run(cls, TARGET, be)
        head = printable[0].decode() if printable else "-"
        print("%s 자기무모순 %d개 / printable %d개   앞 16바이트: %s" %
              (name, len(surv), len(printable), head))

python3 sapjil_variants.py

세 변종 비교 출력 — 바이너리 그대로면 printable 1개가 나오지만 꼬리를 빼거나 빅엔디언이면 0개다

둘 다 printable 후보 0개다.

재미있는 건 자기무모순 후보가 3개, 2개씩은 여전히 나온다는 점이다. "몇 개 살아남았다"는 것 자체는 아무 보증이 안 된다. 살아남은 값이 읽을 수 있는 글자인가까지 봐야 비로소 신호가 된다.

덧붙이면, 호출 순서는 틀려도 티가 안 난다. 명세는 워드를 먼저 뽑고 LFSR 을 미는데 이 바이너리는 반대다. 그런데 명세가 초기화 직후 클럭을 한 번 더 넣으라고 하기 때문에 결국 같은 수열이 나온다. 이건 확인해 보고 나서야 알았다.

🎯 main 이 하는 일

이제 마지막 조각이다.

objdump -d -M intel --start-address=0x1d22 --stop-address=0x1db8 prob | sed -E -f annot_main.sed

objdump 로 본 main 의 변환 루프 — 워드마다 0x3f2c 를 XOR 하고 키스트림 최하위 비트가 1이면 16비트 NOT 을 건다

C 로 옮기면 이게 전부다.

if (argc != 2)              { printf("usage: %s <string>", argv[0]); exit(-1); }
if (strlen(argv[1]) != 32)  { puts("length of string must be 32."); exit(-1); }
 
char buf[32] = {0};
strcpy(buf, argv[1]);
Initialize(buf);                      // IV = buf[0..15]
 
for (int i = 0; i < 16; i++) {
    uint16_t *w = (uint16_t *)(buf + 2*i);
    *w ^= 0x3f2c;
    if (GenerateKeystream() & 1)      // 32비트 워드에서 최하위 1비트만
        *w = ~*w;
}
puts(memcmp(target, buf, 32) == 0 ? "Correct!" : "Wrong...");

32비트 키스트림 워드를 통째로 뽑아 놓고 1비트만 쓴다. 나머지 31비트는 버린다.

암호학적으로는 아깝지만, 푸는 쪽에서는 이게 전부다. 워드 하나를 되돌리는 데 필요한 정보가 한 비트뿐이라는 뜻이니까.

💡 핵심 — 자기참조를 8비트로 접는다

처음 이 구조를 보고 든 생각은 "닭이 먼저냐"였다. 키스트림을 알아야 입력을 되돌리는데, 키스트림은 그 입력의 앞 16바이트로 만들어진다.

그런데 조금만 들여다보면 고리가 생각보다 얇다.

목표 워드를 t_i, 키스트림 워드를 z_i 라 하자. 변환은 XOR 한 번과 조건부 NOT 한 번뿐이고 둘 다 자기역원이다. 그래서 역산은 이렇게 끝난다.

z_i 의 최하위 비트가 0 이면   원래 워드 = t_i ^ 0x3f2c
z_i 의 최하위 비트가 1 이면   원래 워드 = (~t_i) ^ 0x3f2c

워드 하나당 미지수는 딱 1비트다.

그리고 IV 를 이루는 것은 앞 16바이트, 즉 워드 0~~7 이다. 이 여덟 개만 정해지면 키스트림 전체가 결정된다. 뒤쪽 워드 8~~15 는 IV 에 아무 영향을 주지 않는다.

그러니 절차는 이렇게 된다.

b0..b7 여덟 비트를 가정한다 — 경우의 수 256.
그 가정으로 앞 16바이트를 역산해 IV 를 만든다.
그 IV 로 SNOW 3G 를 실제로 돌려 z_0..z_7 을 뽑는다.
뽑힌 최하위 비트들이 가정과 같은지 본다. 다르면 그 가정은 자기모순이니 버린다.
살아남은 가정에서 z_8..z_15 로 뒤 16바이트를 마저 역산한다.

2^128 처럼 보이던 문제가 2^8 이 된다. 노트북에서 1초도 안 걸린다.

🚀 Full Exploit

SNOW 3G 부분은 파일을 나눠 뒀다. 명세를 옮긴 게 아니라 디스어셈블리를 옮긴 것이라, 위에서 확인한 주소를 주석에 남겼다.

# snow3g.py
"""prob 안에 박혀 있는 SNOW 3G 를 파이썬으로 그대로 옮긴 것.
 
바이너리에서 확인한 대응 관계:
  0x1209 MULx(V, c)            0x1240 MULxPOW(V, i, c)
  0x128b S1(w)  <- SR @0x4020, c=0x1b
  0x1530 S2(w)  <- SQ @0x4420, c=0x69
  0x1845 MULalpha(c)           0x18bc DIValpha(c)
  0x17d3 ClockFSM()            0x1933 ClockLFSR(mode, F)   mode 0x69='i' / 0x6b='k'
  0x1adf Initialize(buf)       0x1c2f GenerateKeystream()
LFSR s0..s15 는 .bss 0x4860, R1/R2/R3 는 0x48a0/0x48a4/0x48a8 (전부 0으로 시작).
"""
import struct
 
DELTA = 0x1000  # .data: vaddr 0x4000 == file offset 0x3000
 
M32 = 0xFFFFFFFF
# 바이너리 안 고정 키. 워드 단위로 뒤집혀 있어 k[3]..k[0] 을 이어 붙이면 "Merry-Christmas!".
KEY = [0x2173616D, 0x74736972, 0x68432D79, 0x7272654D]
 
 
def load_tables(path="prob"):
    data = open(path, "rb").read()
    sr = list(struct.unpack_from("<256I", data, 0x4020 - DELTA))
    sq = list(struct.unpack_from("<256I", data, 0x4420 - DELTA))
    target = data[0x4820 - DELTA: 0x4820 - DELTA + 32]
    return sr, sq, target
 
 
class Snow3G:
    def __init__(self, sr, sq):
        self.SR, self.SQ = sr, sq
 
    # --- GF(2^8) 헬퍼 -------------------------------------------------
    @staticmethod
    def MULx(V, c):
        return ((V << 1) & 0xFF) ^ c if V & 0x80 else (V << 1) & 0xFF
 
    def MULxPOW(self, V, i, c):
        for _ in range(i):
            V = self.MULx(V, c)
        return V & 0xFF
 
    def _box(self, w, T, c):
        """S1/S2 공통 골격 — 테이블과 기약다항식 상수만 다르다."""
        w0, w1, w2, w3 = (w >> 24) & 0xFF, (w >> 16) & 0xFF, (w >> 8) & 0xFF, w & 0xFF
        t0, t1, t2, t3 = T[w0], T[w1], T[w2], T[w3]
        m = lambda v: self.MULx(v, c)
        r0 = m(t0) ^ t1 ^ t2 ^ m(t3) ^ t3
        r1 = m(t0) ^ t0 ^ m(t1) ^ t2 ^ t3
        r2 = t0 ^ m(t1) ^ t1 ^ m(t2) ^ t3
        r3 = t0 ^ t1 ^ m(t2) ^ t2 ^ m(t3)
        return ((r0 << 24) | (r1 << 16) | (r2 << 8) | r3) & M32
 
    def S1(self, w):
        return self._box(w, self.SR, 0x1B)
 
    def S2(self, w):
        return self._box(w, self.SQ, 0x69)
 
    def MULalpha(self, c):
        return ((self.MULxPOW(c, 23, 0xA9) << 24) | (self.MULxPOW(c, 245, 0xA9) << 16) |
                (self.MULxPOW(c, 48, 0xA9) << 8) | self.MULxPOW(c, 239, 0xA9))
 
    def DIValpha(self, c):
        return ((self.MULxPOW(c, 16, 0xA9) << 24) | (self.MULxPOW(c, 39, 0xA9) << 16) |
                (self.MULxPOW(c, 6, 0xA9) << 8) | self.MULxPOW(c, 64, 0xA9))
 
    # --- 상태 갱신 ----------------------------------------------------
    def ClockFSM(self):
        s = self.s
        F = ((s[15] + self.R1) & M32) ^ self.R2
        r = (self.R2 + (self.R3 ^ s[5])) & M32
        self.R3 = self.S2(self.R2)
        self.R2 = self.S1(self.R1)
        self.R1 = r
        return F
 
    def ClockLFSR(self, mode, F=0):
        s = self.s
        v = (((s[0] << 8) & M32) ^ self.MULalpha(s[0] >> 24) ^ s[2] ^
             (s[11] >> 8) ^ self.DIValpha(s[11] & 0xFF))
        if mode == "i":
            v ^= F
        self.s = s[1:] + [v & M32]
 
    # --- 키 스케줄 / 키스트림 ----------------------------------------
    def initialize(self, iv):
        k, F = KEY, 0xFFFFFFFF
        self.s = [
            k[0] ^ F, k[1] ^ F, k[2] ^ F, k[3] ^ F,          # s0..s3
            k[0], k[1], k[2], k[3],                          # s4..s7
            k[0] ^ F, k[1] ^ F ^ iv[3], k[2] ^ F ^ iv[2], k[3] ^ F,   # s8..s11
            k[0] ^ iv[1], k[1], k[2], k[3] ^ iv[0],          # s12..s15
        ]
        self.R1 = self.R2 = self.R3 = 0
        for _ in range(32):
            self.ClockLFSR("i", self.ClockFSM())
        self.ClockFSM()   # 초기화 마지막 한 번 — 반환값은 버린다
 
    def keystream_word(self):
        self.ClockLFSR("k")
        return (self.ClockFSM() ^ self.s[0]) & M32

풀이 본체는 위에서 정리한 다섯 단계를 그대로 옮긴 것이다.

# solve.py
"""snow (Dreamhack, Silver 1 / reversing) 풀이.
 
main 이 하는 일:
    strlen(argv[1]) == 32 강제 → 32바이트를 스택 버퍼로 strcpy
    Initialize(buf)            ← IV = buf[0:16] (u32 4개, 리틀엔디언)
    for i in 0..15:
        w  = *(u16*)(buf+2i);  w ^= 0x3f2c;  *(u16*)(buf+2i) = w
        z  = GenerateKeystream()
        if z & 1:  *(u16*)(buf+2i) = ~w
    memcmp(TARGET, buf, 32) == 0  → "Correct!"
 
핵심: 키스트림은 IV, 즉 **입력의 앞 16바이트에만** 의존한다. 그런데 그 앞 16바이트는
워드 0~7 이고, 각 워드의 역산은 z_i 의 LSB 한 비트만 알면 끝난다.
따라서 b0..b7 8비트(=256가지)만 가정하면 앞 16바이트가 정해지고, 그걸로 실제
키스트림을 돌려 가정이 자기모순이 아닌지 확인하면 된다. 살아남은 후보에서
z_8..z_15 로 뒷 16바이트를 마저 역산한다.
"""
import struct
import sys
 
from snow3g import Snow3G, load_tables
 
XOR = 0x3F2C
 
 
def words_of(buf):
    return list(struct.unpack("<16H", buf))
 
 
def invert(target_w, bit):
    """정답 워드와 z 의 LSB 로 원래 입력 워드를 되돌린다."""
    w = (~target_w) & 0xFFFF if bit else target_w
    return w ^ XOR
 
 
def main():
    SR, SQ, TARGET = load_tables(sys.argv[1] if len(sys.argv) > 1 else "prob")
    tw = words_of(TARGET)
    print("TARGET   :", TARGET.hex())
 
    hits = []
    for guess in range(256):
        bits = [(guess >> i) & 1 for i in range(8)]
        head = b"".join(struct.pack("<H", invert(tw[i], bits[i])) for i in range(8))
        iv = list(struct.unpack("<4I", head))
 
        c = Snow3G(SR, SQ)
        c.initialize(iv)
        z = [c.keystream_word() for _ in range(16)]
 
        if [zi & 1 for zi in z[:8]] != bits:      # 가정이 자기모순이면 버린다
            continue
        tail = b"".join(struct.pack("<H", invert(tw[8 + i], z[8 + i] & 1)) for i in range(8))
        hits.append((guess, head + tail, z))
 
    print("가정 256개 중 자기모순 없이 살아남은 것:", len(hits))
    answer = None
    for guess, cand, z in hits:
        printable = all(32 <= b < 127 for b in cand)
        print("  b0..b7=0x%02x  printable=%-5s  %s" % (
            guess, printable, cand.decode() if printable else cand.hex()))
        if not printable:
            continue
 
        # 정방향으로 다시 돌려 memcmp 가 실제로 통과하는지 확인
        buf = bytearray(cand)
        c = Snow3G(SR, SQ)
        c.initialize(list(struct.unpack("<4I", cand[:16])))
        for i in range(16):
            w = struct.unpack_from("<H", buf, 2 * i)[0] ^ XOR
            if c.keystream_word() & 1:
                w = (~w) & 0xFFFF
            struct.pack_into("<H", buf, 2 * i, w)
        ok = bytes(buf) == TARGET
        print("  정방향 재현 =", bytes(buf).hex(), "→ 일치" if ok else "→ 불일치")
        if ok:
            answer = cand.decode()
 
    if answer:
        print()
        print("ANSWER:", answer)
 
 
if __name__ == "__main__":
    main()

python3 solve.py

solve.py 실행 결과 — 256가지 중 4개가 자기무모순으로 남고 그 중 읽을 수 있는 하나가 플래그다

살아남은 후보가 4개다. 나머지 셋은 바이트가 깨져 있어 32글자 문자열로 성립하지 않는다.

읽히는 하나는 DH{F805042AC5E59FD07ABEF1E9B2EF}. 정방향으로 다시 돌려 봐도 .data 의 32바이트와 정확히 같다.

🧪 검증 — 모델이 정말 그 바이너리인가

파이썬으로 옮긴 게 진짜 이 바이너리와 같은지는 따로 확인해야 한다. 정답 하나가 맞았다는 것만으로는 우연일 여지가 남는다.

PIE 라 주소를 관례로 가정하면 안 된다. gdb 배치 스크립트 안에서 info proc mappings 로 로드 베이스를 직접 읽었다.

# verify.gdb
set confirm off
set pagination off
set args DH{F805042AC5E59FD07ABEF1E9B2EF}
starti
python
import gdb
base = None
for ln in gdb.execute("info proc mappings", to_string=True).splitlines():
    f = ln.split()
    if len(f) >= 5 and f[-1].endswith("/prob"):
        base = int(f[0], 16)
        break
gdb.execute("set $b = 0x%x" % base)
print("PIE base = 0x%x  (관례 가정 금지 — info proc mappings 로 읽었다)" % base)
end
break *($b + 0x1d22)
break *($b + 0x1d99)
continue
printf "\n[Initialize 직후] LFSR s0..s15\n"
x/16xw $b+0x4860
printf "[Initialize 직후] R1 R2 R3\n"
x/3xw $b+0x48a0
continue
printf "\n[memcmp 직전] 변환된 입력 버퍼 32바이트\n"
x/32xb $rbp-0x30
printf "[memcmp 직전] .data 0x4820 의 정답 32바이트\n"
x/32xb $b+0x4820
continue

gdb -q -batch -x verify.gdb ./prob

gdb 런타임 확인 — Initialize 직후 LFSR 16워드와 R1 R2 R3 를 덤프하고 memcmp 직전 버퍼가 정답과 같음을 보인다

두 지점을 봤다. Initialize 가 끝난 직후의 LFSR 16워드와 FSM 세 레지스터, 그리고 memcmp 직전 스택 버퍼와 .data 의 목표값.

버퍼 32바이트가 목표와 바이트 단위로 같고, 마지막에 Correct! 가 찍힌다.

이제 파이썬 모델이 같은 중간 상태를 만드는지 대조한다.

# check_state.py — 실측치를 박아 두고 파이썬 모델과 비교한다
GDB_LFSR = [0xFF22D888, 0xA8777BA5, 0x6992F244, 0xCAF46272,
            0xC38C6DE9, 0xA1D77FA2, 0x25B7F11C, 0xC3A147A3,
            0xA402D8F2, 0xADFBD6E5, 0xAE331D05, 0x69DC8CA7,
            0x747420EA, 0xF3530624, 0x12AD67EE, 0xC8007FAB]
GDB_FSM = [0xC0B7C911, 0xF64EB4D7, 0xFF628DC0]
 
SR, SQ, TARGET = load_tables("prob")
c = Snow3G(SR, SQ)
c.initialize(list(struct.unpack("<4I", FLAG.encode()[:16])))
 
print("파이썬 모델 s0..s15")
for i in range(0, 16, 4):
    print("  s%-2d " % i, " ".join("0x%08x" % v for v in c.s[i:i + 4]))
print("파이썬 모델 R1 R2 R3")
print("      ", " ".join("0x%08x" % v for v in (c.R1, c.R2, c.R3)))
print()
print("gdb 실측 LFSR 과 일치 :", c.s == GDB_LFSR)
print("gdb 실측 FSM  과 일치 :", [c.R1, c.R2, c.R3] == GDB_FSM)

python3 check_state.py

check_state.py 출력 — 파이썬 모델의 LFSR 16워드와 FSM 세 값이 gdb 로 읽은 실제 메모리와 모두 일치한다

32라운드 초기화를 거친 뒤의 중간 상태 19개 워드가 전부 일치한다. 최종 결과 하나가 아니라 중간이 맞아떨어지니, 우연히 답만 맞은 게 아니라는 근거가 된다.

✅ 진짜 바이너리로 한 번 더

마지막은 배포된 실행 파일에 직접 먹여 보는 것이다. 파이프 대신 subprocess 로 인자를 넘긴다.

# verify.py
import subprocess
 
flag = "DH{F805042AC5E59FD07ABEF1E9B2EF}"
r = subprocess.run(["./prob", flag], capture_output=True, text=True)
print("Input  :", flag, "(len=%d)" % len(flag))
print("Output :", r.stdout.strip())
 
wrong = "DH{F805042AC5E59FD07ABEF1E9B2Ef}"      # 마지막 글자 하나만 바꾼 것
r2 = subprocess.run(["./prob", wrong], capture_output=True, text=True)
print("Input  :", wrong, "(한 글자 변조)")
print("Output :", r2.stdout.strip())

python3 verify.py

verify.py 출력 — 복원한 32글자는 Correct! 를 내고 마지막 글자 하나만 바꾸면 Wrong... 이 나온다

한 글자만 대소문자를 바꿔도 바로 Wrong... 이다. 우연히 통과할 여지가 없다는 확인이다.

백업본만 가지고도 다시 플래그를 뽑을 수 있게, 빌드부터 대조까지 한 방에 도는 스크립트를 남겼다.

#!/usr/bin/env bash
# snow (Dreamhack, Silver 1 / reversing) — 한 방 재현.
# 배포 바이너리 prob 하나만 있으면 된다. 테이블·정답 32바이트를 .data 에서 직접 읽으므로
# 별도 입력 파일이 없다. 파이썬 3 만 있으면 어디서든 돈다(외부 패키지 없음).
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
EXPECT=$(python3 -c "import json;print(json.load(open('../문제.json'))['flag'])" 2>/dev/null || echo '')
 
chmod +x prob 2>/dev/null || true
 
OUT=$(timeout 300 python3 solve.py 2>&1) || true
echo "$OUT" | tail -8
 
# 후보 목록에도 DH{ 로 시작하는 깨진 문자열이 섞이므로 마지막 ANSWER 줄에서만 뽑는다.
FLAG=$(printf '%s' "$OUT" | sed -n 's/^ANSWER: //p' | tail -1)
 
# 뽑은 값을 배포 바이너리에 그대로 먹여 Correct! 가 나오는지까지 본다.
if [ -n "$FLAG" ]; then
  VERDICT=$(./prob "$FLAG" 2>&1 || true)
  echo "./prob '$FLAG' → $VERDICT"
else
  VERDICT=""
fi
 
if [ -n "$FLAG" ] && [ "$VERDICT" = "Correct!" ] && { [ -z "$EXPECT" ] || [ "$FLAG" = "$EXPECT" ]; }; then
  echo; echo "✅ PASS  $FLAG"; exit 0
fi
echo; echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 바이너리 판정: '${VERDICT:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh

reproduce.sh 실행 결과 — 플래그를 뽑고 배포 바이너리로 Correct! 까지 확인한 뒤 PASS 로 끝난다

로컬 환경: Ubuntu 22.04 · x86-64 · Python 3.10(외부 패키지 없음) · binutils 2.38 의 objdump · GNU gdb 12.1. 문제 바이너리는 for GNU/Linux 3.2.0 로 빌드된 것이라 요즘 배포판에서도 그대로 돈다.

📝 결론

표준 알고리즘은 상수로 찾는 게 빠르다

디스어셈블리를 위에서부터 다 읽을 필요는 없었다. MULxPOW 의 지수 23, 245, 48, 239 와 상수 0xa9 — 이 조합 하나가 "SNOW 3G 다"를 확정해 줬다.

AES S-box 는 여러 알고리즘이 빌려 쓰니 그것만으로는 부족하다. 반면 alpha 곱셈의 지수 네 개는 그 알고리즘에만 있다. 낯선 암호 루틴을 만나면 가장 특이한 상수부터 검색하는 게 함수 이름 없는 바이너리에서 제일 빠른 길이다.

출력을 버리는 지점이 곧 공격면이다

이 문제의 급소는 SNOW 3G 자체가 아니라, 32비트를 뽑아 1비트만 쓴 설계였다. 워드마다 미지수가 1비트로 줄어드니 자기참조 고리가 8비트로 접힌다.

암호 알고리즘이 아무리 튼튼해도 그걸 쓰는 코드가 정보를 버리면 그 자리가 탐색 공간이 된다. 실무에서도 "해시의 앞 4바이트만 쓴다", "난수의 하위 비트만 쓴다" 같은 절약이 같은 방식으로 무너진다.

후보가 살아남았다는 것 자체는 증거가 아니다

자기무모순 검사만으로 256개 중 4개가 남았다. 잘못된 모델(초기화 꼬리 누락, 빅엔디언 IV)에서도 2~3개는 남았다. "몇 개 살아남았다"는 사실은 모델이 맞다는 보증이 전혀 안 된다.

판정은 밖에서 온 독립 기준이어야 한다. 여기서는 printable 여부, 정방향 재현, 그리고 실제 바이너리의 Correct! 셋이었다.

IV 를 사용자 입력으로 두면 재현성이 사라진다

방어 관점으로 옮기면 이 문제 코드는 IV 를 검증 없이 사용자 입력에서 가져온다. 진짜 서비스라면 IV 는 매번 새로 뽑아 암호문과 함께 저장하거나, 최소한 카운터로 관리해야 한다.

같은 IV 를 재사용하면 키스트림이 그대로 반복되고, 지금처럼 IV 를 공격자가 고를 수 있으면 키스트림을 원하는 방향으로 유도할 수 있다. 스트림 암호에서 nonce 재사용이 치명적인 이유가 이것이다.

[🥈 Silver 1] 키스트림 1비트로 되돌린 SNOW 3G — DreamHack snow 풀이

댓글

관련 글

[🥈 Silver 3] 2MB 바이너리에서 코드는 509바이트뿐이었다 — DreamHack Branches and Leaves 풀이

[🥈 Silver 3] srand(0xBEEF) 하나로 6MB 사진을 되찾다 — DreamHack photographer 풀이

[🥈 Silver 2] Rust 크랙미의 비트 치환을 거꾸로 돌려 64글자 입력 복원 — DreamHack CrabME 풀이