TL;DR

AES-CBC Oracle Padding Attack

Oracle Noise: 각 오라클 응답에 대해 2x64-bit LFSR 기반 RNG XORed
Replay protection: 동일한 페이로드 제출 거부

Analysis

1
from Crypto.Cipher import AES
2
from Crypto.Util.Padding import pad, unpad
3
from os import urandom, environ
4

5
def parity(v):
6
    return bin(v).count("1")&1
7

8
class LFSR:
9
    def __init__(self,fb,state):
10
        self.fb = fb
11
        self.state = state
12

13
    def clock(self):
14
        out = self.state&1
15
        self.state = (parity(self.state&self.fb)<<63)|(self.state>>1)
16
        return out
17

18
class RNG:
19
    def __init__(self,state=None):
20
        if state==None:
21
            state = urandom(16)
22
        s1 = int.from_bytes(state[:8],"big")
23
        s2 = int.from_bytes(state[8:],"big")
24
        self.L1 = LFSR(11277095078203943143,s1)
25
        self.L2 = LFSR(12022921549183311343,s2)
26

27
    def bit(self):
28
        return self.L1.clock()^self.L2.clock()
29

30
def check_padding(key,ct):
31
    iv,ct = ct[:16],ct[16:]
32
    cipher = AES.new(key,AES.MODE_CBC,iv=iv)
33
    try:
34
        pt = cipher.decrypt(ct)
35
    except:
36
        return False
37
    padlen = pt[-1]
38
    return pt[-padlen:] == bytes([padlen])*padlen
39

40
key = urandom(16)
41
msg = urandom(32)
42
rng = RNG()
43
tried = set()
44
while True:
45
    inp = input("> ")
46
    if inp == "1":
47
        iv = urandom(16)
48
        cipher = AES.new(key,AES.MODE_CBC,iv=iv)
49
        ct = iv+cipher.encrypt(msg)
50
        print(ct.hex())
51
    elif inp == "2":
52
        ct = input("(hex) > ")
53
        ct = bytes.fromhex(ct)
54
        if ct in tried:
55
            print("No repeat")
56
            continue
57
        tried.add(ct)
58
        o = int(check_padding(key,ct))
59
        o ^= rng.bit()
60
        print(o)
61
    elif inp == "3":
62
        guess = input("(hex) > ")
63
        guess = bytes.fromhex(guess)
64
        if msg == guess:
65
            flag = environ.get("CHALFLAG","hspace{this_is_not_a_real_flag}")
66
            print(flag)
67
        else:
68
            print("No cookie! :(")
69
        break

원격 오라클에 임의 길이 payload 전송 가능.

1
    cipher = AES.new(key,AES.MODE_CBC,iv=iv)
2
    try:
3
        pt = cipher.decrypt(ct)
4
    except:
5
        return False

유효하지 않은 길이 제출 시 예외를 발생시키고 패딩 검사가 실행되지 않음. 그러나 RNG 비트는 여전히 소모되어 응답에 XOR된다.

알려진 LFSR의 피드백 다항식 fb1=11277095078203943143, fb2=12022921549183311343

재전송 방지로 인해 매 쿼리마다 새로운 16바이트 prefix를 생성해야함.

서비스가 주는 $IV || c_1 || c_2$ 를 복호화하여 플래그 회수.

Exploit

1. Extract raw RNG bits

유효하지 않은 길이의 페이로드는 패딩 검사가 실행되지 않는다. $\rightarrow$ 오라클의 응답은 오로지 RNG 비트에만 의존.

1
o = int(check_padding(key, ct))
2
o ^= rng.bit()

서비스가 check_padding(key, ct) 결과를 다음 코드와 같이 처리하기에 패딩 검사 결과가 항상 Flase 또는 rng.bit() 와 동일.
Replay protection으로 인해 페이로드는 항상 유일하므로 랜덤 바이트를 매번 생성한다.
위 과정 반복으로 비트 수집 $\rightarrow$ LFSR 조합 출력의 연속된 출력 비트

2. Recover dual-LFSR state

fb1=11277095078203943143, `fb2=12022921549183311343

1
class LFSR:
2
    ..
3
    def clock(self):
4
        out = self.state&1
5
        self.state = (parity(self.state&self.fb)<<63)|(self.state>>1)
6
        return out
7

8
class RNG:
9
    ..
10
    def bit(self):
11
        return self.L1.clock()^self.L2.clock()

RNG 출력은 다음 코드처럼 L1.clock()^L2.clock()이다.

각 LFSR은 64비트 상태 $s = (s_0, s_1, \dots, s_{63})$ 를 유지하며 매 clock마다 $s_{\text{new}} = \left(\bigoplus_{i=0}^{63} f_i s_i \right) \parallel s_0 s_1 \dots s_{62}$ 형태로 갱신된다. 여기서 $f_i$ 는 피드백의 다항식 계수, $(\parallel)$ 은 bit-shift 응답에서 추출한 $z_t$ 는 $z_t = \ell_t^{(1)} \oplus \ell_t^{(2)}$ 으로,

으로, 각각의 $\ell_t^{(k)}$ 는 $L_k$ 의 상태 비트들의 $\mathbb{F}_2$ 선형 결합이다. 즉, 모든 출력 비트를 $\mathbb{F}_2$ 선형방정식으로 표현할 수 있다. 128개의 미지수(각 LFSR 상태의 64비트)에 대해 128개 이상의 독립 방정식을 수집하면 가우스 소거법으로 초기 상태를 정확히 복원한다.

2.1 노이즈 비트 수집

31바이트 임의 바이트열(= 16바이트 IV + 15바이트 암호문)로 오라클을 질의하면 AES 복호화가 실패하여 곧바로 $z_t$ 를 얻는다.

재사용 방지를 위해 모든 페이로드는 기억해 두고 다시 사용하지 않는다.

2.2 가우스 소거

각 시간 $t$ 에 대해, 다음과 같은 식을 행으로 갖는 행렬을 만든다. $z_t = \sum_{i=0}^{63} a_{t,i} s^{(1)}_i \oplus \sum_{i=0}^{63} b_{t,i} s^{(2)}_i$

여기서 $a_{t,i}, b_{t,i} \in \{0,1\}$ 는 해당 시점의 LFSR 전이에서 유도된다. 이 128차 선형 시스템을 가우스 소거로 해결하 면 $s^{(1)}, s^{(2)}$ 를 모두 복구할 수 있다.

복구된 상태를 이용해 로컬 RNG를 구성하고, 수집에 사용된 질의 수만큼 advance하여 서버와 동일한 타임스텝으로 wjdfuf한다

3. Obtain the target Ciphertext

옵션 1을 한 번 호출해 암호분 $C = IV \parallel C_1 \parallel C_2$ 를 받는다. 이때 RNG는 소비되지 않으므로 로컬 RNG와 서버 RNG 동기화는 유지된다.

$C = \text{IV} \,\|\, C_1 \,\|\, C_2$

4. Oracle Noise 제거

패딩 오라클을 사용할 때마다 서버는 새로운 $z_t$ 를 생성한다. 로컬 RNG에서 동일한 타임스텝의 비트를 통해 XOR하면 clean 패딩이 복원된다.

1
int(check_padding(key,ct)) ^ rng.bit()

$\hat{o} = (\text{response}) \oplus z_t = \mathbf{1}_{\text{valid padding}}$ 재사용 막기 위해 질의마다 무작위 가짜 IV를 붙인다. 실제 질의는

$\text{payload} = \underbrace{\text{IV}_{\text{rand}}}_{16\text{B}} \,\|\, \text{crafted block} \,\|\, \text{target block}$ 형태가 된다.

주의점

모든 쿼리마다 서로 다른 prefix를 붙여 원격 쿼리가 중복되지 않도록 해야한다.
응답 $r$ 을 받으면 로컬 LFSR가 가리키는 예측 RNG 비트 $p$ 와 XOR: clean = r ^ p, clean == 1이면 패딩 검사가 성공
각 원격 쿼리ㅏ다 RNG가 한 비트 소비되므로 로컬 LFSR도 한 비트를 advance 시킨다.

5. CBC Padding oracle attack

평문 블록을 한 바이트씩 역으로 복원한다. 현재 위치를 $i$ 라고 한다면 패딩 값은 $p=16-i$ 이다. 이미 얻은 중간 값을 이용해 나머지 바이트를 패딩에 맞춰 조정한다.

$\text{crafted}[j] = \text{intermediate}[j] \oplus p \quad (j > i)$

그 후 가능한 바이트 후보 $g \in \{0,\dots,255\}$ 에 대해 $\text{payload} = \text{IV}_{\text{rand}} \,\|\, (\text{crafted with } g) \,\|\, C_\text{target}$ 을 오라클에 넣어 $\hat{o} = 1$ 인 후보를 탐색한다. 오진(정확한 표현을 모르겠다)을 줄이기 위해 발견한 후보에 대해 블록을 살짝 변형(예: 한 바이트 XOR 1)한 뒤 다시 질의하여 여전히 성공하면 우연한 패딩 성공으로 간주하고버린다.

패딩 검증에 통과한 후보에서 중간값과 평문 바이트는 다음과 같이 계산된다.

\begin{aligned} \text{intermediate}[i] &= g \oplus p \\ \text{plaintext}[i] &= \text{intermediate}[i] \oplus \text{prev\_block}[i] \end{aligned}

$C_2$ 는 $C_1$ 을, $C_1$ 은 $IV$ 를 각각 이전 블록으로 사용하여 두 블록 모두를 복호화한다.

복원된 평문

1
946aeb016f18b1b3000305540b420089d51ad02b359fc1ad9f81feb9c49b18f2

이걸 다시 서버에 제출하면 플래그를 받을 수 있다.

1
import os
2
import binascii
3
from pwn import *
4

5
context.log_level = 'debug'
6

7
NUM_SAMPLES = 300
8

9
FB1 = 11277095078203943143
10
FB2 = 12022921549183311343
11

12
class LFSR:
13
    def __init__(self, fb, state):
14
        self.fb = fb
15
        self.state = state
16

17
    def clock(self):
18
        out = self.state & 1
19
        parity = bin(self.state & self.fb).count("1") & 1
20
        self.state = (parity << 63) | (self.state >> 1)
21
        return out
22

23

24
class RNG:
25
    def __init__(self, s1, s2):
26
        self.l1 = LFSR(FB1, s1)
27
        self.l2 = LFSR(FB2, s2)
28

29
    def bit(self):
30
        return self.l1.clock() ^ self.l2.clock()
31

32
    def advance(self, steps):
33
        for _ in range(steps):
34
            self.bit()
35

36

37
def lfsr_rows(fb, steps):
38
    coeffs = [1 << i for i in range(64)]
39
    rows = []
40
    for _ in range(steps):
41
        rows.append(coeffs[0])
42
        feedback = 0
43
        for i in range(64):
44
            if (fb >> i) & 1:
45
                feedback ^= coeffs[i]
46
        coeffs = coeffs[1:] + [feedback]
47
    return rows
48

49

50
def solve_states(outputs):
51
    l1_rows = lfsr_rows(FB1, len(outputs))
52
    l2_rows = lfsr_rows(FB2, len(outputs))
53
    rows = [l1_rows[i] | (l2_rows[i] << 64) for i in range(len(outputs))]
54

55
    nvars = 128
56
    res = outputs[:]
57
    row_idx = 0
58
    pivot_cols = []
59

60
    for col in range(nvars):
61
        pivot = Non
62
        for r in range(row_idx, len(rows)):
63
            if (rows[r] >> col) & 1:
64
                pivot = r
65
                break
66
        if pivot is None:
67
            continue
68
        rows[row_idx], rows[pivot] = rows[pivot], rows[row_idx]
69
        res[row_idx], res[pivot] = res[pivot], res[row_idx]
70
        for r in range(row_idx + 1, len(rows)):
71
            if (rows[r] >> col) & 1:
72
                rows[r] ^= rows[row_idx]
73
                res[r] ^= res[row_idx]
74
        pivot_cols.append(col)
75
        row_idx += 1
76

77
    for r in range(row_idx, len(rows)):
78
        if rows[r] == 0 and res[r]:
79
            raise SystemExit("system inconsistent")
80

81
    solution = [0] * nvars
82
    for idx in range(len(pivot_cols) - 1, -1, -1):
83
        col = pivot_cols[idx]
84
        row = rows[idx]
85
        total = res[idx]
86
        mask = row >> (col + 1)
87
        j = col + 1
88
        while mask:
89
            if mask & 1:
90
                total ^= solution[j]
91
            mask >>= 1
92
            j += 1
93
        solution[col] = total
94

95
    l1_state = sum((solution[i] & 1) << i for i in range(64))
96
    l2_state = sum((solution[64 + i] & 1) << i for i in range(64))
97
    return l1_state, l2_state
98

99

100
def oracle_bit(p, payload):
101
    # 메뉴 2: oracle raw bit
102
    p.sendline(b"2")
103
    p.recvuntil(b"(hex) > ")
104
    p.sendline(binascii.hexlify(payload))
105
    resp = p.recvline().strip()
106
    if resp == b"No repeat":
107
        p.recvuntil(b"> ")
108
        return None
109
    p.recvuntil(b"> ")
110
    return int(resp)
111

112

113
def oracle_clean(p, rng, crafted_block, target_block):
114
    while True:
115
        iv_rand = os.urandom(16)
116
        payload = iv_rand + crafted_block + target_block
117
        raw = oracle_bit(p, payload)
118
        if raw is None:
119
            continue
120
        bit = rng.bit()
121
        return (raw ^ bit) == 1
122

123

124
def recover_block(p, rng, ct_block, prev_block):
125
    block_size = 16
126
    intermediate = [0] * block_size
127
    plaintext = [0] * block_size
128
    crafted = [0] * block_size
129

130
    for index in range(block_size - 1, -1, -1):
131
        pad = block_size - index
132
        for j in range(index + 1, block_size):
133
            crafted[j] = intermediate[j] ^ pad
134
        for guess in range(256):
135
            crafted[index] = guess
136
            if not oracle_clean(p, rng, bytes(crafted), ct_block):
137
                continue
138
            # 확인 쿼리: 우연한 성공 배제
139
            tweak = bytearray(ct_block)
140
            tweak[index] ^= 1
141
            if oracle_clean(p, rng, bytes(crafted), bytes(tweak)):
142
                continue
143
            intermediate[index] = guess ^ pad
144
            plaintext[index] = intermediate[index] ^ prev_block[index]
145
            break
146
        else:
147
            raise SystemExit("failed to recover byte")
148
    return bytes(plaintext)
149

150

151
def main():
152
    p = remote("13.125.132.168", 13372)
153
    p.recvuntil(b"> ")
154

155
    seen = set()
156
    rng_outputs = []
157
    while len(rng_outputs) < NUM_SAMPLES:
158
        payload = os.urandom(31)
159
        if payload in seen:
160
            continue
161
        seen.add(payload)
162
        raw = oracle_bit(p, payload)
163
        if raw is None:
164
            continue
165
        rng_outputs.append(raw)
166

167
    l1_state, l2_state = solve_states(rng_outputs)
168
    rng = RNG(l1_state, l2_state)
169
    rng.advance(NUM_SAMPLES)
170

171
    p.sendline(b"1")
172
    ct_line = p.recvline().strip()
173
    p.recvuntil(b"> ")
174
    cipher = bytes.fromhex(ct_line.decode())
175

176
    iv = cipher[:16]
177
    c1 = cipher[16:32]
178
    c2 = cipher[32:48]
179

180
    p2 = recover_block(p, rng, c2, c1)
181
    p1 = recover_block(p, rng, c1, iv)
182
    message = p1 + p2
183

184
    p.sendline(b"3")
185
    p.recvuntil(b"(hex) > ")
186
    p.sendline(message.hex().encode())
187
    flag = p.recvline().strip().decode()
188
    print("Plaintext:", message.hex())
189
    print("Flag:", flag)
190
    p.close()
191

192

193
if __name__ == "__main__":
194
    main()

노이즈 비트 수집: 31바이트 난수 페이로드로 RNG 출력 $z_t$ 를 수집.
가우스 소거: 수집한 $z_t$ 벡터로 128-변수 $GF(2)$ 선형 시스템을 풀어 $L_1, L_2$ 상태 복원.
패딩 오라클 보정: 로컬 RNG로 노이즈를 제거해
CBC 패딩 오라클 복호화: 표준 바이트 단위 복호화 루틴으로 두 블록 평문 추출.

1
[DEBUG] Sent 0x61 bytes:
2
    b'abb7c9128820cb705e9d0abbe622ee638646ca5830b0c56b95408f51ffeddd3edfaee0604ddf80793cfe19288b5964ca\n'
3
[DEBUG] Received 0x4 bytes:
4
    b'0\n'
5
    b'> '
6
[DEBUG] Sent 0x2 bytes:
7
    b'3\n'
8
[DEBUG] Received 0x8 bytes:
9
    b'(hex) > '
10
[DEBUG] Sent 0x41 bytes:
11
    b'3630ea06fab1a7e1f9d9d1a15a5195e13c4316d336ac1f0eb3d15a6e4efea773\n'
12
[DEBUG] Received 0x1e bytes:
13
    b'hspace{god_will_bless_you_XD}\n'
14
Plaintext: 3630ea06fab1a7e1f9d9d1a15a5195e13c4316d336ac1f0eb3d15a6e4efea773
15
Flag: hspace{god_will_bless_you_XD}
16
[*] Closed connection to 13.125.132.168 port 13372

[CLUB LEAGUE] delpih writeup