18 Nov
2016
18 Nov
'16
2:40 p.m.
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