HackMD
Lab 1 - Substitution Cipher
這題是類似凱薩加密的移項式密碼，會將字串 '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}' 裡的每個字元同時位移。因為位移 (key) 只有 65 種可能，所以只要枚舉 key 就可以在其中一種找出答案。
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。
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\) 之後就可以預測接下來出現的數字。
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
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。
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}\)。
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\) 是兩個大質數的乘積所以是奇數，並且：
- 若 \(0 \le k < n/2\)，則 \(0 \le 2k < n \Leftrightarrow (2k \bmod n) \bmod 2 = 2k \bmod 2 = 0\)。
- 若 \(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\)。由以上的觀察可以知道：
- 若 \(s^{\prime d} \bmod n \bmod 2 = 0\)，則 \(2m \bmod n \bmod 2 = 0 \Leftrightarrow 0 \le m < n/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\) 的值。
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 用有理數來計算範圍，若使用整數或浮點數會有不準確的問題。
賽前
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 成功時的執行時間才會獲得正確的結果。
