[LEAPSECS] crc-8?

[Rob Seaman]

Hi Poul-Henning,

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’m not finding much on the application of CRCs to such short arrays.  There’s a discussion on CRC-5 for USB in:

	http://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf <http://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf>

It isn’t obvious from first principles whether the class E prefix of four 1-bits might significantly skew the CRC.  Certainly printing out the values doesn’t reveal any obvious problem.  The leap.py comment shows a Hamming distance of 3:

       # bit-     Missed     Total   Miss-Rate
        # errors
        # -------------------------------------
        #  <=1          0        28    0.000000
        #  <=2          0       406    0.000000
        #  <=3          0      3682    0.000000

Which seems good for a short string.  I guess I’m wondering if the search was over all class E addresses, or rather actually over 28-bit messages as stated?  And if the former whether “best performance” included a check that all CRC patterns were more-or-less evenly sampled in the output?

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.

Regarding the matter at hand, not that you asked, but this CRC appears a good choice and there’s no need to investigate other checksums.  (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.  Ditto with some sort of parity bit scheme on the individual numbers.)

If more certainty is required a message digest or other long hash could be computed and broken into four IPv4 values retrievable as something like hash1.leapsec.com <http://hash1.leapsec.com/> to hash4.leapsec.com <http://hash4.leapsec.com/>, but again it isn’t obvious this is worth the trouble.  If a rogue wifi wants to intentionally mess with a DNS version of Bulletin C, they could equally well mess with any hash, even doing their own exhaustive dump of MD5s or whatever if needed.

Rob

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://pairlist6.pair.net/pipermail/leapsecs/attachments/20150123/93f19103/attachment-0001.html>