Guessing CRC-24 parameters

Question

I want to find parameters for some CRC-24 algorithm.

All I know is that:

---

Source 1

• generator polynomial is 1010111010110110111001011 = 0x15D6DCB, i.e.

  5D6DCB
  

  in normal representation (MSB-first code)

• data (in hex)

  00 40 00 01 09 01 01 B0 A0 0C 0A 01 00 04 07 A0 05 A5 03 80 01 02 00 00 00 00 00 00 00 00 00
  

  gives

  99 84 62
  

Generator polynomial is the same as used in CRC-24/FLEXRAY, but it's all about finding other parameters. I did some tests using flexible jacksum tool, but without success so far.

BYTES="00 40 00 01 09 01 01 B0 A0 0C 0A 01 00 04 07 A0 05 A5 03 80 01 02 00 00 00 00 00 00 00 00 00"
jacksum -s '\t' -a 'crc:24,5D6DCB,000000,fals,fals,000000+crc:24,5D6DCB,000000,true,true,000000+crc:24,5D6DCB,abcdef,fals,fals,000000+crc:24,5D6DCB,abcdef,true,true,000000+crc:24,5D6DCB,fedcba,fals,fals,000000+crc:24,5D6DCB,fedcba,true,true,000000+crc:24,5D6DCB,ffffff,fals,fals,ffffff+crc:24,5D6DCB,ffffff,true,true,ffffff' -F '#FILESIZE #ALGONAME{i}#SEPARATOR#CHECKSUM{i}' -E hex -q "hex:$(echo $BYTES | sed 's/ //g')"

31 crc:24,5d6dcb,000000,fals,fals,000000    6579ac
31 crc:24,5d6dcb,000000,true,true,000000    b17f3a
31 crc:24,5d6dcb,abcdef,fals,fals,000000    fd794d  # CRC-24/FLEXRAY-B
31 crc:24,5d6dcb,abcdef,true,true,000000    367f23
31 crc:24,5d6dcb,fedcba,fals,fals,000000    e8a75b  # CRC-24/FLEXRAY-A
31 crc:24,5d6dcb,fedcba,true,true,000000    5e048b
31 crc:24,5d6dcb,ffffff,fals,fals,ffffff    a408f7
31 crc:24,5d6dcb,ffffff,true,true,ffffff    6bf1b9

Just in case I tried also reversed bytes order and reversed nibble order of input data, but there was no 99 84 62 or 62 84 99 there.

I think that refIn=false refOut=false xorOut=0, but don't know for sure.

---

Source 2

DATA + CRC (in hex) - one entry per line:

00C01FFF057EA013CEFFCD1361D5E6E6001D64001400002C667E0000000000329BEA
00FFEC01007EA018CDCE2313BB18E6E7001E0149534B050000000100B3017E38CD0F
00C01FFF1B7EA021CEFFCD133817E6E6001CFEFEFEFEFEFEFEFE0149534B050000000100100CE67E00000000000000000000000000000000000000000000000000000054F223
00C01010107EA0080223C993E4437E000000000000000000000000000000003F96F1
00010C011D7EA01FC9022373B49681801205017E06017E0704000000010804000000015F757E0000000000000000000000000000000000000000000000000000000000723D01
00C010101B7EA0450223C9102148E6E6006036A1090607608574050801018A0207808B0760857405080201AC0A80083132333435363738BE10040E01000000065F1F0400007E1FFFFF83D77E0000000000000000000000000000000000000000000000000000009BFF67
00010C01037EA039C902233022BDE6E700612AA109060760857405080101A203020100A305A103020100BE11040F080100065F1F0400007C1F04000007194A7E00000010E99A
00C01010227EA01A0223C932AF55E6E600C0014000080000010000FF0200EADD7E00000000000000000000000000000000000000000000000000000000000000000000C22B4A
00010C011D7EA01FC90223523FA6E6E700C4014000090C07D201070101231A00FFC40080EC7E0000000000000000000000000000000000000000000000000000000000C162A6
00010C011D7EA01FC9022373B49681801205017E06017E0704000000010804000000015F757E0000000000000000000000000000000000000000000000000000000000723D01

Running reveng -w 24 -F -s ... gives no models found. Does it mean that some of the above examples may be corrupted? Unfortunately I'm not 100% sure that all of them are correct...

---

Is there any sane way to find init, refIn, refOut and xorOut without using brute-force?

Answer 1

You need to provide more than one sequence and associated crc's in order to solve for the parameters. Please provide four sequences consisting of two pairs, where each pair are sequences of the same length, and the two pairs have different lengths.

Take a look at CRC RevEng. With just the one sequence and specifying the polynomial, it reports two possibilities:

width=24  poly=0x5d6dcb  init=0xe959e3  refin=false  refout=false  xorout=0x000000  check=0x13fe57  name=(none)
width=24  poly=0x5d6dcb  init=0x005035  refin=true  refout=true  xorout=0x000000  check=0x63b7b9  name=(none)

However they cannot be distinguished or verified with just one example.

Update:

I found the crc. It turns out that the last three bytes before the crc do not participate in the crc calculation. Then the provided polynomial is used non-reflected on the data with no pre or post processing. However the resulting crc needs to be reflected and then written in big endian order.

You can use RevEng to generate the crc. For example, for the first example you posted (with the last three bytes deleted):

$ reveng -c -w 24 -L -p 5d6dcb 00400001090101B0A00C0A01000407A005A503800102000000000000
628499

where reveng provided the answer in little endian order. In your data it is in big endian order: 99 84 62.

This works for all of the examples except for the one that starts with 00 FF. That one is also anomalous in that the penultimate three bytes are not zero, where they are zero in all the other cases.

This particular crc unfortunately cannot be deduced by RevEng, since it is an odd one that RevEng won't search. When you try to use -s with -L, you get:

reveng: cannot search for crossed-endian models

Here is code to generate the crc. Note that the last three bytes before the crc are not to be provided to crc24(), and the result of crc24() has to be written to or compared in big endian order.

unsigned long reflect(unsigned long val, int bits)
{
    unsigned long vers;

    vers = 0;
    while (bits) {
        vers = (vers << 1) | (val & 1);
        val >>= 1;
        bits--;
    }
    return vers;
}

#define POLY 0x5d6dcb
#define CARRY 0x800000

unsigned long crc24(unsigned long crc, unsigned char *buf, unsigned len)
{
    crc = reflect(crc, 24);
    while (len--) {
        crc ^= (unsigned long)(*buf++) << 16;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
        crc = crc & CARRY ? (crc << 1) ^ POLY : crc << 1;
    }
    return reflect(crc, 24);
}