# HTB Business CTF 2024: The Vault Of Hope

Write-up for Crypto Challenges
<!--more-->
## eXciting Outpost Recon
**source.py**

from hashlib import sha256

import os

LENGTH = 32


def encrypt_data(data, k):
    data += b'\x00' * (-len(data) % LENGTH)
    encrypted = b''

    for i in range(0, len(data), LENGTH):
        chunk = data[i:i+LENGTH]

        for a, b in zip(chunk, k):
            encrypted += bytes([a ^ b])

        k = sha256(k).digest()

    return encrypted


key = os.urandom(32)

with open('plaintext.txt', 'rb') as f:
    plaintext = f.read()

assert plaintext.startswith(b'Great and Noble Leader of the Tariaki')       # have to make sure we are aptly sycophantic

with open('output.txt', 'w') as f:
    enc = encrypt_data(plaintext, key)
    f.write(enc.hex())

**output.txt**

fd94e649fc4c898297f2acd4cb6661d5b69c5bb51448687f60c7531a97a0e683072bbd92adc5a871e9ab3c188741948e20ef9afe8bcc601555c29fa6b61de710a718571c09e89027413e2d94fd3126300eff106e2e4d0d4f7dc8744827731dc6ee587a982f4599a2dec253743c02b9ae1c3847a810778a20d1dff34a2c69b11c06015a8212d242ef807edbf888f56943065d730a703e27fa3bbb2f1309835469a3e0c8ded7d676ddb663fdb6508db9599018cb4049b00a5ba1690ca205e64ddc29fd74a6969b7dead69a7341ff4f32a3f09c349d92e0b21737f26a85bfa2a10d

Đọc source ta nhận thấy plaintext được xor với các key 32 bytes, ta có $key' = sha(key)$ nên từ $key_0$ ta có thể gen ra các key còn lại và lấy flag.
Việc lấy $key_0$ khá dễ dàng vì ta đã biết được đoạn đầu của plaintext là `b'Great and Noble Leader of the Tariaki'`

**script:**

from pwn import xor
from hashlib import sha256
enc = bytes.fromhex("fd94e649fc4c898297f2acd4cb6661d5b69c5bb51448687f60c7531a97a0e683072bbd92adc5a871e9ab3c188741948e20ef9afe8bcc601555c29fa6b61de710a718571c09e89027413e2d94fd3126300eff106e2e4d0d4f7dc8744827731dc6ee587a982f4599a2dec253743c02b9ae1c3847a810778a20d1dff34a2c69b11c06015a8212d242ef807edbf888f56943065d730a703e27fa3bbb2f1309835469a3e0c8ded7d676ddb663fdb6508db9599018cb4049b00a5ba1690ca205e64ddc29fd74a6969b7dead69a7341ff4f32a3f09c349d92e0b21737f26a85bfa2a10d")
  

plaitext = b"Great and Noble Leader of the Tariaki"

key = xor(plaitext, enc)[:32]

def decrypt(data, k):
    LENGTH = 32
    plaintext = b''

    for i in range(0, len(data), LENGTH):
        chunk = data[i:i+LENGTH]

        for a, b in zip(chunk, k):
            plaintext += bytes([a ^ b])

        k = sha256(k).digest()

    return plaintext

print(decrypt(enc, key))

## Living with Elegance
**server.py**

from secrets import token_bytes, randbelow
from Crypto.Util.number import bytes_to_long as b2l

class ElegantCryptosystem:
    def __init__(self):
        self.d = 16
        self.n = 256
        self.S = token_bytes(self.d)

    def noise_prod(self):
        return randbelow(2*self.n//3) - self.n//2

    def get_encryption(self, bit):
        A = token_bytes(self.d)
        b = self.punc_prod(A, self.S) % self.n
        e = self.noise_prod()
        if bit == 1:
            return A, b + e
        else:
            return A, randbelow(self.n)
    
    def punc_prod(self, x, y):
        return sum(_x * _y for _x, _y in zip(x, y))

def main():
    FLAGBIN = bin(b2l(open('flag.txt', 'rb').read()))[2:]
    crypto = ElegantCryptosystem()

    while True:
        idx = input('Specify the index of the bit you want to get an encryption for : ')
        if not idx.isnumeric():
            print('The index must be an integer.')
            continue
        idx = int(idx)
        if idx < 0 or idx >= len(FLAGBIN):
            print(f'The index must lie in the interval [0, {len(FLAGBIN)-1}]')
            continue
        
        bit = int(FLAGBIN[idx])
        A, b = crypto.get_encryption(bit)
        print('Here is your ciphertext: ')
        print(f'A = {b2l(A)}')
        print(f'b = {b}')


if __name__ == '__main__':
    main()

Flag sẽ được chuyển thành binary. Khi ta gửi vào index của Flag_bin:
Ta có:
- `b = self.punc_prod(A, self.S) % self.n`
- `e = self.noise_prod() = randbelow(2*self.n//3) - self.n//2`
- Nếu như đó là bit 0: thì trả về $b' = b + e$ như vậy thì trường hợp này nó có thể trả về giá trị $b'<0$ hoặc $b'>0$
- Nếu như đó là bit 1: thì trả về `b = randbelow(self.n)` một giá trị bé hơn n

Ta có thể dựa vào đó để biết chính xác các bit của flag bằng cách spam một vị trí nhiều lần và kiểm tra kết quả đầu ra.
Sau khi chạy đi chạy lại thì ta biết được độ dài của `Flag_bin = 427`
Ta có một script siêu đẹp của anh Quốc, ở đây có một trick để gửi đi tất cả payload cùng một lúc và tránh bị tình trạng delay server.

**script:**

from pwn import *
from tqdm import tqdm

conn = remote('83.136.252.165', 59718)
l = 471

flag = ['0']*l
payloads = b''

for j in range(l):
    payload = b''
    for i in range(30):
        payload += str(j).encode() + b'\n'
    payloads += payload 

conn.recvuntil(b'Specify the index of the bit you want to get an encryption for : ')
conn.sendline(payloads[:-1])

for ind in tqdm(range(l)):
    for i in range(30):
        conn.recvuntil(b'A = ')
        A = int(conn.recvline().strip().decode())
        conn.recvuntil(b'b = ')
        b = int(conn.recvline().strip().decode())
        if b < 0:
            flag[ind] = '1'
        
from Crypto.Util.number import *
bf = ''.join(flag)
bf = long_to_bytes(int(bf, 2))
print(bf)

## Bloom Bloom
**source.py**

from random import randint, shuffle
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from secret import *
import os

assert sha256(KEY).hexdigest().startswith('786f36dd7c9d902f1921629161d9b057')

class BBS:
    def __init__(self, bits, length):
        self.bits = bits
        self.out_length = length

    def reset_params(self):
        self.state = randint(2, 2 ** self.bits - 2)
        self.m = getPrime(self.bits//2) * getPrime(self.bits//2) * randint(1, 2)
    
    def extract_bit(self):
        self.state = pow(self.state, 2, self.m)
        return str(self.state % 2)

    def gen_output(self):
        self.reset_params()
        out = ''
        for _ in range(self.out_length):
            out += self.extract_bit()
        return out

    def encrypt(self, msg):
        out = self.gen_output()
        key = sha256(out.encode()).digest()
        iv = os.urandom(16)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        return (iv.hex(), cipher.encrypt(pad(msg.encode(), 16)).hex())

encryptor = BBS(512, 256)

enc_messages = []
for msg in MESSAGES:
    enc_messages.append([encryptor.encrypt(msg) for _ in range(10)])

enc_flag = AES.new(KEY, AES.MODE_ECB).encrypt(pad(FLAG, 16))

with open('output.txt', 'w') as f:
    f.write(f'{enc_messages}\n')
    f.write(f'{enc_flag.hex()}\n')

File output.txt khá dài nên mình không để ở đây. Mỗi `msg` trong `MESSAGES` được mã hóa 10 lần bằng AES với mode là EBC. Nhưng khóa được gen bằng `class BBC()`.

class BBS:
    def __init__(self, bits, length):
        self.bits = bits
        self.out_length = length

    def reset_params(self):
        self.state = randint(2, 2 ** self.bits - 2)
        self.m = getPrime(self.bits//2) * getPrime(self.bits//2) * randint(1, 2)
    
    def extract_bit(self):
        self.state = pow(self.state, 2, self.m)
        return str(self.state % 2)

    def gen_output(self):
        self.reset_params()
        out = ''
        for _ in range(self.out_length):
            out += self.extract_bit()
        return out

    def encrypt(self, msg):
        out = self.gen_output()
        key = sha256(out.encode()).digest()
        iv = os.urandom(16)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        return (iv.hex(), cipher.encrypt(pad(msg.encode(), 16)).hex())

Key của ta chỉ gồm các chữ số 0 và 1 ta có thể nhận thấy rõ ở hàm `extract_bit`.
Ta có:
- `state = randint(2, 2 ** self.bits - 2)`
- `m = getPrime(self.bits//2) * getPrime(self.bits//2) * randint(1, 2)`
- giả sử `state` và `m` cùng chẵn thì các `state` tiếp theo cùng chẵn và ta sẽ nhận được các bit `0`. Và xác xuất để xảy ra là rất cao mình đã chạy thử thì thấy cũng khá cao đấy.
Mình sẽ sử dụng key dự đoán để xem xem nó ra như nào:

from output import *
from Crypto.Cipher import AES
from hashlib import sha256

out = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"

key_sha = sha256(out.encode()).digest()

lst = []

for i in enc_messages:
    for j in i:
        try:
            iv = bytes.fromhex(j[0])
            cipher = AES.new(key_sha, AES.MODE_CBC, iv)
            lst.append(cipher.decrypt(bytes.fromhex(j[1])).decode())
            break
        except:
            pass

for i in lst:
    print(i, end='\n\n')

Ta được như thế này:

Welcome! If you see this you have successfully decrypted the first message. To get the symmetric key that decrypts the flag you need to do the following:

1. Collect all 5 shares from these messages
2. Use them to interpolate the polynomial in a finite field that will be revealed in another message
3. Convert the constant term of the polynomial to bytes and use it to decrypt the flag. Here is your first share!

Share#1#: (1, 27006418753792019267647881709336369603809025474153761185424552629526746515909)

Keep up the good work! Offered say visited elderly and. Waited period are played family man formed. He ye body or made on pain part meet. You one delay nor begin our folly abode. By disposed replying mr me unpacked no. As moonlight of my resolving unwilling. Turned it up should no valley cousin he. Speaking numerous ask did horrible packages set. Ashamed herself has distant can studied mrs.

Share#2#: (2, 76590454267924193303526931251420387908730989759486987968207839464816350274449)

Only a few more are left! Of be talent me answer do relied. Mistress in on so laughing throwing endeavor occasion welcomed. Gravity sir brandon calling can. No years do widow house delay stand. Prospect six kindness use steepest new ask. High gone kind calm call as ever is. Introduced melancholy estimating motionless on up as do. Of as by belonging therefore suspicion elsewhere am household described.

Share#3#: (3, 67564500698667187837224046797217120599664632018519685208508601443605280795068)

You are almost there! Not him old music think his found enjoy merry. Listening acuteness dependent at or an. Apartments thoroughly unsatiable terminated sex how themselves. She are ten hours wrong walls stand early. Domestic perceive on an ladyship extended received do. Why jennings our whatever his learning gay perceive. Is against no he without subject. Bed connection unreserved preference partiality not unaffected.

Share#4#: (4, 57120102994643471094254225269948720992016639286627873340589938545214763610538)

Congratulations!!! Not him old music think his found enjoy merry. Listening acuteness dependent at or an. Apartments thoroughly unsatiable terminated how themselves. She are ten hours wrong walls stand early. Domestic perceive on an ladyship extended received do. You need to interpolate the polynomial in the finite field GF(88061271168532822384517279587784001104302157326759940683992330399098283633319).
Share#5#: (5, 87036956450994410488989322365773556006053008613964544744444104769020810012336)

Qua đoạn MESSAGES ta có được 5 điểm và có gợi ý là
`Use them to interpolate the polynomial in a finite field that will be revealed in another message`. Ta cần tạo một đa thức chứa 5 điểm đó trên trường hữu hạn GF(88061271168532822384517279587784001104302157326759940683992330399098283633319).

Phương trình có dạng:
$y = a * x ^ 4 + b * x ^ 3 + c * x ^ 2 + d * x + e$
Việc của ta là tìm ra hệ số của phương trình này và lấy $e$ làm key để lấy FLAG.
Ở đây có 2 cách giải là sử dụng matrix hoặc đa thức Lagrange được implement sẵn trong sagemath.

**Sage**

from Crypto.Util.number import *
from hashlib import sha256
from output import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import *

P = GF(88061271168532822384517279587784001104302157326759940683992330399098283633319)
s1 = (1, 27006418753792019267647881709336369603809025474153761185424552629526746515909)
s2 = (2, 76590454267924193303526931251420387908730989759486987968207839464816350274449)
s3 = (3, 67564500698667187837224046797217120599664632018519685208508601443605280795068)
s4 = (4, 57120102994643471094254225269948720992016639286627873340589938545214763610538)
s5 = (5, 87036956450994410488989322365773556006053008613964544744444104769020810012336)

R = P['x']
e = R.lagrange_polynomial([s1, s2, s3, s4, s5]).constant_coefficient()

KEY = long_to_bytes(int(e))
assert sha256(KEY).hexdigest().startswith('786f36dd7c9d902f1921629161d9b057')

flag = AES.new(KEY, AES.MODE_ECB).decrypt(bytes.fromhex(enc_flag))
print(unpad(flag, 16).decode())

## Not that random
**server.py**

from Crypto.Util.number import *
from Crypto.Random import random, get_random_bytes
from hashlib import sha256
from secret import FLAG

def success(s):
    print(f'\033[92m[+] {s} \033[0m')

def fail(s):
    print(f'\033[91m\033[1m[-] {s} \033[0m')

MENU = '''
Make a choice:

1. Buy flag (-500 coins)
2. Buy hint (-10 coins)
3. Play (+5/-10 coins)
4. Print balance (free)
5. Exit'''

def keyed_hash(key, inp):
    return sha256(key + inp).digest()

def custom_hmac(key, inp):
    return keyed_hash(keyed_hash(key, b"Improving on the security of SHA is easy"), inp) + keyed_hash(key, inp)

def impostor_hmac(key, inp):
    return get_random_bytes(64)

class Casino:
    def __init__(self):
        self.player_money = 100
        self.secret_key = get_random_bytes(16)
    
    def buy_flag(self):
        if self.player_money >= 500:
            self.player_money -= 500
            success(f"Winner winner chicken dinner! Thank you for playing, here's your flag :: {FLAG}")
        else:
            fail("You broke")
    
    def buy_hint(self):
        self.player_money -= 10
        hash_input = bytes.fromhex(input("Enter your input in hex :: "))
        if random.getrandbits(1) == 0:
            print("Your output is :: " + custom_hmac(self.secret_key, hash_input).hex())
        else:
            print("Your output is :: " + impostor_hmac(self.secret_key, hash_input).hex())

    def play(self):
        my_bit = random.getrandbits(1)
        my_hash_input = get_random_bytes(32)

        print("I used input " + my_hash_input.hex())

        if my_bit == 0:
            my_hash_output = custom_hmac(self.secret_key, my_hash_input)
        else:
            my_hash_output = impostor_hmac(self.secret_key, my_hash_input)

        print("I got output " + my_hash_output.hex())

        answer = int(input("Was the output from my hash or random? (Enter 0 or 1 respectively) :: "))

        if answer == my_bit:
            self.player_money += 5
            success("Lucky you!")
        else:
            self.player_money -= 10
            fail("Wrong!")

    def print_balance(self):
        print(f"You have {self.player_money} coins.")



def main():
    print("Welcome to my online casino! Let's play a game!")
    casino = Casino()

    while casino.player_money > 0:
        print(MENU)
        option = int(input('Option: '))

        if option == 1:
            casino.buy_flag()
                
        elif option == 2:
            casino.buy_hint()
                
        elif option == 3:
            casino.play()
                
        elif option == 4:
            casino.print_balance()
            
        elif option == 5:
            print("Bye.")
            break
        
    print("The house always wins, sorry ):")

if __name__ == '__main__':
    main()

Đọc source code ta nhận thấy server có những chức năng như sau:
- play(): mỗi lần chơi ta cần đoán được đầu ra là custom_hmac() hay impostor_hmac() bằng cách gửi đi giá trị 1 hoặc không. Với mỗi lần đoán đúng ta sẽ được cộng thêm vào 5 đồng đoán sai thì bị trừ đi 10 đồng.
- buy(): Khi có 500 đồng thì ta có thể mua Flag.
- buy_hint(): mỗi lần sài sẽ mất 10 đồng

def buy_hint(self):
        self.player_money -= 10
        hash_input = bytes.fromhex(input("Enter your input in hex :: "))
        if random.getrandbits(1) == 0:
            print("Your output is :: " + custom_hmac(self.secret_key, hash_input).hex())
        else:
            print("Your output is :: " + impostor_hmac(self.secret_key, hash_input).hex())

Với input ta nhập vào thì nó sẽ trả về output sau đi qua custom_hmac hoặc impostor_hmac.

**custom_hmac()**

def custom_hmac(key, inp):
    return keyed_hash(keyed_hash(key, b"Improving on the security of SHA is easy"), inp) + keyed_hash(key, inp)

trả về kết quả như trên.
**impostor_hmac()**

def impostor_hmac(key, inp):
    return get_random_bytes(64)

chỉ trả về các bytes ngẫu nhiên không có quy luật nào cả.

Qua đó ta có thể dựa vào **custom_hmac()** để check output thuộc loại nào. Với input cho sẵn ta có thể tính toán chính xác được ouput khi đi qua **custom_hmac()**. Nhưng trước tiên ta cần tìm được giá trị của `keyed_hash(key, b"Improving on the security of SHA is easy")`, ta có thể tìm nó bằng chức năng **buy_hint()** với việc truyền vào input là `b"Improving on the security of SHA is easy"`.

Ta cần gửi đến server vài lần để lấy đúng được giá trị của `keyed_hash(key, b"Improving on the security of SHA is easy"`

**script:**

from pwn import *
from hashlib import sha256

io = remote("94.237.49.212", 30279)
payload = b"Improving on the security of SHA is easy"

def keyed_hash(key, inp):
    return sha256(key + inp).digest()

tmp = []
while 1:
    io.recvuntil(b'Option: ')
    io.sendline(b'2')
    io.recvuntil(b':: ')
    io.sendline(payload.hex().encode())
    io.recvuntil(b':: ')
    ans = io.recvuntil(b'\n')[:-1].decode()
    if ans in tmp:
        _hash = bytes.fromhex(ans)[32:]
        break
    else:
        tmp.append(ans)

for i in range(100):
    io.recvuntil(b'Option: ')
    io.sendline(b'3')
    io.recvuntil(b'I used input ')
    my_hash_input = io.recvuntil(b'\n')[:-1].decode()
    my_hash_input = bytes.fromhex(my_hash_input)

    io.recvuntil(b'I got output ')
    my_hash_output = io.recvuntil(b'\n')[:-1].decode()
    my_hash_output = bytes.fromhex(my_hash_output)

    check = keyed_hash(_hash, my_hash_input)
    guess = b'0' if check == my_hash_output[:32] else b'1'
    io.recvuntil(b' :: ')
    io.sendline(guess)

io.recvuntil(b'Option: ')
io.sendline(b'1')
io.interactive()

## Note
Giải này mình khá phế chỉ theo dõi mn giải rồi end giải mình mới bắt đầu giải lại.