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/