# Slashroot Final 2024

This is a short writeup for Slashroot 8.0's finals. This CTF was held on a Friday so it's in a bit of a weird mood, as most people have work or classes. Nevertheless, I think we still placed first, as competition was a bit light. This writeup is mostly just a one to one copy from my team's official writeup in Indonesian.

## Cry/Habbo

Chall cukup sederhana, dimana goal utama adalah forge token admin. Token dalam chall ini berupa JSON yang encrypted dengan AES ECB, dan kita diberikan input nama pada JSON, sehingga solusi cukup straightforward, cukup manipulasi block dari enkripsi.

class Token:
    def __init__(
        self,
        name: str = "",
        timestamp: int = 0,
        rand: str = RANDOM,
        admin: bool = False
    ) -> None:
        if timestamp == 0:
            timestamp = int(datetime.now().timestamp())

        self.rand = rand
        self.name = name
        self.timestamp = timestamp
        self.admin = admin

    def authenticate(self):
        if self.admin and self.rand != RANDOM and self.timestamp == -1:
            return True
        else:
            return False

    def is_expired(self):
        now = int(datetime.now().timestamp())
        if self.timestamp == -1:
            return False
        elif self.timestamp + 60 < now:
            return True
        else:
            return False

class HabboHotel:
    def __init__(self) -> None:
        self.aes = AES.new(KEY, AES.MODE_ECB)

    def strip_keys(self, token: dict):
        new = {}
        for key in token:
            value = token[key]
            if type(key) == str:
                new[key.strip()] = value
            else:
                new[key] = value
        return new

    def generate_token(self, name: str):
        try:
            self.token = Token(name)
            token_str = json.dumps(self.token.__dict__)
            print("token block:", [token_str[i:i+16] for i in range(0, len(token_str), 16)])
            self.enc_token = self.aes.encrypt(pad(token_str.encode(), 16)).hex()
        except Exception as e:
            return f"Faulty token :( {repr(e)}"

    def read_token(self, enc_token: str):
        try:
            dec_token = self.aes.decrypt(unhexlify(enc_token))
            print(unpad(dec_token, 16).decode())
            data = self.strip_keys(json.loads(unpad(dec_token, 16).decode()))
            self.token = Token(**data)
            self.enc_token = enc_token
        except Exception as e:
            return f"Faulty token :( {repr(e)}"

Terdapat tiga bypass utama yang harus dilakukan:
1. Merubah value random
2. Merubah value timestamp
3. Merubah value admin

Pertama, untuk merubah value random, ide dilakukan adalah mengambil block `","timestamp": ` yang akan menutup string random (truncate) dan memulai key timestamp.

Kemudian, value timestamp dapat diubah dengan memasukan nama ` -1 ` dengan banyak spasi, sehingga terdapat block yang hanya berisi -1 dan spasi.

Terakhir, untuk mengubah value admin, diambil block ` "name …` dan `65005, "admin": ` untuk memperoleh key admin, dan true dapat diperoleh dengan metode yang serupa dengan timestamp.

Payload akhir yang diharapkan terbentuk (setelah decrypt) adalah sebagai berikut:
`{"rand": "3731e3", "timestamp": -1, "name ": 65005, "admin": true }`

### Solver

from azunyan.conn import process, remote

#r = process(['python3', 'chall.py'], level='debug')
r = remote('139.59.99.85', 10012, level='debug')

def login(tok: str):
    r.sendlineafter(b'Input:', b'2')
    r.sendlineafter(b'Token:', tok.encode())
    r.interactive()
    
def generate_token(payload: str):
    r.sendlineafter(b'Input:', b'1')
    r.sendlineafter(b'Your name: ', payload.encode())
    r.recvuntil(b'Here is your token:')
    tok = r.recvtype(str)
    r.sendlineafter(b'Input: ', b'3')
    return tok

BLOCK_SIZE = 32

tok = generate_token('true')
close = tok[-BLOCK_SIZE:]
first_block = tok[:BLOCK_SIZE]
name_block = tok[BLOCK_SIZE:2*BLOCK_SIZE]
tok = generate_token('trueaaaaaaaaaa')
close_str_timestamp_block = tok[BLOCK_SIZE * 3 : BLOCK_SIZE * 4]
tok = generate_token("               -1,             ")
min_1_block = tok[BLOCK_SIZE * 3 : BLOCK_SIZE * 4]
tok = generate_token("name              -1,             ")
open_str_block = tok[BLOCK_SIZE * 2 : BLOCK_SIZE * 3]
tok = generate_token(":              -1,             ")
close_property = tok[BLOCK_SIZE * 2 : BLOCK_SIZE * 3]
tok = generate_token('aaaaaaaaa')
admin_block = tok[BLOCK_SIZE * 4 : BLOCK_SIZE * 5]
tok = generate_token("               true             ")
true_block = tok[BLOCK_SIZE * 3 : BLOCK_SIZE * 4]

login(first_block + close_str_timestamp_block + min_1_block + open_str_block + close_property + admin_block + true_block + close)

## Cry/Stacking
Chall pada dasarnya hanya classical cipher yang vigenere-like. Solusi hanya berupa optimasi brute force.

class Stacker:
    def __init__(self, key: str) -> None:
        self.charset = string.ascii_uppercase
        self.rounds = 9


        self.key, self.x = self.generate_keypair(key)
        self.mixed_charset = self.mix_charset()


    def generate_keypair(self, key: str):
        key = key.upper()
        x = 0
        for k in key:
            x += self.charset.index(k)


        return key, x % len(self.charset)


    def mix_charset(self):
        charset_length = len(self.charset)
        key_length = len(self.key)
        blocks = [self.charset[i:i+key_length] for i in range(0, charset_length, key_length)][::-1]
        final_charset = ""
        for i in range(key_length):
            for block in blocks:
                try:
                    final_charset += block[i]
                except IndexError:
                    pass


        return final_charset


    def sub(self, text: str):
        result = ""
        for i, p in enumerate(text):
            key_loc = self.mixed_charset.index(self.key[i%len(self.key)])
            plain_loc = self.mixed_charset.index(p)
            result += self.mixed_charset[(plain_loc + key_loc) % 26]


        return result


    def flip(self, text: str):
        result = ""
        for c in text:
            c_loc = self.charset.index(c)
            result += self.mixed_charset[c_loc]


        return result


    def shift(self, text: str):
        result = ""
        for c in text:
            c_loc = self.charset.index(c)
            result += self.charset[(c_loc + self.x) % len(self.charset)]


        return result


    def encrypt(self, plaintext: str):
        data = plaintext.upper()


        for _ in range(self.rounds):
            data = self.sub(data)
            data = self.flip(data)
            data = self.shift(data)


        return data

Pertama, kita akan mengimplementasikan fungsi decrypt. Ini sangat mudah karena semua operasi encrypt reversible. Kemudian, perhatikan bahwa sebagian besar enkripsi hanya bergantung pada key_length dan nilai x, dan selain itu, enkripsi sangat mirip dengan vigenere cipher. Strategi pada dasarnya adalah menebak key_length dan x, dan kemudian membrute key hingga plaintext sesuai. Mengingat bahwa search space sangat kecil, brute force sederhana sudah cukup.

import string
import re
from tqdm import trange, tqdm

CHARSET = string.ascii_uppercase

class Stacker:
    def __init__(self, key: str) -> None:
        self.charset = string.ascii_uppercase
        self.rounds = 9

        self.key, self.x = self.generate_keypair(key)
        self.mixed_charset = self.mix_charset()
        
    def reset(self, key: str, x: int) -> None:
        self.key = key
        self.x = x
        self.mixed_charset = self.mix_charset()

    def generate_keypair(self, key: str):
        key = key.upper()
        x = 0
        for k in key:
            x += self.charset.index(k)

        return key, x % len(self.charset)

    def mix_charset(self):
        charset_length = len(self.charset)
        key_length = len(self.key)
        blocks = [self.charset[i:i+key_length] for i in range(0, charset_length, key_length)][::-1]
        final_charset = ""
        for i in range(key_length):
            for block in blocks:
                try:
                    final_charset += block[i]
                except IndexError:
                    pass

        return final_charset

    def sub(self, text: str):
        result = ""
        for i, p in enumerate(text):
            key_loc = self.mixed_charset.index(self.key[i%len(self.key)])
            plain_loc = self.mixed_charset.index(p)
            result += self.mixed_charset[(plain_loc + key_loc) % 26]

        return result
    
    def invsub(self, text: str):
        result = ""
        for i, p in enumerate(text):
            key_loc = self.mixed_charset.index(self.key[i%len(self.key)])
            plain_loc = self.mixed_charset.index(p)
            result += self.mixed_charset[(plain_loc - key_loc) % 26]

        return result

    def flip(self, text: str):
        result = ""
        for c in text:
            c_loc = self.charset.index(c)
            result += self.mixed_charset[c_loc]

        return result
    
    def invflip(self, text: str):
        result = ""
        for c in text:
            c_loc = self.mixed_charset.index(c)
            result += self.charset[c_loc]

        return result

    def shift(self, text: str):
        result = ""
        for c in text:
            c_loc = self.charset.index(c)
            result += self.charset[(c_loc + self.x) % len(self.charset)]

        return result
    
    def invshift(self, text: str):
        result = ""
        for c in text:
            c_loc = self.charset.index(c)
            result += self.charset[(c_loc - self.x) % len(self.charset)]

        return result

    def encrypt(self, plaintext: str):
        data = plaintext.upper()

        for _ in range(self.rounds):
            data = self.sub(data)
            data = self.flip(data)
            data = self.shift(data)

        return data

    def decrypt(self, ciphertext: str):
        data = ciphertext.upper()
        
        for _ in range(self.rounds):
            data = self.invshift(data)
            data = self.invflip(data)
            data = self.invsub(data)
            
        return data
    
    
sub = Stacker('abced')

pts = []
with open("./plain.txt") as f:
    references = f.read().split("\n")
    for line in references:
        plain = "".join(re.findall(r'[a-zA-Z]', line))
        pts.append(plain.upper())

cts = []
with open("./plain.enc", "r") as h:
    for line in h.read().split("\n"):
        plain = "".join(re.findall(r'[a-zA-Z]', line))
        cts.append(plain)


def brute():
    for len_guess in trange(2, 15):
        for x_guess in range(len(CHARSET)):
            known = ""
            while len(known) != len_guess:
                cur_len = len(known)
                for c in CHARSET:
                    pw_guess = known + c + 'A' * (len_guess - len(known) - 1)
                    assert(len(pw_guess) == len_guess)
                    sub.reset(pw_guess, x_guess)
                    f = True
                    for pt, ct in zip(pts, cts):
                        dec = sub.decrypt(ct)
                        if not f: break
                        for i in range(0, len(pt), len_guess):
                            for j in range(i, i + len(known) + 1):
                                if j >= len(pt): break
                                if dec[j] != pt[j]:
                                    f = False
                                    break
                    if f:
                        known += c
                        print(f"FOUND: {known}")
                        sub.__init__(known)
                        break
                if cur_len == len(known):
                    break
            if len(known) == len_guess:
                print(f'FOUND: {known}')
                return
brute()
flag_enc = "NLPDNZGMMEPPXQNYRJDVKWJENTKLLKWJGRK"
print(f"slashroot8{{{sub.decrypt(flag_enc)}}}")

## Cry/Sprei Gratis
Chall cukup straightforward, sepertinya hanya RSA dengan beberapa leak fungsi dari secret bits.

from Crypto.Util.number import *
from base64 import urlsafe_b64encode
from hashlib import sha256
import secrets

SPREI = "slashroot{omke_gas}"# if "SPREI" not in os.environ else os.environ['SPREI']

class OMKE_GAS:
    def __init__(self, bit):
        self.bit = bit
        self.p = getPrime(self.bit//2)
        self.q = getPrime(self.bit//2)
        self.n = self.p * self.q
        self.e = 0x10001
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    
    def fufufafa(self, x, y):
        a = x ^ (y >> 25)
        b = y ^ (x << 52) & ((1 << 64) - 1)
        a ^= ((b << 11) & ((1 << 64) - 1)) | 0xf0f0fAfAf0f0fAfA
        b ^= ((a >> 17) & ((1 << 64) - 1)) & 0xf4f4f4f4f0f0f0f0
        return a, b

    def makan_gratis(self, m):
        h = int(sha256(m.encode()).hexdigest(), 16)
        mp = pow(h, self.d % (self.p-1), self.p)
        mq = pow(h, self.d % (self.q-1), self.q)
        c = mq + self.q * ((mp - mq) * pow(self.q, -1, self.p) % self.p)
        a, b = self.fufufafa(mq >> ((self.bit//2)-64), secrets.randbits(64))
        return b'.'.join([urlsafe_b64encode(long_to_bytes(i)).strip(b'=') for i in [c, a, b]]).decode()
    
    def sprei_gratis(self, sprei):
        self.cipher = pow(bytes_to_long(sprei), self.e, self.n)
        return b'.'.join([urlsafe_b64encode(long_to_bytes(i)).strip(b'=') for i in [self.cipher, self.n]]).decode()    

chal = OMKE_GAS(1024)

print("plizzzz wokkk 😣😣😢😢 aku mau sprei gratis ibuku itu agak miskin 😭😭😭💔💔 kok saya liat livestream mu kenapa kamu ketawa hah 😡😡😡😡‼️‼️mana sprei gratis yang kau janjikan itu hah disaat pendukungmu oke gas oke gas 😝😝😝kamu malah ketawa 😂😂🤣 itu ga rizzpek banget wok😂😂 dan jangan lupa makanan siang gratisnya wok 😂😂😅😅😅")
print(f"Sprei gratis tapi dienkripsi fufufafa: {chal.sprei_gratis(SPREI)}")

while True:
    choice = int(input("Ketik 1 untuk dapat makan siang gratis: "))
    if choice == 1:
        m = input("Request lauk makan siang gratis: ")
        print(f"Vocer makan siang gratis tapi dienkripsi fufufafa: {chal.makan_gratis(m)}")
    else:
        break

Pertama, perhatikan fungsi fufufafa. Dua operasi xor terakhir dapat di-reverse dengan mudah, cukup dengan melakukan xor yang sama. Dari situ, kita peroleh `a = x ^ (y >> 25)`. Dengan asumsi x dan y adalah 64 bit, kita dapat peroleh 39 bit dari x.

Pada fungsi makan_gratis, kita diberikan nilai a dan b dari output fufufafa, dan nilai `c = mq + q * pi` untuk suatu `pi < p`. Welp, sepertinya ini approximate GCD klasik, dimana kita diberikan 39 bit MSB dari residu mq. Solver sebenarnya dapat dioptimasi lebih lanjut dengan memanfaatkan nilai `n = pq` dalam lattice reduction, tetapi setelah mencoba reduksi dengan 80 equation `c`, jawaban sudah diperoleh sehingga optimasi lebih lanjut tidak diperlukan.

### Solver

from secrets import randbits
from Crypto.Util.number import *
from base64 import urlsafe_b64encode, urlsafe_b64decode
from libnum import n2s, s2n
from hashlib import sha256
from sage.all import *
from azunyan.conn import remote
import secrets

r = remote('ctf.slashrootctf.id', 10011, level='debug')

def fufufafa(x, y):
    a = x ^ (y >> 25)
    b = y ^ (x << 52) & ((1 << 64) - 1)
    a ^= ((b << 11) & ((1 << 64) - 1)) | 0xf0f0fAfAf0f0fAfA
    b ^= ((a >> 17) & ((1 << 64) - 1)) & 0xf4f4f4f4f0f0f0f0
    return a, b

def invfufufafa(a, b):
    b ^= ((a >> 17) & ((1 << 64) - 1)) & 0xf4f4f4f4f0f0f0f0
    a ^= ((b << 11) & ((1 << 64) - 1)) | 0xf0f0fAfAf0f0fAfA
    return a

ms = [str(i) for i in range(80)]
ct = []

def deserialize(ct: str):
    nums = ct.split('.')
    res = []
    for num in nums:
        res.append(s2n(urlsafe_b64decode(num + '=======')))
    return res

def makan(s: str):
    r.sendlineafter(b'Ketik 1 untuk dapat makan siang gratis:', b'1')
    r.sendlineafter(b'Request lauk makan siang gratis:', s.encode())
    r.recvuntil(b'Vocer makan siang gratis tapi dienkripsi fufufafa: ')
    return r.recvtype(str)

r.recvuntil(b'Sprei gratis tapi dienkripsi fufufafa:')
sprei = r.recvtype(str)
ctflag, n  = deserialize(sprei)

lost_bits = 25
l = 64
for m in ms:
    c, a, b = deserialize(makan(m))
    a = invfufufafa(a, b)
    a = (a >> (l - lost_bits)) << (l - lost_bits)
    
    a = a << (512 - 64)
    ct.append(c - a)
    

# approximate gcd
arr = [[1] + [ct[i] for i in range(1, len(ct))]]
arr += [[0 if i!=j else -ct[0] for j in range(len(ct))] for i in range(1, len(ct))]
B = matrix(ZZ, arr)
B = B.LLL()

q = abs(B[0, 0])
p = (ct[0]) // q
p = int(p)
print(p.bit_length())
print(n % p == 0)
q = n // p
d = pow(0x10001, -1, (p-1) * (q-1))
d = int(d)
print(n2s(int(pow(ctflag, d, n))))