<h1 style="text-align:center;">KMACTF 2025</h1>
## Chatgpt (500pts)
:::spoiler **chall․py**
```python=
from Crypto.Cipher import AES
from Crypto.Util import Counter
import secrets, sys
import random
from hashlib import sha256
BLOCK = 16
R_POLY = 0xE1000000000000000000000000000000
KEY_SIZE_BITS = 256
MAX_INT = 1 << KEY_SIZE_BITS
MOD = MAX_INT - 189
SEED = MAX_INT // 6
def xor_bytes(a: bytes, b: bytes) -> bytes:
assert len(a) == len(b)
return bytes(x ^ y for x, y in zip(a, b))
def pad16(b: bytes) -> bytes:
if len(b) % BLOCK == 0:
return b
return b + b"\x00" * (BLOCK - (len(b) % BLOCK))
def int_from_bytes(b: bytes) -> int:
return int.from_bytes(b, "big")
def int_to_bytes(x: int) -> bytes:
return x.to_bytes(16, "big")
def gf_mul(X: int, Y: int) -> int:
Z = 0
V = X
for i in range(128):
if (Y >> (127 - i)) & 1:
Z ^= V
lsb = V & 1
V >>= 1
if lsb:
V ^= R_POLY
return Z & ((1 << 128) - 1)
def ghash(H: bytes, data: bytes) -> bytes:
assert len(H) == 16
H_int = int_from_bytes(H)
data = pad16(data)
y = 0
for i in range(0, len(data), BLOCK):
Xi = int_from_bytes(data[i:i+BLOCK])
y = gf_mul(y ^ Xi, H_int)
return int_to_bytes(y)
class GHASH:
def __init__(self, aes_key_for_H: bytes):
cipher = AES.new(aes_key_for_H, AES.MODE_ECB)
self.H = cipher.encrypt(b"\x00"*16)
def h(self, X: bytes, T: bytes) -> bytes:
return ghash(self.H, pad16(X) + pad16(T))
class AESBlock:
def __init__(self, key: bytes):
self.key = key
def enc(self, block: bytes) -> bytes:
cipher = AES.new(self.key, AES.MODE_ECB)
return cipher.encrypt(block)
def dec(self, block: bytes) -> bytes:
cipher = AES.new(self.key, AES.MODE_ECB)
return cipher.decrypt(block)
class StreamAESCTR:
def __init__(self, key: bytes):
self.key = key
def keystream(self, S: bytes, length: int) -> bytes:
init_val = int.from_bytes(S, "big")
ctr = Counter.new(128, initial_value=init_val)
cipher = AES.new(self.key, AES.MODE_CTR, counter=ctr)
return cipher.encrypt(b"\x00" * length)
class Encryptor:
def __init__(self, key_e: bytes, key_d: bytes, key_c: bytes, key_for_H: bytes):
self.e = AESBlock(key_e)
self.d = AESBlock(key_d)
self.h1 = GHASH(key_for_H)
self.h2 = GHASH(key_for_H)
self.c = StreamAESCTR(key_c)
def encrypt(self, T: bytes, plaintext: bytes) -> bytes:
assert len(T) == BLOCK and len(plaintext) >= BLOCK
A = plaintext[:BLOCK]; B = plaintext[BLOCK:]
U = self.e.enc(A)
S = xor_bytes(U, self.h1.h(B, T))
keystream = self.c.keystream(S, len(B))
E = xor_bytes(B, keystream) if len(B) > 0 else b""
V = xor_bytes(S, self.h2.h(E, T))
G = self.d.enc(V)
return G + E
def decrypt(self, T: bytes, ciphertext: bytes) -> bytes:
assert len(T) == BLOCK and len(ciphertext) >= BLOCK
G = ciphertext[:BLOCK]; E = ciphertext[BLOCK:]
V = self.d.dec(G)
S = xor_bytes(V, self.h2.h(E, T))
keystream = self.c.keystream(S, len(E))
B = xor_bytes(E, keystream) if len(E) > 0 else b""
U = xor_bytes(S, self.h1.h(B, T))
A = self.e.dec(U)
return A + B
class Newbie_Stager:
def __init__(self, alice_private_key: int, bob_key_private: int):
self.alice_private_key = alice_private_key
self.bob_key_private = bob_key_private
def key_exchange(self, seed, exponents):
result = seed
exp = 1
while exponents > 0:
if exponents % 2 == 1:
mult = 1
for i in range(exp):
result = (3 * result * mult) % MOD
mult <<= 1
exponents >>= 1
exp += 1
return result
def get_shared_key(self):
A = self.key_exchange(SEED, self.alice_private_key)
B = self.key_exchange(SEED, self.bob_key_private)
shared_key_A = self.key_exchange(B, self.alice_private_key)
share_key_B = self.key_exchange(A, self.bob_key_private)
assert shared_key_A == share_key_B
return shared_key_A , A, B
# Setup
m_blocks = 12
key_e = secrets.token_bytes(16)
key_d = secrets.token_bytes(16)
key_c = secrets.token_bytes(16)
key_for_H = secrets.token_bytes(16)
encryptor = Encryptor(key_e, key_d, key_c, key_for_H)
# Encrypt
total_len = m_blocks * BLOCK
plaintext = secrets.token_bytes(total_len)
T = secrets.token_bytes(BLOCK)
ciphertext = encryptor.encrypt(T, plaintext)
# Encrypt but for newbie
alice_private = random.getrandbits(256)
bob_private = random.getrandbits(256)
shared_key, A, B = Newbie_Stager(alice_private, bob_private).get_shared_key()
shared_key = sha256(str(shared_key).encode()).digest()[:16]
newbie_aes = AESBlock(shared_key)
cipher_enc = newbie_aes.enc(ciphertext)
print("Newbie cant see my ciphertext !!!")
print("Here is your ciphertext:", cipher_enc.hex())
print("Here is your T (hex):", newbie_aes.enc(T).hex())
print("Here is your A:", A)
print("Here is your B:", B)
coint = 10
menu = """
1) Decrypt
2) Encrypt
3) Get Flag
"""
while coint > 0:
print(menu)
print(f"You have {coint} coins left")
choice = input("Your choice: ").strip()
if choice == "1":
try:
hex_ct = input("Ciphertext (hex): ").strip()
T = bytes.fromhex(input("T (hex): ").strip())
if len(T) != BLOCK:
print("Invalid T length")
continue
ciphertext_ = bytes.fromhex(hex_ct)
if len(ciphertext_) < BLOCK:
print("Ciphertext too short")
continue
control = 0
for i in range(0, len(ciphertext_), BLOCK):
block = ciphertext_[i:i+BLOCK]
if block in ciphertext :
control +=1
if control > 2 :
print("You are not allowed to repeat blocks more than 2 times")
exit()
pt = encryptor.decrypt(T, ciphertext_)
print("Plaintext (hex):", pt.hex())
coint -= 3
except Exception as e:
print("Error:", e)
continue
if choice == "2":
try:
hex_pt = input("Plaintext (hex): ").strip()
T = bytes.fromhex(input("T (hex): ").strip())
if len(T) != BLOCK:
print("Invalid T length")
continue
plaintext_ = bytes.fromhex(hex_pt)
if len(plaintext_) < BLOCK:
print("Plaintext too short")
continue
control = 0
for i in range(0, len(plaintext_), BLOCK):
block = plaintext_[i:i+BLOCK]
if block in ciphertext :
control +=1
if control > 2 :
print("You are not allowed to repeat blocks more than 2 times")
exit()
ct = encryptor.encrypt(T, plaintext_)
print("Ciphertext (hex):", ct.hex())
coint -= 4
except Exception as e:
print("Error:", e)
continue
if choice == "3":
plaintext_ = bytes.fromhex(input("Plaintext (hex): ").strip())
if plaintext_ == plaintext[BLOCK:]:
print("Here is your flag: KMACTF{????????????????????????????????}")
exit()
else:
print("Nope")
coint -= 5
```
:::
++**Mô tả:**++ Challenge này sử dụng hai lớp mã hóa là `Encryptor` và `Newbie_Stager` để mã hóa `Plaintext`, và nó yêu cầu ta phải giải mã được `Plaintext[16:]` (bỏ đi block đầu) để nhận `Flag`.
Bên cạnh đó Challenge còn cung cấp cho ta `10 coin` và cho phép dùng `3` option là `Decrypt` (3 coin), `Encrypt` (4 coin), `Get Flag` (5 coin) để tương tác với server.
>Theo code thì ta có thể dùng được tối đa: 3 lần `Decrypt` 1 lần `Get Flag`, hoặc 1 lần `Decrypt` 1 lần `Encrypt` 1 lần `Get Flag`, hoặc 2 lần `Encrypt` 1 lần `Get Flag`.
---
Tiến hành phân tích class `Encryptor` và class `Newbie_Stager`.
1️⃣ Class `Encryptor` :
```python=
class Encryptor:
def __init__(self, key_e: bytes, key_d: bytes, key_c: bytes, key_for_H: bytes):
self.e = AESBlock(key_e)
self.d = AESBlock(key_d)
self.h1 = GHASH(key_for_H)
self.h2 = GHASH(key_for_H)
self.c = StreamAESCTR(key_c)
def encrypt(self, T: bytes, plaintext: bytes) -> bytes:
assert len(T) == BLOCK and len(plaintext) >= BLOCK
A = plaintext[:BLOCK]; B = plaintext[BLOCK:]
U = self.e.enc(A)
S = xor_bytes(U, self.h1.h(B, T))
keystream = self.c.keystream(S, len(B))
E = xor_bytes(B, keystream) if len(B) > 0 else b""
V = xor_bytes(S, self.h2.h(E, T))
G = self.d.enc(V)
return G + E
def decrypt(self, T: bytes, ciphertext: bytes) -> bytes:
assert len(T) == BLOCK and len(ciphertext) >= BLOCK
G = ciphertext[:BLOCK]; E = ciphertext[BLOCK:]
V = self.d.dec(G)
S = xor_bytes(V, self.h2.h(E, T))
keystream = self.c.keystream(S, len(E))
B = xor_bytes(E, keystream) if len(E) > 0 else b""
U = xor_bytes(S, self.h1.h(B, T))
A = self.e.dec(U)
return A + B
```
🔎 Class này kết hợp `3` cơ chế bảo mật là:
1. `AES ECB` (trong class `AESBlock`) để mã hóa và giải mã block đầu của `Plaintext`.
1. `GHASH` (trong class `GHASH`) để tạo hai đối tượng `h1, h2` sử dụng trong quá trình mã hóa và tạo `Keystream`. Nó sử dụng phép nhân trong trường `GF(2^128)` với đa thức bất khả quy là `x^128 + x^7 + x^2 + x + 1`.
1. `AES CTR` (trong class `StreamAESCTR`) để tạo Keystream cho phần đuôi của `Plaintext`.
🔎 Quy trình `encrypt` hoạt động như sau:
1. Chia `Plaintext` thành `A` (block đầu) dài `16 bytes` và `B` (phần còn lại).
2. Tính `U = ECB_e(A)`, sau đó tính `S = U ⊕ h1(B, T)`.
3. Dùng `S` làm `nonce` cho `CTR` để tạo keystream, sau đó xor với `B` → ta được phần `E` của Ciphertext.
4. Tiếp tục tính `V = S ⊕ h2(E, T)` rồi mã hóa bằng `ECB_d` để tạo block đầu `G`.
5. Kết quả `ciphertext = G || E`.
🔎 Khi giải mã (`decrypt`), ta đảo ngược quá trên trên.
>[!Important] Hint
Được hint rằng cơ chế mã hóa trên là một trong các [**Mode of operation**](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation) thì sau một hồi tìm kiếm và được hint thêm thì mình tìm được nó là mode `XCBv2fb` (một mode bị chứng minh là không an toàn và có thể bị bẻ gãy chỉ trong vài tương tác).
---
2️⃣ Class `Newbie_Stager` :
```python=
class Newbie_Stager:
def __init__(self, alice_private_key: int, bob_key_private: int):
self.alice_private_key = alice_private_key
self.bob_key_private = bob_key_private
def key_exchange(self, seed, exponents):
result = seed
exp = 1
while exponents > 0:
if exponents % 2 == 1:
mult = 1
for i in range(exp):
result = (3 * result * mult) % MOD
mult <<= 1
exponents >>= 1
exp += 1
return result
def get_shared_key(self):
A = self.key_exchange(SEED, self.alice_private_key)
B = self.key_exchange(SEED, self.bob_key_private)
shared_key_A = self.key_exchange(B, self.alice_private_key)
share_key_B = self.key_exchange(A, self.bob_key_private)
assert shared_key_A == share_key_B
return shared_key_A , A, B
```
Mục đích của Class này là để tạo `shared_key` cho `newbie_aes` mã hóa `Token` và `Ciphertext`, vì vậy ta cần tìm lại `shared_key` thì mới giải mã cái `newbie_aes` được.
🔎 Ta có công thức của hàm `key_exchange` là:
$$\text{result} \equiv \text{SEED} \cdot \prod(3.2^k) \pmod {MOD}$$
> với `k` phụ thuộc vào giá trị của `exponents`.
🔎 Ta có thể viết lại công thức của `A,B` như sau:
$$A \equiv \text{SEED} \cdot a \pmod {MOD}$$
$$B \equiv \text{SEED} \cdot b \pmod {MOD}$$
>Trong đó `a, b` là giá trị của `∏(3.2^k)`.
🔎 Vì đã có `A,B` nên ta tính được `a,b`:
$$a \equiv \frac{A}{\text{SEED}} \pmod {MOD}$$
$$b \equiv \frac{B}{\text{SEED}} \pmod {MOD}$$
🔎 Có `a,b` ta thay vào công thức của `shared_key` là tính được `shared_key`:
$$\text{shared key} \equiv A.b \equiv \text{SEED}.a.b \pmod {MOD}$$
> Có `shared_key` thì có được `Token` và `Ciphertext` gốc.
---
❔Có `Ciphertext` và `Token`, giờ ta sử dụng `10 coin` và hai option `Decrypt` và `Encrypt` như thế nào để khôi phục `Plaintext[16:]`?
Ta không được phép gửi toàn bộ `Ciphertext` vào option `Decrypt` vì server có check như sau:
```python=
control = 0
for i in range(0, len(ciphertext_), BLOCK):
block = ciphertext_[i:i+BLOCK]
if block in ciphertext :
control +=1
if control > 2 :
print("You are not allowed to repeat blocks more than 2 times")
exit()
```
Biết rằng mode `XCBv2fb` là không an toàn, ta có thể dễ dàng tìm được các bài báo cáo nói về tính bảo mật của nó và mình tìm được bài báo cáo [**này**](https://eprint.iacr.org/2024/1527.pdf) hướng dẫn cách khôi phục `Plaintext[16:]` chỉ với 1 lần `Decrypt` và 1 lần `Encrypt` mà thôi.
>[!Important]
Ở `trang 7`, tác giả có hướng dẫn như sau:
✅ Vậy ta thực hiện như sau:
1. Đặt `plaintext` cần tìm là `A||B`, `ciphertext` là `G||A` và Token là `T`. Khởi tạo một chuỗi bytes `△` ngẫu nhiên dài bằng `len(B)`.
2. Ta sử dụng option 1 `Decrypt` với `ciphertext = G||(E ⊕ △)` và nhận được `A1||B1`.
3. Còn `7 coin`, ta sử dụng option 2 `Encrypt` với `plaintext = A1||(B1 ⊕ △)` và được `G2||E2`.
4. Cuối cùng tính lại `B` bằng công thức `B = E ⊕ B1 ⊕ E2 ⊕ △`.
5. Gửi `B` đến server bằng option 3 và nhận `Flag.`
:::spoiler **Full Script**
```python=
from pwn import *
from Crypto.Cipher import AES
import secrets, sys
from hashlib import sha256
BLOCK = 16
R_POLY = 0xE1000000000000000000000000000000
KEY_SIZE_BITS = 256
MAX_INT = 1 << KEY_SIZE_BITS
MOD = MAX_INT - 189
SEED = MAX_INT // 6
class AESBlock:
def __init__(self, key: bytes):
self.key = key
def enc(self, block: bytes) -> bytes:
cipher = AES.new(self.key, AES.MODE_ECB)
return cipher.encrypt(block)
def dec(self, block: bytes) -> bytes:
cipher = AES.new(self.key, AES.MODE_ECB)
return cipher.decrypt(block)
io = remote("165.22.55.200", 30002)
def find_newbie_key(A, B):
shared = (A * B) * pow(SEED, -1, MOD) % MOD
key16 = sha256(str(shared).encode()).digest()[:16]
return key16
# ciphertext và T bị mã hóa bằng newbie_aes
io.recvuntil(b"ciphertext:"); ct = bytes.fromhex(io.recvlineS())
io.recvuntil(b"T (hex): "); T = bytes.fromhex(io.recvlineS())
io.recvuntil(b"A: "); A = int(io.recvlineS())
io.recvuntil(b"B: "); B = int(io.recvlineS())
shared_key = find_newbie_key(A, B)
newbie_aes = AESBlock(shared_key)
# Có T và ciphertext gốc, tiến hành khôi phục plaintext
T = newbie_aes.dec(T)
C = newbie_aes.dec(ct)
delta = secrets.token_bytes(16*11)
G = C[:16]
E = C[16:]
# round 1
C = G + xor(E, delta)
io.sendlineafter(b"Your choice: ", b"1")
io.sendlineafter(b"Ciphertext (hex): ", C.hex().encode())
io.sendlineafter(b"T (hex): ", T.hex().encode())
io.recvuntil(b"Plaintext (hex): "); P1 = bytes.fromhex(io.recvlineS())
A1 = P1[:16]
B1 = P1[16:]
# round 2
P1 = A1 + xor(B1, delta)
io.sendlineafter(b"Your choice: ", b"2")
io.sendlineafter(b"Plaintext (hex): ", P1.hex().encode())
io.sendlineafter(b"T (hex): ", T.hex().encode())
io.recvuntil(b"Ciphertext (hex): "); C2 = bytes.fromhex(io.recvlineS())
G2 = C2[:16]
E2 = C2[16:]
B = (xor(E, B1, E2, delta)).hex()
io.sendlineafter(b"Your choice: ", b"3")
io.sendlineafter(b"Plaintext (hex): ", B.encode())
io.interactive()
"""
[+] Opening connection to 165.22.55.200 on port 30002: Done
[*] Switching to interactive mode
Here is your flag: KMACTF{h0w_m4ny_qu3ri3s_d0_y0u_n33d_2_bre4k_m3?_i_know_2_4r3_3n0ugh}
[*] Got EOF while reading in interactive
"""
```
:::spoiler **Flag**
**KMACTF{h0w_m4ny_qu3ri3s_d0_y0u_n33d_2_bre4k_m3?_i_know_2_4r3_3n0ugh}**
:::
## RAS (500pts)
:::spoiler **chall․py**
```python=
from Crypto.Util.number import *
from math import prod
import random
class RAS(object):
def __init__(self, arr):
self.n = prod(arr)*prod(arr)
def generate_e(self):
e = random.getrandbits(4048)
return e
def encrypt(self, pt):
e = self.generate_e()
assert self.n.bit_length() == 4048
c = [pow(m, e, self.n) for m in pt]
return c
flag = b'KMACTF{???????????????????????????????}'
flag1, flag2, flag3 = bytes_to_long(flag[:len(flag)//3]), bytes_to_long(flag[len(flag)//3:2*len(flag)//3]), bytes_to_long(flag[2*len(flag)//3:])
# shuffle it
m1 = flag3
m2 = 65537*flag1**2 + flag3*flag2**2
menu = '''
Welcome to my RAS stolen from tvd2004
1. Send primes
2. Get encrypted flag
'''
while True :
print(menu)
choose = input('> ')
if choose == '1':
try:
count = int(input(f"Not 1, not 2, you can choose number prime in RSA system : "))
except :
exit()
arr = []
for i in range(count) :
p = int(input(f"Prime {i} : "))
arr.append(p)
ras = RAS(arr)
elif choose == '2':
print("Here is ciphertext :")
print(ras.encrypt([m1,m2]))
else:
raise Exception("Invalid choice!!!")
```
:::
++**Mô tả:**++ Một Challenge lấy ý tưởng từ Challenge `RAS` của giải `WannaGame Championship 2024` khi nó cho phép ta chọn modulus `n` để mã hóa `RSA`, sau đó nó trả về kết quả của:
$$
\left\{\begin{matrix}
c_1 = m_1^e \pmod {n^2} \\
c_2 = m_2^e \pmod {n^2}
\end{matrix}\right.
$$
Trong đó:
$$
\left\{\begin{align}
m_1 &= \text{Flag}_3 \\
m_2 &= 65537 \times \text{Flag}_1^2 + \text{Flag}_3\times \text{Flag}_2^2
\end{align}\right.
$$
> Với `Flag1 Flag2 Flag3` là ba phần của `Flag` và `e` là một số ngẫu nhiên `4048` bit.
Nhưng Challenge này khó hơn hơn Challenge gốc của anh `tvdat` nhiều vì nó chỉ trả về giá trị của `(c1, c2)` chứ không trả về mũ `e`. Liệu ta có thể gửi vào một giá trị `n` mà khi không biết `e` nhưng vẫn khôi phục được khóa bí mật `d`?
---
>[!Important] Hint
Được `hint` là sử dụng [**Carmichael function**](https://en.wikipedia.org/wiki/Carmichael_function) và tìm cách để cho nó nhỏ nhất nên ta sẽ tiến hành tìm hiểu định nghĩa của nó như sau.
++**Định nghĩa**++: Hàm Carmichael `λ(n)` của một số nguyên dương `n` là giá trị `m` nhỏ nhất sao cho:
$$a^m \equiv 1 \pmod n$$
Với `a` là mọi số nguyên tố với `n` (tức `GCD(a,n)=1`).
Đôi lúc hàm Carmichael `λ(n)` được sử dụng để thay thế hàm Euler `φ(n)` vì nó có thể mang giá trị nhỏ hơn hàm Euler, giúp giảm chi phí tính toán, cụ thể là ở phép tính khóa bí mật `d`, ta có công thức:
$$d \equiv e^{-1} \pmod {\varphi(n)}$$
Có thể được thay thế thành:
$$d \equiv e^{-1} \pmod {\lambda(n)}$$
Bời vì tính chất: $\lambda(n) | \varphi(n)$.
Điều này giúp khóa bí mật `d` nhỏ hơn (vì nó được tính dưới modulo `λ(n)`).
> `λ(n)` có tính chất giống với `φ(n)` nhưng điểm đặc biệt là nó có thể mang giá trị nhỏ hơn rất nhiều so với `φ(n)`:
Công thức của hàm `λ(n)` có thể được biểu diễn dưới công thức của hàm `φ(n)` như sau:
$$
\lambda(n) =
\begin{cases}
\varphi(n), & \text{if } n \text{ is } 1, 2, 4, \text{ or an odd prime power}, \\[6pt]
\dfrac{1}{2}\varphi(n), & \text{if } n = 2^r,\; r \geq 3, \\[6pt]
\operatorname{lcm}\!\bigl(\lambda(n_1), \lambda(n_2), \ldots, \lambda(n_k)\bigr),
& \text{if } n = n_1 n_2 \cdots n_k.
\end{cases}
$$
Trong đó công thức của $\varphi(p^r)$ với $p$ là số nguyên tố và $r \geq 1$ là:
$$\varphi(p^r) = p^{r-1}(p-1)$$
> Ta có công thức tính nhanh của `λ(2^r)` với `r≥3` là: `λ(2^r) = 2^(r-2)`.
---
>[!Important] question
Nắm được tính chất của hàm `Carmichael` rồi, giờ ta sẽ ứng dụng nó vào Challenge của ta như thế nào?
Để hiểu được độ nhỏ của `λ(n)` so với `φ(n)`, ta lấy một ví dụ sau. Giả sử ta có một modulus `n` có kích thước `769 bit` là:
```!
1803242098136617403627683032744086816519252253990109601462437157066086605676458401806269865232873095138146210634332410317591885037589708869541207369916371793985701096750146464842229232786571609836773779621227343176417379009783159710
```
Ta factor giá trị `n` trên và được các ước nhỏ như sau:
```!
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 113, 127, 131, 157, 181, 199, 211, 241, 281, 313, 331, 337, 397, 421, 463, 521, 547, 617, 631, 661, 859, 881, 911, 937, 991, 1009, 1093, 1171, 1321, 1873, 2003, 2311, 2341, 2521, 2731, 2861, 3121, 3433, 3697, 4621, 6007, 6553, 8009, 8191, 8581, 9241, 16381, 18481, 20021, 20593, 21841, 25741, 36037, 48049, 51481, 55441, 65521, 72073, 120121, 180181]
```
Nếu như ta tính `φ(n)`, thì ta sẽ được một giá trị `766 bit` là:
```!
210156846527805359340602028013011250122036425319594741530754303546212895650172863606787491430002451850407734077095483694468155323926575925884187925175777901763375521410065105999673536985169920000000000000000000000000000000000000000
```
Nhưng nếu ta tính `λ(n)` thì ta sẽ được một giá trị rất nhỏ chỉ `20 bit` là:
```
720720
```
Mà ta có tính chất: `λ(n)` là ước của `φ(n)`:
$$\lambda(n)|\varphi(n)$$
Nên công thức của khóa bí mật `d` sẽ từ:
$$d \equiv e^{-1} \pmod {\varphi(n)}$$
Trở thành:
$$d \equiv e^{-1} \pmod {\lambda(n)}$$
>[!Important]
Với một `λ(n)` nhỏ thì dù `e` có lớn đến đâu, `d` cũng không thể lớn hơn `λ(n)` được vì công thức của `d` là `d = e^-1 mod λ(n)` sẽ cho ra một giá trị bé hơn `λ(n)`, từ đó ta có thể dễ dàng brute force khóa bí mật `d` trong đoạn `[1, λ(n)-1]`.
++**Minh họa**++:
```python=
from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime
from math import prod, lcm, gcd
n = 1803242098136617403627683032744086816519252253990109601462437157066086605676458401806269865232873095138146210634332410317591885037589708869541207369916371793985701096750146464842229232786571609836773779621227343176417379009783159710
factors = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 113, 127, 131, 157, 181, 199, 211, 241, 281, 313, 331, 337, 397, 421, 463, 521, 547, 617, 631, 661, 859, 881, 911, 937, 991, 1009, 1093, 1171, 1321, 1873, 2003, 2311, 2341, 2521, 2731, 2861, 3121, 3433, 3697, 4621, 6007, 6553, 8009, 8191, 8581, 9241, 16381, 18481, 20021, 20593, 21841, 25741, 36037, 48049, 51481, 55441, 65521, 72073, 120121, 180181]
assert all([isPrime(i) for i in factors])
phi = prod([p-1 for p in factors])
lam = 720720
e = 0x10001
m = bytes_to_long(b"AT20N0118")
c = pow(m, e, n)
d1 = pow(e, -1, phi) # một giá trị 765 bit
d2 = pow(e, -1, lam) # 554993
print(long_to_bytes(pow(c, d1, n)))
print(long_to_bytes(pow(c, d2, n)))
# b'AT20N0118'
# b'AT20N0118'
```
---
>[!Important]
Vậy hướng đi của ta là: Tìm `n` đủ lớn → `n` cho ra `λ(n)` đủ nhỏ → Gửi `n` đến server nhận `c1,c2` → brute force khóa bí mật `d` trong đoạn `[1, λ(n)-1]` → Giải mã được `m1,m2` → Có `m1,m2` thì giải được Flag 😎
✅ Vậy đầu tiên ta cần tìm `n` sao cho ra `λ(n)` là một giá trị nhỏ.
Giả sử ta cần tìm `n` dạng `n = n1 x n2 x ... x nk` với `n1, n2, nk` là các số `nguyên tố nhỏ`. Thì khi này công thức của `λ(n)` là: $$\operatorname{lcm}\!\bigl(n_1-1, n_2-1, \ldots, n_k-1\bigr)$$
Nên ta sẽ chọn trước một số `λ(n)` sao cho nó chứa các ước nhỏ là `n1-1, n2-1 ,..., nk-1`, sau đó nhân các giá trị `n1, n2,...,nk` lại là có được `n`. Thực hiện như sau:
```python=
from Crypto.Util.number import *
from sage.all import *
def carmichael_lambda(n):
factors = factor(n)
lambdas = []
for p, e in factors:
if p == 2 and e >= 3:
lambdas.append(2**(e-2))
else:
lambdas.append((p-1) * p**(e-1))
return lcm(lambdas)
sample = 720720
divisor = []
for i in range(1 , sample + 1) :
if sample % i == 0 and isPrime(i+1) :
divisor.append(i+1)
print(f"{divisor = }")
N = 1
for i in divisor :
N*=i
print("bit length of N =", N.bit_length())
assert carmichael_lambda(N) == sample
# divisor = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 113, 127, 131, 157, 181, 199, 211, 241, 281, 313, 331, 337, 397, 421, 463, 521, 547, 617, 631, 661, 859, 881, 911, 937, 991, 1009, 1093, 1171, 1321, 1873, 2003, 2311, 2341, 2521, 2731, 2861, 3121, 3433, 3697, 4621, 6007, 6553, 8009, 8191, 8581, 9241, 16381, 18481, 20021, 20593, 21841, 25741, 36037, 48049, 51481, 55441, 65521, 72073, 120121, 180181]
# bit length of N = 769
```
> Vậy là ta có thể tạo được một modulus `n` từ một `λ(n)` cho trước rồi.
✅ Vậy bây giờ độ lớn của `n` và `λ(n)` là bao nhiêu thì hợp lý?
Quan trọng nhất thì `λ(n)` không được quá lớn vì nếu quá lớn (hơn `10 triệu`) thì bước brute force `d` diễn ra rất lâu vì phép lũy thừa chạy rất chậm.
Tiếp theo, dựa vào format của `Flag` là `KMACTF{???????????????????????????????}` ta ước chừng được độ lớn của `m1,m2` sẽ là `103` và `309` bit nên ta tìm một giá trị `n` khoảng `500` bit là hợp lý. Sau đó ta sẽ nhân thêm `n` với một số `n1` nữa để kích thước đạt `2024` bit.
>[!Important] question
Tại sao không cần tìm `λ(n)` cho ra `n` 2048 bit, lý do là vì `n` lớn thì `λ(n)` cũng có thể sẽ lớn theo, ảnh hưởng quá trình tìm `d`. Không phải lúc nào `d` cũng tồn tại vì `e` chưa chắc đã nguyên tố với `λ(n)` nên ta cần connect tới server nhiều lần đến khi `e` nguyên tố với `λ(n)` thì mới có `d` được, vì vậy `λ(n)` quá lớn sẽ không tốt.
Bên cạnh đó `n` quá to cũng không cần thiết vì khi ta gửi `N = n.n1` đến server (n1 là phần pad vào cho đủ 2024 bit), server sẽ thực hiện phép tính sau:
$$c_1 = m_1^e \pmod {n.n.n_1.n_1}$$
Vì `n|N` nên ta chỉ cần mod hai vế cho `n` là phép tính trở thành:
$$c_1 = m_1^e \pmod {n}$$
Sau nhiều bước test và thử nghiệm thì giá trị `λ(n)` mình thấy hợp lý là:
$$\lambda(n) = 2^6 . 3^2 . 5 . 7 . 13 = 262080$$
Nó không quá lớn và cũng cho ra `n` 555 bit, khá vừa vặn với `m1,m2`:
```!
N =
85217303986526089768208675693780350913114318459795065165687931019468545740678895390536616742913898903010234170773026814502401638427394841422684958144254198784116180310
factors =
[2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
```
---
Có `n`, ta gửi đến server để nó tính `c1,c2`, sau đó brute force `d` trong khoảng `[1,λ(n)-1]` đến khi nào giải mã được `m1,m2` thì dừng:
```python=
from Crypto.Util.number import *
from math import prod
from pwn import *
from tqdm import *
from sage.all import *
carmichael = 2**6 * 3**2 * 5 * 7 * 13
Q = [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
n = prod(Q)
# n1 là padding cho đủ 2024 bit
n1 = 16137065238548023209354216756994085116039071329741992404760044520469775763598604679740651617211548370722607323479545645549867358928555262389728162798543590988183336155777102822466433736318341045782578414126244103517499384317415648780840623744041560018889448526450175979862047825655610652640229808466274926539017341691446592144579795902560014607660916789992333812186930296354747949841511313853809884979361487225668820393379628401205576558482036
N = n*n1
assert (N**2).bit_length() == 4048
exit = False
while True:
if exit:
break
print("Finding e such that gcd(e, lambda) == 1")
io = remote("165.22.55.200", 30001)
# io = process(["python3", "test.py"])
io.sendlineafter(b"> ", b"1"); io.sendlineafter(b" : ", b"1"); io.sendlineafter(b" : ", str(N).encode())
io.sendlineafter(b"> ", b"2"); io.recvuntil(b"ciphertext :\n")
c1, c2 = eval(io.recvline())
io.close()
c1 = c1 % n
c2 = c2 % n
# không biết e nên ta sẽ brute force d
print("finding d in range(1, lambda-1)")
for d in trange(1, carmichael):
m1 = pow(c1, d, n)
if m1.bit_length() < 300 and m1.bit_length() != 1 and long_to_bytes(m1).endswith(b"}"):
print("✅")
print(f"{d = }")
exit = True
break
io.close()
# có m1 là có flag3
m1 = int(m1)
m2 = pow(c2, d, n)
print(f"{m1 = }")
print(f"{m2 = }")
```
Vậy là tìm được `m1,m2` rồi 😎
```!
m1 = 35689003380947478572094688521116102469800350398642557
m2 = 15374382952448648386234156647364992061140979466732533176937863507778552068695153712875826599052803361828508498209602868391557371030313888768898114752847802838
```
> Mình thử giải mã `m1` thì được `_ch4113n93_15_50_345y}`, nó không dài `13` bytes như trong format của `Flag` mà dài `22` bytes 💀
---
Giờ ta cần giải phương trình:
$$m_2 = 65537 \times \text{Flag}_1^2 + m_1\times \text{Flag}_2^2$$
Để tìm lại nốt `Flag1` và `Flag2`.
Đây là phương trình bậc nhất hai ẩn nên nó sẽ có vô số nghiệm, mình thử `LLL` để giải phương trình `65537.a + m1.b = m2` nhưng mà không được vì `a,b` khá to.
Để giải nó thì ta cần triệt tiêu một ẩn đi, mẹo chính là mod phương trình trên cho `m1`, nó sẽ triệt tiêu đi phần `Flag2^2`, chỉ còn lại `Flag1^2` mà thôi, ta được một phương trình modulo bậc 2 là:
$$m_2 = 65537 \times \text{Flag}_1^2 \pmod {m_1}$$
Phương trình chỉ có một ẩn `Flag1` nên ta sẽ sử dụng phương thức `.roots(multiplicities = False)` của sagemath để giải, tìm được `Flag1` là `KMACTF{n07h1n_1d34_70_`:
```python=
from Crypto.Util.number import *
from sage.all import *
Q = [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
n = prod(Q)
m1 = 35689003380947478572094688521116102469800350398642557
m2 = 15374382952448648386234156647364992061140979466732533176937863507778552068695153712875826599052803361828508498209602868391557371030313888768898114752847802838
x = PolynomialRing(Zmod(m1), "x").gen()
f = 65537*x**2 - m2
for i in f.roots(multiplicities = False):
print(i, long_to_bytes(int(i)))
```
> ++**Chú ý**++: Phương trình sẽ cho ra `2^3` nghiệm và trong số đó sẽ có `Flag1 mod m1`, ở đây vì `Flag1 < m1` nên nó tìm ra được `Flag1` luôn, còn nếu `Flag1 > m1` thì sẽ cho ra `Flag1 mod m1` chứ không phải `Flag1`, cũng không ảnh hưởng gì nhiều, ta chỉ cần brute force thêm một xíu thôi.
Có `Flag1`, thay ngược lại phương trình `m2` và tính được `flag2` là `7yp3_h323_83c4u53_7h15`:
```python=
from Crypto.Util.number import *
from sage.all import *
m2 = 15374382952448648386234156647364992061140979466732533176937863507778552068695153712875826599052803361828508498209602868391557371030313888768898114752847802838
x = PolynomialRing(ZZ, "x").gen()
f = 65537*bytes_to_long(b"KMACTF{n07h1n_1d34_70_")**2 + bytes_to_long(b"_ch4113n93_15_50_345y}")*x**2 - m2
print(long_to_bytes(int(f.roots()[0][0])))
```
Ta tìm được Flag hoàn chỉnh là:
```
KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}
```
Kết thúc Challenge.
:::spoiler **Full script**
```python=
from Crypto.Util.number import *
from math import prod
from pwn import *
from tqdm import *
from sage.all import *
carmichael = 2**6 * 3**2 * 5 * 7 * 13
Q = [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
n = prod(Q)
# n1 là padding cho đủ 2024 bit
n1 = 16137065238548023209354216756994085116039071329741992404760044520469775763598604679740651617211548370722607323479545645549867358928555262389728162798543590988183336155777102822466433736318341045782578414126244103517499384317415648780840623744041560018889448526450175979862047825655610652640229808466274926539017341691446592144579795902560014607660916789992333812186930296354747949841511313853809884979361487225668820393379628401205576558482036
N = n*n1
assert (N**2).bit_length() == 4048
exit = False
while True:
if exit:
break
print("Finding e such that gcd(e, lambda) == 1")
io = remote("165.22.55.200", 30001)
# io = process(["python3", "test.py"])
io.sendlineafter(b"> ", b"1"); io.sendlineafter(b" : ", b"1"); io.sendlineafter(b" : ", str(N).encode())
io.sendlineafter(b"> ", b"2"); io.recvuntil(b"ciphertext :\n")
c1, c2 = eval(io.recvline())
io.close()
c1 = c1 % n
c2 = c2 % n
# không biết e nên ta sẽ brute force d
print("finding d in range(1, lambda-1)")
for d in trange(1, carmichael):
m1 = pow(c1, d, n)
if m1.bit_length() < 300 and m1.bit_length() != 1 and long_to_bytes(m1).endswith(b"}"):
print("✅")
print(f"{d = }")
exit = True
break
io.close()
# có m1 là có flag3
m1 = int(m1)
m2 = pow(c2, d, n)
flag3 = long_to_bytes(m1)
print(f"{flag3 = }")
# credit: vanMjnh
# có flag3, ta mod m2 cho flag3
# được phương trình f = 65537*flag1**2 - m2
x = PolynomialRing(Zmod(m1), "x").gen()
f = 65537*x**2 - m2
# sẽ tìm ra nghiệm flag1 % flag3, xét luôn trường hợp flag1 > flag3
root = f.roots(multiplicities = False)
exit = False
for r in root:
if exit:
break
flag1_mod = int(r)
for k in range(100):
flag1 = long_to_bytes(flag1_mod + k*m1) # flag1 = flag1_mod + k*m1
if flag1.startswith(b"KMACTF{"):
print(f"{flag1 = }")
exit = True
break
# có flag1 và flag3 ta thay vào pt m2 để tìm nốt flag2
x = PolynomialRing(ZZ, "x").gen()
f = 65537*bytes_to_long(flag1)**2 + bytes_to_long(flag3)*x**2 - m2
root = f.roots()
flag2 = long_to_bytes(int(root[0][0]))
print(f"{flag2 = }")
print("✅", flag1 + flag2 + flag3)
"""
Finding e such that gcd(e, lambda) == 1
[+] Opening connection to 165.22.55.200 on port 30001: Done
[*] Closed connection to 165.22.55.200 port 30001
finding d in range(1, lambda-1)
61%|██████████████████████████████████████████████████████████▏ | 158761/262079 [00:04<00:03, 30791.95it/s]
✅ d = 159361
flag3 = b'_ch4113n93_15_50_345y}'
flag1 = b'KMACTF{n07h1n_1d34_70_'
flag2 = b'7yp3_h323_83c4u53_7h15'
✅ b'KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}'
"""
```
:::spoiler **Flag**
**KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}**
:::
# End
:::spoiler
Lại một mùa KMACTF trôi qua, em xin lỗi anh Tuệ
:::
Sign in with Wallet
Connect another wallet