Informations

  • Catégorie : Crypto
  • Niveau : Medium
  • Auteur : Hiruko
  • Flag : MB{LCG_IS_UNSECURE_?}

Intitulé

Vous avez capté des échanges entre deux parties. Un espion a découvert le protocole de communication. À vous de percer le générateur sous-jacent et de prendre l'avantage.

Write-up

La première chose à faire est de récupérer le code du serveur qui communique avec le client, contenu dans le .zip du challenge.

Dans le README.md, on trouve une mention d’un développeur qui aurait publié le code source du serveur sur GitHub.

Une fois tous les morceaux de code récupérés, l’analyse peut commencer.

Dans ce challenge, nous avons un échange sécurisé entre un client et un serveur. La communication est chiffrée à l’aide d’un XOR, mais la clé utilisée pour le chiffrement est générée via un générateur pseudo-aléatoire linéaire congruentiel (LCG). Ce type de générateur est réversible et prédictible si l'on connaît l’état initial ou actuel.

Le chiffrement fonctionne comme suit :

  • Le serveur génère une séquence de nombres pseudo-aléatoires via le LCG.
  • La taille du message détermine combien de nombres sont générés.
  • Les bits de poids fort de ces nombres sont extraits pour générer une clé de chiffrement.
  • Le message est ensuite XORé avec cette clé avant d’être envoyé au client.

🎯 Objectif

Votre objectif est de récupérer l’état actuel du serveur, qui est envoyé à chaque commande. En utilisant cet état, vous devez inverser le LCG, calculer la clé, et déchiffrer les communications.

Étapes de Résolution

1. Analyse du Code Client et Serveur

Étudiez les codes fournis pour comprendre :

  • l’utilisation du LCG ;
  • le rôle de la taille du message ;
  • la construction de la clé de chiffrement.

2. Extraction de l'État Actuel

L'état actuel du serveur est transmis à chaque commande. Identifiez ce champ dans le trafic intercepté.

3. Inversion du LCG

Utilisez cet état pour reproduire les valeurs générées. Le LCG étant prévisible, il est possible de générer la même séquence que le serveur.

4. Déchiffrement du Message

Générez la même clé à partir des bits de poids fort, puis appliquez un XOR inverse pour récupérer le message original.

import pwn import parameters import base64 as b64 HOST = '0.0.0.0' PORT = 12345 FIRSTRUN = True class LCG: def __init__(self): self.state = 0 self.a = parameters.a self.c = parameters.c self.m = parameters.m def nextGeneration(self): self.state = (self.a * self.state + self.c) % self.m return self.state def genKeyXor(self, length): key = bytearray() for i in range(length): part = self.nextGeneration() key += ((part >> ((part.bit_length() - 8) if part.bit_length() > 8 else 0)) & 0xFF).to_bytes(1, 'big') return bytes(key) def encrypt(self, msg): return pwn.xor(msg.encode(), self.genKeyXor(len(msg))) def decrypt(self, encrypted_msg): return pwn.xor(encrypted_msg, self.genKeyXor(len(encrypted_msg))).decode() def backGeneration(self): self.state = ((self.state - self.c) * pow(self.a, -1, self.m)) % self.m return self.state l = LCG() # FLAG 1 # Second command l.state = 15813009896856 commande="i/zPktPX5qjw9ua0lZyJp58=" commande=b64.b64decode(commande) for i in range(len(commande)): l.backGeneration() key = l.genKeyXor(len(commande)) print(pwn.xor(commande, key)) # Response command reponse="lda3i+/tt5SU4PK02tGTjvOk252G5tCC1tXe2tfi6OWs06Pq0arIkI68kaiQireW84yX59TVt6u318zk" reponse=b64.b64decode(reponse) key = l.genKeyXor(len(reponse)) print(pwn.xor(reponse, key)) # Third command l.state = 17068328826065 commande="ttvzz9LH0bb1iYHCrJaV" commande=b64.b64decode(commande) for i in range(len(commande)): l.backGeneration() key = l.genKeyXor(len(commande)) print(pwn.xor(commande, key)) # Response command reponse="7feLus36x924tKKVyqGzmfLCqbbDq8Ph68ekraPnkZ/kprzcy5DG96e9rJWVvKKlxZ+eqvCehpXFpaTWkLmk2uetosPD8J/g9savpsDYivv21YrgkPi54ZSewrzCoautmZetndW7p7Hat+Hb3oOQ08iJqJTywbGS1pbsu8ung4LaluTQ24Dwm4i4t5CIh/SwzY3Cs7zlm4uj97+ThOeTrLPxiJrQp8aNiZq0qLX7ucTi0enY/Ny4146l9d3J7O/21PXux/GE3/28q4CE0YK5l8LY3YyM3eDwtNqi6uK3mcC0toqPktLP67WfiaCv2OaZot/oyqqv5du3le/fjuL06/GCu8y4iYqC/4j3kLrciaT/+ovUuLrx2r/Ewf3J+5Dx6bXai6+Fqq+02baYqdzPrM6RiZ65+/P+/dW864mfzfPriJno5/CE/8rMoqLJjKW16LGPhN6X6oKk0OSKzLuf6LDt7eKLnNfo5o3h/5fBsKOC8bqczIqN24O3lt2ZiePdzYeDhb2BssrrxqXnt/n0zOzNkvTfw/r/67r6z5DBocDVyu+vw47v176UrrTtgJGugruK0N7Oncm1sP73wff11ZjXtrzzv6PKtIC+p86WmsXKhevt1uHbtez6/Jrv3PjE7NvAw7a4uun51rawy+KX7cq8lKrstYXcrNWu7Oy14vCY05/I3ouGkvPa3+27zKSm1+qEh7K0" reponse=b64.b64decode(reponse) key = l.genKeyXor(len(reponse)) print(pwn.xor(reponse, key)) # Fourth command l.state = 9882815798089 commande="i6CeuJiAuvurro7fifec5eCwvdT84oavnobZ4w==" commande=b64.b64decode(commande) for i in range(len(commande)): l.backGeneration() key = l.genKeyXor(len(commande)) print(pwn.xor(commande, key)) # Response command reponse="5ZH2hbi0ne3ckKWphaah3YW4hfihsN7zvOeTr7/riffOn7fhmd+NpdyvvuGUvY3Qg6PQoIb0hM+Aq6jGqPHRhdWrh9z5i6XIm8DIuvLF1rHBzpzb+t7/z4CD4MCClYHcx6ykrIqlmJKl082Il5iQ0P2D6eDTirXwsrCWq4r1/aqCubGSiOTNi67qluqPkf32yuLU3c++ocnApKCF/ZOJ/+TCy72utbXk98G3hp721c+U9uLq8f/L6/jRzaOIr8ax0dnK5dXy/azN1vaS/9jK9IXjmP/xkIHWmb+3oY+Znq3Z1avU/vTIpqHVl9z3merioeub4q7S5fm+geDWneTdmf2XgYbC+anK1e+HzrLQi9nHl/fAzMfSoYrOptGgnsiW64GAh4jCze2HjIqT5O6qgqP6qMbY57e0+8afifOJhYDTzq662MyWhev83cnx/7invdmVnf7x2MXWg++QwNPajN+ItJrk97+C2Niqs9TK5t7+5+iYycWa1rn12qW4iuTWzNr8vfatkpb7j5+N7ZPM5/r/r8rAwYjb1bWfjeuT9LGfk56IkLWpleHWxPKhvub94N7iy8XsseiM9Z6F4Ni+0sO6t/PEmczWyK3bttz146/u" reponse=b64.b64decode(reponse) key = l.genKeyXor(len(reponse)) print(pwn.xor(reponse, key)) # FLAG 2 # TAKE INITIAL STATE l.state = 15813009896856 cmd="i/zPktPX5qjw9ua0lZyJp58=" cmd=b64.b64decode(cmd) for i in range(len(cmd)): l.backGeneration() result="3ujUj7j4mrzir5/9qvOM9YLtva2rsIeo9InVifGnn5uWtbP9vYea6/bqi930rsSc0MClx+Wv3eTg7IGBuuKqy92M1L2N0OzY2uqnjdKg+A==" result=b64.b64decode(result) for i in range(len(result)): l.backGeneration() comamnde="t5U=" comamnde=b64.b64decode(comamnde) for i in range(len(comamnde)): l.backGeneration() # GRAINE print("##############") print(f"# Graine: {l.state} #") print("##############")⏎
a = 0x25189764115487 c = 0x15684162332011 m = 0x100000000000⏎