Solution de ribt pour Guess Me Too

misc

29 novembre 2023

Table des matières

Compréhension du sujet

Il faut prendre le temps de comprendre le code du serveur :

from Crypto.Random.random import getrandbits, randrange

N = 128
C = 136
K =  32

def I():
    try:
        return int(input(">>> "))
    except:
        exit(0)

def w(x):
    return bin(x).count("1") & 1

def game():
    secret = getrandbits(N)

    M = [ I() for _ in range(C) ]
    if len(M) != len(set(M)):
        print("Repetitions are not allowed")
        exit(0)

    E = [0] * C
    E[randrange(C)] = 1
    print([ w(m & secret) ^ e for m, e in zip(M, E) ])

    print("Now, can you guess the secret?")
    ch = I() == secret
    if ch:
        print("Well done!")
    else:
        print("Nope.")

    return ch

if __name__ == "__main__":

    flag = open("flag.txt").read()

    G = [ game() for _ in range(K) ]
    if False not in G:
        print(flag)

On peut résumer le jeu comme cela :

  • Le serveur choisit un nombre aléatoire de 128 bits.
  • Le joueur doit proposer 136 nombres à comparer avec le nombre secret.
  • Pour chaque proposition, le serveur fait un et logique entre le nombre proposé par le joueur et son nombre choisi et il nous dit si le nombre de 1 dans le résultat de ce et est pair ou impair.
  • Le joueur doit deviner le nombre secret.

Avec quelques contraintes pour pimenter le jeu :

  • Le serveur enregistre d’abord TOUTES les propositions du joueur. Après cela il envoie TOUTES ses réponses. Le jeu n’est pas interactif.

  • Le serveur ment forcément pour une (et une seule) de ses 136 réponses.

  • Le joueur ne peut pas proposer deux fois le même nombre.

Résolution

Dans un premier temps, je me demande comment je jouerais à ce jeu si le serveur ne mentais pas. Notre propostion est en fait un masque à appliquer au nombre secret pour ensuite avoir une sorte de somme de contrôle.

J’imagine donc la stratégie suivante :

  • Proposer le nombre $2^{128} - 1$ (composé de 128 bits à 1) comme ça le et entre le masque et le nombre secret renvoie simplement le nombre secret et l’information renvoyée par le serveur sera la réponse à la question Le nombre de bits à 1 dans le nombre secret est-il impair ?.
  • Proposer le nombre composé de 128 bits à 1 sauf le 1er qui sera à 0. Cela permettra de réponse à la question Si je remplace le 1er bit de ton nombre par un 0 , le nombre de bits à 1 est-il impair ?. Si la réponse est la même que celle de la question précédente alors le 1er bit est un 0 car si c’était un 1 la somme de contrôle aurait été changée en appliquant mon masque.
  • Puis proposer le nombre composé de 128 bits à 1 sauf le 2e qui sera à 0 et comparer avec la 1ère réponse pour savoir si le 2e bit du nombre secret est un 0 et ainsi de suite…

Cela me permet en 129 questions de deviner le nombre en entier.

Edit : En relisant ce WU à tête reposée je me dis que ma stratégie n’est pas optimale. Je récupère 128 bits d’informations avec 129 questions, on devrait pouvoir faire un chouïa mieux. Et en réfléchissant un tout petit peu je comprends que la stratégie optimale c’est d’envoyer un masque avec tous les bits à 0 sauf un comme ça le serveur nous renvoie la valeur de ce bit là. La simplification du code pour appliquer cette stratégie est laissée en exercice au lecteur 😉

Mais le problème est que, comme le serveur ment une fois, mon nombre diffère d’un bit du nombre secret. Un (et un seul) bit sur 128 est incorrect. Et j’ai le droit de poser 7 questions pour savoir lequel c’est.

7 questions ça veut dire que je peux retirer 7 bits d’information. Or justement l’information que je cherche c’est la position du bit erroné (comme je sais qu’il y en a un seul) et cette information est un nombre entre 0 et 127… soit un nombre codé sur 7 bits !

Il faudrait que ma 130e question soit Quel est le premier bit de la position de mon erreur encodée en binaire ?… En se rappelant que ces 7 questions doivent être “universelles” car je ne connaîtrai pas le nombre que je pense être le nombre secret au moment de les poser. En fait il me faudrait 7 patterns pour lesquels je vérifierais si les bits désignés sont identiques ou non entre ma version et celle du serveur. 7 patterns différents qui, quelle que soit la position de l’erreur, me permettent de la localiser à coup sûr. Voici 7 patterns qui remplissent ces conditions :

11111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000
11111111111111111111111111111111000000000000000000000000000000001111111111111111111111111111111100000000000000000000000000000000
11111111111111110000000000000000111111111111111100000000000000001111111111111111000000000000000011111111111111110000000000000000
11111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000
11110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000011110000
11001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100
10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010

En regardant bien, j’ai écrit tous les nombre de 127 à 0 en binaire et en colonne. Si par exemple le premier pattern renvoie une réponse différente de celle que je peux calculer sur le nombre que je pense être la solution, que le 2e masque donne une somme de contrôle identique sur le nombre du serveur et le mien, que le 3e pattern donne une parité différente et tous les autres une parité identique. Cela signifiera que la position de mon erreur est situé à la position 1010000 soit 80. J’aurai donc à inverser le 80e bit.

Pour résumer, voici les 136 nombres que je vais envoyer au serveur (en binaire) :

11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000
11111111111111111111111111111111000000000000000000000000000000001111111111111111111111111111111100000000000000000000000000000000
11111111111111110000000000000000111111111111111100000000000000001111111111111111000000000000000011111111111111110000000000000000
11111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000
11110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000011110000
11001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100
10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010

Le 1er sert de référence (on suppose que le mensonge n’intervient pas à ce moment-là), les 128 suivants interrogent les 128 bits du nombre secret et les 7 derniers demandent une info qui me permettra de localiser le bit erroné.

Et voici le programme Python (commenté) qui automatise tout ça :

from pwn import remote
import json

N = 128
C = 136
K =  32

def w(x):
    return bin(x).count("1") & 1

conn = remote("challenges.france-cybersecurity-challenge.fr", 2003)

mask = 2**N - 1  # tous les bits à 1
M = [mask]

for i in range(N):
    M.append(mask ^ 2**i)  # tous les bits à 1 sauf le i-ème

M += [
    0b11111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000,
    0b11111111111111111111111111111111000000000000000000000000000000001111111111111111111111111111111100000000000000000000000000000000,
    0b11111111111111110000000000000000111111111111111100000000000000001111111111111111000000000000000011111111111111110000000000000000,
    0b11111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000,
    0b11110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000011110000,
    0b11001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100,
    0b10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010,
]

for _ in range(K):
    for i in range(C):
        conn.recvuntil(">>> ")
        conn.send(str(M[i])+"\n")

    infos = json.loads(conn.recvline())
    print(infos)

    ref = infos[0]
    ans = ""
    for b in infos[1:N+1]:  # pour les 128 questions on regarde si la réponse diffère de la référence
        if b != ref:
            ans = "1"+ans
        else:
            ans = "0"+ans
    print(ans)
    show = int(ans, 2) # le serveur nous "montre" ce nombre

    if w(show) != ref:  # si la somme de contrôle est identique alors le serveur n'a pas menti sur les 129 premières réponses
        test = [ w(m & show) for m in M[129:]]  # j'applique mes 7 dernières questions au nombre que je pense

        err = 0
        for i in range(7):  # le rang du bit erroné est donné grâce aux 7 patterns
            err *= 2
            if infos[129+i] != test[i]:
                err += 1

        n = show ^ 2**err  # on inverse le bit de rang err
    else:
        n = show
    print("erreur digit ", err)
    print(bin(n)[2:])
    conn.recvuntil(">>> ")
    conn.send(str(n)+"\n")
    print(conn.recvline().decode())

conn.interactive()

Le programme joue ses 32 parties… Et affiche le flag : FCSC{e055ea6ffd540907c52a34bef47cbf79758e6732af597d98c33aceade78979c5}

Merci pour ce challenge algorithmique un peu prise de tête !