Hacking Part 2



Tags: Misc HSCTF-2022

Problem Description:

Eljimike is back at it again with his weird hacking contests. Can you help him this time?

This one is more interesting. It seems like a minimal spanning tree problem this time. Because I don’t know how to write code, I found an MST algorithm online. Let’s implement it for the problem. The only difference between the algorithm and the problem is that an edge can have multiple values. Therefore, we need to take the minimum of it. Additionally, we have to account for input, and parse that correctly.

from pwn import *
import gmpy2

io = remote("hacking-pt2.hsctf.com", 1337)
class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        # Initialize the adjacency matrix with zeros
        self.m_graph = [[0 for column in range(num_of_nodes)] 
                    for row in range(num_of_nodes)]

    def add_edge(self, node1, node2, weight):
        if self.m_graph[node1][node2] == 0:
            self.m_graph[node1][node2] = weight
            self.m_graph[node2][node1] = weight
        elif self.m_graph[node1][node2] > weight or self.m_graph[node2][node1] > weight:
            self.m_graph[node1][node2] = weight
            self.m_graph[node2][node1] = weight
    def prims_mst(self):
        # Defining a really big number, that'll always be the highest weight in comparisons
        postitive_inf = float('inf')
        # This is a list showing which nodes are already selected 
        # so we don't pick the same node twice and we can actually know when stop looking
        selected_nodes = [False for node in range(self.m_num_of_nodes)]
        # Matrix of the resulting MST
        result = [[0 for column in range(self.m_num_of_nodes)] 
                    for row in range(self.m_num_of_nodes)]
        indx = 0
        for i in range(self.m_num_of_nodes):
        # While there are nodes that are not included in the MST, keep looking:
        while(False in selected_nodes):
            # We use the big number we created before as the possible minimum weight
            minimum = postitive_inf
            # The starting node
            start = 0
            # The ending node
            end = 0
            for i in range(self.m_num_of_nodes):
                # If the node is part of the MST, look its relationships
                if selected_nodes[i]:
                    for j in range(self.m_num_of_nodes):
                        # If the analyzed node have a path to the ending node AND its not included in the MST (to avoid cycles)
                        if (not selected_nodes[j] and self.m_graph[i][j]>0):  
                            # If the weight path analized is less than the minimum of the MST
                            if self.m_graph[i][j] < minimum:
                                # Defines the new minimum weight, the starting vertex and the ending vertex
                                minimum = self.m_graph[i][j]
                                start, end = i, j
            # Since we added the ending vertex to the MST, it's already selected:
            selected_nodes[end] = True
            # Filling the MST Adjacency Matrix fields:
            result[start][end] = minimum
            if minimum == postitive_inf:
                result[start][end] = 0
            print("(%d.) %d - %d: %d" % (indx, start, end, result[start][end]))
            indx += 1
            result[end][start] = result[start][end]
        # Print the resulting MST
        # for node1, node2, weight in result:
        totaltotal = 0
        for i in range(len(result)):
            for j in range(0+i, len(result)):
                if result[i][j] != 0:
                    totaltotal += result[i][j]
        return totaltotal
for k in range(5):
    asdf = io.recvline().strip().decode()
    a = int(asdf)
    asdfi = Graph(a)
    for i in range(a):
        asdf = io.recvline().strip('\n'.encode()).decode()
        b = list(map(str, asdf.split(" ")))
        for j in range(len(b) - 1):
            c, d = map(int, b[j].split(","))
            c -= 1
            asdfi.add_edge(i, c, d)
    asdff = asdfi.prims_mst()
    asdff += str(asdff) + "\n"

Running this, we get the flag: flag{eLjMiKe_Is_PrOuD_oF_yOu}