Reverse-engineering a weird 24-bit possibly not CRC checksum

Question

Yes, it's one of these!

I have a 199mumble Brother integrated word processor, with a very weird non-PC floppy format. I've built a floppy controller and have successfully read the flux off the disk, decoded both kinds of GCR, and reassembled the result into a disk image. But I need to be able to check the checksums in the sectors to know whether I've done it right. (Eyeballing it looks good.)

Each sector is 256 bytes and is followed by three bytes which vary depending on the contents of the sector --- identical sectors produce identical values, so I'm assuming it's a checksum. Interestingly, the all-zero sector produces an all-zero checksum, so I suspect it's not a regular CRC.

I have 100 different examples but there may be some incorrect results in there (due to misread sectors); the full list is at https://pastebin.com/0HZrUVPR but here are a few selected examples, in what's hopefully reveng format so the checksum is in the last three bytes:

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005750314120464c4f505059080000000000000000000000000000000000000000616161616161616120202020000000000000000000000000000002000a5d000064656d6f20202020a4ca1a
414141414141414141410000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008b38af
414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141de6162636465666768696a6b6c6d6e6f707172737475767778797a303132333435363738394141414141414141414141414141414141414141414141414141414141de4141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141de4141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141415a6ea1
41414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141de4141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141de6162636465666768696a6b6c6d6e6f707172737475767778797a303132333435363738394141414141414141414141414141414141414141414141414141414141de41414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141413362ac

Note that the last two contain the same data, rotated right a whole number of bytes.

So, I'm stumped. There are some 24 bit CRCs but they appear to be quite rare. reveng had nothing, but I'm not entirely sure I'm driving it correctly --- it appeared to execute more quickly than anything which does a brute force search ought to. I've tried some trivial summing methods but the easy ones didn't work and there are too many variations just to guess.

How would I go about figuring this out?

Answer 1

The answer turns out to be very simple, once you understand what CRC is.

It's similar to a CRC -- the checksum is the remainder when dividing the input by the polynomial with truncated representation 0x000201.

I wrote a quick Python script to validate checksum:

def crc(data, poly):
    # width = 24 bit
    # data len = 2048 bit
    assert poly<(1<<24)
    for i in range(2048-1,24-1,-1):
        if data>>i&1:
            data^=1<<i
            data^=poly<<(i-24)
    assert i==24
    assert data<(1<<24)
    return data

import sys
for line in sys.stdin.read().splitlines():
    line = int(line,16)
    print(crc(line>>24,0x000201) == line&~(-1<<24))

Try it online!

The crc function may be used to generate missing checksum values.

How?

First, I assumed that the checksum function satisfies the property: for all x and y, we have checksum(x) xor checksum(y) == checksum(x xor y).

Using Gaussian elimination on the provided data, I can deduce that the hash of 000000...000000bb0301 is bb0301. Looks pretty reasonable.

Then, I read about existing hash functions and see what method they uses. I note that CRC uses polynomial remainder mod 2, so I guess that the hash is the input as a polynomial modulo some polynomial with degree 25 (because the output has 24 bits).

With simple brute force, I conclude that the polynomial is 000201. Testing reveals that it's correct.

reveng had nothing, but I'm not entirely sure I'm driving it correctly --- it appeared to execute more quickly than anything which does a brute force search ought to.

Why reveng executes so quickly?

It's because there are only 2^width possible polynomials. reveng only takes small time to try each polynomial. In this case width = 24, so there are only 1048576 polynomials, which is not very large for a computer.

Why reveng returns no output? What's the difference between this and CRC?

CRC appends width (in this case - 24) bits to the input before computing polynomial remainder, this algorithm doesn't.