Vault of Hope: HTB2024 Write-up
I almost missed taking part in the HTB2024:Vault of hope this year, but finally managed to get a few hours one night dedicated to trying out some of these challenges. I was able to solve 2 crypto challenges but didn’t have time for the others due to family visiting. Overall, our team at Microsoft, ranked 15 (we were rank 24 last year) :-)
As always, there are some good lessons to learn for real-world software development. To skip the details of the challenges and jump to the conclusions click here.
Challenge 1: Crypto Bloom Bloom
Summary: Imagine you’re building a web application and you need to encrypt some sensitive data. You need to generate a secret key. You invoke a library from your programming language of choice (such as Crypto.Random in python), which under the hood uses the operating system’s source of entropy (such as /dev/urandom on Linux or BCryptGenRandom on windows etc).
How is that underlying random number generator itself implemented? This challenge gives one such implementation with a few tweaks. (Btw, The Linux kernel’s cryptographic random number generator implementation is in random.c)
In this challenge we’re provided with an implementation of the Blum Blum Shub Pseudo-Random Number Generator (PRNG) that’s used to generate keys for encrypting messages. We’re also provided with the encrypted files and the objective is to decrypt them to reveal the flag.
Primer on Blum-Blum-Shub and Pseudo-Random-Generators:
Blum-Blum-Shub (BBS) is based on Rabin’s one-way function
where M is the product of 2 primes and x is initialized with a random value between (1, M) and must be co-prime to M. The last few bits (typically the Least Significant Bit (LSB) a.k.a parity bit) are used as the ‘outputs’ of the Blum-Blum-Shub PRNG.
How secure is this PRNG? What does Security even mean in this context?
To give a very generalized and informal overview, any adversary could predict a single bit (say the LSB) correctly with 1/2 probability. The PRNG is considered secure if the adversary’s advantage in predicting the LSB is
1/2 + e, where e is negligible. See Pseudo-Random-Generators for more details. In other words, the PRNG is secure if the adversary couldn’t gain any non-negligible advantage in distinguishing the output of the PRNG from a truly random distribution.
Given all this information, how secure is Blum-Blum-Shub?Well, there’s a proof that effectively reduces it’s security to the computational hardness of factoring.
So, as long as we initialize BBS with parameters of appropriate sizes, there’s no computationally feasible way to break the security of this PRNG.
Now, let’s move on to the source code…..
Challenge: (I’ve added some comments within this source to add more context)
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):
# 512 bits
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 = ''
# extract 256 bits after this loop
for _ in range(self.out_length):
out += self.extract_bit()
return out
def encrypt(self, msg):
out = self.gen_output()
print (f"key: {out}")
# key generated using blum-blum-shub cryptosystem
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')Intuition for a solution:
A slightly tweaked version of Blum-Blum-Shub is used to generate cryptographic keys. Every character of the key is generated from a call to extract_bit(), which returns the LSB (i.e. parity bit) from BBS’ internal state ‘x’ after performing the square mod M.
The intuition comes from the definition of self.m inside the reset_params function, where we note that 50% of the time, m is set to 2 * p * q instead of p * q, where p and q are primes 256 bit primes.
Why is this significant? if M is even, then
- if x is odd, then x², x⁴, x⁸… (mod M) will always be odd => parity bit is always 1
- if x is even, then x², x⁴, x⁸… (mod M) will always be even => parity bit is always 0
Solution:
Putting all this together, we see that about 50% of the time, the final symmetric key generated by this modified BBS is either 256 zeros or 256 ones depending on whether the initial random seed was even or odd.
Trying to decrypt all the ciphertexts with both keys of size 256 characters (0000…000 and 11111…111), we’re able to decrypt the messages:
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)Now we’re given 5 shares and asked to interpolate the polynomial in a finite field. We use sage and python to perform lagrange’s polynomial interpolation to recover the key.
Now we use this key to decrypt the flag using AES in ECB mode
def decrypt_flag(key: str, flag: str):
bkey = key.encode()
bflag = bytes.fromhex(flag)
cipher = AES.new(bkey, AES.MODE_ECB)
return cipher.decrypt(bflag)
if __name__ == "__main__":
key = '1_4m_y0ur_k3y_t0_g3t_th3_fl4g123'
flag = '00cc03bebb6756fded9a55e772b665d3f98004163904713b83c0bfed06558e9ce57d1d50409179741b09d5f059d668d5fd7775892e403357200c5c516125cb53451f52d34f08e4e2885588c046360bfc44c84a3a4da194484d2ca414ba01e698221936ea8e372b6a3bf4af1c85a99e54df52b58d6a7a0add3752e88fa928c15d'
print (decrypt_flag(key=key, flag=flag))and we get the Flag: HTB{what_a_cool_random_number_generator_by_bluuuuuum_bluuuuuum_and_shuuuuuub_i_implemented_it_securely_didnt_i?}
Challenge 2: Not That Random
Summary:
If you’ve ever used a Shared Access Signature (SAS), then you’ve definitely used Hash-based Message Authentication Codes (HMAC). A layman’s definition would be that HMAC’s are keyed-hashes used to compute an authentication code or digest against a given message. Under a given key, thee same message would always produce the same HMAC. This is not to be confused with cryptographic hashes (these do not require a secret key). In fact, HMAC’s are constructed using cryptographic hashes, but they offer different properties.
In this challenge, we’re given the source code of a server that implements a “custom (insecure) hmac” scheme using a ‘keyed’ hash as shown below
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)We’re asked to play a game at a Casino, that uses the custom_hmac() internally and returns a 64 byte output value. Our objective is to guess whether this was generated by the custom_hmac() or generated as random numbers.
We start with 100 coins and we need to earn 500 coins to retrieve the flag. Obviously we could make a random guess every time correctly with 1/2 (50%) probability, but since we get only 5 coins as a reward for every valid guess (but lose 10 coins for every wrong guess), we need to guess correctly at least 80 times.
Now let’s look through the source code:
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()Intuition for a solution:
The buy_hint method is the key here — it enables a ‘chosen plaintext’ scenario where we could supply arbitrary plaintext and obtain the value of the custom_hmac() on that plaintext message under the same secret key. (well, with 50% probability since the code seems to flip a coin and return randomness half the times, but you get the point…..)
what if we queried this oracle with the input “Improving on the security of SHA is easy”? Then the output of the custom_hmac is going to have a specific pattern as shown below:
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)
# let t = keyed_hash(key, input)
t = keyed_hash(secret_key, b"Improving on the security of SHA is easy")
p = keyed_hash(t, b"Improving on the security of SHA is easy")
# output of custom_hmac
p || tIn other words, the oracle allowed us to take a peek into ‘t’. Knowing ‘t’, we could compute the keyed_hash using ‘t’ as the key and the same input string “Improving on the security of SHA is easy” and The concatenation of these two values is the output from custom_hmac.
Knowing ‘t’ allows us to build a ‘distinguisher’ against the play scenario. We could use ‘t’ and the random input value generated for that play session, to compute the first 32 bytes of the custom_hmac value. if this matches against the first 32 bytes of the output, then we know that the custom_hmac was used, otherwise the output was random. This gives us a distinguisher with 100% accuracy.
Solution:
We run this solution 81 times (since we started with 100 coins, then lost 10 coins buying the hint, and we need more than 500 coins in total) and then obtain the flag.
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 get_key_from_hint_custom_hash(val: str, inp: bytes = b"Improving on the security of SHA is easy") -> Tuple[bytes, bytes]:
# split the value into leaked key, mac
mac, x_key = bytes.fromhex(val)[0:32], bytes.fromhex(val)[32:]
# assuming we have the 'x_key' which is keyed_hash(key, inp)
# where key is the unknown secret key
y = keyed_hash(x_key, inp).hex()
print (y)
print (mac.hex())
if y == mac.hex():
return (x_key, bytes.fromhex(y))
return None, None
def is_custom_hash(x: bytes, inp: bytes, op: bytes):
# compute custom_hash(x, inp) and compare against first 32 bytes of op
return keyed_hash(x, inp).hex() == op[0:32].hex()
if __name__ == "__main__":
hex_val = input('enter hint:')
key, _ = get_key_from_hint_custom_hash(hex_val)
assert key is not None
inp = input('enter input hex string:')
op = input('enter output hex string:')
print (is_custom_hash(key, bytes.fromhex(inp), bytes.fromhex(op)))
and we get the flag:
What are some real-world lessons from this?
- A Cryptographic Hash is not a Message Authentication Code (MAC), Encryption does not provide Integrity — It’s well known that ‘Rolling your own crypto is not a good idea’. However, it’s equally important to use cryptographic algorithms for the right purpose and to achieve the security properties that the algorithms were designed to guarantee. Tweaking a given algorithm’s usage almost always results in subtle security failures.
- Random Number Generators are crucial for security — we noted this in the previous post from last year as well (click here to read 3 lessons for applied crypto from HTB2023). Crypto-random generators (such as /dev/urandom on Linux) are necessary for generating keys, nonces and even passwords. Using non-cryptographic generators or tweaking crypto-random generators to generate keys, passwords (or anything sensitive really) are not recommended — This leads to biased or predictable random numbers that completely break the security of the system.
References:
- https://hackthebox.com/
- https://en.wikipedia.org/wiki/Blum_Blum_Shub
- https://linux.die.net/man/4/urandom
- https://en.wikipedia.org/wiki/HMAC
- https://en.wikipedia.org/wiki/Pseudorandom_number_generator
- https://github.com/torvalds/linux/blob/master/drivers/char/random.c
- https://learn.microsoft.com/en-us/windows/win32/api/bcrypt/nf-bcrypt-bcryptgenrandom