File Verification Using CRC

File verification is the process of determining whether a file on a computer has been modified unexpectedly. No matter whether this happens through hardware failure, program error, or malicious tampering, I like to know when a file has had its contents altered. Likewise, I'd like a convenient way to check the integrity of a file to verify that it hasn't been changed.

The question of file integrity has been on my mind because of several nearly simultaneous incidents. First of all, I recently ran dozens of relatively untested programs through my home system when judging the Dr. Dobb's Data Compression Contest. At least two programs caused inadvertent damage to the file systems on my PC, one under UNIX and the other under MS-DOS. In both cases, I was able to spot much of the damage; but after I restored the data that looked bad, I was left feeling unsure about the rest of my system. Had other files been damaged in more subtle ways? I suddenly felt as though I couldn't trust my system.

An even more alarming incident occurred a couple of weeks later. A programmer who supplies my company (Greenleaf Software) with a product for resale called and casually mentioned that his office had been infested with the notorious "Stoned" virus. Had we by any chance noticed anything funny in our systems? We see funny things on our systems on an hourly basis, so suddenly we again did not trust any of the files on our PCs. (Fortunately, this turned out to be a false alarm.)

Finally, as part of a recent product release at Greenleaf, we decided to implement a program that would allow our customers to download short patch files from our BBS to apply to the source code they purchased from us. I wrote a small program that could read in the patch file and make modifications to an existing source file, resulting in a corrected output file. To keep the program simple, however, we had to have a way to be sure that the input file we were patching was the file we expected it to be, and that it hadn't been modified in any way. Our patch program would be capable of really fouling up the file if a programmer had just changed a few lines here and there before trying to patch it.

The solution to all these problems consists of two parts. The first is to use the CRC-32 algorithm to provide a "fingerprint" method of file identification. The second is a general-purpose program called CRCMAN that can develop a catalog of CRC values for all the files in a directory tree, and can later check the files in the same directory tree against the catalog.

CRC-32 is an acronym for the "32-bit Cyclical Redundancy Check" algorithm. CRC-32 generally refers to a specific 32-bit CRC formula sanctioned by the CCITT, an international standards body primarily concerned with telecommunications. CRC-32 is used in communications protocols such as HDLC and ZMODEM to verify the integrity of blocks of data being transferred through various media.

CRC calculations are done using a technique with the formidable name of "polynomial division." A block of data, regardless of how long, is treated as if each bit in the block is the coefficient in a long polynomial. For example, a single hexadecimal byte, F0H, would be considered to be the polynomial: 1*X⁷ + 1*X⁶ + 1*X⁵ + 1*X⁴ + 0*X³ + 0*X² + 0*X¹ + 0*X⁰. The terms with coefficients of 0 drop out, so the polynomial can be expressed as: X⁷ + X⁶ + X⁵ + X⁴. If we are calculating the CRC of an entire file, the exponents will be very large but this is not a problem. The actual values of the exponents do not come into play during the calculation of the CRC, so the CRC values can grow indefinitely without affecting the algorithm.

The calculation of the CRC is done by dividing a second polynomial, the "generator polynomial," into the message polynomial, producing a quotient and a remainder. The generator polynomial used by the CRC-32 is: X³² + X²⁶ + X²³ + X²² + X¹⁶ + X¹² + X¹¹ + X¹⁰ + X⁸ + X⁷ + X⁵ + X⁴ + X² + X¹. After dividing this generator polynomial into our message polynomial, we simply discard the quotient, and use the remainder as our 32-bit CRC.

Polynomial division to create a CRC was originally done using hardware shift registers and Boolean glue logic. Fortunately, "cookbook" algorithms now exist to implement the CRC on PCs in a relatively fast and efficient manner. In CRCMAN, I use a table-lookup version of the algorithm that exchanges a small increase in storage space for fast calculation.

The details of how the CRC calculations work have been discussed in many places, so I won't go into further details in this article. Some excellent resources are listed in the References section, if you are interested in exploring this topic further.

CRCMAN uses the CRC-32 algorithm to generate a 32-bit number for any given file. We then treat this 32-bit number as a somewhat unique "fingerprint" for that file. The fingerprint differs from the human fingerprint in that while no two people have identical fingerprints, this is not the case for files. More than 4,294,967,296 different files exist in the world, so it is a foregone conclusion that some of them must have identical checksums. However, the CRC-32 does have attributes that make it attractive for verification of files. These include the following:

• Every bit in the message contributes to the CRC. This means that changing any bit in the message changes the CRC.
• Relatively small changes in the message are guaranteed to change in the CRC. Thus, two files that differ by only a few bits are certain to have different CRC values.
• The histogram of output CRC values for input messages tends to be flat. For a given input message, the probability of a given CRC being produced is nearly equal across the entire range of possible CRCs from 0 to FFFFFFFFH.

Another characteristic we would like to see in the CRC-32 is noninvertability. Although not really necessary when using the CRC to simply guard against accidental file corruption, noninvertability becomes much more important when we want to detect virus infestations of our files.

A typical virus might operate by modifying the MS-DOS command interpreter, COMMAND.COM. My version of COMMAND.COM happens to have a CRC-32 of O2f8690cH. In the event that a virus modifies this file, it will undoubtedly have a new CRC-32. The challenge to the virus programmer would then be to add new bytes to the end of the file so that the original CRC was restored.

Unfortunately, it is possible to do this through simple brute force. In theory, the virus programmer could just add a limited number of bytes to the end of COMMAND.COM, and then begin systematically trying out new values of those bytes until random chance produces a combination that yields the correct checksum. An efficient algorithm that could calculate a new CRC in a millisecond should then never need more than a few weeks of processing power to come up with a set of numbers that solves this puzzle. And a programmer with access to hardware with an extra couple of orders of magnitude of CPU power could solve the same problem in an afternoon.

This means that while CRCMAN will be an excellent judge of unintentional damage to files, it is possible than an exceptionally clever virus will be able to defeat it. Further modifications to the program would improve its ability to fight viruses. For example, just storing the length of the file along with its CRC would make a virus programmer's job much more difficult, if not impossible.

CRCMAN was written as a dual-purpose program. It has two operating modes: one for building a list of CRC values, and another for checking files against that list. The command line for CRCMAN has one of two forms. The first form is used to create a CRC listing file that has the CRC and filename of every file in a directory tree. The syntax for invoking CRCMAN in this mode is: CRCMAN-b directory crc-filename. The directory parameter passed to CRCMAN is the name of a root directory. CRCMAN will calculate the CRC-32 for every file in and under that directory, and store the results in the CRC file named as the second parameter. The CRC file created is an ordinary ASCII text file that can be edited and manipulated using any text editor. All it contains is a sequence of lines that contain a CRC-32 value followed by a filename.

363476a4 .\CRC.TXT
b97a5169 .\CRC.BAK
d6a5f5f5 .\CRCMAN.C
02f8690c .\TEST\COMMAND.COM
88f2e4d6 .\CRCMAN.EXE
23123e1c .\TEMP.CRC

    Checking .\CRC.TXT  .
    Error: Expected 76a414c6, got 86793634
    Checking .\CRC.BAK  .
    Error: Expected 516914c6, got 76a4b97a
    Checking .\CRCMAN.C  .  OK
    Checking .\TEST\COMMAND.COM ..  OK
    Checking .\CRCMAN.EXE  .  OK
    Checking .\TEMP.CRC  .  OK

CRCMAN correctly detected the changes in the two files. In the current implementation of CRCMAN, when an error is detected, an error message is printed out to the screen. In a production version of this program, the action taken can obviously grow to be as sophisticated as you like.

Of the two possible jobs given to this program, building the CRC file is the more complex. Both tasks have to calculate the CRC-32 values for one or more files, but building the file has the additional job of navigating through the directory tree. Complicating this even more, navigating the directory tree has to be done differently under UNIX and MS-DOS.

BuildCRCFile() sets things up for the task by opening up the output file that will receive all the filenames and CRC values. It then makes a call to the routine that does all the work, ProcessAllFiles(). This routine takes two arguments, a path name and a CRC file FILE pointer.

    ProcessAllFiles( path )
         dir = OpenDirectory( path )
          while FilesLeftInDirectory( dir )
               filename = GetNextFile( dir )
               if filename is a directory then
                    ProcessAllFiles( filename )
               else
                    crc = CalculateCRC( filename )
                    write filename and crc
               endif
          end of while
     end of ProcessAllFiles

The underlying operating systems primitives to implement this pseudocode are different under MS-DOS and UNIX. UNIX uses a pair of functions called opendir() and readdir() to open the directory and get the next filename. Under MS-DOS, there are a pair of MS-DOS function calls named findfirst() and findnext(). To complicate things under MS-DOS, Borland has implemented these system calls using different function and structure names than those selected by other vendors.

The result of all these variations is a routine that has been coded using a rat's nest of #ifdef statements and macro definitions. However, if you understand the underlying pseudocode, the C is not too bad. One nice thing about this particular function is that it provides an excellent example of a job that is truly easier to do using recursion.

Examining the body of ProcessAllFiles() shows that near the bottom of the routine, a call is made to Calculate CRCFile(). This routine calculates the CRC-32 file for the file. The result is then printed out along with the filename to the CRC log file. As ProcessAllFiles() does its work, a complete listing of the entire directory tree is built up, for later use by CRCMAN in its checking mode.

Calculating the CRC-32 for a given file is relatively easy. The CalculateFileCRC() routine repeatedly reads in blocks of 512 bytes and passes them through the CalculateBufferCRC() routine. CalculateBufferCRC takes as an argument the CRC of the file up to that point, and returns the new CRC for the file so far. This process repeats until the entire file has been processed.

When calculating the file CRC, this routine initializes the CRC value to all 1s, or 0xFFFFFFFFL. After the file calculation has completed, the bits in the CRC are inverted by XORing with the same value, 0xFFFFFFFFL. This pre- and postconditioning is intended to provide additional error immunity and is used by protocols such as ZMODEM, as well as programs such as PKZIP and ARJ. The CRC values produced by CRCMAN consequently match up with those you would see in the listing of a ZIP file containing the same list of files.

The second mode of operation for this program is the CRC check. Most of the work here is done in the CheckFiles() routine. It gets to bypass the directory tree navigation, because all the filenames it needs to check are already stored in the CRC log file. All this routine does is repeatedly read in a line from the CRC log file containing a 32-bit CRC value and a filename. It then calculates the actual CRC for the file and reports on whether the stored and calculated CRC values match up.

The simple ASCII format of this file makes for easy maintenance of the CRC log files. For example, if the log file contains the CRC values for the directory tree containing your Borland C++ compiler, you will probably regularly get reports from CRCMAN that your configuration file, TURBOC.CFG, has changed. Because you know this file is supposed to change, it is a simple enough matter to edit the log file and delete the line that refers to the file.

CRCMAN can be set up to provide a quick way to check the integrity of any or all of the files on your system. By calling CRCMAN with the -b parameter for every directory full of executables, you create a set of CRC log files that can be periodically checked with a single call to CRCMAN. CRCMAN operates quickly enough that you can even include it as part of your AUTOEXECBAT file under MS-DOS, without letting it slow down your work too much.

CRCMAN could also be easily modified to provide good virus checking. To make things a little tougher on the virus programmer, you would probably want to store the length of the file along with CRC-32, and perhaps even store the file time stamp. While even these measures don't give you an iron-clad guarantee against a virus attack, they will probably detect the vast majority of infestations.

Ultimately, the best way to use CRCMAN would be as a concurrent process that runs continuously on your machine at low priority. This is fairly easy to implement under OS/2 or UNIX, but is somewhat problematic under MS-DOS.

Campbell, Joe. C Programmer's Guide to Serial Communications. Indianapolis, Ind.: Howard W. Sams, 1988.

Ramabadran, Tenkasi V. and Sunil S. Gaitonde. "A Tutorial on CRC Computations." IEEE Micro (August 1988).

DDJ

<a name="0117_0011">

/************************** Start of CRCMAN.C *************************
 * This program is used to build a list of CRC-32 values for all of files in a
 * given directory tree. After building file, program can be run later to
 * verify CRC values, giving assurance of integrity of files. To build CRC file
 * command line is: CRCMAN -b root-dir crc-file-name
 * To check list of files created, run with: CRCMAN crc-file-name
 * Should work with most 16 and 32-bit compilers under MS-DOS and UNIX. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>

unsigned long CRCTable[ 256 ];

/* To build this program under UNIX, define UNIX either on the command line or
 * by editing this file. To define it on the command line, program should be
 * built like this: cc -o crcman -DUNIX crcman.c   Code in this program assumes
 * UNIX compiler is K&R variety; does away with real function prototyping. */
#ifdef UNIX

#include <varargs.h>
#ifdef M_XENIX
#include <sys/ndir.h>
#else
#include <sys/dirent.h>
#endif /* M_XENIX */

#define SEPARATOR "/"
#define FILENAME_SIZE 81

void FatalError();
unsigned long CalculateFileCRC();
void ProcessAllFiles();
void BuildCRCFile();
void CheckFiles();
unsigned long CalculateBufferCRC();
void BuildCRCTable();

#else /* not UNIX, must be MSDOS */
/* Most MS-DOS compilers have converged on same names for structures and
 * functions used when searching directories. Borland C implementations use a
 * variant, requiring macro definitions. Functions work in an identical manner,
 * so actual implementation of code is straightforward. Addition of MS-DOS
 * definition helps convince Zortech compiler to use same structure and
 * function names as everyone else. */
#define MSDOS 1
#include <stdarg.h>
#include <dos.h>

#define SEPARATOR "\\"
#define FILENAME_SIZE FILENAME_MAX

#ifdef __TURBOC__

#include <dir.h>
#define FILE_INFO                 struct ffblk
#define FIND_FIRST( n, i )        findfirst( ( n ), ( i ), FA_DIREC )
#define FIND_NEXT( info )         findnext( ( info ) )
#define FILE_NAME( info )         ( ( info ).ff_name )

#else

#define FILE_INFO                 struct find_t
#define FIND_FIRST( n, i )        _dos_findfirst( (n), _A_SUBDIR, (i) )
#define FIND_NEXT( info )         _dos_findnext( ( info ) )
#define FILE_NAME( info )         ( ( info ).name )

#endif

void FatalError( char *fmt, ... );
unsigned long CalculateFileCRC( FILE *file );
void ProcessAllFiles( char *path, FILE *crc_file );
void BuildCRCFile( char *input_dir_name, char *crc_file_name );
void CheckFiles( char *crc_file_name );
unsigned long CalculateBufferCRC( unsigned int count, unsigned long crc,
                                  void *buffer );
void BuildCRCTable( void );

#endif  /* UNIX */

/* Main program checks for valid occurences of two different types of command
 * lines, and executes them if found. Otherwise, it prints out a simple
 * usage statement and exits.  */
int main( argc, argv )
int argc;
char *argv[];
{
    setbuf( stdout, NULL );
    BuildCRCTable();
    if ( argc == 2 )
        CheckFiles( argv[ 1 ] );
    else if ( argc == 4 && strcmp( argv[ 1 ], "-b" ) == 0 )
        BuildCRCFile( argv[ 2 ], argv[ 3 ] );
    else {
        printf( "Usage: CRCMAN [-b input_dir] crc-file \n" );
        printf( "\n" );
        printf( "Using the -b option checks all files under the input_dir\n" );
        printf( "and appends their data to the crc-file.  Otherwise, the\n" );
        printf( "program checks the CRC data of all of the files in the\n" );
        printf( "crc-file and prints the results\n" );
        return( 1 );
    }
    return( 0 );
}
/* Instead of performing a straightforward calculation of the 32-bit CRC using
 * a series of logical operations, program uses faster table lookup method. */
#define CRC32_POLYNOMIAL     0xEDB88320L

void BuildCRCTable()
{
    int i;
    int j;
    unsigned long crc;

    for ( i = 0; i <= 255 ; i++ ) {
        crc = i;
        for ( j = 8 ; j > 0; j-- ) {
            if ( crc & 1 )
                crc = ( crc >> 1 ) ^ CRC32_POLYNOMIAL;
            else
                crc >>= 1;
        }
        CRCTable[ i ] = crc;
    }
}
/* Routine checks CRC values for a list of files. */
void CheckFiles( crc_file_name )
char *crc_file_name;
{
    FILE *crc_file;
    FILE *test_file;
    unsigned long log_crc;
    unsigned long crc;
    char log_name[ FILENAME_SIZE ];
    int result;

    crc_file = fopen( crc_file_name, "r" );
    if ( crc_file == NULL )
        FatalError( "Couldn't open the log file: %s\n", crc_file_name );
    for ( ; ; ) {
        result = fscanf( crc_file, "%lx %s", &log_crc, log_name );
        if ( result < 2 )
            break;
        test_file = fopen( log_name, "rb" );
        if ( test_file != NULL ) {
            printf( "Checking %s ", log_name  );
            crc = CalculateFileCRC( test_file );
            fclose( test_file );
            if ( crc != log_crc )
                printf( "Error:  Expected %08lx, got %08lx\n",
                        log_name, log_crc, crc );
            else
                printf( "OK\n" );
        } else
            printf( "Could not open file %s\n", log_name );
    }
}
/* ProcessAllFiles() scans directory. Routine also makes sure that directory
 * name passed on command line is stripped of trailing '/' or '\' character. */
void BuildCRCFile( input_dir_name, crc_file_name )
char *input_dir_name;
char *crc_file_name;
{
    char path[ FILENAME_SIZE ];
    FILE *crc_file;

    strcpy( path, input_dir_name );
    if ( path[ strlen( path ) - 1 ] == SEPARATOR[ 0 ] )
        path[ strlen( path ) - 1 ] = '\0';
    crc_file = fopen( crc_file_name, "w" );
    if ( crc_file == NULL )
        FatalError( "Can't open crc log file: %s\n", crc_file_name );
    ProcessAllFiles( path, crc_file );
}
/* This routine is responsible for actually performing the calculation of the
 * 32-bit CRC for the entire file. We precondition the CRC value with all 1's,
 * then invert every bit after the entire file has been done. This gives us a
 * CRC value that corresponds with the values calculated by PKZIP and ARJ. */
unsigned long CalculateFileCRC( file )
FILE *file;
{
    unsigned long crc;
    int count;
    unsigned char buffer[ 512 ];
    int i;

    crc = 0xFFFFFFFFL;
    i = 0;
    for ( ; ; ) {
        count = fread( buffer, 1, 512, file );
        if ( ( i++ % 32 ) == 0 )
            putc( '.', stdout );
        if ( count == 0 )
            break;
        crc = CalculateBufferCRC( count, crc, buffer );
    }
    putc( ' ', stdout );
    return( crc ^= 0xFFFFFFFFL );
}
/* This is the routine that is responsible for calculating all of CRC values
 * for files in a given directory. The CRC values and file names are written
 * out to the crc_file. */
void ProcessAllFiles( path, crc_file )
char *path;
FILE *crc_file;
{
#ifdef UNIX
    DIR *dirp;
#ifdef M_XENIX
    struct direct *entry;
#else
    struct dirent *entry;
#endif /* M_XENIX */
#define NAME entry->d_name
#else
    FILE_INFO fileinfo;
    int done;
#define NAME FILE_NAME( fileinfo )
#endif
    char fullname[ FILENAME_SIZE ];
    struct stat buf;
    unsigned long crc;
    FILE *file;

    printf( "Searching %s\n", path );
    strcat( path, SEPARATOR );
#ifdef UNIX
    dirp = opendir( path );
    if ( dirp == NULL )
        FatalError( "Error opening directory %s\n", path );
    entry = readdir( dirp );
    while ( entry != 0 ) {
#else
    strcpy( fullname, path );
    strcat( fullname, "*.*" );
    done = FIND_FIRST( fullname, &fileinfo );
    while ( done == 0 ) {
#endif
        strcpy( fullname, path );
        if ( strcmp( NAME, "." ) && strcmp( NAME, ".." ) ) {
            strcat( fullname, NAME );
            if ( stat( fullname, &buf ) == -1 )
                FatalError( "Error reading stat from file %s!\n", fullname );
            if ( buf.st_mode & S_IFDIR )
                ProcessAllFiles( fullname, crc_file );
            else {
                file = fopen( fullname, "rb" );
                if ( file != NULL ) {
                    printf( "Scanning %s ", fullname  );
                    crc = CalculateFileCRC( file );
                    putc( '\n', stdout );
                    fprintf( crc_file, "%08lx %s\n", crc, fullname );
                    fclose( file );
               } else
                    printf( "Could not open %s!\n", fullname );
            }
        }
#ifdef UNIX
        entry = readdir( dirp );
#else
        done = FIND_NEXT( &fileinfo );
#endif
    }
}
/* Routine calculates the CRC for a block of data using table lookup method.
 * It accepts an original value for the crc, and returns the updated value. */
unsigned long CalculateBufferCRC( count, crc, buffer )
unsigned int count;
unsigned long crc;
void *buffer;
{
    unsigned char *p;
    unsigned long temp1;
    unsigned long temp2;

    p = (unsigned char*) buffer;
    while ( count-- != 0 ) {
        temp1 = ( crc >> 8 ) & 0x00FFFFFFL;
        temp2 = CRCTable[ ( (int) crc ^ *p++ ) & 0xff ];
        crc = temp1 ^ temp2;
    }
    return( crc );
}
/* Fatal error handler prints a formatted error message and then exits. */
#ifdef UNIX

void FatalError( va_alist )
va_dcl
{
    char *fmt;
    va_list argptr;

    va_start( argptr );
    fmt = va_arg( argptr, char * );
#else

void FatalError( char *fmt, ... )
{
    va_list argptr;
    va_start( argptr, fmt );
#endif

    printf( "Fatal error: " );
    vprintf( fmt, argptr );
    va_end( argptr );
    exit( -1 );

}

Copyright © 1992, Dr. Dobb's Journal