In 1984 I wrote a paper for the company I was working for at the time. It was in support of a new test instrument the company was about to release. The paper was published in the IEEE Instrumentation and Measurement Technology Conference Proceedings. I was scheduled to go to Long Beach California and present the paper during the conference January 17-18, 1984. But the company cancelled the release of the product and I did not attend the conference.
Before there was the World Wide Web there were online services you could subscribe to, dial up with a modem (1200 baud rocked!) and do searches of periodicals, journals, papers, etc. This is what one of those services, Dialog, had in their records in July of 1984:
A scan of the paper is here (click on each to get a readable version):
Today, over 30 years later, there is probably very little of the paper which is applicable to modern test equipment. But something I learned while writing the paper is something I still occasionally “put people in their place” with.
Unless you know the something about the error statistics of whatever digital system you are trying to test then it almost doesn’t matter which checksum, hash, or CRC you use for error detection. In fact, surprising to nearly everyone, if you assume that all errors are equally likely, then you can just pick the last (or first, whatever) 256 bits of a digital message and have just as good error detection as any other 256-bit hash. Or if you are using a 16-bit checksum then you might as well use the last (or first, whatever) 16 bits of the message.
It all boils down to the assumptions about the types of errors in the message. You, whether you realize it or not, make lots of assumptions about the types of errors in a digital message. For example you assume it is very unlikely, compared to other types of errors, that every 17th bit will be inverted. Or that every DWORD will be XORed with 0xBAADF00D. But the assumption, “every error is equally likely” means the math for detecting those errors will arrive at an interesting conclusion:
For a message N bits long there are 2N-1 possible errors. Any hash, checksum, etc., M bits long can only have 2M different states. One of those states represents a valid hash/checksum/etc. The other 2M – 1 represent detected errors.
If all errors are equally likely then those 2N-1 possible errors are equally mapped into each of the 2M possible states of the hash. It will only detect a fraction of those errors. The fraction will be (2M-1)/(2M). Or stated differently the fraction of errors which map into the valid hash is 1/2M. For a N bit message (2N-1)/2M errors are missed. For 2N >> 1 (all real world cases) this is essentially equal to 2N/2M or 2(N – M).
If you use the last M bits of the message it will detect all 2M-1 errors in the last M bits and miss 2(N-M) errors in the previous part of the message.
Hence it does not matter if you use a M bit hash of the entire message or the last M bits of the message. The same number of errors will be escape detection.
In “real life”, not all errors are equally likely. This is particularly true when you are trying to detect messages which have been altered by an attacker. But there are many situations where people spend way too much effort trying to determine the “best” hash to use when just using the first/last/whatever M bits or a simple checksum of M bits will work just as well as the latest NSA blessed crypto hash and consume far less computational resources.
I find this counter intuitive and very interesting. I suspect it says more about our intuition than anything.
Like this:
Like Loading...
