15 Nov
2016
15 Nov
'16
7:19 p.m.
Has anyone determined what 48-bit and 56-bit ECC polynomials are used by
the National Semiconductor hard disk controllers? The DP8496/97 allows
choice of hard-wired 16-bit CRC, or 32-bit, 48-bit, or 56-bit ECC. The
32-bit ECC is a common polynomial known as the Glover polynomial, and it's
the same one used by WD and others. However, National was apparently
extremely proud of the 48-bit and 56-bit polynomials they chose, and the
data sheets say that they require a license agreement with National.
The more common DP8466 supports 32-bit 48-bit, but allows the user to
configure the polynomial. The data sheet states that National's 48-bit
polynomial is available under license.
WD wasn't as proud of their 56-bit polynomial; it's given in the WD42C22
data sheet. It doesn't seem to match National Semicondutor's 56-bit
polynomial.
17 Nov
17 Nov
1:42 p.m.
Signal boosting (For me, Eric's post landed in the naughty corner)
On 16 November 2016 at 00:19, Eric Smith <spacewar at gmail.com> wrote:
Has anyone determined what 48-bit and 56-bit ECC
polynomials are used by
the National Semiconductor hard disk controllers? The DP8496/97 allows
choice of hard-wired 16-bit CRC, or 32-bit, 48-bit, or 56-bit ECC. The
32-bit ECC is a common polynomial known as the Glover polynomial, and it's
the same one used by WD and others. However, National was apparently
extremely proud of the 48-bit and 56-bit polynomials they chose, and the
data sheets say that they require a license agreement with National.
The more common DP8466 supports 32-bit 48-bit, but allows the user to
configure the polynomial. The data sheet states that National's 48-bit
polynomial is available under license.
WD wasn't as proud of their 56-bit polynomial; it's given in the WD42C22
data sheet. It doesn't seem to match National Semicondutor's 56-bit
polynomial.
5:33 p.m.
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.
5:59 p.m.
Do you have working hardware?
A lot can be deduced by using simple data, like all 0's
and different data lengths.
Dwight
________________________________
From: cctalk <cctalk-bounces at classiccmp.org> on behalf of Eric Smith <spacewar
at gmail.com>
Sent: Thursday, November 17, 2016 2:33:36 PM
To: General Discussion: On-Topic and Off-Topic Posts
Subject: Re: National Semiconductor 48-bit and 56-bit ECC polynomials
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.
6:07 p.m.
On Thu, Nov 17, 2016 at 3:59 PM, dwight <dkelvey at hotmail.com> wrote:
Do you have working hardware?
No, only a drive that 48-bit ECC. I don't know whether it used a National
Semiconductor based controller, but it doesn't use the Western Digital
polynomial, so NS is my first guess. If it used the DP8466, it might have
used the NS Sooper-Sekrit 48-bit polynomial, or some other polynomial.
A lot can be deduced by using simple data, like all
0's and different
data lengths.
If I got my hands on a DP8496 or DP8497, or a SCSI drive containing one of
them, I might be able to hack up something like you describe in order to
reverse-engineer the polynomials.
9:54 p.m.
On 11/17/16 3:07 PM, Eric Smith wrote:
On Thu, Nov 17, 2016 at 3:59 PM, dwight <dkelvey at
hotmail.com> wrote:
MFM?
For a while, I was collecting ISA controllers that weren't adaptec, wd, dtc, or omti
for the uncommon controllers. I just bought a multibus hd/flpy board for the signetics
68454 on it. I may have a board with a 8466. If nothing else, there are a few domestic
8466 chip pulls on eBay for $13 that maybe you could decap or push a bitstream into.
Do you have working hardware?
No, only a drive that 48-bit ECC.
18 Nov
18 Nov
1:09 a.m.
On Thu, Nov 17, 2016 at 7:54 PM, Al Kossow <aek at bitsavers.org> wrote:
MFM?
Yes.
If nothing else, there are a few domestic
8466 chip pulls on eBay for $13 that maybe you could decap or push a
bitstream into.
A DP8466 by itself won't help, because the ECC polynomial gets loaded into
it by another processor.
A DP8496 or DP8497 has the polynomial hardwired.
17 Nov
17 Nov
7:49 p.m.
On 11/17/2016 02:59 PM, dwight wrote:
Do you have working hardware?
A lot can be deduced by using simple data, like all 0's
and different data lengths.
Perhaps there's something useful here:
http://reveng.sourceforge.net/
I've used the code for oddball floppy CRCs.
--Chuck
8:59 p.m.
On Thu, Nov 17, 2016 at 5:49 PM, Chuck Guzis <cclist at sydex.com> wrote:
Perhaps there's something useful here:
http://reveng.sourceforge.net/
I wrote something like that back in the mid-1990s, though not as polished.
The problem is the exponential increase in search space. Polynomials
beyond order 32 quickly become intractable on general-purpose CPUs.
18 Nov
18 Nov
9:40 a.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
3:01 p.m.
On Fri, Nov 18, 2016 at 7:40 AM, Paul Koning <paulkoning at comcast.net> wrote:
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;
Finding only "good" polynomials and then testing those against the data is
far more work than doing the brute-force search of all order-n polynomials
that have a relatively small number of terms including x^0. However,
National might not have restricted their search to a small number of terms,
which had been done in the early days to minimize hardware (number of XOR
gates, and resulting depth of XOR tree). By the mid-1980s that was less of
a concern. There is some evidence that using an order n polynomial with
roughly n/2 terms may typically be stronger than order n polynomials with
few terms, in which case a brute force search for a 56 bit polynomial
becomes almost completely intractable, short of a distributed search on a
large number of machines with GPUs.
I would assume this means you can deduce the CRC
polynomial by
straightforward math from a few well chosen test data blocks.
If I had the hardware that wrote the disk in question, there are a lot of
things I could do, including that.
I may have to tell the owner of the disk drive that I can give him the
uncorrected data only.
8:53 p.m.
On Fri, Nov 18, 2016 at 1:48 PM, Al Kossow <aek at bitsavers.org> wrote:
is there any way to find out what the system and disk
controller board was?
Unfortunately not.
It's possible that the 56-bit ECC code is generated by something other than
division by a polynomial in GF(2). For instance, it could be interleaved
Reed-Solomon coding.
6:02 p.m.
On Thu, Nov 17, 2016 at 03:33:36PM -0700, Eric Smith 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.
...
There might be some other short-cuts to reducing the
search space, but I
haven't yet given it a lot of thought.
I haven't run across it yet. If they used it for the header it is easy to
reverse since they naturally have a pattern that is easy to calculate the
polynomial from. You may find sector data with the correct pattern to also
use the method.
http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.…
6:22 p.m.
you might also look at patent 4979173
cirrus / adaptec from around that time
x^52 + x^50 + x^43 + x^41 + x^34 + x^30 + x^26 + x^24 + x^8 +1
licensed from Glover
On 11/18/16 3:02 PM, David Gesswein wrote:
On Thu, Nov 17, 2016 at 03:33:36PM -0700, Eric Smith
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.
...
There might be some other short-cuts to reducing
the search space, but I
haven't yet given it a lot of thought.
I haven't run across it yet. If they used it for the header it is easy to
reverse since they naturally have a pattern that is easy to calculate the
polynomial from. You may find sector data with the correct pattern to also
use the method.
http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.…
8:49 p.m.
On Fri, Nov 18, 2016 at 4:02 PM, David Gesswein <djg at pdp8online.com> wrote:
I haven't run across it yet. If they used it for
the header it is easy to
reverse since they naturally have a pattern that is easy to calculate the
polynomial from.
They used normal CRC for the headers.
2803
days inactive
2806
days old
15 comments
7 participants
participants (7)
-
aek＠bitsavers.org -
cclist＠sydex.com -
djg＠pdp8online.com -
dkelvey＠hotmail.com -
ed.spittles＠gmail.com -
paulkoning＠comcast.net -
spacewar＠gmail.com