National Semiconductor 48-bit and 56-bit ECC polynomials

[Paul Koning]

> On Nov 17, 2016, at 5:33 PM, Eric Smith <spacewar at gmail.com> wrote:
> 
> I'm not looking forward to trying to reverse-engineer 48-bit and 56-bit ECC
> polynomials. However, they usually tried to choose polynomials with
> relatively few terms, to minimize the number of XOR gates needed in the
> hardware.
> 
> The common "Glover" 32-bit polynomial was:
>    x^32 + x^28 + x^26 + x^19 + x^17 + x^10 + x^6 + x^2 + x^0
> 
> WD's 56-bit polynomial was
>    x^56 + x^52 + x^50 + x^43 + x^41 + x^34 + x^30 + x^26 + x^24 + x^8 + x^0
> 
> Assuming that National's 56-bit polynomials don't use any fewer terms than
> the 32-bit, nor any more terms than the WD 56-bit, there are not quite 8
> billion possibilities to brute-force. x^n and x^0 are always used, so the
> size of the search space is comb(55,9) + comb(55,8) + comb(55, 7). That
> would take to long to brute-force search in software on a general purpose
> CPU, so I think I'd have to code it for a GPU or FPGA.
> 
> There might be some other short-cuts to reducing the search space, but I
> haven't yet given it a lot of thought.

I don't know enough math to do the work, but a little rubbed off from listening to those who do.

CRC polynomials have special properties, they aren't arbitrary polynomials.  That reduces the number of possible choices dramatically.  In fact, I remember that finding a good one is hard work; a mathematician at DEC who specializes in this stuff spend a big chunk of time (weeks if not months) finding a 64 bit CRC polynomial that was proposed for the HPPI high speed channel standard.  (I don't remember if it was adopted, but some technical details do exist.)

The other key property of CRCs is that they are linear functions.  This is why you can compute the change to the CRC for a given data change easily -- which means that a CRC is never useable as a cryptographic data integrity code, even though WEP abused it that way.  I would assume this means you can deduce the CRC polynomial by straightforward math from a few well chosen test data blocks.  Not sure which ones; perhaps all zeroes plus single bit set at each of <width> different bit offsets.

In other words, exhaustive search, which would be somewhat painful though obviously doable these days, should not be needed.

	paul