# HCMUS-Quals 2023 Crypto
### bootleg aes

Chall cho 3 files `ciphertext.bin`, `enc.sh`, `log.txt`. Dựa vào file `enc.sh` và `log.txt` ta biết được rằng flag đã được pad đằng trước 253 bytes rồi mang đi encypt AES-CBC, key được ghi trong file `log.txt`. Do không có iv chính xác nên mình chỉ có thể decrypt đúng từ block thứ 2 trở đi nhưng điều này không ảnh hưởng tới flag.

- Flag: `HCMUS-CTF{it5_c4ll3d_pr1v4t3_k3y_crypt09raphy_f0r_4_r3450n}`

### CRY1

Chương trình sẽ thực thi hàm handle mỗi khi có một kết nối tới. Khi một kết nối được gửi tới, nó sẽ gen user_id là số giây tính từ 1/1/1970 tới nay bằng hàm `int(time.time()` và lấy giá trị này làm seed để thực thi srand, nên đây là giá trị mà mình sẽ có thể lấy được. Sau đó chương trình gen ra 26 số ngẫu nhiên và thực hiện tính tổng các byte của flag và các giá trị ngẫu nhiên được gen ra từ đầu tới cuối.

Thuật toán cũng khá đơn giản nên mình tổng kết được các ý sau:
- Có 26 biến và format như sau: `x0*randnum[0] + x1*randnum[1] + ... + x25*randnum[25] == sum` (với biến sum được lấy từ server là giá trị mà server gửi cho mình)
- Vậy cần 26 phương trình để giải hệ 26 phương trình 26 ẩn bằng z3
- Vậy ta cần lấy được số giây lúc chương trình chạy ứng với giá trị tổng của phương trình, tức ta phải lấy đúng seed và sum 26 lần

Để lấy giá trị seed và sum (mình sẽ gọi là biến encode), khi vừa kết nối thì ta thực thi `time.time()` để lấy seed và khi server trả về sum thì ta lấy sum. Mình sẽ chạy liên tục để lấy toàn bộ dữ liệu và chạy trong vòng 27 giây để lấy nhiều trường hợp nhất có thể và từ đó lọc ra 27 trường hợp:

from pwn import *
import time
import random
import os
from z3 import *
import threading

done = 0
def get_seed_internal():
	global done
	while not done:
		p = process('ncat --ssl cry1.chall.ctf.blackpinker.com 443'.split())
		# p = remote('128.199.142.5', 8080)
		# p = remote('127.0.0.1', 8080)

		t = int(time.time())
		p.recvuntil(b'flag: ')
		flag_enc = int(p.recvline().strip())
		msg = f'{int(t)} {flag_enc}\n'
		with open('flagenc', 'a') as f:
			f.write(msg)
		print(int(t), flag_enc)

		p.close()

def get_seed():
	global done
	if os.path.exists('flagenc'):
		os.remove('flagenc')

	threading.Thread(target=get_seed_internal, args=()).start()
	time.sleep(28)
	done = 1

Vì giá trị time.time() trên server thay đổi trước nên giá trị sum trả về cũng sẽ thay đổi trước so với khi ta chạy time.time() để lấy giây trên máy mình. Do đó ta có thể lấy dòng dữ liệu ngay trước lúc giá trị encode thay đổi với hàm sau:

seed = []
encode = []
def parse_seed_encode():
	global seed, encode
	with open('flagenc', 'r') as f:
		datas = f.read().strip().split('\n')
	pres, pree = 0, 0
	for i, data in enumerate(datas):
		s, e = data.split()
		s, e = int(s), int(e)
		if pres == 0 and pree == 0:
			pres = s
			pree = e
		elif e != pree:
			seed.append(pres)
			encode.append(pree)
		pres = s
		pree = e

Với seed và giá trị encode thì ta chỉ việc xài z3 để giải nữa là xong:

def gen_key(user_id):
    random.seed(user_id)
    return [random.randrange(1024) for i in range(26)]

def solve_flag():
	parse_seed_encode()
	print(len(seed))
	print(seed)
	print(len(encode))
	print(encode)
	arr = [Int(f'x{i}') for i in range(26)]
	s = Solver()

	# Add conditions
	for i in range(26):
		s.add(arr[i] > 0x20, arr[i] < 0x7f)

	for i in range(26):
		print(seed[i], encode[i])
		data = gen_key(seed[i])
		s.add(sum([a * b for a, b in zip(arr, data)]) == encode[i])

	# Solve
	while s.check() == sat:
		for i in range(26):
			print(chr(s.model()[arr[i]].as_long()), end='')
		print()
		s.add(Or(
			arr[0] != s.model()[arr[0]],
			arr[1] != s.model()[arr[1]],
			arr[2] != s.model()[arr[2]],
			arr[3] != s.model()[arr[3]],
			arr[4] != s.model()[arr[4]],
			arr[5] != s.model()[arr[5]],
			arr[6] != s.model()[arr[6]],
			arr[7] != s.model()[arr[7]],
			arr[8] != s.model()[arr[8]],
			arr[9] != s.model()[arr[9]],
			arr[10] != s.model()[arr[10]],
			arr[11] != s.model()[arr[11]],
			arr[12] != s.model()[arr[12]],
			arr[13] != s.model()[arr[13]],
			arr[14] != s.model()[arr[14]],
			arr[15] != s.model()[arr[15]],
			arr[16] != s.model()[arr[16]],
			arr[17] != s.model()[arr[17]],
			arr[18] != s.model()[arr[18]],
			arr[19] != s.model()[arr[19]],
			arr[20] != s.model()[arr[20]],
			arr[21] != s.model()[arr[21]],
			arr[22] != s.model()[arr[22]],
			arr[23] != s.model()[arr[23]],
			arr[24] != s.model()[arr[24]],
			arr[25] != s.model()[arr[25]],
			))

Để chạy 1 lần thì:

if __name__=='__main__':
	get_seed()
	solve_flag()

Chạy script trên máy thì không được, có thể do kết nối lâu nên seed bị sai, hoặc do server ở Singaport nên giá trị `int(time.time())` của server khác với máy. Ta deploy 1 con vps ở Singaport bằng Digital Ocean thì chạy một phát ra flag luôn.

- Flag: `HCMUS-CTF{the_EASIEST_0ne}`

### falsehood

Phân tích file `prob.py` mình biết được rằng key chính là hệ số của đa thức bậc 15 có dạng:

$$
key[0]x^0 + key[1]x^1 +...+key[15]x^{15}=y
$$

Mình cũng đã có 16 cặp giá trị $x,y$ trong file `ouput.txt` để giải hệ phương trình 16 ẩn:

from Crypto.Cipher import AES
out = [[8833677163, 7159466859734884050485160017085648949938620549936739498951806707835448713685207536552299918328868591349533273061478374089984223260577742322460362334647], [1762352339, 226021067407224282748442153993506422184559341973942542463611713009302649608941949660293486972516731321467369225717344439888178648461773300463], [6814325828, 145915445591160853098610646953738314537732696913127480076359637783667652244881400087606152610739138506056218199806589240306741950875956525839170443027], [7865890147, 1255960511416167089973436987379886082394930531153251392262351559661203914293720867397614316726175343133363293139291718249474745356688772183204229822751], [3446680058, 5293859406843167459297872689128502546567761548640003856519557803475599388573073027426285178678302790672452768542207529392596772806973985884693237], [5877771652, 15883583178415793156782570756223737797760371065858523945056072346852806064052610100332389954372845836435762293469821829936427366159434784004504398291], [5589586633, 7472281200056449019563455444999813482028446397663996508394508567670602924631065370355170602075256758870709465268255309886778027432655593535614166637], [1175276268, 518629639886914674796931012497083502361229856009622285824810204881645367508380387007577326543311405957619591605841895258801496781885398507], [3312651249, 2920072124198357353277671402963439479294095254775553378538026906919501392975483266953780010186413153114694525677661955925502702904273824951901573], [1690420045, 120969905638890571692249167310237577968012605711450331530578304692989016303379573026678222839813088165787719888874515256743894818676147474521], [8298141391, 2802013920829536770649820952830225273137583982204944734413323800249577243089166668778583649665043009034143120874987986020037964205143133245123290632883], [733386150, 439287044309927586596972381366960178061704411347096135895831191742005839221734048948610767236121358802659929070752762370822244956535801], [7897145685, 1332938401210287323326359805632057169759318295533885927320250339098837407040892547133970478663396358868892779722453565866390506758764909670000617998161], [9797888335, 33864534898740204255025855638155912349784294672865719351405048784504660475905319925895086755774471151890089727930776090169445401259844048317273142069811], [4557234547, 349364318043137479854576449493426376983315472777226775365310579193760250715517761090058069937282741206013319707277840448237966901906357292702335951], [7667001731, 855344863189641492213600127143839128290386097202448105626863527763958015786114563445357087338205788545215994676722500375202243293047596358065835329663]]
ct = bytes.fromhex('be205fd34ebe59af55ea11fec9aea50197fbf35d5b52c650a6c9563186625e8b6021ba31db538fa4b60c69a42c96ee3bebaba53ac9afa9c3c185d4d0b145bc8251d892c243f1aa4037aeea003714e24c')
iv = bytes.fromhex('370abc6fce33f812de7b88daaa82e4c4')
coff_1 = []
coff_2 = []
for i in range(16):
    tmp = []
    for j in range(16):
        tmp.append(pow(out[i][0], j))
    coff_1.append(tmp)
    coff_2.append(out[i][1])
A = matrix(coff_1)
B = vector(coff_2)
C = A.solve_right(B)
key = bytes(C)
Cipher = AES.new(key, AES.MODE_CBC, iv)
flag = Cipher.decrypt(ct)
print(flag)

- Flag: `HCMUS-CTF{just_because_you're_correct_doesn't_mean_you're_right}`

### M Side

Phân tích file `prob.py` thì đây là hệ mã RSA với $p,q$ sao cho $4p^2+q^2$ là một số nguyên tố. Mình sẽ dùng tool https://www.alpertron.com/SUMCUAD.HTM để tổng hợp lại các bình phương, sau khi bỏ số `hint` vô tool ta đã có được $q \implies$ dễ dàng suy ra $p \implies$ `flag`


- Flag: `HCMUS-CTF{either_thu3_0r_3uclid_wh1ch3v3r_it_t4k35}`

### Sneak Peak

Phân tích file `prob.py` thì flag đã được mã hóa bằng RSA và biết được $MSB_{272}(p)$. Đây là dạng `Recovery from Most Significant Bits of p`, vấn đề ở đây là số bit bị mất đã lớn hơn 1/3 tổng số bit của p nên không thể dùng ma trận 3x3 thông thường để giải mà phải tạo một ma trận cấp lớn hơn. Rất may mình tìm được một implementation có sẵn nên không phải mất công tạo ma trận:
`sol.sage`

# https://connor-mccartney.github.io/cryptography/small-roots/corrupt-key-1-picoMini

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes
def small_roots(f, X, beta=1.0, m=None):
    N = f.parent().characteristic()
    delta = f.degree()
    if m is None:
        epsilon = RR(beta^2/f.degree() - log(2*X, N))
        m = max(beta**2/(delta * epsilon), 7*beta/delta).ceil()
    t = int((delta*m*(1/beta - 1)).floor())
    
    f = f.monic().change_ring(ZZ)
    P,(x,) = f.parent().objgens()
    g  = [x**j * N**(m-i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)]) 
    B = Matrix(ZZ, len(g), delta*m + max(delta,t))

    for i in range(B.nrows()):
        for j in range(g[i].degree()+1):
            B[i,j] = g[i][j]*X**j

    B =  B.LLL()
    f = sum([ZZ(B[0,i]//X**i)*x**i for i in range(B.ncols())])
    roots = set([f.base_ring()(r) for r,m in f.roots() if abs(r) <= X])
    return [root for root in roots if N.gcd(ZZ(f(root))) >= N**beta]

def recover(p_high, n, m):
        p_bits = (len(bin(n))-2)//2
        p_high_bits = len(bin(p_high)) - 2
        PR.<x> = PolynomialRing(Zmod(n))
        f = p_high * 2**(p_bits-p_high_bits) + x
        x = small_roots(f, X=2**(p_bits-p_high_bits), beta=0.4, m=m)
        if x == []:
                return None
        p = int(f(x[0]))
        return p

def solve(bits, m):
    for x in tqdm(range(2**bits, -1, -1)):
        _p = _p_high + x * 2**(256-bits)
        p_high = int(bin(_p)[:256+bits+2], 2)
        p = recover(p_high, n, m)
        if p is not None:
            return p
peek = 6745414226866166172286907691060333580739794735754141517928503510445368134531623057
n = 137695652953436635868173236797773337408441001182675256086214756367750388214098882698624844625677992374523583895607386174643756159168603070583418054134776836804709359451133350283742854338177917816199855370966725059377660312824879861277400624102267119229693994595857701696025366109135127015217981691938713787569
ct = 60939585660386801273264345336943282595466297131309357817378708003135300231065734017829038358019271553508356563122851120615655640023951268162873980957560729424913748657116293860815453225453706274388027182906741605930908510329721874004000783548599414462355143868922204060850666210978837231187722295496753756990
_p_high = peek << 240
p = int(solve(bits=8, m=18))
q = n//p
assert p*q==n
e = 65537
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
flag = pow(ct,d,n)
print(long_to_bytes(int(flag)))

- Flag: `HCMUS-CTF{d0nt_b3_4n_3XhiB1ti0ni5t_0r_y0uLL_g3t_eXp0s3d}`