[LEAPSECS] crc-8?

[Poul-Henning Kamp]

--------
In message <1EDF02FF-9589-4413-8C09-710B179BE461 at noao.edu>, Rob Seaman writes:
>

>Getting off topic a bit, the comment in leap.py says:
>
>        # I chose 0xcf after an exhaustive search for best performance
>        # on 28 bit messages.
>
>However, crc8() is being called on the entire first three bytes so 
>24-bits on encoding and 32-bits on decoding.  I=E2=80=99m not finding 
>much on the application of CRCs to such short arrays.  There=E2=80=99s a 
>discussion on CRC-5 for USB in:

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.

>I guess I'm wondering if the search was over all class E addresses,
>or rather actually over 28-bit messages as stated?

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.

>The fact that you felt the need to do this work yourself suggests you 
>could write this up as a useful brief paper, if only direct-to-arXiv.

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.

>(I suppose an explicit numeric check byte might be an alternative, 
>calculated from special knowledge of the encoded values, but this is 
>likely not worth the trouble.)

Not only that, it would perform worse than the CRC.

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.

>If more certainty is required a message digest or other long hash could 
>be computed and broken into four IPv4 values retrievable as something 

That would undoubtedly be overkill.

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


-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
phk at FreeBSD.ORG         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.