LSt*_*ing 4 c crc32 reverse-engineering
我需要计算消息的CRC并将其放在此消息的开头,以便带有"prepended"补丁字节的消息的最终CRC等于0.我能够在几篇文章的帮助下很容易地做到这一点,但不是我的具体参数.问题是我必须使用给定的CRC32算法来计算内存块的CRC,但是我没有那个"反向"算法来计算那4个补丁字节/'种类的CRC'.给定CRC32算法的参数是:
计算CRC的代码(半字节,表驱动,我希望数据类型定义不言自明):
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;
}
需要的表是(我认为short [16]表应该包含大[256]表中的每个第16个元素,但是这个表实际上包含了前 16个元素,但这就是它提供给我的方式):
static const uint32 tab[16]=
{
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
我修改了代码所以它不是很长,但功能保持不变.问题是这个正向CRC计算看起来更像是后向/反向CRC计算.
我花了将近一个星期的时间试图找出正确的多项式/算法/表组合,但没有运气.如果它有帮助,我想出了与上面的表驱动代码相对应的逐位算法,尽管毕竟不是那么难:
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;
}
这是预期的结果 - 前2个16位字构成所需的未知CRC,其余为已知数据本身(通过将这些示例提供给提供的算法,结果为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
我认为在0xFFFF或0x0000字上测试这个很方便,因为计算和结束的方向并不重要(我希望:D).所以要小心使用其他测试字节,因为计算方向非常狡猾:D.您还可以看到,通过向算法(向前和向后)仅提供零,结果是所谓的残差(0xC704DD7B),这可能会有所帮助.
所以...我写了至少10个不同的函数(咬合,表,多项式的组合等)试图解决这个问题,但没有运气.我在这里给你的功能,我寄予厚望.它是上面表格驱动的"逆转"算法,当然也有不同的表格.问题是我从中得到的唯一正确的CRC是全0的消息,并不是那么出乎意料.我也编写了逐位算法的反向实现(反向移位等),但是只返回正确的第一个字节.
这是表驱动的,指向数据的指针应该指向消息的最后一个元素和crc输入应该是请求的crc(整个消息的0或者你可以采取另一种方法 - 消息的最后4个字节是你正在寻找的CRC:计算CRC初始值而不是将CRC附加到有效载荷):
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 ...)
}
该表,我希望是"被选中的":
static const uint32 revtab[16]=
{
0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
};
正如你所看到的,这个算法有一些额外的好处,让我在圈子里运行,我想我可能在正确的轨道上,但我错过了一些东西.我希望额外的一双眼睛会看到我不能的东西.我很遗憾这篇长篇文章(没有马铃薯:D),但我认为所有这些解释都是必要的.提前感谢您的见解或建议.
我将回答您的CRC规范,即CRC-32/MPEG-2的规范.我将不得不忽略您计算CRC的尝试,因为它们是不正确的.
无论如何,为了回答你的问题,我碰巧编写了一个解决这个问题的程序.它被称为spoof.c.它可以非常快速地计算消息中要更改的位以获得所需的CRC.它按log(n)的顺序执行此操作,其中n是消息的长度.这是一个例子:
我们取9个字节的消息123456789(用ASCII表示的那些数字).我们将在它前面添加四个零字节,我们将更改它以在结束时获得所需的CRC.然后是十六进制的消息:00 00 00 00 31 32 33 34 35 36 37 38 39.现在我们为该消息计算CRC-32/MPEG-2.我们得到了373c5870.
现在我们运行spoof这个输入,它是以位为单位的CRC长度,未反映的事实,多项式,我们刚刚计算的CRC,以字节为单位的消息长度,以及前四个字节中的所有32位位置(这是我们允许spoof改变的):
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
它为此输出提供前四个字节中要设置的位:
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
然后我们将前四个字节设置为:76 a5 e5 b7.然后,我们通过计算消息的CRC-32/MPEG-2进行测试,76 a5 e5 b7 31 32 33 34 35 36 37 38 39得到00000000所需的结果.
您可以适应spoof.c您的应用程序.
下面是一个使用逐位算法正确计算字节流上的CRC-32/MPEG-2的示例:
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;
}
使用问题中的表(这是正确的)使用nybble-wise算法:
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;
}
在这两种情况下,初始CRC必须是0xffffffff.
好吧，在我提出问题几个小时后，一个我不记得名字的人发布了我问题的答案，结果证明是正确的。不知何故，这个答案被完全删除了，我不知道为什么或是谁干的，但我要感谢这个人，如果你会看到这个，请再次发布你的答案，我会删除这个答案。但对于其他用户来说，这是他对我有用的答案，再次感谢你，神秘的答案（不幸的是，我无法很好地复制他的注释和建议，只能复制代码本身）：
编辑：最初的答案来自用户samgak，所以这会留在这里，直到他发布他的答案。
反向CRC算法：
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;
}
查找补丁字节：
#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;
}
}
}
用法：
uint16 test[] = {0x0123, 0x4567, 0x89AB, 0xCDEF}; // prefix should be 0x0CD8236A
bruteforcecrc32(revcrc32(test, 4, 0L));