Un casier qui veut tomber sur 300
Inverser un calcul de vérification consiste à partir du résultat attendu et à défaire les étapes une à une pour retrouver la valeur d’entrée. Beaucoup de petits programmes vérifient un nombre ainsi, avec quelques additions, soustractions et xor.
Un casier de bibliothèque s’ouvre quand un nombre, après trois étapes de calcul, tombe sur 300. Lire les étapes suffit à retrouver le nombre. Rappel : seuls les programmes de votre labo se lisent ici.
À la fin de cette leçon
Remarque
Je peux défaire un petit calcul fait d’un xor, d’une soustraction et d’une addition pour retrouver la valeur d’entrée.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Opération inverse | l’opération qui défait une autre | sub défait add |
| xor | un « ou exclusif » bit à bit, qui est sa propre opération inverse | 5 xor 3 vaut 6 |
| Hexadécimal | une écriture des nombres en base 16, marquée 0x | 0x2a vaut 42 |
| Entier non signé | un nombre sans signe, ici sur 32 bits, de 0 à 4294967295 | |
| Constante | un nombre écrit dans le programme |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Des étapes de calcul, puis une comparaison
Le programme verif prend un nombre. Il lui applique trois étapes, l’une après l’autre, puis compare le résultat à une constante. Si c’est égal, il répond « Acces accorde. ».
Les deux premiers Runs écrivent verif.c et le compilent. Chaque étape a sa ligne dans le C. Sur une seule ligne, gcc les replierait en une comparaison, même sans optimisation.
Écrire le programme verif.c
printf '%s\n' '#include <stdio.h>' '#include <stdlib.h>' 'static int accepte(unsigned n) {' ' unsigned x = n;' ' x = x ^ 42;' ' x = x - 15;' ' x = x + 100;' ' return x == 300;' '}' 'int main(int argc, char **argv) {' ' if (argc != 2) { puts("usage: verif NOMBRE"); return 2; }' ' if (accepte((unsigned)strtoul(argv[1], 0, 10))) { puts("Acces accorde."); return 0; }' ' puts("Acces refuse.");' ' return 1;' '}' > verif.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le compiler avec les réglages du labo
gcc -O0 -no-pie -fno-stack-protector -o verif verif.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les étapes se lisent dans la fonction accepte
Le Run désassemble la fonction accepte et garde les lignes xor, sub, add et cmp. Dans l’ordre du fichier, ce sont les étapes du programme, puis la comparaison.
Chaque ligne agit sur la même case de mémoire, [rbp-0x4]. Les nombres sont en hexadécimal : 0x2a, 0xf, 0x64 et 0x12c.
Garder les étapes et la comparaison
objdump -d -M intel verif --disassemble=accepte | grep -E 'xor|sub|add|cmp'Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Convertir la constante de la comparaison
printf '%d\n' 0x12cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Exemple travaillé : de 300 à l’entrée
| Étape du programme | Étape à défaire | Valeur après |
|---|---|---|
| (comparaison avec 300) | On part de la cible | 300 |
| add 100 (la dernière) | Retirer 100 | 200 |
| sub 15 | Ajouter 15 | 215 |
| xor 42 (la première) | Refaire xor 42 | 253 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
On défait les étapes dans l’ordre inverse
Pour défaire un calcul, on part de la fin. Une addition se défait par une soustraction, une soustraction par une addition, et un xor par le même xor.
L’ordre compte : la dernière étape du programme se défait en premier. Les Runs suivants refont le calcul avec le shell, puis le vérifient avec le programme.
Faire le calcul inverse avec le shell
echo $(( (300 - 100 + 15) ^ 42 ))Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Essayer le nombre trouvé
./verif 253Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Essayer le nombre voisin
./verif 252Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup de gens défont les étapes dans le même ordre que le programme. C’est faux : il faut défaire la dernière en premier. Avec une addition suivie d’un xor, défaire l’addition d’abord donne un autre nombre. Écrivez la liste, puis lisez-la de bas en haut.
Sous zéro, un entier repart du haut
Un entier non signé sur 32 bits va de 0 à 4294967295. Si une soustraction passe sous zéro, le résultat repart du haut : 0 moins 10 donne 4294967286.
Le Run le montre avec le shell : le & 0xFFFFFFFF garde les 32 bits du bas. Quand une étape a pu passer sous zéro ou au-dessus du maximum, calculez donc modulo 4294967296.
Voir un nombre repartir du haut
echo $(( (0 - 10) & 0xFFFFFFFF ))Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pour aller plus loin
Dans verif.c, remplacez les trois étapes par x = x + 7;, puis x = x ^ 21;, puis x = x - 3;, et 300 par 120. Recompilez, lisez les quatre lignes avec objdump, puis retrouvez le nombre à la main.
Vérifiez enfin avec ./verif : le nombre est accepté, et son voisin est refusé.