CRC-8 algorithm in m3/y

[AMP3R]

Does anyone know what crc-8 algorithm is used in M3/Y? I've tried different 20 and none of them are similar to Tesla's.
I'm trying to emulate the steering column switch.

[uhi22]

Other OEMs use a combination of CRC and a table of magic bytes (with 16 entries). The counter (0 to 15) would select a row in the table. The content of the table can be added to the byte stream for the CRC. If we would have more data (also changing some payload data it should be possible to reverse-engineer the algorithm.

Edit: What I wrote is public available as E2E Profile 2 in the Autosar E2E specification, https://www.autosar.org/fileadmin/stand ... otocol.pdf

[AMP3R]

I have already almost done this table of bytes.

[uhi22]

Yeah, great. This looks like the "pragmatic" approach. Just putting the CRC into a lookup table, and having different tables for different message payload. And then selecting the right table based on the payload. With this approach, no real CRC calculation is necessary, because the CRC can be taken directly from the table. Ok so far, as long as the number of combinations is small (e.g. in the case that the message only contains buttons, and maximum one button is pressed at a certain time).

The more flexible approach would have only *one* table with 16 entries, and calculate the CRC over the payload and magic byte.

It is possible to find out the CRC polynom, if we have some messages where single bits are set and reset, and where the message counter (and so the magic byte) is identical. Each bit in the message leads to a characteristic change in the CRC, and this reveals the polynom. The approach was successfully used here: https://knx-user-forum.de/forum/%C3%B6f ... post626281

When the polynom is found, a set of 16 messages with identical payload and counter values from 0 to 15 can be used to calculate the 16 magic bytes.

[AMP3R]

Since other car manufacturers use prepared CRC arrays, why am I worse?

In general, what is easier for a microcontroller, to calculate CRC in real time or to take ready-made ones from arrays?

[uhi22]

Both is fine Tables need ROM space, calculation needs runtime. Depends on the project which of both is more important.
But there are two different layers we are mixing up here:
1. The CRC calculation itself: The CRC calculation function can use either tables or loops with bit operations.
2. How to find the value for CRC field in the CAN message. This can eigher use
(a) the CRC function (see 1), or
(b) it can use pre-calculated table entry which needs to be available for each possible combination of payload data.

The 2b explodes, if we have more than a few bits in the payload. E.g. 8 independent buttons combined with 16 values of the counter would need 256*16=4096 table entries.

[projectgus]

I've had good luck using CRCBeagle in the past: https://github.com/colinoflynn/crcbeagle/ - fed enough samples of data and CRC, it should be able to calculate init/poly/xor.

Of course if it's something like the Autosar algorithm mentioned by uhi22 then it won't be able to recover that.

[AMP3R]

Both is fine Tables need ROM space, calculation needs runtime. Depends on the project which of both is more important.
But there are two different layers we are mixing up here:
1. The CRC calculation itself: The CRC calculation function can use either tables or loops with bit operations.
2. How to find the value for CRC field in the CAN message. This can eigher use
(a) the CRC function (see 1), or
(b) it can use pre-calculated table entry which needs to be available for each possible combination of payload data.

The 2b explodes, if we have more than a few bits in the payload. E.g. 8 independent buttons combined with 16 values of the counter would need 256*16=4096 table entries.

Then in my case with gear selector it is better to use arrays with CRC.

[AMP3R]

If anyone is interested in how the checksum is calculated in most of messages in M3/Y, here is an example.

ID (0×313) 0×02 0×00 0×C8 0×07 0×00 0×00 0×E0 0×checksum

0×02 + 0×00 + 0×C8 + 0×07 + 0×00 + 0×00 + 0×E0 + 0×13 (ID rh 2 digits) + 0×03 (ID first digit) = 0×C7

[tg1929]

Hi AMP3R, I am currently playing with generating Stalk messages and UI messages to test how the VCLeft, VCRight and VCFront modules interact in my model 3.
For example I simulated blinker commands by sending 0x249 messages with a cksum lookup based on a capture of successful messages from the Steering and Stalk ECU.
I am now trying to generate the CKSUM messages for cases where I cant generate a successful example. I have spent all afternoon trying different crc algorithms and different sections of the data packets without success.
I came across this thread but cant seem to replicate the results in the example above. I saw another post, I think also from you mentioning the algorithm is CRC-8/SAE-J1850, is this the case for the example above?
When I use the following data
0x02 0x00 0xC8 0x07 0x00 0x00 0xE0 0x13 0x03
I get result 0x03 not 0xC7 as shown.
Can you give me a hint where I'm going wrong?

[uhi22]

If anyone is interested in how the checksum is calculated in most of messages in M3/Y, here is an example.

ID (0×313) 0×02 0×00 0×C8 0×07 0×00 0×00 0×E0 0×checksum

0×02 + 0×00 + 0×C8 + 0×07 + 0×00 + 0×00 + 0×E0 + 0×13 (ID rh 2 digits) + 0×03 (ID first digit) = 0×C7

If I interpret the "+" just as a normal "plus", then my result is 0x1C7, so the low byte 0xC7 would fit. So no CRC at all, just a basic addition.
I'm not sure whether this is the truth, I would have expected a CRC. Would need more data to verify what it really is.

[AMP3R]

Hi AMP3R, I am currently playing with generating Stalk messages and UI messages to test how the VCLeft, VCRight and VCFront modules interact in my model 3.
For example I simulated blinker commands by sending 0x249 messages with a cksum lookup based on a capture of successful messages from the Steering and Stalk ECU.
I am now trying to generate the CKSUM messages for cases where I cant generate a successful example. I have spent all afternoon trying different crc algorithms and different sections of the data packets without success.
I came across this thread but cant seem to replicate the results in the example above. I saw another post, I think also from you mentioning the algorithm is CRC-8/SAE-J1850, is this the case for the example above?
When I use the following data
0x02 0x00 0xC8 0x07 0x00 0x00 0xE0 0x13 0x03
I get result 0x03 not 0xC7 as shown.
Can you give me a hint where I'm going wrong?

I don't know yet what crc algorithm is used in the stalks. None of the popular ones are suitable. Sum of bytes doesn't give anything either.

But for UI messages, the method I described above is suitable. Carefully sum each byte separately.

crc-8/sae-j1850 is used in ibooster.

[AMP3R]

If we would have more data (also changing some payload data it should be possible to reverse-engineer the algorithm.

Hey uhi22. Would you help to reverse the algorithm?

Frames crcCenter:
0x229 0x46 0x00 0x00
0x229 0x44 0x01 0x00
0x229 0x52 0x02 0x00
0x229 0x6D 0x03 0x00
0x229 0x43 0x04 0x00
0x229 0x41 0x05 0x00
0x229 0xDD 0x06 0x00
0x229 0xF9 0x07 0x00
0x229 0x4C 0x08 0x00
0x229 0xA5 0x09 0x00
0x229 0xF6 0x0A 0x00
0x229 0x8C 0x0B 0x00
0x229 0x49 0x0C 0x00
0x229 0x2F 0x0D 0x00
0x229 0x31 0x0E 0x00
0x229 0x3B 0x0F 0x00

Frames crcFullDown:
0x229 0xB7 0x40 0x00
0x229 0xB5 0x41 0x00
0x229 0xA3 0x42 0x00
0x229 0x9C 0x43 0x00
0x229 0xB2 0x44 0x00
0x229 0xB0 0x45 0x00
0x229 0x2C 0x46 0x00
0x229 0x08 0x47 0x00
0x229 0xBD 0x48 0x00
0x229 0x54 0x49 0x00
0x229 0x07 0x4A 0x00
0x229 0x7D 0x4B 0x00
0x229 0xB8 0x4C 0x00
0x229 0xDE 0x4D 0x00
0x229 0xC0 0x4E 0x00
0x229 0xCA 0x4F 0x00

Frames crcParkButton:
0x229 0xAF 0x00 0x01
0x229 0xAD 0x01 0x01
0x229 0xBB 0x02 0x01
0x229 0x84 0x03 0x01
0x229 0xAA 0x04 0x01
0x229 0xA8 0x05 0x01
0x229 0x34 0x06 0x01
0x229 0x10 0x07 0x01
0x229 0xA5 0x08 0x01
0x229 0x4C 0x09 0x01
0x229 0x1F 0x0A 0x01
0x229 0x65 0x0B 0x01
0x229 0xA0 0x0C 0x01
0x229 0xC6 0x0D 0x01
0x229 0xD8 0x0E 0x01
0x229 0xD2 0x0F 0x01

[uhi22]

We would need more data. The full counter range, and some more bits of the buttons.

[AMP3R]

We would need more data. The full counter range, and some more bits of the buttons.

Added more data.

[tg1929]

Hi AMP3R, I tested the sum method and it indeed works for ID 293 UI Chassis Control.
I didn't get any time to test today but this should let me turn the handbrakes on and off among other things.
Following along on the conversation for ID 229 Right Stalk, hopefully if a solution is found it would also work for 249 Left Stalk.
Thanks all for the info.

[uhi22]

Added more data.

Looks good, I see patterns. Each button causes a certain XOR delta in the checksum. Do we have more data of single buttons, and maybe also combinations e.g. Park+Down?

[AMP3R]

Frames crcFullUp:
0x229 0xA9 0x20 0x00
0x229 0xAB 0x21 0x00
0x229 0xBD 0x22 0x00
0x229 0x82 0x23 0x00
0x229 0xAC 0x24 0x00
0x229 0xAE 0x25 0x00
0x229 0x32 0x26 0x00
0x229 0x16 0x27 0x00
0x229 0xA3 0x28 0x00
0x229 0x4A 0x29 0x00
0x229 0x19 0x2A 0x00
0x229 0x63 0x2B 0x00
0x229 0xA6 0x2C 0x00
0x229 0xC0 0x2D 0x00
0x229 0xDE 0x2E 0x00
0x229 0xD4 0x2F 0x00

Frames crcHalfDown:
0x229 0x49 0x30 0x00
0x229 0x4B 0x31 0x00
0x229 0x5D 0x32 0x00
0x229 0x62 0x33 0x00
0x229 0x4C 0x34 0x00
0x229 0x4E 0x35 0x00
0x229 0xD2 0x36 0x00
0x229 0xF6 0x37 0x00
0x229 0x43 0x38 0x00
0x229 0xAA 0x39 0x00
0x229 0xF9 0x3A 0x00
0x229 0x83 0x3B 0x00
0x229 0x46 0x3C 0x00
0x229 0x20 0x3D 0x00
0x229 0x3E 0x3E 0x00
0x229 0x34 0x3F 0x00

also combinations e.g. Park+Down?

Don't have.

[uhi22]

Which positions are possible? If there are only
- Idle
- Full Up
- Full down
- halve Up
- half down
- Park
I guess it is possible to calculate the crc using
1. A table with 16 entries ("Magic Bytes") and
2. A table with 5 "addon" XOR patterns.
If more combinations are necessary, it is worth to search for the crc polynom in the addon patterns.

[AMP3R]

Which positions are possible? If there are only
- Idle
- Full Up
- Full down
- halve Up
- half down
- Park

No more positions.

I guess it is possible to calculate the crc using
1. A table with 16 entries ("Magic Bytes") and
2. A table with 5 "addon" XOR patterns.

In short, there is no way to do without tables of bytes? If so, then I don't see the point in bothering with the search. I'll stick with the dumb method I showed at the beginning of the topic.

[tg1929]

Hi All, In case it is useful to anyone I spent some time today logging all possible movements of both the left and the right stalk.
Attached is a sorted and filtered list in the format D0 D1 D2 D3(249 only) in both cases D0 is the cksum
I came up with 178 different options for 229 and 870 options for 249
Each possible stick position should have 16 messages as they include the counter, I must have missed a couple as the totals are not divisible by 16.
AMP3R I found when simulating the 249 messages the car would respond to a minimum of 4 consecutive messages with correct cksums. did you find something similar?

[uhi22]

In short, there is no way to do without tables of bytes? If so, then I don't see the point in bothering with the search. I'll stick with the dumb method I showed at the beginning of the topic.

Just tested my assumptions, and they fit perfectly to the published data of the 0x229. It needs one table with 16 entries for the magic bytes, and for each direction an additional one-byte value. Available here: https://github.com/uhi22/tesla-crc
To be tested, whether this sufficient for the 0x229, and what is the difference for the 0x249.

[AMP3R]

I found when simulating the 249 messages the car would respond to a minimum of 4 consecutive messages with correct cksums. did you find something similar?

Judging by the different logs, apparently even two valid frames are enough.

[AMP3R]

Just tested my assumptions, and they fit perfectly to the published data of the 0x229. It needs one table with 16 entries for the magic bytes, and for each direction an additional one-byte value. Available here: https://github.com/uhi22/tesla-crc
To be tested, whether this sufficient for the 0x229, and what is the difference for the 0x249.

Okay, but how difficult will it be to find the polynom?

[uhi22]

Small exercise
Using the "big data" from @tg1929, I found the polynom used in the message 0x249. Not yet verified with the complete data, but what I checked looks plausible. I guess the 0x229 will use the same, just with a different length and different list of magic bytes.
Updated the readme on the github. No C code yet.