Énoncé
Nous avons réussi à écouter notre cible lorsqu’elle s’est connectée à son serveur distant. Parviendrez-vous à retrouver son mot de passe ?
Le code source décrit une version modifiée de L’échange de clés Diffie-Hellman Un mot de passe est nécessaire pour effectuer l’échange. Nous disposons d’une retranscription d’un échange effectué entre un client et le serveur, tous deux disposant du mot de passe. L’objectif du challenge et de retrouver ce mot de passe.
Chiffrement de la communication
Les échanges entre le client et le serveur sont chiffrés grâce à une simple multiplication modulaire.
class Server:
def __init__(self, password):
# ...
self.p = 9912608149[...]7338297607 # nombre premier de 3067 bits
self.gen_p = 5
self.key = int(sha256(password.encode()).digest().hex(), 16)
def _encrypt(self, m):
return m * pow(self.gen_p, self.key, self.p) % self.p
def _decrypt(self, c):
return c * pow(self.gen_p, -self.key, self.p) % self.p
Le client et le serveur disposent d’une clé secrète dérivée du mot de passe recherché, $K \equiv \mathtt{gen_p}^k \mod p$, où $k$ désigne l’empreinte SHA256 du mot de passe.
Lorsque le client et le serveur échangent leur clé publique, ils envoient sur le canal de communication $c \equiv \text{Enc}(K, m) \equiv m \cdot K \mod p$, que le destinataire peut simplement déchiffrer par $m \equiv \text{Dec}(K, c) \equiv c \cdot K^{-1} \mod p$.
Échange de clés Diffie-Hellman
class Server:
def __init__(self, password):
# ...
self.q = 2194170942[...]1499677887 # nombre premier sur 257 bits
self.gen_q = 7215471464[...]0825328784 # nombre composé, sur 3066 bit
Les autres fonctions de la classe Server permettent d’effectuer un échange de clés Diffie-Hellman sur $F_p$.
La fonction init_DH génère une paire de clés $(x, X)$, où $x$ est une clé privée choisie au hasard entre 2 et $q$, et $X \equiv G^x \mod p$ est la clé publique qui servira pour l’échange de clés.
La fonction enregistre la clé privée de manière interne, et renvoie la clé publique chiffrée grâce au mot de passe.
class Server:
def init_DH(self):
self.x = randrange(2, self.q)
X = pow(self.gen_q, self.x, self.p)
Xenc = self._encrypt(X)
return Xenc
La fonction complete_DH permet de finaliser l’échange de clés.
En supposant que le client ait lui aussi généré une paire de clés $(y, Y)$
et nous ait transmis la version chiffrée de sa clé publique, $\text{Enc}(Y)$,
alors la fonction complete_DH déchiffre la clé publique du client,
et calcule le secret commun $S \equiv Y^x \equiv G^{xy} \equiv X^y \mod p$.
La fonction retourne enfin une empreinte du secret commun, afin de s’assurer que l’échange s’est déroulé correctement.
class Server:
def complete_DH(self, Y_enc):
Y = self._decrypt(Y_enc)
self.K = pow(Y, self.x, self.p)
self.H = sha256(hex(self.K).encode() + b"Server").digest().hex()
return self.H
De manière symétrique, le serveur peut vérifier l’empreinte donnée par le client afin d’assurer l’intégrité de leurs futures communications.
class Server:
def check_DH(self, your_H):
return your_H == sha256(hex(self.K).encode() + b"Client").digest().hex()
Vulnérabilité
La première vulnérabilité évidente concerne les contraintes connues sur le mot de passe. Le mot de passe est uniquement composé de quatre lettres minuscules, ce qui ne laisse que $26^4 = 456,976$ possibilités.
assert len(PASSWORD) == 4
assert all(x in string.ascii_lowercase for x in PASSWORD)
Dans notre modèle d’attaque, nous sommes observateur d’un échange qui a eu lieu avec succès entre un client et le serveur. Nous avons accès à la version chiffrée des clés publiques du serveur et du client, ainsi qu’à deux empreintes de leur secret commun.
S = Server(PASSWORD)
Xenc = S.init_DH() # On connaît la version chiffrée de X
Y_enc = int(input()) # On connaît la version chiffrée de Y
H = S.complete_DH(Y_enc)
your_H = input()
assert S.check_DH(your_H) # True
Si nous pouvons énumérer toutes les possibilités de mot de passe, là où réside le challenge est de savoir comment vérifier si un mot de passe est correct.
En analysant de plus près les paramètres, on remarque que les clés privées sont des entiers entre 1 et $q$. De plus, le nom du générateur $G$ dans le programme est $\mathtt{gen_q}$. Cela laisse sous-entendre que dans le groupe multiplicatif $(\mathbb Z/p\mathbb Z)^{\times}$ des entiers modulo $p$, $G$ serait d’ordre $q$.
Cela se vérifie simplement avec un script Python :
» p = 9912608149[...]7338297607
» q = 2194170942[...]1499677887
» gen_a = 7215471464[...]0825328784
» pow(gen_q, q, p)
1
Comme $G^q \equiv 1 \mod p$, cela implique que l’ordre de $G$ divise $q$. $q$ étant un nombre premier, l’ordre de $G$ ne peut être que $1$ ou $q$, et comme $G \not\equiv 1 \mod p$, l’ordre de $G$ doit nécessairement être $q$.
La clé publique $X$ étant dérivée de la clé privée $x$ par $X \equiv G^x \mod p$, $X$ doit nécessairement appartenir au sous-groupe $\langle G \rangle$ engendré par $G$. Ce sous-groupe ne possédant que $q$ éléments, il ne représente qu’une infime proportion de $(\mathbb Z/p\mathbb Z)^{\times}$. En clair, en choisissant un entier au hasard entre 1 et $p-1$, la probabilité qu’il appartienne à $\langle G \rangle$ est inférieure à une chance sur $10^{846}$. On peut alors déterminer de manière assez fiable si un mot de passe est le bon : si un mot de passe est correct, alors depuis la clé $K$ dérivée, $\text{Dec}(K, X’)$ doit renvoyer un élément de $\langle G \rangle$, où $X’$ représente la clé publique chiffrée du serveur, que nous possédons.
Afin de savoir si un élément appartient à $\langle G \rangle$, on doit simplement s’assurer que son ordre divise celui de $G$ :
» from random import randint
» x = randint(2, q)
» vraie_cle = pow(gen_q, x, p)
» fausse_cle = randint(1, p)
» pow(vraie_cle, q, p)
1 # appartient à ⟨G⟩
» pow(fausse_cle, q, p)
335817358[...]978259582 # n'appartient pas à ⟨G⟩
Mise en œuvre
for combinaison in product(string.ascii_lowercase, repeat = 4):
password = ''.join(list(combinaison))
k = int(sha256(password.encode()).digest().hex(), 16)
K = pow(gen_p, k, p)
Y = (Yenc * pow(K, -1, p)) % p
X = (Xenc * pow(K, -1, p)) % p
if pow(X, q, p) == 1 and pow(Y, q, p) == 1:
break
print(password)
# ltjd