Slashdot Mirror

← Back to Stories (view on slashdot.org)

Reversing a Checksum Algorithm?

Posted by Cliff on from the hope-you've-brushed-up-on-your-math dept.

Todd asks: "Does anyone have good suggestions or advice regarding techniques for determining the checksum of a serial data protocol? I am currently working on a fun little project using a digital display sign which uses an unknown serial protocol. I cannot move on with the project until I figure this dreaded checksum out."

3 of 35 comments (clear)

  1. Use the Force Luke! by psavo · · Score: 5, Insightful

    really.
    I don't think you have much choice but brute-force it.
    Collect as many as possible checksum -generators, and try them on portions of message.
    Some more-or less trivial are 'LRC', CRC, CRC16, and CRC32 ones. Of course XOR too. difficulty is to determine which characters go to checksum, as it's not always that 'STX'/'ETX' are included.

    --
    fucktard is a tenderhearted description
  2. Input! More Input! by cookd · · Score: 5, Insightful

    I played around with the sample data you provided. I came across some funny business which I am almost certain is an error in your spreadsheet, which throws the whole thing into doubt. Did you mean to repeat the slot encoding 0x05 for both slots 5 and 6? I'm going to assume it was a typo. If so, I learned the following about the impact the slot number has on the checksum:

    8-bit-number
    Bits == 76543210

    Csum(x) is the value of the checksum with slot #x and all else held constant.

    Csum(x) = Csum(0) +
    (Bit0(x) ? -0x0F : 0) +
    (Bit1(x) ? -0x1E : 0) +
    (Bit2(x) ? +0x3C : 0) +
    (Bit3(x) ? -0x78 : 0) +
    (Bit4(x) ? -0xF0 : 0)

    Note that the values added/subtracted for each bit follow a pattern:
    0x0F = 00001111
    0x1E = 00011110
    0x3C = 00111100
    0x78 = 01111000
    0xF0 = 11110000

    More data might shed some light on the pattern. Whatever the case, I think this is reminiscent of a CRC16, since I don't think a checksum would have this kind of behavior -- a standard addition checksum or a XOR-based checksum (even with bit rotation) would make a bit always add/subtract the same amount, but it would be a power of 2 (I think).

    So now you need to find the CRC's polynomial, and I don't know enough about that kind of thing to help you. (And there is a chance that everything I've said here is wrong, since this is not my specialty!)

    --
    Time flies like an arrow. Fruit flies like a banana.
  3. Solved it by sepulcrum · · Score: 5, Interesting

    I put sign.exe thru IDA and identified the checksum algorithm. I found out that the only thing that goes thru the checksum is 35 35 00 then 0E DA is skipped and then the rest is put thru. The algorithm is a simple crc alike algo that adds the chars xors with the length and rotates some bits. You can find a perl program i wrote to calculate the checksum for a given range at: this location.

    Good luck with your project,
    Gijs