任何种子在同一字符串上的 CRC32 哈希冲突

Question

我试图找到种子来哈希最大可能长度的小写字母短字符串而不会发生冲突。我选择 SSE 4.2 CRC32 来简化任务。对于长度为 4、5、6 的种子，达到某个合理的小值时不会发生碰撞（我等不及了）。

#include <bitset>
#include <limits>
#include <iterator>
#include <iostream>

#include <x86intrin.h>

static std::bitset<size_t(std::numeric_limits<uint32_t>::max()) + 1> hashes;

static void findSeed()
{
    uint8_t c[7];
    const auto findCollision = [&] (uint32_t seed)
    {
        std::cout << "seed = " << seed << std::endl;
        hashes.reset();
        for (c[0] = 'a'; c[0] <= 'z'; ++c[0]) {
            uint32_t hash0 = _mm_crc32_u8(~seed, c[0]);
            for (c[1] = 'a'; c[1] <= 'z'; ++c[1]) {
                uint32_t hash1 = _mm_crc32_u8(hash0, c[1]);
                for (c[2] = 'a'; c[2] <= 'z'; ++c[2]) {
                    uint32_t hash2 = _mm_crc32_u8(hash1, c[2]);
                    for (c[3] = 'a'; c[3] <= 'z'; ++c[3]) {
                        uint32_t hash3 = _mm_crc32_u8(hash2, c[3]);
                        for (c[4] = 'a'; c[4] <= 'z'; ++c[4]) {
                            uint32_t hash4 = _mm_crc32_u8(hash3, c[4]);
                            for (c[5] = 'a'; c[5] <= 'z'; ++c[5]) {
                                uint32_t hash5 = _mm_crc32_u8(hash4, c[5]);
                                for (c[6] = 'a'; c[6] <= 'z'; ++c[6]) {
                                    uint32_t hash6 = _mm_crc32_u8(hash5, c[6]);
                                    if (hashes[hash6]) {
                                        std::cerr << "collision at ";
                                        std::copy(std::cbegin(c), std::cend(c), std::ostream_iterator<uint8_t>(std::cerr, ""));
                                        std::cerr << " " << hash6 << '\n';
                                        return;
                                    }
                                    hashes.set(hash6);
                                }
                            }
                        }
                    }
                }
            }
            std::cout << "c[0] = " << c[0] << std::endl;
        }
    };
    for (uint32_t seed = 0; seed != std::numeric_limits<uint32_t>::max(); ++seed) {
        findCollision(seed);
    }
    findCollision(std::numeric_limits<uint32_t>::max());
}

int main()
{
    findSeed();
}

很明显，对于长度为 7 的字符串，不可能找到这样的种子，因为 ('z' - 'a' + 1)^7 = 26^7 = 8 031 810 176 > 4 294 967 296 = size_t(std::numeric_limits<uint32_t>::max()) + 1。但值得注意的是，对于字符串 abfcmbk 和 baabaaa 对于 any 种子，存在第一次碰撞。 hash6 发生碰撞时，不同的种子会有所不同。心里很好奇。

如何解释？

Answer 1

如果CRC(seed,dat)是dat的CRC，使用指定的seed，那么对于任何种子（seed1，seed2），和matching-length对数据（ dat1, dat2)，并给定 CRC(seed1,dat1)，可以通过计算 CRC(seed1, dat1)、CRC(seed1,dat2) 和 CRC(seed2,dat2).[=26= 的异或来计算 CRC(seed2,dat1) ]

这反过来意味着，如果两条数据会为任何特定种子产生相同的 CRC 值，则它们会为每个可能的种子产生相同的值。如果对于任何 seed1，CRC(seed1,dat1a) 等于 CRC(seed1,dat1b)，并且字符串长度相等，那么对于任何其他种子 seed2 和 same-length 数据 dat2、CRC(seed2,dat1a) 将等于 CRC(seed1, dat1a) xor CRC(seed1,dat2) xor CRC(seed2,dat2)，而 CRC(seed2,dat1b) 将等于 CRC(seed1, dat1b) xor CRC(seed1,dat2) xor CRC(seed2,dat2)。由于异或的所有三项都相等，这意味着结果将同样相等。

Answer 2

如另一个答案中所述，CRC 对此无能为力。相反，您应该简单地将六个或更少的小写字母编码为 base 26 32 位整数，并根据字符串的长度进行一些偏移。 n=0 到 6 的 26^n 之和小于 2^32。实际上要少得多，因为它可以用 29 位编码。或者正如 Peter Cordes 评论的那样，在 30 位中有六个 five-bit 字段。

不会发生碰撞。如果有用，您可以对该整数应用 32 位 CRC 来加扰这些位，并且不会再次发生冲突。

如您所见，不可能在 32 位中对七个或更多 lower-case 个字符进行唯一编码。

任何种子在同一字符串上的 CRC32 哈希冲突

CRC32 hash collision on the same string for any seed

c++

hash

crc32

sse

crc