PBCTF 2021 Writeups

October 13, 2021

crypto writeup

PBCTF 2021 Writeups

Crypto

Steroid Stream

gen.py

#!/usr/bin/env python3

import random
from flag import flag

def keygen(ln):
    # Generate a linearly independent key
    arr = [ 1 << i for i in range(ln) ]

    for i in range(ln):
        for j in range(i):
            if random.getrandbits(1):
                arr[j] ^= arr[i]
    for i in range(ln):
        for j in range(i):
            if random.getrandbits(1):
                arr[ln - 1 - j] ^= arr[ln - 1 - i]

    return arr

def gen_keystream(key):
    ln = len(key)
    assert ln > 50
    
    # Generate some fake values based on the given key...
    fake = [0] * ln
    for i in range(ln - ln // 3):
        arr = list(range(i + 1, ln))
        random.shuffle(arr)
        for j in arr[:ln // 3]:
            fake[i] ^= key[j]

    # Generate the keystream
    res = []
    for i in range(ln):
        t = random.getrandbits(1)
        if t:
            res.append((t, [fake[i], key[i]]))
        else:
            res.append((t, [key[i], fake[i]]))

    # Shuffle!
    random.shuffle(res)

    keystream = [v[0] for v in res]
    public = [v[1] for v in res]
    return keystream, public

def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]

def recover_keystream(key, public):
    st = set(key)
    keystream = []
    for v0, v1 in public:
        if v0 in st:
            keystream.append(0)
        elif v1 in st:
            keystream.append(1)
        else:
            assert False, "Failed to recover the keystream"
    return keystream

def bytes_to_bits(inp):
    res = []
    for v in inp:
        res.extend(list(map(int, format(v, '08b'))))
    return res

def bits_to_bytes(inp):
    res = []
    for i in range(0, len(inp), 8):
        res.append(int(''.join(map(str, inp[i:i+8])), 2))
    return bytes(res)

flag = bytes_to_bits(flag)

key = keygen(len(flag))
keystream, public = gen_keystream(key)
assert keystream == recover_keystream(key, public)
enc = bits_to_bytes(xor(flag, keystream))

print(enc.hex())
print(public)

Challenge Summary

The goal of the challenge is to recover the keystream used to encrypt the flag.

Intially, “ln = len(flag_bits)” bit numbers are generated as keys. In order to recover the keystream for decryption, entire keystream is encoded into an array of 2 element tuple. Every $i$th bit is encoded by adding the tuple (fake[i], key[i]) if bit is $0$ and (key[i], fake[i]) if bit is $1$. We were given this array and if we manage to distinguish between “fake” value and “key” value then we can recover the keystream thus the flag.

Solution

Let’s see how “fake” values are generated

def gen_keystream(key):
    ln = len(key)
    assert ln > 50
    
    # Generate some fake values based on the given key...
    fake = [0] * ln
    for i in range(ln - ln // 3):
        arr = list(range(i + 1, ln))
        random.shuffle(arr)
        for j in arr[:ln // 3]:
            fake[i] ^= key[j]
...

fake[i] is equal to xor of ln/3 elements randomly chosen from the list key[i+1:]. fake values for last ln/3 indices are not modified and are equal to $0$. Using that, we can recover key[ln//3:].

With key[ln//3:], we can get the fake value at index ln/3 - 1 by just xoring key[ln//3:] and checking the public array. However, to recover keys at lower indices, this approach doesn’t work as keys used are randomly selected, number of combinations of keys used increase as index decreases. To recover the keys at lower indices, we need a different approach.

The idea is to realise that fake[i] is xor of some of keys[i+1:] and xor operation is equivalent to addition in Finite Field $GF(2)$. As a result, fake values can be written as a linear combination of vectors formed by known keys.

Example: consider 4 keys, out of which 2 randomly selected values are used to calculate the fake value. keys = 4, 5, 7, 9 and fake = 5 xor 7 = 2. fake can be further written as

\[fake = 5\ xor \ 7 = (0, 1, 0, 1)\ xor\ (0, 1, 1, 1) = (0, 1, 0, 1) + (0, 1, 1, 1) \ \ (in\ \ GF(2))\]

we can include other unused keys in the equation with 0 coefficients

\[fake = 1 \cdot (0, 1, 0, 1) + 1 \cdot (0, 1, 1, 1) + 0 \cdot (0, 1, 0, 0) + 0 \cdot (1, 0, 0, 1)\]

As fake values are linear combination of known keys, we can construct a matrix in $GF(2)$ with all the known upper index keys and try to solve for each value in the tuple.

if the value is a fake value then a solution must exist and it should contain only ln/3 $1's$. similarly, if the value is a key, assuming the keys are independent a solution will not exist and we can be sure that present value is part of keys.

Using this method, we can differentiate fake value from a key value and recover the keystream.

recover_keystream.sage

import ast

def num2vec(i, bits=616):
	return vector(GF(2), list(map(int, bin(i)[2:].zfill(ln))))

def construct_rows(keys):
	rows = []
	for i in keys:
		rows.append(num2vec(i))
	return rows

def get_previous_key(M):
	global public
	for ind, (i, j) in enumerate(public):
		v, u = map(num2vec, (i, j))
		FLAG_1 = False
		ERROR_1 = False
		try:
			s = M.solve_left(v)
			s = list(map(int, s))
			if sum(s) == 205:
				FLAG_1 = True
		except ValueError:
			ERROR_1 = True
			pass
		FLAG_2 = False
		ERROR_2 = False
		try:
			s = M.solve_left(u)
			s = list(map(int, s))
			if sum(s) == 205:
				FLAG_2 = True
		except ValueError:
			ERROR_2 = True
			pass
		if FLAG_1 and ERROR_2:
			return j, (i, j)
		elif FLAG_2 and ERROR_1:
			return i, (i, j)
	print("FAILED")
	return None

keys = []
public = ast.literal_eval(open("output.txt").read())
public = [(i, j) for i, j in public]
ln = len(public)
to_remove = []
for ind, (i, j) in enumerate(public):
	if i == 0:
		keys.append(j)
		to_remove.append((i, j))
	elif j == 0:
		keys.append(i)
		to_remove.append((i, j))
for e in to_remove:
	public.remove(e)

rows = construct_rows(keys)

for i in range(len(keys), ln):
	M = Matrix(GF(2), rows)
	t, e = get_previous_key(M)
	print("[*] found key", t, "\n")
	keys.append(t)
	rows.append(num2vec(t))
	public.remove(e)

with open("keys", "w") as f:
	f.write(str(keys))

After finding all the keys, we can use the functions defined in challenge file to recover keystream and get the flag.

FLAG: pbctf{I_hope_you_enjoyed_this_challenge_now_how_about_playing_Metroid_Dread?}

GoodHash

main.py

#!/usr/bin/env python3

from Crypto.Cipher import AES
from Crypto.Util.number import *
from flag import flag
import json
import os
import string

ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "


class GoodHash:
    def __init__(self, v=b""):
        self.key = b"goodhashGOODHASH"
        self.buf = v

    def update(self, v):
        self.buf += v

    def digest(self):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.buf)
        enc, tag = cipher.encrypt_and_digest(b"\0" * 32)
        return enc + tag

    def hexdigest(self):
        return self.digest().hex()


if __name__ == "__main__":
    token = json.dumps({"token": os.urandom(16).hex(), "admin": False})
    token_hash = GoodHash(token.encode()).hexdigest()
    print(f"Body: {token}")
    print(f"Hash: {token_hash}")

    inp = input("> ")
    if len(inp) > 64 or any(v not in ACCEPTABLE for v in inp):
        print("Invalid input :(")
        exit(0)

    inp_hash = GoodHash(inp.encode()).hexdigest()

    if token_hash == inp_hash:
        try:
            token = json.loads(inp)
            if token["admin"] == True:
                print("Wow, how did you find a collision?")
                print(f"Here's the flag: {flag}")
            else:
                print("Nice try.")
                print("Now you need to set the admin value to True")
        except:
            print("Invalid input :(")
    else:
        print("Invalid input :(")

Challenge Summary

Challenge file defines a new hash function “GoodHash” based on AES-GCM. The input buffer is used as nonce for AES-GCM and plaintext consisting of 32 null bytes is encrypted using that. Hash of the input buffer is equal to $ciphertext + tag$. The key used for AES-GCM is fixed and is equal to “goodhashGOODHASH”. The way challenge works is it first generates a random json token with “admin” set to “False” and prints the token and it’s hash computed using “GoodHash” function. The player has to generate a valid json token with same “GoodHash” hash as previously generated token but with “admin” set to “True” to get the flag and the length of token is restricted to 64 bytes.

Solution

Given that key is constant, the ciphertext and tag of AES-GCM will only be equal if the nonces used are equal. In AES-GCM, if the nonce length is greater than 12 bytes, it is hashed with GHASH and the result is used as the nonce. This means that if the GHASH of nonces are equal then the “GoodHash” of the input buffers(nonce) will be equal i.e hash collision of GHASH is hash collision of “GoodHash”. Now, the goal is to generate valid json GHASH collision for the challenge token. For that, let’s try to understand how GHASH works.

GHASH is a polynomial hash function. The input buffer is divided into blocks of size 16 bytes(128 bit) and each block is encoded as an element of $GF(2^{128})$. The elements are used as coefficients for the polynomial and final hash is the result of evaluation of this at $H$. simply,

Given $X$ and $H$ where

\[X = X_{1} || X_{2} || X_{3} || ... || X_{m}\]

the GHASH $Y_{m}$ is

\[Y_{m} = \sum_{i=1}^{m} X_{i} \cdot H^{m-i+1}\]

For AES-GCM, $H = E(K, 0)$ where $E(K, 0)$ is AES encryption of null block with AES-GCM key $K$.

So, to generate a collision for token whose hash is say, $T$ and $Z_{i}$ are $d$ known input blocks beyond attacker’s control present at the end of the input, the attacker has to find $X_{i}$ that will statisfy the following equation

\[\sum_{i=1}^{e} X_{i} \cdot H^{m-i+1} = T - \sum_{i=e+1}^{m} Z_{i} \cdot H^{m-i+1} \ \ \ \ where, m = e + d\]

Let’s try to write this problem specific to our challenge as it is hard to understand attack on generalised instance.

Before hashing the nonce with GHASH, the input buffer is padded and length of the input nonce is encoded into the last block. $Z_{i}$ in the above equation are there to account for this padding block. $T$ is equal to GHASH of challenge token.

The length of the input token is restricted to 64 bytes, this 64 bytes are used as the first 4 blocks $X_{i}, 1 \leqslant i \leqslant 4$.

let $l0 = H^{m}, l1 = H^{m-1}, l2 = H^{m-2}, l3 = H^{m-3}$ and $b_{0}, b_{1}, b_{2}, b_{3}$ be the first four input blocks. The challenge comes down to finding $b_{i}$’s such that

\[b_{0} \cdot l_{0} + b_{1} \cdot l_{1} + b_{2} \cdot l_{2} + b_{3} \cdot l_{3} = T - \sum_{i=4}^{m} Z_{i} \cdot H^{m-i+1} = t\]

As key is fixed and public, $H$ and powers of it can be calculated easily.

if there are no constraints on $b_{i}$, we can set all but one block to random and solve for the last block. But, the challenge requires a valid json token and that means all the bytes of the input need to be ASCII and must follow json format.

These constraints can be written as constraints on the coefficients of $x^{j}, 0 \leqslant j < 128$. That’s because, every element of $GF(2^{128})$ is represented as a polynomial of degree less than 128 and each bit of plaintext block is used as coefficient of a certain monomial $x_{j}$. In other terms if we want certain bits of plaintext, say, msb of every byte to be 0 then the coefficients of monomials corresponding to that position need to be 0. We can solve this problem of certain coefficients set to predetermined values if we can let enough number of other bits to whatever value. To understand how, let’s consider an example

Example : suppose, we have to find $b_{0}, b_{1}$ such that $b_{0} \cdot l_{0} + b_{1} \cdot l_{1} = t$ and all the elements are in $GF(2^{3})$. if we want coefficient of $x^{2}$ of $b_{0}$ to be $1$ and $x$ coefficient in $b_{1}$ to be $0$, we can do the following

$b_{0} \cdot l_{0} + b_{1} \cdot l_{1} = (1 \cdot x^{2} + c_{01} \cdot x + c_{00} \cdot 1) \cdot l_{0} + (c_{12} \cdot x^{2} + 0 \cdot x + c_{10} \cdot 1) \cdot l_{1}$,

\[\ \ \ \ \ \ \ \ \ \ \ = 1 \cdot (x^{2} \cdot l_{0}) + c_{01} \cdot (x \cdot l_{0}) + c_{00} \cdot (1 \cdot l_{0}) + c_{12} \cdot (x^{2} \cdot l_{1}) + 0 \cdot (x \cdot l_{1}) + c_{10} \cdot (1 \cdot l_{1})\]

$x^{i} \cdot l_{j}$ are themselves elements(polynomials of degree 2) in $GF(2^3)$.

so, $\ \ b_{0} \cdot l_{0} + b_{1} \cdot l_{1}$ can be written as linear sum of polynomials where $c_{ji}$ are elements of $GF(2)$. The use of writing in this way is that, polynomial addition is equivalent to addition of coefficient vectors. so, if the target vector is $t$, above equation can be written as

\[c_{01} \cdot v_{01} + c_{00} \cdot v_{00} + c_{12} \cdot v_{12} + c_{10} \cdot v_{10} = t - 1 \cdot v_{02} - 0 \cdot v_{11}\]

where $v_{ji} = x^{i} \cdot l_{j}$

Now, the problem reduced to finding scalar multipliers of vectors such that their linear combination is equal to the target vector. This is same as solving matrix equations. so, to find $c_{ji}$, we can form a matrix consisting of $v_{ij}$ and solve with target vector.

In short, method is to write the multiplication of two polynomials as sum of polynomials by expanding the unknown variables and realise that polynomial sum is same as vector addition and solve matrix equations to find the solution.

This method can be used to find solutions for such equations in any finite field $GF(p^{n})$.

As input token needs to be a valid json and admin set to true to get the flag, I used the following format

input = '{"x":"' + random_valid_characters + '","admin": true}'

using this format allows “random_valid_characters” to be any valid ASCII except few characters like double quotes and escape characters. To restrict bytes to printable characters, I set msb of every byte to 0 and 5th bit to 1 (> 32). These constraints can be used to find valid json input, there will be many solutions to the system. so, we can find a valid input by trying the solutions one by one.

find_collision.sage

from Crypto.Util.number import bytes_to_long, long_to_bytes
import random
import string

def rev_bits(s, nbits):
	"""
	reverse the order of bits 
	"""
	return long_to_bytes(int(bin(bytes_to_long(s))[2:].zfill(nbits)[::-1], 2))

def bytes2pol(s):
	return FF.fetch_int(bytes_to_long(rev_bits(s, 128)))

def pol2bytes(s):
	return rev_bits(long_to_bytes(s.integer_representation()), 128)

def pol2vec(s):
	return vector(GF(2), list(map(int, bin(s.integer_representation())[2:].zfill(128))))

def GHASH(buf, H):
	assert len(buf) % 16 == 0
	H = bytes2pol(H)
	coefficients = [bytes2pol(buf[i:i+16]) for i in range(0, len(buf), 16)]
	H_powers = [H**i for i in range(1, len(coefficients) + 1, 1)][::-1]
	result = sum([i*j for i, j in zip(coefficients, H_powers)])
	return pol2bytes(result)

def ghash_padding(buf_length):
	# nonce is padded by pycrypto before ghash
	fill = (16 - (buf_length % 16)) % 16 + 8
	padding =  (b'\x00' * fill + long_to_bytes(8 * buf_length, 8))
	return padding

def calculate_new_target(target, H):
	last_block = b'","admin": true}'
	H = bytes2pol(H)
	padding = ghash_padding(64)
	buf = b"\x00"*(16*3) + last_block + padding 
	coefficients = [bytes2pol(buf[i: i+16]) for i  in range(0, len(buf), 16)]
	H_powers = [H**i for i in range(1, len(coefficients) + 1, 1)][::-1]
	result = sum([i*j for i, j in zip(coefficients, H_powers)])
	new_target = target - result
	linear_coefficients = H_powers[:3]
	return new_target, linear_coefficients

R.<x> = GF(2)[]
gcm_modulus = x ** 128 + x ** 7 + x ** 2 + x + 1

FF = GF(2 ** 128, name = "X", modulus = gcm_modulus)
X = FF.gen()

charset = string.ascii_letters + string.digits + "!#$%&'()*+,-./:;<=>?@_`|~" + " "
ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "


H = b'\x8c[\xb3\x0f\xba\xa0\xdf\xdb\xc7\xee\xb7\x1f_M\xd6\xab'
token = input("> ").encode().strip()
token_ = token + ghash_padding(len(token))
target = bytes2pol(GHASH(token_, H))
new_target, linear_coefficients = calculate_new_target(target, H)

last_block = b'","admin": true}'

def valid_string(buf, charset):
	return all(bytes([i]) in charset for i in buf)

def solve_constraints(new_target, linear_coefficients):
	l0, l1, l2 = linear_coefficients
	# find b0, b1, b2 => b0*l0 + b1*l1 + b2*l2 = new_target
	# and b0, b1, b2 follow format
	first_block = b'{"x":"' + bytes([32]) * 10
	rem_block = bytes([32]) * 16
	final_target = new_target - bytes2pol(first_block) * l0
	final_target -= bytes2pol(rem_block) * l1
	final_target -= bytes2pol(rem_block) * l2
	terms = [X**1, X**3, X**4, X**5, X**6, X**7]
	first_block_terms = []
	for i in range(6, 16):
		first_block_terms.extend([j*X**(8*i) for j in terms])
	second_block_terms = []
	for i in range(16):
		second_block_terms.extend([j*X**(8*i) for j in terms])
	third_block_terms = []
	for i in range(16):
		third_block_terms.extend([j*X**(8*i) for j in terms])

	rows_polynomials = []
	for li, rand_terms in zip(linear_coefficients, [first_block_terms, second_block_terms, third_block_terms]):
		for j in rand_terms:
			rows_polynomials.append(j*li)

	M = Matrix(GF(2), [pol2vec(i) for i in rows_polynomials])
	v = pol2vec(final_target)
	u = M.solve_left(v)
	for counter, s in enumerate(M.left_kernel()):
		sol = u + s
		f1 = 0
		ind = 0
		for i in first_block_terms:
			f1 += int(sol[ind])*i
			ind += 1
		f2 = 0
		for i in second_block_terms:
			f2 += int(sol[ind])*i
			ind += 1
		f3 = 0
		for i in third_block_terms:
			f3  += int(sol[ind]) * i
			ind += 1

		b0 = bytes2pol(first_block) + f1
		b1 = bytes2pol(rem_block) + f2
		b2 = bytes2pol(rem_block) + f3
		b0, b1, b2 = map(pol2bytes, (b0, b1, b2))
		last_block = b'","admin": true}'
		try:
			answer = (b0 + b1 + b2 + last_block).decode()
			if any(v not in ACCEPTABLE for v in answer):
				continue
			r = json.loads(answer)
			return answer
		except:
			continue

my = solve_constraints(new_target, linear_coefficients)
print("solved")
print(my)

FLAG:pbctf{GHASH_is_short_for_GoodHash_:joy:}

SEED ME

Main.java

import java.nio.file.Files;
import java.nio.file.Path;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;

class Main {

    private static void printFlag() {
        try {
            System.out.println(Files.readString(Path.of("flag.txt")));
        }
        catch(IOException e) {
            System.out.println("Flag file is missing, please contact admins");
        }
    }

    public static void main(String[] args) {
        int unlucky = 03777;
        int success = 0;
        int correct = 16;

        System.out.println("Welcome to the 'Lucky Crystal Game'!");
        System.out.println("Please provide a lucky seed:");
        Scanner scr = new Scanner(System.in);
        long seed = scr.nextLong();
        Random rng = new Random(seed);

        for(int i=0; i<correct; i++) {
            /* Throw away the unlucky numbers */
            for(int j=0; j<unlucky; j++) {
                rng.nextFloat();
            }

            /* Do you feel lucky? */
            if (rng.nextFloat() >= (7.331f*.1337f)) {
                success++;
            }
        }

        if (success == correct) {
            printFlag();
        }
        else {
            System.out.println("Unlucky!");
        }
    }
}

Challenge Summary

Challenge first takes long int as input from the player. Input long int is used as the seed for java’s Random number generator.After intialising the rng, every $2048$ float generated by this rng is compared with hardcoded value of “7.331f*.1337f”. For challenge server to print the flag, every $2048$th number for 16 iterations should be greater than the before mentioned float.

Solution

Java uses LCG as the random number generator. The parameters used for LCG are $M = 2^{48}, A = 0x5deece66d, B = 0xb$. The next random number in LCG is calculated using

\[X_{i+1} = A \cdot X_{i} + B \ \ \ \ (\ mod\ \ M)\]

And when calling “rng.nextFloat”, only top 24 bits are used to calculate the float. In order for the challenge condition to pass LCG output should be greater than $16444267 \cdot 2^{24}$ i.e Every $2048$ output random number generated by LCG with the given input seed must be greater than $16444267 \cdot 2^{24}$. Let’s call this the lower bound($lb$). LCG next function is linear and closed form for $n$th iteration can be written in terms of intial seed $x$.

using sage,

def getnext():
	global seed
	seed = (seed*A + B)
	return seed

coefficients = []
P.<x> = PolynomialRing(Zmod(M))
seed = x
for i in range(niterations):
	for j in range(0o3777):
		t = getnext()
	y = getnext()
	d = y.dict()
	# c1*x + c2 
	coefficients.append((d[1], d[0]))

The condition is checked for 16 iterations. Let $a_{i}, b_{i}$ be the coefficients corresponding to $i$th iteration i.e $O_{i} = a_{i} \cdot x + b_{i}$ where $O_{i}$ is ith iteration or $2048 \cdot i$ LCG output number.

Now that all the outputs depend on the intial seed, the idea to form a lattice using $a_{i}$, $b_{i}$ and $M$. A lattice consists of all the vectors which are result of linear combination of basis vectors. To see the use of this, consider the following basis

$$L = \begin{bmatrix} a_{1}&a_{2}&\cdots&a_{16}&1&0 \\ b_{1}&b_{2}&\cdots&b_{16}&0&c \\ M&0&\cdots&0&0&0 \\ 0&M&\cdots&0&0&0 \\ & &\ddots& \\ 0&0&\cdots&M&0&0 \\ \end{bmatrix}$$

Using above matrix, every possible output sequence($O_{i}$) can be generated by using an appropriate $v$ in $v \cdot L$ and all the $v$ entries are integers. That means, the lattice contains all the output sequences possible for each possible($x < 2^{48}$). so, if there’s a solution for this challenge then the corresponding output sequence will also be in the Lattice.To find the seed, we can use CVP approximate solver. Closest Vector Problem is the problem of finding a vector in the Lattice which is closest to the given target vector. CVP is a hard problem and there are only approximation algorithms but these work just fine for our problem.

The output sequence elements should be $lb = 16444267 * 2^{24} < O_{i} < ub = 2^{48}$. Using $bound = \frac{lb + ub}{2}$ as entries of target vector gives a pretty good solution. However, last output didn’t statisfy the bounds. It is slightly larger then $M$ as a result when reduced modulo $M$, the output was very small. After testing various values around the intial bound, I observed that only last output is not statisfying the bounds. So, I tested with lower bound for that entry in the target vector and remaining entries set to intial $bound = \frac{lb + ub}{2}$ and it worked.

Note that $c$ in the above matrix is also set to $bound$ it’s purpose is to restrict the approximate algorithm to use $1$ for $b$ vector as $b_{i}$ coefficients are all $1$.

solver.sage

def Babai_closest_vector(M, G, target):
	small = target
	for _ in range(1):
		for i in reversed(range(M.nrows())):
			c = ((small * G[i]) / (G[i] * G[i])).round()
			small -=  M[i] * c
	return target - small 

def getnext():
	global seed
	seed = (seed*A + B)
	return seed

def check_bound(bound, coefficients, last_bound=None):
	rows = [[], []]
	for (a, b) in coefficients:
		rows[0].append(a)
		rows[1].append(b)
	rows[0].extend([1, 0])
	rows[1].extend([0, bound])
	for i in range(niterations):
		row = [0]*len(rows[0])
		row[i] = M
		rows.append(row)
	A = Matrix(ZZ, rows)
	target = [bound] * len(A[0])
	if last_bound is not None:
		target[-3] = last_bound
	Target = vector(ZZ, target)
	B = A.LLL()
	GG = B.gram_schmidt()[0]
	TT = Babai_closest_vector(B, GG, Target)
	print("TT =", TT)
	for i in TT:
		print((i % M) > lb, i < ub)
	print("seed: ", TT[-2])
	print("TT[-1] == bound", TT[-1] == bound)

niterations = 16

M = 2**48
A = 0x5DEECE66D
B = 0xB

coefficients = []
P.<x> = PolynomialRing(Zmod(M))
seed = x
for i in range(niterations):
	for j in range(0o3777):
		t = getnext()
	y = getnext()
	d = y.dict()
	# c1*x + c2 
	coefficients.append((d[1], d[0]))

lb = 16444267 << 24
ub = (2**24) << 24
bound = (lb + ub) // 2

check_bound(bound, coefficients, lb)

The input number is first scrambled by xoring with $A$ before used as LCG seed. So, the calculated seed needs to be unscrambled before giving it as the input.

FLAG : pbctf{intended_is_LLL_with_branch_and_bound_9ad09becbc4c7685}