/:/ Integer overflow /:/
                                       lame version
                                         by `and
                                            _





 What is in :


  ._ Intro _.
  ._ Integer ( Sta je integer i sta je integer overflow ! )
  ._ Example ( Jednostavni primeri                        )
  ._ Outro _.


 Intro :

Ok, evo jos jedan tutorial od mene, ovog puta o overflowing-u integer-a i njegovom exploatisanju ! 

Ovo je pocetnicki tutorial ... pocetnicima preporucujem da procitaju moj prvi tutorial
( Win32Stackbof[full&lame].final )... da bi sto bolje razumeli ono o cemu cu razglabati ovde ... :)

 * OS Windows XP SP1
 * Compiler VC++ 6.0




 Integer :

Integer je promenjiva koja predstavlja realan broj bez decimalnog dela, tj to su celi brojevi ! Njihova velicina zavisi od systema na kojem ih posmatramo, a da bi videli velicinu na nasem systemu napisacemo jednostavan program :


#include <iostream.h>

   int main()
   {
    cout << "Velicina int :\t\t"       << sizeof(int)    << " bajta.\n";
    cout << "Velicina short int is:\t" << sizeof(short)  << " bajta.\n";
    cout << "Velicina long int is:\t"  << sizeof(long)   << " bajta.\n";
    cout << "Velicina char is:\t\t"    << sizeof(char)   << " bajta.\n";
    cout << "Velicina float is:\t\t"   << sizeof(float)  << " bajta.\n";
    cout << "Velicina double is:\t"    << sizeof(double) << " bajta.\n";

    return 0;
 }


Kod mene je to ovako :

Velicina  int  :          4 bajta.
Velicina  short int :     2 bajta.
Velicina  long int :      4 bajta.
Velicina  char :          1 bajta.
Velicina  float :         4 bajta.
Velicina  double :        8 bajta.


Ok to smo videli, sada treba da znamo da postoje pozitivni i negativni brojevi. Oni se razlikuju po takozvanom "most significant bit (MSB) ", ako je MSB = 1 onda je broj negativan a ako je MSB = 0 onda je broj pozitivan, MSB je prvi bit u promenljivoj.

Neki put su nam potrebni i negativni i pozitivni brojevi, a nekad samo pozitivni ... zato se uvodi pojam "signed" i "unsigned", gde "unsigned" brojevi predstavljaju samo pozitivne brojeve, a "signed" i pozitivne i negativne.


  * U C jeziku svi brojevi su po default-u signed


Pazi sad, kako imamo isti broj bajta i za "signed" i za "unsigned" integer-e, najveci broj koji mozemo da upisemo u "unsigned" integer je dva puta veci nego najveci pozitivni broj koji se moze upisati u "signed" integer. Zacudjeni ... ?
 
Jedan unsigned short integer moze raditi sa brojevima od 0 do 65535. Polovina brojeva predstavljeni kao signed short su negativni, tj to su brojevi od -32768 do 32767. Ok ?

Pamti ovo ( a i ne moras, mozes uvek ovde da pogledas :) :

unsigned short int    2 bytes  0 to 65,535 
short int             2 bytes  -32,768 to 32,767 
unsigned long int     4 bytes  0 to 4,294,967,295 
long int              4 bytes  -2,147,483,648 to 2,147,483,647 
int (16 bit)          2 bytes  -32,768 to 32,767 
int (32 bit)          4 bytes  -2,147,483,648 to 2,147,483,647 
unsigned int (16 bit) 2 bytes  0 to 65,535 
unsigned int (32 bit) 2 bytes  0 to 4,294,967,295 
char                  1 byte   256 character values 
float                 4 bytes  1.2e-38 to 3.4e38 
double                8 bytes  2.2e-308 to 1.8e308 


Sada znamo da integer overflow nastaje kada u neku vrednost npr. tipa short int pokusamo da upisemo promenljivu tipa long int. Pitanje je sta se tada desava, evo sta se desava po ISO C99 standardu :

"A computation involving unsigned operands can never overflow,
 because a result that cannot be represented by the resulting unsigned
 integer type is reduced modulo the number that is one greater than
 the largest value that can be represented by the resulting type."

Tj ne moze dodji do overflow-a vec se kao vrednost uzima modul ( ostatak pri deljenju ) operanda. Evo primera da bi sve to bilo malo jasnije ...

a = 0xffffffff
b = 0x1
r = a + b

A rezultat je :

r = (0xffffffff + 0x1) % 0x100000000
r = (0x100000000) % 0x100000000 = 0

Menjanje rezultata primenom modul-a osigurava da samo nizi bitovi budu iskorisceni kao rezultat, pa se samim tim izbegava greska ali se ne dobija tacan rezultat. Ovo se inace naziva "wrap around" tehnika.

Kada sam rekao nizi bitovi sigurno niste obratili mnogo paznje na to ali je to veoma vazno, jer je to poenta "wrap around-a" ... a mozete shvatiti to ovako : Imate neki double int i zelite ga staviti u int, ako je :

double int = 0xBADC0DEDEEFBED ( 52596298052729837 dec )
int        =       0xEDEEFBED (        3991862253 dec )





Example :

........................................................................................
Sta se desava kada pokusamo da "veliki" broj stavimo u "mali" broj ... "widthness bug" :
........................................................................................

#include <stdio.h>
#include <string.h>

    int main(int argc, char *argv[])
	{
            
            
            char buf[80];
            int i;
	    unsigned short s;

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

            if ( s >= 80 )
            {            
               printf("\n Oh no no!\n");
               return -1;
            }

            printf("s = %d\n", s);

            strncpy(buf, argv[2], i);
     
            printf("%s\n", buf);

            return 0;
    }

U ovom primeru vidimo da kao parametar unosimo prvo duzinu stringa a zatim i sam string. Vidimo da je velicna bafera 80 ... zanimljivo je sledece :

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

Ovde stavljamo i u s, a s je manje od i , tj maximalna vrednost za s je 65535, a maximalna vrednost s koju mi trazimo ne sme da bude veca od 80 ( ne sme da bude veca od naseg buffer-a, da ne bi doslo do overflow-a ) ... a mi hocemo da izvrsimo overflow i to bas ovde : 

strncpy(buf, argv[2], i);

Ovde vidimo da u nas bufer mozemo da stavimo i bajta tj mozemo da izvrsimo overflow ako je i vece od 80 ... zakljucujemo da nekako treba preskociti onu proveru velicne s :

if(s >= 80)
{            
  printf("\n Oh no no!\n");
  return -1;
}

A to cemo da uradimo tako sto cemo kao prvi parametar da unesemo neki broj koji je veci od 65535, npr 65560 i videcemo da ce s biti jednako 24. Ali i ostaje 65560 a to znaci da kao drugi parametar mozemo uneti vise od 80by i izvrsiti overflow.



..............................................................................
Hajde sada da vidimo sta je "Arithmetic overflow", pogledajmo sledeci primer :
..............................................................................


#include <stdio.h>
#include <string.h>

main(int argc, char *argv[])
 {

    char mybuf[256];
    unsigned int len1; 
    unsigned int len2;

    len1 = atoi(argv[1]);
    len2 = atoi(argv[2]);

    if((len1 + len2) >= 256)
	{    
       printf("\n Oh no no ...\n");

       return -1;
	}

	else 
	{
	printf("\nsumlen = %d\n\n",(len1+len2));

        strncpy(mybuf,argv[3],len1);

        printf("%s",&mybuf);
	}
   }

Ovaj code je samo primer da bi vam pokazao kako radi ovaj bug, tesko je da ce te se negde sresti sa slicnim ... Vidimo da se ovde uzimaju tri parametra, prva dva su int vrednosti a druga je neki string koji "ne sme" da bude veci od 256by jer se smesta u toliki baffer. Da ne bi doslo do prelivanja baffera koristimo ovaj deo koda :

if((len1 + len2) >= 256)
	{    
       printf("\n Oh no no ...\n");

       return -1;
	}

Ovde vidimo da ako je zbir prvog i drugog parametra veci od 256 program se zavrsava. A ako ne onda se parametar 3 kopira u "mybuf" duzine prvog parametra :

strncpy(mybuf,argv[3],len1); 

Ovde moze doci do prelivanja bufera ako je len1 > 256 ! Zamislite sledecu situaciju :

len1 = 0x104          \\ Decimalno 260
len2 = 0xfffffffc     \\ Decimalno 4 294 967 292

A secamo se ovoga :
unsigned int (32 bit) 2 bytes  0 to 4,294,967,295

I sta se sada desava kada saberemo ove dve vrednosti :

 0x104 + 0xfffffffc = 0x100000100 , rezultat decimalno 4294967552 je veci od dozvoljene vrednosti i zato se kao rezultat uzimaju nizi bitovi ( 32 ). I kao rezultat dobijamo 0x100 decimalno 256.

A to znaci da mozemo zavarati proveru :

if((len1 + len2) > 256)
	{    
       printf("\n Oh no no ...\n");

       return -1;
	}

Ako npr kao len1 unesemo 264 i kao len2 4294967288 dobicemo sledece :

264 dec = 0x108
4294967288 = 0xFFFFFFF8

 0x108 + 0xFFFFFFF8 = 100000100, vidimo da provera prolazi jer je rezultat sabiranja ox100 dec 256 a nas len1 je 264 a to znaci da smo ovde :

strncpy(mybuf,argv[3],len1); 

Izvrsili bufer overflow i prepisali EBP i EIP !


                                         ***

Evo jos jednog primera koji se desava prilikom mnozenja i to kod operatora new[] :

#include <stdio.h>
main()
{
    int howmany;
    howmany = 0x40000002;
    howmany = howmany * sizeof(int);
    printf("%s",howmany);
}

Izlaz je 8 zato sto dolazi do "wrap around-a" ... a kada pogledamo sledeci primer :

int *allocate_integers(int howmany)
{
    return new int[howmany];
}

i malo prostudiramo code iz nekog programa sa ovom funkcijom zapazicemo sledece :

mov  eax, [esp+4] ; eax = howmany
shl  eax, 2       ; eax = howmany * sizeof(int)
push eax
call operator new ; allocate that many bytes
pop  ecx
retd 4

Zakljucujemo da mozemo izvrsiti "under-allocating memory", tj dealociranje memorije.



                                         ***

Evo jos jednog banalnog primera :

bool func(char *s1, int len1, char *s2, int len2) 
{

char buf[128];

if (1 + len1 + len2 > 128) 
return false;

if (buf)
{ 
strncpy(buf,s1,len1);
strncat(buf,s2,len2);
}

return true;

}

Ovde vidimo da len1 moze biti veci od 128 sve dok je len2 negativan a to znaci da mozemo izvrsiti overflow ovde : strncpy(buf,s1,len1); .




........................................................................
Ostaje nam jos da se upoznamo sa menjanjem znaka broja "signedness bug":
........................................................................


    #include <stdio.h>

    int main(void){
            int l;

            l = 0x7fffffff;

            printf("l = %d (0x%x)\n", l, l);
            printf("l + 1 = %d (0x%x)\n", l + 1 , l + 1);

            return 0;
    }


Izlaz je :

    l = 2147483647 (0x7fffffff)
    l + 1 = -2147483648 (0x80000000)

Ovde je l inicijalizovan kao najveci pozitivni broj koji signed long int moze da prihvati. Kada je uvecan MSB je promenjen i sada je l predstavljen kao negativan broj. 

Pogledaj ovo :

int copy_something(char *buf, int len){
        char kbuf[800];

        if(len > sizeof(kbuf)){         
            return -1;
        }

        return memcpy(kbuf, buf, len);  
    }

Funkcija memcpy je ranjiva na ovaj bug jer parametar 3 koji predstavlja koliko se bajtova treba iskopirati mora biti pozitivan a to znaci da ako nekim slucajem preskocimo proveru promenljive len unoseci neki negativan broj, izvrsiti buffer overflow zato sto ce len u funkciji memcpy biti predstavljen kao veliki pozitivan broj koji ce biti veci od kbuf.





                                         ***

A znate sta se desava kod oduzimanja i malloc funkcije ...

int func(size_t Size) 
{
if (Size < 1024) 
{
char *buf = (char *)malloc(Size-1);
memset(buf,0,Size-1); 
return 1;
} 
else 
{ 
return 0; 
} 

}

Kao prvo Size ne moze biti negativan zbog tipa size_t, ali sta ako je 0 ? Dolazi do alociranja memorije od 4GB. Zasto ?
Pa zato sto malloc funkcija kao parametar uzima pozitivan broj a ovde je taj broj -1, a kada se -1 prebaci u hex dobijemo 0xFFFFFFFF a to je jednako ( unsigned\pozitivno ) 4,294,967,295.






Outro :

... mislim da je ovo gore jasno svima ako ne onda bacite pogled na "p60-0x0a integer overflow.txt", toliko od mene za sada ... ako ima gresaka\pitanja cimnite me !




                                                                      `and 2005
                                                              im_happy_icefor@yahoo.com