CryptoHack | No Way Back Home

No Way Back Home

Pour ce challenge à 100 points Alice et Bob utilisent leur propre protocole d'échange de clés. Les valeurs échangées sont publiques mais le secret est choisi pour ne pas être inversible modulo n. Il faut retrouver ce secret pour déchiffrer le flag.

Le challenge fournit deux fichiers. nowayback.py contient le protocole et out.txt contient les valeurs publiques ainsi que le message chiffré.

Comprendre l'échange

Le programme génère deux nombres premiers p et q de 512 bits puis construit :

Alice choisit un secret v et une clé k_A. Bob choisit une clé k_B. Les deux clés sont premières avec n et possèdent donc un inverse modulo n.

Les valeurs échangées sont :

Alice envoie d'abord vka. Bob multiplie cette valeur par sa clé pour produire vkakb. Alice retire ensuite sa propre clé en multipliant par son inverse. Elle obtient vkb que Bob peut à son tour multiplier par l'inverse de k_B pour retrouver v.

Le message est chiffré avec une clé AES dérivée du secret partagé. Si on retrouve v on peut reproduire cette clé.

Repérer le choix du secret

Le secret est généré avec cette ligne :

v = (p * randint(1, n)) % n

v reste un multiple de p même après la réduction modulo n puisque n est lui-même divisible par p. On sait donc que :

Cela empêche d'inverser v modulo n. Les trois valeurs échangées sont aussi des multiples de p. En particulier vkakb n'a pas d'inverse modulo n.

On pourrait vouloir calculer directement :

Mais cette opération bloque sur l'inverse de vkakb. Il faut changer de modulo.

Travailler modulo q

Le fichier de sortie donne les valeurs vka, vkakb, vkb et le ciphertext c. Il donne aussi les deux nombres premiers p et q.

Puisque q est connu on peut regarder les échanges modulo ce nombre premier. Les clés k_A et k_B y restent inversibles. Sur les données du challenge v est également non nul modulo q, ce qui rend vkakb inversible dans ce calcul.

Le produit des deux échanges simples donne :

En multipliant par l'inverse de l'échange qui contient les deux clés on obtient :

On retrouve ainsi v_q, le reste du secret modulo q :

vq = (vka * vkb * pow(vkakb, -1, q)) % q

pow(x, -1, q) calcule l'inverse de x modulo q. Il ne s'agit pas d'une division ordinaire.

Pour info : ne pas être inversible modulo p × q ne signifie pas être non inversible modulo chacun de ses facteurs. Ici le multiple de p bloque l'inverse modulo n mais pas modulo q.

Reconstruire le secret

On connaît maintenant deux congruences :

Comme p et q sont deux premiers distincts le théorème des restes chinois donne une solution unique modulo n.

La première congruence permet d'écrire v = p × t. En remplaçant dans la seconde :

p possède un inverse modulo q. On peut donc isoler t :

Il reste à choisir le représentant entre 0 et q - 1 puis à le multiplier par p :

t = (vq * pow(p, -1, q)) % q
v = p * t

La valeur obtenue est comprise entre 0 et n - 1. C'est exactement l'intervalle utilisé par le programme pour son secret.

Retrouver la clé AES

Le protocole dérive sa clé avec :

key = sha256(long_to_bytes(v)).digest()

long_to_bytes convertit le secret en octets dans l'ordre big-endian. SHA-256 produit ensuite les 32 octets utilisés pour la clé AES-256.

Le mode utilisé est ECB. Il n'y a donc pas d'IV à récupérer. Après le déchiffrement unpad retire le padding PKCS#7 ajouté pour compléter les blocs de 16 octets.

Script de résolution

Le script solve.py prend le chemin du fichier de sortie en argument. Sans argument il cherche out.txt dans son dossier. Il utilise PyCryptodome pour AES.

from ast import literal_eval
from hashlib import sha256
from math import gcd
from pathlib import Path
from sys import argv
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad

input_file = Path(argv[1]) if len(argv) > 1 else Path(__file__).with_name("out.txt")
values = {}

for line in input_file.read_text().splitlines():
    if not line.strip():
        continue
    name, value = line.split("=", 1)
    name = name.strip()
    parsed = literal_eval(value.strip())
    if name.replace(" ", "") == "p,q":
        values["p"], values["q"] = parsed
    else:
        values[name] = parsed

p = values["p"]
q = values["q"]
n = p * q
vka = values["vka"]
vkakb = values["vkakb"]
vkb = values["vkb"]

assert gcd(vkakb, q) == 1
vq = (vka * vkb * pow(vkakb, -1, q)) % q
v = p * (vq * pow(p, -1, q) % q)

assert 0 <= v < n
assert v % p == 0
assert v % q == vq

key = sha256(long_to_bytes(v)).digest()
cipher = AES.new(key, AES.MODE_ECB)
plaintext = cipher.decrypt(bytes.fromhex(values["c"]))
flag = unpad(plaintext, AES.block_size)

print(flag.decode())

La première ligne de données contient un couple p, q. Les autres contiennent des entiers ou une chaîne hexadécimale. literal_eval permet de lire ces valeurs sans exécuter le fichier avec exec.

Avant le déchiffrement les assertions vérifient l'existence de l'inverse modulo q puis les deux congruences du secret reconstruit.

Vérifier le déchiffrement

Le secret reconstruit permet de retrouver la clé et de déchiffrer le message. Le flag est masqué sur la capture.

Conclusion

Le secret n'est pas inversible modulo n mais on peut retrouver son reste modulo q. Comme il est aussi multiple de p les restes chinois permettent de reconstruire sa valeur complète. Les trois échanges publics suffisent alors à calculer la clé AES. Le choix d'un secret non inversible ne protège donc pas ce protocole lorsque les facteurs sont connus.

Références

• No Way Back Home sur CryptoHack