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_secretas 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_stringssifting 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] == 1Initialize 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 BIf 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_secretWe 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)
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
getStarSightingsfunction always return ≥ 2 elements - Call the
upgradeToAndCallfunction (it’s from UUPSUpgradeable.sol, that’s why there’s the_authorizeUpgradefunction) and upgrade the kernel to our fake kernel contract. - solved!
