Contexte
Battre l’algorithme optimal et trouver une entrée qui donnera le flag.
Analyse
Le script cupide.py se découpe en 4 phases :
-
Saisie d’un chiffre $x$.
-
Saisie d’une liste de chiffres $E = { a, b, c, … }$. L’addition d’un ou plusieurs éléments de $E$ permet d’obtenir $x$, un même élément pouvant être utilisé plusieurs fois (ex: $a + c + c = x$).
-
L’algorithme optimal détermine sa combinaison optimale de chiffres appartenant à $E$ dont l’addition donne $x$.
-
Saisie d’une liste de chiffres appartenant à $E$ dont l’addition a aussi pour résultat $x$. Si cette combinaison utilise moins d’éléments que l’algorithme optimal alors il sera battu.
Algorithme optimal
L’algorithme optimal prend en paramètre $x$.
-
Il recherche dans la liste $E$ triée par ordre décroissant le plus grand chiffre inférieur ou égal au paramètre passé.
-
Le chiffre sélectionné est ajouté à la combinaison optimale.
-
Le chiffre sélectionné est soustrait du paramètre passé.
-
Si la soustraction égale 0, l’algorithme s’arrête sinon il retourne au point 1. récursivement en utilisant pour paramètre le résultat de la soustraction.
Défaut
L’algorithme optimal utilise systématiquement le plus gand chiffre lui empêchant par la suite l’utilisation de chiffres inférieurs dont la combinaison utiliserait moins d’éléments.
Exemples
$ nc localhost 4000
17
10 8 1
L’algo optimal va choisir la combinaison 10 1 1 1 1 1 1 1 soit 8 éléments alors qu’il est possible de n’en utiliser que 3 :
8 8 1
FCSC{bfa26d8861b987d439fe8d8f1004e8b8ea07a7b6f936b844e0f78f43c2dc33e9}
$ nc localhost 4000
8
5 4 1
L’algo optimal va choisir la combinaison 5 1 1 1
4 4
FCSC{bfa26d8861b987d439fe8d8f1004e8b8ea07a7b6f936b844e0f78f43c2dc33e9}
$ nc localhost 4000
6
4 3 1
L’algo optimal va choisir la combinaison 4 1 1
3 3
FCSC{bfa26d8861b987d439fe8d8f1004e8b8ea07a7b6f936b844e0f78f43c2dc33e9}