Zeecka zeecka

Hack Code - Genius Level

INS'HACK 2019 - Programming (200 pts)

4 mai 2019 · Programming

INS’HACK 2019 - Hack Code - Genius Level

Détails du challenge

EventChallengeCategoryPointsSolves
INS’HACK 2019Hack Code - Genius LevelProgrammation20062

Nous avons un petit problème de budget avec notre dernière campagne red team. Aidez-nous à y voir plus clair :

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

Ce challenge propose 4 flags différents, les meilleures solutions vous octroieront davantage de flags.

routes.txt - md5sum : 24fdce70d91edc6719c99691f55e029a

Problème

Ce fichier contient 10 000 routes réseau. Nous voulons avoir au moins un network tap sur chaque route. Trouvez une liste de routeurs à intercepter, et gardez le nombre de taps bas ! Vous obtiendrez le premier flag pour toute solution comportant au plus 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

Exemple

Si nous avons les routes suivantes :

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

Une solution pourrait être :

g
b

TL;DR

Il s’agissait d’un problème de dominating set minimal, qui est un problème NP-Hard. Ce problème peut être résolu en calculant le nœud ayant le plus d’occurrences, en supprimant les lignes dans lesquelles ce nœud se trouve, puis en calculant le nouveau nœud ayant le plus d’occurrences… jusqu’à ce qu’il ne reste plus aucune ligne. Cela nous a donné une solution « 127 ».
La solution attendue pour le dernier challenge était « 126 », j’ai donc décidé de conserver toutes les solutions à 127, de garder leurs premiers nœuds de départ et de bruteforcer le 2e nœud, puis de calculer la fin avec le même algorithme et voilà, nous avons obtenu une solution « 126 ».

Méthodologie

Identifier le problème

J’ai décidé d’utiliser la théorie des graphes pour modéliser notre problème. Dans notre graphe, il y a plusieurs routes entre les taps. Nos taps sont les « vertices » (les cercles), et les routes sont les lignes entre chaque vertice (les edges).

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

*En rouge : dominating set d'un petit graphe*

Notre problème est un problème « Minimal Dominating Set ». D’après wikipedia, un dominating set est 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.

En d’autres termes : dans notre problème, nous devons minimiser le nombre de taps (vertices) de sorte que les vertices choisis et leur voisinage direct couvrent le graphe.

Ce problème est un problème KP-Hard, ce qui signifie qu’il n’existe pas de véritable algorithme rapide pour obtenir la meilleure solution. Nous pouvons approcher la meilleure solution avec certains algorithmes, mais si nous voulons obtenir la bonne, nous devons tester chaque vertice.

Implémentation

Comme je l’ai dit, il n’y a pas de solution optimale. Nous pouvons chercher une implémentation de « dominating set » mais nous n’obtiendrons pas la solution optimale. Certaines bibliothèques proposent un algorithme, comme NetworkX ainsi que l’explique cet article. Cependant, dans notre problème, la réponse fournie est bien trop grande pour le challenge.

J’ai décidé d’implémenter mon propre algorithme. Voici l’idée :

  • M est une liste de routes ; L est une route composée de taps ; T est un tap
  • Calculer le nombre d’occurrences pour chaque tap T dans M et les trier du plus présent au moins présent. Le tap le plus utilisé sera nommé best.
  • Parcourir M et supprimer chaque ligne L de M où best figure dans la ligne. En d’autres termes : supprimer chaque route où le tap le plus utilisé est présent.
  • Calculer le nouveau nombre d’occurrences. Vous devez le recalculer car M a changé (lignes supprimées) et le 2e tap le plus utilisé à l’étape 1 n’est pas nécessairement le plus utilisé à l’étape 2. c.-à-d. : si les 2 taps les plus utilisés partagent exactement les mêmes routes, une fois les routes du tap 1 supprimées, le tap 2 n’aura plus aucune route.
  • Parcourir M à nouveau… et répéter chaque étape jusqu’à ce que M soit vide.

Implémentation Python :

# /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)

Sortie :

[+] 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

La solution à 128 taps n’est pas la meilleure. J’ai décidé d’ajouter un peu de bruteforce en testant chaque tap du graphe. Pour cela, j’ai fait une boucle et, pour chaque tap, j’ai calculé M_new (supprimer les routes contenant le tap courant) et appliqué l’algorithme Solve() dessus. J’ai aussi ajouté une condition pour n’afficher que les solutions < 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

Sortie

[+] 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, nous avons plusieurs solutions à 127. Peut-être devrions-nous bruteforcer les 2 premiers taps ? Comme il y a 2387 taps, je vais choisir le tap 1 parmi ceux qui nous ont donné les solutions à 127, puis je vais bruteforcer le 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

Sortie :

[+] 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
...

Soumission

J’ai soumis l’une des réponses correctes à 126 sur la plateforme (je pense que seul l’ordre des taps change entre chaque 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