Les integer overflows

Les integer overflows

Lorsque vous souhaitez stocker un nombre dans un langage tel que le C, vous devez généralement préciser son type (short, int, long, signé ou non etc). Ce type détermine l'espace de stockage alloué pour ce nombre et par la même occasion, le nombre maximum qui pourra être stocké. En effet, si vous déclarer, par exemple, un short signé stocké sur 2 octets (signé veut dire que le bit de poids fort va déterminer si le nombre est positif ou négatif), les valeurs maximales que vous pouvez stocker vont de −32,767 à +32,767. Si le nombre est entre ces bornes, il n'y aura pas de problème mais que se passe t-il si l'on essaye de stocker un nombre plus petit que -32 767 ou plus grand que 32 767 ?

C'est ce que nous allons voir tout de suite grâce au petit programme suivant.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    short nb1, nb2, res = 0;

    printf("Entrez le premier nombre : ");
    scanf("%hd", &nb1);

    printf("Entrez le second nombre : ");
    scanf("%hd", &nb2);

    res = nb1 + nb2;

    printf("%hd + %hd = %hd\n", nb1, nb2, res);

    return 0;
}

Rien de bien sorcier, on demande à l'utilisateur d'entrer deux nombres, on additionne ces deux nombres et on affiche le résultat.

Le type utilisé est un short et sa taille, sur mon système du moins, est de 2 octets et il est signé et pour rappel, le nombre positif maximum que l'on peut stocker est donc 32 767.

Testons notre petit programme !

que20@hacktion:~$ ./integeroverflow
Entrez le premier nombre : 10000
Entrez le second nombre : 20000
10000 + 20000 = 30000
que20@hacktion:~$

Le résultat est tout à fait correct. Maintenant, effectuons une opération où le résultat serait supérieur à 32 767 et voyons ce que ça nous donne comme réponse.

que20@hacktion:~$ ./integeroverflow
Entrez le premier nombre : 10000
Entrez le second nombre : 22769
10000 + 22769 = -32767
que20@hacktion:~$

Hein ? 10000 + 22769 = ... -32767 ? Il n'y a pas comme une petite erreur là ?

Eh bien, non ! Le résultat n'est certes pas le bon mais il est "normal" : vous avez essayé de stocker un nombre qui ne peut pas être contenu dans 2 octets Qu'a fait alors votre ordinateur ? Il a tout simplement tronqué ce qui dépassait et a gardé ce qui rentrait dans les 2 octets (il faut également tenir compte du bit de poids fort qui, pour un nombre positif DOIT être égal à 0. Si celui-ci passe à 1, notre nombre basculera alors dans le négatif). On se retrouve donc avec un nombre qui n'est pas du tout celui qui était attendu.

Schématisons ce comportement (on va prendre le cas d'un char signé, stocké sur 1 seul octet, donc pouvant aller de -127 à +127).

Le résultat de l'opération 100 + 27 nous donne 127 (0111111 en binaire). En mémoire, voici comment notre nombre sera stocké.

+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+

Si jamais on rajoute ne serait ce que 1 à ce résultat, cela DEVRA impacter le bit de poids fort.

Maintenant, essayons de stocker le résultat de l'opération 100 + 30 (ce qui donne 130 ou 10000010 en binaire).

+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
+---+---+---+---+---+---+---+---+

Et là, c'est le drame : on est au delà de ce que l'on peut stocker comme nombre positif. Le bit de poids fort est modifié et vu qu'il vaut à présent 1 et que notre nombre est signé, cela signifie qu'il est désormais considéré comme négatif. Le résultat final vaudra donc -126 et non 130.

Voilà l'explication de l'étrange résultat obtenu.

Les integer overflows ont été responsables de nombreuses anecdotes, certaines étaient amusantes alors que d'autres beaucoup moins et ont coutées gros, très très gros mais toutes ont pour origine cette fameuse erreur. Nous allons en voir quelques unes.

Chrono Trigger sur DS : Le boss qui pouvait être vaincu en le soignant

Les integer overflows sont particulièrement appréciés dans le domaine du jeu vidéo (oui, les overflows, ça ne sert pas qu'à prendre le contrôle de machines à des fins malveillantes :D) car ils amènent à des situations assez improbables.

Le cas que nous allons voir en premier, car il est assez simple à comprendre, est celui du boss final de Chrono Trigger sur DS. Ce boss avait la particularité qu'à un moment donné du combat, il absorbait les attaques magiques. Cela signifiait que si vous lui faisiez une attaque de soin, cela le soignait (et augmentait par conséquent son nombre de PV). Ses PV étaient stockés sur un entier signé de 2 octets (16 bits), ce qui fait que, comme dit plus haut, le nombre maximum pouvant être stocké est de 32767, or ce boss avait de base 32000 PV. J'imagine que vous devinez où je veux en venir : si vous le soigniez et que ses PV dépassaient le seuil fatidique des 32767, eh bien, par le cheminement que nous avons vu ci-dessus, son nombre de PV se retrouvait alors dans le négatif ! Résultat des courses, la console considérait qu'il était vaincu !

Voici la preuve en live !

A la fin du combat, notre boss se retrouve avec 35158 PV ce qui engendre un integer overflow puisque les PV sont stockés sur un entier de 2 octets où le nombre positif maximum est de 32767. Le résultat final étant un nombre négatif, la console considère alors que vous avez gagné le combat !

Démontrons l'overflow avec notre petit programme d'addition.

que20@hacktion:~$ ./integeroverflow
Entrez le premier nombre : 10000
Entrez le second nombre : 25158
10000 + 25158 = -30378
que20@hacktion:~$

Nous obtenons bel et bien un nombre négatif !

Gandhi : le dictateur le plus sanguinaire qui ait jamais existé

Autre cas de figure assez célèbre, celui de Gandhi dans le jeu Civilization. Dans ce jeu, vous deviez bâtir votre empire et faire face à celui de vos concurrents. Chaque dirigeant possédait des caractéristiques particulières qui déterminaient en quelque sorte leur caractère : certains étaient plus agressifs alors que d'autres jouaient de façon nettement plus pacifiste. Gandhi était l'un de ces dirigeants et, pour coller au personnage, il était bien entendu très pacifiste. Seulement voilà, souvent, à un moment donné de la partie, notre cher Gandhi pétait littéralement un cable et devenait extrémement agressif, prêt à nucléariser tous ses voisins, et ce sans raison apparente. Une situation pour le moins étrange... ou pas.

En fait, comme indiqué ci-dessus, chaque dirigeant possédait des caractéristiques. L'une d'elles était le niveau d'aggresivité. Ce niveau était stocké dans un entier non signé de 1 octet (donc pouvant aller de 0 à 255). Gandhi avait 1 de base. Mais il se fait que ces caractéristiques pouvaient être légèrement modifiées selon les choix que vous preniez. Par exemple, choisir la démocratie vous faisait bénéficier d'un bonus de -2 pour le niveau d'aggresivité. Pour la plupart des dirigeants, ce bonus ne posait pas de problème mais pour Gandhi, c'était une tout autre histoire ! En effet, Gandhi avait un niveau d'aggresivité initial de 1 donc si Gandhi choisissait la démocratie, son niveau d'aggresivité diminuait de 2, ce qui l'amenait à -1 (111111111 en binaire). Sauf que le problème, c'était que le niveau d'aggresivité était stocké sur un entier NON SIGNÉ ! On avait donc un joli integer overflow, on peut même parler d'underflow ici ! Et ce n'est pas tout car que vaut le nombre binaire 111111111 s'il est non signé ? Réponse : 255 ! Résultat, notre ami Gandhi se retrouvait alors avec le niveau d'aggresivité MAXIMUM et voulait de ce fait assez souvent atomiser ses adversaires qui ne lui avaient pourtant rien fait. Voilà l'explication « logique » de son étrange comportement.

Une fois de plus, nous allons prouver ce bug. Modifions légèrement notre programme pour effectuer non plus une addition mais une soustraction et stockons le résultat dans un char non signé.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    unsigned char nb1, nb2, res = 0;

    printf("Entrez le premier nombre : ");
    scanf("%hhu", &nb1);

    printf("Entrez le second nombre : ");
    scanf("%hhu", &nb2);

    res = nb1 - nb2;

    printf("%hhu - %hhu = %hhu\n", nb1, nb2, res);

    return 0;
}

Reproduisons ensuite la situation.

que20@hacktion:~$ ./integeroverflow
Entrez le premier nombre : 1
Entrez le second nombre : 2
1 - 2 = 255
que20@hacktion:~$

On obtient bien 255 ! :)

Maintenant vous savez pourquoi il est si méchant dans Civilization ! :D

Le bug, bien qu'étant involontaire à la base, est depuis volontairement conservé dans les autres jeux Civilization.

Le cas Ariane 5 : Houston, on a un problème

L'integer overflow le plus célèbre et probablement le plus coûteux de l'histoire est très certainement celui qui fût à l'origine de l'échec explosif du premier lancement d'Ariane 5 en 1996. En effet, 40 secondes seulement après avoir décollée, la fusée explosa en plein vol. Il a fallu des mois avant de trouver quelle était l'origine de cet échec : un « simple » integer overflow.

En fait, on s'est finalement aperçu que le logiciel de navigation d'Ariane 5 était celui qui avait été conçu pour Ariane 4. Seulement voilà, les moteurs d'Ariane 4 étaient bien moins puissants que ceux d'Ariane 5 qui ont produit des nombres bien plus grands. Le logiciel de navigation n'étant pas prévu pour gérer de tels ordres de grandeur, il en a résulté une erreur de cast d'un entier 64 bits à un entier 16 bits ce qui a, au final, trompé complétement l'ordinateur de bord qui croyait que la fusée partait en vrille alors que ce n'était pas du tout le cas et a enclenché une tentative de redressement. Ce virage brusque a provoqué le détachement d'un des deux accélérateurs auxiliaires ce qui a fini par déclencher le système d'auto-destruction de la fusée.

Un petit débordement qui ne coûta « que » quelques centaines de millions (voir peut être quelques milliards avec les coûts sous-jacent) de dollars.

Conclusion

Dans le hacking, ce qui intéresse généralement, ce sont les cas extrêmes car ce sont eux qui sont le plus souvent susceptibles de provoquer un comportement inattendu du programme et les integer overflows font partie de ces cas. Ils sont assez fréquents dans des langages tels que le C/C++ car tout est laissé à la charge du développeur et ne sont pas toujours évidents à détecter (parce que l'on aura tendance à tester les cas les plus courants). Comme nous avons pu le voir, les conséquences peuvent être multiples, parfois sans gravité ou bien au contraire carrément catastrophiques.

Facebook button Twitter button Google button

Laissez un commentaire

Votre adresse email ne sera pas publiée. Les champs marqués d'une * sont obligatoires.

Commentaires (2)

Tar.gz 23/05/2017

Ton blog est génial, il est très propre et tes articles sont d'une rare qualité ! (et on apprend aussi pourquoi Gandhi nous prend en grippe sans raison :D) Tu parles beaucoup d'exploitation de binaires, as-tu déjà trouvé ce genre de faille dans des conditions réeles ? Un petit article sur ça serait ultra cool (genre fuzzing, etc ...)

Que20 25/05/2017

Merci, content que ce blog plaise (c'est un peu pour cela que je l'ai créé :) ). Pour répondre à ta question, non je ne me suis pas vraiment penché sur l'exploitation en situation réelle, il faut dire qu'il y a encore l'une ou l'autre protection qui vient rendre l'exploitation très difficile. De plus, trouver une faille en situation réelle est NETTEMENT plus compliqué ne serait déjà que parce que tu ne sais pas s'il y en a une ou pas, que le programme est souvent bien plus gros que les exemples à la con que je propose et que les programmes ne seront pas forcément compilés pour te faciliter la tâche. Après je parle d'une faille non connue, tu peux bien sûr toujours faire un tour sur celles qui sont déjà listées et là forcément tu sauras déjà vers où chercher. Par contre, pour ce qui est de failles web (elles sont plus faciles d'accès), là oui, j'en ai déjà trouvé en situation réelle. ;) (le blog manque un peu de web d'ailleurs)