# KCSC Recruitment Writeup
> Đây là lần đầu tiên mình được tham gia một giải CTF, là một hoạt động đầu khóa khá hay với bản thân mình. Làm quen với CTF nói chung là Crypto nói riêng cũng chưa thực sự đủ lâu, vì thế qua giải lần này mình cảm nhận rằng còn quá nhiều thứ mới mẻ với bản thân mình.
> Trong contest lần này mình giải quyết được 2 bài crypto: **Base64** và **BabyRSA**. Chưa thực sự ấn tượng, nhưng cũng là đáp ứng được target ban đầu đã đặt ra. Và trong writeup lần này, mình sẽ ghi chép lại quá trình mình làm việc và giải quyết 2 bài này.
>

## Base64:
> *Difficulty: Warmup*

Đúng như tiêu đề, đây là một bài sử dụng đến kiến thức về hệ mã Base64. Dưới đây là file chall được cung cấp.

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))

Output của bài này:

gObheRHIpN+wlQ7vqQiQb3XzpAbJn4iv6lR=

**Phân tích file chall**
Cùng đi sâu vào phân tích đoạn code để hình thành cách giải:
- Bảng mã hóa Base64 được cung cấp với các chuỗi nhị phân 6 bit.
- Hàm `encode()` được thiết lập, thực hiện mã hóa chuỗi theo bảng mã hõa:
Với mỗi chuỗi string nhập vào, hàm sẽ duyệt từng kí tự trong chuỗi. Sử dụng hàm `order()` để có thể chuyển kí tự thành số nguyên tương ứng trong bảng ASCII. Hàm `bin()` chuyển giá trị số nguyên thành chuỗi nhị phân tương ứng, cắt bỏ 2 kí tự đầu để lấy được chuỗi nhị phân, rồi sử dụng `zfill()` để thêm các số 0 vào chuỗi nhị phân để đảm bảo độ dài là 8bit, ghép lại với nhau để được xâu `s`.

s = ""
for i in string:
    s += bin(ord(i))[2:].zfill(8)

- Phần padding được đệm bằng những dấu "=" để đảm bảo số lượng bit trong chuỗi thỏa mãn yêu cầu của hệ B64.
- Cuối cùng là chuyển chuỗi nhị phân về dạng Base64, kết hợp với phần padding:

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

*Nhận xét: một thuật toán mã hóa Base64 khá cơ bản. Mình sẽ đảo ngược lại quá trình mã hóa để lụm flag.*

**Solution**

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",
}
b64_reverse = {v: k for k, v in b64.items()}

def decode(b64_string):
    #Loại bỏ các dấu "="
    pad = b64_string.count('=')
    b64_string = b64_string.rstrip('=')
    
    #Chuyển B64 về nhị phân
    s = ""
    for char in b64_string:
        s += b64_reverse[char]
    
    #Xóa các kí tự bit thừa(nếu có)
    if pad == 1:
        s = s[:-2]
    elif pad == 2:
        s = s[:-4]
    
    #Chuyển nhị phân về xâu kí tự
    ret = ""
    for i in range(0, len(s), 8):
        ret += chr(int(s[i:i+8], 2))
    
    return ret

 
ciphertext = "gObheRHIpN+wlQ7vqQiQb3XzpAbJn4iv6lR="
print(decode(ciphertext))

Flag sau khi chạy đoạn mã: `KCSC{no0b_base64_encode!!}`

## Baby RSA
> *Difficulty: Medium hoặc Easy, idk*

Từ tên gọi, mình định hướng bài này sẽ áp dụng các phương thức tấn công đối với hệ mã RSA. Mình sẽ phân tích file chall để xác định phương thức tấn công phù hợp.
File chall như sau:

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 = }')

Output được cung cấp:

c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733

Phân tích thì đây là một quá trình mã hóa RSA khá... cơ bản. Flag từ bytes chuyển sang dạng long, N được cấu thành từ tích của hai thừa số `p` và `q` với độ dài 512 bit, tạo nên số N với độ dài 1024 bit.Hai số mũ `e1` và `e2` khác nhau được khởi tạo với cùng độ dài 15 bit. Hai khóa công khai khác nhau về số mũ nhưng lại chung tham số modulo N, cùng mã hóa một bản rõ. Nói đến đây, mình bắt đầu nghiên cứu lại document để tìm ra hướng tấn công, và nhận thấy có thể áp dụng phương pháp Common Modulus Attack:
*Source: 20 years of Attacks on the RSA Cryptosystem*
Tuy nhiên, vấn đề lớn nhất mình gặp phải trong quá trình giải bài này là không có được 2 giá trị e mình cần tìm. Mình đã create ticket để xác nhận lại hướng đi, và tìm cách để giải quyết vấn đề. Sau khi đã được xác nhận đúng cách tiếp cận bài, lại thêm việc nhận thấy các giá trị `e1` và `e2` cùng có độ dài 15 bit, mình quyết định bruteforce trong khoảng 20 phút trước khi sự kiện TTV kết thúc.
**Solution**

from math import gcd
from Crypto.Util.number import *

#Thuật toán Extended Euclid
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd_val, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd_val, x, y
#Tìm GCD
def check_gcd(a,b):
    if gcd(a, b) == 1:
        return True
    else:
        return False

# Thuật toán tấn công
def common_modulus_attack(c1, c2, e1, e2, n):

    gcd_val, x, y = extended_gcd(e1, e2)
    
    if x < 0:
        x = -x
        c1 = pow(c1, -1, n) 
    if y < 0:
        y = -y
        c2 = pow(c2, -1, n) 

    m = (pow(c1, x, n) * pow(c2, y, n)) % n
    return m

c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733

for i in range(2**14, 2**15):
    if isPrime(i) == True:
        for h in range(2**14, 2**15):
            if isPrime(h) == True:
                e1 = i
                e2 = h
                m = common_modulus_attack(c1, c2, e1, e2, n)
                ans = long_to_bytes(m)
                if b'KCSC' in ans:
                    print(ans)

Vì có sẵn code các thuật toán cho phương thức tấn công này, nên mình chỉ cần thêm thao tác bruteforce tìm 2 giá trị `e1` và `e2` để có thể hoàn thành. Sau khoảng 5-10p chạy code, flag đã hiện ra: `KCSC{3x73rn4l_4774ck_1n_r54}`.

## Lời kết:
Một sự kiện, trải nghiệm đáng nhớ với bản thân mình. Cảm ơn các anh chị CLB KCSC đã tạo điều kiện, cho em cơ hội được tiếp xúc lần đầu với một sân chơi về CTF. Rất mong được tham gia nhiều sự kiện của CLB trong tương lai!