[TOC]

## Lab 1 - Substitution Cipher

這題是類似凱薩加密的移項式密碼，會將字串 `'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}'` 裡的每個字元同時位移。因為位移 (`key`) 只有 65 種可能，所以只要枚舉 `key` 就可以在其中一種找出答案。

:::spoiler Code

chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}'

encrypted = 'iodjEv7eL6YN76HG0DSH2XJ4De4G_J0F'

for key in range(len(chars)):
    flag = ''
    for char in encrypted:
        num = chars.index(char)
        num = (num - key) % len(chars)
        flag += chars[num]
    print(key, flag)

:::

另外也可以直接從 `encrypted[0]` (`'i'`) 和 `flag[0]` (`'F'`) 直接推出 `key = 42`。

## Lab 2 - XOR Key Reuse

雖然 `key_derive` 裡面做了許多看似複雜的操作，但加密的方法只是將算出的 `keystream` 和輸入做 XOR，所以把第一次加密的輸出和輸入 XOR 即可得到 `keystream`。

因為兩次加密的 `key` 相同，所以 `keystream` 也會相同。將上面得到的 `keystream` 與密文 XOR 即可拿到 flag。

:::spoiler Code

test_crypt = bytes.fromhex('c64a98d7e96fe0b82aba3599055a1030de4398cabd63ebec')
flag_crypt = bytes.fromhex('f46eb0e3b26fccef24f46688295c5535c147aec5966df6e114fb269d1f401e6e9c5f')

test = b'this is a test plaintext'
keystream = bytearray(16)
for i in range(16):
    keystream[i] = test[i] ^ test_crypt[i]

flag = bytearray(flag_crypt)
for i in range(len(flag)):
    flag[i] ^= keystream[i % 16]

print(flag.decode())

:::

## Lab 3 - LCG

令 $s_0$, $s_1$, $s_2$ 為 LCG 前三次產生的數字，則

$$
\begin{cases}
s_1 = a s_0 + b & \pmod m \\
s_2 = a s_1 + b & \pmod m \\
\end{cases}
$$

於是有

$$
\begin{align*}
&\phantom{\Rightarrow} s_2 - s_1 = a (s_1 - s_0) & \pmod m \\
&\Rightarrow a = (s_2 - s_1) (s_1 - s_0)^{-1} & \pmod m \\
&\Rightarrow b = s_1 - a s_0 & \pmod m \\
\end{align*}
$$

解出 $a$, $b$ 之後就可以預測接下來出現的數字。

:::spoiler Code

import pwn
from Crypto.Util.number import inverse

m = 1000000000000000000000000000000000000000000000000000000000007

io = pwn.remote('165.192.159.206', 10100)

io.sendlineafter(b'number: ', b'0')
s0 = int(io.recvline().split()[-1])
io.sendlineafter(b'number: ', b'0')
s1 = int(io.recvline().split()[-1])
io.sendlineafter(b'number: ', b'0')
s2 = int(io.recvline().split()[-1])

a = (s2 - s1) * inverse(s1 - s0, m) % m
b = (s1 - a * s0) % m

s3 = (a * s2 + b) % m
io.sendlineafter(b'number: ', str(s3).encode())
io.interactive()

:::

## Lab 4 - ECB

這題是經典的 ECB Prepend Oracle Attack，我們可以對任意 `s` 獲得 `encrypt(s + flag)` 的值，目標是找出 `flag`。

假設 `s` 是 `AAAAAAAAAAAAAAA`，則 `s + flag` 的第一個區塊就會是 `AAAAAAAAAAAAAAA?` 其中 `?` 是 `flag[0]`。我們可以把 `AAAAAAAAAAAAAAA0`、`AAAAAAAAAAAAAAA1`、`AAAAAAAAAAAAAAA2` 等等分別加密，然後判斷何者與 `encrypt(s + flag)` 的第一個區塊相同，即可獲得 `flag[0]`。同理利用 `'AAAAAAAAAAAAAA' + flag[0]` 可以得到 `flag[1]`，以此類推能獲得前 16 個字元。

我們可以依序找出每個字元。在解 `flag[i]` 時，我們可以送出 $15 - i \bmod 15$ 個 `A`，這時包含 `flag[i]` 的區塊會包含 15 個已知字元以及要求出的 `flag[i]`，利用這些已知字元以及枚舉未知字元可以找出 `flag[i]`。

i = 5 example
flag = 'FLAG{?'
AAAAAAAAAAFLAG{?
<-------------->
     block1

i = 25 example
flag = 'FLAG{abcabcabcabcabcabcab?'
AAAAAAFLAG{abcabcabcabcabcabcab?
<--------------><-------------->
     block1          block2

:::spoiler Code

import pwn

io = pwn.remote('165.192.159.206', 10101)

def get_ciphertext(s):
    io.sendlineafter(b'encrypt: ', s.encode())
    return bytes.fromhex(io.readline().split()[-1].decode())

def brute_force(pos, known_flag):
    pos += 16
    off = 15 - pos % 16
    block = pos // 16
    padded_flag = 'A' * (off + 16) + known_flag
    chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}'

    target_ct = get_ciphertext('A' * (off + 16))[block*16:block*16+16]

    for guess in chars:
        pt = padded_flag[-15:] + guess
        if get_ciphertext(pt)[:16] == target_ct:
            return guess

length = int(io.readline().split()[-1])

known_flag = ''
for i in range(length):
    known_flag += brute_force(i, known_flag)
    print(known_flag)

:::

## Lab 5 - Padding Oracle

我們可以知道任意密文解密完的 padding 是否合法。

求最後一個區塊的最後一個 byte：我們可以將前一個區塊的密文（或是第一個區塊的 IV）的最後一個 byte 分別 XOR 0~255 的每一個數字，而這也會讓解密的結果最後一個 byte 也 XOR 該數字。如果解密成功，代表最後一個 byte XOR 該數字是合法的 padding（高機率是 `0x01`），由此可以得到原本解密完的最後一個 byte。

求最後一個區塊的倒數第 $i$ 個 byte：若已知它之後的值，則可以透過對前一個區塊的密文 XOR 來使得解密完最後 $i-1$ 個 byte 皆為 $i$。接下來一樣把倒數第 $i$ 個 byte 分別 XOR 0~255 的每一個數字。如果解密成功，代表倒數第 $i$ 個 byte XOR 該數字也是 $i$（才能形成合法 padding），所以可以求得倒數第 $i$ 個 byte。

對於每個 block，可以用以上方法從最後開始一個一個字元還原 flag。

:::spoiler Code

import pwn

io = pwn.remote('165.192.159.206', 10102)

def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

def oracle(iv, ct):
    io.sendlineafter(b'decrypt: ', ct.hex().encode())
    io.sendlineafter(b'IV: ', iv.hex().encode())
    return io.recvline().strip() == b'Ok'

def get_block(iv, ct):
    cur = b''
    for i in range(15, -1, -1):
        padding = bytes([16 - i] * (16 - i))
        for b in range(256):
            guess = bytes([b]) + cur
            new_iv = bytes(i) + xor(padding, bytes([b]) + cur)
            if oracle(new_iv, ct):
                cur = guess
                break
    return xor(iv, cur)

ct = bytes.fromhex(io.readline().split()[-1].decode())
iv = bytes.fromhex(io.readline().split()[-1].decode())

flag = get_block(iv, ct[0:16])
for i in range(len(ct) // 16):
    flag += get_block(ct[i*16-16:i*16], ct[i*16:i*16+16])
print(flag)

:::

## Lab 6 - Broadcast Attack

這題可以利用一個簡單版本的中國剩餘定理：若 $\gcd(m, n) = 1$，則 $x \equiv a \pmod m, x \equiv b \pmod n$ 若且唯若

$$
x \bmod mn = (m^{-1}(b - a) \bmod n) m + a
$$

由於這題所有的 $n_i$ 皆互質，重複用上面的公式可以找到 $y$ 使得所有 $y \equiv c_i \equiv m^e \pmod{n_i}$ 皆成立，並求得 $y \bmod \prod n_i$ 的值。

因為 $\prod n_i > m^e$ 且 $y \equiv m^e \pmod{\prod n_i}$，我們知道 $y \bmod \prod n_i = m^e$ ，所以 $m = \sqrt[e]{y \bmod \prod n_i}$。

:::spoiler Code

from Crypto.Util.number import long_to_bytes, inverse

def crt(a, m, b, n):
    x = inverse(m, n)
    x = ((b - a) * x) % n * m + a
    return x

def root_17th(x):
    ans = 0
    for step in range(1024, -1, -1):
        if (ans + 2**step)**17 <= x:
            ans += 2**step
    return ans

mods = []
for line in open('output.txt'):
    n, c = line.split()
    mods.append((int(c), int(n)))

mod = 0
prod = 1
for c, n in mods:
    mod = crt(mod, prod, c, n)
    prod *= n

pow_flag_17 = mod
flag = long_to_bytes(root_17th(pow_flag_17))
print(flag)

:::

以上 code 使用二分搜來求 $\sqrt[17]{x}$。

## Lab 7 - LSB Oracle

我們知道 $s^e \bmod n$ 的值，並且對於任意的 $m$ 可以知道 $(m^d \bmod n) \bmod 2$。

首先可以觀察到 $n$ 是兩個大質數的乘積所以是奇數，並且：

1. 若 $0 \le k < n/2$，則 $0 \le 2k < n \Leftrightarrow (2k \bmod n) \bmod 2 = 2k \bmod 2 = 0$。
2. 若 $n/2 < k < n$，則 $n \le 2k < 2n \Leftrightarrow (2k \bmod n) \bmod 2 = (2k - n) \bmod 2 = 1$。

令 $s^\prime = s^e \times 2^e \bmod n$，則 $s^{\prime d} \bmod n = s^{ed} \times 2^{ed} \bmod n = 2s$。由以上的觀察可以知道：

1. 若 $s^{\prime d} \bmod n \bmod 2 = 0$，則 $2m \bmod n \bmod 2 = 0 \Leftrightarrow 0 \le m < n/2$。
2. 若 $s^{\prime d} \bmod n \bmod 2 = 1$，則 $2m \bmod n \bmod 2 = 1 \Leftrightarrow n/2 < m < n$。

於是可以將 $s$ 的可能值範圍縮小一半。如果再令 $s^{\prime\prime} = s^{\prime e} \times 2^e \bmod n$，那同理可以將 $s^\prime$ 的範圍也縮小一半，即 $s$ 的可能值範圍變成 $1/4$。重複這個過程 $\log_2 n$ 次後，用類似二分搜的方法就可以確定 $s$ 的值。

:::spoiler Code

import pwn
from fractions import Fraction

io = pwn.remote('165.192.159.206', 10103)

keys = io.recvline().split()
n, e = int(keys[1]), int(keys[2])

hint = io.recvline().split()
hint = int(hint[1])

l, r = Fraction(0), Fraction(n)
c = hint
while l + 1 < r:
    m = (l + r) / 2
    c = c * pow(2, e, n) % n
    io.sendlineafter(b'Ciphertext: ', str(c).encode())
    lsb = io.recvline().strip() == b'Odd'
    if lsb:
        l = m
    else:
        r = m
secret = int(r)

io.sendline(b'0')
io.sendline(str(secret).encode())
io.interactive()

:::

以上的 code 用有理數來計算範圍，若使用整數或浮點數會有不準確的問題。

## 賽前

:::spoiler Code

import json
import pwn
import time

admin_data = json.loads('''
{"rsa_data": "391b06a1740b8c9cf1c8d2bb66ba5b191caa8534b4be18c22ce81069658dd2cd3ca3a8d1a3fc8dfab4b68a6b076bf89be807404e0a98dd1bf9daaf8ba34e0556131d3e56cae61c0302d24a177481209e82de7ecf91c2fe66aa39162d7af9c2fdabaf0c444badfc6b82b071fda8e3b26d4d3e57dba25c36298601ae0153c73b7469c472ac4702531c38849772e7c6e24313e6eb7def64a7bec1c21150c1fded52b3ca716d4444b4d75836dff8c92a371f6256ee7a48034f6d5ea949d982f9f05c04d3d7cce10bd11b806cc02088b42fa0cb069390700fb586287ba224ea0b210ebd0479a4f1d2ef5f914bcc861125b7d8d714cf0feecb515c1b1ef869e91ca179", "aes_data": "1709bf9489f6df6dc31491cee4711f7a2a3e050f1ed3e9772442e8a8483e341313713383dd31fbf0133d55e977b8edf54ba832002ee4ee52da32c260b083a35b01626201c36dad6fca7b2be2aa03d90bf5c9a601a24149f55cdcd39f0bf6a032bfabeebee5259a21e188f5c5f8776cd9d7c072054781169174bddbc390e6da21bd7b85f76c93f48914fb1958ac89e464511d9a17fb2174aab825cb13eb3f0dfa"}
''')

io = pwn.remote('165.192.159.206', 7777)

def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

def timing_oracle(iv, ct, hmac):
    data = json.dumps({'rsa_data' : admin_data['rsa_data'], 'aes_data' : (iv + ct + hmac).hex()}).encode()
    time_start = time.time()
    for _ in range(3):
        io.sendlineafter(b'> ', data)
        io.recvline()
    time_end = time.time()
    return (time_end - time_start) / 3 > 0.2

def get_block(iv, ct, hmac):
    cur = b''
    for i in range(15, -1, -1):
        padding = bytes([16 - i] * (16 - i))
        for b in range(256):
            guess = bytes([b]) + cur
            new_iv = bytes(i) + xor(padding, bytes([b]) + cur)
            if timing_oracle(new_iv, ct, hmac):
                cur = guess
                print(xor(iv[i:], cur))
                break
    return xor(iv, cur)

aes_data = bytes.fromhex(admin_data['aes_data'])
iv, ct, hmac = aes_data[:16], aes_data[16:-16], aes_data[-16:]

io.recvuntil(b'Welcome to the n1ogin system!\n')

ct_blocks = [iv] + [ct[i*16:i*16+16] for i in range(len(ct) // 16)]
for i in range(8, len(ct_blocks)):
    pt_block = get_block(ct_blocks[i - 1], ct_blocks[i], hmac)
    print(pt_block)

:::

Code 裡的 0.2 秒要改成實際 padding 成功時的執行時間才會獲得正確的結果。