c++ - 任何种子在同一字符串上的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，任何种子都首先发生冲突。发生冲突时，不同种子的 hash6不同。我心里很好奇。
怎么解释呢？

Answer 1

如果CRC(seed,dat)是dat的CRC，使用指定的seed，则对于任何种子(seed1，seed2)和长度匹配的数据对(dat1，dat2)，并给定CRC(seed1，dat1)，可以通过以下方式计算CRC(seed2,dat1):计算CRC(seed1, dat1)，CRC(seed1,dat2)和CRC(seed2,dat2)的异或。
这反过来意味着，如果两个数据对任何特定种子将产生相同的CRC值，则它们对每个可能的种子将产生相同的值。如果对于任何seed1，CRC(seed1,dat1a)等于CRC(seed1,dat1b)，并且字符串的长度相等，那么对于任何其他种子seed2和相同长度的数据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)。由于xor的所有三个项都相等，这意味着结果也将相等。