[TOC] ## Reliable Security Approach I encrypted the flag with RSA, it is now very secure! ### 題目分析 Flag 每個字元都被 RSA 加密了。請找出 flag。 ### 解法 由於每個字元是分開加密的，明文會是 0~127 之間的數字，所以只要檢查 0~127 哪一個數字加密後等於密文就好。 ```py # from output.txt n = ... e = ... encrypted = ... flag = '' for encrypted_char in encrypted: for plaintext_char in range(128): if pow(plaintext_char, e, n) == encrypted_char: flag += chr(plaintext_char) print(flag) ``` ## Reasonably Sophisticated Application If my encryption code is very complex (and slow), then no one will be able to break it! ### 題目分析 有一個看起來非常複雜的加密演算法 `encrypt(plaintext, key, rounds)`，並且有兩個用一樣的 `key` 與 `rounds` 加密的結果。其中一個明文已知，另一個是 flag。 ### 解法 加密流程為用 `key` 算出 `derived`，然後把 `derived` 用某種方法和明文 xor，是一種（很爛的） stream cipher。因為是使用 xor，所以加密和解密的操作是一樣的。 雖然 `key_derive` 裡面的過程比較複雜，但可以發現同個 `key` 被用了兩次，所以兩次得到的 `derived` 結果會一樣。因此其實不需要知道 `key` 是什麼或是 `key_derive` 裡面在幹嘛，只要得到加密時用的 `derived` 就可以解密。 我們發現 `derived` 是長度 16 的 bytes，而且從 ```py for i in range(len(plaintext)): ciphertext[i] ^= derived[(i ^ (i >> 4)) % 16] ``` 可以知道 `derived` 就是 `ciphertext[0:16]` xor `plaintext[0:16]`。利用題目提供的 test plaintext/ciphertext 可以得到 `derived` 解密。 ```py # from output.txt test_crypt = bytes.fromhex(...) flag_crypt = bytes.fromhex(...) test_plain = b'this is a test plaintext' derived = bytearray(16) for i in range(16): derived[i] = test_plain[i] ^ test_crypt[i] flag = bytearray(flag_crypt) for i in range(len(flag)): flag[i] ^= derived[(i ^ (i >> 4)) % 16] print(flag.decode()) ``` ## Revised Signature Algorithm I heard that SHA-1 or similar functions are vulnerable to [LEA](https://en.wikipedia.org/wiki/Length_extension_attack), so I revised my hash algorithm. Can you make a fake signature? ### 題目分析 服務有兩種功能： 1. 提供 `message`，獲得 `sign(message)` 也就是 `hash(secret + nonce + message)` 的值，但 `message` 只能是八位數字 2. 提供 `nonce` 和 `sign('GIVE ME THE FLAG!!')`，獲得 flag Hash 的實作是用 byte 陣列 $s_0s_1s_2\dots s_{n-1}$ 計算 $$ \begin{align*} & (\dots (((s_0b + s_1)b + s_2)b + s_3) \dots)b + s_{n-1} \bmod p\\ \vphantom{}=\vphantom{} &\sum_{i=0}^{n-1} s_i b^{n-1-i} \bmod p \end{align*} $$ 的值，其中 $b, p$ 是未知的隨機整數。 ### 解法 如果知道 $b, p, c$，那就能從 $\operatorname{hash}(s_0s_1 \dots s_{n-1})$ 推出 $\operatorname{hash}(s_0s_1 \dots s_{n-1}c)$ 的值，因為 $$ \begin{align*} & \operatorname{hash}(s_0s_1 \dots s_{n-1}c)\\ \vphantom{}=\vphantom{} &((\dots ((s_0b + s_1)b + s_2) \dots) + s_{n-1})b + c \bmod p\\ \vphantom{}=\vphantom{} &\operatorname{hash}(s_0s_1 \dots s_{n-1}) \times b + c \bmod p\\ \end{align*} $$ 反之也可以得到 $$ \begin{align*} & \operatorname{hash}(s_0s_1 \dots s_{n-1})\\ \vphantom{}=\vphantom{} &(\operatorname{hash}(s_0s_1 \dots s_{n-1}c) - c) \times b^{-1} \bmod p\\ \end{align*} $$ 重複這個流程，就能對於任意字串 $s, t$，在不知道 $s$ 的情況下從 $\operatorname{hash}(s)$ 推出 $\operatorname{hash}(s+t)$ 的值（或是反過來）。 如果令 `s = secret + nonce`，那我們可以從 `sign(b'12345678') = hash(s + b'12345678')` 推得 `hash(s)` 然後再推得 `hash(s + b'GIVE ME THE FLAG!!') = sign(b'GIVE ME THE FLAG!!')`： ```py hash_value = sign(b'12345678') for char in reversed(b'12345678'): hash_value = (hash_value - char) * pow(b, -1, p) % p for char in b'GIVE ME THE FLAG!!': hash_value = (hash_value * b + char) % p # hash_value == sign(b'GIVE ME THE FLAG!!') ``` 所以得到 $b, p$ 就可以拿 flag。得到 $b, p$ 的方法有很多，這裡講其中一種： 我們知道 `secret` 與 `nonce` 長度，並且第 $i$ 次使用服務的 `nonce` 會等於 `str(i).encode() * 8`。因此，當 $m$ 是八位數時，`sign(m)` 的值是 $\operatorname{hash}(s_0s_1 \dots s_{15} cccccccc m_0m_1 \dots m_7)$，其中 $s$ 是 `secret`、$c$ 是 `ord('0') + i`。把他展開可以得到 $$ \begin{align*} & \operatorname{hash}(\color{blue}{s_0s_1 \dots s_{15}} \color{green}{cccccccc} {m_0m_1 \dots m_7})\\ \vphantom{}=\vphantom{} & \color{blue}{s_0b^{31} + s_1b^{30} + \dots + s_{15}b^{16}} + \\ & \color{green}{cb^{15} + cb^{14} + \dots + cb^8} + \\ & {m_0b^7 + m_1b^6 + \dots + m_6b + m_7} \bmod p\\ \end{align*} $$ 如果第 0 次、第 1 次 sign 一樣的 $m = \texttt{"00000000"}$，令得到的值為 $h_0, h_1$，那麼會有 $$ \begin{align*} & h_1 - h_0 \\ \vphantom{}\equiv\vphantom{} & (\color{blue}{s_0b^{31} + s_1b^{30} + \dots + s_{15}b^{16}} + \\ & \color{green}{\texttt{`1'}b^{15} + \texttt{`1'}b^{14} + \dots + \texttt{`1'}b^8} + \\ & \texttt{`0'}b^7 + \texttt{`0'}b^6 + \dots + \texttt{`0'}b + \texttt{`0'}) -\\ & (\color{blue}{s_0b^{31} + s_1b^{30} + \dots + s_{15}b^{16}} + \\ & \color{green}{\texttt{`0'}b^{15} + \texttt{`0'}b^{14} + \dots + \texttt{`0'}b^8} + \\ & \texttt{`0'}b^7 + \texttt{`0'}b^6 + \dots + \texttt{`0'}b + \texttt{`0'}) \\ \vphantom{}\equiv\vphantom{} & (\color{green}{\texttt{`1'}b^{15} + \texttt{`1'}b^{14} + \dots + \texttt{`1'}b^8})-\\ & (\color{green}{\texttt{`0'}b^{15} + \texttt{`0'}b^{14} + \dots + \texttt{`0'}b^8}) \\ \vphantom{}\equiv\vphantom{} & b^{15} + b^{14} + \dots + b^8 \pmod p\\ \end{align*} $$ 令 $b^{15} + b^{14} + \dots + b^8 \bmod p = r$。 因為 $h_0, h_1$ 是 $\vphantom{}\bmod p$ 的結果，$h_1 - h_0$ 的實際值可能是 $r$ 或是 $r - p$（看運氣）。 如果第 2 次 sign 的是 $m = \texttt{"000000}\color{red}{\texttt{1}}\texttt{0"}$，得到 $h_2$，那麼 $$ \begin{align*} & h_2 - h_1 \\ \vphantom{}\equiv\vphantom{} & (\color{blue}{s_0b^{31} + s_1b^{30} + \dots + s_{15}b^{16}} + \\ & \color{green}{\texttt{`2'}b^{15} + \texttt{`2'}b^{14} + \dots + \texttt{`2'}b^8} + \\ & \texttt{`0'}b^7 + \texttt{`0'}b^6 + \dots + \color{red}{\texttt{`1'}b} + \texttt{`0'}) -\\ & (\color{blue}{s_0b^{31} + s_1b^{30} + \dots + s_{15}b^{16}} + \\ & \color{green}{\texttt{`1'}b^{15} + \texttt{`1'}b^{14} + \dots + \texttt{`1'}b^8} + \\ & \texttt{`0'}b^7 + \texttt{`0'}b^6 + \dots + \color{red}{\texttt{`0'}b} + \texttt{`0'}) \\ \vphantom{}\equiv\vphantom{} & (\color{green}{\texttt{`2'}b^{15} + \texttt{`2'}b^{14} + \dots + \texttt{`2'}b^8})-\\ & (\color{green}{\texttt{`1'}b^{15} + \texttt{`1'}b^{14} + \dots + \texttt{`1'}b^8}) +\\ & (\color{red}{\texttt{`1'}b} - \color{red}{\texttt{`0'}b})\\ \vphantom{}\equiv\vphantom{} & b^{15} + b^{14} + \dots + b^8 + b\\ \vphantom{}\equiv\vphantom{} & r + b \pmod p\\ \end{align*} $$ 而 $h_2 - h_1$ 的實際值可能是 $r + b$ 或是 $r + b - p$（看運氣）。 如果第 3 次 sign 一樣的 $m = \texttt{"00000010"}$，得到 $h_3$，那麼與 $h_1 - h_0$ 同理，$h_3 - h_2$ 會是 $r$ 或 $r - p$。 若 $h_3 - h_2 < 0$ 且 $h_1 - h_0 \ge 0$，那麼 $h_3 - h_2 = r - p, h_1 - h_0 = r$，所以 $p = (h_1 - h_0) - (h_3 - h_2)$，並且 $b = (h_2 - h_1) - r \bmod p$。因為有一些運氣成份，這個解法可能要跑幾次才會過。有了 $b, p$ 之後就可以用之前的方法獲得 `b'GIVE ME THE FLAG!!'` 的 signature 來拿 flag。可能有其他更簡單的方法拿 $b, p$，但這個應該比較直觀（？）。 :::spoiler 完整 script ```py import pwn io = pwn.remote('localhost', '33334') def sign_password(password): io.sendlineafter(b'> ', b'1') io.sendlineafter(b'Password? ', password) signature = bytes.fromhex(io.recvline().decode()) _nonce, hash = signature[:8], signature[8:] return int.from_bytes(hash, 'big') def verify_password(password, signature): io.sendlineafter(b'> ', b'2') io.sendlineafter(b'Password? ', password) io.sendlineafter(b'Signature? ', signature.hex().encode()) return io.recvline().decode() h0 = sign_password(b'00000000') h1 = sign_password(b'00000000') h2 = sign_password(b'00000010') h3 = sign_password(b'00000010') # r = b^8 + b^9 + ... + b^15 # h1 - h0 = r (mod p) # h2 - h1 = r + b (mod p) # h3 - h2 = r (mod p) if h1 - h0 > 0 and h3 - h2 < 0: r = h1 - h0 negr = h3 - h2 elif h1 - h0 < 0 and h3 - h2 > 0: negr = h1 - h0 r = h3 - h2 else: print('solve fail') exit(1) p = r - negr b = ((h2 - h1) - r) % p # make h4 = sign('GIVE ME THE FLAG!!') h4 = h3 for char in reversed(b'00000010'): h4 = (h4 - char) * pow(b, -1, p) % p for char in b'GIVE ME THE FLAG!!': h4 = (h4 * b + char) % p h4 = h4.to_bytes(64, 'big') nonce = b'3' * 8 flag = verify_password(b'GIVE ME THE FLAG!!', nonce + h4) print(flag) ``` :::