# TMUCTF 2021
Rank: 58th
Points: 2254
## Common Factor (52 solves, 383 pts)
:::spoiler **Source Code**
```python=
from Crypto.Util.number import *
from functools import reduce
def encrypt(msg, n):
enc = pow(bytes_to_long(msg), e, n)
return enc
e = 65537
primes = [getPrime(2048) for i in range(5)]
n = reduce(lambda a, x: a * x, primes, 1)
print(n)
x1 = primes[1] ** 2
x2 = primes[2] ** 2
x3 = primes[1] * primes[2]
y1 = x1 * primes[2] + x2 * primes[1]
y2 = x2 * (primes[3] + 1) - 1
y3 = x3 * (primes[3] + 1) - 1
print(x2 + x3 + y1)
print(y2 + y3)
with open('flag', 'rb') as f:
flag = f.read()
print(encrypt(flag, n))
```
:::
從題目名稱也也能看出這題要幹嘛 :D。首先，根據定義化簡可得$$x_2+x_3+y_1 = p_2(p_1+p_2)(p_1+1)$$ 以及 $$y_2+y_3 = p_2(p_1+p_2)(p_3+1)-2$$ 因為質數都是隨機取的，所以基本上可以確定 $$p_2 = (x_2+x_3+y_1, n)$$ 另一方面，我們知道 $$p_2(p_1+p_2) \mid (x_2+x_3+y_1, y_2+y_3+2) $$ 並且他們的商是 $(p_1+1, p_3+1)$，可以預期它不會太大。直接窮舉就能得到 $p_1$，從而也知道 $p_3$。
一般來說，RSA 要完全分解才能解密，但是我們並沒有 $p_0, p_4$ 的資訊，因此就想說把它當作 $N = p_1p_2p_3$ 的 RSA (參考 CryptoCTF 2020 Three Raven)
:::spoiler **Script**
```python=
from Crypto.Util.number import *
from functools import reduce
from output import *
from math import gcd
### x2 + x3 + y1 = p2(p1 + p2)(p1 + 1)
### y2 + y3 + 2 = p2(p1 + p2)(p3 + 1)
p2 = gcd(n, a)
assert isPrime(p2)
_ = gcd(a, b+2) // p2
for i in range(10, 30):
if _ % i == 0:
p1 = _ // i - p2
if isPrime(p1) and n % p1 == 0:
break
assert a == p2 * (p1 + p2) * (p1 + 1)
p3 = (b+2) // (p2 * (p1 + p2)) - 1
assert (b+2) == p2 * (p1 + p2) * (p3 + 1) and isPrime(p3)
fake_phi = (p1 - 1) * (p2 - 1) * (p3 - 1)
d = pow(65537, -1, fake_phi)
pt = pow(c, d, p1 * p2 * p3)
flag = long_to_bytes(pt)
print(flag)
```
:::
:::success
TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}
:::
## 435! (45 solves, 413 pts)
:::spoiler **Source Code**
```python=
import binascii
import hashlib
import sys
from Crypto.Cipher import AES
key = b'*XhN2*8d%8Slp3*v'
key_len = len(key)
def pad(message):
padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
return message + padding
def encrypt(message, key, iv):
aes = AES.new(key, AES.MODE_CBC, iv)
return aes.encrypt(message)
h = hashlib.sha256(key).hexdigest()
hidden = binascii.unhexlify(h)[:10]
message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden
with open('flag', 'rb') as f:
IV = f.read().strip(b'TMUCTF{').strip(b'}')
print(binascii.hexlify(encrypt(pad(message), key, IV)))
```
:::
題目給了 AES-CBC 的部分 key，然後用 flag 當作 IV，加密一個跟 key 有關的訊息，然後密文也只有給一部分。
注意到 key 只有被遮掉三個 character，並且密文後一個半個 block 都沒被碼掉，所以能去暴搜所有可能的 key，然後看下面的等式有沒有可能成立：$$ AES_{ECB}(msg[i] \oplus block[i-1]) = block[i] $$ 具體的方式是去看 $$ AES_{ECB}^{-1}(block[i]) \oplus msg[i] $$ 跟 $block[i-1]$ 已知的 bytes 有沒有一致。若有的話，代表是可能的 key。
:::spoiler **Find key**
```python=
import binascii
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
key_len = 16
def pad(message):
padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
return message + padding
def Decrypt(c, k):
aes = AES.new(k, AES.MODE_ECB)
return aes.decrypt(c)
# block1 = binascii.unhexlify("************1b3*******9f43fd6634")
ind = [6, 11, 12, 13, 14, 15]
block1 = {
6: b'\x1b',
11: b'\x9f',
12: b'\x43',
13: b'\xfd',
14: b'\x66',
15: b'\x34'
}
block2 = binascii.unhexlify("1f3ef3fab2bbfc838b9ef71867c3bcbb")
chars = [chr(_) for _ in range(128)]
for char1 in chars:
for char2 in chars:
for char3 in chars:
key = char1 + "XhN2" + char2 + "8d%8Slp3" + char3 + "v"
key = key.encode()
h = hashlib.sha256(key).hexdigest()
hidden = binascii.unhexlify(h)[:10]
message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden
message = pad(message)
message = message[-16:]
decrypted_block2 = Decrypt(block2, key)
check = True
for i in ind:
_ = decrypted_block2[i] ^ block1[i][0]
if message[i:i+1] != long_to_bytes(_):
check = False
if check:
print("Found!")
print(key)
```
:::
倒著解密回去就可以知道 $flag\oplus msg[0]$ 的值，也就拿到 flag 啦！
:::spoiler **Get flag**
```python=
import binascii
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
key = b'0XhN2!8d%8Slp3Ov'
key_len = len(key)
def pad(message):
padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
return message + padding
h = hashlib.sha256(key).hexdigest()
hidden = binascii.unhexlify(h)[:10]
message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden
message = pad(message)
def decrypt(c, k):
aes = AES.new(k, AES.MODE_ECB)
return aes.decrypt(c)
def xor_blocks(b1, b2):
res = b''
for x, y in zip(b1, b2):
res += long_to_bytes(x^y)
return res
current_block = binascii.unhexlify("1f3ef3fab2bbfc838b9ef71867c3bcbb")
for i in range(6):
current_block = decrypt(current_block, key)
j, k = -16 * (i+1), -16 * i
if k:
c = message[j: k]
else:
c = message[j:]
current_block = xor_blocks(current_block, c)
print(current_block)
```
:::
:::success
TMUCTF{Y0U_D3CrYP73D_17}
:::
## Broken RSA (21 solves, 482 pts)
:::spoiler **Source Code**
```python=
from Crypto.Util.number import *
e = 65537
with open('n', 'rb') as f:
n = int(f.read())
with open('secret', 'rb') as f:
secret_msg = f.read()
pads = [b'\x04', b'\x02', b'\x00', b'\x01', b'\x03']
with open('out.txt', 'w') as f:
for i in range(len(pads)):
for j in range(len(pads)):
msg = pads[j] * (i + 1) + b'TMUCTF' + pads[len(pads) - j - 1] * (i + 1)
enc = pow(bytes_to_long(msg), e, n)
f.write(str(enc) + '\n')
enc = pow(bytes_to_long(secret_msg), e, n)
f.write(str(enc))
```
:::
我們拿到了很多個已知明文的加密結果以及加密後的 flag，算 gcd 就能把 $n$ 給找回來，但也僅限於此。關鍵點是要去看 $n$ 的二進制，然後會發現中間有很多 $0$，頭尾看起來是形如 $$2^{k}\triangle + (2^{k}-1-\triangle) = (2^{k}-1)(\triangle+1)$$ 的東西，於是 $n$ 會被 $2^{k-1}$ 整除，剩下就輕鬆ㄌ！
:::spoiler **Script**
```python=
from Crypto.Util.number import *
with open('output.txt', 'r') as f:
for _ in range(25):
f.readline()
enc = int(f.readline().strip())
from tmp import n
p = (1 << 1279) - 1
q = n // p
assert isPrime(p) and isPrime(q)
flag = pow(enc, pow(65537, -1, (p-1)*(q-1)), n)
print(long_to_bytes(flag))
```
:::
:::success
TMUCTF{Ju57_4n07h3r_R54_ch4ll3n63!_C0u1d_y0u_50lv3_17?!?}
:::
## Baby Encoder (17 solves, 489 pts)
:::spoiler **Source Code**
```python=
from Crypto.Util.number import bytes_to_long
def displace(a, base):
res = []
for i in range(base):
if base + i >= len(a):
for j in range(base - 1, i - 1, -1):
res.append(a[j])
return res
res.append(a[base + i])
res.append(a[i])
for j in range(len(a) - 1, 2 * base - 1, -1):
res.append(a[j])
return res
def flag_encoder(flag):
encoded_flag = []
n = len(flag)
for i in range(n):
encoded_flag.append(ord(flag[i]) ^ ord(flag[i - 1]))
for i in range(n):
encoded_flag[i] ^= encoded_flag[n - i - 1]
a = []
for i in range(0, n, 3):
a.append(encoded_flag[i] + encoded_flag[i + 1])
a.append(encoded_flag[i + 1] + encoded_flag[i + 2])
a.append(encoded_flag[i + 2] + encoded_flag[i])
encoded_flag = a
for i in range(1, n):
if i % 6 == 0:
encoded_flag = displace(encoded_flag, i)
encoded_flag = ''.join(chr(encoded_flag[i]) for i in range(n))
return encoded_flag
with open('flag', 'rb') as f:
flag = f.read().decode('UTF-8')
print(str(bytes_to_long(flag_encoder(flag).encode())))
```
:::
不難注意到 displace 是將陣列重排，我們也不用管它具體怎麼操作，把 identity 丟進去給它排，就能輕鬆的逆向回來。
:::spoiler **Reverse displace**
```python=
def rev_displace(a, base):
identity = [i for i in range(n)]
inv = displace(identity, base)
res = [0 for i in range(n)]
for _ in range(n):
res[inv[_]] = a[_]
return res
for i in range(n-1, 0, -1):
if i % 6 == 0:
encoded_flag = rev_displace(encoded_flag, i)
```
:::
接著是將陣列三個三個一組，然後換成兩兩相加的結果，也就是 $$ (a,b,c) \rightarrow (a+b, b+c, c+a) $$ 很明顯地，$$ (d,e,f) \rightarrow \left(\frac{d+f-e}{2},\frac{e+d-f}{2},\frac{f+e-d}{2}\right) $$ 是它的逆操作。在前一步是將陣列頭尾配對，依序給它們做 XOR，那因為 XOR 是 involution，所以直接反著 XOR 回去就能得到原本的陣列。
:::spoiler
```python=
for i in range(0, n, 3):
encoded_flag[i] = (a[i] + a[i+2] - a[i+1]) // 2
encoded_flag[i+1] = (a[i+1] + a[i] - a[i+2]) // 2
encoded_flag[i+2] = (a[i+2] + a[i+1] - a[i]) // 2
for i in range(n-1, -1, -1):
encoded_flag[i] ^= encoded_flag[n - i - 1]
```
:::
最後由於陣列是透過 flag 相鄰的字元 XOR 得來的，我們枚舉所有可能的開頭，然後看解出來的 flag 有沒有 TMUCTF 即可。
:::spoiler **Get Flag**
```python=
for c in range(128):
possible_flag = str(chr(c))
for i in range(1, n):
next_char = chr(ord(possible_flag[-1]) ^ encoded_flag[i])
possible_flag += next_char
if "TMUCTF" in possible_flag:
print(possible_flag)
```
:::
:::success
TMUCTF{0h!_3nc0d1n6_15_n07_4lw4y5_4_600d_1d34_70_h1d3_7h3_fl46__d0_y0u_46r33?}
:::
## Signed Flag (15 solves, 492 pts)
:::spoiler **Source Code**
```python=
from string import ascii_uppercase, ascii_lowercase, digits
from random import randrange, choice
from Crypto.PublicKey import DSA
from hashlib import sha1
from gmpy2 import xmpz, to_binary, invert, powmod, is_prime
def gen_rand_str(size=40, chars=ascii_uppercase + ascii_lowercase + digits):
return ''.join(choice(chars) for _ in range(size))
def gen_g(p, q):
while True:
h = randrange(2, p - 1)
exp = xmpz((p - 1) // q)
g = powmod(h, exp, p)
if g > 1:
break
return g
def keys(g, p, q):
d = randrange(2, q)
e = powmod(g, d, p)
return e, d
def sign(msg, k, p, q, g, d):
while True:
r = powmod(g, k, p) % q
h = int(sha1(msg).hexdigest(), 16)
try:
s = (invert(k, q) * (h + d * r)) % q
return r, s
except ZeroDivisionError:
pass
if __name__ == "__main__":
print("\n")
print(".___________..___ ___. __ __ ______ .___________. _______ ___ ___ ___ __ ")
print("| || \/ | | | | | / || || ____| |__ \ / _ \ |__ \ /_ | ")
print('`---| |----`| \ / | | | | | | ,----"`---| |----`| |__ ) | | | | | ) | | | ')
print(" | | | |\/| | | | | | | | | | | __| / / | | | | / / | | ")
print(" | | | | | | | `--' | | `----. | | | | / /_ | |_| | / /_ | | ")
print(" |__| |__| |__| \______/ \______| |__| |__| |____| \___/ |____| |_| ")
steps = 10
for i in range(steps):
key = DSA.generate(2048)
p, q = key.p, key.q
print("\n\nq =", q)
g = gen_g(p, q)
e, d = keys(g, p, q)
k = randrange(2, q)
msg1 = gen_rand_str()
msg2 = gen_rand_str()
msg1 = str.encode(msg1, "ascii")
msg2 = str.encode(msg2, "ascii")
r1, s1 = sign(msg1, k, p, q, g, d)
r2, s2 = sign(msg2, k, p, q, g, d)
print("\nsign('" + msg1.decode() + "') =", s1)
print("\nsign('" + msg2.decode() + "') =", s2)
if i == (steps - 1):
with open('flag', 'rb') as f:
flag = f.read()
secret = flag
else:
secret = gen_rand_str()
secret = str.encode(secret, "ascii")
r3, s3 = sign(secret, k, p, q, g, d)
print("\nsign(secret) =", s3, r3)
h = input("\nGive me SHA1(secret) : ")
if h == str(int(sha1(secret).hexdigest(), 16)):
print("\nThat's right, the secret is", secret.decode())
else:
print("\nSorry, I cannot give you the secret. Bye!")
break
```
:::
簡單來說，題目每次會給兩個訊息跟它們的 DSA 簽章，接著在給個簽章，問你說知不知道它簽了什麼訊息。那本身 DSA 沒有問題，有問題的是它重複使用了 nonce，也就是說我們有兩條式子：$$ \begin{align} s_1 & = k^{-1}(h_1+dr) \pmod{q} \\ s_2 & = k^{-1}(h_2+dr) \pmod{q} \end{align} $$ 於是我們有 $$ k = \frac{h_1-h_2}{s_1-s_2} \pmod{q} $$ 解得 $k$ 後，對於新的簽章 $s_3$，我們便可以很輕易地算出 $h_3$，$$ h_3 = k(s_3-s_1)+h_1 \pmod{q} $$
:::spoiler **Script**
```python=
from pwn import *
from hashlib import sha1
bb = b"\') = "
print(bb)
def connect():
r = remote('185.235.41.166', 5000)
return r
def sign(r):
r.recvuntil("q = ")
q = int(r.recvline().strip())
r.recvuntil("sign")
_ = r.recvline()[2:].strip().split(bb)
h1 = int(sha1(_[0]).hexdigest(), 16)
s1 = int(_[1])
r.recvuntil("sign")
_ = r.recvline()[2:].strip().split(bb)
h2 = int(sha1(_[0]).hexdigest(), 16)
s2 = int(_[1])
r.recvuntil("sign(secret) = ")
_ = r.recvline().strip().split(b" ")
s3 = int(_[0])
r3 = int(_[1])
### s1 - s2 = k^-1 (h1 - h2)
### s3 - s1 = k^-1 (h3 - h1)
inv_k = pow(h1 - h2, -1, q) * (s1 - s2) % q
h3 = (pow(inv_k, -1, q) * (s3 - s1) + h1) % q
c.sendline(str(h3))
c = connect()
step = 10
for i in range(step):
sign(c)
c.interactive()
```
:::
:::success
TMUCTF{7h15_w45_my_m1574k3__1_f0r607_7h47_1_5h0uld_n3v3r_516n_mul71pl3_m3554635_w17h_4_dupl1c473_k3y!!!}
:::
Sign in with Wallet
Connect another wallet