How would I reverse this simple-looking algorithm?

Question

I got some old LED board to which you'd send some text and hang it up somewhere... it was manufactured in 1994/95 and it communicates over a serial port, with a 16-bit MS-DOS application in which you can type in some text.

So, because you probably couldn't run it anywhere except by using DOSBox or similar tricks, I decided to rewrite it in C#.

After port-monitoring the original dos-exe I've found that it's really not interested in you rebuilding it - requests must be answered suitable, varying bytes, pre-sent "ping" messages, etc...

Maybe you know a similar checksum routine/pattern as my dos-exe uses or you could give any tips in trying to reverse-engineer this... Additionally, because I am only familiar with programming and didn't spend much time on reversing methods and/or analyzing protocols, please don't judge me if this topic is a bit of a stupid idea - I'll be glad about any help I get...

The message really containing the text that should be displayed is 143 bytes long (just that long because it puts filler bytes if you don't use up all the space with your text), and in that msg I noticed the following patterns:

• The fourth byte (which still belongs to the msg header) varies from a list of 6 or 7 repeating values (in my examples, that byte will always be 0F).

• The two last bytes function as a checksum

Some examples:

• displayed text: "123" (hex: "31 32 33"), checksum hex: "45 52"
• text: "132" ("31 33 32"), checksum hex: "55 FF"
• text: "122" ("31 32 32"), checksum hex: "95 F4"
• text: "133" ("31 33 33"), checksum hex: "85 59"
• text: "112" ("31 31 32"), checksum hex: "C5 C8"
• text: "124" ("31 32 34"), checksum hex: "56 62"
• text: "134" ("31 33 34"), checksum hex: "96 69"
• text: "211" ("32 31 31"), checksum hex: "5D 63"
• text: "212" ("32 31 32"), checksum hex: "3C A8"
• text: {empty}, checksum hex: "DB BA"
• text: "1" ("31"), checksum hex: "AE 5F"

So far I am completely sure that the checksum really does depend on this fourth byte in the header, because if it changes, the checksums will be completely different for the same text to be displayed.

Here's an an example of a full 143 bytes-string displaying "123", just for giving you a better orientation:

02 86 04 0F 05 03 01 03 01 03 01 03 00 01 03 00   ...............
00 31 00 32 00 33 00 20 00 20 00 20 00 20 00 20   .1.2.3. . . . . 
00 20 00 20 00 20 00 20 00 20 00 20 00 20 00 20   . . . . . . . . 
00 20 00 20 00 20 00 20 00 20 00 20 00 20 00 20   . . . . . . . . 
00 20 00 20 00 20 00 20 00 20 00 FE 03 01 03 01   . . . . . .þ....
04 01 03 00 01 03 00 00 20 00 20 00 20 00 20 00   ........ . . . .
20 00 20 00 20 00 20 00 20 00 20 00 20 00 20 00    . . . . . . . .
20 00 20 00 20 00 20 00 20 00 20 00 20 00 20 00    . . . . . . . .
20 00 20 00 20 00 20 00 20 00 20 00 20 45 52

(the text information starts with 2nd byte in 2nd line "31 00 32 00 33 00 (...)"

Unfortunately on the whole web, there are no user manuals, documentations, not even a real evidence that this info board-device ever existed.

Answer 1

I'll write F(s) for the checksum you get when feeding in string s.

Observe that:

• F("122") xor F("123") = 95 F4 xor 45 52 = D0 A6
• F("132") xor F("133") = 55 FF xor 85 59 = D0 A6
• F("123") xor F("124") = 45 52 xor 56 62 = 13 30
• F("133") xor F("134") = 85 59 xor 96 69 = 13 30

all of which is consistent with the checksum having the following property, which checksums not infrequently have: changing a given bit in the input always XORs the output with the same thing.

I predict, e.g., that F("210") = F("211") xor D0 A6 = 8D C5, and similarly that F("222") = 3C A8 xor C5 C8 xor 95 F4 = 6C 94.

If this is true, then the following gives you a brute-force-y way to figure out the checksum in general, provided you have a black box that computes checksums for you (which apparently you have):

• Find the checksum of an input all of whose bits are 0. Call this a.
• For each bit position k, find the checksum of an input all of whose bits are 0 except for bit k which is 1. Call this a XOR b(k).
• Now the checksum of an arbitrary input is a XOR each b(k) where bit k is set in the input.

Usually the b(k) will be closely related to one another -- the usual pattern is that you're feeding bits into a shift register -- so the above is more brute-force-y than you'd need given an understanding of the algorithm. But I expect it works, if you are able to feed in arbitrarily chosen bit patterns as input.

If not, you may still be able to do it. E.g., suppose all you actually get to choose is 29 7-bit ASCII character values, at positions 17,19,...73 of your input. Then you can first of all feed in all spaces (0x20) and then XOR each in turn with 1-bits in positions 0..6. That won't give you all the b(k) but it will give you enough for arbitrary 29-ASCII-character inputs.