I received an e-mail 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 1-bit 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 high-HD CRC will usually get you better non-malicious error detection for less computational cost.
Note that any "perfect" pseudo-random number generator will produce HD=1, including cryptographically secure random number generators.
Getting HD>1 means there is a predictable structure in the pseudo-random 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 high-HD CRC will usually get you better non-malicious error detection for less computational cost.
Note that any "perfect" pseudo-random number generator will produce HD=1, including cryptographically secure random number generators.
Getting HD>1 means there is a predictable structure in the pseudo-random 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.
No comments:
Post a Comment