Wow someone went and calculated the best polynomials to use for CRC and they don't seem to match up with the polynomials most commonly used.

users.ece.cmu.edu/~koopman/crc

@dredmorbius So there's a thing called Cyclic Redundancy Check (CRC) that's used as a hash to correct errors in data. It's used in a bunch of internet protocols and file types because it's simple to calculate and pretty effective at detecting errors. There's a lot of comp-sci in its origins which is why the magic number you use is called a “polynomial” but calculating it is easy.

For reasons of “math I don't understand” some initial polynomials can detect more errors—with a trade-off of having a smaller maximum amount of data they can detect errors in. In the link in my previous post they calculated the best polynomials for the number of errors you want to be able to detect and the size of data you want, and none of them seem to match up with the most common polynomials everyone uses.

@nytpu Do we know where the "most common polynomials everyone uses" come from?

I know that in the case of numerous crypto algos, there've been "suggestions" (typically through US NIST) for some key values which on further examination seem to be workfactor reduction mechanisms originating from the US intelligence community (almost always the NSA).

One consequential result is that NIST's suggestions on crypto algos are very poorly received these days.

@dredmorbius By “most common polynomial” I'm referring specifically to CRC-32 only, not any other algorithm or even any other CRC size. The most common CRC-32 polynomial (sometimes called “CRC-32-IEEE” to distinguish it) seemed to have been calculated in 1975 and was used in ethernet so everybody figured they should use that one since it's the most well-known.

The research paper on the calculation is public so you don't have to worry about some security backdoor, plus CRC is used as accidental error detection and not as a defense against a malicious actor, you'd use a real cryptographic hash for that.

It looks like one of the “optimal” polynomials is used in the CRC-32C specification which is becoming more commonly used.

On your magic numbers being suggested, most contemporary hashing algorithms now use a “Nothing Up My Sleeve” magic number

Follow

@alcinnz @dredmorbius 3blue1brown has a good video on Hamming codes in particular which provides a good base for learning about more complex error detecting/correcting codes: invidious.silkky.cloud/watch?v & invidious.silkky.cloud/watch?v

@nytpu @alcinnz Those videos are really excellent descriptions and explanations of Hamming Codes.

Thanks both of you!

Sign in to participate in the conversation
tilde.zone

masto instance for the tildeverse