Hack Code - Genius Level

INS'HACK 2019 - Programming (200 pts).

INS’HACK 2019 - Hack Code - Genius Level

Challenge details

Event	Challenge	Category	Points	Solves
INS’HACK 2019	Hack Code - Genius Level	Programming	200	62

We have a little budgeting issue with our latest red team campaign. Please help us figure it out :

https://hack-code.ctf.insecurity-insa.fr

This challenge has 4 different flags, better solutions will grant you more flags.

routes.txt - md5sum : 24fdce70d91edc6719c99691f55e029a

Problem

This file contains 10 000 network routes. We want to have at least one network tap on each route. Find a list of routers to intercept, and keep the number of taps low ! You will get the first flag for any solution with at most 150 taps.

head routes.txt

e5a10f35,3514c407,c4eb2a08,9ab8a703,c48ecbc5,cbd85052,d7d3fe6d,cefca924,100284b7
d46e5c37,5e054df9,68febf4c,ed83bae6,d75d5106,38cd53d1,02e60b7d,2cc8c1a5,fd7476b3,6d7eec26,0d9b5434,32696a91
eb827452,c859bec6,4d14cef2,0f386ce7,e97100bf,c7214949,9f6c10a5,1eeb2715,3bf1af45
59b7380e,69d8550b,54cf5fc3,93e7f2e0,0a86dbb1,197d0ecb,c7439b27,0a984a37,e5a10f35,74439dae,30fcdf42,f64c2747
e5a10f35,4f833f83,197cc56d,18eca114,aac1d765,6893b042,a85ec4f2,917b943f,2518e3c7,f2ed2491,38ae1ae1,b36267f7,702e8987,64d000d4,7c5c7a0a,6db414eb,b812acf5,70ea5af6,8be79885,5a03698a,c2031bb6
ab1eabc8,625f50f8,e0daa618,94e469e7,8f97501f,2e094eb6
aca5924c,91774308,fc332b15,b36267f7,38ae1ae1,f2ed2491,2518e3c7,917b943f,a85ec4f2,6893b042,aac1d765,18eca114,2ef22b69,197cc56d,e5a10f35
ff05d014,46eef43f,439f2ad2,1861cfb1,9ffe046a,a2adb0d9,4454d916,dc98dc28,23aee827,31c02fce,87296558,2d036ecb,fc9a452f,f40c6ef0
8c93b33d,289c2573,79318626,ce54d138,dfcedb2a,24572287,68deebf4,7d49a0cd,2ba8adc5
40ecaca0,c36b4e4b,060679b2,ab5e1d7c,9a46c3fe

Example

If we have the following routes :

c,b,a
d,a,g
b,c,e
f,d,g

One solution could be :

g
b

TL;DR

This was a minimal dominating set problem which is a NP-Hard problem. This problem can be solved by computing the node with the most occurrences, remove the lines in which the node is, then compute the new node with the most occurrences… until there is no line left. This gave us a “127” solution.
The solution expected for the latest challenge was “126” so I decided to keep every 127 solutions, keep their first starting nodes and bruteforce the 2nd node, then compute the end using the same algorithm and here it is, we got a “126” solution.

Methodology

Identifying the problem

I decided to use the graph theory to model our problem. In our graph there is multiple roads between taps. Our taps are the “vertices” (circle), and the roads are the lines between each vertice (edges).

![dominating.png](/files/inshack_2019/Genius/dominating.png)
*In red: dominating set of a small graph*

Our problem is a “Minimal Dominating Set” problem. According to wikipedia, a dominating set is a subset D of V such that every vertices not in D is adjacent to at least one member of D. The domination number γ(G) is the number of vertices in a smallest dominating set for G.

In other word: in our problem we need to minimise the number of taps (vertices) such as the choosen vertices and their direct neighborhood fulfill the graph.

This problem is a KP-Hard problem, which mean that there is no real fast algorithm to get the best solution. We can approximate the best solution with some algorithms but if we want to have the correct one, we need to test each vertice.

Implementation

As I said, there is no optimal solution. We can search for “dominating set” implementation but we will not get the optimal solution. Some library propose algrithm such as NetworkX as explain in this article. However, in our problem the given response is way too big for the challenge.

I decided to implement my own algorithm. Here is the idea:

M is a list of roads; L is a road composed of taps; T is a tap
Compute the number of occurrences for each taps T in M and sort them from the most present to the least. The most used tap will be name best.
Parse M and remove each line L of M where the best is in the line. In other word: remove each road where the most used tap is present.
Compute the new number of occurrences. You must re-compute it because M has changed (lines removed) and the 2nd most used tap in step 1 is not necessarily the most used in step 2. IE: if the 2 most used taps share exactly the same roads, once the roads of tap 1 are removed, then tap 2 will not have any road left.
Parse M again… and repeat each step until M is empty.

Python implementation:

# /bin/env python3
# -*- coding:utf-8 -*-

#################    M = List of roads                 #########################

with open("routes.txt",'r') as f:
    M = f.read()
M = M.split('\n')
M = [x.split(",") for x in M]  # M = List of roads
M.pop()  # remove empty road

################################################################################


def getTopTaps(M):
    """ Return a list of taps in M from the most used to the less used """
    dtaps = {}
    for L in M:
        for tap in L:
            dtaps[tap] = dtaps.get(tap, 0) + 1  # Increment occurence
    topTaps = sorted(dtaps.items(), key=lambda x: x[1])[::-1]  # Sort
    topTaps = [x[0] for x in topTaps]  # Keep name only
    return topTaps


def Solve(M,s=[]):
    """ Recursiv function,
    - M is the current list of roads
    - s are the used taps (only used at the end to print the solution)
    """

    topTaps = getTopTaps(M)
    best = topTaps[0]
    s.append(best)  # add best to s

    M_new = []  # M after roads are removed
    for L in M:
        if best not in L:  # Remove road where best is in it
            M_new.append(L)

    if len(M_new) == 0:  # No roads left
        print("[+] "+str(len(s))+" ==> "+str(' '.join(s)))  # Print number of tap for solution
    else:
        Solve(M_new,list(s))  # Solve on the new M

### Solve :

Solve(M)

Ouput:

[+] 128 ==> e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 32be7184 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 ed83bae6 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f bc9049f3 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d cfae9f8e b51e4382 f0b8318e 435b85ac f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a dec18abb e8d835aa 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 bfb54ff8 be83d735 1f8c57a0 763d8f7c a342005c 72213ae3 d5de2bf3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 32696a91 c0028f7c 2a11dff7

Bruteforce

The 128 tapssolution is not the best one. I decided to add some bruteforce by testing each tap of the graph. For this, I made a loop and, for each taps, I computed M_new (remove road containing the current tap) and apply the Solve() algorithm en it. I also added a condition to print only solution < 128.

# /bin/env python3
# -*- coding:utf-8 -*-

BEST_SCORE = 128

#################    M = List of roads                 #########################

with open("routes.txt",'r') as f:
    M = f.read()
M = M.split('\n')
M = [x.split(",") for x in M]  # M = List of roads
M.pop()  # remove empty road

################################################################################


def getTopTaps(M):
    """ Return a list of taps in M from the most used to the less used """
    dtaps = {}
    for L in M:
        for tap in L:
            dtaps[tap] = dtaps.get(tap, 0) + 1  # Increment occurence
    topTaps = sorted(dtaps.items(), key=lambda x: x[1])[::-1]  # Sort
    topTaps = [x[0] for x in topTaps]  # Keep name only
    return topTaps


def Solve(M,s=[]):
    """ Recursiv function,
    - M is the current list of roads
    - s are the used taps (only used at the end to print the solution)
    """

    topTaps = getTopTaps(M)
    best = topTaps[0]
    s.append(best)  # add best to s

    M_new = []  # M after roads are removed
    for L in M:
        if best not in L:  # Remove road where best is in it
            M_new.append(L)

    if len(M_new) == 0:  # No roads left
        if len(s) < BEST_SCORE:
            print("[+] Got best score starting with "+s[0])
            print("[+] "+str(len(s))+" ==> "+str(' '.join(s)))  # Print number of tap for solution
    else:
        Solve(M_new,list(s))  # Solve on the new M

### Solve

tapsList = getTopTaps(M)  # List of taps

for tap in tapsList:
    M_current = []
    for L in M:
        if tap not in L:  # Remove road where tap is in it
            M_current.append(L)
    Solve(M_current,[tap])  # Solve with a forced tap

Ouput

[+] Got best score starting with bfb54ff8
[+] 127 ==> bfb54ff8 e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 3d6fa6dd 8c93b33d b70a9235 45df9dfc 453d437e 32be7184 d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 ed83bae6 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f bc9049f3 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d b51e4382 f0b8318e 435b85ac f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a dec18abb e8d835aa 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 a342005c d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 be83d735 1f8c57a0 763d8f7c 72213ae3 d5de2bf3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 32696a91 c0028f7c 2a11dff7
[+] Got best score starting with 32696a91
[+] 127 ==> 32696a91 e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 32be7184 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d dec18abb 9c965aaa fffce5b2 b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 ed83bae6 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d cfae9f8e b51e4382 be83d735 f0b8318e 435b85ac 3d9f9c70 48e2375e f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a e8d835aa 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 cc4babff 28b514b1 1eb38c6d 74439dae d75d5106 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 bfb54ff8 1f8c57a0 763d8f7c a342005c 72213ae3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 c0028f7c 2a11dff7
[+] Got best score starting with 46eef43f
[+] 127 ==> 46eef43f e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 e6608890 a656ec74 32be7184 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 366b0fc2 9cefa7a2 68deebf4 85ea0d43 ed83bae6 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f bc9049f3 859b2713 8b6fd6ec 7f655bbb dc98dc28 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d b51e4382 f0b8318e 435b85ac f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a dec18abb e8d835aa bfb54ff8 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 be83d735 1f8c57a0 763d8f7c 72213ae3 d5de2bf3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 32696a91 c0028f7c 2a11dff7
[+] Got best score starting with a342005c
[+] 127 ==> a342005c e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 e6608890 a656ec74 32be7184 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 ed83bae6 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f bc9049f3 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d b51e4382 f0b8318e 435b85ac f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a dec18abb e8d835aa bfb54ff8 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 be83d735 1f8c57a0 763d8f7c 72213ae3 d5de2bf3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 32696a91 c0028f7c 2a11dff7
[+] Got best score starting with ff05d014
[+] 127 ==> ff05d014 e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 32be7184 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 366b0fc2 9cefa7a2 68deebf4 85ea0d43 ed83bae6 dc98dc28 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f bc9049f3 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d b51e4382 f0b8318e 435b85ac f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a dec18abb e8d835aa bfb54ff8 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 be83d735 1f8c57a0 763d8f7c 72213ae3 d5de2bf3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 32696a91 c0028f7c 2a11dff7
[+] Got best score starting with 16cccd8e
[+] 127 ==> 16cccd8e e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 32be7184 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 ed83bae6 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f bc9049f3 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d b51e4382 f0b8318e 435b85ac f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a dec18abb e8d835aa bfb54ff8 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 be83d735 1f8c57a0 763d8f7c 72213ae3 d5de2bf3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 32696a91 c0028f7c 2a11dff7
[+] Got best score starting with 1ee2d70f
[+] 127 ==> 1ee2d70f e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 32be7184 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 8c93b33d 3d6fa6dd b70a9235 45df9dfc 453d437e d75d5106 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d fffce5b2 9c965aaa b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 32696a91 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 3d9f9c70 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d cfae9f8e b51e4382 f0b8318e 435b85ac 48e2375e f8f62aff 40ee0a0b 3f228bf4 326ceb8a dec18abb e8d835aa 72464937 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 ed83bae6 28b514b1 1eb38c6d 74439dae 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 bfb54ff8 be83d735 1f8c57a0 763d8f7c a342005c 72213ae3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 c0028f7c 2a11dff7
...

Ok we got multiple 127 solutions. Maybe we should bruteforce the 2 first taps? Since there is 2387 taps, I’m gonna choose the tap 1 among the ones which gave us the 127 solutions, then I’m gonna bruteforce the tap 2.

# /bin/env python3
# -*- coding:utf-8 -*-

BEST_SCORE = 127

#################    M = List of roads                 #########################

with open("routes.txt",'r') as f:
    M = f.read()
M = M.split('\n')
M = [x.split(",") for x in M]  # M = List of roads
M.pop()  # remove empty road

################################################################################


def getTopTaps(M):
    """ Return a list of taps in M from the most used to the less used """
    dtaps = {}
    for L in M:
        for tap in L:
            dtaps[tap] = dtaps.get(tap, 0) + 1  # Increment occurence
    topTaps = sorted(dtaps.items(), key=lambda x: x[1])[::-1]  # Sort
    topTaps = [x[0] for x in topTaps]  # Keep name only
    return topTaps


def Solve(M,s=[]):
    """ Recursiv function,
    - M is the current list of roads
    - s are the used taps (only used at the end to print the solution)
    """

    topTaps = getTopTaps(M)
    best = topTaps[0]
    s.append(best)  # add best to s

    M_new = []  # M after roads are removed
    for L in M:
        if best not in L:  # Remove road where best is in it
            M_new.append(L)
    if len(s) >= BEST_SCORE:
        return
    if len(M_new) == 0:  # No roads left
        if len(s) < BEST_SCORE:
            print("[+] "+str(len(s))+" ==> "+str(' '.join(s)))  # Print number of tap for solution
    else:
        Solve(M_new,list(s))  # Solve on the new M

### Solve:

taps1 = ["bfb54ff8","32696a91","46eef43f","a342005c","ff05d014","16cccd8e",
"1ee2d70f","0a5ab0f8","48e2375e","1f30daa4","f2d7c991","2b59fb0e","d5de2bf3",
"71cc1bd2","f377b4fb","69487797","fa688dee","756d687b","70210a59","29bf0c1f",
"11c03bdf","f62e7af1","7643b3f0","2be7e28c"]

for t1 in taps1:
    M2 = []  # M without tap 1
    for L in M:
        if t1 not in L:  # Remove road where best is in it
            M2.append(L)
    tapsList = getTopTaps(M2)[50:]  # List of taps
    for t2 in tapsList:
        M_current = []  # M without tap 1 and tap 2
        for L in M2:
            if t2 not in L:  # Remove road where tap is in it
                M_current.append(L)
        Solve(M_current,[t1,t2])  # Solve with a forced tap

Ouput:

[+] 126 ==> bfb54ff8 32696a91 e5a10f35 5070956c fc3094b2 da06c64f c633d389 4301b2e9 e6608890 a656ec74 5daefe0d 3d3452f2 628a7eb9 67846f20 0f386ce7 3d6fa6dd 8c93b33d b70a9235 45df9dfc 453d437e 32be7184 556f8572 8c89de99 ab16a2fc fc55d2bc ddad739d dec18abb 9c965aaa fffce5b2 b36267f7 cb9101fa 6dc19d5b ae43a954 dc98dc28 366b0fc2 9cefa7a2 68deebf4 85ea0d43 71651baa de354f47 bb7d6e5c b5e69d6e 2e094eb6 c41cb9f6 f1d2d613 ed83bae6 35baf228 9a46c3fe 7b4e5e8e 5cc167e0 abc7a89c 0f13b66f 859b2713 8b6fd6ec 7f655bbb 9f6c10a5 ae9bf0c7 0cd1f825 65aadb0f bdc365c1 61e4803f 61cb28ef dbffb4f3 bdae8a7a dc17e12d b51e4382 be83d735 f0b8318e 435b85ac 3d9f9c70 48e2375e f8f62aff 40ee0a0b 1ee2d70f 3f228bf4 326ceb8a e8d835aa 59133c3f fa688dee 0d5a45b4 fd87cd09 e8e5c457 8417d624 a342005c d126ef39 d42ed823 71015428 19e34302 4fe2ab99 100284b7 3e777083 bc1e10a5 cc4babff 28b514b1 1eb38c6d 74439dae d75d5106 878cdd1f 9d0c98ba bdfe9853 a6602da0 301f5cc3 6e3df68d 0b950b5d 62d05ae0 fe9432b8 5d0c4fdf 34d6f7ed 22f829a3 c2f65f49 1f8c57a0 763d8f7c 72213ae3 658a7fac 060679b2 571e5d8f 6734fb11 8c15eb99 01de1787 1ccb4ad0 d5f013e6 29f7bd82 2d036ecb 1afd57e3 c0028f7c 2a11dff7
...

Submit

I submitted one of the correct 126 response on the plateform (I think than only the order of the taps change between each solution):

![submit.png](/files/inshack_2019/Genius/submit.png)

![flags.png](/files/inshack_2019/Genius/flags.png) ```text The first flag is INSA{N0t_bad_f0r_a_start}. The next flag will be awarded at <= 135. INSA{135_is_pretty_g0Od_but_how_l0w_c4n_u_gO}. Get your next flag at <= 128 INSA{Getting_cl0ser}. The last flag is waiting for you at 126 ! INSA{Master_of_0pt1mizatioN}. 126 is the best solution we could find, please contact @Mathis_Hammel or another admin if you find lower and we'll award you a few bonus points ! ```

Flag

INSA{N0t_bad_f0r_a_start}
INSA{135_is_pretty_g0Od_but_how_l0w_c4n_u_gO}
INSA{Getting_cl0ser}
INSA{Master_of_0pt1mizatioN}

Zeecka