# KCSC TTV CRYPTO MB 2024 (8/8)
## Base64 (warm up)
- **Source Code:**
```python!
b64 = {'000000': '/', '000001': '+', '000010': '0', '000011': '1', '000100': '2', '000101': '3', '000110': '4', '000111': '5', '001000': '6', '001001': '7', '001010': '8', '001011': '9', '001100': 'a', '001101': 'b', '001110': 'c', '001111': 'd', '010000': 'e', '010001': 'f', '010010': 'g', '010011': 'h', '010100': 'i', '010101': 'j', '010110': 'k', '010111': 'l', '011000': 'm', '011001': 'n', '011010': 'o', '011011': 'p', '011100': 'q', '011101': 'r', '011110': 's', '011111': 't', '100000': 'u', '100001': 'v', '100010': 'w', '100011': 'x', '100100': 'y', '100101': 'z', '100110': 'A', '100111': 'B', '101000': 'C', '101001': 'D', '101010': 'E', '101011': 'F', '101100': 'G', '101101': 'H', '101110': 'I', '101111': 'J', '110000': 'K', '110001': 'L', '110010': 'M', '110011': 'N', '110100': 'O', '110101': 'P', '110110': 'Q', '110111': 'R', '111000': 'S', '111001': 'T', '111010': 'U', '111011': 'V', '111100': 'W', '111101': 'X', '111110': 'Y', '111111': 'Z'}
def encode(string):
s = ""
for i in string:
s += bin(ord(i))[2:].zfill(8)
pad = ""
if len(s) % 6 == 4:
pad = "="
s += "11"
elif len(s) % 6 == 2:
pad = "=="
s += "1111"
ret = ""
for i in range(0,len(s),6):
ret += b64[s[i:i+6]]
return ret+pad
from secret import FLAG
print(encode(FLAG))
# gObheRHIpN+wlQ7vqQiQb3XzpAbJn4iv6lR=
```
- **Mô tả:** Challenge này thực hiện mã hóa `Base64` thủ công nhưng vị trí các ký tự trong `b64` không giống như trong mã hóa `Base64` thông thường và thay vì pad những bit `0` thì challenge pad bit `1`, nói chung là ta không dùng hàm `b64decode()` được đâu :smile:
- Để thực hiện giải mã ciphertext thì ta sẽ ánh xạ ngược lại ciphertext vào bảng `b64` của challenge là được, vì thế ta sẽ đảo ngược lại `b64`:
```python!
rev_b64 = {v: k for k, v in b64.items()}
```
- Ta có `rev_b64` như sau:
```python!
{'/': '000000', '+': '000001', '0': '000010', '1': '000011', '2': '000100', '3': '000101', '4': '000110', '5': '000111', '6': '001000', '7': '001001', '8': '001010', '9': '001011', 'a': '001100', 'b': '001101', 'c': '001110', 'd': '001111', 'e': '010000', 'f': '010001', 'g': '010010', 'h': '010011', 'i': '010100', 'j': '010101', 'k': '010110', 'l': '010111', 'm': '011000', 'n': '011001', 'o': '011010', 'p': '011011', 'q': '011100', 'r': '011101', 's': '011110', 't': '011111', 'u': '100000', 'v': '100001', 'w': '100010', 'x': '100011', 'y': '100100', 'z': '100101', 'A': '100110', 'B': '100111', 'C': '101000', 'D': '101001', 'E': '101010', 'F': '101011', 'G': '101100', 'H': '101101', 'I': '101110', 'J': '101111', 'K': '110000', 'L': '110001', 'M': '110010', 'N': '110011', 'O': '110100', 'P': '110101', 'Q': '110110', 'R': '110111', 'S': '111000', 'T': '111001', 'U': '111010', 'V': '111011', 'W': '111100', 'X': '111101', 'Y': '111110', 'Z': '111111'}
```
- Nhìn vào source code thì ta thấy nếu chiều dài chuỗi nhị phân của plaintext `% 6` mà còn `4` thì sẽ được thêm hai bit `11` và được thêm dấu `=` ở ciphertext, vì thế ta sẽ phải bỏ đi dấu `=` và bỏ đi hai bit `11` ở cuối.
- **Script**:
```python!
a = "gObheRHIpN+wlQ7vqQiQb3XzpAbJn4iv6lR="
b64 = {'000000': '/', '000001': '+', '000010': '0', '000011': '1', '000100': '2', '000101': '3', '000110': '4', '000111': '5', '001000': '6', '001001': '7', '001010': '8', '001011': '9', '001100': 'a', '001101': 'b', '001110': 'c', '001111': 'd', '010000': 'e', '010001': 'f', '010010': 'g', '010011': 'h', '010100': 'i', '010101': 'j', '010110': 'k', '010111': 'l', '011000': 'm', '011001': 'n', '011010': 'o', '011011': 'p', '011100': 'q', '011101': 'r', '011110': 's', '011111': 't', '100000': 'u', '100001': 'v', '100010': 'w', '100011': 'x', '100100': 'y', '100101': 'z', '100110': 'A', '100111': 'B', '101000': 'C', '101001': 'D', '101010': 'E', '101011': 'F', '101100': 'G', '101101': 'H', '101110': 'I', '101111': 'J', '110000': 'K', '110001': 'L', '110010': 'M', '110011': 'N', '110100': 'O', '110101': 'P', '110110': 'Q', '110111': 'R', '111000': 'S', '111001': 'T', '111010': 'U', '111011': 'V', '111100': 'W', '111101': 'X', '111110': 'Y', '111111': 'Z'}
rev_b64 = {v: k for k, v in b64.items()} #đảo ngược dict b64
def decode(flag):
s = ""
for i in flag[:-1]: #bỏ đi dấu =
s += rev_b64[i]
s = s[:-2] #vì có dấu = ở cuối nên bỏ đi 11
a = ""
for i in range(0, len(s), 8):
a += chr(int(s[i:i+8], 2))
return a
print(decode(a))
```
:::spoiler Flag
**KCSC{no0b_base64_encode!!}**
:::
## Baby RSA (easy)
- **Source Code:**
```python!
from Crypto.Util.number import *
from secret import flag
# Params
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e1 , e2 = getPrime(15) , getPrime(15)
# Encrypt
c1 , c2 = pow(m,e1,n) , pow(m,e2,n)
#Print
print(f'{c1 = }')
print(f'{c2 = }')
print(f'{n = }')
```
:::spoiler output
c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733
:::
- **Mô tả:** Chơi RSA đủ lâu bạn sẽ biết ngay đây là kiểu tấn công `Common Modolus` vì Challenge này mã hóa hai Ciphertext nhưng sử dụng chung Modulus $N$ và khác mũ $e$.
- Ta sẽ sử dụng thuật toán Euclid mở rộng để tìm được hai giá trị $u,v$ sao cho:
$$e_1 \times u + e_2 \times v = 1$$
- Mục đích là khi ta nhân $C_1^u$ cho $C_2^v$ thì ta được:
$$C_1^u \times C_2^v = M^{e_1\times u + e_2 \times v} = M^1 = M$$
- Nhưng Challenge này không cho ta biết hai giá trị $e_1, e_2$, ta sẽ phải đi brute-force chúng.
- Ta biết rằng $e$ là số nguyên tố có giá trị $15$ bit, khoảng $2^{14} \leqslant e \leqslant 2^{15}-1$, nên ta sẽ sử dụng hàm `primerange()` của thư viện `sympy` để liệt kê các số nguyên tố trong khoảng đó mà không phải xét qua các giá trị không cần thiết.
- Để tính thuật toán Euclid mở rộng thì có thể code tay hoặc dùng hàm có sẵn như mình cũng được. Mình sẽ dùng hàm `gcdext()` của thư viện `gmpy2`. Hàm nhận vào hai giá trị và trả về ba giá trị là **gcd, u, v**.
- **Script:**
```python!
from sympy import primerange
from Crypto.Util.number import*
import gmpy2
from tqdm import tqdm
c1 = ...
c2 = ...
n = ...
# các số nguyên tố 15-bit
primes_15bit = list(primerange(2**14, 2**15-1))
# thử tất cả các cặp (e1, e2)
flag_found = False
for e1_guess in tqdm(primes_15bit):
if flag_found:
break
for e2_guess in primes_15bit:
g, u, v = gmpy2.gcdext(e1_guess, e2_guess)
a = long_to_bytes((pow(c1, u, n) * pow(c2, v, n)) %n)
if b'KCSC{' in a:
print(e1_guess)
print(e2_guess)
print(a)
flag_found = True
break
```
:::spoiler Flag
e1 = 21341
e2 = 25261
**KCSC{3x73rn4l_4774ck_1n_r54}**
:::
## Equation (easy)
- **Source Code:**
```python!
from Crypto.Util.number import *
from secret import flag
def encrypt(key,m,p) :
x = pow(key[0],key[1]*key[3])*m[0] + pow(key[1],key[0])*m[1] + key[3]*pow(key[0],key[2])
y = pow(key[2],7)*m[0] - key[3]*m[1] - pow(key[1],key[2]) + pow(key[1],key[3])
return x % p , y % p
l = len(flag)
m = [bytes_to_long(flag[:l//2]) , bytes_to_long(flag[l//2:])]
key = [getPrime(512) for _ in range(4)]
p = getPrime(513)
assert m[0] < p and m[1] < p
print(f'{p = }')
print(f'{key = }')
print(f'enc = {encrypt(key,m,p)}')
```
:::spoiler output
p = 20750581162356901822371358081190571328015802896649862988773357210365403451164295986427869541008180700500353488943618054413871626104729648400643237412907397
key = [10615429627321757928177738179133185296570017221477669072758978616664228021845901597204223511408890540624134699383980095897619794674624492632667368475358259, 8098501561956901533078786276609230622379951738654895152558539730068867983865132393839072902654774417952229287146962827464998772217889942772581719194190131, 9269375490983296814341239266604470459081391713689916499923163097001047076919399181791596915795736751249702479913935198254324261729115107153324477349756427, 12874926087069061223584117322772472091608363055078190028227481439885266810498837550235424358641464176775190647579561772510312989190222563737455288997494613]
enc = (5309143145537110495610885061155974900644691542339737247048051865028676282189484534760797421532227725431411920294833901798304659011582328440228296618492754, 12319093933825845906195612210823362436789866252839892395323597642449461144960813359448423496536622280247713676669361185330767001694340173433507185981408484)
:::
- **Mô tả:** Challenge này yêu cầu ta giải một hệ phương trình hai ẩn để tìm lại được hai nửa của Flag. Làm Challenge này thì nên thêm phép Modulo $p$ vào hàm `pow()`.
- Ta có hệ như sau:
$$
\left\{\begin{matrix}
key[0]^{key[1] \times key[3]} \times m[0] + key[1]^{key[0]} \times m[1]+key[3] \times key[0]^{key[2]} & = x\\
key[2]^7 \times m[0] - key[3] \times m[1] - key[1]^{key[2]} + key[1]^{key[3]}& = y \\
\end{matrix}\right.
$$
- Ta sẽ đặt các hằng số thành các giá trị $A,B,C,D,E,F$ để dễ dàng tính toán hơn:
```python!
A = pow(key[0],key[1]*key[3],p)
B = pow(key[1],key[0],p)
C = (key[3]*pow(key[0],key[2],p))%p
D = pow(key[2], 7, p)
E = key[3]
F = (- pow(key[1],key[2],p) + pow(key[1],key[3],p))%p
```
- Ta sẽ có được hệ sau:
$$
\left\{\begin{matrix}
A \times m[0]+B\times m[1]+C & = x \\
D\times m[0]-E\times m[1]+F & = y\\
\end{matrix}\right.
$$
- Hệ này giải cũng khá đơn giản, chuyển vế đổi dấu là xong:
- Cô lập $m[1]$ ta được:
$$m[1] = \frac{(y-F) \times A - D \times (x-C)}{-D \times B - E \times A}$$
- Sau khi có $m[1]$ thì thế vào phương trình dưới:
$$m[0] = \frac{y-F+E\times m[1]}{D}$$
- **Chú ý:** không tồn tại **phép chia** trong trường Modulo, để chia thì ta sẽ phải nhân nghịch đảo Modulo của số chia.
- **Script:**
```python!
from Crypto.Util.number import *
from sympy import *
p = ...
key = ...
x,y = ...
#các hằng
A = pow(key[0], key[1] * key[3], p)
B = pow(key[1], key[0], p)
C = (key[3] * pow(key[0], key[2], p)) % p
D = pow(key[2], 7, p)
E = key[3]
F = (- pow(key[1], key[2], p) + pow(key[1], key[3], p)) % p
#giải hệ
b = (((y - F) * A - D * (x - C) % p) * pow(-D * B - E * A, -1, p)) % p
a = (((y - F + E * b) % p) * pow(D, -1, p)) % p
print(long_to_bytes(a) + long_to_bytes(b))
```
- Hoặc nếu bạn lười cô lập nghiệm thì có thể sử dụng hàm `solve()` của sagemath để giải:
- **Script:**
```python
from sage.all import *
from Crypto.Util.number import long_to_bytes
p = ...
key = [...]
enc = (...)
F = GF(p)
x, y = var('x y')
eq1 = (pow(key[0],key[1]*key[3],p)*x + pow(key[1],key[0],p)*y + key[3]*pow(key[0],key[2],p) == enc[0])
eq2 = (pow(key[2],7,p)*x - key[3]*y - pow(key[1],key[2],p) + pow(key[1],key[3],p) == enc[1])
solutions = solve([eq1, eq2], x, y, solution_dict=True)
for sol in solutions:
nghiem_1 = int(F(sol[x]))
nghiem_2 = int(F(sol[y]))
print((long_to_bytes(nghiem_1) + long_to_bytes(nghiem_2)).decode())
```
- Chúng ta cũng có một cách giải hệ phương trình nữa đó là chuyển hệ thành **ma trận** rồi giải, cách này rất hiệu quả khi ta có hệ nhiều phương trình và cũng rất nhanh nữa:
$$
\begin{bmatrix}
A & B \\
D & -E\\
\end{bmatrix}
\times
\begin{bmatrix}
x \\
y \\
\end{bmatrix}
=
\begin{bmatrix}
x- C \\
y-F \\
\end{bmatrix}
$$
$$
\Leftrightarrow \begin{bmatrix}
x \\
y \\
\end{bmatrix}
=
\begin{bmatrix}
x- C \\
y-F \\
\end{bmatrix}
\times
{\begin{bmatrix}
A & B \\
D & -E\\
\end{bmatrix}}^{-1}
$$
- **Script:**
```python
from Crypto.Util.number import *
from sympy import Matrix
p =
key = [, , , ]
x,y = (, )
k0, k1, k2, k3 = key
A = Matrix([
[pow(k0, k1 * k3, p), pow(k1, k0, p)],
[pow(k2, 7, p), -k3 % p]
])
B = Matrix([
[(x - k3 * pow(k0, k2, p)) % p],
[(y + pow(k1, k2, p) - pow(k1, k3, p)) % p]
])
A_inv = A.inv_mod(p)
m = (A_inv * B) % p
m0, m1 = m[0], m[1]
print(long_to_bytes(m0) + long_to_bytes(m1))
```
- Còn trong sagemath thì ta sẽ sử dụng `.solve_right()`:
```python
from sage.all import *
from Crypto.Util.number import long_to_bytes
p =
key = [, , , ]
x,y = (, )
A = pow(key[0],key[1]*key[3],p)
B = pow(key[1],key[0],p)
C = (key[3]*pow(key[0],key[2],p))%p
D = pow(key[2], 7, p)
E = key[3]
F = (- pow(key[1],key[2],p) + pow(key[1],key[3],p))%p
Zmod_p = Zmod(p)
A = Matrix(Zmod_p, [[A, B], [D, -E % p]])
B = vector(Zmod_p, [(x-C) % p, (y-F) % p])
X = A.solve_right(B)
print(long_to_bytes(int(X[0])) + long_to_bytes(int(X[1])))
```
:::spoiler Flag
**KCSC{b4by_3qu4710n_l34rn1n6}**
:::
## Caesar Starter (easy)
- **Source Code:**
```python!
import random
from secret import flag
def generate_key():
return [random.randint(0, len(words)) for _ in range(4)]
def encrypted(key,flag) :
data = [printable.index(i) for i in flag]
encrypted = ''
for i in range(len(flag)) :
encrypted += words[(data[i] + key[i%4]) % 96]
return encrypted
words = r"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"
random.seed(random.randrange(0,2**20))
printable_characters = list(words)
printable = ''
for i in range(len(printable_characters)) :
chosen_char = random.choice(printable_characters)
if chosen_char != ' ' :
printable += chosen_char
printable_characters.remove(chosen_char)
key = generate_key()
ct = encrypted(key,flag)
print(ct)
# -}Pnr<U5bYw}p.UU5JM5S[Z[*nT]SY6~
```
- **Mô tả:** Challenge mã hóa bằng cách ánh xạ các ký tự của Flag qua lại giữa tập **words** và tập **printable**, thêm vào đó là thêm bước mã hóa **Caesar**. Nếu ta phân tích được từng bước biến đổi của nó thì Challenge này không khó.
- **Các bước** biến đổi của Challenge như sau:
- Đầu tiên nó tạo một bản xáo trộn của `words`, gọi là `printable`, mục đích là để ánh xạ `plaintext` vào đó.
- Sau đó Challenge tạo bộ khóa gồm $4$ giá trị, mục đích là để dịch các ký tự trong `plaintext` đi một khoảng bằng **key** (giống mã caesar).
- Sau khi dịch xong thì ánh xạ ngược lại `words`.
- **Ví dụ** như sau:
- `plaintext` là chữ `"a"`, key là `key = [43, 92, 1, 24]`, giả sử `printable` là:
```python!
printable = "7cbNo_HA@v\\4[p$Y:V\(<G53Z;R%-twIF1ixjfTUEX=&lQO})K>JM#k!,]u\B`|~WS^syn\"?PCLeqam/z9.+D'*{h6r2gd80"
```
- Vị trí của chữ `"a"` trong `printable` là $77$, sau đó Challenge cộng $77$ cho $43$ (giá trị đầu của key), được $120$, lấy `120 % 96 = 24`, $24$ chính là thứ tự của chữ `"o"` trong `words`.
- Vậy chữ `"a"` sau các phép biến đổi sẽ là chữ `"o"`.
- Vậy giờ làm ngược lại như thế nào?
- Bắt đầu với chữ `"o"`, ta ánh xạ chữ `"o"` vào bảng `words` được số $24$, sau đó ta làm ngược lại phép dịch ký tự bằng cách trừ $24$ đi cho $43$, được $-19$, `-19 % 96 = 77`, khi này $77$ sẽ là thứ tự của chữ `"a"` trong tập `printable`. Rất đơn giản phải không.
- **Chú ý:** Challenge sử dụng `seed()` để làm hạt giống cho các hàm random nên ta sẽ phải brute-force đúng `seed` mà đề đã dùng.
- **Script:**
```python!
import random
from tqdm import trange
ct = r"-}Pnr<U5bYw}p.UU5JM5S[Z[*nT]SY6~"
def generate_key():
return [random.randint(0, len(words)) for _ in range(4)]
def decrypted(key,ct) :
data = [words.index(i) for i in ct]
decrypted = ''
for i in range(len(ct)) :
decrypted += printable[(data[i] - key[i%4]) % 96]
return decrypted
words = r"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"
for i in trange(2**20):
random.seed(i)
printable_characters = list(words)
printable = ''
for i in range(len(printable_characters)) :
chosen_char = random.choice(printable_characters)
if chosen_char != ' ' :
printable += chosen_char
printable_characters.remove(chosen_char)
key = generate_key()
pt = decrypted(key, ct)
if "KCSC{" in pt:
print(pt)
```
:::info
:pencil: không nên thay đổi thứ tự của các hàm vì nó sẽ làm hỏng thuật toán **random**, nên bê nguyên từ source code qua, chỉ thay lại các biến và tham số thôi.
:::
:::spoiler Flag
seed = 66156
**KCSC{345y_c4354r_cu570m_r16h7_?}**
:::
## 43S (easy)
- **Source Code:**
```python!
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
import os
from pwn import xor
from secret import flag
def encrypt(key: bytes, msg: bytes) -> bytes:
iv = os.urandom(16)
plaintext = [msg[i:i + 16] for i in range(0, len(msg), 16)]
blocks = []
prev_ciphertext = iv
prev_plaintext = bytes(16)
for plaintext_block in plaintext:
c = AES.new(key, AES.MODE_ECB)
ciphertext_block = c.encrypt(xor(plaintext_block,prev_ciphertext, prev_plaintext))
blocks.append(ciphertext_block)
prev_ciphertext = ciphertext_block
prev_plaintext = plaintext_block
return iv + b''.join(blocks)
def decrypt(key: bytes, msg: bytes) -> bytes:
c = AES.new(key, AES.MODE_ECB)
return c.decrypt(msg[16:])
key = os.urandom(16)
ciphertext = encrypt(key, pad(flag, 16))
print(f'Here is my gift for you , good luck : {ciphertext.hex()}')
while True:
print("1. Encrypt")
print("2. Decrypt")
otp = int(input(">> "))
if otp == 1:
msg = bytes.fromhex(input("Enter your message: "))
ciphertext = encrypt(key, pad(msg, 16))
print(f'Ciphertext : {ciphertext.hex()}')
elif otp == 2:
msg = bytes.fromhex(input("Enter the ciphertext: "))
plaintext = decrypt(key, msg)
print(f'Plaintext : {plaintext.hex()}')
else:
exit()
```
- **Mô tả:** Challenge mã hóa **Flag** theo mode Propagating Cipher Block Chaining (**PCBC**) của AES và tạo ra kha khá lỗ hổng để ta khai thác. Hàm **Encrypt()** mã hóa theo kiểu **PCBC** nhưng hàm **decrypt()** lại giải mã theo kiểu **ECB**?
- Challenge cho ta **gift** là kết quả của Flag được mã hóa bằng mode **PCBC**, mà hàm `decrypt()` sử dụng mode **ECB** nên ta có thể dùng hàm `decrypt()` để giải mã **gift** ra **pre_encrypt** là đầu vào của thuật toán AES hay kết quả của phép tính **plaintext** $\oplus$ **prev ciphertext** $\oplus$ **prev plaintext**.
> Ta chỉ cần thực hiện phép **Xor** là có thể khôi phục toàn bộ Flag.
- Đầu tiên ta nhận **gift**:
```python!
gift = "538ef06164d7203acd2fbac58445a258a1669e658a8effe985db59111b09698b8c88117dcad0a217ae815619d83c22013f4b351e5be2d3f654a0bc82061317bd2924d1c6a7a2d223c36f56cbd5591d01"
```
- Tiếp theo ta giải mã **gift** bằng hàm **decrypt()** của Challenge, được **pre_encrypt**:
```python!
pe = "18cda3221fe21057fe70caf6b435ce6bb541fd48c6e4f8ec87ea427d1a0f5a89e6b3107e8dbfe748ab810a19d82422406976672c46e2c5f25fb38ddb317b4ecb"
```
- Ở khối thứ nhất (16 bytes đầu) thì **pre_encrypt (Pe)** được mã hóa bằng công thức:
$$Pe_1 = IV \oplus Flag_1 \oplus 0$$
$$\Rightarrow Flag_1 = Pe_1 \oplus IV$$
- Có $Pe_1$, có $IV$, ta khôi phục được $Flag_1$ như sau:
```python!
from pwn import xor
gift = bytes.fromhex("538ef06164d7203acd2fbac58445a258a1669e658a8effe985db59111b09698b8c88117dcad0a217ae815619d83c22013f4b351e5be2d3f654a0bc82061317bd2924d1c6a7a2d223c36f56cbd5591d01")
pe = bytes.fromhex("18cda3221fe21057fe70caf6b435ce6bb541fd48c6e4f8ec87ea427d1a0f5a89e6b3107e8dbfe748ab810a19d82422406976672c46e2c5f25fb38ddb317b4ecb")
f1 = xor(gift[:16], pe[:16]) #iv sẽ là 16 bytes đầu của gift
print(f1)
#KCSC{50m3_p30pl3
```
$\Rightarrow$ Vậy là có được $16$ bytes đầu tiên của Flag.
- Ở khối thứ hai, **pre_encrypt** được mã hóa như sau:
$$Pe_2 = Flag_1 \oplus Gift_1 \oplus Flag_2$$
$$\Rightarrow Flag_2 = Pe_2 \oplus Flag_1 \oplus Gift_1$$
- Khôi phục $Flag_2$:
```python!
from pwn import xor
gift = bytes.fromhex("538ef06164d7203acd2fbac58445a258a1669e658a8effe985db59111b09698b8c88117dcad0a217ae815619d83c22013f4b351e5be2d3f654a0bc82061317bd2924d1c6a7a2d223c36f56cbd5591d01")
pe = bytes.fromhex("18cda3221fe21057fe70caf6b435ce6bb541fd48c6e4f8ec87ea427d1a0f5a89e6b3107e8dbfe748ab810a19d82422406976672c46e2c5f25fb38ddb317b4ecb")
f1 = xor(gift[:16], pe[:16])
f2 = xor(gift[16:32], f1, pe[16:32])
print(f1+f2)
#KCSC{50m3_p30pl3_d0n7_7h1nk_1v_1
```
> Làm tương tự với những khối còn lại, ta sẽ được Flag hoàn chỉnh.
- **Script:**
```python!
from pwn import xor
from Crypto.Util.Padding import unpad
gift = bytes.fromhex("538ef06164d7203acd2fbac58445a258a1669e658a8effe985db59111b09698b8c88117dcad0a217ae815619d83c22013f4b351e5be2d3f654a0bc82061317bd2924d1c6a7a2d223c36f56cbd5591d01")
pe = bytes.fromhex("18cda3221fe21057fe70caf6b435ce6bb541fd48c6e4f8ec87ea427d1a0f5a89e6b3107e8dbfe748ab810a19d82422406976672c46e2c5f25fb38ddb317b4ecb")
f1 = xor(gift[:16], pe[:16])
f2 = xor(gift[16:32], f1, pe[16:32])
f3 = xor(gift[32:48], f2, pe[32:48])
f4 = xor(gift[48:64], f3, pe[48:64])
print(unpad(f1+f2+f3+f4, 16).decode())
```
:::spoiler Flag
**KCSC{50m3_p30pl3_d0n7_7h1nk_1v_15_1mp0r74n7_1n_pcbc_m0d3?}**
:::
## Heoman (medium)
- **Source Code:**
```python!
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha256
from random import randint
from secret import flag
# Params
p = getPrime(512)
a = randint(2**33,2**35)
g = 2050493
# Exchange
gA = pow(g,a,p)
r = randint(0,p-1)
B = pow(r,(p-1)//g,p)
gB = pow(B,a,p)
# Encrypt
key = sha256(str(gB).encode()).digest()[:16]
cipher = AES.new(key,AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(flag,16))
# Print
print(f'{ciphertext = }')
print(f'{p = }')
print(f'{B = }')
```
:::spoiler output
ciphertext = b'\xe6\xcb\xc6\x1d\xb19\xa4\xb8)V\x95u\xf8\x1b\x139 PI8\xa3\xcb\xb3\x85\x1ap\xbai.\xea\x1d\xab\x9a\x90\x82\x1a3\x91_;\xa5\x0e \x05\xf7\xf58%'
p = 12373179506263461354514623365077132800661338897023082048202681278072369025695953393083636918398048660173612137128780210954723129668855320275665251703736793
B = 12000841720785201162570293150131106089496068719117766176856306894850593806350814073092246930470170348368143014207968119599751108320780548445547875340920785
:::
- Challenge này sử dụng giao thức **Diffie-Hellman** để trao đổi khóa bí mật giữa hai bên, giá trị $g_B$ sẽ được băm ra bằng **sha256** để làm khóa bí mật cho thuật toán **AES**.
- Khi mình thử factor $p-1$ thì $g$ là một trong số các ước của nó ($2050493$), điều này chưa giúp ích nhưng mình sẽ chú ý đến $g$ nhiều hơn.
```python!
p-1 = 2^3 * 3^2 * 2050493 * 83808974409944484858266221864944544235224697568822351829282852668929760805598901453100661634909592881197162348604702834843479170272542859717592927
```
- Vì được mã hóa bằng **AES** nên mục tiêu của ta là tìm lại được $g_B$ thì mới có thể giải mã được, ta sẽ chú ý vào công thức của $g_B$:
$$g_B \equiv B^a \pmod p$$
- Nhưng $g_B$ được tính khá kỳ lạ, thay vì được tính như $g_A$ thì nó chọn giá trị $B$ làm cơ số và được tính bằng công thức:
$$B \equiv r^{(p-1) / g} \pmod p$$
- Từ công thức trên, ta mũ hai vế cho $g$:
$$B^g \equiv r^{p-1} \pmod p$$
$$\Leftrightarrow B^g \equiv 1 \pmod p$$
- Ta thấy $B^g$ đồng dư với $1$ trong modulo $p$, mà $g$ | $(p-1)$, suy ra $B$ là một phần tử thuộc nhóm con có **bậc** là $g$. Tức nếu ta dùng số $B$ để làm cơ số cho phép mũ thì số lượng phần tử nó có thể tạo ra là $g$ phần tử mà thôi.
- Điều này cực kỳ nghiêm trọng vì khi kẻ tấn công biết được bậc của $B$ là một số nhỏ thì thay vì đi giải bài toán Logarit rời rạc để tìm $a$ thì giờ chúng chỉ cần **brute-force** $a$ trong khoảng $(0, g)$ mà thôi. Đây được gọi là kiểu tấn công **Small subgroup attack on Diffie-Hellman**.
- Từ lỗi trên thì phạm vi của $a$ đã được thu nhỏ từ $(2^{33}, 2^{35})$ xuống chỉ còn $(0, 2050493)$, ta hoàn toàn có thể brute force được!
- **Script:**
```python
from Crypto.Cipher import AES
from hashlib import sha256
from tqdm import trange
ciphertext =
p =
B =
g = 2050493
for a in trange(g):
gB = pow(B,a,p)
key = sha256(str(gB).encode()).digest()[:16]
cipher = AES.new(key,AES.MODE_ECB)
plaintext = cipher.decrypt(ciphertext)
if b'KCSC{' in plaintext:
print(f"{a = }")
print(plaintext)
break
```
:::spoiler Flag
a = 861875
**KCSC{5m4ll_5ub_6r0up_4774ck_1n_p0hl16_h3llm4n}**
:::
## Sign (medium)
- **Source Code:**
```python!
from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from os import *
from random import randint
from pwn import xor
from base64 import b64decode
flag = "KCSC{???????????????}"
secret = urandom(16)
G = generator_256
p = G.order()
def genKeyPair():
d = randint(1,p-1)
pubkey = Public_key(G, d*G)
privkey = Private_key(pubkey, d)
return pubkey, privkey
def ecdsa_sign(msg, nonce,privkey):
hsh = sha256(b64decode(msg)).digest()
nonce = sha256(xor(b64decode(nonce),secret)).digest()
sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}
def challenge() :
pubkey , privkey = genKeyPair()
print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
print("1 : Sign msg ")
print("2 : Submit private key")
nonces = []
for _ in range(3) :
try :
option = int(input("Option : "))
if option == 1 :
msg = (input("Enter your message: ")).encode()
nonce = (input("Enter your nonce: ")).encode()
if nonce in nonces :
print('Nope')
exit()
if len(nonces) > 0 :
for i in nonces :
if nonce in i or i in nonce:
print('Nope')
exit()
nonces.append(nonce)
print(ecdsa_sign(msg,nonce,privkey))
if option == 2 :
d = int(input("Private key : "))
print(nonces)
if d == int(privkey.secret_multiplier) :
print(f'Very nice , here is your flag : {flag}')
exit()
else :
print(f'Wrong key , correct is {privkey.secret_multiplier}')
exit()
except :
print("Not legal option")
exit()
print("Out of attemps !! ")
challenge()
```
- **Mô tả:** Một Challenge liên quan đến Elliptic Curve Digital Signature Algorithm (**ECDSA**). Nó cho ta hai lựa chọn là **Ký tin nhắn** và **Gửi khóa bí mật**, nếu ta gửi đúng giá trị của khóa bí mật thì Challenge sẽ trả về **Flag**. Ta sẽ lợi dụng điểm yếu của phần ký tin nhắn để từ đó tìm ra được khóa bí mật.
- Giới thiệu sơ qua về **ECDSA**, thì ecdsa là thuật toán dùng để tính cặp khóa $(r,s)$, mục đích là để người nhận có thể xác thực tin nhắn $M$ được gửi qua có chính xác không? có được chỉnh sửa trong lúc gửi đi không? Thuật toán như sau:
- Đầu tiên tạo một giá trị $k$ (có thể gọi là nonce) ngẫu nhiên (khác với khóa bí mật $d$), mục đích là tính $P = k \times G$ với $G$ là điểm sinh của đường cong. giá trị $x_P$ sẽ là $r$, sau khi có $r$ thì tiếp tục tìm $s$ bằng công thức:
$$s \equiv k^{-1} \times (z + d_A \times r)\mod(p) $$
- Với $z$ là giá trị băm của $M$, $d_A$ là khóa bí mật của người gửi.
- Người nhận sau khi có $r$ và $s$ và tin nhắn $M$ sẽ tiến hành xác thực bằng công thức:
$$P \equiv s^{-1} \times z \times G + s^{-1} \times r \times Q_A \mod(p)$$
- Với $z$ là giá trị băm của $M$, $Q_A$ là khóa công khai mà người kia gửi từ trước.
- Nếu $x_p = r$ thì tin nhắn và các giá trị $(r,s)$ chưa bị thay đổi trong quá trình gửi đi.
- Ở source code ta chú ý vào hàm **ecdsa_sign()** là hàm được sử dụng để ký. Giá trị $k$ được tính bằng công thức `nonce = sha256(xor(b64decode(nonce),secret)).digest()`. $k$ được tính nhờ vào **nonce** mà ta nhập thủ công vào nên challenge sẽ có đoạn code để kiểm tra `nonce` mà ta nhập vào có trùng với `nonce` nhập từ trước không, nếu có thì thoát chương trình ngay lập tức.
- Mục đích của việc kiểm tra `nonce` đã được dùng hay chưa là để tránh bị tấn công **ECDSA Nonce Reuse Attack**, kiểu tấn công này hoạt động khi `nonce` ($k$) được sử dụng lại nhiều lần giống nhau, khiến cho giá trị $r$ của chữ ký không đổi, vì $r = x_P = k \times G$ mà. Khi giống $r$ mà khác $s$ thì dẫn đến điều sau:
$$s_1 = k^{-1} \times (z_1 + r \times d)$$
$$s_2 = k^{-1} \times (z_2 + r \times d)$$
- Ta lấy $s_1 - s_2$ là triệt tiêu được $r\times d$:
$$s_1-s_2 = k^{-1} \times (z_1-z_2)$$
- Từ đó ta tính được $k$:
$$k = \frac{z_1-z_2}{s_1-s_2}$$
- Có $k$ thì ta có thể tính được $d$ rồi, bài toán kết thúc:
$$d = \frac{s_1 \times k - z_1}{r}$$
- Quay trở lại Challenge thì ta thấy rằng Challenge kiểm tra `nonce` không kỹ, nó chỉ kiểm tra giá trị **Base64** của `nonce` mà thôi, ta hoàn toàn có thể qua mặt được. **Ví dụ:** `AA==` và `AAA=` là khác nhau, nhưng chúng đều có giá trị là $0$.
- Ta sẽ gửi `nonce = 0` vì $nonce \oplus secret = 0 \oplus secret = secret$, mà `secret` không thay đổi, dẫn đến $r$ của mỗi lần ký là giống nhau. Vậy là đủ để ta tấn công rồi.
- **Script:**
```python!
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from ecdsa.ecdsa import generator_256
from base64 import b64decode
from json import loads
from pwn import process
# vì server của bài bị gỡ rồi nên mình sẽ chạy bằng local host (phải chạy bằng wsl), file test.py là source code
io = process(["python3", "test.py"])
G = generator_256
p = G.order()
msg1 = b"AA=="
nonce1 = b'AA=='
msg2 = b'QUFB'
nonce2 = b'AAA='
io.sendlineafter(b"Option : ", b"1")
io.sendlineafter(b"Enter your message: ", msg1)
io.sendlineafter(b"Enter your nonce: ", nonce1)
io.recvuntil(b"\n\x1b[J")
a = io.recvline().decode()
a = a.replace("b'", '"').replace("'", '"')
a = loads(a)
io.sendlineafter(b"Option : ", b"1")
io.sendlineafter(b"Enter your message: ", msg2)
io.sendlineafter(b"Enter your nonce: ", nonce2)
io.recvuntil(b"\n\x1b[J")
b = io.recvline().decode()
b = b.replace("b'", '"').replace("'", '"')
b = loads(b)
s1 = int(a["s"], 16)
s2 = int(b["s"], 16)
r = int(a["r"], 16)
h1 = bytes_to_long(sha256(b64decode(msg1)).digest())
h2 = bytes_to_long(sha256(b64decode(msg2)).digest())
k = ((h1 - h2) * pow(s1 - s2, -1, p)) % p
d = ((s1 * k - h1) * pow(r, -1, p)) % p
io.sendlineafter(b"Option : ", b'2')
io.sendlineafter(b"Private key : ", str(d).encode())
io.recvuntil(b'Very nice , here is your flag : ')
flag = io.recvuntil(b"\n", drop = True)
print(flag)
```
:::spoiler Flag
**KCSC{https://youtu.be/IzSYlr3VI1A}**
:::
## Adult RSA (hard)
- **Source Code:**
```python!
from Crypto.Util.number import *
import random
from secret import flag
def gen_prime_rsa_p(nbits,e):
while True:
p = getPrime(nbits)
if (p-1) % e == 0 and (p-1) % e**2 != 0:
return p
def gen_prime_rsa_q_z(nbits,e):
while True:
q = getPrime(nbits)
if (q-1) % e != 0:
return q
e = 71
nbits = 64
p = gen_prime_rsa_p(256,e)
q = gen_prime_rsa_q_z(256,e)
z = gen_prime_rsa_q_z(256,e)
N = p * q * z
cipher = pow(bytes_to_long(flag), e, N)
x_random = []
x_result = []
for i in range(16):
x = random.getrandbits(nbits)
x_random.append(x)
r = (q * x + z) % p + random.randint(-2**32 + 1, 2**32)
x_result.append(r)
a = (q-1)*(z-1)
d = inverse(e,a)
print(long_to_bytes(pow(cipher,d,q*z)))
print(f'{x_random = }')
print(f'{x_result = }')
print(f"n = {N}")
print(f"p = {p}")
print(f"e = {e}")
print(f"C = {cipher}")
```
:::spoiler output
x_random = [8643291332705198277, 17174614327362281726, 15517127706104132406, 9995477138511354306, 13056359184422157742, 7587016065185392284, 9920196087957288832, 4952856612988664544, 5400203381242752352, 16576729197299286985, 3973228161970229092, 1766627902400563838, 11348902064522144204, 16275357069408139519, 13702106965727543557, 4703399577523548417]
x_result = [104769762949973515003186398069307441812047659769870223704600152813608642465924, 19240036943626126268867100328802805554153842788101708322529920247684682326111, 12872167480066142198055220003342391658416424740122512375229591959608296202631, 45245681900612751628524950620689624320206486801875865224835291789607248539141, 89174302840170283311531755935367036323146884100751346415988392131733295994022, 93558762831267599991524549218850060166785794865518267150157882124236756776229, 35334857205000198530989566036180247858527073565848690385874491796896655487832, 48582907639890216074557704293111289752104462411913600690382605831588458449292, 2016756199999958140783087348943917358308350962876495006453605085056481261346, 27769515582048691173698542555157381741265320283349469274846441026970926086274, 2509804360455560909035722789851300261852699570010154269398229008039953894020, 52048088979121750160075716905451109678634402978216783809835560945560954214895, 98161921782416668850151589231441352837262317193409143953232303925375964152202, 103908881452290364956007856502624631194187804940528712150623661515672853059255, 2441158614263009247426256779029825410595899337637342611525937734371617282258, 2459264866325694410614372765423053147832404738353976083506075134734276029099]
n = 609105711554562987480385746218512529022252330552247630394781811768956681666381155442184196776297236078736773335862755588901545589600370539269710342801857148190223818733295279783258645163683394386497845747001139631409101743225988501
p = 106426942433971470657898579372762947809790292384453810719107482848817482215411
e = 71
C = 110684508716853838208041576724352556783516725281742611028522115035500008314350404208335808630949265486412535388862401924455351546168798205658188240618862927337867580712334009503358702013924669467798852160329991510793706397540234731
:::
- **Mô tả:** Một Challenge RSA liên quan đến [**HNP**](https://hackmd.io/@at20n0118/Hy5LBsS51l#Hidden-Number-Problem) (mình nghĩ vậy). Challenge sử dụng modulus $n = p.q.z$, để giải mã `ciphertext` thì ta cần tìm được $q,z$ vì challenge đã cho $p$, thêm vào đó challenge cho ta thêm $16$ phương trình chứa $q$, ta sẽ tìm cách khai thác chúng và khôi phục lại $q$ và giải mã `Flag`
- Ta có $16$ phương trình dạng:
$$r_i = (q.x_i + z \mod p) + y_i$$
> Trong đó $q$ là một số nguyên tố của modulus $n$ (ta cần tìm $q$), $x_i$ là các số ngẫu nhiên `64 bit` (đã biết), $z$ là số nguyên tố của modulus $n$ (nếu biết $q$ thì ta sẽ biết được $z$) và cuối cùng $y_i$ là các số ngẫu nhiên trong đoạn $[-2^{32}, 2^{32}]$.
- Ta biến đổi phương trình trên như sau:
$$r_{i+1} - r_i = (x_{i+1} - x_i).q + (y_{i+1} - y_i) + k.p$$
$$\Leftrightarrow (y_{i+1} - y_i) + (x_{i+1} - x_i).q - (r_{i+1} - r_i) + k.p = 0 \hspace{5mm} (*)$$
- Đặt $(y_{i+1} - y_i)$ là $\beta_i$ (vì chưa biết) với bound $\beta_i = 2^{32}$ ta có được một phương trình **HNP** dạng:
$$\beta_i + (x_{i+1} - x_i).q - (r_{i+1} - r_i) + k.p = 0$$
- Làm tương tự với các phương trình còn lại, ta sẽ thu được $8$ phương trình như trên, lập ma trận HNP là tính được $\beta_i$, có $\beta_i$ là tính được $q$, kết thúc bài toán
:::spoiler **solve.sage**
```python=
from Crypto.Util.number import *
x =
r =
n =
p =
e = 71
C =
assert len(x) == len(r) == 16
xx = [x[i] - x[i+1] for i in range(0, len(x), 2)]
rr = [r[i] - r[i+1] for i in range(0, len(r), 2)]
B = 2**32
index = 8
P = diagonal_matrix(index, [p]*index)
M = P.stack(Matrix(QQ, xx))
M = M.stack(-Matrix(QQ, rr))
M = M.augment(vector(QQ, [0]*index + [B/p] + [0]))
M = M.augment(vector(QQ, [0]*(index + 1) + [B])).dense_matrix()
M = M.LLL()
for i in M:
if int(i[-1]) == B:
beta = i[:-2]
beta = [int(-1*i) for i in beta]
break
if int(i[-1]) == -B:
beta = i[:-2]
beta = [int(i) for i in beta]
break
q = ((rr[0] - beta[0]) * pow(xx[0], -1, p)) % p
while True:
if isPrime(q):
break
else:
q = q + p
assert isPrime(q)
z = n//(q*p)
while True:
if isPrime(z):
break
else:
z = z + p
assert isPrime(z)
print(f"{q = }")
print(f"{z = }")
a = (q-1)*(z-1)
d = inverse(e,a)
print(long_to_bytes(pow(C,d,q*z)))
```
:::spoiler **Flag**
**KCSC{U_Should_Choose_e_reasonable}**
:::
# KCSC TTV CRYPTO MN 2023 (10/10)
## Ez_Ceasar (easy)
- **Source code:**
```python
import string
import random
alphabet = string.ascii_letters + string.digits + "!{_}?"
flag = 'KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}'
assert all(i in alphabet for i in flag)
key = random.randint(0, 2**256)
ct = ""
for i in flag:
ct += (alphabet[(alphabet.index(i) + key) % len(alphabet)])
print(f"{ct=}")
# ct='ldtdMdEQ8F7NC8Nd1F88CSF1NF3TNdBB1O'
```
- **Mô tả:** Challenge thực hiện mã hóa **Caesar** bằng cách dịch một ký tự trong $Flag$ qua bên phải **key** lần, để giải bài này thì ta đi tìm key rồi dịch ngược lại qua bên trái thôi.
- Dù **key** thuộc khoảng $(0, 2^{256})$ nhưng mà ta có phép `% len(alphabet)` nên giá trị của nó không lớn hơn chiều dài của `alphabet` được đâu, hoàn toàn có thể brute force được.
- **Script:**
```python
import string
alphabet = string.ascii_letters + string.digits + "!{_}?"
ct = 'ldtdMdEQ8F7NC8Nd1F88CSF1NF3TNdBB1O'
for key in range(len(alphabet)):
pt = ""
for i in ct:
pt += (alphabet[(alphabet.index(i) - key) % len(alphabet)])
if "KCSC{" in pt:
print(f"{pt = }")
print(f"{key = }")
```
:::spoiler Flag
key = 42
**KCSC{C3as4r_1s_Cl4ss1c4l_4nd_C00l}**
:::
## Is_it_CRT (easy)
- **output.txt**
```python
e = 65537
n1 = 130970791706695167120816954281347910242271741380848697030582097380414164464669582077501935100534315672736591163867589462360532537474343007717114862677036219839049659638193590918904482709879798794387701429067711189339541090962315499562919351155480834958649104605830303759610881412035697138279914413112238740763
n2 = 113641455496435721193134074028475386176456392079379291332104843107150260592574545964197594045447402797691233409140148854647138554130435281685396694982224051757694663968334285795059648876331981127831706285859528658283228869511829743448319293252496057080243050538084390601445944010478822202867577802474801791329
n3 = 115457592377723871442877828120043009812666552225344030925643785294781982752845765738712585283013530383946783306354281324295808919863405271857497036597560796067884303380890822753721631162428079111639955037289448237030785776123607750456878915823785099809072723104652279115157324089611136858768836165863398680203
c1 = 30205641158783357163061598073735588730679950235840534382941497051587980282400902972347912576505274818761099007699493094299366801627409654097234796805851040864489706974546874446811476122681874102134051059499515262761274274546668369933320015216502163383548510236101225370599258753560708068722034210162626804923
c2 = 7340742323302407330422449647684226850070712253152501455033801379382023949033438352721378237409230914162113993246249149771113074063922424514756305027050874444877721126264284642454264098887344586634403180691682203341368972229942120849177826057673408055065848316876227141406653440730644459969340909926030700535
c3 = 55645356229576991726290820253166125559920178689701167851283019943562627606690176220109383257847017836775793827103662981412236830329482802454580242635314923411008056558210411063545158619407523528841487658337051518783958350562281456553772083003206890498586599056920249966475452673566793925144997181076187273153
```
- Khi nhìn vào output như thế này thì mình nghĩ ngay đây là kiểu tấn công **Hastad’s Broadcast Attack** bởi vì nhìn nó rất giống **ciphertext** được mã hóa từ chung một $e$ và sử dụng khác $n$, ta chỉ cần tính **CRT** của chúng rồi lấy căn bậc $e$ là xong.
- Ta có điều kiện của **CRT** là $GCD(N_i, N_j) = 1$ với $i \neq j$.
- Nhưng khi tính $GCD(n_1, n_2)$ thì nó cho ra kết quả $\neq 1$ nên đó chắc chắn là giá trị $p$ hoặc $q$ của $n_1$ và $n_2$. Có được $p$ rồi thì ta lấy $n \div p$ là có được $q$, bài toán kết thúc:
```python
from Crypto.Util.number import long_to_bytes, GCD
e = 65537
n1 =
n2 =
c1 =
p = GCD(n1,n2)
q = n1 // p
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c1, d, n1)))
```
:::spoiler Flag
**KCSC{N0t_Rea11y_4_CR1_4tt4ck_R1ght??!!??}**
:::
## A3S_C1R (easy)
- **Source code:**
```python
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto import Random
flag = b'KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}'
nonce = Random.get_random_bytes(8)
countf = Counter.new(64, nonce)
key = Random.get_random_bytes(32)
encrypto = AES.new(key, AES.MODE_CTR, counter=countf)
encrypted = encrypto.encrypt(b"TODO:\n - ADD HARDER CHALLENGE IN CRYPTO\n - ADD FLAG TO THE CHALLENGE\n")
encrypto = AES.new(key, AES.MODE_CTR, counter=countf)
encrypted2 = encrypto.encrypt(flag)
print(f"encrypted: {encrypted.hex()}")
print(f"encrypted2: {encrypted2.hex()}")
# encrypted: 5e07dfa19e2b256c205df16b349c0863a15839d056ada1fb425449f2f9af9563eccca6d15cb01aabbe338c851f7b163982127033787fff49e74e3e09f0aee048a1d5b29f5a
# encrypted2: 410bc8addf6036125f5fe17d4bb61c00ba565a9e71d1bf846f625eeac5bfa972f9e7c4fd60800ac9aa689f9b280f5a09fd3768674401ac60
```
- **Mô tả:** Challenge này sử dụng mode **CTR** của AES để mã hóa $Flag$ nhưng mà lại tạo ra một lỗ hổng vô cùng nghiêm trọng để ta có thể khai thác.
- Ta thấy rằng đầu vào của thuật toán **AES** là **Nonce+Counter**, $Flag$ của ta sẽ được **xor** với output của AES (**keystream**) để cho ra **ciphertext**, vì thế nếu ta biết được `keystream` thì ta sẽ **xor** nó với ciphertext là có **Flag** rồi. Ta đã có `ciphertext`, làm sao để có được `keystream` nhỉ?
- Ta chú ý vào đoạn:
```python
encrypto = AES.new(key, AES.MODE_CTR, counter=countf)
encrypted = encrypto.encrypt(b"TODO:\n - ADD HARDER CHALLENGE IN CRYPTO\n - ADD FLAG TO THE CHALLENGE\n")
```
- Ta thấy rằng nó thực hiện mã hóa **CTR** đoạn **"TODO:\n..."** nhưng lại sử dụng chung bộ đếm (**counter**) với $Flag$ của chúng ta.
```python!
encrypto = AES.new(key, AES.MODE_CTR, counter=countf) #counter của cả hai là counterf nên đầu vào của AES sẽ giống nhau
encrypted2 = encrypto.encrypt(flag)
```
- Nghĩa là đầu vào của cả hai là giống nhau (đều là **counterf**) nên `keystream` của cả hai sẽ giống nhau, vì vậy ta sẽ **xor** đoạn **"TODO:\n..."** với `ciphertext` của nó là có được `keystream`, sau đó lấy `keystream` đó **xor** với `ciphertext` của `Flag` là có được $Flag$.
- **Script:**
```python
from pwn import xor
encrypted = bytes.fromhex("5e07dfa19e2b256c205df16b349c0863a15839d056ada1fb425449f2f9af9563eccca6d15cb01aabbe338c851f7b163982127033787fff49e74e3e09f0aee048a1d5b29f5a")
encrypted2 = bytes.fromhex("410bc8addf6036125f5fe17d4bb61c00ba565a9e71d1bf846f625eeac5bfa972f9e7c4fd60800ac9aa689f9b280f5a09fd3768674401ac60")
todo = b"TODO:\n - ADD HARDER CHALLENGE IN CRYPTO\n - ADD FLAG TO THE CHALLENGE\n"
Counterf = xor(todo[:len(encrypted2)], encrypted[:len(encrypted2)])
print(xor(Counterf, encrypted2))
```
:::spoiler Flag
**KCSC{A3S_CTR_bU1_K1nd4_3asY_y0u_5h0uld_h4v3_s0lv3d_th1s}**
:::
## r54 (medium)
- **Source code:**
```python
from Crypto.Util.number import *
import hashlib
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)
e = 65537
flag = b'KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}'
m = len(flag)
if m%2:
flag+= bytes(0x01)
def dbytes2int(b):
return b[0]*256+b[1]
ciphertxt = b''
for i in range(0, len(flag), 2):
plt = dbytes2int(flag[i:i+2])
c = pow(plt,e,n)
# print(c)
h = hashlib.sha256(long_to_bytes(c)).hexdigest()
k = bytes.fromhex(h[:8])
# print(h)
ciphertxt += k
# print(ciphertxt)
with open("./Chall_med_4/enc_msg.bin", "wb") as f:
f.write(ciphertxt)
# n = 20675528040670526996752940893288629654073674678976458593562885254372323957903532876778575683971980608430988271483012687068546409103618011471627912308716870404710200387846081948584012645579489130659361868569525868828863142513688732813453572263121568340255562594977295513766156580889393986895191199436845252360294885224181350174035317346113446210888214332389015986819447524673296950196284975878585211748477505072532061859389809017849787533731620947172314201145532242513117285325664785809436379731158841381092296256976553945301076520532403729003821419792192809111636400447743715443579056636708987896016462504011033448823
```
:::spoiler enc_msg_fixed.bin
**eca4b94be6b9267d4d0d4f39adfdfe16bc4eb09b88f2aca8f1898f818f41545cac4924615d82f3d7ff6ea1c0c91106e5683f5d71**
:::
- Challenge này thực hiện mã hóa **RSA** từng cụm hai chữ của $Flag$ rồi **băm** ra. Vì có bước băm nên ta không thể làm ngược lại nên ý tưởng của ta là thực hiện **brute force** từng cụm hai chữ của **Flag**, nếu nó mã hóa ra giống giá trị băm thì lụm.
- Chỉ brute force **hai** chữ cái thôi nên quá trình trên sẽ diễn ra khá nhanh, ta sẽ so sánh giá trị băm của **RSA** xem nó có giống với giá trị băm của file `enc_msg_fixed.bin` không.
- **Script:**
```python
import string
import hashlib
from Crypto.Util.number import long_to_bytes
#ct = open("enc_msg_fixed.bin", "rb").read()
ct = bytes.fromhex("eca4b94be6b9267d4d0d4f39adfdfe16bc4eb09b88f2aca8f1898f818f41545cac4924615d82f3d7ff6ea1c0c91106e5683f5d71")
alphabet = string.printable[:-5]
n =
e = 0x10001
def dbytes2int(b):
return b[0]*256+b[1]
flag = ""
for r in range(0, len(ct), 4):
for i in alphabet:
for j in alphabet:
plt = dbytes2int((i+j).encode())
c = pow(plt,e,n)
h = hashlib.sha256(long_to_bytes(c)).hexdigest()
k = bytes.fromhex(h[:8])
if k == ct[r:r+4]:
print(i+j)
flag += (i+j)
print(f"{flag = }")
```
:::spoiler Flag
`KCSC{r54_!5_51Mp|3_r1gH+?}`
:::
## Ceasar_but_Harder!!!! (medium)
- **Source code:**
```python
import string
import random
flag = "KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}"
alphabet = string.ascii_letters + string.digits + "!{_}?"
assert all(i in alphabet for i in flag)
for i in range(3):
k = random.randint(0, len(alphabet))
alphabet = alphabet[:k] + alphabet[k+1:]
key = random.randint(0, 2**512)
ct = ""
for i in flag:
ct += (alphabet[(alphabet.index(i) + key) % len(alphabet)])
print(f"{ct=}")
# ct='2V9VnRcNosvgMo4RoVfThg8osNjo0G}mmqmp'
```
- **Mô tả:** Challenge này khá giống challenge **Ez_Ceasar** mà ta gặp lúc nãy nhưng mà tăng độ khó lên bằng cách bỏ ngẫu nhiên $3$ ký tự trong bảng chữ cái trước khi mã hóa, điều đó khiến **index** các từ bị thay đổi dẫn đến phép dịch sang phải cũng thay đổi.
- Bài này sẽ có nhiều hướng giải, nhưng mình sẽ theo hướng thử tất cả các tổ hợp $3$ chữ bị bỏ trong bảng chữ cái, tổ hợp nào mà cho ra $Flag$ thì lụm, **Alphabet** có $67$ chữ nên tổ hợp chập $3$ của $67$ là $47905$, ta hoàn toàn có thể brute force được hết.
- Sử dụng hàm `combinations` của thư viện **itertools** để tạo ra các tổ hợp.
- **Script:**
```python
import string
from itertools import combinations
alphabet = string.ascii_letters + string.digits + "!{_}?"
ct= '2V9VnRcNosvgMo4RoVfThg8osNjo0G}mmqmp'
C = combinations(alphabet,3)
for char in C:
rm_alphabet = alphabet
for j in char:
rm_alphabet = rm_alphabet.replace(j, "")
try:
for key in range(67):
pt = ""
for k in ct:
pt += (rm_alphabet[(rm_alphabet.index(k) - key) % len(rm_alphabet)])
if pt.startswith("KCSC{") and pt.endswith("}"):
print(pt)
except:
continue
```
- Bởi vì chỉ cần có từ **"KCSC{"** và **"}"** thì in ra nên nó sẽ in ra rất nhiều trường hợp, ta sẽ chọn cái nào mà có ý nghĩa nhất làm **Flag**:
:::spoiler Flag
**KCSC{y0u_be4t_My_C3A54R_bu7_HoW!!?!}**
:::
## Basic Math (medium)
- **Source code:**
```python
from Crypto.Util.number import getPrime
flag = b'KCSC{fake_flag}'
def verify(g, p, y, x, k, h):
return (y*x*pow(g, k, p)) % p == pow(g, h, p)
p = getPrime(256)
g = getPrime(128)
y = 65537
lst_x = []
lst_h = []
print(f"p = {p}")
print(f"g = {g}")
print(f"y = {y}")
try:
for i in range(20):
x = 0
h = 0
x = int(input("x = "))
h = int(input("h = "))
if x in lst_x or h in lst_h:
print('get out !!!')
exit(-1)
rs = verify(g, p, y, x, i, h)
if rs:
lst_x.append(x)
lst_h.append(h)
else:
print('get out !!!')
exit(-1)
print(flag)
except:
print("something went wrong")
```
- Challenge yêu cầu ta gửi đi **hai** giá trị là $x$ và $h$ $20$ lần sao cho nó thỏa mãn $20$ phương trình:
$$y \times x \times g^k \equiv g^h \pmod p$$
- Với $k$ chạy từ $0\rightarrow19$
- Ý tưởng của ta là gửi đi $x = y^{-1}$, khi này $x$ và $y$ sẽ triệt tiêu cho nhau, chỉ còn:
$$g^k \equiv g^h \pmod p$$
- Sau đó ta cho $h$ chạy từ $0\rightarrow19$ mỗi lần lặp là ok :smile:
- Nhưng Challenge không cho ta gửi các giá trị giống giá trị trước đó, ví dụ ở lần đầu nếu ta gửi $x=1$ thì lần lặp sau không được gửi $x=1$ nữa, ta có $h$ thay đổi liên tục từ $0 \rightarrow 19$ nên nó không vi phạm nhưng còn $x=y^{-1}$ nên ta phải tìm cách thay đổi $x$ sao cho mỗi lần lặp nó khác nhau nhưng phải triệt tiêu được $y$.
- Ta biến đổi $x$ như sau:
$$x \equiv y^{-1} \pmod p$$
$$\Leftrightarrow x = y^{-1} + i\times p$$
- Với mỗi lần lặp ta cho $i$ khác nhau khiến cho $x$ cũng thay đổi theo nhưng $x\times y \mod p$ vẫn sẽ là $1$.
- **Script:**
```python
from pwn import process
# chạy local vì server bị xóa lâu rồi, test.py là source code
io = process(["python3", "test.py"])
def verify(g, p, y, x, k, h):
return (y*x*pow(g, k, p)) % p == pow(g, h, p)
io.recvuntil(b"p = ")
p = int(io.recvline(keepends = False))
io.recvuntil(b"g = ")
g = int(io.recvline(keepends = False))
io.recvuntil(b"y = ")
y = int(io.recvline(keepends = False))
for i in range(20):
io.recvuntil(b"x = ")
io.sendline(str(pow(y, -1, p) + (i*p)).encode())
io.recvuntil(b"h = ")
io.sendline(str(i).encode())
io.interactive()
```
:::spoiler Flag
**KCSC{b4by_m4th_f0r_b4by_crypt0}**
:::
## Qu4dr4t1c (medium)
- **Source code:**
```python
from Crypto.Util.number import *
e = 65537
flag = b'KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}'
def reverse(n):{
#function to reverse binary of n
}
while True:
p = getPrime(1024)
q = inverse(e, p)
if not isPrime(q):
continue
n = p * q
cipher = pow(bytes_to_long(flag),e,n)
n = reverse(n)
f = open('output.txt','w')
print(f"N = {n}",file=f)
print(f"e = {e}",file=f)
print(f"Cipher = {cipher}",file=f)
```
:::spoiler output
N = 13524733362044232010736349595937464796777752381282044858904535549598695415259485540306280531287404403541039855661018351433654227342950710134306170544748441173774593898898768923907735212448495520658645896437678387670188401560165044043577269969416130117140222729708904953465161496726313677920240975640999580444678641072701612002184731572732086781180661428229265121878536891979130796853074814897843058889565035037987946761236280609366824566706376823708457581218333217098354233306312287549927586100725051273954453617494755601749327688591032955254157726764321151877093977335572150146339853526534429133266975640029987854181
e = 65537
Cipher = 3678620397255743852788853741107986108860981676309723331641730290544731009447106060307185476663548386172571801713658668783790148410569386488760778490944114348420614589196065297281576228195492339713201469195237426515519163981864121592862248581092535664172672153903696701157467812876812796524706730400133900257530235932000707810825149259236944828592989457788651053131965278448678769098840150302476398856999420129829083563611916558475165369663734941095660119099130765405955767410469621006246831917091632524062249541513097151767121519911807673852738866453379562168834013804186606786287157327927655505568604704262776577804
:::
- Challenge mã hóa **RSA** khá dị khi chọn $q \equiv e^{-1} \pmod p$ thay vì cho nó là một số nguyên tố :skull:
- [**Tham khảo đường link này**](https://crypto.stackexchange.com/questions/100766/how-to-break-rsa-when-q-e-1-bmod-p). Đầu tiên ta biến đổi $q \equiv e^{-1} \pmod p$ thành $q \times e = 1 + k\times p$ sau đó thế vào $n \times e$ thì ta được:
$$n \times e = p \times q \times e = p \times (1 + k\times p) = k \times p^2 + p$$
- Vậy để có $p$ thì ta giải phương trình bậc hai $k \times p^2 + p = n \times e$ là xong, nhưng làm sao để biết $k$ nằm trong khoảng nào mà brute force? lỡ đâu nó quá lớn thì sao.
- Với $q \times e = 1+ k\times p$ ta có $k = \frac{q \times e - 1}{p}$ suy ra:
$$1 \leqslant \frac{q \times e - 1}{p} < \frac{p \times e}{p}$$
$$\Leftrightarrow 1 \leqslant k < 65537$$
- Có $k$ là ta tính được $p$, bài toán kết thúc.
- **Script:**
```python
from gmpy2 import iroot
from Crypto.Util.number import *
N = str(bin(...))[2:] # nhập N vào dấu ... để đảo ngược lại
N = int(N[::-1],2)
e = 65537
Cipher = ...
k = 0
for i in range(1, 65537):
delta = 1 + 4 * i * N * e # b^2 - 4ac
sqrt_delta = iroot(delta,2)
if sqrt_delta[1] is True: # nếu True thì delta có thể căn ra số nguyên
k = i
print(k)
break
p = (-1 + sqrt_delta[0]) // (2 * k)
q = N//p
d = pow(e,-1, (p-1)*(q-1))
print(long_to_bytes(pow(Cipher, d, N)).decode())
```
:::spoiler Flag
**KCSC{1f_D4m14n_g3t_m4rr13d_w1th_4ny4,th3_34st_4nd_th3_W3st_w1ll_b3_p34c3ful!!!!}**
:::
## Affinity (medium)
- **Source code:**
```python
from Crypto.Util.number import getPrime
from random import randint
FLAG = b"KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}"
assert FLAG.startswith(b"KCSC{") and FLAG.endswith(b"}")
def caesar_affine(msg, key, p):
ct = []
for m in msg:
c = (m + key[0]) % p
c = (key[1]*c + key[2]) % p
ct.append(c)
return ct
enc = list(FLAG)
n = getPrime(32)
for i in range(32):
key = (randint(1,n), randint(1,n-1), randint(1,n))
enc = caesar_affine(enc, key, n)
# print(n) In your dream! :)
print(enc)
# [1910234182, 2771761218, 1048707146, 2771761218, 871449803, 617943628, 2163740357, 1302213321, 2302873284, 3886794429, 1086831562, 2752699010, 1517595080, 3886794429, 1498532872, 3240649152, 2321935492, 3690474878, 3886794429, 2379122116, 364437453, 3886794429, 3006205185, 852387595, 3905856637, 364437453, 364437453, 3886794429, 4064051772, 2809885634, 2379122116, 3240649152, 149055694, 3886794429, 2125615941, 206242318, 3886794429, 3671412670, 3886794429, 1283151113, 2321935492, 1086831562, 3886794429, 168117902, 2752699010, 1302213321, 3886794429, 2771761218, 2752699010, 1517595080, 579819212, 598881420, 3886794429, 1086831562, 2752699010, 1517595080, 3886794429, 1283151113, 2752699010, 3886794429, 579819212, 852387595, 2321935492, 3690474878, 2302873284, 2302873284, 3202524736, 3202524736, 2302873284, 656068044]
```
- **Mô tả:** Challenge thực hiện mã hóa **Affine** $32$ lần lên từng ký tự của $Flag$ với mỗi ký tự đều sử dụng chung 32 $key$ và $n$, nhưng challenge tăng độ khó bằng cách dấu đi $n$ và $key$. Mình đánh giá bài này khó, mất kha khá thời gian để làm.
- Đầu tiên ta nhìn vào hàm `caesar_affine()`, thấy rằng nó mã hóa $m$ bằng cách kết hợp mã **caesar** và mã **affine**, kết quả như sau:
$$c \equiv k_1 \times (m +k_0) + k_2 \equiv k_1 \times m + (k_1\times k_0 + k_2) \pmod n$$
- Sau đó nó thực hiện $32$ lần mã hóa như trên với kết quả $c$ trước đó để cho ra kết quả cuối cùng.
- Cho dù thực hiện bao nhiêu lần phép tính thì công thức tổng quát của nó vẫn là $c \equiv A \times m + B \pmod n$ với $m$ là ký tự của $Flag$ và $A,B$ của mỗi $c$ là giống nhau vì chúng được tạo nên từ chung $key$.
> Thử nhìn vào $5$ giá trị đầu của **output:** `[1910234182, 2771761218, 1048707146, 2771761218, 871449803]` đó là $5$ giá trị được mã hóa của từ `KCSC{`, vì $A,B$ là giống nhau nên giá trị mã hóa của hai chữ `C` là giống nhau (đều bằng **2771761218**).
- Vậy hướng giải của ta là tìm lại được $A,B$ và $n$, xong tìm lại $m$ bằng công thức $m \equiv (c-B) \times A^{-1} \pmod n$
> Nhưng làm sao để tìm lại $A,B,n$?
- Ta dựa vào format của $Flag$, biết được các ký tự như **K,C,S,{,}** là có thể tìm lại $n$.
- Với **K=75, C = 67, S = 83, { =123** ta lập được $4$ phương trình sau:
$$C_1 \equiv A \times 75 + B \pmod n$$
$$C_2 \equiv A \times 67 + B \pmod n$$
$$C_3 \equiv A \times 83 + B \pmod n$$
$$C_4 \equiv A \times 123 + B \pmod n$$
- Lấy $C_2 - C_1$ và $C_4 - C_3$ ta được:
$$C_2 - C_1 \equiv -8 \times A \pmod n$$
$$C_4 - C_3 \equiv 40 \times A \equiv -8 \times A \times -5 \pmod n$$
- Lấy $C_2 - C_1$ thế vào $C_4 - C_3$ được:
$$C_4 - C_3 \equiv -5 \times (C_2 - C_1) \pmod n$$
$$\Leftrightarrow C_4 - C_3 + 5\times (C_2 - C_1) \equiv 0 \pmod n$$
- Suy ra $C_4 - C_3 + 5\times (C_2 - C_1)$ chia hết cho $n$, vậy là ta tính được $n$ rồi.
- Sau khi có $n$, thì ta có thể tính dược $A$ và $B$, thông qua hai phương trình $C_4 - C_3 \equiv 40 \times A \pmod n$ và $C_2 \equiv A \times 67 + B \pmod n$.
- Có $A,B$ và $n$ thì bài toán kết thúc.
- **Script:**
```python
c = [1910234182, 2771761218, 1048707146, 2771761218, 871449803, 617943628, 2163740357, 1302213321, 2302873284, 3886794429, 1086831562, 2752699010, 1517595080, 3886794429, 1498532872, 3240649152, 2321935492, 3690474878, 3886794429, 2379122116, 364437453, 3886794429, 3006205185, 852387595, 3905856637, 364437453, 364437453, 3886794429, 4064051772, 2809885634, 2379122116, 3240649152, 149055694, 3886794429, 2125615941, 206242318, 3886794429, 3671412670, 3886794429, 1283151113, 2321935492, 1086831562, 3886794429, 168117902, 2752699010, 1302213321, 3886794429, 2771761218, 2752699010, 1517595080, 579819212, 598881420, 3886794429, 1086831562, 2752699010, 1517595080, 3886794429, 1283151113, 2752699010, 3886794429, 579819212, 852387595, 2321935492, 3690474878, 2302873284, 2302873284, 3202524736, 3202524736, 2302873284, 656068044]
c1 = 1910234182
c2 = 2771761218
c3 = 1048707146
c4 = 871449803
n = c4 - c3 + 5 * (c2 - c1)
A = ((c4 - c3) * pow(40, -1, n)) % n
B = (c1 - 75 * A)%n
def decrypt(msg):
pt = []
for i in msg:
pt.append(((i-B)*pow(A,-1,n))%n)
return pt
print(bytes(decrypt(c)).decode())
```
:::spoiler Flag
**KCSC{Wow!_y0u_be4t_m3_Thr33_7ime5_In_a_d4y_H0w_C0u1D_y0u_d0_1h4t!!??!}**
:::
## random (medium)
- **Source code:**
```python
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
import random, time
import struct
with open('flag.txt', 'r') as f:
FLAG = f.read()
def aes_encrypt(key, plaintext, iv):
key = key.ljust(32)[:32]
plaintext = plaintext.encode()
iv = iv.encode()
padder = padding.PKCS7(128).padder()
padded_plaintext = padder.update(plaintext) + padder.finalize()
cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
encryptor = cipher.encryptor()
ciphertext = encryptor.update(padded_plaintext) + encryptor.finalize()
return ciphertext
def aes_decrypt(key, ciphertext, iv):
key = key.ljust(32)[:32]
iv = iv.encode()
cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
decryptor = cipher.decryptor()
padded_plaintext = decryptor.update(ciphertext) + decryptor.finalize()
unpadder = padding.PKCS7(128).unpadder()
plaintext = unpadder.update(padded_plaintext) + unpadder.finalize()
return plaintext.decode()
random.seed(int(time.time()/4))
iv = str(random.randint(10**(16-1), 10**16 - 1))
with open('/dev/random', 'rb') as f:
num = int.from_bytes(f.read(3), byteorder='little')
random.seed(num)
num = (num >> 1 << 1) | random.choice([0,1])
key = num.to_bytes(3, byteorder='little')
cipher_text = aes_encrypt(key, FLAG, iv)
cipher_text = ' '.join(f'{byte:02x}' for byte in struct.unpack(f'{len(cipher_text)}B', cipher_text))
print('cipher text:', cipher_text)
exit(0)
```
- Bài này code nhìn phức tạp nhưng thật ra ý tưởng khá là đơn giản, mình thấy bài này dễ hơn bài **affine**.
- Bạn xem hai hàm `aes_encrypt()` và `aes_decrypt()` là hai hàm mã hóa và giải mã **AES** bình thường, nó chỉ thay đổi ở $key$ bằng cách pad thêm cho $key$ dài đủ $32$ bytes.
- Vì đây là mã hóa **CBC** nên ta phải đi tìm được **key** và **iv**. Ta có thể có **iv** rất dễ vì nó được random từ **seed** `int(time.time()/4`. Việc còn lại là đi tìm **key** thôi.
- Đại khái thì **key** được random từ seed `num`, mà `num` được random từ $3$ bytes ngẫu nhiên, thế thì ta đi **brute force** 3 bytes đó là có `num`, số trường hợp là $256^3 = 16777216$, hoàn toàn có thể brute force được, nên cài thư viện **tqdm** để dễ theo dõi tiến trình brute force hơn :smile:
- **Script:**
```python
from pwn import *
import random, time
from Crypto.Cipher import AES
from tqdm import trange
# chạy local vì server bị xóa lâu rồi
io = process(["python3", "test.py"])
io.recvuntil(b"cipher text: ")
data = bytes.fromhex(io.recvuntil(b"\n", drop=True).decode().replace(" ",""))
random.seed(int(time.time()/4))
iv = str(random.randint(10**(16-1), 10**16 - 1)).encode()
is_flag = False
for i in trange(256):
if is_flag:
break
for j in range(256):
for k in range(256):
num = int.from_bytes(bytes([i,j,k]), byteorder='little')
random.seed(num)
num = (num >> 1 << 1) | random.choice([0,1])
key = num.to_bytes(3, byteorder='little')
key = key.ljust(32)[:32]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(data)
if b"KCSC{" in flag:
print(flag)
print(num)
is_flag = True
break
```
> chạy nhanh hay chậm thì hên xui nha vì **num** được random mà :smile:
:::spoiler Flag
**KCSC{Brut3_F0rc3_3asy_Pe4sy!}**
:::
## No More Basic Math (hard)
- **Sourc code:**
```python
from Crypto.Util.number import bytes_to_long
from random import getrandbits
FLAG = b'KCSC{fake_flag}'
p = getrandbits(1024)
q = getrandbits(1024)
def encrypt(msg, key):
m = bytes_to_long(msg)
return p * m + q * (m**3 + m**2 + m) + (3*m + 2*p + q) * key
n = len(FLAG)
assert(n > 20)
key = getrandbits(1024)
print(f'n = {n}')
print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {encrypt(FLAG[:20], key)}')
print(f'c2 = {encrypt(FLAG[-20:], key)}')
```
:::spoiler output
n = 30
p = 48762188199150535581975412897924691165761153794040728191647919999953750500528915467941977942434049609148928874111418540791659239318033502960490438029918494978450003766475054277305000975826296521110691624198929727387822917181466972531783670424803605073382160801015364428887438227795060240461156343151628730113
q = 123154173062875129803388789468997467602861692189899574796521281322028039797350493630230549858629977130216821188366984746616639200404382396043604419180869596904421472720201306121199119571368299417757494448400590479108311324077855468994881760593143713996410859474408904326793393402741912427742694768217550181270
c1 = 21361708399259692476490585224474478239848096267728875151027667930547884138531321455258045949871008481309353774592024104870537486086028259415199204699193912434732702436520694573344765029331922878031532757006467986508373826559848018510846704694596043438688980012743479503379279444261834245820139438602646123909719216866856864573656625922211883930084371564748739048999645791127706355352400765930549436631488077615035313501456035704196655631076251694505647371287090426267130518184310327417676973790605083858188079554372289805772049887809199182600395727164328773350053287895190505219555434017220365550650906129322383481252
c2 = 21361708399259692476490585224474478239848096267728875151027667930547884138531321455258045949871008481309353774592024104870537486086028259415199204699193912434732702462872923491616113323696576471401453366769073405539609186296897006352387813496579755357765019379630756911340195523429031527586036900468063337747524187687027790122248988574172180712302674206934331239449040784296700054535172565955515658035497532654412975186522396759714280936589419263016914222837327779108969285650803460583010919600081536939185789237255320735405198555005684445856588326590949453146466337908623498742769971401502687499945846050861617865180
:::
- Một Challenge khó về Lattice, thật sự thì Lattice là một thứ vô cùng trừu tượng để hiểu và giải thích nên để hiểu được những thứ mình nói sắp tới thì các bạn có thể tham khảo hai nguồn sau ([link1](https://theblupper.github.io/blog/posts/lattices/), [link2](https://youtu.be/vREqxm0j784))
- Đại khái thì để giải bài này ta cần phải chuyển phương trình `c = p * m + q * (m**3 + m**2 + m) + (3*m + 2*p + q) * key` về phương trình tuyến tính dạng:
$$A\times x +B \times y \equiv w\times C \pmod n$$
- Với $x,y$ là hai nửa của $Flag$ mà ta cần tìm. Ta biến đổi phương trình trên thành:
$$w \times C - A\times x - B \times y + k\times n = 0$$
- Từ phương trình tuyến tính trên, ta lập một ma trận theo cấu trúc sau:
$$
\begin{bmatrix}
C & 1 & 0& 0 \\
-A & 0 & 1 & 0\\
-B & 0 & 0 & 1\\
n & 0 & 0 & 0\\
\end{bmatrix}
$$
- Gọi ma trận trên là **4 vector cơ sở** của một Lattice thì **mọi điểm** trong Lattice đó sẽ được biểu diễn bằng tổ hợp tuyến tính như sau:
$$
[w,x,y,k] \times
\begin{bmatrix}
C & 1 & 0& 0 \\
-A & 0 & 1 & 0\\
-B & 0 & 0 & 1\\
n & 0 & 0 & 0\\
\end{bmatrix}
=
\begin{bmatrix}
wC -Ax-By+kn,& w, & x, & y \\
\end{bmatrix}
$$
- Mà đã có $w \times C - A\times x - B \times y + k\times n = 0$ (là một giá trị **nhỏ**), nên ta sẽ bắt thuật toán **LLL** đi tìm một vector ngắn nhất thỏa mãn điều kiện trên, hay nói cách khác là bắt `LLL` đi tìm hai giá trị $x$ và $y$ sao cho phương trình trên có giá trị bằng $0$, khi này vector ngắn nhất đó sẽ có dạng:
$$
\begin{bmatrix}
wC -Ax-By+kn,& w, & x, & y \\
\end{bmatrix}
= [0, w, x, y] = [0,1,x,y]
$$
- Vector ngắn nhất đó sẽ chứa $x,y$ là hai nửa của $Flag$. Thuật toán **LLL** sẽ trả về nhiều vector nên ta phải check xem vecor nào bắt đầu bằng hoặc có $[0,1]$ thì lấy vì sẽ có các vector không thỏa yêu cầu.
- Vậy công việc của ta là biến đổi sao cho từ phương trình ban đầu là:
$$c = p \times m + q \times (m^3 + m^2 + m) + (3\times m + 2\times p + q) \times key$$
- Thành dạng:
$$A\times x +B \times y \equiv C \pmod n$$
$$\Leftrightarrow C - A\times x - B \times y + k\times n = 0$$
- Sau đó biến đổi thành ma trận như trên rồi áp dụng **LLL** là lụm.
- Ta biến đổi như sau, gọi $key$ là $K$ ta có phương trình ban đầu là:
$$C = p.m + q.(m^3 + m^2 + m) + (3m + 2p + q).K$$
$$\Leftrightarrow C = p. m + q.(m^3 + m^2 + m) + q.K + (3m + 2p).K$$
$$\Leftrightarrow C = p. m + q.(m^3 + m^2 + m + K)+ (3m + 2p).K$$
- Ta Modulo hai vế cho $q$ được phương trình modulo sau:
$$C \equiv p.m + (3m+2p).K \pmod q$$
$$\Leftrightarrow (C-p.m) \times (3m+2p)^{-1} \equiv K \pmod q$$
- Vì $(C_1-p.m_1) \times (3m_1+2p)^{-1}$ và $(C_2-p.m_2) \times (3m_2+2p)^{-1}$ đều đồng dư với $K$ trong modulo $q$ nên ta có:
$$(C_1-p.m_1) \times (3m_1+2p)^{-1} \equiv (C_2-p.m_2) \times (3m_2+2p)^{-1} \pmod q$$
$$\Leftrightarrow (C_1-p.m_1) \times(3m_2+2p) \equiv (C_2-p.m_2) \times (3m_1+2p) \pmod q $$
- Khai triển ra thì ta được:
$$3C_1.m_2 + 2p.C_1 - \underline{3p.m_1.m_2} - 2p^2.m_1 \equiv 3C_2.m_1 + 2p.C_2 - \underline{3p.m_1.m_2} - 2p^2.m_2 \pmod q$$
$$\Leftrightarrow 2p.(C_1-C_2) \equiv (3C_2+2p^2).m_1 - (3C_1+2p^2).m_2 \pmod q$$
- Giờ phương trình của ta thành dạng tuyến tính $A.x + B.y \equiv C.w \pmod n$ rồi, với $w = 1$ ta có:
$$(3C_2+2p^2).m_1 - (3C_1+2p^2).m_2 - 2p.(C_1-C_2).w + k.q = 0 $$
- Biến đổi phương trình trên thành ma trận sau:
$$
\begin{bmatrix}
3C_2+2p^2 & 1 & 0& 0 \\
-(3C_1+2p^2) & 0 & 1 & 0\\
-2p.(C_1-C_2) & 0 & 0 & 1\\
q & 0 & 0 & 0\\
\end{bmatrix}
$$
- Sau đó sử dụng **LLL**, ta sẽ được vector ngắn nhất là:
$$[0, m_1, m_2, 1]$$
- **Script:**
```python
from sage.all import *
from Crypto.Util.number import long_to_bytes
p =
q =
c1 =
c2 =
A = 3 * c2 + 2*p**2
B = 3 * c1 + 2*p**2
C = 2*p*(c2-c1)
#A*m1 - B*m2 - C.w + k*q = 0
W = Matrix([[A, 1, 0, 0], [-B, 0, 1, 0], [-C, 0, 0, 1], [q, 0, 0, 0]])
B = W.LLL()
print(B[0])
print(B[1])
print(B[2])
print(B[3])
```
- Thuật toán **LLL** sẽ cho ta nhiều kết quả nhưng ta chỉ chọn vector nào thỏa mãn yêu cầu thôi:
- Chọn vector `(0, 429675711022751492886702095556098737230277718905, 664415457209781694288264696393686878037291584637, 1)` vì nó là vector dạng $[0, m_1, m_2, w]$.
- Vậy $Flag$ của ta là:
```python
from Crypto.Util.number import long_to_bytes
SV = (0, 429675711022751492886702095556098737230277718905, 664415457209781694288264696393686878037291584637, 1)
print(long_to_bytes(SV[1])[:10] + long_to_bytes(SV[2]))
```
:::spoiler Flag
**KCSC{cant_take_my_3y3s_0f_LLL}**
:::
# END
Sign in with Wallet
Connect another wallet