BreizhCTF 2025 | Write-up de mes challenges

Introduction

Le BreizhCTF est un CTF français se déroulant en présentiel au couvent des jacobins à Rennes ; il n’y pas de qualification. Ce dernier réunissait cette année plus de 100 équipes de 5 personnes chacunes ! Les challenges sont réalisés une année sur deux par des élèves de l’ENSIBS (mon école !) et de l’ESNA (nos copains de Rennes 👀). Cette année, c’était au tour de mon école, et j’ai eu l’opportunité avec ThéoR de concevoir les challenges de cryptographie de l’événement.

Voici un tableau synthétique de nos challenges :

Challenge	Auteur	Difficulté	Nombre de résolution	Tags
Cube Median	TheoR	Facile	58	PRNG, QR code
AutHentification (ou pas…)	skilo	Facile	19	AES-GCM, Nonce reuse
Leaked	TheoR	Facile	6	Side Channel, Courbe elliptique
Demi-tour	skilo	Moyen	4	SIS
Locked	TheoR	Difficile	0	PRNG, Time-lock encryption
AutHentification, le retour !	skilo	Difficile	1	AES-GCM, Erreur d'implémentation
As-tu de bons yeux ?	skilo	Très Difficile	0	Module LWE, CRT

L’article de blog ci-après détaille les étapes de résolution de chacun de mes challenges. Voici un TL;DR de la résolution de chacun de ces challenges :

• AutHentification (ou pas…) : Pas de vérification du tag GCM et réutilisation du nonce permettent de forger un ticket administrateur valide ;
• Demi-tour : Ce challenge implémente une fonction de hachage construite sur le problème SIS (Short Integer Solution), i.e. étant donné $A$, trouver $s$ de normes infinie petite tel que $As = 0 \pmod q$). Le problème SIS étant mal dimensionné, il est possible de trouver une préimage en utilisant LLL ou BKZ ;
• AutHentification, le retour ! : Une erreur d’implémentation dans le mode GCM permet de forger des tags valides (une attack du style Forbidden Fruit) ;
• As-tu de bons yeux ? : Demande de casser une instance du Module-LWE dans sa version decisional avec le module $\mathcal{R}_q = \frac{\mathbb{Z}_q[X]}{(X^{256} - 1)}$ ; le polynôme du quotient possède une factorisation particulière permettant la résolution du Module-LWE dans plusieurs réseaux euclidiens de plus petites dimensions via le théorème des restes chinois.

Pour l’ensemble de ces challenges, les sources et scripts de résolution Python/SageMath sont disponibles à l’adresse suivante : github.com/BreizhCTF/breizhctf-2025/crypto. De plus, mes challenges sont disponibles pour rejeu sur la platforme CryptoHack : cryptohack.org/challenges/ctf-archive/.

Solutions des challenges

AutHentification 1

L’objectif de ce challenge est de forger un cookie admin afin d’accéder à l’espace administrateur. Pour cela, il faut réussir à chiffrer du JSON contenant la charge utile : "role": "super_admin".

Pour le chiffrement, c’est de l’AES-GCM 128 qui est utilisé. Dans notre cas, nous pouvons voir ce chiffrement comme de l’AES-CTR, en effet, l’authenticité n’est pas vérifiée ; on le remarque dans le code crypto.py en faisant du diffing avec le même challenge de difficulté supérieure.

Nous pouvons également remarquer que la clé AES est constante et l’IV est fixé à 0, le keystream sera donc toujours le même. En combinant cela au fait que nous pouvons nous créer un compte en choisissant le nom d’utilisateur (appelons-le compte 1, et notons C1 son cookie), nous sommes capables de forger un cookie admin (appelons le compte 2, et notons C2 son cookie).

En effet, le cookie user vaut : C1 = keystream XOR JSON_user, nous connaissons JSON_user, nous pouvons alors récupérer le keystream, car : keystream = C1 XOR JSON_user. Nous pouvons maintenant forger C2 en faisant : C2 = keystream XOR JSON_admin, avec JSON_admin un JSON de notre choix contenant le rôle super_admin.

Une implémentation complète de cette solution est disponible en Python dans le fichier solve.py.

Demi-tour

Quelques notations

• $[\beta]$ : l’ensemble $ { -\beta, -\beta+1, \ldots, 0, \ldots, \beta-1, \beta } $.
• $E^{k}$ : l’ensemble des vecteurs de taille $k$ à coefficients dans $E$.
• $E^{k \times l}$ : l’ensemble des matrices de taille $k \times l$ à coefficients dans $E$.
• $\mathbb{Z}_{n}$ : l’anneau des entiers modulo $n$, aussi noté $\mathbb{Z}/n\mathbb{Z}$.
• Si $\mathbf{x}$ est un vecteur de taille $n$, alors $x_1, x_2, \ldots, x_n$ sont ses coordonnées.

Paramétrage

Paramètre	Valeur
$k$	48
$l$	50
$\beta$	2
$n$	256

Objectif

L’objectif de ce challenge est de réussir à trouver une pré-image pour la fonction hash().

def hash(msg: str):
    msg = msg.encode()
    msg = sanitize(msg, l)

    x = vector(Zn, msg)
    A = Matrix(Zn, k, l, get_a())

    return bytes(A*x)

Analysons, petit pas par petit pas, cette fonction.

sanitize

def sanitize(a: bytes, l: int):
    a = pad(a, BLOCK_LEN)
    out = b"\x00"*BLOCK_LEN

    for i in range(0, len(a), BLOCK_LEN):
        out = xor(out, a[i:i+BLOCK_LEN])

    return btq(out)[:l]

Voici le fonctionnement de cette fonction :

1. Le message - après avoir été paddé avec PKCS #7 - est groupé en blocs de 16 octets.
2. Les blocs sont tous XORés entre eux dans out.
3. La variable out est convertie dans une base à 5 éléments puis tronquée au $l$-ème élément (i.e. elle est convertit en un vecteur de $[\beta]^{l}$) ; c’est cette version tronquée qui est retournée.

L’entrée de cette fonction est une chaîne d’octets de longueur 16 (cf. assert du fichier chal.sage), et la sortie, un vecteur de $[\beta]^l$.

>>> log(256**16, 2) # Taille en bits de l'ensemble de départ
128.0
>>> log(5**50, 2)   # Taille en bits de l'ensemble d'arrivé
116.09640474436812

Cette fonction induit une légère compression - 12 bits - donc rien de méchant, elle ne sera pas dure à reverser avec du bruteforce (en effet, nous avons une condition d’arrêt : le format du flag). Analysons maintenant la suite de la fonction hash().

A*x

Nous avons $\mathbf{A} \in \mathbb{Z}_{n}^{k \times l}$ : la matrice constante (cf. fichier A.txt), et $\mathbf{x} \in [\beta]^l$ : notre message après passage dans la fonction sanitize(). Le hash $\mathbf{h}$ est lui un élément de $\mathbb{Z}_{n}^k$, obtenu par le produit : $\mathbf{A} \mathbf{x} \pmod n$.

Le problème qui consiste à retrouver $\mathbf{x}$ dans $[\beta]^l$ (comprendre : trouver un $\mathbf{x}$ avec uniquement des petits coefficients ; dans $[\beta]$) à partir de $\mathbf{A}$ et $\mathbf{h}$, s’appelle le ISIS (pour Inhomogeneous Secret Integer Solution).

Dans notre cas, le paramètrage est faible, nous devons alors résoudre un ISIS de petite dimension, ce qui est très efficace avec l’algorithme LLL (ou sa variante BKZ).

Résolution

*Une implémentation complète de la solution est disponible dans le fichier* `solve.sage`

TL;DR

• Nous allons construire la matrice qui a pour noyau l’ensemble des $x \in \mathbb{Z}_{n}^k$ tel que $h = Ax \pmod n$.
• Ensuite, nous allons lancer LLL() sur la matrice engendrant ce noyau afin de chercher une petite solution (et oui, nous cherchons un $\mathbf{x}$ petit).
• Magie (ou pas …) : le petit $\mathbf{x}$ que nous cherchons sera dans la matrice réduite.
• On bruteforce pour reverse sanitize(). Fini.

---

Si je construis la matrice : \(L = \begin{pmatrix} \mathbf{A}~ \bigg| -\mathbf{h}~ \bigg| ~n\mathbf{I}_{k}~ \end{pmatrix}\)

On remarque, en developpant le produit matriciel, qu’avec $y = \begin{pmatrix} x_1 \ x_2 \ \vdots \ x_l \ 1 \ q_1 \ q_2 \ \vdots \ q_l \end{pmatrix}$, le produit $\mathbf{A} \mathbf{y} = 0$ (ssi les $q_i$ sont bien choisis pour retirer ou ajouter le bon nombre de fois le module $n$).

Le vecteur $\mathbf{y}$ se trouve donc dans le noyau de $\mathbf{L}$. Il suffit maintenant de calculer ce noyau. Étant donné que $\mathbf{y}$ a une petite norme, l’application de LLL() ou BKZ() sur la matrice engendrant ce noyau nous permettra de retrouver $\mathbf{y}$ et donc $\mathbf{x}$.

Voici l’implémentation de ce procédé en sagemath :

L = block_matrix([A, -h, n*identity_matrix(k)])
kerL = L.right_kernel().matrix()
llled = kerL.LLL()

for idx, vec in enumerate(llled.rows()):
    vec = vec[:l]

    if all([v in range(-beta, beta+1) for v in vec]):
        x = list(vec)
        break

Il suffit ensuite de bruteforce les caractères manquant du flag jusqu’à ce que ce dernier, en bytestring, match le format du flag.

AutHentification 2

Ce challenge est le même que sa première version, à un détail près : le tag est maintenant vérifié.

---

Rappelons le contexte :

1. Les cookies sont du JSON chiffré et authentifié contenant deux valeurs : “username” et “role”.
2. L’objectif est de forger un cookie admin, i.e., chiffrer et authentifier la charge utile : { "username": "toto", "role": "super_admin"}.
3. Le chiffrement intègre est assuré par une implémentation python d’AES-GCM 128 avec un IV constant et nul.
4. Par couple de (clé, IV), nous avons un oracle de chiffrement sur une unique charge utile JSON.

Avec ces éléments de contexte, nous déduisons rapidement que :

• Le chiffrement est très facile à contourner, cf. challenge AutHentification (ou pas...).
• Pour l’authentification : impossible d’utiliser la Forbidden Attack (cf. point numéro 4 ci-dessus).

L’énoncé et le header du fichier gcm.py disent clairement que l’implémentation a été faite par le stagiaire, cherchons une erreur d’implémentation. Le code étant assez long, nous allons utiliser une approche par diffing. Nous allons comparer les fonctions une par une avec les spécifications cités dans le commentaire en en-tête du fichier gcm.py : NIST Special Publication 800-38D.

---

Après avoir comparé — algorithme par algorithme — le code python aux spécifications, nous nous rendons compte que, dans l’algorithme 5, à la ligne 4, il manque une incrémentation :

# Algorithm 5: GCM-AD_K
def decrypt(self, C, T, A=b""):
    assert len(T) == BLOCK_LEN
    J = self.iv + b"\x00"*(CTR_LEN-1) + b"\x01"
    P = self.gctr(J, C) # Ici, sur le J.

    TT = self.build_tag(C, A, J)
    
    if TT != T:
        return (P, False)

    return (P, True)

Cela peut paraître anodin à première vue, mais, en regardant de plus près le schéma ci-dessous, nous nous rendons compte que les nonces des deux GCTR_K (celui servant à assurer la confidentialité et celui servant à assurer l’authentification) sont alors identiques.

Nous en déduisons : (l’ensemble des opérations suivantes a lieu dans $\mathbb{F}_2^{128}/f$, avec $f = 1 + \alpha + \alpha^2 + \alpha^7 + \alpha^{128}$)

\[T = K_s + \text{GHASH}(A \text{ || } C \text{ || } \text{len}A \text{ || } \text{len}C)\]

Avec $K_s$ le keystream (nous le connaissons, c’est le même que celui assurant la confidentialité), $A$ et $C$ les AAD et le chiffré (que nous considérerons chacun de la taille d’un bloc).

De plus, d’après la définition de GHASH :

\[T = K_s + AH^4 + CH^3 + \text{len}AH^2 + \text{len}CH^1\]

Nous connaissons $K_s$, il suffit de le soustraire puis de résoudre cette équation pour $H$. Une fois $H$ retrouvé il devient trivial de forger un tag valide. Une solution complète est implémentée dans le fichier solve.sage.

As-tu de bons yeux ?

Quelques notations

• $[\beta]$ : l’ensemble ${-\beta, -\beta+1, \ldots, 0, \ldots, \beta-1, \beta}$.
• $\mathbb{Z}_{n}$ : l’anneau des entiers modulo $n$, aussi noté $\mathbb{Z}/n\mathbb{Z}$.

---

Il est évidemment impossible — du moins à l’heure actuelle — de casser le problème (D-)MLWE lorsque celui-ci utilise le paramétrage de niveaux 5 de ML-DSA ; il est donc nécessaire de trouver une erreur d’implémentation.

Nous pouvons remarquer que, dans le fichier parameters.sage le polynôme par lequel est quotienté l’anneau $\mathbb{Z}_q[X]$ est $X^{256} - 1$ au lieu de $X^{256} + 1$. Ce dernier est factorisable dans $\mathbb{Z}$. En effet :

\[X^{256} - 1 = {\left(X^{128} + 1\right)} {\left(X^{64} + 1\right)} {\left(X^{32} + 1\right)} {\left(X^{16} + 1\right)} {\left(X^{8} + 1\right)} {\left(X^{4} + 1\right)} {\left(X^{2} + 1\right)} {\left(X + 1\right)} {\left(X - 1\right)}\]

Posons $f = X^{256} - 1$ et $g = X - 1$, nous avons un morphisme d’anneau allant de $\mathbb{Z}_q[X]/f$ vers $\mathbb{Z}_{q}[X]/g$ qui map les éléments $a = \sum_{i = 0}^{256} a_iX^i \in \mathbb{Z}_q[X]$ vers $a’ = \sum_{i = 0}^{256} a_i \in \mathbb{Z}_q[X]$ (Bref. C’est une évaluation en $X = 1$).

Il map donc les éléments vers $\mathbb{Z}_q$ (en effet, $\mathbb{Z}_q[X]/g$ est isomorphique à $\mathbb{Z}_q$), ce qui est cool avec ce morphisme c’est qu’il “préserve” à peu près la taille des coefficients, c’est-à-dire que, si un élément de $\mathbb{Z}_q[X]/f$ a des coefficients dans $[\beta]$, alors, en sortie du morphisme il deviendra un élément de $[256\beta]$. Comme $256 \ll q$, l’élément reste “petit”.

Si nous avons une instance du D-MLWE : $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$, où $\mathbf{t}$, $\mathbf{s}$ et $\mathbf{e}$ sont des vecteurs de $\mathbb{Z}_q[X]/f$ et où $\mathbf{A}$ est une matrice de ce même ensemble. Nous pouvons appliquer ce morphisme à chacun de ces éléments et nous retrouver ainsi avec un D-MLWE $t’ = A’s’ + e’$ de très petit paramétrage et dans $Z_q$ (se résout très efficacement avec LLL()/BKZ()).

En effet, si nous trouvons un $s’$ et un $e’$ avec des coefficients dans $[256\beta]$, alors, il s’agit d’une instance du MLWE ; sinon, non. Grâce à cette stratégie, nous pouvons résoudre le challenge ! Une implémentation complète de cette solution est disponible dans le fichier solve.sage.

Pour plus de ressources sur ce sujet, la section 4.5 du paper Basic Lattice Cryptography - The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA) de Vadim Lyubashevsky explique très bien cette attaque.