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;
}

---

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.

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.

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 :(

Quote:

---

Originally Posted by abybaby87

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! :D

Freakin awesome :D :D :D

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.

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;
}

---

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;
        }
    }
}

---

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.

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.

wow! thanks man! thanks a lot, a lot of potential to climb the learning curve here :)

Quote:

---

Originally Posted by rcgldr

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

---

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

---

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.