“Random nonces? Where we’re going, we don’t need random nonces!” - D. Brown
Category: crypto
Solver: 3mb0, nh1729
Flag: HTB{buzzw0rd_s0up_h45_n3v3r_t45t3d_s0_g00d}
Writeup
For this challenge, we were given a python script that processes the flag and some other file alongside its output and additional files used .
import random
from Crypto.Util.number import bytes_to_long
from functools import reduce
def buzzor(b1, b2):
return bytes([_b1 ^ _b2 for _b1, _b2 in zip(b1, b2)])
def buzzrandom():
return bytes([random.randrange(0, 2) for _ in range(keylen)])
flag = bytes_to_long(open("flag.txt", "rb").read())
buzzwords = open("bee_movie.txt", "rb").read()
keylen = 0xbb
buzzword_soup = [buzzwords[i:i+keylen] for i in range(0, len(buzzwords), keylen)][:-1]
buzzcount = len(buzzword_soup)
with open("output.txt", "w") as f:
while flag:
bit = flag & 1
flag >>= 1
output = ""
for _ in range(0xb):
keycount = random.randrange(buzzcount//4, buzzcount//2)
keys = random.sample(buzzword_soup, keycount)
out = reduce(buzzor, keys)
if bit:
output += out.hex()
else:
output += buzzor(out, buzzrandom()).hex()
f.write(output + "\n")
From the script we learn that every line in the output corresponds to one bit of the flag.
First, an array of ‘buzzwords’ is loaded as bytes objects from the file we are given. Then, for every bit in the flag, if it is a 1, we get the XOR of some random number of random buzzwords. Otherwise, we get the such a value XOR some random data. For every bit of the flag, we are provided with eleven (0xb) of these results.
Thus, we can tell the output generated for a 0 and 1 apart by checking whether out outputs could have been created by XORing of buzzwords. In other words, we want to know whether they are linearly dependent to the buzzwords in a Galois-Field F(2), because XOR is equivalent to adding in F(2).
To accomplish this, we use the fact that the matrix with all the bit vectors of buzzwords as rows maintains its rank when we add linearly dependent rows. We just build such a matrix and for every line in the output, we fill the last 11 rows with the bit vectors of the output. The python modules galois and numpy are used for the calculation of the rank. Thus, we collect all bits of the flag and re-assemple it.
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes
import numpy as np
import galois
def bytes_to_bits(b):
l = bytes_to_long(b)
return [(l >> i) & 1 for i in range(len(b)*8-1,-1,-1)]
def bits_to_bytes(bits, size = 0):
return long_to_bytes(sum((bits[i] << i for i in range(len(bits)))), size)
buzzwords = open("bee_movie.txt", "rb").read()
keylen = 0xbb
keybitlen = 8 * keylen
samples = 0xb #11
buzzword_soup = [buzzwords[i:i+keylen] for i in range(0, len(buzzwords), keylen)][:-1]
buzzcount = len(buzzword_soup)
def solve():
flag_bits = []
GF = galois.GF(2)
print(f'Creating Matrix')
M = GF.Zeros((buzzcount + samples, keybitlen))
print(f'Filling Matrix')
for i in range(buzzcount):
M[i] = bytes_to_bits(buzzword_soup[i])
print(f'Determining original rank')
buzzrank = np.linalg.matrix_rank(M)
print(f'Original rank: {buzzrank}')
with open("output.txt", "r") as f:
for line in f.readlines():
line = bytes.fromhex(line)
for i in range(samples):
M[buzzcount + i] = bytes_to_bits(line[keylen * i : keylen * (i+1)])
newrank = np.linalg.matrix_rank(M)
flag_bits.append(int(buzzrank == newrank))
if (len(flag_bits) % 8) == 0:
print(bits_to_bytes(flag_bits))
return bits_to_bytes(flag_bits).decode()
if __name__ == '__main__':
print(solve())
Other resources
[1] https://en.wikipedia.org/wiki/Rank\_(linear\_algebra)#Main\_definitions
[3]Documentation galois (python module) https://galois.readthedocs.io/en/latest/basic-usage/linear-algebra.html