Over the course of the summer I was able to get a little time to revise and update my CRC data web site. It is still workinprogress, but you'll find a lot more data than was there previously.
New summary tables: http://users.ece.cmu.edu/~koopman/crc/
Recommendations for "good" polynomials with various HD values are completed through 25 bit CRCs, and I'll let the scripts compute away for a few months until eventually the tables are completed through 32 bits. Past 32 bits my search algorithm starts taking a long time to execute so probably will only have samples above that, but we'll see how it goes.
When you look at the data, yellow and blank mean things I'm working on (the color coding helps me keep straight what the scripts are currently working on). Green boxes and "under construction" mean preliminary results that should be OK but aren't doublechecked yet. A significant addition is that I've added automatically generated examples of violations of the HD so you can confirm results for yourself. There is also some doityourself HD computation help here.
If you see a polynomial missing that is published somewhere let me know and I'll add it.
I should mention that Prof. Berthold Gick from University of Applied Sciences, Koblenz, Germany has been independently working in this area and verified many of my results. More importantly, he's pointed out a few typos and other issues that I'm working to correct. I'd like to take this chance to thank him for his efforts. If anyone else notices problems please let me know.
Cyclic Redundancy Codes, Checksums, and related issues for computer system data integrity.
Tuesday, July 28, 2015
Thursday, June 11, 2015
Is HD=1 Useful?
I received an email with a question as to why a HD=1 checksum would ever be useful (referred to on slide 89 of my Sept 2014 slide set on CRCs). The point is that HD=1 means you are not guaranteeing detection of any error, not even 1bit errors. Here's my answer, which I am posting since it might have general interest:
HD=1 (zero errors guaranteed to be detected) means that there is still a
residual capability to randomly detect most errors (all errors except 1
in 2**k for k bits).
If you only need an error detection ratio of a few orders of magnitude this is fine if you have a large CRC.
If you are using a 256 bit cryptographic checksum (which must be assumed to have HD=1) then undetected error probability is 1 in 2**256, which is pretty good. However, a highHD CRC will usually get you better nonmalicious error detection for less computational cost.
Note that any "perfect" pseudorandom number generator will produce HD=1, including cryptographically secure random number generators.
Getting HD>1 means there is a predictable structure in the pseudorandom numbers generated by a CRC in terms of certain outputs being less probable. In fact, for small numbers of bits set in the inputs it is impossible to produce certain outputs with small numbers of bits set, because that would violate the HD. Thus, the outputs are less than perfectly random in a way that is predictable. For security this is bad, because it means the hash function leaks information, and you'd hope a good hash doesn't leak information. But for error detection that's good because it gives you a HD.
If you are using a 256 bit cryptographic checksum (which must be assumed to have HD=1) then undetected error probability is 1 in 2**256, which is pretty good. However, a highHD CRC will usually get you better nonmalicious error detection for less computational cost.
Note that any "perfect" pseudorandom number generator will produce HD=1, including cryptographically secure random number generators.
Getting HD>1 means there is a predictable structure in the pseudorandom numbers generated by a CRC in terms of certain outputs being less probable. In fact, for small numbers of bits set in the inputs it is impossible to produce certain outputs with small numbers of bits set, because that would violate the HD. Thus, the outputs are less than perfectly random in a way that is predictable. For security this is bad, because it means the hash function leaks information, and you'd hope a good hash doesn't leak information. But for error detection that's good because it gives you a HD.
Saturday, April 11, 2015
FAA CRC Report
After an extensive editing and approval process, the FAA has released the report that I did with Kevin Driscoll & Brendan Hall from Honeywell. You can see it here:
Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity
DOT/FAA/TC14/49
http://www.tc.faa.gov/its/worldpac/techrpt/tc1449.pdf
Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity
DOT/FAA/TC14/49
http://www.tc.faa.gov/its/worldpac/techrpt/tc1449.pdf
Subscribe to:
Posts (Atom)
Why To Avoid Hash Algorithms If What You Really Need Is A Checksum
Sometimes we hear that someone plans to use a hash function for fault detection instead of a checksum. This is probably not the best idea, b...

Checksums and CRCs involve a repeated computation over the length of a dataword that accumulates a result to form an FCS value. The accumul...

An Improved Modular Addition Checksum Algorithm Philip Koopman This paper introduces a checksum algorithm that provides a new point in the p...

Here is a video explaining the mechanics of Cyclic Redundancy Check computations, including: An example of the polynomial division approach...