[LEAPSECS] crc-8?

Rob Seaman seaman at noao.edu
Fri Jan 23 19:09:49 EST 2015

As with you and Warner, just making sure we’re on the same page.

> On Jan 23, 2015, at 2:05 PM, Poul-Henning Kamp <phk at phk.freebsd.dk> wrote:
> There is a separate identity test on the first four bits, so in
> relation to the CRC they just modify the initial state.


> The actual message, including CRC is therefore 28 bits.

And 20 bits without.  However we count it, I’ve now looped over all 10^20 three-byte class E options and verified that each of the 256 CRC outputs appear 4096 times.

> With CRC the actual message does not matter, only which and how many
> bit positions where flipped, so you only have to test the 28 cases
> of one bit flipped, 28*27 cases of two bits flipped etc.  It's
> quite manageable, you can do all possible 8-bit CRC in a matter
> of minutes for this message size.

Indeed.  A few tens of seconds on my aging iMac.  

The actual message can matter if the data are correlated in some fashion, i.e., the detectability of systematic errors imposed on the message.  I think we’re ok unless lying DNS resolvers preferentially tend to lie about the same IPv4 ranges, thus hammering only a subset of the CRC outputs.

> See:
>   http://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
> Amongst other things they showed that pretty much any and all CRCs
> ever written into a standard document were suboptimal.

Good to see you’re pointing me to the same reference I located.  There does seem likely to be more to say about CRCs since that was written in 2004.

> And don't forget that once the CRC is satisfied, there are still other
> checks which can be performed, for instance that the numbered month
> is not known to be in the past.

Indeed, was thinking of just that (for the primary use case).

> The CRC protects against the common risks (lying DNS resolvers), we
> don't need more than that.



More information about the LEAPSECS mailing list