# SWSEC HW1 Writeup
###### tags: `swsec` `writeup`
<style>
p:has(img) {
text-align: center;
}
</style>
## LFSR
![](https://hackmd.io/_uploads/B1D3Dl_GT.png)
因為在 $GF(2)$ 中,加法與 XOR 同義,LFSR 的轉移其實可以透過轉移矩陣來呈現。
題目內的 LFSR 為 feedback 到最後一個 state,因此構造方式為 `DIM-1` 的 identity matrix 左方 extend zero vector,最底下的 row 再 extend `TAP_VECTOR` 上去。
![](https://hackmd.io/_uploads/B1fBwXufp.png =300x)
`LFSR/solve.sage`
```python
DIM = 64
TAPS = [0, 2, 17, 19, 23, 37, 41, 53]
TAPS_VECTOR = zero_vector(GF(2), DIM)
for idx in TAPS:
TAPS_VECTOR[idx] = 1
MATRIX = matrix.identity(GF(2), DIM - 1)
MATRIX = matrix(GF(2), (DIM - 1), 1, [0] * (DIM - 1)).augment(MATRIX)
MATRIX = MATRIX.stack(TAPS_VECTOR)
```
進行多次 LFSR state 轉移,也就是乘上多次轉移矩陣,也因為反矩陣存在,因此我們可以透過乘上反矩陣的方式來回推 state。
題目所附 bitstream 最尾端 70 bits 沒有 XOR 其他東西,可以讓我們直接蒐集來構造聯立方程式解 state。
取剛輸出最後一個與 flag XOR 的 bit 時 (idx-th) 的 state 為基準如下:
$$
\begin{bmatrix}
s_0 \\ s_1 \\ \vdots \\ s_{63}
\end{bmatrix}
$$
後面每乘上 70 次轉移矩陣,輸出最上方的一個 1 bit ($s_0^\prime$),此時蒐集累積的轉移矩陣的第一個 row,取得一條方程式$M^{70}[0] \times \begin{bmatrix}
s_0, s_1, \dots, s_{63}
\end{bmatrix}^T = s_0^\prime$ 後,再乘上一次以代表取值後的 state 轉移。
$$
\begin{bmatrix}
s_0^\prime \\ s_1^\prime \\ \vdots \\ s_{63}^\prime
\end{bmatrix} = C^{70} \begin{bmatrix}
s_0 \\ s_1 \\ \vdots \\ s_63
\end{bmatrix}, \begin{bmatrix}
s_0^{\prime\prime} \\ s_1^{\prime\prime} \\ \vdots \\ s_{63}^{\prime\prime}
\end{bmatrix} = C^{70} C C^{70} \begin{bmatrix}
s_0 \\ s_1 \\ \vdots \\ s_{63}
\end{bmatrix}, \dots
$$
依序取得 70 個有 64 個未知數 ($s_0$ ~ $s_{63}$) 的式子,組成聯立方程式,透過 sage 可方便的於 $GF(2)$ 做 `solve_right(A, b)` 來解 idx-th state。
```python
STATE_START_NEGATIVE = -70
SKIP_BITS = 70
MATRIX_INV = MATRIX.inverse()
MATRIX_SKIP = MATRIX ^ SKIP_BITS
def solve(bitstream):
A = []
b = []
tmp_matrix = matrix.identity(GF(2), DIM)
# transit to STATE_START_NEGATIVE state
for i in range(-STATE_START_NEGATIVE):
# for __ in range(SKIP_BITS): randomness.getbit()
tmp_matrix = MATRIX_SKIP * tmp_matrix
# randomness.getbit(): return state[0]
A.append(tmp_matrix[0])
b.append(bitstream[STATE_START_NEGATIVE + i])
# randomness.getbit(): state = state[1:] + [f]
tmp_matrix = MATRIX * tmp_matrix
A = matrix(GF(2), A)
b = vector(GF(2), b)
# idx-th state, need to be inversed for initial state
idx = (len(bitstream) + STATE_START_NEGATIVE) * (SKIP_BITS + 1)
state = A.solve_right(b)
return (MATRIX_INV ^ idx) * state
```
乘上 idx 個反矩陣後,則可還原 LFSR 的初始 state。
```python
def decrypt(key):
randomness = LFSR(TAPS, key)
output = []
for i in range(len(bitstream)):
for __ in range(SKIP_BITS):
randomness.getbit()
output.append(bitstream[i] ^^ randomness.getbit())
return output
key = solve(bitstream)
flag_stream = decrypt(list(map(int, key)))
# strip non-key part
flag = bytes.fromhex(f"{int(''.join(map(str, flag_stream[:STATE_START_NEGATIVE])),2):x}")
```
生成新的 key bitstream,重新 XOR 即可解密 flag。
FLAG: `FLAG{Lf5r_15_50_eZZzZzZZZzzZzzz}`
## Oracle
題目提供了 RSA 的 N 與 e,以及經過 RSA 加密的 AES IV 與 KEY。
另外 Alice 會接收使用者所提供之已經 RSA 加密 AES IV、KEY 與密文,變成 AES 的 padding oracle。
在 AES 的 CBC 模式中,前一塊的密文 (或是 IV) 會先與明文 XOR 再進行加密:
![](https://hackmd.io/_uploads/Bkae-lJGT.png =350x)
而 CBC 解密時,則是會在解密區塊後,跟前一塊的密文 (或是 IV) XOR 得到明文:
![](https://hackmd.io/_uploads/Syp7bl1fa.png =350x)
這代表解密輸出的明文能透過前一塊的密文 (或是 IV) 來控制,若 $O_p$ 會在 padding 錯誤時噴 error,便可用前一塊的密文 (或是 IV) 來猜測原本區塊解密出的結果,最後與原始密文 (或是 IV) XOR 即可得到真正的明文。
使用以上方法,可以一次解一個 block。從 block 尾端往前,一個一個 byte 暴力猜,當 padding error 未發生,即可判斷已經成功將其 XOR 為正確的 padding,因此將 padding byte $\oplus$ 猜的 byte $=$ 原本的 IV,再將 IV $\oplus$ 原始密文則得到原始明文。
![](https://hackmd.io/_uploads/ryvjITvGp.png =350x)
由於 RSA 的加密參數有提供,能自由的構造 AES IV、KEY。
若我們不能解密 RSA,那就交給 Alice 來解。
![](https://hackmd.io/_uploads/HJn7EZOz6.png =400x)
Padding Oracle Attack 不只能用來在已知 IV 的情況下炸出 Decrypt 後的結果,反過來說,若 Decrypt 後的結果可控 (上圖紅色部分),可以用來炸放在 IV 的未知資料。
要控制 Decrypt 後的結果,可以直接使用自己的 AES KEY,並將 IV 全部設為 0x00,輸出的 Ciphertext 即直接為 Decrypt 後的結果。
此題的 padding 驗證同 PCKS#7 (padding = len $\times$ byte(len)),但若訊息剛好一個 block 的長度,則不需要 additional block。
因此這題從炸整張圖片,變成炸 AES IV 與 KEY 即可 (各為 1 block 長)。
分別把題目的 AES KEY 與 IV 當作 IV,KEY 與 Ciphertext 則為自己產生的,並 send 給 Alice。
當在猜第 idx 個 byte 時,先生成其 padding 並與已 leak 出的 IV 做 XOR 以使 XOR 完的輸出符合 padding 規則。
`Oracle/exp.py`
```python
# Exploit:
# Put encrypted message as IV
# Control AES key and plaintext to form correct padding
# Use null IV for encryption to directly XOR plaintext with unknown IV on server
def brute_block(r, target: bytes) -> bytes:
result = [0x00] * BLOCK_SIZE
for i in range(BLOCK_SIZE):
idx = -(i + 1)
brute_byte(r, target, result, idx)
return bytes(result)
# bruteforce with iv
def brute_byte(r, target: bytes, result: List[int], idx: int):
padding = gen_padding(-idx)
for i in range(256):
# guessing target[idx] (without prepended padding)
result[idx] = i
pt = strxor(padding, bytes(result))
ct = AES_encrypt_null_iv(pt)
r.sendlineafter(b": ", str(rsa_encrypt(MYKEY)).encode()) # encrypted_key
r.sendlineafter(b": ", str(bytes_to_long(target)).encode()) # encrypted_iv
r.sendlineafter(b": ", str(ct.hex()).encode()) # ciphertext
res = r.recvline()
# padding: PCKS#7 but no need to have additional block
# for the case of len(msg) == BLOCK_SIZE
if b"OK" in res:
break
else:
raise ValueError
def padding_oracle(target):
r = remote(host, port)
pt = brute_block(r, target)
r.close()
return pt
key = padding_oracle(encrypted_key_bytes)
iv = padding_oracle(encrypted_iv_bytes)
with open("encrypted_flag_d6fbfd5306695c4a.not_png", "rb") as f:
ct = f.read()
with open("flag.png", "wb") as f:
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(ct))
f.write(flag)
```
![](https://hackmd.io/_uploads/SkPMvlufp.png)
有了 AES KEY 與 IV 後,直接 local 解密圖片如下:
![](https://hackmd.io/_uploads/Syj4Pxdfa.png =500x)
FLAG: `FLAG{Rea11yu5efu110rac1eisntit?}`
## Oracle_Revenge
接續 [Oracle](#Oracle),此題的 Alice 是一樣的,不同的是,這次要解的 encrypted message 很長,最長是 1024 bit (128 bytes)。
每一次執行 padding oracle attack 可以取得一個 block (16 bytes) 的明文,實際上可以視為 mod $2^{16 \times 8}$ 的 LSB attack。
假設明文為 $m$,其實可將其拆為 $m = 2^{16 \times 8} y_1 + x_0$,$x_0$ 即為我們取得的輸出。
$({2^{16 \times 8}})^{-1} m = y_1 + ({2^{16 \times 8}})^{-1} x_0 = (2^{16 \times 8}y_2 + x_1) + ({2^{16 \times 8}})^{-1} x_0 \quad (\text{mod} \quad n)$,將 $({2^{16 \times 8}})^{-1} m = (({2^{16 \times 8}})^{-1})^e c$ 作為輸入可以得到 $r = [x_1 + ({2^{16 \times 8}})^{-1} x_0]_{\mod n} \mod 2^{16 \times 8}$。此時 $x_0$ 與 $({2^{16 \times 8}})^{-1} \mod n$ 皆已知,因此可推論 $x_1$。
一直持續算下去,則可得到 $x_k$, $x_{k-1}$, ..., $x_0$,並將 $m = \sum^k_{i=0} ({2^{16 \times 8}})^{i} x_i$ 還原出來。當 ${2^{16 \times 8}}^k > n$ 時即可終止。
因為 Alice 會自己取 `[:-16]`,所以我們可以放心的傳整個 encrypted_flag 做為 IV 過去。
`Oracle_Revenge/exp.py`
```python
def LSB_attack(enc: int, send: Callable[[bytes, int], int]):
mod = 1 << (16 * 8) # 16 bytes
mod_inv = pow(mod, -1, N)
mod_inv_e = pow(mod, -e, N)
flag_long = 0
exponential = 1
remain = 0
while exponential <= N:
res = send(long_to_bytes(enc))
x = (res - remain) % mod
flag_long += x * exponential
enc = (enc * mod_inv_e) % N
remain = (mod_inv * (remain + x)) % N
exponential *= mod
return long_to_bytes(flag_long)
flag = LSB_attack(encrypted_flag, lambda arg: bytes_to_long(padding_oracle(arg)))
```
![](https://hackmd.io/_uploads/r1nR8l_Gp.png)
FLAG: `FLAG{Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_Oo_oracle_of_oracle_oO_oO_o_oO_oO_o_oO_oO_o_oO_oO_o_oO_oO_o_oO_oO}`
## invalid_curve_attack
題目讓使用者可以輸入一個點 $G$,其會輸出橢圓曲線 $E: y^3= x^2 + ax + b$ 上的 $\text{flag} \times G$。
此題是要解 ECDLP,即解出 $dG$ 的 $d$。
題目之 $E$ 使用 NIST P-256 構造,是已經驗證安全的曲線,ECDLP 非常困難。
`elliptic_curve.py`
```python
class Point:
def __init__(self, curve, x, y):
if curve == None:
self.curve = self.x = self.y = None
return
self.curve = curve
self.x = x % curve.p
self.y = y % curve.p
```
但觀察以上 Point 的 constructor,可以發現其未檢查此點是否在 curve 上。
因為計算時僅使用 x 座標,因此僅更動 $b$,可以造在其他 $E^\prime$ 上的點,但結果仍可以被計算出來。
在更動 $b$ 後,可以取得 order 較小的 $E^\prime$,藉此降低在此曲線上解 ECDLP 的難度。
這時就能透過 Pohlig-Hellman 來解原始的 ECDLP。
![](https://hackmd.io/_uploads/SJkJMM_fa.png =500x)
分別找到許多小 order 的 $E^\prime$,以用來解出較小的 $d_i$,最後綜合用 CRT 解出真正的 $d$。
`invalid_curve_attack/exp.py`
```python
from sage.all import *
def solve():
prod = 1
b = 0
crt_pairs = []
while prod < N:
b += 1
# singular
if (4 * a**3 + 27 * b**2) % p == 0: continue
E = EllipticCurve(K, (a, b))
for G in E.gens():
hint = get_hint(*G.xy())
try:
P = E(*hint) # d * G does not on our curve'
except:
continue
order = G.order()
# find small subgroups, should be co-prime with prod for CRT
for f, e in order.factor():
v = f ** e
if v.bit_length() > 32 or gcd(v, prod) != 1: continue
s = order // v
x = discrete_log(s * P, s * G, ord=ZZ(v), operation="+")
crt_pairs.append((x, f))
prod *= v
# just find first available G
break
return crt(*map(list, zip(*crt_pairs)))
flag = solve()
```
以上先遍立 $b$,跳過會造成 singular 的 case。
接著透過 sage 的 `EllipticCurve` 相關函式計算此 $E^\prime$ 的 generater $G$ 給 server 測試,若回傳的點不在 $E^\prime$ 上,則不使用此 $G$,換下一個 $G^\prime$ 繼續測試。
接著是從其 order 的質因數中找較小的值以控制 `discrete_log` 的難度,這裡要讓 factor 全部互質,CRT 才能解出唯一解。蒐集足夠的 group 後 (`prod > N`),就足夠 CRT 來解出 $\text{flag}$。
![](https://hackmd.io/_uploads/SJQWueuGp.png)
FLAG: `FLAG{YouAreARealECDLPMaster}`
## signature_revenge
此題的 $k_1$, $k_2$ 互相有關聯如下 ($m_1$: magic1, $m_2$: magic2):
$$
k_1 = 2^{128} \times m_1 + m_2 \\
k_2 = 2^{128} \times m_2 + m_1
$$
其在 ECDSA 中,可得到式子如下:
$$
s_1 = k_1^{–1} (h_1 + d \times r_1) \pmod n \\
s_2 = k_2^{–1} (h_2 + d \times r_2) \pmod n
$$
可移項消掉 $d$:
$$
\begin{align}
d &= r_1^{-1}(s_1 k_1-h_1) \pmod{n} \\
&= r_2^{-1}(s_2 k_2-h_2) \pmod{n}.
\end{align} \\
k_1 − s_1^{−1}s_2r_1r_2^{−1}k_2 + s_1^{−1}r_1h_2r_2{−1} − s_1^{−1}h_1 = 0 \pmod{n} \quad (1)
$$
此時若 $k_1, k_2 \lt K \approx \sqrt{n}$,則可令 $t = -s_1^{−1}s_2r_1r_2 ^{−1}, \space u = s_1^{−1}r_1h_2r_2^{−1} − s_1^{−1}h_1$
得到 $k_1 + tk_2 + u \equiv 0 \pmod n$
並使用以下 LLL basis 解出 $v = (-k_1, k_2, K)$:
$$
\begin{bmatrix}
n & 0 & 0\\
t & 1 & 0\\
u & 0 & B
\end{bmatrix}
$$
但這裡的 $n \approx 2^{256}$, $k_1$, $k_2$ 也 $\approx 2^{256}$,都太大了。
但若我們將 (1) 中的 $k_1$, $k_2$ 展開的話:
$$
m_1 + (r_1^{-1}s_1 2^{128} - r_2^{-1}s_2)^{-1} \times (r_1^{-1}s_1 - r_2^{-1}s_2 2^{128}) \times m_2 \\ +(r_1^{-1}s_1 2^{128} - r_2^{-1}s_2)^{-1} \times (r_2^{-1}h_2 - r_1^{-1}h_1) = 0 \pmod{n}
$$
$$
m_1 + (r_1^{-1}s_1 2^{128} - r_2^{-1}s_2)^{-1} t \times m_2 +(r_1^{-1}s_1 2^{128} - r_2^{-1}s_2)^{-1} u = 0 \pmod{n}
$$
這時候的 $m_1, m_2 < 2^{128}$,把 $t, u$ 稍作調整後,即可使用相同的 LLL basis。
$t^\prime=(r_1^{-1}s_1 2^{128} - r_2^{-1}s_2)^{-1}(r_1^{-1}s_1 - r_2^{-1}s_2 2^{128}) \pmod n$
$u^\prime=(r_1^{-1}s_1 2^{128} - r_2^{-1}s_2)^{-1}(r_2^{-1}h_2 - r_1^{-1}h_1) \pmod n$
`signature_revenge/solve.py`
```python
t = (- pow(s1, -1, n) * s2 * r1 * pow(r2, -1, n)) % n
u = (pow(s1, -1, n) * r1 * h2 * pow(r2, -1, n) - pow(s1, -1, n) * h1) % n
tp = (1 + (2**l) * t) * pow((2**l) + t, -1, n) % n
up = u * pow((2**l) + t, -1, n) % n
K = int(iroot(n, 2)[0])
B = [
[n, 0, 0],
[tp, 1, 0],
[up, 0, K]
]
L = matrix(B).LLL()
```
有時 LLL 找到的 vector 會更短,這時候可以對得到的 short vectors 做線性組合爆搜:
`signature_revenge/solve.py`
```python
cnt = 0
try_top = 32
try_low = 0
for coeff in itertools.product(range(try_low, try_top), repeat=3):
vec = zero_vector(3)
for c, v in zip(coeff, L):
vec += c * v
m1 = -vec[0]
m2 = vec[1]
if vec[2] != K or m1 < 0 or m2 < 0: continue
k1 = m1 * (2 ** l) + m2
d = int(((s1 * k1 - h1) * pow(r1, -1, n)) % n)
if bytes_to_long(md5(d.to_bytes(32, "big")).digest()) == m1 and \
bytes_to_long(md5(d.to_bytes(32, "big")[::-1]).digest()) == m2:
print(f"{coeff=}, {m1=}, {m2=}")
break
cnt += 1
else:
print("Not Found :(")
print(f"{cnt=}")
exit(1)
d = long_to_bytes(d)
flag = d[d.index(b"FLAG"):]
```
![](https://hackmd.io/_uploads/H1LDvxOGa.png)
FLAG: `FLAG{LLLisreaLLyusefuL}`
## Power Analysis
在 AES 加密時,硬體可能會出現功率的變化,如下圖,當一個 bit 在 CMOS 中做 flip 時,會有瞬間的強電流出現。另外若 #bitflip 變多,其差異也會更明顯。
<img src="https://hackmd.io/_uploads/HJuY8X_fa.png" style="width: 49%">
<img src="https://hackmd.io/_uploads/S1ZQnXdG6.png" style="width: 49%">
將題目所附之資料分析如下: `pt`: 明文、`ct`: 密文、`pm`: 功率
共有 D = 50 組資料,每組有 T = 1806 個測量資料
挑一組 record 的 `pm` 畫出來,得到下圖:
![](https://hackmd.io/_uploads/BJ7JimuGT.png)
可以發現有明顯的規律,每個 round 開始會有類似的 power pattern 產生。
因為有明文,可以透過 Correlation Power Analysis 的方法來炸 key。
Power 測量點在 SubByte (SBOX[p $\oplus$ k]) 與 ShiftRow 中間的輸出,挑在這裡是因為他尚未進入 複雜的 MixColumn,又是每個 round 開始過後一小段時間,相對準確。
接下來,透過猜測 K 個 key[i] 可能的 byte,能一個一個 byte 來 recover key。
將 plaintext[i] 與 key[i] 做 XOR,去 SBOX 取值後,套用 Power Model 以得到 hypothetical_model$_{D \times K}$。這裡因為是測量 Cortex M 系列晶片,根據經驗法則選擇 Hamming Weight Model,也就是此 byte 有多少 bit 為 1。
再來將 hypothetical_model 中的每個 column 掃過所有 `pm` 的 column 來計算 Pearson's Correlation Coefficient。最後會得到 correlation_matrix$_{K \times T}$。其中最大值所在的 row,可以推測其 key 與 power 消耗的相關度最大,故猜測此 byte 為 key[i]。
`Power Analysis/solve.py`
```python
def hamming_weight(b):
return sum(map(int, f"{b:b}"))
def pearson_correlation_coefficient(measured_data, modeled_data):
"""
measuredData: D x T
modeledData: D x K
"""
coeffs = np.corrcoef(modeled_data, measured_data, rowvar=False) # (K+T) x (T+K)
return coeffs[:K , K:] # K x T
def find_max_correlation_coefficient(correlation_matrix):
"""
correlation_matrix: K x T
"""
max_value = np.amax(correlation_matrix, 0)
max_idx = np.argmax(correlation_matrix, 0)
return int(max_idx[np.argmax(max_value)])
def solve(i):
pt_i = pts[:, i]
hypothetical_model = []
for k in range(KEY_RANGE):
intermediate = map(SBOX.__getitem__, pt_i ^ k)
hypothetical_model.append(list(map(hamming_weight, intermediate)))
hypothetical_model = np.transpose(np.array(hypothetical_model)) # D x K
coeffs = pearson_correlation_coefficient(pms, hypothetical_model)
result = find_max_correlation_coefficient(coeffs)
return result
```
使用 `solve(i)` 解 key[i]。
`np.corrcoef(X, Y)` 會將 X 與 Y 裡的每個 row (`rowvar=False` 則是 column) 視為一個變數,一次計算所有變數間的相關係數,結果如下圖:
```
\ X0 X1 X2 |Y1 Y2 Y3|
X0 1 | _ _ _|
X1 1 | _ _ _|
X2 1 | _ _ _|
Y1 1
Y2 1
Y3 1
```
要取所需的結果,直接取 `coeffs[:K , K:]` (右上角框起來處) 即可,會比一個一個 column 做快得多。
因為 flag 都是 ASCII 字元,因此炸 K = 128 即可。
![](https://hackmd.io/_uploads/HJWUVmufp.png)
FLAG: `FLAG{W0ckAwocKaWoCka1}`