CRC背后的故事

本文为翻译文章，笔者翻译水平有限，原文详见Understanding CRC

http://www.secmem.org/blog/2020/08/19/Understanding-CRC/

介绍

去年的时候，在一些CTF赛事中出现了与CRC相关的问题。问题的关键就是找到一个x使得flag{x}的CRC值为x。在解题的过程中，我们发现大多数人并不了解CRC的性质。实际在网络应用中，通常使用CRC作为冗余校验码，但是也仅限于使用现有的函数接口计算文件或数据的CRC值，而没有深入了解CRC的性质。

我对CRC的本质也不太理解，于是我重新学习并写下了这篇文章。

背景知识

Finite Field

有限域的更多性质详见[有限域]:https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E5%9F%9F

CRC

unsigned?int?crc32b(unsigned?char?*message)?{
???int?i,?j;
???unsigned?int?byte,?crc,?mask;

???i?=?0;
???crc?=?0xFFFFFFFF;
???while?(message[i]?!=?0)?{
??????byte?=?message[i];????????????//?Get?next?byte.
??????crc?=?crc?^?byte;
??????for?(j?=?7;?j?>=?0;?j--)?{????//?Do?eight?times.
?????????mask?=?-(crc?&?1);
?????????crc?=?(crc?>>?1)?^?(0xEDB88320?&?mask);
??????}
??????i?=?i?+?1;
???}
???return?~crc;
}

Playing With CRC

poly?=?0x104C11DB7

def?normalize(x):
????while?x.bit_length()?>?32:
????????x?^=?poly?<<?(x.bit_length()?-?33)
????return?x

def?mult(x,?y):
????res?=?0
????for?i?in?range(32):
????????if?y?&?(1?<<?i)?!=?0:
????????????res?^=?(x?<<?i)
????return?normalize(res)

def?bytes_to_gf32(s):
????val?=?0
????for?c?in?s:
????????rev?=?int(format(c,?'08b')[::-1],?2)
????????val?=?(val?<<?8)?|?rev
????return?normalize(val)

def?crc32(s):
????l?=?len(s)
????m?=?bytes_to_gf32(s)
????return?normalize((m?<<?32)?^?(0xFFFFFFFF?<<?(8?*?l))?^?0xFFFFFFFF)

def?crc32b(message):
????crc?=?0xFFFFFFFF
????for?i?in?range(len(message)):
????????byte?=?message[i]
????????crc?=?crc?^?byte
????????for?j?in?range(8):
????????????if?crc?&?1:
????????????????crc?=?(crc?>>?1)?^?0xEDB88320
????????????else:
????????????????crc?>>=?1
????return?crc?^?0xFFFFFFFF

message?=?b"test"

crc1?=?crc32(message)
crc2?=?crc32b(message)

print(format(crc1,?'032b'))
print(format(crc2,?'032b')[::-1])

> python .\test.py
00110000011111101111111000011011
00110000011111101111111000011011

代码：

def?pow(x,?y):
????if?y?==?0:
????????return?1
????elif?y?==?1:
????????return?x
????else:
????????res?=?pow(x,?y?//?2)
????????res?=?mult(res,?res)
????????if?y?&?1:
????????????res?=?mult(res,?x)
????????return?res

def?inverse(x):
????return?pow(x,?2?**?32?-?2)

const?=?crc32(b"flag{\0\0\0\0}")
coef?=?normalize((1?<<?40)?^?1)
x?=?mult(const,?inverse(coef))

print(format(x,?'032b')[::-1])

#?01110011?10011011?01000101?00000111

#?????0x73?????0x9b?????0x45?????0x07

print(hex(x))
print(hex(bytes_to_gf32(b"\x07\x45\x9b\x73")))
print(hex(crc32(b"flag{\x07\x45\x9b\x73}")))
print(hex(crc32b(b"flag{\x07\x45\x9b\x73}")))

输出结果为：

python .\test.py
01110011100110110100010100000111
0xe0a2d9ce
0xe0a2d9ce
0xe0a2d9ce
0x739b4507

于是预期的x为\x07\x45\x9b\x73

总结

我们花了一些时间来了解CRC的数学基础，并深入了解了CRC,并找出了某些字符串的CRC值等于字符串自身情况。除了CRC以外，有限域本身也是一个经常在其他地方使用的概念，因此希望在以后出现混淆的时候可以参考这篇文章。

参考资料

1. https://en.wikipedia.org/wiki/Finite_field
2. https://en.wikipedia.org/wiki/Cyclic_redundancy_check
3. https://stackoverflow.com/questions/21001659/crc32-algorithm-implementation-in-c-without-a-look-up-table-and-with-a-public-li
4. https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E5%9F%9F

https://github.com/ChaMd5Team/Venom-WP/blob/main/CRC背后的故事.pdf

查看以下链接或点击文末阅读原文

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/