Guess Me

Dans ce challenge misc, nous allons tenter de récupérer un flag en devinant un nombre généré aléatoirement.

Analyse

Nous allons tout d'abord regarder le script Python guessme.py.

import os

N = 64
M = 16
success = 0
try:
	for i in range(M):
		secret = int.from_bytes(os.urandom(N // 8), "big")
		for _ in range(N + 1):
			x = int(input(">>> "))
			if secret < x:
				print("-1")
			elif secret > x:
				print("+1")
			elif secret == x:
				print("0")
				print(f"{i+1} found, {M-1-i} more to go")
				success += 1
				break
	if success == M:
		print(open("flag.txt").read())
except:
	pass

Analysons ce script :

2 variables sont initialisées. Net M
Nous avons ensuite une boucle for à partir d'un range compris de 0 à 16
Un nombre aléatoire de 8 octets est généré (64 // 8 = 8) (l'opérateur // rentourne la partie entière d'une division euclidienne)
Nous avons aussi une 2e boucle for qui va itérer entre 0 et 65
On saisit une valeur entière au clavier
Si la valeur aléatoirement générée est inférieure à la valur saisie, alors on affiche -1
Sinon si la valeur aléatoirement générée est supérieur à la valeur saisie, on affiche +1
Sinon si la valeur aléatoirement générée est égale à la valeur saisie, on affiche un message pour dire qu'on a trouvé la valeur et qu'il nous reste {M-1-i} nombres à trouver

Pour résumer, nous avons 16 nombres aléatoires à trouver, dans la limite de 65 tentatives chacune.

Un algorithme de recherche bien connu est la dichotomie. Le but étant de trouver la valeur d'une échelle de nombres en testant la valeur / 2 entre le min et le max.

Exemple : sur une echelle de 1 à 10, avec une itération de 1 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] par exemple.

Pour trouver la valeure 7, nous allons faire (0 + 10) / 2 = 5.

5 n'étant pas la bonne valeur, et sachant que la valeur à trouver (ici 7) est supérieure à 5, nous allons chercher la valeur médiane entre 5 et 10 soit : (5 + 10) // 2 = 7

(// pour récupérer la valeur entière de la division)

Écrivons un script pour faire la recherche des 16 nombres aléatoirement générés

Scripting

import os
import socket
import time

class Netcat:
    """ Python 'netcat like' module """

    def __init__(self, ip, port):
        self.buff = ""
        self.socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.socket.connect((ip, port))

    def read(self, length=1024):
        """ Read 1024 bytes off the socket """

        return self.socket.recv(length)

    def read_until(self, data):
        """ Read data into the buffer until we have data """

        while not data in self.buff:
            self.buff += self.socket.recv(1024)

        pos = self.buff.find(data)
        rval = self.buff[:pos + len(data)]
        self.buff = self.buff[pos + len(data):]

        return rval

    def write(self, data):
        self.socket.sendall(data)

    def close(self):
        self.socket.close()

nc = Netcat('challenges.france-cybersecurity-challenge.fr', 2001)
N = 64
max = int.from_bytes(b"\xff\xff\xff\xff\xff\xff\xff\xff", "big")
min = 0
max_range = max // 2
min_range = 0
current = max
precedent_current = current
data = nc.read().decode().strip()
print(data)
nc.write((str(max)+"\n").encode())
print(max)
data = nc.read().decode().strip()
print(data)
i = 1
while "16 found, 0 more to go" not in data:
    if "-1" in data:
        max_range = current
        current = (min_range + max_range) // 2
    elif "+1" in data:
        min_range = current
        current = (min_range + max_range) // 2
    elif "-1"not in data or "+1" not in data:
        max_range = max
        min_range = 0
        current = max // 2
        i=0
        nc.write((str(current) + "\n").encode())
        data = nc.read().decode().strip()
        while "1" not in data:
            data = nc.read().decode().strip()
            print(data)
        print(data)
        continue
    print("min range : " + str(min_range))
    print("max range : " + str(max_range))
    print("N : "+str(i))
    print(str(current))
    nc.write((str(current)+"\n").encode())
    data = nc.read().decode().strip()
    while "1" not in data:
        data = nc.read().decode().strip()
        if "more to go" in data:
            break
        print(data)
    print(data)
    if i > 65:
        print("break")
        break
    i = i + 1

nc.write((str(max)+"\n").encode())
print(str(max))
data = nc.read().decode().strip()
print(data)

Dans ce script, nous avons une classe Netcat pour pouvoir se connecter via sockets sur le serveur.

Note : cette classe n'est pas de moi, merci github

Explications du script :

Après la classe Netcat qui nous permet de manipuler les sockets TCP
On initialise la connexion au serveur du challenge
On stocke la valeur N pour ne pas faire de recherche au dela du nombre de tentatives autorisées
On stocke la valeur maximale et minimale qui peut être générée aléatoirement par le script guessme.py
On stocke la valeur maximale et minimale que l'on va trouver au fur et à mesure de l'exécution du script.
On stocke aussi les valeurs courantes et précédemment trouvées lors de l'execution du script.
On initalise les transactions en lisant le socket pour récupérer la réponse du serveur
On envoie notre première valeur (valeur médiane entre 0 et la valeur maximale qui peut être générée sur 8 octets)
On initialise la variable i pour avoir l'itération courante de la recherche
Tant que l'on n'a pas la phrase 16 found, 0 more to go dans la réponse du serveur
Si -1 est dans la réponse, cela veut dire que la valeur à trouver est inférieure à la valeur envoyée, donc nous allons diviser par 2 la somme de la valeur minimum et maximum et stocker la valeur précédemment envoyée comme valeur maximale pour la prochaine itération
Si +1 est dans la réponse, celà veut dire que la valeur à trouver est supérieure à la valeur envoyée, donc nous allons diviser par 2 la valeur minimum et maximum et stocker la valeur précédemment envoyée comme valeur minimale pour la prochaine itération
Si -1 ou +1 n'est pas dans la réponse, nous réinitialisons les variables de recherche comme au début du script car cela veut dire que l'on a trouvé la valeur aléatoire
On affiche le range min et max à chaque itération ainsi que la valeur de l'itération courante
Si on dépasse les 65 possibilités, on stop le script car on ne pourra pas trouver la valeur vu qu'une autre aura été générée et qu'on ne pourra pas trouver les 16 valeurs
On récupère et on affiche la réponse du serveur qui contient le flag

Les boucles while "1" not in data sont là pour récupérer toutes les réponses du serveur en cas de latence réseau / load de la machine en face.

Cette solution n'est vraiment pas parfaite et assez crade. Mais ça marche la plupart du temps.

Résultat :

>>>
18446744073709551615
-1
>>>
min range : 0
max range : 18446744073709551615
N : 1
9223372036854775807
-1
>>>
min range : 0
max range : 9223372036854775807
N : 2
4611686018427387903
+1

[...]

min range : 16255468609472438399
max range : 16255468609472438527
N : 56
16255468609472438463
+1
min range : 16255468609472438463
max range : 16255468609472438527
N : 57
16255468609472438495
0
15 found, 1 more to go
-1
>>>

[...]

>>>
min range : 8616244697834045895
max range : 8616244697834045899
N : 61
8616244697834045897
-1
min range : 8616244697834045895
max range : 8616244697834045897
N : 62
8616244697834045896
0
16 found, 0 more to go
FCSC{7b20416c4f019ea4486e1e5c13d2d1667eebac732268b46268a9b64035ab294d}

Flag :

FCSC{7b20416c4f019ea4486e1e5c13d2d1667eebac732268b46268a9b64035ab294d}