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

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

## COR
triLFSR 是一種 Geffe generator，其輸出為 $x_1$ ? $x_2$ : $x_3$


但比較輸出與 $x_2$、$x_3$ 的關係後，可以發現輸出有 75% 的機率分別跟 $x_2$、$x_3$ 相同，即當我們猜測的初始 state 是對的，output 會有 75% 是相同的。
因為 tap 已知，因此我們可以分別對 $x_2$ 與 $x_3$ 初始 state 進行爆破，需要爆破的數量從 $2^{19 + 23 + 27}$ 降為 $2^{19} + 2^{23} + 2^{27}$。
因為題目是先直接輸出，我們可以取前 `len(state)` 個 bit 直接做 flip 來回推可能的 state (75% 是對的，只要 flip 25% 的 bit 就有可能猜到)。

`COR/brute_COR.py`

def brute(output, bits):
    for i in range(bits):
        for t in itertools.combinations(range(bits),i):
            state = brute_sub(output, bits, t)
            if state:
                return state


def brute_sub(output, bits, t):
    state = output[:bits]
    for idx in t:
        state[idx] = int(not state[idx]) # bit flip
    lfsr = LFSR([0, 1, 2, 5], state)

    tmp = [lfsr.getbit() for _ in range(FLAG_OFFSET)]
    union = sum(map(lambda x: int(x[0] == x[1]), zip(output, tmp)))
    if union >= FLAG_OFFSET * 0.7:
        return state

以上的 `brute()` 會透過 `itertools.combination` 產生要做 bit flipping 的 index，再傳給 `brute_sub()` 來測試這個猜測是否正確。
由於可能不能整除導致誤差，因此取 0.7 而非 0.75 作為 threshold。

在爆破完 $x_2$ 與 $x_3$ 的 state 後，最後再進行 $x_1$ 的爆破即可。

`COR/brute_COR.py`

FLAG_OFFSET = 200

# lfsr3
lfsr3_state = brute(output, 27)

# lfsr 2
lfsr2_state = brute(output, 23)

for n in tqdm.tqdm(range(1 << 19)):
    lfsr3 = LFSR([0, 1, 2, 5], lfsr3_state)
    lfsr2 = LFSR([0, 1, 2, 5], lfsr2_state)

    state = list(map(int, f"{n:>019b}"))
    lfsr1 = LFSR([0, 1, 2, 5], state)

    lfsr = triLFSR(lfsr1, lfsr2, lfsr3)

    for gt in output[:FLAG_OFFSET]:
        b = lfsr.getbit()
        if b != gt:
            break
    else:
        flag = [b ^ lfsr.getbit() for b in output[FLAG_OFFSET:]]
        break


FLAG: `FLAG{Corre1ati0n_Attack!_!}`

## POA
Padding Oracle $O_{p}$ (server) 可以幫我們檢查 padding 是否正確。

在 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$ 原始密文則得到原始明文。


`POA/brute.py`

def brute_block(iv: bytes, block: bytes) -> bytes:
    # tmp == data before xor
    tmp = [0x00] * BLOCK_SIZE

    for i in tqdm.tqdm(range(BLOCK_SIZE)):
        idx = -(i + 1)
        brute_byte(iv, tmp, block, idx)

    return bytes(xor_array(tmp, iv))


def brute_byte(iv: bytes, tmp: List[int], block: bytes, idx: int):
    for i in range(128):
        tmp[idx] = i ^ iv[idx] ^ 0x80
        iv_bytes = bytes(tmp)

        r.sendline((iv_bytes + block).hex().encode())
        res = r.recvline()

        # padding correct: [0x80][0x00]...[0x00]
        # leave index > idx as original bytes
        if b"wrong" not in res:
            tmp[idx] ^= 0x80
            break
    else:
        # 0x80 case
        tmp[idx] = 0x80 ^ iv[idx]


def padding_oracle(data: bytes) -> bytes:
    blocks = [data[i:i+BLOCK_SIZE] for i in range(0, len(data), BLOCK_SIZE)]
    plaintext = b""

    for i in range(1, len(blocks)):
        iv_block = blocks[i-1]
        block = blocks[i]

        print("Block", i)
        plaintext += brute_block(iv_block, block)

    return plaintext

因為此題的 padding 格式是 `<oooooo[0x80][0x00]...[0x00]> (find first [0x80])`，且明文是 ASCII，每個 byte 皆在 0 ~ 127 之間，因此只需要暴力炸 (0 ~ 127) $\oplus$ 0x80 (小於 0x80 => MSB 為 0，XOR 0x80 後 MSB 會被設成 1)。

炸第一個 byte 時，要讓 XOR 輸出 0x80，炸後續 byte 後則要使正在炸的 byte 為 0x80，其後的則為 0x00，所以將結果 XOR 0x80 則取得 IV，另 IV XOR 解密輸出為 0x00，因此 IV 同時等於明文。

另外若炸 0 ~ 127 都噴錯，則代表原本 IV $\oplus$ 密文 = 0x80，所以 flag 為 IV $\oplus$ 0x80。


FLAG: `FLAG{pAdd1NG_0rAcL3_A77aCK}`

## LSB
這題是一個 LSB Oracle $O_{LSB}$，會根據使用者所輸入的明文加密後，輸出 密文 % 3 的結果。

假設明文為 $m$，其實可將其拆為 $m = 3y_1 + x_0$，$x_0$ 即為我們可以取得的輸出。

$3^{-1} m = y_1 + 3^{-1} x_0 = (3y_2 + x_1) + 3^{-1} x_0 \quad (\text{mod} \quad n)$，將 $3^{-1} m = (3^{-1})^e c$ 作為輸入可以得到 $r = [x_1 + 3^{-1} x_0]_{\mod n} \mod 3$。此時 $x_0$ 與 $3^{-1} \mod n$ 皆已知，因此可推論 $x_1$。

一直持續算下去，則可得到 $x_k$, $x_{k-1}$, ..., $x_0$，並將 $m = \sum^k_{i=0} 3^{i} x_i$ 還原出來。當 $3^k > n$ 時即可終止。

`LSB/brute.py`

mod = 3
mod_inv = pow(mod, -1, n)
mod_inv_e = pow(mod, -e, n)

flag_long = 0

exponential = 1
remain = 0

while exponential <= n:
    r.sendline(str(enc).encode())
    res = int(r.recvline().decode().strip())

    x = (res - remain) % mod

    flag_long += x * exponential

    enc = (enc * mod_inv_e) % n
    remain = (mod_inv * (remain + x)) % n

    exponential *= mod


FLAG: `FLAG{Viycx_qsklsjgmeld_fgd_spkgjo}`

## dlog
此題可自行輸入 $p$ 與 $g$，題目會回傳 $g^{flag} \mod p$。
要解出 flag，則此題實際上為一個 Discrete Logarithm Problem (DLP)

當 $p$ 的 order ($\phi(p)$) 是 smooth 的 (由許多小質數相乘)，則可透過 Pohlig-Hellman 將一個大的 DLP 化為數個 order 小的 DLP，此時可用大步小步等算法來快速計算小 order DLP 的解。


最後再透過 CRT 將這些解出來的 $x_i$ 算出 $x\mod\phi(p)$，即為 flag。


`dlog/exp.py`

from sage.all import *
from Crypto.Util.number import getPrime, isPrime

def gen_smooth_number(bits):
    while True:
        N = 2        
        while (l := N.bit_length()) <= bits:
            if l == bits and isPrime(N+1):
                return N
            N *= getPrime(10)

N = gen_smooth_number(1024) + 1
F = GF(N, modulus="primitive")
g = F.gen()
print(f"{N=}, {g=}")

m = get_result(N, g)
print(f"{m=}")

FLAG = discrete_log( F(m), F(g) )

若使用 Sage，其有內建 `discrete_log` 函式，因此不須自行實作 Pohlig-Hellman 與大步小步算法。


FLAG: `FLAG{YouAreARealRealRealRealDiscreteLogMaster}`

## signature
此題為 ECDSA 的簽章 server，可以傳送非指定字串的明文給他簽章，或是驗證簽章。

if option == '1':
    msg = input('What do you want? ')
    if msg == 'Give me the FLAG.':
            print('No way!')
    else:
        h = sha256(msg.encode()).digest()
        k = k * 1337 % n
        sig = prikey.sign(bytes_to_long(h), k)
        print(f'sig = ({sig.r}, {sig.s})')

其中可以發現不同次加密的 $k$ 互相有關係。
假設訊息相同 ($H$ 相同)，兩次得到的 $s_1$, $s_2$ 分別如下:

$$
s_1 = k^{–1} (H + d \times r_1) \mod n \\
s_2 = (1337k)^{–1} (H + d \times r_2) \mod n
$$

移項後得到

$$
k = s_1^{–1}H + s_1^{–1} \times d \times r_1 \mod n \\
1337k = s_2^{–1}H + s_2^{–1} \times d \times r_2 \mod n \\
1337 (s_1^{–1}H + s_1^{–1} \times d \times r_1) = s_2^{–1}H + s_2^{–1} \times d \times r_2 \mod n
$$

因此

$$
1337 s_1^{–1}H - s_2^{–1}H = d [(s_2^{–1} \times r_2) - 1337(s_1^{–1} \times r_1)] \mod n \\
d = \frac{1337 s_1^{–1}H - s_2^{–1}H}{[(s_2^{–1} \times r_2) - 1337(s_1^{–1} \times r_1)]} \mod n
$$

解開 $d$ 後即可自行簽署任意簽章。


FLAG: `FLAG{EphemeralKeyShouldBeRandom}`

## coppersmith
Flag 在加密前先 prepend 了一段很長的已知 padding，且加密的 $e$ 很小 ($e = 3$)。

此時可令明文 $m = a + x_0, x_0 \leq R$，密文 $c = m^e = (a+x_0)^e$
$x_0$ 為 $f(x) = (a+x)^3 - c$ 的整數根。


$f(x)$ 的根不好解，而透過 Coppersmith's Method，建構較容易解，且有相同根的 $Q(x)$。

設 $s(x) = c_3$, $t(x) = c_2x^2 + c_1x + c_0$
得到 $Q(x) = c_3(x^3 + 3ax^2 + 3a^2x + (a_3 - c)) + c_2Nx^2 + c_1Nx + c_0N, \deg(Q) <= 3$
且 $Q(x_0) \leq Q(R) = c_3(R^3 + 3aR^2 + 3a^2R + (a_3 - c)) + c_2NR^2 + c_1NR + c_0N$


因為 $Q(R)$ 足夠小，因此透過 LLL，則可在線性時間內解出長度最短的 vector ，且值為 $[Q_3R^3, Q_2R^2, Q_1R, Q_0]$，因此得到 Q 的各項係數


此時解 $Q(x) = Q_3x^3 + Q_2x^3 + Q_1x^3 + Q_0$ 的根則可得到 $f(x)$ 的根 $x_0$，也就是 flag。

已知 flag 長度 30 bytes，意即 $a = \text{padding} \times (30 \times 8)$

`coppersmith/exp.py`

a = bytes_to_long(padding + b"\x00" * LEN)

R = 1 << (LEN * 8)

basis = [
    [R**3, 3 * a * R**2, 3 * a ** 2 * R, a**3 - ct],
    [0, n * R ** 2, 0, 0],
    [0, 0, n * R, 0],
    [0, 0, 0, n]
]

L = matrix(basis).LLL()

v = L[0]
F.<x> = PolynomialRing(ZZ)
Q = (v[0] // R**3) * x**3 + (v[1] // R**2) * x ** 2 + (v[2] // R) * x + v[3]
result = Q.roots()

flag = long_to_bytes(result[0][0]).decode()

LLL 解開係數後，建立一個在 $\mathbb Z$ 下的多項式 $Q(x)$，呼叫 `Q.roots()` 找其解得到 flag。


FLAG: `FLAG{RandomPaddingIsImportant}`