Writeup - La quête de l'anneau

  • Catégorie : Cryptanalyse
  • Fichiers fournis : la-quete-de-l-anneau.py, output.txt
  • Format du flag : FCSC{...}
  • Auteur du WriteUp : DonAsako

Contexte

Sauron a conçu un système de chiffrement basé sur des multiplications modulaires pour communiquer avec ses Nazgûls. Ce chiffrement repose sur une valeur secrète s, utilisée comme modulo. Heureusement, les Elfes ont intercepté deux messages aléatoires (avec le clair, les IV et les chiffrés), et un message chiffré contenant probablement le flag.

Notre objectif est de retrouver la valeur secrète s utilisée comme modulo, puis de déchiffrer le message intercepté.

🔍 Analyse Initiale

Dans la-quete-de-l-anneau.py, on observe que le chiffrement suit la formule suivante :

c = (m * iv) % s

Le fichier output.txt contient :

  • Deux couples (m, iv, c)
  • Un troisième message contenant seulement (iv, c), à déchiffrer

On peut réécrire la relation : $$ a = m \cdot iv \mod s \Rightarrow m \cdot iv - a \equiv 0 \mod s \Rightarrow s \mid (m \cdot iv - a) $$

Donc : $$ s = \gcd(m_1 \cdot iv_1 - c_1,\ m_2 \cdot iv_2 - c_2) $$ Cette propriété nous permet de retrouver le modulo s utilisé par le chiffrement.

Étapes

  1. Récupérer m1, iv1, c1, m2, iv2, c2 depuis output.txt
  2. Calculer x1 = m1 * iv1 - c1, x2 = m2 * iv2 - c2
  3. Obtenir s = gcd(x1, x2)
  4. Utiliser la classe Cipher et modifier son attribut s pour le déchiffrement
  5. Appliquer .decrypt() sur le message chiffré

Script de résolution

from la_quete_de_l_anneau import Cipher
from math import gcd
import json

# Données extraites de output.txt
a1 = 1460897189...
a2 = 7362760529...
b1 = 5300924613...
b2 = 5100397453...
iv1 = 9904787853...
iv2 = 7475569552...

x1 = b1 * iv1 - a1
x2 = b2 * iv2 - a2
s = gcd(x1, x2)
print("s =", s)

# Charger le message chiffré C
with open('output.txt', 'r') as f:
    data = json.load(f)

flag_data = data['C']

# Déchiffrer
cipher = Cipher()
cipher.s = s
flag = cipher.decrypt(flag_data)
print(flag)

Flag

FCSC{96fd29a6fc2301da363a4392cd4a9b9465d65b029a52913add2fd4001d}

Conclusion

Ce challenge est une belle illustration des attaques par analyse de structure modulaire. Lorsqu’un schéma de chiffrement repose sur des opérations arithmétiques simples comme la multiplication modulaire, il est crucial de ne jamais révéler des couples (m, iv, c) , cela peut directement compromettre le secret.

🔐 Ne jamais réutiliser des constructions aussi faibles pour un usage réel de chiffrement.