0
$\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$
  • $\begingroup$ CRC's are not hash functions. One can easily find collisions. $\endgroup$ – kelalaka Jun 9 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 at 13:52
2
$\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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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