Katanaverse 1.0 : bi0sCTF 2024

tl;dr

• Utilises a VM to receive an input and modify the input by performing bit manipulation
• Quantum gates (quantum operations) are applied to the modified flag
• A quantum algorithm for the decisive match

Challenge points: 1000
No. of solves: 0

Challenge Description

Yes, that should work.

MD5 Hash:

katanaverse1.0: c86e0909a1f1d0296d58c059a02bbeed
1_dump.dmp: de7024faaf03edc69c2e52ee9aa95f9f

Author

• Sejal Koshta: k1n0r4 | k1n0r4

This challenge is a second part of Katanaverse 0.0

Two phases of Challenge:

1. VM involving Bit Manipulation
2. Quantum computation and algorithm

Overview

This challenge’s binary is broken and unexecutable beyond a particular point in the code since it starts involving quantum operations, which are provided in Python. On Quantum servers, these procedures may be carried out via the Python qiskit module.

The challenge’s primary goal was to comprehend how the binary operates and re-implement any sections that cannot be performed or do not exist. To understand the suggestion provided to re-implement the non-existent function, you might also need to refer to the earlier section of this challenge, “Katanaverse 0.0”. You may find the necessary technique/method by performing a simple Google search using the essential terms.

Visit this page to learn more about Katanaverse 0.0’s functionality. This comprises the challenge’s organizational notes.

Q. How will I know that it makes use of quantum concepts?

Indeed, you can observe the occurrence of alpha and beta in the shellcode itself, and the structure of the shellcode also suggests a quantum or Qiskit module.

VM

Control flow of the VM

1. Prompt for Flag
2. Takes the input
3. Transforms the flag into its string encoded in base 64.
4. Register S0 stores the updated flag’s length.
5. Copying and storing flag bytes in “memory” and stack
6. Binary representations of flag bytes are created and placed on the stack.
7. As a result, each time a flag byte is converted, the byte is removed from memory.
8. Memory is discovered to be empty following the conversion.
9. A bit modification that is kept in memory is carried out using stored binary from the stack.
10. VM exits
11. It replicates its memory into a “classified” 2D array
12. It stores the altered input length from register S0 in a new variable for use in future applications.

Here is more information on the VM used.

Quantum

Upon obtaining the bit-manipulated array, which I refer to as the “classified” array, the quantum operations commence.

Runtime Constant generation

Prior to that, a few significant constants are created at runtime using the flag’s known portion, that is, it’s flag format.

Seed for the srand function - 89
Aes key - [24, 6, 59, 77, 181, 112, 85, 180, 113, 194, 137, 37, 74, 136, 6, 25]

uint8_t aes_key[16];

for(int i =0;i<16;i++)
{
aes_key[i] = classified[i][7] * 1 + classified[i][6] * 2 + classified[i][5] * 4 + classified[i][4] * 8 + classified[i][3] * 16 + classified[i][2] * 32 + classified[i][1] * 64 + classified[i][0] * 128;
}

The seed generation also involves a user character input, which is ‘r’

By taking two bytes of the modified flag at a time and creating six bytes for each such pair, the classified array is created. Therefore, a pair of flag bytes corresponds to each of these sets of six bytes. The last byte of the preceding pair is overlapped and used as the first byte to obtain the next pair of bytes.

The classified array then has certain constraints applied to it, where the produced random numbers decide which row satisfies each requirement. Three such constraints are given here for each group in the classified array.

Five constraints were provided to each group in the preceding section of the challenge, “Katanaverse 0.0”, allowing any constraint solver to recover the flag (Ps. This was the unintended solution to the challenge).

Next in the line are 2 other constants, subtract_key and xor_key, which are again computed using the known part of the flag format

subtract_key = 24
xor_key = 181

Determining the operations performed

Each one group of the classififed array includes 12 nibbles which determine which 12 operations will be performed on the initial qubit.

The given loop first initialises the qubit as
Alpha = 1 + 0i
Beta = 0 + 0i

and then 12 operations are performed on the qubit(func_11) one after the other. These 12 states of qubits are saved and later converted into their coordinate form via func_13

These correspond to different operations performed on the qubit, one such function is Blaze.
There are in total 16 operations named as Blaze, Horizon, Nova, Quantum, Echo, Radiant, Zenith, Cipher, Nimbus, Pulse, Serene, Ember, Aurora, Lumina, Cascade and Kinetic.

Within func_10 under Blaze, we can see that it attempts at executing the shellcode given, but upon failure intends to displays “Well, I already said it’s broken.”

Shellcode given unside the Blaze function looks like this

OPENQASM 2.0;
include "qelib1.inc";
gate disentangler_dg q0 {  }
gate state_preparation(param0,param1) q0 { disentangler_dg q0; }
gate initialize(param0,param1) q0 { reset q0; state_preparation(alpha,beta) q0; }
qreg q2[1];
creg c2[1];
initialize(alpha,beta) q2[0];
rx(pi/4) q2[0];
ry(pi/3) q2[0];
rz(pi/4) q2[0];
measure q2[0] -> c2[0]; 

Division of points

The lines that are depicted between two spots are formed or determined by 41 pairs of numbers or integers. The distances between these locations multiplied by 10 (func_8) make up the weights of these points.

In this case, the two numbers point in the direction of two points that are connected by a line, as a result, a network made up of all 12 points is formed which are connected by those lines.

For each of the 41 pairings, the two points and their respective weights are kept in an array and sent to a function (func_7).

What is func_7 ?

This is revealed by the shellcode or encrypted bytes within the function.

Oh no! Not only is this function flawed, it is nonexistent. Could you please solve this?

**Static noise

Agent, We happened to record a conversation between Martin and his subordinates. For your reference, here is the transcript of our conversation.

Subordinate 1: Is it possible for an ordinary person to open the vault?
Martin: No, definitely not. The vault needs to be slashed 12 times in order to divide those 12 points efficiently, and this needs to be done multiple times...
Subordinate 2: However, I have heard that you are required to use an 'efficient method' to divide the points
Martin: You are right, the key to this strange method is 'Brute'

All we have is this. All the best in finding the correct replacement for the given function.

**Static noise

Now let’s have a look at the shellcode given in Katanaverse 0.0 as well, because after all , this challenge is just an another part of 0.0

Oh no! Not only is this function flawed, it is nonexistent. Could you please solve this?

**Static noise

Agent, We happened to record a conversation between Martin and his subordinates. For your reference, here is the transcript of our conversation.

Subordinate 1: Is it possible for an ordinary person to open the vault?
Martin: No, definitely not. The vault needs to be slashed 12 times in order to divide those 12 points efficiently, and this needs to be done multiple times...
Subordinate 2: However, I have heard that you are not required to use an 'efficient method' to divide the points, but rather some other strange method?
Martin: You are right, the key to this strange method is 'Quantum'... Have you heard of Optimization?

All we have is this. All the best in finding the correct replacement for the given function.

**Static noise

This clearly states few points -

1. Quantum
2. Division of points
3. Optimization
4. Weighted (Because of the distance calculated between 2 points)
5. Brute

Using these terms in a Google search provides us with the necessary response.

These searches hint at using a popular Quantum optimization technique used in efficient division of enities, that is, QAOA (Quantum Approximate Optimization Algorithm)

In Katanaverse 1.0, we only need the brute version of this algorithm, which can be again found on blog posts or can be attempted to write on your own.

Since here, the weights of the points are also given, that again can be used to find the technique

Official qiskit page itself gives us an easy script to implement the given problem qiskit

Last step

After applying QAOA to every group in the classified array, 12 bits per group are obtained. These bits are then split in half to create two bytes. As a consequence, each group yields two final bytes, which are subsequently encrypted collectively using AES.

For comparison, the encrypted bytes of the right flag (after going through the full process) are provided.

Solution

So far we know what all is going on this challenge, therefore it’s time to consider how to get the flag back.

The constraints are given to make life easier.
We have the encrypted bytes of the result of the QAOA applied to the points. First, it is possible to decrypt the encrypted bytes and obtain all of the constants generated during runtime.

Since each group/set of classified array is constructed from overlapped pairs of modified flag, we can make use of the flag format to obtain the flag byte by byte.

The approach being, make use of the last known character of the flag format, that is, ‘{‘. The characters of the flag after this character are unknown, hence we find all the possibilities of the next byte by using the constraints given. Since the number of constraints for the classified array group of ‘{‘ and the next byte of the flag is 3, we have 32 possibilites (2^8[All possible 1 byte values] / 2^3[Branches narrowed down due to constraints given])

These 32 possibilites are passed through the entire process until the QAOA function and then the result is compared with the decrypted bytes from the binary.

Likewise, the discovered byte can be used to find the next byte in the order.

Authors note:
These might lead to more than one possible character for the given scenario, but the branches can be eliminated by acquiring the subsequent iteration. There is a single path that leads to the last character ‘{‘. You receive the right flag if you continue down that path.

Final Script

import numpy as np
import networkx as nx
from numpy import pi, cos, sin, arccos, arctan2

def calc_weight(a, b):       # Distance between 2 points
    sum_of_squares = 0
    for i in range(3):
        diff = a[i] - b[i]
        sum_of_squares += diff*diff
    return np.round(10*np.sqrt(sum_of_squares))

def rotate(initial_coords, rotation_matrix):
    return np.dot(rotation_matrix, initial_coords)

def xyz_to_alpha_beta(xyz):
  xyz = np.asarray(xyz)
  r = np.linalg.norm(xyz)
  theta = arccos(xyz[2] / r)
  phi = arctan2(xyz[1], xyz[0])
  alpha = cos(theta / 2)
  beta = np.exp(1j * phi) * sin(theta / 2)
  return alpha, beta

def alpha_beta_to_xyz(alpha, beta):
  r = abs(alpha)**2 + abs(beta)**2
  theta = 2 * arccos(abs(alpha) / np.sqrt(r))
  phi = np.angle(beta / alpha)
  x = r * sin(theta) * cos(phi)
  y = r * sin(theta) * sin(phi)
  z = r * cos(theta)
  return np.array([x, y, z])

def zeroth(coords_xyz):                        #Blaze
  a = rotate(coords_xyz, rx_op(np.pi / 4))
  a = rotate(a, ry_op(np.pi / 3))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a
  
def first(coords_xyz):                        #Horizon
  a = rotate(coords_xyz, ry_op(np.pi / 4))
  a = rotate(a, rz_op(np.pi / 3))
  a = rotate(a, rx_op(np.pi / 3))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def second(coords_xyz):                        #Nova
  a = rotate(coords_xyz, rx_op(np.pi / 6))
  a = rotate(a, ry_op(np.pi / 2))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def third(coords_xyz):                        #Quantum
  a = rotate(coords_xyz, ry_op(np.pi / 6))
  a = rotate(a, rx_op(np.pi / 2))
  a = rotate(a, rz_op(np.pi / 6))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def fourth(coords_xyz):                        #Echo
  a = rotate(coords_xyz, rx_op(np.pi / 4))
  a = rotate(a, ry_op(np.pi / 3))
  a = rotate(a, rz_op(np.pi / 6))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def fifth(coords_xyz):                        #Radiant
  a = rotate(coords_xyz, ry_op(np.pi / 2))
  a = rotate(a, rx_op(np.pi))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def sixth(coords_xyz):                        #Zenith
  a = rotate(coords_xyz, rx_op(np.pi / 3))
  a = rotate(a, ry_op(np.pi))
  a = rotate(a, rz_op(np.pi / 3))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def seventh(coords_xyz):                      #Cipher
  a = rotate(coords_xyz, ry_op(np.pi / 6))
  a = rotate(a, rz_op(np.pi / 4))
  a = rotate(a, rx_op(np.pi / 2))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def eigth(coords_xyz):                        #Nimbus
  a = rotate(coords_xyz, rx_op(np.pi / 6))
  a = rotate(a, ry_op(np.pi))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def ninth(coords_xyz):                        #Pulse
  a = rotate(coords_xyz, ry_op(np.pi / 4))
  a = rotate(a, rx_op(np.pi))
  a = rotate(a, rz_op(np.pi / 3))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def tenth(coords_xyz):                        #Serene
  a = rotate(coords_xyz, rx_op(np.pi / 6))
  a = rotate(a, ry_op(np.pi / 3))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def eleventh(coords_xyz):                    #Ember
  a = rotate(coords_xyz, rx_op(np.pi / 4))
  a = rotate(a, ry_op(np.pi))
  a = rotate(a, rz_op(np.pi / 6))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def twelfth(coords_xyz):                    #Aurora
  a = rotate(coords_xyz, ry_op(np.pi / 2))
  a = rotate(a, rx_op(np.pi))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def thirteenth(coords_xyz):                #Lumina
  a = rotate(coords_xyz, rx_op(np.pi / 2))
  a = rotate(a, ry_op(np.pi / 6))
  a = rotate(a, rz_op(np.pi / 3))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def fourteenth(coords_xyz):                #Cascade
  a = rotate(coords_xyz, rx_op(np.pi / 3))
  a = rotate(a, ry_op(np.pi / 3))
  a = rotate(a, rz_op(np.pi / 4))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def fifteenth(coords_xyz):                #Kinetic
  a = rotate(coords_xyz, ry_op(np.pi / 4))
  a = rotate(a, rz_op(np.pi / 6))
  a = rotate(a, rx_op(np.pi / 6))
  a[0] = round(a[0], 5) if abs(a[0]) > 0.00001 else 0
  a[1] = round(a[1], 5) if abs(a[1]) > 0.00001 else 0
  a[2] = round(a[2], 5) if abs(a[2]) > 0.00001 else 0
  return a

def rx_op(theta):                #Rotation along x axis
    cos_a = np.cos(theta)
    sin_a = np.sin(theta)
    Rx = np.array([[1, 0, 0],
                   [0, cos_a, -sin_a],
                   [0, sin_a, cos_a]])
    return Rx

def ry_op(theta):                #Rotation along y axis
    cos = np.cos(theta)
    sin = np.sin(theta)
    Ry = np.array([[cos, 0, sin],
                   [0, 1, 0],
                   [-sin, 0, cos]])
    return Ry

def rz_op(theta):                #Rotation along z axis
    cos = np.cos(theta)
    sin = np.sin(theta)
    Rz = np.array([[cos, -sin, 0],
                   [sin, cos, 0],
                   [0, 0, 1]])
    return Rz

def choice(choi, points):
  if choi == 0:
    return zeroth(points)
  elif choi == 1:
    return first(points)
  elif choi == 2:
    return second(points)
  elif choi == 3:
    return third(points)
  elif choi == 4:
    return fourth(points)
  elif choi == 5:
    return fifth(points)
  elif choi == 6:
    return sixth(points)
  elif choi == 7:
    return seventh(points)
  elif choi == 8:
    return eigth(points)
  elif choi == 9:
    return ninth(points)
  elif choi == 10:
    return tenth(points)
  elif choi == 11:
    return eleventh(points)
  elif choi == 12:
    return twelfth(points)
  elif choi == 13:
    return thirteenth(points)
  elif choi == 14:
    return fourteenth(points)
  elif choi == 15:
    return fifteenth(points)
  
pairs = [[0,2], [0,4], [0,6], [0,8], [0,10], [1,0], [1,3], [1,5], [1,7], [1,9], [1,11], [2,1], [2,4], [2,6], [2,8], [2,10], [3,2], [3,5], [3,7], [3,9], [3,11], [4,3], [4,6], [4,8], [4,10], [5,4], [5,7], [5,9], [5,11], [6,5], [6,8], [6,10], [7,6], [7,9], [7,11], [8,7], [8,10], [9,8], [9,11], [10,9], [11,10]]

rand_arr = [1, 2, 0, 3, 2, 1, 2, 3, 1, 0, 2, 3, 3, 0, 1, 2, 0, 1, 1, 2, 3, 2, 0, 1, 0, 1, 3, 3, 2, 0, 1, 2, 0, 1, 3, 2, 3, 2, 0, 0, 3, 2, 3, 1, 0, 3, 2, 0, 0, 3, 1, 3, 1, 2, 3, 2, 1, 2, 0, 3, 0, 2, 3]

cond_arr = [0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]

dec_arr = [85, 74, 105, 82, 105, 102, 85, 74, 101, 90, 85, 106, 89, 102, 101, 90, 85, 106, 90, 116, 116, 90, 117, 74, 102, 86, 85, 106, 91, 82, 90, 86, 85, 74, 86, 100, 86, 118, 85, 106, 84, 110]

new_sol = []
new_sol.append([0, 1, 1, 1, 1, 0, 1, 1])    #Initial solution '{'

for bug in range(21):

    solutions = new_sol
    new_sol=[]

    print("\nFor ", bug)
    for hat in solutions:
        print("Trying...", hat)
        a = hat
        cond = [cond_arr[bug*3], cond_arr[bug*3+1], cond_arr[bug*3+2]]                
        rand = [rand_arr[bug*3], rand_arr[bug*3+1], rand_arr[bug*3+2]]

        res = []

        dec_bytes = [dec_arr[bug*2], dec_arr[bug*2+1]]    #AES decrypted bytes for each character
        best = ''
        best_sol=[]
        
        #Retrieveing the 12 bit form of the encrypted bytes
        for i in range(2):
            best += bin(dec_bytes[i])[3:]
        best_sol = [int(char) for char in best]    

        for q in range(0,2):
            for w in range(0,2):
                for e in range(0,2):
                    for r in range(0,2):
                        for t in range(0,2):
                            for y in range(0,2):
                                for u in range(0,2):
                                    for i in range(0,2):
                                        
                                        #Bruting the second character in the pair
                                        b = q,w,e,r,t,y,u,i         
                                        c = [[0]*8]*6
                                        k=0
                                        for j in rand:
                                            c = [0]*8
                                            c[0] = a[(j+0)]^b[(j+0)]
                                            c[1] = a[(1+j)]^b[(1+j)]
                                            c[2] = a[(2+j)]^b[(2+j)]
                                            c[3] = a[(1+j)]^b[(0+j)]
                                            c[4] = a[(0+j)]^b[(1+j)]
                                            c[5] = a[(2+j)]^b[(1+j)]
                                            c[6] = a[(1+j)]^b[(2+j)]
                                            c[7] = a[(0+j)]^b[(1+j)]^a[(2+j)]
                                            
                                            #Check for constraints
                                            if c[0] ^ c[7] != cond[k]:                
                                                k+=1  
                                        if k == 3:
                                            res.append(b)

        for i in range(len(res)):
            classified = []
            final_res = res[i]
            b = res[i]
            
            #Formation of the classified array for each possibilitity
            for j in range(6):                
                c = [0]*8
                c[0] = a[(j+0)]^b[(j+0)]        #Bit manipulation
                c[1] = a[(1+j)]^b[(1+j)]
                c[2] = a[(2+j)]^b[(2+j)]
                c[3] = a[(1+j)]^b[(0+j)]
                c[4] = a[(0+j)]^b[(1+j)]
                c[5] = a[(2+j)]^b[(1+j)]
                c[6] = a[(1+j)]^b[(2+j)]
                c[7] = a[(0+j)]^b[(1+j)]^a[(2+j)]
                classified.append(c)
            op_list = []
            
            #Obtaining the list of (12) operations based on the value of each nibble
            for k in range(6):                
                op_list.append(classified[k][0]*8+classified[k][1]*4+classified[k][2]*2+classified[k][3]*1)
                op_list.append(classified[k][4]*1+classified[k][5]*2+classified[k][6]*4+classified[k][7]*8)
    
            points = [[0]*3 for _ in range(12)]

            #Inital QuBit Value in coordinate form
            xyz_in = np.array([0,0,1])        
            for j in range(12):
                ant = op_list[j]
                #Performing the given operation on the QuBit
                xyz_in = choice(ant, xyz_in)    
                points[j] = xyz_in

            elist = [[0] * 3 for _ in range(41)] 

            #Formation of elist array
            for j in range(41):
                elist[j][0] = pairs[j][0]
                elist[j][1] = pairs[j][1]
                elist[j][2] = calc_weight(points[pairs[j][0]], points[pairs[j][1]])  

            n = 12                          #Number of points
            G = nx.Graph()
            G.add_nodes_from(np.arange(0, n, 1))

            G.add_weighted_edges_from(elist)
            
            w = np.zeros([n, n])
            for iy in range(n):
                for j in range(n):
                    temp = G.get_edge_data(iy, j, default=0)
                    if temp != 0:
                        w[iy, j] = temp["weight"]
                
            #Bruting the way to divide the points in 2 groups
            best_cost_brute = 0                    
            for b in range(2**n):
                x = [int(t) for t in reversed(list(bin(b)[2:].zfill(n)))]
                cost = 0
                for iy in range(n):
                    for j in range(n):
                        cost = cost + w[iy, j] * x[iy] * (1 - x[j])
                if best_cost_brute < cost:
                    best_cost_brute = cost
                    xbest_brute = x
        
            if xbest_brute == best_sol:
                charac_s = ''.join(str(bit) for bit in final_res)
                if chr(int(charac_s, 2)) in '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ}{':
                    #Eliminating duplicate solutions
                    if final_res not in new_sol:            
                        new_sol.append(final_res)
                    print("Found: ", final_res, chr(int(charac_s, 2)))

Output:


For  0
Trying... [0, 1, 1, 1, 1, 0, 1, 1]
Found:  (0, 1, 1, 0, 0, 0, 1, 0) b
Found:  (0, 1, 1, 0, 0, 0, 1, 1) c

For  1
Trying... (0, 1, 1, 0, 0, 0, 1, 0)
Trying... (0, 1, 1, 0, 0, 0, 1, 1)
Found:  (0, 1, 0, 1, 0, 1, 1, 0) V

For  2
Trying... (0, 1, 0, 1, 0, 1, 1, 0)
Found:  (0, 0, 1, 1, 1, 0, 0, 0) 8
Found:  (0, 0, 1, 1, 1, 0, 0, 1) 9

For  3
Trying... (0, 0, 1, 1, 1, 0, 0, 0)
Found:  (0, 1, 1, 0, 1, 0, 1, 0) j
Found:  (0, 1, 1, 0, 1, 0, 1, 1) k
Trying... (0, 0, 1, 1, 1, 0, 0, 1)
Found:  (0, 1, 1, 0, 1, 0, 1, 0) j
Found:  (0, 1, 1, 0, 1, 0, 1, 1) k

For  4
Trying... (0, 1, 1, 0, 1, 0, 1, 0)
Found:  (0, 1, 1, 0, 0, 0, 0, 1) a
Found:  (0, 1, 1, 0, 0, 0, 1, 0) b
Found:  (0, 1, 1, 0, 0, 0, 1, 1) c
Found:  (0, 1, 1, 0, 0, 1, 0, 0) d
Trying... (0, 1, 1, 0, 1, 0, 1, 1)
Found:  (0, 1, 1, 0, 0, 0, 0, 1) a
Found:  (0, 1, 1, 0, 0, 0, 1, 0) b
Found:  (0, 1, 1, 0, 0, 0, 1, 1) c
Found:  (0, 1, 1, 0, 0, 1, 0, 1) e

For  5
Trying... (0, 1, 1, 0, 0, 0, 0, 1)
Found:  (0, 1, 0, 1, 0, 0, 0, 1) Q
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z
Trying... (0, 1, 1, 0, 0, 0, 1, 0)
Found:  (0, 1, 0, 1, 0, 0, 1, 0) R
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z
Trying... (0, 1, 1, 0, 0, 0, 1, 1)
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z
Trying... (0, 1, 1, 0, 0, 1, 0, 0)
Found:  (0, 1, 0, 1, 0, 0, 1, 0) R
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z
Trying... (0, 1, 1, 0, 0, 1, 0, 1)
Found:  (0, 1, 0, 1, 0, 0, 1, 1) S
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y

For  6
Trying... (0, 1, 0, 1, 0, 0, 0, 1)
Trying... (0, 1, 0, 1, 1, 0, 0, 0)
Found:  (0, 1, 0, 0, 0, 0, 1, 0) B
Trying... (0, 1, 0, 1, 1, 0, 0, 1)
Found:  (0, 1, 0, 0, 0, 0, 1, 1) C
Trying... (0, 1, 0, 1, 1, 0, 1, 0)
Found:  (0, 1, 0, 0, 0, 0, 0, 1) A
Trying... (0, 1, 0, 1, 0, 0, 1, 0)
Trying... (0, 1, 0, 1, 0, 0, 1, 1)

For  7
Trying... (0, 1, 0, 0, 0, 0, 1, 0)
Found:  (0, 0, 1, 1, 0, 0, 0, 0) 0
Trying... (0, 1, 0, 0, 0, 0, 1, 1)
Found:  (0, 0, 1, 1, 0, 0, 0, 1) 1
Trying... (0, 1, 0, 0, 0, 0, 0, 1)

For  8
Trying... (0, 0, 1, 1, 0, 0, 0, 0)
Found:  (0, 1, 1, 0, 0, 0, 0, 1) a
Found:  (0, 1, 1, 0, 0, 0, 1, 0) b
Found:  (0, 1, 1, 0, 0, 1, 0, 0) d
Found:  (0, 1, 1, 0, 0, 1, 0, 1) e
Trying... (0, 0, 1, 1, 0, 0, 0, 1)
Found:  (0, 1, 1, 0, 0, 0, 0, 1) a
Found:  (0, 1, 1, 0, 0, 0, 1, 1) c
Found:  (0, 1, 1, 0, 0, 1, 0, 0) d
Found:  (0, 1, 1, 0, 0, 1, 0, 1) e

For  9
Trying... (0, 1, 1, 0, 0, 0, 0, 1)
Trying... (0, 1, 1, 0, 0, 0, 1, 0)
Found:  (0, 1, 1, 0, 1, 1, 0, 1) m
Found:  (0, 1, 1, 0, 1, 1, 1, 0) n
Trying... (0, 1, 1, 0, 0, 1, 0, 0)
Trying... (0, 1, 1, 0, 0, 1, 0, 1)
Trying... (0, 1, 1, 0, 0, 0, 1, 1)
Found:  (0, 1, 1, 0, 1, 1, 0, 0) l
Found:  (0, 1, 1, 0, 1, 1, 1, 1) o

For  10
Trying... (0, 1, 1, 0, 1, 1, 0, 1)
Found:  (0, 1, 1, 0, 0, 0, 1, 1) c
Trying... (0, 1, 1, 0, 1, 1, 1, 0)
Trying... (0, 1, 1, 0, 1, 1, 0, 0)
Trying... (0, 1, 1, 0, 1, 1, 1, 1)

For  11
Trying... (0, 1, 1, 0, 0, 0, 1, 1)
Found:  (0, 1, 1, 1, 0, 1, 0, 0) t
Found:  (0, 1, 1, 1, 0, 1, 0, 1) u

For  12
Trying... (0, 1, 1, 1, 0, 1, 0, 0)
Found:  (0, 1, 1, 0, 0, 0, 0, 1) a
Found:  (0, 1, 1, 0, 0, 0, 1, 1) c
Trying... (0, 1, 1, 1, 0, 1, 0, 1)
Found:  (0, 1, 1, 0, 0, 0, 1, 0) b

For  13
Trying... (0, 1, 1, 0, 0, 0, 0, 1)
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z
Trying... (0, 1, 1, 0, 0, 0, 1, 1)
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z
Trying... (0, 1, 1, 0, 0, 0, 1, 0)
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z

For  14
Trying... (0, 1, 0, 1, 1, 0, 0, 0)
Found:  (0, 1, 0, 0, 1, 1, 1, 0) N
Trying... (0, 1, 0, 1, 1, 0, 0, 1)
Trying... (0, 1, 0, 1, 1, 0, 1, 0)

For  15
Trying... (0, 1, 0, 0, 1, 1, 1, 0)
Found:  (0, 1, 1, 0, 0, 1, 1, 0) f

For  16
Trying... (0, 1, 1, 0, 0, 1, 1, 0)
Found:  (0, 1, 0, 1, 1, 0, 0, 0) X
Found:  (0, 1, 0, 1, 1, 0, 0, 1) Y
Found:  (0, 1, 0, 1, 1, 0, 1, 0) Z

For  17
Trying... (0, 1, 0, 1, 1, 0, 0, 0)
Trying... (0, 1, 0, 1, 1, 0, 0, 1)
Trying... (0, 1, 0, 1, 1, 0, 1, 0)
Found:  (0, 1, 1, 0, 1, 1, 1, 0) n

For  18
Trying... (0, 1, 1, 0, 1, 1, 1, 0)
Found:  (0, 1, 0, 1, 0, 1, 1, 0) V
Found:  (0, 1, 0, 1, 0, 1, 1, 1) W

For  19
Trying... (0, 1, 0, 1, 0, 1, 1, 0)
Found:  (0, 1, 0, 0, 1, 0, 1, 0) J
Found:  (0, 1, 0, 0, 1, 0, 1, 1) K
Found:  (0, 1, 1, 1, 0, 0, 1, 1) s
Found:  (0, 1, 1, 1, 0, 1, 0, 0) t
Found:  (0, 1, 1, 1, 0, 1, 0, 1) u
Trying... (0, 1, 0, 1, 0, 1, 1, 1)
Found:  (0, 1, 0, 0, 1, 0, 0, 1) I
Found:  (0, 1, 0, 0, 1, 0, 1, 0) J
Found:  (0, 1, 0, 0, 1, 0, 1, 1) K
Found:  (0, 1, 1, 1, 0, 0, 1, 0) r
Found:  (0, 1, 1, 1, 0, 1, 0, 0) t
Found:  (0, 1, 1, 1, 0, 1, 0, 1) u

For  20
Trying... (0, 1, 0, 0, 1, 0, 1, 0)
Trying... (0, 1, 0, 0, 1, 0, 1, 1)
Trying... (0, 1, 1, 1, 0, 0, 1, 1)
Trying... (0, 1, 1, 1, 0, 1, 0, 0)
Trying... (0, 1, 1, 1, 0, 1, 0, 1)
Found:  (0, 1, 1, 1, 1, 1, 0, 1) }
Trying... (0, 1, 0, 0, 1, 0, 0, 1)
Trying... (0, 1, 1, 1, 0, 0, 1, 0)

Basically prune the branches which are not yielding any output in the next iteration and that narrows down the flag to

cV9jbXB0bmctaXNfZnVu

with a requirement of brute for few of the characters

Flag - bi0sctf{q_cmptng-is_fun}

Katanaverse 0.0

With the exception of the quantity of constraints and the technique for Dividing the points, this level is comparable to 1.0 in many ways. In contrast to the brute technique employed in 1.0, the appropriate quantum method is utilized in 0.0 to divide points more quickly. The same URL as previously has the code implementation for the same.

The platform that allows us to run our code on quantum computers, or the platform that supports the Qiskit module, is required to execute this. I think IBM’s Quantum laboratories is the best platform to conduct this on.

Flag - bi0sCTF{QuBitJugglr}

Closing Notes

It is undoubtedly difficult to use the notion of quantum in a challenge, but I did my best to do so and do it right.

We appreciate everyone who tried their hand at the CTF challenge.

Contact: k1n0r4 | twitter | linkedin