Du tatouage (Machine Learning) - 404CTF2025

Principe:
Brute-forcer les clefs de tatouage possible pour chaque entrée d'un journal, pour trouver quelle clef a permi de tatouer certaines entrées

Infos (cf menu latéral):
🚩 Flaggué! +496 points gagnés — 💾 Téléchargez les fichiers du challenge
404CTF{436333370349117}

Le challenge

L'énoncé du challenge

Watermarking

Ne connaissant pas les méthodes de watermarking des LLM, je vais voir le arxiv proposé
Le visuel est clair, et la méthode probabiliste (détaillée plus bas) est assez simple
Le principe consiste à laisser le LLM prédire les N prochains tokens, et à n'en garder qu'une partie (dire G, green) "au hasard" en prenant le token précédent comme seed

Prendre le token précédent comme seed permet de rendre répétable l'opération. C'est indispensable pour vérifier le watermark car à chaque token N, la vérification va consister à confirmer que le token N+1 est bien dans G, les tokens conservés. Il faut donc que l'ensemble G ne soit pas aléatoire. En revanche, le choix du token dans G peut l'être.

Les données du challenge

Le challenge nous donne une liste de textes générés via un modèle (qu'il nous donne aussi)
On sait que les tokens seront tatoués à partir du 20e, donc, le tatouage ne devra pas être testé avec les tous premiers tokens (mots)
Bon, en revanche, qui utilise des accents dans ses noms de variables?! 🤣
Cela a tendance à péter un peu la coloration de mousepad, mais tant pis

Tester pour comprendre

D'abord, le mieux est de tester un peu les codes pour comprendre le fonctionnement des tatouages, en générant un texte non tatoué et un texte tatoué
Cette fois, c'est sans Jupyter, mais wow, on a toujours une grande quantité de données téléchargées!

Ici, le challenge ne nous a pas fourni de poids car on utilise un modèle standardisé, qui sera téléchargé depuis internet

Avec quelques print, on comprend le principe du tatouage Red/Green

Le principe est de générer N tokens (les Choix initiaux dont le \n fait partie) puis de discriminer la liste (True/False pour Green/Red) pour n'en garder qu'une partie (True). Cela nous donne les Nouveaux choix, parmi lesquels le modèle va choisir un token en fonction de sa probabilité (le Jeton choisi). Et de même avec chaque nouveau token prédit.

Un petit test nous permet de voir qu'avec le même prompt, deux générations différentes s'opèrent, puisque l'ensemble G des tokens admissibles n'est pas aléatoire, mais le choix du token dans G l'est.
Le concept est donc de prendre les N tokens précédents, de prédire le N+1, de générer le groupe Green et de voir si token N+1 est dans G

Pour une suite de tokens t(0),t(1),…,t(N) si le t(N+1) de la sortie, donnée dans le journal.json, ne fait pas partie du groupe Green qu'on aura généré, alors on saura que le token N+1 n'a pas pu venir d'une génération tatouée

Ici, j'ai démarré mon test au 12e token car il s'agit de la longueur de mon prompt de départ. Mais dans le challenge, on ne connait pas le prompt initial ni sa longueur!

En appliquant ce principe sur mon prompt de test et en itérant sur chaque key possible (dans un petit intervalle pour aller vite), je confirme que la seule clef de tatouage plausible est celle que j'avais utilisée: le concept marche!
Sans GPU, ce n'est pas rapide… espérons que je puisse quand même faire mon brute-force!
Mais, en cherchant dans l'intervalle plus large de 1…999999 donné par le challenge, je m'aperçois que j'ai plusieurs clefs possibles!

Les plus observateurs (que moi) auront remarqué que j'ai pris 1…999999 au lieu de 1…99999 !

Forcément, ça sera 10x plus long comme brute-force!
En corrigeant cette coquille…
… j'ai moins de clefs possibles, mais j'en ai toujours beaucoup
Au passage, j'ai eu des bizareries dans mes sorties, mais en printant les choses à fond, j'ai constaté qu'il s'agit d'un caractère spécial dans certaines sorties (token 564)
J'ai donc finalement travaillé avec les ID des tokens, plus sûrs, et une génération plus longue: je n'ai obtenu plus qu'une seule clef possible sur mes tests!

Un challenge plus complexe aurait pu consister à trouver K clefs pour chaque entrée tatouée du journal, et à ne garder que la clef communes à tous les journaux tatoués. Mais cela aurait obligé à trouver comment les identifier, ce qui aurait pu être difficile.
Toutefois, des méthodes statistiques devraient permettre de le faire, en considérant par exemple la clef qui ne revient pas forcément à chaque entrée de journal (ne sachant si l'entrée est tatouée ou pas) mais qui revient le plus souvent dans tous les journaux.

On lance donc, en parallèle pour gagner du temps car 100% du CPU n'est pas utilisé, le brute-force de chaque journal
Et après avoir récupéré et rassemblé la clef de tatouage de chacun, on a le flag!

On notera qu'il y a, pour chaque journal, deux clefs possibles. C'est normal, il y a un modulo dans l'algorithme aléatoire. J'ai donc pris, au pif, la valeur la plus petite. Théoriquement, les deux devraient valider le challenge, mais je ne peux pas le confirmer.

On le valide, et le challenge est terminé

Flag: 404CTF{436333370349117}