TL;DR

스도쿠 판을 복원한 뒤 빈칸이 적은 행부터 9자리 숫자로 나열해 입력값을 구성한다
각 9자리 입력은 내부에서 천 단위로 세 조각으로 나뉘어 27바이트 키스트림을 만든다
하드코딩된 39바이트 암호문과 키스트림을 XOR해야한다.

Analysis

Ukodus/ukodus의 main은 시작과 동시에 .rodata의 9x9 정수 보드를 지역 버퍼로 복사한다.

1
; Ukodus/ukodus@0x1391
2
1391: 48 8d 15 e8 0c 00 00    lea   rdx, [rip+0xce8]    ; 0x2080
3
1398: b9 28 00 00 00          mov   ecx, 0x28
4
13a3: f3 48 a5                rep   movsq                ; 40개의 qword 복사
5
13ac: 8b 0a                   mov   ecx, dword ptr [rdx]
6
13ae: 89 08                   mov   dword ptr [rax], ecx ; 남은 1개 보정

0x2080에 저장된 값은 스도쿠 퍼즐 형태다. 0을 빈칸으로 해석하면 다음과 같이 정리된다.

1
puzzle = [
2
    [8, 6, 7, 2, 0, 0, 0, 0, 5],
3
    [0, 0, 9, 0, 3, 8, 0, 0, 0],
4
    [0, 0, 3, 0, 0, 0, 2, 0, 0],
5
    [0, 2, 0, 0, 0, 4, 0, 0, 0],
6
    [9, 0, 0, 5, 0, 2, 0, 0, 7],
7
    [0, 0, 0, 8, 0, 0, 0, 6, 0],
8
    [0, 0, 8, 0, 0, 0, 5, 0, 0],
9
    [0, 0, 0, 6, 8, 0, 7, 0, 0],
10
    [5, 0, 0, 0, 0, 1, 6, 2, 8],
11
]

바로 이어지는 39개의 mov dword ptr [rbp - off], imm 구간이 암호문을 초기화한다.

1
; Ukodus/ukodus@0x13b0
2
13b0: c7 85 10 fe ff ff 2b 03 00 00    mov dword ptr [rbp-0x1f0], 0x32b
3
13ba: c7 85 14 fe ff ff ce 00 00 00    mov dword ptr [rbp-0x1ec], 0xce
4
...                                    ; 총 39개, 4바이트씩
5
152c: c7 85 a8 fe ff ff a1 01 00 00    mov dword ptr [rbp-0x158], 0x1a1

이 배열이 그대로 39바이트 $C_i$ 가 된다.

이후 main은 9회 반복 입력을 받아 각 줄을 세 분할로 저장한다. 분할은 곱셈-시프트 기반 정수 나눗셈으로 구현되어 있다.

1
; Ukodus/ukodus@0x15b5
2
15b5: 8b 85 8c fd ff ff          mov eax, dword ptr [rbp-0x274] ; scanf 입력
3
15bb: 48 69 d0 d3 4d 62 10       imul rdx, rax, 0x10624dd3      ; /1000 준비
4
15cc: c1 f8 1f                   sar eax, 0x1f
5
15d1: 8b 8d 90 fd ff ff          mov ecx, dword ptr [rbp-0x270] ; 현재 행 index
6
15db: 01 c8                      add eax, ecx                   ; 3*row + 1
7
15e0: 48 63 c2                   movsxd rax, edx
8
15f8: 69 f0 e8 03 00 00          imul esi, eax, 0x3e8           ; *1000
9
1600: 29 f0                      sub eax, esi                   ; 나머지 추출
10
1605: 89 84 95 a0 fd ff ff       mov dword ptr [rbp+4*rdx-0x260], eax

같은 패턴이 오프셋 +0, +1, +2로 반복되며 한 행의 9자리 숫자를 ABC DEF GHI $\rightarrow$ [ABC, DEF, GHI] 세 조각으로 변환한다.

입력 전에는 행마다 빈칸 수를 기록해 정렬 순서를 사용자에게 알려주는 보조 함수가 존재한다.

1
; Ukodus/ukodus@0x130b (pmitonsicnufsihtknihtuoyod)
2
130b: 48 8d 05 0e 0d 00 00       lea rax, [rip+0xd0e] ; "[ n[i], zero_count ] (sorted):"
3
1315: e8 86 fd ff ff             call puts
4
1323: 8b 54 c5 b4                mov edx, dword ptr [rbp+8*rax-0x4c] ; zero_count
5
1331: 8b 44 c5 b0                mov eax, dword ptr [rbp+8*rax-0x50] ; 행 index
6
1337: 48 8d 05 02 0d 00 00       lea rax, [rip+0xd02] ; "[%d, %d]\n"
7
1346: e8 75 fd ff ff             call printf

스도쿠 원본에서 0의 개수를 세어 보면 [4, 6, 7, 7, 5, 7, 7, 6, 4]이며, 안정 정렬 결과 행 순서는 0, 8, 4, 1, 7, 2, 3, 5, 6이 된다. 프로그램은 이 순서를 플레이어에게 노출할 뿐 자동으로 재정렬하지 않으므로, 입력을 해당 순서로 준비해야 키스트림이 맞춰진다.

분해된 27개의 정수는 최종 루프에서 인덱스 i % 27로 순환 사용된다.

1
; Ukodus/ukodus@0x1690
2
1690: 8b 8c 85 10 fe ff ff        mov ecx, dword ptr [rbp+4*rax-0x1f0] ; 암호문 C[i]
3
169f: 8b 85 90 fd ff ff           mov eax, dword ptr [rbp-0x270]        ; i
4
16a6: f7 bd 98 fd ff ff           idiv dword ptr [rbp-0x268]            ; 나머지 = i % 27
5
16b0: 8b 84 85 a0 fd ff ff        mov eax, dword ptr [rbp+4*rax-0x260]  ; 키스트림
6
16b7: 31 c8                       xor eax, ecx
7
16bf: 89 c7                       mov edi, eax
8
16c7: e8 c4 f9 ff ff              call putchar

따라서 27바이트 키와 암호문 39바이트의 XOR 결과가 평문이다. 스도쿠를 해결하고 빈칸 수를 기준으로 행을 재배치하면 다음 키스트림이 만들어진다.

Exploit

Ukodus/ukodus의 .rodata에서 스도쿠 퍼즐을 추출하고 백트래킹으로 완성한다
각 행의 0 개수를 세어 오름차순으로 재배치한다 (0, 8, 4, 1, 7, 2, 3, 5, 6)
재배치된 행을 9자리 숫자(세 칸씩 묶어 ABCDEF GHI)로 만들어 입력값 9줄을 구성한다
내부 키스트림은 세 자리씩 잘라 모듈로 256을 취한 27바이트가 되고, 하드코딩된 39바이트 암호문과 XOR하여 평문을 얻는다

1
sorted_rows = [0, 8, 4, 1, 7, 2, 3, 5, 6]
2
key = [
3
    row[0]*100 + row[1]*10 + row[2],
4
    row[3]*100 + row[4]*10 + row[5],
5
    row[6]*100 + row[7]*10 + row[8],
6
]  # 각 행에 대해 반복
7
key_bytes = [k % 256 for row_idx in sorted_rows for k in key_for_row(row_idx)]

대충 이런 느낌

1
from itertools import product
2

3
def solve_sudoku(board):
4
    def find_empty():
5
        for r, c in product(range(9), repeat=2):
6
            if board[r][c] == 0:
7
                return r, c
8
        return None
9

10
    def is_valid(r, c, val):
11
        if val in board[r]:
12
            return False
13
        if any(board[i][c] == val for i in range(9)):
14
            return False
15
        br, bc = 3 * (r // 3), 3 * (c // 3)
16
        for i in range(br, br + 3):
17
            for j in range(bc, bc + 3):
18
                if board[i][j] == val:
19
                    return False
20
        return True
21

22
    empty = find_empty()
23
    if empty is None:
24
        return True
25
    r, c = empty
26

27
    for val in range(1, 10):
28
        if is_valid(r, c, val):
29
            board[r][c] = val
30
            if solve_sudoku(board):
31
                return True
32
            board[r][c] = 0
33
    return False
34

35

36
def main():
37
    puzzle = [
38
        [8, 6, 7, 2, 0, 0, 0, 0, 5],
39
        [0, 0, 9, 0, 3, 8, 0, 0, 0],
40
        [0, 0, 3, 0, 0, 0, 2, 0, 0],
41
        [0, 2, 0, 0, 0, 4, 0, 0, 0],
42
        [9, 0, 0, 5, 0, 2, 0, 0, 7],
43
        [0, 0, 0, 8, 0, 0, 0, 6, 0],
44
        [0, 0, 8, 0, 0, 0, 5, 0, 0],
45
        [0, 0, 0, 6, 8, 0, 7, 0, 0],
46
        [5, 0, 0, 0, 0, 1, 6, 2, 8],
47
    ]
48

49
    cipher = [
50
        43, 206, 196, 106, 193, 15, 230, 2, 56, 59,
51
        238, 239, 176, 206, 34, 174, 193, 71, 127, 173,
52
        96, 209, 29, 246, 131, 153, 103, 81, 154, 230,
53
        14, 181, 77, 237, 0, 111, 58, 238, 161,
54
    ]
55

56
    solved = [row[:] for row in puzzle]
57
    if not solve_sudoku(solved):
58
        raise RuntimeError("Sudoku solver failed")
59

60
    zero_counts = [(sum(1 for val in row if val == 0), idx) for idx, row in enumerate(puzzle)]
61
    zero_counts.sort()  # 안정 정렬로 행 순서를 결정
62
    sorted_rows = [idx for _, idx in zero_counts]
63

64
    key_stream = []
65
    for idx in sorted_rows:
66
        row = solved[idx]
67
        key_stream.extend([
68
            row[0] * 100 + row[1] * 10 + row[2],
69
            row[3] * 100 + row[4] * 10 + row[5],
70
            row[6] * 100 + row[7] * 10 + row[8],
71
        ])
72

73
    key_stream = [val % 256 for val in key_stream]
74
    plaintext_bytes = bytes(
75
        cipher[i] ^ key_stream[i % len(key_stream)]
76
        for i in range(len(cipher))
77
    )
78

79
    print(plaintext_bytes.decode())
80

81

82
if __name__ == "__main__":
83
    main()

H7CTF{30c8d34c835f9c380492f2ca0298249d}
pwned@x00 ~ %

[H7CTF 2025] Ukodus writeup

TL;DR

Analysis

Exploit