• Reliable Security Approach
  • 題目分析
  • 解法
• Reasonably Sophisticated Application
  • 題目分析
  • 解法
• Revised Signature Algorithm
  • 題目分析
  • 解法

Reliable Security Approach

I encrypted the flag with RSA, it is now very secure!

題目分析

Flag 每個字元都被 RSA 加密了。請找出 flag。

解法

由於每個字元是分開加密的，明文會是 0~127 之間的數字，所以只要檢查 0~127 哪一個數字加密後等於密文就好。

# 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，而且從

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 解密。

# 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, 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_0{s}_1{s}_2\dots s_{n-1}$ 計算

$$\begin{array}{rl}& (\dots (((s_{0}b+s_1)b+s_2)b+s_3)\dots )b+s_{n-1}modp\\ \phantom{}=\phantom{}& \sum _{i=0}^{n-1}{s}_i{b}^{n-1-i}modp\end{array}$$

的值，其中

$b,p$ 是未知的隨機整數。

解法

如果知道

$b,p,c$，那就能從

$\mathrm{hash}(s_0{s}_1\dots s_{n-1})$ 推出

$\mathrm{hash}(s_0{s}_1\dots s_{n-1}c)$ 的值，因為

$$\begin{array}{rl}& \mathrm{hash}(s_0{s}_1\dots s_{n-1}c)\\ \phantom{}=\phantom{}& ((\dots ((s_{0}b+s_1)b+s_2)\dots )+s_{n-1})b+cmodp\\ \phantom{}=\phantom{}& \mathrm{hash}(s_0{s}_1\dots s_{n-1})\times b+cmodp\end{array}$$

反之也可以得到

$$\begin{array}{rl}& \mathrm{hash}(s_0{s}_1\dots s_{n-1})\\ \phantom{}=\phantom{}& (\mathrm{hash}(s_0{s}_1\dots s_{n-1}c)-c)\times b^{-1}modp\end{array}$$

重複這個流程，就能對於任意字串

$s,t$，在不知道

$s$ 的情況下從

$\mathrm{hash}(s)$ 推出

$\mathrm{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!!')：

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) 的值是

$\mathrm{hash}(s_0{s}_1\dots s_{15}cccccccc{m}_0{m}_1\dots m_7)$，其中

$s$ 是 secret、

$c$ 是 ord('0') + i。把他展開可以得到

$$\begin{array}{rl}& \mathrm{hash}(\text{color}blue{s}_0{s}_1\dots s_{15}\text{color}greencccccccc{m}_0{m}_1\dots m_7)\\ \phantom{}=\phantom{}& \text{color}blue{s}_0{b}^{31}+s_1{b}^{30}+\cdots +s_{15}{b}^{16}+\\ & \text{color}greenc{b}^{15}+c{b}^{14}+\cdots +c{b}^8+\\ & m_0{b}^7+m_1{b}^6+\cdots +m_{6}b+m_{7}modp\end{array}$$

如果第 0 次、第 1 次 sign 一樣的

$m=\mathtt{\text{"00000000"}}$，令得到的值為

$h_0,h_1$，那麼會有

$$\begin{array}{rl}& h_1-h_0\\ \phantom{}\equiv \phantom{}& (\text{color}blue{s}_0{b}^{31}+s_1{b}^{30}+\cdots +s_{15}{b}^{16}+\\ & \text{color}green\mathtt{\text{`1'}}{b}^{15}+\mathtt{\text{`1'}}{b}^{14}+\cdots +\mathtt{\text{`1'}}{b}^8+\\ & \mathtt{\text{`0'}}{b}^7+\mathtt{\text{`0'}}{b}^6+\cdots +\mathtt{\text{`0'}}b+\mathtt{\text{`0'}})-\\ & (\text{color}blue{s}_0{b}^{31}+s_1{b}^{30}+\cdots +s_{15}{b}^{16}+\\ & \text{color}green\mathtt{\text{`0'}}{b}^{15}+\mathtt{\text{`0'}}{b}^{14}+\cdots +\mathtt{\text{`0'}}{b}^8+\\ & \mathtt{\text{`0'}}{b}^7+\mathtt{\text{`0'}}{b}^6+\cdots +\mathtt{\text{`0'}}b+\mathtt{\text{`0'}})\\ \phantom{}\equiv \phantom{}& (\text{color}green\mathtt{\text{`1'}}{b}^{15}+\mathtt{\text{`1'}}{b}^{14}+\cdots +\mathtt{\text{`1'}}{b}^8)-\\ & (\text{color}green\mathtt{\text{`0'}}{b}^{15}+\mathtt{\text{`0'}}{b}^{14}+\cdots +\mathtt{\text{`0'}}{b}^8)\\ \phantom{}\equiv \phantom{}& b^{15}+b^{14}+\cdots +b^8(\mathrm{mod}p)\end{array}$$

令

$b^{15}+b^{14}+\cdots +b^{8}modp=r$。
因為

$h_0,h_1$ 是

$\phantom{}modp$ 的結果，

$h_1-h_0$ 的實際值可能是

$r$ 或是

$r-p$（看運氣）。

如果第 2 次 sign 的是

$m=\mathtt{\text{"000000}}\text{color}red\mathtt{\text{1}}\mathtt{\text{0"}}$，得到

$h_2$，那麼

$$\begin{array}{rl}& h_2-h_1\\ \phantom{}\equiv \phantom{}& (\text{color}blue{s}_0{b}^{31}+s_1{b}^{30}+\cdots +s_{15}{b}^{16}+\\ & \text{color}green\mathtt{\text{`2'}}{b}^{15}+\mathtt{\text{`2'}}{b}^{14}+\cdots +\mathtt{\text{`2'}}{b}^8+\\ & \mathtt{\text{`0'}}{b}^7+\mathtt{\text{`0'}}{b}^6+\cdots +\text{color}red\mathtt{\text{`1'}}b+\mathtt{\text{`0'}})-\\ & (\text{color}blue{s}_0{b}^{31}+s_1{b}^{30}+\cdots +s_{15}{b}^{16}+\\ & \text{color}green\mathtt{\text{`1'}}{b}^{15}+\mathtt{\text{`1'}}{b}^{14}+\cdots +\mathtt{\text{`1'}}{b}^8+\\ & \mathtt{\text{`0'}}{b}^7+\mathtt{\text{`0'}}{b}^6+\cdots +\text{color}red\mathtt{\text{`0'}}b+\mathtt{\text{`0'}})\\ \phantom{}\equiv \phantom{}& (\text{color}green\mathtt{\text{`2'}}{b}^{15}+\mathtt{\text{`2'}}{b}^{14}+\cdots +\mathtt{\text{`2'}}{b}^8)-\\ & (\text{color}green\mathtt{\text{`1'}}{b}^{15}+\mathtt{\text{`1'}}{b}^{14}+\cdots +\mathtt{\text{`1'}}{b}^8)+\\ & (\text{color}red\mathtt{\text{`1'}}b-\text{color}red\mathtt{\text{`0'}}b)\\ \phantom{}\equiv \phantom{}& b^{15}+b^{14}+\cdots +b^8+b\\ \phantom{}\equiv \phantom{}& r+b(\mathrm{mod}p)\end{array}$$

而

$h_2-h_1$ 的實際值可能是

$r+b$ 或是

$r+b-p$（看運氣）。

如果第 3 次 sign 一樣的

$m=\mathtt{\text{"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)-rmodp$。因為有一些運氣成份，這個解法可能要跑幾次才會過。有了

$b,p$ 之後就可以用之前的方法獲得 b'GIVE ME THE FLAG!!' 的 signature 來拿 flag。可能有其他更簡單的方法拿

$b,p$，但這個應該比較直觀（？）。

完整 script

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)