12.2 Detecting Modification

12.2.1 Problem

Binary patches can be applied to compiled programs to alter the contents of code or data. The program needs a way of verifying its integrity at runtime.

12.2.2 Solution

Detecting whether portions of a binary have been modified is essentially an error-detection problem; therefore, a checksum algorithm such as CRC32, MD5, or SHA1 can be used to generate a signature for an arbitrary block of code or data. This signature can then be checked at runtime to determine whether any modification has taken place.

12.2.3 Discussion

We have chosen the CRC32 algorithm both for its ease of implementation and for its speed. It is ideal for detecting changes to short sequences of bytes; however, because there are only 2³² possible checksum values, and because it is not cryptographically secure, the likelihood of a collision is high, giving the attacker a realistic chance to replace code without changing the checksum. For this kind of application, cryptographic strength is probably overkill, as there are easier attacks than forcing a collision in the checksums (e.g., simply patch the checksumming code).

The checksum API presented here is an implementation of CRC32, which consists of macros for marking the start and end of the block to be checked, as well as a function to calculate the checksum of the block. The function crc32_calc( ) is used to compute the checksum of a buffer.

#define CRC_START_BLOCK(label) void label(void) {  } #define CRC_END_BLOCK(label)   void _##label(void) {  } #define CRC_BLOCK_LEN(label)   (int)_##label - (int)label #define CRC_BLOCK_ADDR(label)  (unsigned char *)label     static unsigned long crc32_table[256] = {0};     #define CRC_TABLE_LEN 256 #define CRC_POLY      0xEDB88320L     static int crc32(unsigned long a, unsigned long b) {   int idx, prev;       prev = (a >> 8) & 0x00FFFFFF;   idx = (a ^ b) & 0xFF;   return (prev ^ crc32_table[idx] ^ 0xFFFFFFFF); }     static unsigned long crc32_table_init(void) {   int           i, j;   unsigned long crc;       for (i = 0;  i < CRC_TABLE_LEN;  i++) {     crc = i;     for (j = 8;  j > 0;  j--) {       if (crc & 1) crc = (crc >> 1) ^ CRC_POLY;       else crc >>= 1;     }     crc32_table[i] = crc;   }   return 1; }      unsigned long crc32_calc(unsigned char *buf, int buf_len) {   int           x;   unsigned long crc = 0xFFFFFFFF;       if (!crc32_table[0]) crc32_table_init(  );   for (x = 0;  x < buf_len;  x++) crc = crc32(crc, buf[x]);   return crc; }

The following program demonstrates the use of the checksum implementation. Note that the program is first compiled with a printf( ) in main( ) that will print the checksum to stdout. As long as main( ) is linked into the program after the buffer being checked, this printf( ) can be removed and the program recompiled without the value of the checksum changing. Once the checksum is known, a hex editor can be used to patch the checksum value into the location crc32_stored. In this example, the four bytes of the checksum are stored between two 0xFEEDFACE markers that should be overwritten with random bytes before the binary is distributed. Note that the markers will be stored in little-endian order in the binary, hence the reversed ordering of the bytes in the C source.

#include <stdio.h>     /* warning: replace "crc32_stored" with the real checksum! */ asm(".long 0xCEFAEDFE \n"   /* look for 0xFEEDFACE markers */     "crc32_stored:    \n"     ".long 0xFFFFFFFF \n"   /* change this in the binary! */     ".long 0xCEFAEDFE \n"   /* end marker */ );     CRC_START_BLOCK(test) int test_routine(int a) {   while (a < 12) a = (a - (a * 3)) + 1;   return a; } CRC_END_BLOCK( test )     int main(int argc, char *argv[  ]) {   unsigned long crc;       crc = crc32_calc(CRC_BLOCK_ADDR(test), CRC_BLOCK_LEN(test)); #ifdef TEST_BUILD   /* This printf(  ) displays the CRC value that needs to be stored in the program.    * The printf(  ) must be removed, and the program recompiled before distribution.    */   printf("CRC is %08X\n", crc); #else   if (crc != crc32_stored) {     printf("CRC32 %#08X does not match %#08X\n", crc, crc32_stored);     return 1;   }   printf("CRC32 %#08X is OK\n", crc); #endif   return 0; }

As mentioned in the comment just prior to the printf( ) call in main( ), you should compile this program with TEST_BUILD defined, then execute it to obtain the CRC value that needs to be replaced for crc32_stored in the binary. Then rebuild the program with TEST_BUILD undefined, and modify the binary with the proper CRC value from the first run.

It is tempting to generate a checksum of the entire program and use this to determine whether any bytes have been changed; however, this causes a loss of granularity for the checksum and can degrade performance. Instead, you should generate multiple checksums for vital sections of code. These checksums can be encrypted, and they can even be supplemented with checksums of trivial blocks of code to disguise which portions of code are significant.

The check used in main( ) performs a simple comparison, if (crc != crc32_stored). While this demonstrates the basic use of a checksum, use of a straight comparison such as this is strongly discouraged. When disassembled, the call to crc32( ) and the subsequent compare are immediately obvious:

 804842b:       ff 75 fc                pushl  -4(%ebp)  804842e:       ff 75 f8                pushl  -8(%ebp)  8048431:       e8 f2 fe ff ff          call   8048328 <crc32>  ;call crc32(  )  8048436:       83 c4 10                add    $0x10,%esp  8048439:       89 45 f4                mov    %eax,-12(%ebp)  804843c:       8b 45 f4                mov    -12(%ebp),%eax  804843f:       3b 05 d0 83 04 08       cmp    0x80483d0,%eax   ;compare result  8048445:       74 22                   je     8048469          ;jump-if-equal

An attacker simply has to change the je instruction (opcode 0x74) at offset 8048445 to a jmp instruction (opcode 0xEB) to defeat this protection. The generated checksum should never be checked against a valid one; instead, the generated checksum should be used as a source of information that the program requires to execute properly. A byte within the checksum could be used as an index into a jump table, for example, or the checksum itself could be used as a key to decrypt critical code or data.

The next program demonstrates how to use a table of function pointers to test the value of a checksum. Each nibble or half-byte in the checksum is used as an index into a 16-entry table of function pointers; only the correct table entry calls the function to check the next nibble. This method requires 8 tables of 16 function pointers so that one table is used for each nibble in the checksum.

#include <stdio.h>     CRC_START_BLOCK(test) int test_routine(int a) {   while (a < 12) a = (a - (a * 3)) + 1;   return a; } CRC_END_BLOCK(test)     typedef void (*crc_check_fn)(unsigned long *);     static void crc_check(unsigned long *crc);  static void crc_nib2 (unsigned long *crc);  static void crc_nib3 (unsigned long *crc);  static void crc_nib4 (unsigned long *crc);  static void crc_nib5 (unsigned long *crc);  static void crc_nib6 (unsigned long *crc);  static void crc_nib7 (unsigned long *crc);  static void crc_nib8 (unsigned long *crc);     crc_check_fn b1[16] = {0,}, b2[16] = {0,}, b3[16] = {0,}, b4[16] = {0,},              b5[16] = {0,}, b6[16] = {0,}, b7[16] = {0,}, b8[16] = {0,};     #define CRC_TABLE_LOOKUP(table)             \           int          index = *crc & 0x0F; \           crc_check_fn next = table[index]; \           *crc >>= 4;                       \           (*next)(crc)     static void crc_check(unsigned long *crc) { CRC_TABLE_LOOKUP(b1); } static void crc_nib2 (unsigned long *crc) { CRC_TABLE_LOOKUP(b2); } static void crc_nib3 (unsigned long *crc) { CRC_TABLE_LOOKUP(b3); } static void crc_nib4 (unsigned long *crc) { CRC_TABLE_LOOKUP(b4); } static void crc_nib5 (unsigned long *crc) { CRC_TABLE_LOOKUP(b5); } static void crc_nib6 (unsigned long *crc) { CRC_TABLE_LOOKUP(b6); } static void crc_nib7 (unsigned long *crc) { CRC_TABLE_LOOKUP(b7); } static void crc_nib8 (unsigned long *crc) { CRC_TABLE_LOOKUP(b8); }     static void crc_good(unsigned long *crc) {   printf("CRC is valid.\n"); }     int main(int argc, char *argv[  ]) {   unsigned long crc;       crc = crc32_calc(CRC_BLOCK_ADDR(test), CRC_BLOCK_LEN(test)); #ifdef TEST_BUILD   printf("CRC32 %#08X\n", crc); #else   crc_check(&crc); #endif   return 0; }

When this program is compiled with TEST_BUILD defined, the resulting binary will print the CRC32 computed for the function test_routine( ). If the computed CRC32 is 0xFFF7FB7C, the following table indices will represent valid function pointers: b1[12], b2[7], b3[11], b4[15], b5[7], b6[15], b7[15], b8[15]. Each of these contains a pointer to the function that will process the next nibble in the checksum, except for b8[15], which contains a pointer to the function that is called when the checksum has proven valid. The tables in the source can now be rewritten to reflect these correct values:

crc_check_fn b1[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, crc_nib2, 0, 0, 0 },              b2[16] = { 0, 0, 0, 0, 0, 0, 0, crc_nib3, 0, 0, 0, 0, 0, 0, 0, 0 },              b3[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, crc_nib4, 0, 0, 0, 0 },              b4[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, crc_nib5 },              b5[16] = { 0, 0, 0, 0, 0, 0, 0, crc_nib6, 0, 0, 0, 0, 0, 0, 0, 0 },              b6[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, crc_nib7 },              b7[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, crc_nib8 },              b8[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, crc_good };

Obviously, the NULL bytes will have to be replaced with other values to disguise the fact that they are invalid entries. They can be replaced with pointers to functions that handle incorrect checksums, or they can be filled with garbage values to make the program unstable. For example:

crc_check_fn b8[16] = { crc_good - 64, crc_good - 60, crc_good - 56, crc_good - 52,                         crc_good - 48, crc_good - 44, crc_good - 40, crc_good - 36,                         crc_good - 32, crc_good - 28, crc_good - 24, crc_good - 20,                         crc_good - 16, crc_good - 12, crc_good -  8, crc_good -  4,                         crc_good };

In this table, the use of incrementally increasing values causes the table to appear to be valid data, as opposed to addresses in the code segment. Note that you can use the techniques for disguising function pointers described in Recipe 12.9 so that casual scans through the data segment do not reveal this to be a table of function pointers.

12.2.4 See Also

Recipe 12.9