# SWSEC HW1 Writeup
###### tags: `swsec` `writeup`

<style>
p:has(img) {
text-align: center;
}
</style>

## LFSR

因為在 $GF(2)$ 中，加法與 XOR 同義，LFSR 的轉移其實可以透過轉移矩陣來呈現。
題目內的 LFSR 為 feedback 到最後一個 state，因此構造方式為 `DIM-1` 的 identity matrix 左方 extend zero vector，最底下的 row 再 extend `TAP_VECTOR` 上去。


`LFSR/solve.sage`

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。

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。

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 再進行加密:


而 CBC 解密時，則是會在解密區塊後，跟前一塊的密文 (或是 IV) XOR 得到明文:


這代表解密輸出的明文能透過前一塊的密文 (或是 IV) 來控制，若 $O_p$ 會在 padding 錯誤時噴 error，便可用前一塊的密文 (或是 IV) 來猜測原本區塊解密出的結果，最後與原始密文 (或是 IV) XOR 即可得到真正的明文。

使用以上方法，可以一次解一個 block。從 block 尾端往前，一個一個 byte 暴力猜，當 padding error 未發生，即可判斷已經成功將其 XOR 為正確的 padding，因此將 padding byte $\oplus$ 猜的 byte $=$ 原本的 IV，再將 IV $\oplus$ 原始密文則得到原始明文。


由於 RSA 的加密參數有提供，能自由的構造 AES IV、KEY。
若我們不能解密 RSA，那就交給 Alice 來解。


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`

# 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)


有了 AES KEY 與 IV 後，直接 local 解密圖片如下:


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`

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)))


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`

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。


分別找到許多小 order 的 $E^\prime$，以用來解出較小的 $d_i$，最後綜合用 CRT 解出真正的 $d$。

`invalid_curve_attack/exp.py`

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}$。


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`

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`

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"):]


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` 畫出來，得到下圖:


可以發現有明顯的規律，每個 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`

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 即可。


FLAG: `FLAG{W0ckAwocKaWoCka1}`