<div style="text-align:center">
<h1>KMACTF 2025 2nd</h1>
</div>
## RAS
Source code :
::: 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!!!")
```
:::
Nhìn sơ qua Source code trên ta có thể thấy đây là một bài toán mã hóa RSA. Tuy nhiên, điểm đặc biệt là ta sẽ được phép truyền vào đây một Modulo $N$ và Server sẽ dùng nó để tính giá trị Modulo mới là $N^2$ làm Modulo chính của bài toán mã hóa này. Giá trị Modulo $N^2$ này sẽ phải có độ dài bằng $4048$ bits. Tiếp đến Server sẽ tạo ra một số mũ công khai $e$ có độ dài cũng bằng $4048$ bits. Dù nói là số mũ công khai thế nhưng ta sẽ không biết được giá trị của $e$ này. Cuối dùng, hai giá trị $N^2$ và $e$ này sẽ được dùng để mã hóa hai Plaintext là :
$$
c_1\equiv (\text{flag}_3)^e\pmod{N^2}\\
$$
$$
c_2\equiv (65537\times\text{flag}_1^2+\text{flag}_3\times\text{flag}_1^2)^e\pmod{N^2}
$$
Với từng giá trị $\text{flag}_1,\text{flag}_2,\text{flag}_3$ được định nghĩa như sau :
```python=
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:])
```
Và giờ, với hai kết quả $c_1,c_2$ trả về thì ta phải tìm cách nào đó để khôi phục được ba giá trị của ba phần Flag đó.
Điều đầu tiên mà ta có thể nghĩ đến và khai thác được là ở chỗ ta có thể gửi cho Server một Modulo $N$ tùy ý sao cho Modulo $N^2$ phải dài $4048$ bits. Điều đó có nghĩa là $N$ của ta bắt buộc phải dài $2024$ bits. Với việc biết được từng số nguyên tố cấu tạo nên $N$ và Modulo $N^2$ thì ta hoàn toàn có thể tính được giá trị $\phi(N^2)$, để từ đó có thể hướng tới việc tính giá trị bí mật $d$ bằng công thức :
$$
ed\equiv 1\pmod{\phi(N^2)}
$$
Thế nhưng như đã nói lúc đầu, ta không hề biết được giá trị của $e$. Chính vì vậy nên ta sẽ không thể tính giá trị của $d$. Còn nếu như bạn vẫn cố chày cối brute-force $e$ thì tốt nhất là nên bỏ đi :penguin:, $e$ đề bài cho có độ dài tới $4048$ bits lận, ngang với cả Modulo $N^2$ nên tốt nhất là không nên cố brute-force $e$. :smile:
Vậy bây giờ với bài này thì ta phải làm sao???
Trong quá trình giải đang diễn ra thì Author có hint cho chúng ta một thứ rất là quan trọng như sau :
Ban đầu, mục đích chính của ta khi chọn $N$ là chọn làm sao để cho giá trị của $\phi(N^2)$ là nhỏ nhất có thể. Làm như vậy sẽ giúp cho không gian tìm kiếm của $d$ trở nên nhỏ lại. Khi đó, ta chỉ cần brute-force $d$ sao cho nó thỏa mãn tính chất :
$$
\text{gcd}(d,\phi(N^2))=1
$$
Thế nên, nếu $\phi(N^2)$ quá lớn thì việc tìm $d$ sẽ rất lâu, hoặc có thể là không thể tìm được. Chính vì vậy trong RSA, ngoài giá trị $\phi(N)$ mà ta đã quá quen thuộc ra thì vẫn còn một giá trị khác cũng quan trọng không kém, đó chính là **Carmichael Lambda function**, ki hiệu là $\lambda(n)$.
> Giải thích sơ qua về **[Carmichael Lambda function](https://en.wikipedia.org/wiki/Carmichael_function)** $\lambda(n)$ :
> - Đây là một giá trị cũng quan trọng không khác gì giá trị **Euler Totient Function** $\phi(n)$. Ta hoàn toàn dùng giá trị này để thay thế cho $\phi(n)$ mà vẫn đảm bảo tính bảo mật của RSA.
> - Cho $n=p.q$, với $p,q$ là hai số nguyên tố lớn phân biệt. Giá trị $\lambda(n)$ được tính như sau :
> $$
> \lambda(n)=\text{lcm}(\lambda(p),\lambda(q))
> $$
> - Vì $p,q$ là số nguyên tố nên ta có tính chất :
> $$
> \begin{cases}
> \lambda(p)=\phi(p)=p-1\\
> \lambda(q)=\phi(q)=q-1
> \end{cases}
> $$
>
> $$
> \Rightarrow \lambda(n)=\text{lcm}(p-1,q-1)
> $$
> - Tới đây, ta chọn một số nguyên $e$ bất kì thỏa mãn : $1<e<\lambda(n)$ và $\text{gcd}(e,\lambda(n))=1$. Khi đó, $e$ sẽ là số mũ công khai của ta
> - Còn với giá trị bí mật $d$ thì ta vẫn sẽ tính theo công thức : $ed\equiv1\pmod{\lambda(n)}$
Như vậy đó chính là cách mà RSA hoạt động với hàm $\lambda(n)$ thay vì $\phi(n)$. Vậy nó sẽ có ý nghĩa gì trong bài toán này? Trước hết, ta có được tính chất của hàm $\lambda(n)$ như sau :
$$
\lambda(n)=
\begin{cases}
\phi(n)\hspace{58mm}\text{nếu n là 1, 2, 4 hoặc là lũy thừa của một số nguyên tố lẻ}\\
\frac{1}{2}\phi(n)\hspace{54mm}\text{nếu }n=2^r,r\geq 3 \\
\text{lcm}(\lambda(n_1),\lambda(n_2),...,\lambda(n_k))\hspace{5mm}\text{nếu }n=n_1n_2...n_k\text{ là tích của các lũy thừa nguyên tố}\\
\end{cases}
$$
Có thể thấy, với một vài trường hợp thì $\lambda(n)\leq\phi(n)$. Chính vì vậy sẽ dẫn đến việc nếu biết $\lambda(n)$ chỉ có một giá trị nhỏ thì kẻ tấn công có thể hoàn toàn brute-force $d$ rồi tính : $c^d\pmod{n}$, bởi vì khi này không gian các $d$ hợp lệ chỉ có khoảng từ $1$ cho tới $\lambda(n)$. Nếu tồn tại một giá trị $d$ sao cho $ed\equiv1\pmod{\lambda(n)}$ thì khi đó ta sẽ có : $c^d\equiv m\pmod{n}$.
Tóm lại, ý tưởng ở đây là ta sẽ tạo ra một Modulo $N$ có dạng là $N=n_1.n_2$ sao cho : $n_1$ của ta là một Modulo con có giá trị $\lambda(n_1)$ nhỏ và $n_2$ sẽ là một số nguyên tố lớn đóng vai trò Padding sao cho $N$ dài đủ $2024$ bits để thỏa mãn điều kiện của Server.
Bởi vì khi đó ta sẽ nhận về được hai giá trị :
$$
\begin{cases}
c_1\equiv (m_1)^e\pmod{N^2}\\
c_2\equiv (m_2)^e\pmod{N^2}
\end{cases}
$$
Khi này, lấy Modulo $n_1$ ở cả hai vế ta sẽ có :
$$
\begin{cases}
c_1\equiv (m_1)^e\pmod{n_1}\pmod{N^2}\\
c_2\equiv (m_2)^e\pmod{n_1}\pmod{N^2}
\end{cases}
$$
Và do $n_1<N^2$ nên ta có thể bỏ $\pmod{N^2}$ đi để còn lại :
$$
\begin{cases}
c_1\equiv (m_1)^e\pmod{n_1}\\
c_2\equiv (m_2)^e\pmod{n_1}
\end{cases}
$$
Khi này, ta đã thu về được một công thức mã hóa RSA trong Modulo $n_1$ có $\lambda(n_1)$ là một số nhỏ nhất có thể. Khi này chỉ cần brute-force $d$ trong khoảng từ $1$ cho tới $\lambda(n_1)$ là đã có được giá trị $m_1$ và $m_2$ rồi phải không? Tất nhiên là chưa rồi :smile:. Vì như đã nói, nếu như tồn tại $d$ sao cho $ed\equiv 1\pmod{\lambda(n)}$, hay nói cách khác là $\text{gcd}(e,\lambda(n))=1$ thì khi đó ta sẽ có thể thu lại được hai giá trị $m_1$ và $m_2$ chỉ với :
$$
\begin{cases}
m_1\equiv (c_1)^d\pmod{n_1}\\
m_2\equiv (c_2)^d\pmod{n_1}
\end{cases}
$$
Thế nhưng không phải lúc nào $e$ của ta lại có thể nguyên tố cùng nhau với $\lambda(n)$ bởi vì $e$ Server tạo ra là hoàn toàn ngẫu nhiên như trong đoạn này :
```python=
def generate_e(self):
e = random.getrandbits(4048)
return e
```
Khi đó, xác suất để $\text{gcd}(e,\lambda(n))=1$ sẽ khá thấp. Vậy thì ta sẽ giải quyết vấn đề này như thế nào? Trước hết ta hãy giả sử rằng :
$$
\text{gcd}(e,\lambda(n))=g>1
$$
Khi đó ta sẽ có được công thức của $e$ và $\lambda(n)$ như sau :
$$
\begin{cases}
e=g.h\\
\lambda(n)=g.L
\end{cases}
$$
Với $h$ và $L$ là một số nguyên nào đó thỏa mãn $\text{gcd}(h,L)=1$. Gọi $d\equiv h^{-1}\pmod{L}$. Khi này ta có :
$$
ed=(g.h).d=g.(h.d)=g(1+kL)=g+kgL=g+k.\lambda(n)
$$
Lấy Modulo $\lambda(n)$ ta có :
$$
ed\equiv g\pmod{\lambda(n)}
$$
$$
\Rightarrow c^d\equiv (m^e)^d\equiv m^{ed}\equiv m^g\pmod{n}
$$
Khi này, với việc brute-force $d$ thì ta sẽ có thể nhận lại giá trị $m^g\pmod{n}$ nếu $\text{gcd}(e,\lambda(n))=g>1$. Tới đây sẽ có một trick cực lỏ là ta sẽ spam connect tới Server liên tục sao cho ta nhận được một Ciphertext mà nó được mã hóa bởi $e$ sao cho $\text{gcd}(e,\lambda(n))=g=1$. Nhưng làm sao để biết được $\text{gcd}$ của chúng nếu ta không biết được giá trị của $e$
Giả sử rằng, ta có Modulo $n=p_1.p_2....p_k$ là tích các số nguyên tố khác nhau, hay ta còn gọi $n$ là **square-free**. Khi này, dựa vào công thức tính $\lambda(n)$ đã nói ở trên, ta có :
$$
\lambda(n)=\text{lcm}(p_1-1,p_2-1,...,p_k-1)
$$
Gọi $G=(\mathbb{Z}/n\mathbb{Z})^{\times}$ là nhóm nhân Modulo $n$, có bậc là $\lambda(n)$. Bời vì khi đó với mọi $a\in G$ ta có định lý Carmichael như sau :
$$
a^{\lambda(n)}\equiv 1\pmod{n}
$$
Theo bài toán mà ta có được là :
$$
c_1\equiv m_1^e\pmod{n1}
$$
Nếu như ta gọi $g=\text{gcd}(e,\lambda(n_1))$ thì :
$$
c_1^{\frac{\lambda(n_1)}{g}}\equiv (m_1^e)^{\frac{\lambda(n_1)}{g}}\pmod{n_1}
$$
Vì $e=g.h$, với $h\in\mathbb{Z}$ nên ta có :
$$
m_1^{\frac{e.\lambda(n_1)}{g}}\equiv m_1^{h.\lambda(n_1)}\equiv 1\pmod{n_1}
$$
$$
\Rightarrow c_1^{\frac{\lambda(n_1)}{g}}\equiv 1\pmod{n_1}
$$
Với mỗi giá trị $t$ là ước của $\lambda(n_1)$, ta sẽ kiểm tra xem các giá trị $t$ nào thỏa mãn :
$$
c_1^{\frac{\lambda(n1)}{t}}\equiv 1\pmod{n1}
$$
Và trong tập các giá trị $t$ đó, giá trị nào cao nhất thì đó chính là $g=\text{gcd}(e,\lambda(n))$. Và biết $g$ thì bạn biết rằng ciphertext khi giải mã chỉ trả về $m^g$ chứ không phải là $m$. Chính vì vậy, ta sẽ thử spam connect tới Server sao cho tìm thấy được $g=1$ là ta sẽ thu về được $m_1$ và $m_2$. Vậy khi có được $m_1$ và $m_2$ rồi thì ta sẽ làm gì?
Nhắc lại mối quan hệ giữa $m_1$ và $m_2$ là :
$$
m_2=65537.\text{flag}_1^2+m_1.\text{flag}_2^2
$$
Đặt :
$$
m_2=65537.x+m_1.y
$$
$$
\Leftrightarrow 65537.x+m_1.y-m_2=0
$$
Ý tưởng ở đây là mình sẽ sử dụng LLL để tìm lại hai giá trị $x$ và $y$ thỏa mãn phương trình trên. Nhưng liệu như vậy có đúng hay không? Khi thử test case thì mình thu được như sau :
```python=
from sage.all import *
from Crypto.Util.number import bytes_to_long
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
W = 2**(13*8)
M = Matrix([
[65537 * W, 1, 0 ,0],
[m1 * W, 0, 1, 0],
[-m2 * W, 0, 0, 1]
])
L = M.LLL()
print(L)
"""
[0, -5010948255019824457681085611901, 65537, 0]
[-20282409603651670423947251286016, 1082365434762968018416061887515, -14156, 0]
[0, 328403443396810188616044793109045393, 25109602414486223688247108060940601441107012548648521499031857, 1]
"""
```
Vector mục tiêu của ta sau khi tính LLL là $[0,x,y,1]$ và nó có xuất hiện trong kết quả trả về như trên. Tất nhiên là nó cũng sẽ thỏa mãn điều kiện là :
```python=
assert 65537*x + m1*y - m2 == 0
```
Thế nhưng, nếu để ý kĩ thì ta sẽ thấy điều kì lạ. Rõ ràng $\text{flag}_1$ và $\text{flag}_2$ đều có độ dài ngang nhau. Khi đấy, bình phương của chúng chắc chắn sẽ gần giống nhau. Thế nhưng trong Vector mà LLL trả về cho ta thì giá trị của $x$ lại bé hơn rất nhiều so với giá trị của $y$. Điều đó có thể khiến cho bạn bị bối rối và cho rằng LLL đã sai và sẽ không thể dùng LLL để giải bài này được.
Tuy nhiên, khi sử dụng hàm `iroot` trong thư viện `gmpy2` để tính căn bậc hai của $y$ thì ta sẽ có kết quả là :
```python=
from gmpy2 import iroot
x = L[2][1]
y = L[2][2]
assert 65537*x + m1*y - m2 == 0
print(iroot(y, 2)
#(mpz(5010948255019824457681085658289), False)
```
Đổi giá trị đó sang dạng bytes thì ta sẽ thu được :
```python=
print(long_to_bytes(iroot(y, 2)[0]))
# b'???????????\xf4\xb1'
```
Có thể thấy, đây chính là một phần trong Flag của ta, và nó chính là phần của $\text{flag}_2$. Tuy nhiên có thể thấy là các bytes cuối của phần này nó không được đúng lắm, điều đó chứng tỏ rằng chúng đang bị mất hoặc bị thừa ra một vài LSBs nhất định. Và khi thử test case bằng cách tính :
```python=
delta = (iroot(y, 2)[0] - flag2)
```
Mình nhận thấy được rằng lượng giá trị mà `iroot(y, 2)[0]` bị mất/thừa là dưới giá trị $2^{16}$. Điều cho phép ta hoàn toàn có thể brute-force được trong khoảng không gian đó bằng cách tính :
```python=
flag2 = iroot(y, 2)[0] + delta, với delta < 2^16
```
Khi đó là ta đã hoàn toàn khôi phục được $\text{flag}_2$ chăng? Tất nhiên là vẫn chưa là bởi vì ta chưa có điều kiện dừng cho việc brute-force đó. Với mỗi giá trị $\text{flag}_2$ mà ta có được thì ta sẽ thử thế vào phương trình ban đầu xem khi thử tính căn bậc hai của $\text{flag}_1$ thì ta có thu được giá trị chính xác hay không. Và từ đó là ta đã khôi phục được Flag gốc rồi. Hàm tính LLL để khôi phục Flag cụ thể như sau :
```python=
def LLL_to_get_flag(m1, m2):
W = 2**(len(long_to_bytes(m1))*8)
M = Matrix([
[65537 * W, 1, 0 ,0],
[m1 * W, 0, 1, 0],
[-m2 * W, 0, 0, 1]
])
L = M.LLL()
x = L[2][1]
y = L[2][2]
assert 65537*x + m1*y - m2 == 0
# delta = (iroot(y, 2)[0] - flag2)
# print(long_to_bytes(flag2)) #<- Test case
# print(long_to_bytes(iroot(y, 2)[0] - delta))
for i in range(2**16 - 1):
flag2_test = iroot(y, 2)[0] - i
if all([i in (string.ascii_letters + string.digits + string.punctuation).encode() for i in long_to_bytes(flag2_test)]):
flag1_times_65537 = m2 - m1 * (flag2_test)**2
flag1_test = iroot(flag1_times_65537 // 65537, 2)[1]
if flag1_test:
flag1 = iroot(flag1_times_65537 // 65537, 2)[0]
flag = (long_to_bytes(flag1) + long_to_bytes(flag2_test) + long_to_bytes(m1)).decode()
break
return flag
```
Full Script giải :
```python=
from sage.all import *
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes, getPrime, isPrime
from tqdm import trange
from pwn import process, remote
import string
from sympy import factorint
def LLL_to_get_flag(m1, m2):
W = 2**(len(long_to_bytes(m1))*8)
M = Matrix([
[65537 * W, 1, 0 ,0],
[m1 * W, 0, 1, 0],
[-m2 * W, 0, 0, 1]
])
L = M.LLL()
x = L[2][1]
y = L[2][2]
assert 65537*x + m1*y - m2 == 0
# delta = (iroot(y, 2)[0] - flag2)
# print(long_to_bytes(flag2)) #<- Test case
# print(long_to_bytes(iroot(y, 2)[0] - delta))
for i in range(2**16 - 1):
flag2_test = iroot(y, 2)[0] - i
if all([i in (string.ascii_letters + string.digits + string.punctuation).encode() for i in long_to_bytes(flag2_test)]):
flag1_times_65537 = m2 - m1 * (flag2_test)**2
flag1_test = iroot(flag1_times_65537 // 65537, 2)[1]
if flag1_test:
flag1 = iroot(flag1_times_65537 // 65537, 2)[0]
flag = (long_to_bytes(flag1) + long_to_bytes(flag2_test) + long_to_bytes(m1)).decode()
break
return flag
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)
n1 = 1
for i in divisor :
n1*=i
assert carmichael_lambda(n1) == sample
for i in range(1,10000) :
if gcd(i , n1) == 1 :
assert pow(i , sample , n1) == 1
# n2 = getPrime(2025 - len(bin(n1)[2:]))
n2 = 885768922644060550487726056681266275101625872016671059156257898816212367550284523465929006595894134982312952308108982880630764665335029830169637764939195525779490508106986835729724622178166228657566943635944805951814311998950083437024070197465778152382893189641154963923661362682016314852065827533260554477698263243209630638677192179606586773664154829242789095396953881224380811
divisor = divisor + [n2]
N = n1 * n2
# print(f"n1 = {n1}")
# print(f"n2 = {n2}")
# print(f"N = {N}")
# print(f"bit_length = {n1.bit_length()}")
# print(f"divisors = {divisor}")
HOST, PORT = "165.22.55.200", 30001
io = remote(HOST, PORT)
# io = process(["python", "chal.py"])
io.recvuntil(b"> ")
io.sendline(b"1")
io.recvuntil(b"RSA system : ")
io.sendline(str(len(divisor)).encode())
for i, p in enumerate(divisor):
io.recvuntil(f"Prime {i} : ".encode())
io.sendline(str(p).encode())
io.recvuntil(b"> ")
io.sendline(b"2")
io.recvline()
c1, c2 = eval(io.recvline().decode())
# print(f"c1 = {c1}")
# print(f"c2 = {c2}")
c1_ = c1 % n1
c2_ = c2 % n1
# Tìm gcd(e, λ)
g0 = gcd(c1_, n1)
n_unit = n1 // g0
c1_unit = c1_ % n_unit
factors_unit = list(factorint(n_unit).keys())
lam_unit = 1
for p in factors_unit:
lam_unit = lcm(lam_unit, p-1)
divs = [d for d in range(1, lam_unit+1) if lam_unit % d == 0]
good = []
for t in divs:
if pow(c1_unit, lam_unit//t, n_unit) == 1:
good.append(t)
print("Các t thỏa :", good)
g = good[-1]
print(f"GCD(e, λ) = {g}")
if g == 1:
for e_prime in trange(g, sample + 1):
if gcd(e_prime, sample) != g:
continue
h = e_prime // g
L = sample // g
d = pow(h, -1, L)
m1_try = pow(c1_, d, n1)
m2_try = pow(c2_, d, n1)
if all([i in (string.ascii_letters + string.digits + string.punctuation).encode() for i in long_to_bytes(m1_try)]) and len(long_to_bytes(int(m2_try))) > 35:
m1 = m1_try
m2 = m2_try
print(f"m1 = {m1}")
print(f"m2 = {m2}")
flag = LLL_to_get_flag(m1, m2)
print(f"\nFlag : {flag}\n")
break
else:
print("GCD is not 1. Try again :(")
```
Tất nhiên là bạn sẽ phải thử spam connect tới Server cho đến khi có thể tìm được $g=1$ là sẽ có được Flag như thế này :
<details>
<summary>Flag</summary>
KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}
</details>
## Chatgpt
Source code :
::: 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
```
:::
Nhìn qua Source code thì ta có thể thấy Source đang thực hiện mã hóa AES theo một dạng nào đó với từng bước mã hóa như đã thể hiện trong Source code. Nó giống như là một sự kết hợp giữa chế độ ECB cùng với tính năng xác thực gần giống như GCM và cuối cùng ta có một chức năng mô phỏng trao đổi khóa Diffie-Hellman nhưng nó không phải theo dạng chuẩn mà chỉ là dạng tự xây dựng nên.
Đó là tất cả những thông tin mà ta biết được về các hàm mã hóa. Ở đây, Source sẽ cho ta Ciphertext, tag $T$ và hai giá trị khóa công khai trong giao thức giao đổi khóa mà Source tự xây dựng lên là $A$ và $B$. Source cũng sẽ cho ta 3 option là : `Decrypt, Encrypt, Get Flag`. Mỗi lần sử dụng một chức năng thì ta sẽ bị trừ `coint` tương ứng, với giá trị `coint` ban đầu bằng $10$. Để lấy được Flag thì ta sẽ phải giải mã Ciphertext mà Source cho.
Vậy ta sẽ giải bài này như thế nào đây ?
Trong quá trình giải đang diễn ra thì Author có hint cho bài này như sau :
Dựa vào hint đó thì mình có thể đoán được rằng : Thực chất các hàm mã hóa và giải mã AES như trong Source code cho là đang theo một chế độ mã hóa nào đó mà ta chưa biết. Vậy thì ý tưởng bây giờ là ta sẽ thử đi tìm xem tên của chế độ mã hóa AES đó là gì.
Sau một hồi tìm hiểu trên Internet, cùng với sự giúp đỡ của các công cụ AI thì mình biết được rằng : Tên của chế độ mã hóa đó là **AES_MODE-XCB**
>Nói sơ qua về XCB : **XCB (Extended Codebook)** là một chế độ mã hóa theo dạng TEM (Tweakable Enciphering Mode - chế độ mã hóa có thể tinh chỉnh) đã được chuẩn hóa trong IEEE 1619.2 để mã hóa ổ đĩa, với security proof là STPRP (hoán vị giả ngẫu nhiên mạnh có thể tinh chỉnh). Nó bao gồm các phiên bản như XCBv1, XCBv2, XCBv2fb, đặc biệt là XCBv2 khi mà nó được dùng trong mã hóa ổ đĩa.
Sơ đồ cấu trúc của XCB như sau :
Thực ra khi tìm kiếm về chế độ này thì bạn sẽ có thể dễ dàng tìm thấy được những cái tài liệu hướng dẫn Recover Plaintext từ chế độ này. Ví dụ như là :
Link tải các tài liệu này : **[1527](https://eprint.iacr.org/2024/1527.pdf)**, **[1554](https://eprint.iacr.org/2024/1554.pdf)**
Ở đây mình sẽ phân tích tài liệu số **1527** và **1554** để khai thác bài này. Trước hết, ta cần biết rằng **AES_MODE-XCB** là một dạng mã hóa khối. Ở đây ta sẽ có hai hàm băm là $H1$ và $H2$ được định nghĩa dựa trên hàm băm đa thức như sau :
Ngoài ra, ta có Counter Mode cũng được định nghĩa như sau :
Kèm với đó, ta có hàm sinh khóa cho chế độ này cũng rất đặc biệt và cũng được định nghĩa như sau :
Tất cả những lý thuyết trên đều nằm trong tài liệu số 1554.
Về ý tưởng chính của cách tấn công này, ta sẽ chú ý vào hai hàm băm là $H1$ và $H2$. Chúng được gọi là UHF - Universal Hash Function và ngoài ra chúng đều là XOR-Universal Hash Function, tức là là các hàm băm XOR phổ dụng cho phép với một khoá $K$ được chọn ngẫu nhiên, khi dùng cho 2 Plaintext $A$ và $B$ thì ta có thể có output là một kết quả gần như ngẫu nhiên.
Ngoài ra, các hàm băm này có một tính chất rất quan trọng giúp ta có thể khai thác được chế độ này đó chính là **tính có thể tách rời (separability)**, được định nghĩa trong tài liệu số 1554 như sau :
Với tính chất này, dù cho $H1$ lẫn $H2$ có khác nhau về thiết kế nhưng về bản chất thì chúng vẫn là các hàm băm đa thức với đầu vào được phân tách miền, và chỉ với việc dùng chung một khóa $K$ cho cả hai hàm băm thì đó cũng đã tạo ra một lỗ hỏng bảo mật rất lớn rồi.
Ví dụ ta xét một khóa $K$ với độ dài $k$ bits, một Tweak $T$ có độ dài $t$ bits và hai chuỗi $M$ và $C$ có cùng độ dài là $a$ bits. Ta có định nghĩa về tổng của $H1$ và $H2$ với các Input là :
với $\mathfrak{L}$ là một giá trị cố định phụ thuộc vào $|T|$ và $|M| = |C|$. Chính vì vậy, với mọi chuỗi $\Delta$ có length nhỏ hơn hoặc bằng $a$ thì ta có :
Chính vì thế nên khi thay $M=M\oplus\Delta$ và $C=C\oplus\Delta$ thì từ $(6)$ vẫn có thể ra được $(7)$ là do tính chất XOR $M\oplus\Delta\oplus C\oplus\Delta=M\oplus C$. Do đó, kẻ tấn công có thể xây dựng một Query $C'$ và một Query $M'$ để ép đầu ra $X$ của Counter (IV đầu vào cho CTR) trước đó được sử dụng để tạo ra $C$ xuất hiện lại ở phần Query $M'$. Khi này, chỉ cần $\oplus$ $M'_L$ với tất cả các khối trừ khối cuối của Ciphertext thì ta có thể khôi phục lại hoàn toàn Plaintext chỉ với hai Queries. Cách tấn công này được gọi là **Shared Difference Attack.**. Cụ thể ta có các bước tấn công như sau :
Dựa vào các tấn công trên là ta đã có thể khôi phục lại Plaintext để gửi cho Server rồi!!!
Full Script :
```python=
from binascii import unhexlify, hexlify
from hashlib import sha256
from Crypto.Cipher import AES
from pwn import remote, xor
from secrets import token_bytes
BLOCK = 16
R_POLY = 0xE1000000000000000000000000000000
KEY_SIZE_BITS = 256
MAX_INT = 1 << KEY_SIZE_BITS
MOD = MAX_INT - 189
SEED = MAX_INT // 6
def calculate_sharekey(A: int, B: int):
inv_seed = pow(SEED, -1, MOD)
shared_int = (A * B * inv_seed) % MOD
key16 = sha256(str(shared_int).encode()).digest()[:16]
return shared_int, key16
io = remote("165.22.55.200", 30002)
# Lấy các giá trị của Server trả về
io.recvuntil(b"ciphertext:")
ct = io.recvline().strip().decode()
io.recvuntil(b"T (hex):")
T = io.recvline().strip().decode()
io.recvuntil(b"A:")
A = io.recvline().strip().decode()
io.recvuntil(b"B:")
B = io.recvline().strip().decode()
# Tính key được
share_int, key16 = calculate_sharekey(int(A), int(B))
cipher = AES.new(key16, AES.MODE_ECB)
raw_cipher = cipher.decrypt(unhexlify(ct))
raw_T = cipher.decrypt(unhexlify(T))
if len(raw_cipher) < BLOCK:
print("Break")
G, E = raw_cipher[:BLOCK], raw_cipher[BLOCK:]
print(len(E))
delta = token_bytes(len(E))
if all(b == 0 for b in delta):
S = bytes([1]) * len(E)
# Mã hóa (M'L xor Delta) || M'R
io.recvuntil(b"Your choice:")
io.sendline(b"1")
io.recvuntil(b"Ciphertext (hex):")
# Giải mã (CL xor Delta) || CR với Tweak T
io.sendline((hexlify(G + xor(E, delta)).decode()).encode())
io.recvuntil(b"T (hex):")
io.sendline((hexlify(raw_T).decode()).encode())
io.recvuntil(b"Plaintext (hex):")
plaintext = io.recvline().strip().decode()
plaintext = unhexlify(plaintext)
A1, B1 = plaintext[:BLOCK], plaintext[BLOCK:]
P2 = A1 + xor(B1, delta)
io.recvuntil(b"Your choice:")
io.sendline(b"2")
io.recvuntil(b"Plaintext (hex):")
io.sendline((hexlify(P2).decode()).encode())
io.recvuntil(b"T (hex):")
io.sendline((hexlify(raw_T).decode()).encode())
io.recvuntil(b"Ciphertext (hex):")
ciphertext2 = io.recvline().strip().decode()
ciphertext2 = unhexlify(ciphertext2)
G2, E2 = ciphertext2[:BLOCK], ciphertext2[BLOCK:]
L = min(len(E), len(B1), len(E2), len(delta))
recovered = bytes(x ^ y ^ z ^ w for x,y,z,w in zip(E[:L], B1[:L], E2[:L], delta[:L]))
io.recvuntil(b"Your choice:")
io.sendline(b"3")
io.recvuntil(b"Plaintext (hex):")
io.sendline((hexlify(recovered).decode()).encode())
flag = io.recvline().decode()
print(flag)
```
<details>
<summary>Flag</summary>
KMACTF{h0w_m4ny_qu3ri3s_d0_y0u_n33d_2_bre4k_m3_i_know_2_4r3_3n0ugh}
</details>
BY : **AT21N - Vũ Hoàng Linh**
Sign in with Wallet
Connect another wallet