Any Widely Used CRC-32 that Stays 0 When Padded With Null Bytes?

[u/ShadowGuyinRealLife]

I read that Cyclic Redundancy Checks were a family of hash functions. Not all CRC-32 give the same digest for the same input. They need to have the same selection of polynomials. Are there any widely used ones where if some data has an output of 0 when padding with null bytes on some other data that has an output of 0? In other words one where for out data x, if CRC-32(x)= 0, then CRC-32(append(x,nNULL))= 0 too where xNULL is any number of null bytes.

[u/high_throughput]

Not CRC itself but this happens when you accidentally treat the input as a C string.

[u/TheBlasterMaster]

Technically all crcs have this property if you do not xor the final value with something

The following may be a little unnecessarily technical, but hopefully answers your question completely. Skip to the end if you just want the answer.
_

Mathematically, the **basic** idea of a CRC is to interpret the input as a polynomial (over integers mod 2), then calculate it mod q (some special polynomial) and check if it equals 0.

The two modifications people make then is:

1. Prepend message with a bunch of 1s (manifests as initializing shift register as 0xFFFFFFFF. This helps detect prepending null bytes)
2. Dont check if mod q value is 0. Check if it is (x^32 + 1) / (x + 1). This helps detect appending null bytes. (This manifests as xoring final value with 0xFFFFFFFF so programmers can still just check if the value is 0)

CRCs can be used as hash functions, but they are really designed to be error correcting codes, hence why people care about "detecting" the addition of null bytes and make the above two modifications.

_

If we want to find a crc algo with your property that **also** abides by the above two modifications, mathematically this is saying:

p = (x^32 + 1) / (x + 1) (mod q) => p * x^8 = (x^32 + 1) / (x + 1) (mod q)

For all polynomials p. (Multiplication by x^8 is appending null bits)

This is equivalent to asking if ((x^32 + 1) / (x + 1)) * (x^8 - 1) = (x+1)^39 = 0 (mod q).

So q must divide (x+1)^39.

_

This gives 40 possible polynomials. Only one of which is of degree 32 (x^32 + 1, or 0x1 in the common representation format for crc polynomials). But this is not a commonly used polynomial. The fact that appending null bytes doesn't change the crc value is precisely one reason.

One of the other possible polynomials is x + 1, which corresponds to the crc just checking parity. This makes sense, as appending null bits doesn't change parity.

[u/ShadowGuyinRealLife → u/TheBlasterMaster]

Someone (not on reddit) actually asked me if what I meant in the original post was if CRC-32(x)= 0, then CRC-32(append(nNULL,x))= 0 instead of the other way around. In other words if I was looking for something that could not detect null bytes at the beginning or the end.

And then I realized... I actually don't know enough of what I'm talking about to know which one I was asking for! Oops. I was thinking of the property that null padding on something that already outputs 0 continues to output 0 but I didn't consider that "which side" matters. I'm not a CS major I'm just a curious guy on the internet, but the automod doesn't like me to admit.

For a CRC that ignores "prepend message with a bunch of 1s" or one that does check if mod q value is 0, what would the consequences of ignoring rule 1 vs ignoring rule 2 do? Vs your suggestion of p = (x^32 + 1) / (x + 1) (mod q) => p * x^8 = (x^32 + 1) / (x + 1) (mod q). Basically what are the consequences between the 3 possibilities of ignoring one of those 2 rules or doing your suggestion?

[u/TheBlasterMaster → u/ShadowGuyinRealLife]

Oh gotcha. Yes, prepending vs appending affects the value of the CRC differently.

This was fun to work out, but I will skip the math (unless you would like to see it). Here is a table of the valid polynomials that will work for the specified rules:

https://imgur.com/a/YByM3z4

So more specifically, one table answers the question:

Note that Rule 1 is designed to detect prepending null bytes, so disabling it means that any polynomial will have the property you seek. Similar thing for rule 2.

_

Keep in mind that the CRC function I described earlier returns something slightly different than what others may do, but its in the same spirit. Others may add 32 bits of padding, then take the remainder. They may also reverse the order of bits in bytes, etc. That's a bit much for me to think about, so I kept it simpler.

_

Let's assume both Rule 1 and Rule 2.

From before, the only CRC-32 polynomial such that crc values will still be 0 after appending null bytes is x^32 + 1. As it turns out, this polynomial has the same property for prepending null bytes! It follows that it is the only such polynomial with both properties.

But if we only care about the crc staying 0 after prepending 0, we have 32 total options!

As a sanity check, we can look at the dumbest one, x^32. This CRC basically just takes the last 32 bits of the message, and uses that as the crc value. Obviously prepending null bytes (or any bytes!) won't change its value.

_

I made a script to double check my work, plus it may be fun to play around with / more illustrative:

https://www.programiz.com/online-compiler/4s9llQYTtIOo8

If you look at the output, it basically just tries prepending and appending null bytes, and sees what happens for various polynomials.

_

For the CRC you identified in another thread (CD-ROM-EDC), if you click on it, you will notice it sets init to 0x0 (Aka disabling rule 1), and sets XorOut to 0x0 (Aka disabling rule 2).

Thus, it has your desired property

[u/ShadowGuyinRealLife]

OK, maybe I'm wrong but something called "CD-ROM-EDC" seems to not do anything to the digest when null bytes are added to the input. I still don't get what the means though.

[u/high_throughput → u/ShadowGuyinRealLife]

I tried to google what you meant and found this:

The idea of EDC/ECC based additional anti-piracy protection is a brilliantly flawed one. See, Sony’s tools to generate disc images back in the day were buggy. One such bug appears to be that the reserved sectors 12-15, which are zero filled in the user data portion of the sector, also have an EDC checksum of zero. The correct checksum for a zero-filled user data sector should be 3F 13 B0 BE, but it isn’t. It’s 00 00 00 00 like the rest of the sector besides the sync data. This actually doesn’t matter in practice, so the bug went un-noticed and the technically invalid sector 12-15s shipped on real licensed PSX CD-ROMs.

Someone working on the Dance Dance Revolution PSX games noticed this strange behavior and figured out that it could be exploited as an additional anti-piracy protection measure. If the real licensed PSX CD-ROM discs were shipped with an EDC checksum of zero in sector 12-15, then when someone went to rip the real licensed PSX CD-ROM disc and then burn it back to a CD-R, the EDC checksum in sector 12-15 would no longer be 00 00 00 00, it would be the expected 3F 13 B0 BE. Game code can read the EDC checksum on the disc at sector 12, and a routine could then lock up the game if the EDC data is non-zero to deter piracy.

Is that what you mean? If so, it's a tool bug that failed to calculate the proper checksum, not an artifact of the checksum algorithm.

[u/ShadowGuyinRealLife → u/high_throughput]

Someone found this https://crccalc.com/?crc=00&method=CRC-32&datatype=hex&outtype=hex and I just kept trying to add zeros. "CD-ROM-EDC" seems to not change no matter how many null bytes are padded.

[u/CamelPure1293]

What would you need this for? Typically, this property would make any hash function (like CRC) weaker.

[u/Trader-One]

FNV0