String manipulation functions in Glibc, MS Visual Studio and 0x7efefeff, 0x81010100, 0x81010101

Recently i got a chance to read a blog(first link in https://hiddencodes.wordpress.com/2011/12/20/bug-hunting-to-exploit-log/) about finding vulnerability. He given a tip on finding the string manipulation functions in the binary. It was quite new to me so i started to look into it. Stackoverflow had an interesting link to it. It looks like a optimized way of finding the length of the string. Let’s see how Microsoft Visual Studio and Glibc implements this. I started off with Stackoverflow link http://stackoverflow.com/questions/2372315/how-to-implement-strlen-as-fast-as-possible.

www.lrdev.com/lr/c/strlen.c explains this nicely about the background of this technique.

/* Bit patterns (32 bit system), temporary.
  * The three used 32 bit patterns are 0x7efefeff (7efefeff,
  * 7efefeffh, m), 0x81010101 (81010101, 81010101h, -m) and
  * 0x81010100 (81010100, 81010100h, ~m).
  * On 64 bit systems, the pattern would be 0x7efefefefefefeff (its
  * complement 0x8101010101010101).
*/

/* Check if this chunk is a candidate for having embedded nul
  * bytes.
  * This algorithm assumes two’s complement integer
  * representation.
  * i+0x7efefeff is the same as i-0x81010101.
  * Subtracting 1 from each (possible nul) byte will flip its
  * least significant bit, and possibly some more, depending on
  * the input (all bits up to the least significant set bit).
  * If the byte was zero (all bits cleared, a nul byte), all bits
  * are flipped and a carry bit is generated into the next
  * significant byte, which flips the next byte’s least
  * significant bit a second time.
  * Since we cannot (and don’t want) to check the
  * int-carry-out-bit (the most significant byte’s carry) in C,
  * the most significant byte’s most significant bit is used to do
  * that check, which leads to false candidates if only that bit
  * was set in the most significant byte (i.e. the most
  * significant byte was a \x80 byte).
  * These false candidates weaken the search algorithm’s
  * performance a bit.
  * Comparing the subtraction-flip result with the logic-flip
  * result (^~i), while only considering the sizeof(int) bits of
  * interest (&0x81010100), will reveal if carries have occurred
  * (double-bit-flip vs. single-bit-flip).
*/

Original comparison is,
    (((Orig_value + magic1) ^ ~(Orig_value)) & magic3)

    Usually chosen magic values are (32-bit system),
        magic1 = 0x7efefeff
        magic2 = 0x81010101
        magic3 = 0x81010100

When you see this comparison for first time, it looks like some strange check. But if you read the previous paragraph you can understand this. In simple, what i can say is, we are playing with only four bits here.

Let’s see the first addition:
    Orig_value + magic1
        where,
            magic1 is chosen such that (Orig_value + magic1) and (Orig_value – magic2) is equal (read the above paragraph)

Let’s write the original comparison as,
   (((Orig_value – magic2) ^ ~(Orig_value)) & magic3)

    i.e
    (((Orig_value – 0x81010101) ^ ~(Orig_value)) & 0x81010100)

Basic idea behind this subtraction operation is, if the original byte value is 0x00 and when we subtract 0x01 from it then it has to borrow a bit from the low significant bit of next higher byte. Due to the subtraction operation some bits are flipped once and some are flipped twice. We are interested in bits that are flipped TWICE.

To find this, we are flipping the Orig_value once (That is the result of NOT operation).Now we have two values, once is that subtracted one and another is the flipped one.
Let’s XOR this calculated value and ONCE flipped value.

    (Orig_value – 0x81010101) ^ ~(Orig_value)
 
What we get is a value, with the bits set to 1 that are flipped twice.

Now we have the list of bits that are flipped twice. We will just check whether bit 8, 16, 24 and 31 is set or not. If any one of the bit is set then it means the Orig_value had a byte 0x00.

Yes there is a corner case. For one of the Orig_value we need a special attention.

     (0x00000000 – 0x81010101) = Sub:0x7EFEFEFF ^ 0xFFFFFFFF = 0x81010100 & 0x81010100 = 0x81010100 : ZERO: Yes
     (0x00000001 – 0x81010101) = Sub:0x7EFEFF00 ^ 0xFFFFFFFE = 0x810100FE & 0x81010100 = 0x81010000 : ZERO: Yes
     (0x00000100 – 0x81010101) = Sub:0x7EFEFFFF ^ 0xFFFFFEFF = 0x81010100 & 0x81010100 = 0x81010100 : ZERO: Yes
     (0x00010000 – 0x81010101) = Sub:0x7EFFFEFF ^ 0xFFFEFFFF = 0x81010100 & 0x81010100 = 0x81010100 : ZERO: Yes
     (0x01000000 – 0x81010101) = Sub:0x7FFEFEFF ^ 0xFEFFFFFF = 0x81010100 & 0x81010100 = 0x81010100 : ZERO: Yes
     (0x80000000 – 0x81010101) = Sub:0xFEFEFEFF ^ 0x7FFFFFFF = 0x81010100 & 0x81010100 = 0x81010100 : ZERO: Yes
    (0x80FFFFFF – 0x81010101) = Sub:0xFFFEFEFE ^ 0x7F000000 = 0x80FEFEFE & 0x81010100 = 0x80000000 : ZERO: Yes
     (0x81010101 – 0x81010101) = Sub:0x00000000 ^ 0x7EFEFEFE = 0x7EFEFEFE & 0x81010100 = 0x00000000 : ZERO: No
     (0x00FFFFFF – 0x81010101) = Sub:0x7FFEFEFE ^ 0xFF000000 = 0x80FEFEFE & 0x81010100 = 0x80000000 : ZERO: Yes
     (0xFF00FFFF – 0x81010101) = Sub:0x7DFFFEFE ^ 0x00FF0000 = 0x7D00FEFE & 0x81010100 = 0x01000000 : ZERO: Yes
     (0xFFFF00FF – 0x81010101) = Sub:0x7EFDFFFE ^ 0x0000FF00 = 0x7EFD00FE & 0x81010100 = 0x00010000 : ZERO: Yes
     (0xFFFFFF00 – 0x81010101) = Sub:0x7EFEFDFF ^ 0x000000FF = 0x7EFEFD00 & 0x81010100 = 0x00000100 : ZERO: Yes
     (0xFFFFFFFF – 0x81010101) = Sub:0x7EFEFEFE ^ 0x00000000 = 0x7EFEFEFE & 0x81010100 = 0x00000000 : ZERO: No
     (0x11111111 – 0x81010101) = Sub:0x90101010 ^ 0xEEEEEEEE = 0x7EFEFEFE & 0x81010100 = 0x00000000 : ZERO: No

This algorithm gives a wrong result when Orig_value is 0x80XXXXXX.

 

Let’s see how Glibc and Microsoft VS 2010 implements this algorithm.

Glibc:
    http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strlen.c;h=5f22ce95097d4090c6c32fc7cf6c2ef9cf6e86a8;hb=24c0bf7a76ecec65aca0dbce1f7ebb8f68425dc2
   
    if (((longword – lomagic) & ~longword & himagic) != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr – 1);
        // hiddencodes: Here it is check for the corner case.
      if (cp[0] == 0)
        return cp – str;
      if (cp[1] == 0)
        return cp – str + 1;
      if (cp[2] == 0)
        return cp – str + 2;
      if (cp[3] == 0)
        return cp – str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp – str + 4;
          if (cp[5] == 0)
        return cp – str + 5;
          if (cp[6] == 0)
        return cp – str + 6;
          if (cp[7] == 0)
        return cp – str + 7;
        }
     }

Microsoft VS 2010:
    This implements the algorithm in two different ways. One is a portable version and another is not a portable version.
   
    X:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src\intel\strlen.asm

    Following functions uses this magic value:

X:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src>grep -nri 7efefe *
intel/memchr.asm:128:        mov     edi,7efefeffh
intel/strcat.asm:127:        mov     edx,7efefeffh
intel/strcat.asm:181:        mov     edx,7efefeffh
intel/strchr.asm:102:        mov     edi,7efefeffh       ; work with edi & ecx for looking for chr
intel/strlen.asm:82:        mov     edx,7efefeffh
intel/strncat.asm:94:        mov     edx,7efefeffh
intel/strncat.asm:199:        mov     edx,7efefeffh
intel/strncpy.asm:168:        mov     edx,7efefeffh

X:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src>grep -nri 81010100 *
intel/memchr.asm:136:        and     ecx,81010100h
intel/strcat.asm:132:        test    eax,81010100h
intel/strcat.asm:191:        test    eax,81010100h
intel/strchr.asm:119:        and     ecx,81010100h       ; test for chr
intel/strchr.asm:124:        and     eax,81010100h       ; is any flag set ??
intel/strlen.asm:87:        test    eax,81010100h
intel/strncat.asm:99:        test    eax,81010100h
intel/strncat.asm:209:        test    eax,81010100h
intel/strncpy.asm:175:        test    eax,81010100h

   

Simple C/C++ Program to test this:

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int index=0;
    unsigned int arr[] = { 0x00000000, \
                                                 0x00000001, \
                                                 0x00000100, \
                                                 0x00010000, \
                                                 0x01000000, \
                                                 0x80000000, \
                                                 0x80FFFFFF, \
                                                 0x81010101, \
                                                 0x00FFFFFF, \
                                                 0xFF00FFFF, \
                                                 0xFFFF00FF, \
                                                 0xFFFFFF00, \
                                                 0xFFFFFFFF, \
                                                 0x11111111, \
                                              };
    unsigned int magic1= 0x7efefeff;
    unsigned int magic2= 0x81010100;
   
    unsigned int subbb=  0x81010101;

    printf("\n");
    for (; index < _countof(arr); index++){
        int i = arr[index];
        if (( (i + magic1) ^ ~i) & magic2) {
        //if (( (i – subbb) ^ ~i) & magic2) {
            // Yes zero is there
            //printf(" (0x%08X + 0x%08X) = Sum:0x%08X ^ 0x%08X = 0x%08X & 0x%08X = 0x%08X : ZERO: Yes\n",i, magic1, i+magic1, ~i, (i+magic1)^ ~i, magic2, ((i + magic1) ^ ~i) & magic2);
            printf(" (0x%08X – 0x%08X) = Sub:0x%08X ^ 0x%08X = 0x%08X & 0x%08X = 0x%08X : ZERO: Yes\n",i, subbb, i-subbb, ~i, (i-subbb)^ ~i, magic2, ((i – subbb) ^ ~i) & magic2);
        }
        else{
            //printf(" (0x%08X + 0x%08X) = Sum:0x%08X ^ 0x%08X = 0x%08X & 0x%08X = 0x%08X : ZERO: No\n",i, magic1, i+magic1, ~i, (i+magic1)^ ~i, magic2, ((i + magic1) ^ ~i) & magic2);
            printf(" (0x%08X – 0x%08X) = Sub:0x%08X ^ 0x%08X = 0x%08X & 0x%08X = 0x%08X : ZERO: No\n",i, subbb, i-subbb, ~i, (i-subbb)^ ~i, magic2, ((i – subbb) ^ ~i) & magic2);
        }
        printf("\n");
    }
}

Advertisements
This entry was posted in Binary Auditing, C/C++, Code review experiance, Reversing, Windows VC++ and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s