HackTheBox University 2024 Writeups: Hardest Crypto and Hardest Blockchain

I was quite proud to be able to solve all the Crypto and Blockchain challenges, I decided to make a writeup for two challs, Crypto — Clutch (~15 solves) and Blockchain — Stargazer (~30 solves), both of which are the challenges with least amount of solves.

The crypto solve especially allows my team to secure the top 10 place. It also allows me to become the MVP in this CTF.

Cryptography— Clutch

We are given the following script, which claims that it was an implementation of the Frame-based QKD protocol (Later we will learn that you don’t really need to understand the Quantum stuff to solve this so don’t be so intimidated)

from hashlib import sha256
from random import uniform
import json

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES

from secret import SECRET_MESSAGE
from alice import Alice
from bob import Bob

def json_print(message):
    print(json.dumps(message))

# Python implementation of the Frame-based QKD protocol described here : https://www.mdpi.com/2073-8994/12/6/1053
class QKD:
    def __init__(self, Alice, Bob, pairs = 256, security = 256):
        self.Alice = Alice(pairs)
        self.Bob = Bob(uniform(0, 1))

        self.security = security

    def check_status(self):
        return {"status": "OK", "QBER": self.Bob.depolarizing_probability}

    def execute(self):
        pairs = self.Alice.prepare()
        double_matchings = self.Bob.measure(pairs)

        if not len(double_matchings):
            return {"error": "Key exchange failed, there's no double matchings. Retrying..."}
    
        frames, usable_frames, auxiliary_frames = self.Alice.compute_frames(double_matchings)

        if not len(frames):
            return {"error": "Key exchange failed, there's no frames. Retrying..."}

        bob_sifting_strings = self.Bob.compute_sifting_strings(frames)

        alice_sifting_strings, ambiguous_frames = self.Alice.error_correction(usable_frames, auxiliary_frames, bob_sifting_strings)

        alice_key = self.Alice.generate_shared_key(frames, usable_frames, ambiguous_frames, alice_sifting_strings, bob_sifting_strings)

        bob_key = self.Bob.generate_shared_key(frames, ambiguous_frames, bob_sifting_strings)

        if len(alice_key) < self.security:
            return {"error": "Key exchange failed, the instance does not satisfy the security requirements. Retrying..."}

        if alice_key != bob_key:
            return {"error": "Key exchange failed, both keys are not equal. Retrying..."}

        bob_sifting_strings = list(bob_sifting_strings.values())

        public = {
            "double_matchings": double_matchings,
            "frames": frames,
            "sifting_strings": bob_sifting_strings,
            "ambiguous_frames": ambiguous_frames
        }

        self.shared_key = alice_key.encode()

        return public

    def decrypt_command(self, encrypted_command):
        key = sha256(self.shared_key).digest()

        cipher = AES.new(key, AES.MODE_ECB)
        command = unpad(cipher.decrypt(encrypted_command), 16)
    
        return command.decode()


def main():
    json_print({"info": "To all ships of The Frontier Board, use your secret key to get the coordinates of The Starry Spurr"})
    
    json_print({"info": "Initializing QKD..."})

    while True:
        qkd = QKD(Alice, Bob)
        public = qkd.execute()
        
        json_print(public)

        if "error" not in public:
            status = qkd.check_status()
            json_print(status)
            break

    json_print({"info": "Initialization completed. Only trusted ships can send valid commands"})

    while True:
        try:
            data = json.loads(input("> "))
            encrypted_command = bytes.fromhex(data["command"])
            assert len(encrypted_command) % 16 == 0
        except:
            json_print({"error": "Invalid input. Please, try again"})
            break
            continue

        command = qkd.decrypt_command(encrypted_command)
        
        if command == "OPEN THE GATE":
            FLAG = open('flag.txt').read()
            json_print({"info": f" Welcome to The Frontier Board, the coordinates of The Starry Spurr are {SECRET_MESSAGE}{FLAG}"})
            exit()

        else:
            json_print({"error": "Unknown command. Please, try again"})


if __name__ == '__main__':
    main()

So reading through some keywords we can see that they’re trying to generate a shared key, which means that this is some sort of a key exchange protocol.

One thing that instantly caught my eye is how Bob generates the shared key

bob_key = self.Bob.generate_shared_key(frames, ambiguous_frames, bob_sifting_strings)

Because all the parameters appears to be public

public = {
    "double_matchings": double_matchings,
    "frames": frames,
    "sifting_strings": bob_sifting_strings,
    "ambiguous_frames": ambiguous_frames
}

However, when we actually look at the generate_shared_key function, apparently it does use some internal variables

def generate_shared_key(self, frames, ambiguous_frames, sifting_strings):
    shared_secret = ""

    for frame in frames:
        if frame in ambiguous_frames:
            continue

        else:
            basis_orientation = (self.measurement_basis[frame[0]], self.measurement_basis[frame[1]])
            measurement_result = BOB_MR_DERIVATION[basis_orientation]
            shared_secret += KEY_DERIVATION[sifting_strings[frame]][measurement_result]

    return shared_secret

as you can see, they are using a variable self.measurement_basis which we don’t know, but everything else is known! So if we can somehow get this measurement_basis thing we can easily solve the challenge, but how?

We can see that the measurement basis is generated randomly, the value is either X or Z and it is only used for some quantum stuff

def measure(self, pairs):
    ...
    ...
    
    for i in range(len(pairs)):
        basis = randbits(1)
        if basis:
            # Measurement in "X" basis
            pairs[i][0].h(0)
            pairs[i][1].h(0)
        ...            
        ...
        self.measurement_basis[i] = "X" if basis else "Z"

However the measurement_basis is also used somewhere else, and it relates to the public parameters. Let’s take a look at how sifting strings are generated

def compute_sifting_bits(self, frame):
    sifting_bits = {
        "X": 0, 
        "Z": 0
    }    
    for pair in frame:
        sifting_bits[self.measurement_basis[pair]] ^= int(self.measurement_results[pair][0])        
    return ''.join(map(str, sifting_bits.values()))

def compute_measured_bits(self, frame):
    measured_bits = []
    for pair in frame:
        measured_bits.append(self.measurement_results[pair][0]) # since both bits are equal due to the double matching event
    return ''.join(measured_bits)
        
def compute_sifting_strings(self, frames):
    sifting_strings = {}
    for frame in frames:
        sifting_bits = self.compute_sifting_bits(frame)
        measured_bits = self.compute_measured_bits(frame)
        sifting_strings[frame] = f"{sifting_bits},{measured_bits}"
    return sifting_strings

sifting strings are generated by concatenating two things, a sifting bits and measured bits, the measured bits are just measurement_results but the sifting bits are more interesting.

Before we continue I’m going to make some data clear, you might be confused what a frame or a pair look like, you can analyze it by reading the paper or looking at the public parameters, but simply put a frame is just a pair of pairs, and the definition of a pair here doesn’t really matter. (but in case you’re curious its just two qubits that are measured with the same basis and have the same result (since it only use double_matchings) so it doesn’t really matter, we can treat them as one qubit)

A pair is represented by a single number, so a frame is an array with two numbers on it like [176, 248] etc.

Now back to the sifting bits, a sifting bits is generated by xor-ing the measurement result of each pair to their corresponding basis, consider the following scenario

frame = [123, 456]
measurement_basis[123] == X
measurement_result[123] == 1

measurement_basis[456] == Z
measurement_result[456] == 1

Initialize the sifting bits with both X and Z value to 0, then xor all the pair with X as basis with their result, which means the result will be 0 ^ 1 (from pair 123), and then doing the same with the Z basis, which also makes it 1, the sifting bits will be the concatenation of the two, which makes it 11

Now suppose that the basis for pair 456 is also X, it will make the result to be 0 ^ 1 ^ 1 which will be 0, so the result will be 00

First Breakthrough

From the sifting string alone we can see that we can somehow create some sort of relation between the measurement_basis and measurement_result, in fact, consider if ALL sifting strings have the measured bits/measurement result of 11 (THIS IS SOME CRAZY FORESHADOWING BTW) we can then create the following relation:

If the frame [A, B] has the sifting string 00,11 -> basis A == basis B
If the frame [A, B] has the sifting string 11,11 -> basis A != basis B

If you don’t understand why, go back to the example above where I explained both scenario

But you might be wondering, “well there is no way the entire sifting string is just ??,11 right? if there exist a pair where the measured bits is not 11 then this is just useless”

Well if you simply look at the entire sifting string you will notice that yes, there exist a frame where the sifting string is not ??,11 . But that’s not the end of the story, admittedly I didn’t read through the entire source code but I ended up experimenting with the result and find something interesting

Second Breakthrough

Let’s take a look again at Bob’s generate_shared_key function

def generate_shared_key(self, frames, ambiguous_frames, sifting_strings):
    shared_secret = ""

    for frame in frames:
        if frame in ambiguous_frames:
            continue

        else:
            basis_orientation = (self.measurement_basis[frame[0]], self.measurement_basis[frame[1]])
            measurement_result = BOB_MR_DERIVATION[basis_orientation]
            shared_secret += KEY_DERIVATION[sifting_strings[frame]][measurement_result]

    return shared_secret

We can see that apparently not all frames are being used, there are something called ambiguous_frames, if a frame is in this ambiguous_frames thing, it would not count towards generating the shared secret

That being said let’s see what happens when we only take non-ambiguous frames and look at their sifting strings

a = ... # the public variable
frames = a['frames']
ambiguous = a['ambiguous_frames']
sifting = a['sifting_strings']
for i,j in zip(frames, sifting):
    if i not in ambiguous:
        print(i, j)

Taking only non-ambiguous frames, we can see that all of the sifting strings have the measured bits of “11”

I was pleasantly surprised when I see this, I’m not sure how this happened (it might be some complicated implementation thing) but with this we can now apply our previous breakthrough and create these relations, using z3 we can solve for the entire measurement_basis and recover the shared_key to get the flag!

a = ...
frames = a['frames']
ambiguous = a['ambiguous_frames']
sifting = a['sifting_strings']

from z3 import *
ind = [BitVec('ind_%d' % i, 1) for i in range(max(a['double_matchings'])+1)]
s = Solver()

usedsifting = []
usedframe = []
for i,j in zip(frames, sifting):
    if i not in ambiguous:
        usedframe.append(i)
        usedsifting.append(j)
        print(i, j)
        if j[:2] == "11":
            s.add(ind[i[0]] != ind[i[1]])
        elif j[:2] == "00":
            s.add(ind[i[0]] == ind[i[1]])
s.check()
m = s.model()

from helpers import *
shared_secret = ""
for s,f in zip(usedsifting,usedframe):
    first = 'XZ'[m[ind[f[0]]].as_long()]
    second = 'XZ'[m[ind[f[1]]].as_long()]
    basis_orientation = (first, second)
    measurement_result = BOB_MR_DERIVATION[basis_orientation]
    shared_secret += KEY_DERIVATION[s][measurement_result]

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

key = sha256(shared_secret.encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
cmd = pad(b"OPEN THE GATE", 16)
enc = aes.encrypt(cmd)
print(enc.hex())

Unfortunately the after party is over so I can’t really show you the output but it works during the CTF

Blockchain — Stargazer

I will update this blog post later for full writeup but TL;DR:

• Find a used ticket (check the logs) and take their signature (r, s)
• calculate (r, -s mod n) for a new valid signature and create your own ticket
• Create a fake StargazerKernel contract where the getStarSightings function always return ≥ 2 elements
• Call the upgradeToAndCall function (it’s from UUPSUpgradeable.sol, that’s why there’s the _authorizeUpgrade function) and upgrade the kernel to our fake kernel contract.
• solved!