Thread: Find collision in CRC-16

  1. #1
    Registered User
    Join Date
    Oct 2015
    Location
    Germany
    Posts
    9

    Find collision in CRC-16

    Hello,

    so i wrote a program where the user can input a text of arbitrary length and calculates a CRC-16 checksum of that, and tries to find a collision, i.e a different text that matches the same CRC-16,

    somehow im not really happy with rand() that i used in there, any suggestions to improve efficeincy would be greatly appreciated.

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdint.h>
    
    #define MAX_SIZE 200
    /* CRC calculation macros */
    #define CRC_INIT 0xFFFF
    #define CRC(crcval,newchar) crcval = (crcval >> 8) ^ \
            crc_table[(crcval ^ newchar) & 0x00ff]
    
    static const unsigned short crc_table[256] = {
      0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
      0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
      0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
      0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
      0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
      0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
      0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
      0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
      0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
      0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
      0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
      0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
      0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
      0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
      0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
      0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
      0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
      0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
      0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
      0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
      0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
      0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
      0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
      0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
      0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
      0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
      0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
      0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
      0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
      0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
      0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
      0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
    };
    
    unsigned short crcsum(const unsigned char* message, unsigned long length, unsigned short crc)
    {
      unsigned long i;
    
      for(i = 0; i < length; i++)
        {
          CRC(crc, message[i]);
        }
      return crc;
    }
    /* function to calculate the text that causes collision */
    unsigned short calcCollisionPayload(unsigned int strlen)
    {
        srand(time(NULL));
        char payload_coll[MAX_SIZE];
        unsigned short i, crcSumNew;
        char *payload_collPtr;
    
        payload_collPtr = payload_coll;
    
        *payload_collPtr =  (rand()%74 + 48);
        for(i=0;i<strlen;i++)
        {
            ++payload_collPtr;
            *payload_collPtr = (rand()%74 +49) ;
        }
        *payload_collPtr = '\0';
        printf("\n%s",payload_coll );
        crcSumNew = crcsum(payload_coll,strlen, CRC_INIT);
        return crcSumNew;
    
    }
    
    int main()
    {
        char payload[MAX_SIZE], payload2[MAX_SIZE];
        char  *payloadPtr;
        unsigned int i,charCtr;
        unsigned short CRCsum,CRCsum2;
    
        srand(time(NULL));
    
        payloadPtr = payload;
    
        printf("\nEnter a text: ");
    
        *payloadPtr = getchar();
        while(*payloadPtr!='\n')
        {
          ++charCtr;
          ++payloadPtr;
          *payloadPtr = getchar();
        }
    
        *payloadPtr = '\0';
    
    
        CRCsum = crcsum(payload, charCtr, CRC_INIT);
    
        printf("\nEntered payload is: %s\nThe entered payload size is: %d bytes. ", payload, charCtr);
        printf("\nThe CRC of entered text is: 0x%X ", CRCsum);
    
        //CRCsum2 = calcCollisionPayload(charCtr);
        while((calcCollisionPayload(charCtr)) != CRCsum)
        {
            
          printf("Failure, there has been no collision!\n");
    
        }
    
    
        printf("\nSuccess there has been a collision!");
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    In main(), you need to assign a value to charCtr, since initially it will contain garbage.

    By calling srand() in calcCollisionPayload(), assuming that time() returns the time in seconds, you will be testing only one hash per second. This is because for the duration of each second, srand() will be called with the same value (e.g. srand(2), srand(2), srand(2), srand(2), etc), and rand() will return the same sequence of values, thus testing the same string each time. You just need to call srand() once, at program startup. This will find a collision much faster.

    I'd also advise against naming a variable strlen, as that's the name of a standard function.

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    First, you should maximize your compiler warnings, and ensure the code compiles without warnings

    Code:
    /*
    main.c||In function 'calcCollisionPayload':|
    main.c|59|warning: implicit declaration of function 'time'|
    main.c|74|warning: pointer targets in passing argument 1 of 'crcsum' differ in signedness|
    main.c|46|note: expected 'const unsigned char *' but argument is of type 'char *'|
    main.c||In function 'main':|
    main.c|103|warning: pointer targets in passing argument 1 of 'crcsum' differ in signedness|
    main.c|46|note: expected 'const unsigned char *' but argument is of type 'char *'|
    main.c|84|warning: unused variable 'CRCsum2'|
    main.c|83|warning: unused variable 'i'|
    main.c|81|warning: unused variable 'payload2'|
    ||=== Build finished: 0 errors, 6 warnings ===|
    */
    Code:
    *payloadPtr = getchar();
    while(*payloadPtr!='\n')
    {
      ++charCtr;
      ++payloadPtr;
      *payloadPtr = getchar();
    }
    This is not only an inefficient way to read a string from a user, but there's also no protection against buffer overflow.

    using "fgets()" is much simpler, safer, and doesn't require an extra pointer variable ("payloadPtr") - just the array itself ("payload").

    Also note that on line 95, you increment "charCtr" but this variable is never initialized.

    A few other notes:

    • I'd suggest you implement the CRC calculation as a function, instead of making it a macro.
    • You should only call "srand()" once, near the beginning of the program (i.e. remove the one on line 59)
    • In the argument list of "calcCollisionPayload()", you should avoid naming the variable "strlen", as this is the name of a standard function in string.h


    I don't really want to dig much deeper into this right now, but that's what I saw after a quick perusal.

  4. #4
    Registered User
    Join Date
    Oct 2015
    Location
    Germany
    Posts
    9
    Thank you so much guys for the feedback, note taken on 'strlen' variable name and others too.

    i initialised srand just once this time, let the program run, comes out of the while loop, i get a success on collision,
    but the CRCs i wonder why i get at the end are non-identical

  5. #5
    Registered User
    Join Date
    Oct 2015
    Location
    Germany
    Posts
    9
    Quote Originally Posted by abybaby87 View Post
    Thank you so much guys for the feedback, note taken on 'strlen' variable name and others too.

    i initialised srand just once this time, let the program run, comes out of the while loop, i get a success on collision,
    but the CRCs i wonder why i get at the end are non-identical
    oops replied too soon, right CRC value is the one thats evaluated previously!

    Freakin awesome

  6. #6
    Registered User
    Join Date
    Oct 2015
    Posts
    28
    Well, you could look into the algorithm and see whether you can reverse it. (e.g. generate collisions sequentially from the input of a sum.)

    Otherwise, if you stick with the generate-and-test approach, you could use a counting algorithm with a base of <number of printable characters> and an arbitrary precision, till you find a collision that is not equal to the user's input. This way you can be sure your program actually progresses, instead of the possibility that it may try the same unyielding sequences over and over.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Generating a CRC effectively divides a dividend consisting of the data bits, plus 16 zero bits, by a 17 bit CRC resulting in a 16 bit remainder that is appended to the data. If data + remainder is divided by the CRC, the remainder is zero. Any multiple of the 17 bit CRC xor'ed to the data + remainder will also pass a CRC check. You can try all 65536 possible patterns of 17 bits from 0x10000 to 0x1ffff distributed anywhere in the data, say the least significant bit of the first 17 bytes of the message, and it should find a matching CRC.

    Code:
    #include <memory.h>
    #include <stdio.h>
    #include <stdlib.h>
     
    #define MAX_SIZE 200
    /* CRC calculation macros */
    #define CRC_INIT 0xFFFF
    #define CRC(crcval,newchar) crcval = (crcval >> 8) ^ \
            crc_table[(crcval ^ newchar) & 0x00ff]
     
    static const unsigned short crc_table[256] = {
      0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
      0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
      0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
      0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
      0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
      0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
      0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
      0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
      0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
      0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
      0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
      0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
      0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
      0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
      0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
      0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
      0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
      0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
      0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
      0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
      0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
      0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
      0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
      0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
      0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
      0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
      0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
      0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
      0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
      0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
      0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
      0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
    };
     
    unsigned short crcsum(const unsigned char* message, unsigned long length, unsigned short crc)
    {
      unsigned long i;
     
      for(i = 0; i < length; i++)
        {
          CRC(crc, message[i]);
        }
      return crc;
    }
    
    
    /* function to find the text that causes collision */
    void FindCollision(char payload2[], int charCtr, short CRCsum)
    {
    int i, j, k;
    short CRCsum2;
        if(charCtr < 17)
            return;
        for(k = (1<<16); k < (1<<17); k++){
            j = k;
            for(i = 0; i < 17; i++){
                payload2[i] ^= (j&1);
                j >>= 1;
            }
            CRCsum2= crcsum(payload2, charCtr, CRC_INIT);
            if(CRCsum == CRCsum2){
                printf("\nmatching crc:\n%s\n", payload2);
                break;
            }
            j = k;
            for(i = 0; i < 17; i++){
                payload2[i] ^= (j&1);
                j >>= 1;
            }
        }
    }
     
    int main()
    {
        char payload[MAX_SIZE] = {0};
        char payload2[MAX_SIZE] = {0};
        char  *payloadPtr;
        unsigned int charCtr = 0;
        unsigned short CRCsum;
     
        payloadPtr = payload;
     
        printf("\nEnter a text, 17 bytes long or longer: ");
    
    
        *payloadPtr = getchar();
        while(*payloadPtr!='\n')
        {
          ++charCtr;
          ++payloadPtr;
          *payloadPtr = getchar();
        }
        *payloadPtr = '\0';
    
    
        CRCsum = crcsum(payload, charCtr, CRC_INIT);
     
        printf("\nEntered payload is: %s\nThe entered payload size is: %d bytes. ", payload, charCtr);
        printf("\nThe CRC of entered text is: 0x%X ", CRCsum);
    
    
        memcpy(payload2, payload, charCtr);
    
    
        FindCollision(payload2, charCtr, CRCsum);
    
    
        return 0;
    }
    Last edited by rcgldr; 12-10-2015 at 01:43 AM.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Ran out of time to edit post, change to printf in FindCollision below. Only 4 bits were toggled:

    Example run:

    Code:
    Entered payload is: this is a test of crc
    Alterned payload  : uhis!is a tdst og crc
    Both strings produce a CRC of 0xB01A

    Code:
    /* function to find the text that causes collision */
    void FindCollision(char payload2[], int charCtr, short CRCsum)
    {
    int i, j, k;
    short CRCsum2;
        if(charCtr < 17)
            return;
        for(k = (1<<16); k < (1<<17); k++){
            j = k;
            for(i = 0; i < 17; i++){
                payload2[i] ^= (j&1);
                j >>= 1;
            }
            CRCsum2= crcsum(payload2, charCtr, CRC_INIT);
            if(CRCsum == CRCsum2){
                printf("\nAlterned payload  : %s\n", payload2);
                break;
            }
            j = k;
            for(i = 0; i < 17; i++){
                payload2[i] ^= (j&1);
                j >>= 1;
            }
        }
    }
    Last edited by rcgldr; 12-10-2015 at 02:41 AM.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    In this case, the 17 bit CRC polynomial = 10001000000100001 (binary) = 11021 (hex) = f01f x 0003. This CRC will detect 1 bit, 2 bit, or 3 bit errors in data up to 32767 bits long (4095 bytes). It will fail on some 4 bit patterns. Note that the CRC is a 4 bit pattern. Any bit pattern that is a multiple of this CRC and xor'ed to the data will produce the same CRC. If you raise the 17 bit CRC 10001000000100001 to the 8th power, you get a 17 byte pattern of

    01 00 00 00 01 00 00 00 00 00 00 01 00 00 00 00 01

    You can xor this 17 byte pattern to any 17 bytes in the data and the CRC will be the same.
    Last edited by rcgldr; 12-10-2015 at 03:58 AM.

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Xor'ing the data with the following byte patterns with just 4 bits set each will generate the same CRC:

    Code:
         typedef unsigned char uint8_t;
         uint8_t p1[ 3] = {0x10,0x81,0x10};      // note: 0x01,0x08,0x11 doesn't work
         uint8_t p2[ 5] = {0x01,0x01,0x40,0x00,0x01};
         uint8_t p4[ 9] = {0x01,0x00,0x01,0x00,0x00,0x10,0x00,0x00,0x01};
         uint8_t p8[17] = {0x01,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x01};
    Update to prior posts, the CRC is generated lsb to msb, right shift, so the polynomial is 0x11021 reversed == 0x10811. The code shifts before doing the feedback, so the poly is shifted right one bit for 0x8408. Note that crc_table[0x80] == 0x8408.
    Last edited by rcgldr; 12-10-2015 at 12:48 PM.

  11. #11
    Registered User
    Join Date
    Oct 2015
    Location
    Germany
    Posts
    9
    wow! thanks man! thanks a lot, a lot of potential to climb the learning curve here

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by rcgldr View Post
    Any multiple of the 17 bit CRC xor'ed to the data + remainder will also pass a CRC check.
    The code you're using doesn't redo the CRC with data + CRC appended, so the statement should be: any multiple of the 17 bit CRC xor'ed to the data, and since it's a right shift CRC, the pattern needs to be put in reverse order, so 01 08 11 becomes 11 08 01.

    Code:
    11 08 01
    22 10 02
    33 18 03
    44 20 04
    55 28 05
    66 30 06
    77 38 07
    88 40 08
    99 48 09
    aa 50 0a
    bb 58 0b
    cc 60 0c
    dd 68 0d
    ee 70 0e
    ff 78 0f
    Last edited by rcgldr; 12-13-2015 at 10:16 AM.

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Multiples of 10811, times hex 10, 20, 30, ... f0, byte reversed:

    Code:
    10 81 10
    20 02 21
    30 83 31
    40 04 42
    50 85 52
    60 06 63
    70 87 73
    80 08 84
    90 89 94
    a0 0a a5
    b0 8b b5
    c0 0c c6
    d0 8d d6
    e0 0e e7
    f0 8f f7
    All other patterns that result in the same CRC, can be generated by selecting from the 30 three byte patterns, shifting them (by byte values) and xor'ing them. For example, the previous 5 byte example "divided" down by multiples of 010811:

    Code:
    01 01 40 00 01
    10 81 10
    --------
    11 80 50
    11 08 01
    --------
       88 51 00
       88 40 08
       --------
          11 08 01
    Last edited by rcgldr; 12-13-2015 at 02:28 PM.

  14. #14
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    The math for CRC is binary field math: do the math in binary, and replace add/subtract with xor. The bytes in the data stream are reversed since it's a right shift CRC algorithm.

    Code:
    Multiply example (shown in hex):
    
        010811
      x 010811
    ----------
        010811
       010811
      084088
     000000
    010811
    ---------
    0100400101

    Reverse the bytes for right shift crc: 01 01 40 00 01, which is the 5 byte pattern I posted earlier. Square this again for (010811)^4, reverse the bytes and you get the 9 byte pattern I posted earlier. (010811)^8 byte reversed is the 17 byte pattern I posted earlier.
    Last edited by rcgldr; 12-13-2015 at 03:18 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with collision
    By danishzaidi in forum C++ Programming
    Replies: 4
    Last Post: 01-10-2013, 07:25 PM
  2. collision
    By ichijoji in forum Game Programming
    Replies: 8
    Last Post: 07-13-2004, 07:04 PM
  3. collision
    By lambs4 in forum Game Programming
    Replies: 3
    Last Post: 10-07-2003, 06:42 PM
  4. Box Collision
    By Shiftytitan in forum Game Programming
    Replies: 2
    Last Post: 12-31-2002, 06:19 PM
  5. collision???
    By kas2002 in forum Game Programming
    Replies: 3
    Last Post: 07-08-2002, 05:39 PM

Tags for this Thread