CRC32 calculation with CRC hash at the beginning of a message in C

I need to calculate the CRC of the message and place it at the beginning of this message so that the final CRC of the message with the "added" patch bytes is 0. I was able to do this very easily with a few articles, but not for my specific parameters. The point is that I have to use the given CRC32 algorithm, which calculates the CRC of the memory block, but I do not have this "reverse" algorithm, which calculates these 4 bytes of the patch / "kind of CRC". Parameters of this CRC32 algorithm:

  • Polynomial: 0x04C11DB7
  • Endianess: big-endian
  • Initial value: 0xFFFFFFFF
  • Reflected: false
  • XOR out with: 0L
  • Test thread: 0x0123, 0x4567, 0x89AB, 0xCDEF leads to CRC = 0x612793C3

Code for calculating CRC (nibble, table based, I hope the datatype definitions are self-explanatory):

uint32 crc32tab(uint16* data, uint32 len, uint32 crc)
{
    uint8 nibble;
    int i;
    while(len--)
    {
        for(i = 3; i >= 0; i--)
        {
            nibble = (*data >> i*4) & 0x0F;
            crc = ((crc << 4) | nibble) ^ tab[crc >> 28];
        }
        data++;
    }

    return crc;
}

      

A table is needed (I have to point out that the short [16] table should contain every 16th element from the large table [256], but this table actually contains the first 16 elements, but that's how it was provided to me):

static const uint32 tab[16]=
{
    0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
    0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
    0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
    0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};  

      

I changed the code so it doesn't take long, but the functionality remains the same. The problem is that this forward CRC calculation is more like a reverse / reverse CRC-calc.
I spent almost a week trying to find the correct combination of polynomials / algorithms / tables, but no luck. If that helps, I came up with a bitwise algorithm that matches the above table code, although it wasn't that hard:

uint32 crc32(uint16* data, uint32 len, uint32 crc)
{
    uint32 i;
    while(len--)
    {
        for(i = 0; i < 16; i++)
        {
            // #define POLY 0x04C11DB7
            crc = (crc << 1) ^ (((crc ^ *data) & 0x80000000) ? POLY : 0);
        }
        crc ^= *data++;
    }

    return crc;
}

      

Results are expected here - the first 2 16-bit words make the required unknown CRC, and the rest make the data itself known (by feeding these examples to the provided algorithm, the result is 0).

{0x3288, 0xD244, 0xCDEF, 0x89AB, 0x4567, 0x0123}
{0xC704, 0xDD7B, 0x0000} - append as many zeros as you like, the result is the same
{0xCEBD, 0x1ADD, 0xFFFF}
{0x81AB, 0xB932, 0xFFFF, 0xFFFF}
{0x0857, 0x0465, 0x0000, 0x0123}
{0x1583, 0xD959, 0x0123}
   ^        ^
   |        |
   unknown bytes that I need to calculate

      

I think testing this for 0xFFFF or 0x0000 words is convenient, because the direction of computation and endianess is not important (hopefully: D). So be careful to use other test bytes, because the direction of computation is quite tricky: D. Also you can see that by feeding only zeros to the algorithm (both forward and backward) the result is a so called remainder (0xC704DD7B), which can be helpful.

So ... I wrote at least 10 different functions (bites, tables, combination of polynomials, etc.) trying to solve this, but no luck. I give you the function that I have put my hopes into. This is the "reverse" table management algorithm above, with a different table of course. The problem is that the only correct CRC I get from this is with the whole message 0s, and it's not that unexpected. I also wrote a reverse implementation of the bit algorithm (backshifts, etc.), but that only correctly returns the first byte.
Below is a pointer to a table, the data pointer should point to the last element of the message, and the crc input should be requested by crc (0s for the whole message, or you can use another approach), which is the last 4 bytes of the CRC message you are looking for:Calculating the initial CRC value instead of adding the CRC to the payload ):

uint32 crc32tabrev(uint16* data, uint32 len, uint32 crc)
{
    uint8 nibble;
    int i;
    while(len--)
    {
        for(i = 0; i < 4; i++)
        {
            nibble = (*data >> i*4) & 0x0F;
            crc = (crc >> 4) ^ revtab[((crc ^ nibble) & 0x0F)];
        }
        data--;
     }

     return reverse(crc); //reverse() flips all bits around center (MSB <-> LSB ...) 
}

      

The table that I hope is "selected":

static const uint32 revtab[16]=
{
    0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
    0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
    0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
    0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
};

      

As you can see, this algorithm has some perks that make me run in circles, and I think I might be on the right track, but I am missing something. Hope another pair of eyes sees what I can't. I apologize for the long post (no potatoes: D), but I think this whole explanation was needed. Thank you in advance for your understanding or advice.

+3


source to share


2 answers


Well, a few hours after my question, someone whose name I don't remember posted an answer to my question, which turned out to be correct. Somehow this answer was completely deleted, I don't know why or who did it, but I would like to thank this person, and in case you see this, please post your answer again and I will delete it. But for other users, here's his answer that worked for me, thanks again, mysterious (unfortunately I can't reproduce his notes and suggestions well enough, just the code itself):

Edit: The original answer came from user samgak , so it stays here until he posts his answer.

Reverse CRC algorithm:

uint32 revcrc32(uint16* data, uint32 len, uint32 crc)
{
     uint32 i;
     data += len - 1;

     while(len--)
     {
         crc ^= *data--;
         for(i = 0; i < 16; i++)
         {
             uint32 crc1 = ((crc ^ POLY) >> 1) | 0x80000000;
             uint32 crc2 = crc >> 1;
             if(((crc1 << 1) ^ (((crc1 ^ *data) & 0x80000000) ? POLY : 0)) == crc)
                 crc = crc1;
             else if(((crc2 << 1) ^ (((crc2 ^ *data) & 0x80000000) ? POLY : 0)) == crc)
                 crc = crc2;
         }
     }
     return crc;
}

      



Find patches bytes:

#define CRC_OF_ZERO 0xb7647d
void bruteforcecrc32(uint32 targetcrc)
{
    // compute prefixes:
    uint16 j;
    for(j = 0; j <= 0xffff; j++)
    {
        uint32 crc = revcrc32(&j, 1, targetcrc);
        if((crc >> 16) == (CRC_OF_ZERO >> 16))
        {
           printf("prefixes: %04lX %04lX\n", (crc ^ CRC_OF_ZERO) & 0xffff, (uint32)j);
           return;
        }
    }
}

      

Using:

uint16 test[] = {0x0123, 0x4567, 0x89AB, 0xCDEF};  // prefix should be 0x0CD8236A

bruteforcecrc32(revcrc32(test, 4, 0L));

      

0


source


I am in charge of your CRC specification: CRC-32 / MPEG-2 . I will have to ignore your attempts to calculate this CRC as they are incorrect.

Anyway, to answer your question, I happen to write a program that solves this problem. It's called spoof.c

. It calculates very quickly which bits change in the message to get the desired CRC. It does this in the order of log (n) time, where n is the length of the message. Here's an example:

Take a nine-byte message 123456789

(these are numbers represented in ASCII). We'll add it with four null bytes, which we'll modify to get the desired CRC at the end. Then the message in hexadecimal format 00 00 00 00 31 32 33 34 35 36 37 38 39

. We now compute the CRC-32 / MPEG-2 for this message. We get 373c5870

.

We now start spoof

with this input, which is the length of the CRC in bits, the fact that it is not reflected, the polynomial, the CRC just calculated, the length of the message in bytes, and all 32 bits of the location in the first four bytes (which allows spoof

modification) :

32 0 04C11DB7
373c5870 13
0 0 1 2 3 4 5 6 7 
1 0 1 2 3 4 5 6 7
2 0 1 2 3 4 5 6 7
3 0 1 2 3 4 5 6 7

      

It gives this output with what bits in those first four bytes:

invert these bits in the sequence:
offset bit
     0 1
     0 2
     0 4
     0 5
     0 6
     1 0
     1 2
     1 5
     1 7
     2 0
     2 2
     2 5
     2 6
     2 7
     3 0
     3 1
     3 2
     3 4
     3 5
     3 7

      



Then we set the first four bytes: 76 a5 e5 b7

. Then we test by calculating the CRC-32 / MPEG-2 messages 76 a5 e5 b7 31 32 33 34 35 36 37 38 39

and get the 00000000

desired result.

You can adapt spoof.c

to your application.

Here is an example that correctly calculates CRC-32 / MPEG-2 on a byte stream using a bit-wise algorithm:

uint32_t crc32m(uint32_t crc, const unsigned char *buf, size_t len)
{
    int k;

    while (len--) {
        crc ^= (uint32_t)(*buf++) << 24;
        for (k = 0; k < 8; k++)
            crc = crc & 0x80000000 ? (crc << 1) ^ 0x04c11db7 : crc << 1;
    }
    return crc;
}

      

and with an algorithm using the algorithm using the table in the question (which is correct):

uint32_t crc_table[] = {
    0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
    0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
    0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
    0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};

uint32_t crc32m_nyb(uint32_t crc, const unsigned char *buf, size_t len)
{
    while (len--) {
        crc ^= (uint32_t)(*buf++) << 24;
        crc = (crc << 4) ^ crc_table[crc >> 28];
        crc = (crc << 4) ^ crc_table[crc >> 28];
    }
    return crc;
}

      

In both cases, the original CRC must be 0xffffffff

.

+5


source







All Articles