4
$\begingroup$

Is CRC32C (any) better than CRC32(B)?

I read that CRC32C (alias Castagnoli) is better than CRC32 (sometimes referred as CRC32B) in detecting errors but what that exactly means and how to check it didn't mention. I know they use different polynomial but that alone doesn't explain that. So I started to search a bit more and found nothing really. Only one post on Intel's forum where the guy from Intel says it's been chosen because "this polynomial has nice mathematical properties". I immediately wanted to ask "Since when 'niceness' is a criterion to choose one algorithm (here - polynomial) over the other?". Anyway...

Inspired by this topic I created my own test and checked collisions in English dictionary (from here, note there are two repetitions: "OUTSOURCING", "OUTSOURCINGS"). I used my author's program that hashes all entries and compares these hashes with each other. I also used lowercased, capitalized and first-letter capitalized words. After optimization it gives (n*(n-1)/2) comparisons. The results I got are somewhat characteristic: ('_32a' means first 32 bits of hash ( memcpy(hash32, hash, 4); ), '_lo32b' means low 32 bits of hash ( (uint32_t)hash64; ); (polynomials taken from wikipedia)

| hash         | collisions | polynomial |
+--------------+------------+------------+
| crc32b       |     44     | 0x04C11DB7 |
| crc32c       |     62     | 0x1EDC6F41 |
| crc32k       |     36     | 0x741B8CD7 |
| crc32q       |     54     | 0x814141AB |
| fnv1a        |     51     |      -     |
| md5_32a      |     45     |      -     |
| sha1_32a     |     44     |      -     |
| wyhash_lo32b |     47     |      -     |
| xxh32        |     49     |      -     |
| xxh64        |      0     |      -     |
| xxh64_lo32b  |     51     |      -     |
+--------------+------------+------------+

As you can see - 32 bit hashes are prone to collisions, and good hashes have similar chance of collision in set of this size equal to ~45. All but CRC32C... Seems like CRC32C has 40%+ more collisions than CRC32B which is significant, comparing that other hashes, including cryptographic, have around 45 like CRC32B. Is it better? Somehow I don't see that.

I also checked how they compare in smhasher as it's designed to test hashed and both CRC32B and CRC32C fail miserably on the same tests in the same fashion (collective set of those tests here). Is it better? Somehow I don't see that.

I know this crude test is not the best way of testing but smhasher shown the same, and even more of it, so is CRC32C any better than CRC32(B)?

$\endgroup$
3
  • $\begingroup$ CRC's are not hash functions. One can easily find collisions. $\endgroup$
    – kelalaka
    Jun 9, 2020 at 7:00
  • $\begingroup$ True, they are not hashes but collisions are "as easily" (in fact as difficultly) found with other CRCs or hashes. There are better and worse CRCs (depending on polynomial). I just added K and Q polynomials and they clearly show difference between them. Every collision mean there is an error that is omitted so collisions (or lack of them) do show CRC/checksum/hash quality. $\endgroup$
    – tansy
    Jun 9, 2020 at 13:52
  • $\begingroup$ The most (IMHO) important difference is speed (crc32b ~2.67 bytes/cycle vs crc32c 8 bytes/cycle), reference: stackoverflow.com/a/26612761/1450967 $\endgroup$
    – ggrandes
    Dec 30, 2023 at 8:13

2 Answers 2

3
$\begingroup$

What does «CRC32C (alias Castagnoli) is better than CRC32B in detecting errors» exactly means?

Multiple metrics are used in the original article. One is: when we restrict to messages of equal length differing by at most some low number of bits (e.g. 4 bit), CRC32C gives certainty of error detection up to a larger message length than CRC32 does. This is confirmed independently. Variations consider the probability of error detection for messages slightly above the threshold of perfect detection on either the message length, or number of bits in error.

I'm not sure that the 66 vs 44 collisions found in the question is statistically significant, or the cause of that if it is significant.

$\endgroup$
1
$\begingroup$

In the case of LibTorrent, they picked CRC32C due to the following rationale

it is a fast function

produces well distributed results

there is no need for the hash function to be one-way (the input set is so small that any hash function could be reversed).

CRC32C (Castagnoli) is supported in hardware by SSE 4.2, which can significantly speed up computation, The reason to use CRC32C instead of the CRC32 implemented by zlib is that Intel CPUs have hardware support for the CRC32C calculations. The input being exactly 4 bytes is also deliberate, to make it fit in a single instruction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.