---
# System prepended metadata

title: SWSEC HW1 Writeup
tags: [swsec, writeup]

---

# 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}`