6

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?

  • Wait a minute, I don't understand the background. What's on the floppy disk - the word processor or the document editable by the word processor? What is supposed to reads the floppy disk? Besides, what's GCR? This? – user202729 Oct 22 '18 at 13:52
  • Ah, right, context. This dates back from the days when word processors were things, not programs --- it's an electric typewriter with a screen and a floppy drive. Pictures are annoying hard to find but gizmodo.com/… is a slightly later model than mine. The floppy format used to save files was very very not PC, with 256-byte sectors, GCR rather than MFM (your link is correct), a different low level disk format, etc. I have some custom hardware to read these with a modern PC floppy drive. But that stuff's all figured out. – David Given Oct 22 '18 at 13:57
  • Try producing some sectors with low Hamming distance (number of different bits)? That way it may be possible to determine how individual bits affect the checksum, just in case the checksum algorithm is linear (or close to linear enough). – user202729 Oct 22 '18 at 16:37
  • I'll give that a try, but right now the machine is 9000km away, so it'll have to wait until next week. If I can figure this out from just my disk image that'd be awesome. – David Given Oct 23 '18 at 0:22
6

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 2width 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.

| improve this answer | |
  • Wow --- thank you so much! I was expecting to have to pick away at it myself once I got back to the machine and could generate source data. Yes, this works fine (I have a C implementation and the results match). I'm a bit surprised reveng didn't detect this; it seems like a fairly standard variation to the standard algorithm. – David Given Oct 25 '18 at 4:05
  • Also, would you like a credit in my code, and if so, how? – David Given Oct 25 '18 at 4:05
  • Does reveng always/completely use brute force to find a CRC polynomial? For a CRC32 it needs about 10 minutes. Imagine how long it would take for a CRC64. Are there no methods to reduce the computation effort in a non-brute-force manner? – Silicomancer Apr 26 '19 at 22:06
  • @Silicomancer I think so. / I think cosc.canterbury.ac.nz/greg.ewing/essays/… may have a method. – user202729 Apr 27 '19 at 3:18
  • @user202729: It seems the author uses a very special method to calculate the polynomial. I think in most cases this will not work since it requires very specific modification of the payload data (namely repeated changing the data by a single, walking bit). Do you have an idea if there is a non-brute-force method that uses random payload/checksum pairs to reconstruct the polynomial? – Silicomancer Apr 27 '19 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.