xmas.c, lauréat du concours international de code C obfusqué de 1988

 (udel.edu)
3 points par GN⁺ 2023-12-24 | 1 commentaires | Partager sur WhatsApp
  • xmas.c, lauréat de l’International Obfuscated C Code Contest 1988, affiche les paroles de The Twelve Days of Christmas avec un code C qui ressemble à une frappe aléatoire
  • Il intègre des chaînes chiffrées dans un code plus court que la sortie produite, puis déchiffre mots et expressions à l’aide d’un chiffrement par substitution et d’appels récursifs
  • En développant l’opérateur ternaire en blocs if-then-else et en donnant des noms à words et shift, on voit apparaître une structure où la valeur de t modifie le flux récursif
  • shift associe les caractères du début à ceux situés 31 positions plus loin, et words contient des fragments de paroles chiffrés séparés par des slashs (/)
  • C’est un simple programme d’affichage de paroles, mais le chiffrement par substitution, la récursivité bidirectionnelle, le code superflu et des arguments inutilisés en font un exemple créatif d’obfuscation en C

Ce que produit xmas.c

  • xmas.c est un programme C lauréat de l’International Obfuscated C Code Contest 1988
  • L’analyste a découvert ce programme pour la première fois vers 2000, puis en a démonté le code en novembre 2008 pour en comprendre le fonctionnement
  • Compilé et exécuté sans paramètre, il affiche les paroles du chant de Noël The Twelve Days of Christmas, du premier au douzième jour
  • Les commentaires du code d’origine précisent que le programme est plus petit que la forme « compressée » de sa sortie, et que les juges ont estimé qu’il ressemblait au « résultat d’une vieille machine à écrire frappée au hasard »

Structure interne rendue lisible

  • La première étape de l’analyse consiste à remplacer toutes les formes a ? b : c par des blocs explicites if-then-else
  • Deux chaînes difficiles à interpréter reçoivent des noms correspondant à leur rôle
    • words : un ensemble de mots et d’expressions chiffrés servant à reconstruire les paroles du chant de Noël
    • shift : une chaîne de substitution qui convertit les caractères chiffrés en caractères réellement affichés
  • main() commence par xmas(1, 0, '\0'), puis la fonction unique xmas() prend en charge récursivement toute la sortie
  • La variable t est la valeur clé qui contrôle le sens de la récursion et le comportement des branchements

Chiffrement par substitution et données des paroles

  • La chaîne shift fonctionne en pratique comme la concaténation de deux chaînes
  • Un caractère trouvé dans la première moitié est déchiffré en prenant le caractère situé 31 positions plus loin
    • Par exemple, le premier caractère de la chaîne, !, correspond au caractère de nouvelle ligne situé 31 positions plus loin
  • La branche t < -50 avance dans la chaîne a caractère par caractère jusqu’à ce que le caractère d’entrée _ apparaisse dans shift
    • Lorsqu’un caractère correspondant est trouvé, a[31] est affiché puis la fonction retourne
  • La chaîne words contient des données de paroles chiffrées déchiffrées via ce chiffrement par substitution
    • Les formes ordinales et les fragments de chaque couplet sont séparés par le caractère slash (/)

Le rôle des branches récursives

  • La branche t < -72 rappelle la fonction en inversant les deux premiers arguments et en passant words comme troisième argument
    • Son but principal est de semer la confusion et de permettre une récursion imbriquée qui ignore le troisième argument
  • La branche t < 0 recherche le |t|-ième slash (/) dans la chaîne, puis transmet la sous-chaîne qui commence juste après
  • La branche t == 0 déchiffre et affiche la chaîne jusqu’au slash suivant, puis renvoie 1
  • La branche t == 1 n’est appelée qu’une seule fois au démarrage et lance la vraie récursion avec xmas(2, 2, "%s")
  • La branche t == 2 affiche la première ligne au format "On the [ordinal] day of Christmas my true love gave to me\n"
  • Les deux derniers blocs conditionnels maintiennent la récursion dans les deux directions
    • Ils descendent du jour courant pour afficher en ordre inverse les paroles du couplet correspondant
    • Ils remontent ensuite jusqu’au douzième jour pour répéter l’ensemble des couplets

Flux d’exécution une fois simplifié

  • Une fois le fonctionnement compris, le code peut être réécrit de façon bien plus simple avec des boucles et les routines de la bibliothèque de chaînes C
  • Même dans cette version simplifiée, les données essentielles words et shift restent inchangées
  • La branche t < 0 utilise index(a, '/') pour trouver le délimiteur slash et se déplacer jusqu’au fragment de paroles voulu
  • La branche t == 0 déchiffre et affiche les caractères via index(shift, *a++)[31]
  • La branche t == 2 affiche le début d’un couplet dans l’ordre suivant
    • "On the "
    • la forme ordinale correspondant au jour
    • " my true love gave to me\n"

Pourquoi cette obfuscation est intéressante

  • Une fois totalement simplifié, ce programme se résume à un code qui affiche des paroles
  • L’original combine chiffrement par substitution et récursion pour produire une structure bien plus complexe qu’un simple affichage
  • De petits morceaux de code superflu et des arguments arbitraires jamais réellement utilisés compliquent encore la compréhension
  • Comprendre un tel programme et en écrire un sont deux choses différentes, et xmas.c reste considéré comme un exemple créatif de code C

À lire aussi

1 commentaires

 
GN⁺ 2023-12-24
Avis sur Hacker News

  • Il existe un exemple similaire côté TeX avec xii.tex.
    Mettez ce contenu dans un fichier .tex, exécutez pdftex, puis regardez le PDF obtenu : https://shreevatsa.net/post/xii/

    • Cela ressemble moins à de l’obfuscation qu’à une forme particulière de compression logique.

  • Je l’avais récupéré lors de sa publication initiale, mais contrairement au nom de fichier dans cet article, mon fichier s’appelait carol.c.
    En le compilant et en l’exécutant sur des systèmes modernes, gcc -o carol carol.c produit des avertissements comme return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, type of ‘_’ defaults to ‘int’.

    • À partir de GCC 14, le int implicite ne sera plus autorisé : https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • Le problème vient du fait que xmas() est appelé dans main avant d’être défini.
      Avec GCC sur macOS, la compilation échoue avec l’erreur ISO C99 and later do not support implicit function declarations, et si l’on déplace main() plus bas, le programme se compile correctement et produit la bonne sortie.
    • Il est surprenant qu’il y ait aussi peu d’avertissements, et qu’ils viennent tous de la même ligne.

  • Ça me fait penser à la complexité de Kolmogorov.
    Ici, le programme a l’air de n’avoir ni queue ni tête, mais comme il produit la sortie voulue, je me demande s’il existe aussi un programme plus court et encore plus absurde en apparence qui produise la même sortie.
    Comment pourrait-on trouver un tel programme ?

    • Le record actuel du programme C le plus court qui affiche les paroles de 12 Days of Christmas est de 431 octets : https://code.golf/12-days-of-christmas#c
    • Il est très probable qu’il existe un programme plus court.
      Mais la recherche par force brute est extrêmement inefficace ; en pratique, la réponse réaliste revient plutôt à « être malin » au sens mathématique.
      En général, la complexité de Kolmogorov n’est pas calculable, donc il n’existe pas de programme qui, recevant une chaîne donnée, renvoie le plus court programme qui calcule cette chaîne.
      En revanche, il est en principe possible que quelqu’un prouve que la complexité de Kolmogorov d’une chaîne donnée vaut X.
    • Dans la plupart des cas, calculer directement la complexité de Kolmogorov est pratiquement impossible, et je pense qu’on ne peut comparer qu’en termes de possibilités, par exemple « plus lent que telle version ou telle valeur ».
      C’est pour cela que le sujet se prête bien aux concours et compétitions au long cours ; avec des courbes de progression de type logarithmique, des découvertes intéressantes peuvent parfois surgir tout à la fin.
      En ce moment, j’organise un mini-concours jusqu’en mars prochain pour départager les LLM capables de mémoriser le plus de chiffres de pi ; le prix actuel est de 100 dollars et sera réparti proportionnellement aux contributions dans l’espace logarithmique.
      Comme pi est théoriquement assez compressible, il serait intéressant de voir si un modèle peut apprendre un ensemble de poids proche de la longueur de description minimale (MDL) qui reconstitue, à partir des données, un algorithme à forte compression.
      Cela dit, il n’est pas encore clair que ce soit faisable avec des modèles existants ; pour l’instant, je préfère donc en rester à un concours de mémorisation de chiffres et observer ce qui se passe.

  • L’explication est bonne, et l’IOCCC semble toujours bien vivant en 2023 : https://www.ioccc.org/years.html

    • Sur cette page, le dernier IOCCC indiqué date de 2020.
      Mais la page d’accueil mentionne, dans une mise à jour de mai 2023, qu’ils « prévoient d’organiser le 28e IOCCC ».
      Il y a des choses qui valent la peine d’être attendues, comme les sorties de Nethack.

  • J’ai récemment appris quelque chose d’amusant sur The Twelve Days of Christmas : tous les cadeaux seraient des sortes d’oiseaux.
    Même les dames qui dansent et les seigneurs, apparemment.

  • Il y a aussi ce que j’avais moi-même étudié il y a plus de 20 ans : http://michaeldnahas.com/xmassong/index.html

  • Si l’on désactive les avertissements, ça fonctionne encore même sur trunk : https://compiler-explorer.com/z/hGvs1e9jo

  • Ça me rappelle un bon souvenir : en 2022, pendant mes deux derniers semestres à l’université, un professeur nous avait montré ce bout de code dès le début du cours.

    • La formulation peut aussi se lire comme une blague du genre « mes deux derniers semestres à l’université, donc il y a carrément un an ! », comme si le souvenir était flou parce que cela remontait à très loin.
      Difficile de dire si c’est sincère ou de l’humour pince-sans-rire.

  • À l’université, un professeur l’avait inclus dans un polycopié imprimé sur le langage C, et je me souviens l’avoir retapé entièrement à la main une fois.

  • Rosetta Code propose aussi un exercice similaire.
    Il s’agit d’un programme qui affiche Old Lady Swallowed a Fly, une chanson dont les couplets s’allongent de manière répétitive : https://rosettacode.org/wiki/Old_lady_swallowed_a_fly

    • J’aime bien la version Tcl, qui consiste simplement à compresser les paroles.
      puts [zlib inflate [binary decode base64 "7VRNa8MwDL3nV2(...)"]]
      https://rosettacode.org/wiki/Old_lady_swallowed_a_fly#Tcl
      Il est très probable qu’il existe des versions similaires en Python, Nim, Julia, etc.