CryptoHack | Common Ground

Common Ground

Common Ground sur CryptoHack est un challenge à 75 points. La clé AES dépend du PGCD de deux nombres trop grands pour être calculés directement. On connaît leur base et leurs exposants. Il faut exploiter cette forme pour retrouver la clé.

Comprendre les données

Le fichier téléchargé contient trois entiers N, a et b. On trouve aussi un dictionnaire avec iv et ct au format hexadécimal.

L'énoncé donne la construction utilisée pour chiffrer le flag :

g = gcd(N ** a - 1, N ** b - 1)
key = sha256(long_to_bytes(g)).digest()[:16]

N est un premier de 1024 bits. Les exposants a et b sont des entiers aléatoires inférieurs à 2^2048.

Ces puissances demanderaient trop de mémoire pour être calculées directement. Le nombre de bits de N ** a est de l'ordre de a * log2(N). Avec un exposant de cette taille le problème dépasse largement la mémoire disponible.

Le point intéressant est que les deux nombres ont la même base et se terminent par −1.

Réduire le PGCD aux exposants

Pour une base entière N > 1 et des exposants positifs on a l'identité suivante :

On peut la retrouver avec l'algorithme d'Euclide. Si a >= b on soustrait un multiple du second nombre au premier :

Soustraire un multiple ne change pas le PGCD. On obtient donc :

Les exposants suivent les mêmes réductions que dans l'algorithme d'Euclide. En répétant ces étapes on arrive au PGCD des exposants. Le résultat est N^d - 1 avec d = gcd(a, b).

Pour info : cette identité ne demande pas que N soit premier. C'est la forme des deux puissances qui permet la réduction.

On peut vérifier l'idée sur un petit exemple :

from math import gcd

N = 3
a = 6
b = 4

print(gcd(N ** a - 1, N ** b - 1))
print(N ** gcd(a, b) - 1)

8
8

Pour les données du challenge il suffit donc de calculer le petit PGCD avant de construire la puissance :

d = gcd(data["a"], data["b"])
g = data["N"] ** d - 1

Il reste à calculer N^d - 1. Ce calcul est rapide si le PGCD des exposants est petit.

Reconstruire la clé AES

Une fois g retrouvé il faut reproduire exactement la dérivation de clé :

key = sha256(long_to_bytes(g)).digest()[:16]

long_to_bytes convertit l'entier en octets dans l'ordre big-endian. Les octets de poids fort viennent en premier. Il ne faut pas remplacer cette conversion par str(g).encode() car on hacherait alors les caractères de son écriture décimale.

SHA-256 produit 32 octets. Le [:16] conserve les 16 premiers pour obtenir une clé AES de 128 bits.

Il faut aussi utiliser digest() et non hexdigest(). Le premier renvoie les octets du condensat. Le second renvoie leur représentation hexadécimale sous forme de texte.

Déchiffrer en mode CBC

Le fichier donne un vecteur d'initialisation iv et le ciphertext ct. bytes.fromhex permet de retrouver les octets à partir de leurs chaînes hexadécimales :

iv = bytes.fromhex(data["iv"])
ct = bytes.fromhex(data["ct"])

cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ct)
flag = unpad(plaintext, AES.block_size)

AES travaille sur des blocs de 16 octets. En mode CBC chaque bloc déchiffré est combiné par XOR avec le bloc chiffré précédent. Pour le premier bloc c'est l'IV qui joue ce rôle.

Le message a été complété avant le chiffrement pour atteindre un multiple de 16 octets. unpad retire ce padding PKCS#7 après le déchiffrement. Il faut le faire sur les octets avant d'appeler decode().

Script complet

Le script solve.py prend le chemin du fichier téléchargé en argument :

from ast import literal_eval
from math import gcd
from hashlib import sha256
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

data = {}

input_file = Path(argv[1]) if len(argv) > 1 else Path(__file__).with_name("output.txt")
with input_file.open() as f:
    for line in f:
        line = line.strip()
        if not line:
            continue
        if " = " in line:
            name, value = line.split(" = ", 1)
            data[name] = int(value)
        else:
            data.update(literal_eval(line))

d = gcd(data["a"], data["b"])
g = data["N"] ** d - 1
key = sha256(long_to_bytes(g)).digest()[:16]

iv = bytes.fromhex(data["iv"])
ct = bytes.fromhex(data["ct"])
assert len(iv) == AES.block_size
assert len(ct) % AES.block_size == 0

cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ct)
flag = unpad(plaintext, AES.block_size)

print("gcd :", d)
print("Taille de la clé :", len(key), "octets")
print("Format du flag valide :", flag.startswith(b"crypto{") and flag.endswith(b"}"))
print(flag.decode())

La lecture sépare les lignes nom = entier du dictionnaire qui contient l'IV et le ciphertext.

Vérifier le déchiffrement

Je lance ensuite le script, sur les données fournies le script donne :

gcd : 2
Taille de la clé : 16 octets
Format du flag valide : True

Le PGCD des exposants vaut donc 2. Au lieu des deux puissances gigantesques on calcule simplement N² - 1. La valeur obtenue reste de l'ordre de 2048 bits.

Le déchiffrement donne un message au format attendu par CryptoHack.

Conclusion

Le PGCD des deux puissances se ramène au PGCD de leurs exposants. Ici ce dernier vaut 2 et le calcul devient simplement N² - 1. On peut alors reproduire la dérivation SHA-256 puis déchiffrer le message avec AES-CBC. La faiblesse vient de la valeur utilisée pour construire la clé.

Références

• Common Ground sur CryptoHack