FSoE: Jak funguje dědičnost CRC?

Functional Safety over EtherCAT (FSoE) používá vlastní 16-bitové CRC pro ochranu každé Safety PDU (Protocol Data Unit). Na první pohled algoritmus vypadá jako standardní CRC-16 s vyhledávací tabulkou, ale dvě designové volby ho činí neobvyklým:

Každý datový bajt je násoben extra faktorem $x^{24}$ ve srovnání se standardní bajtové aktualizací CRC.
CRC předchozího rámce je vloženo do CRC dalšího rámce, čímž se vytváří řetěz přes rámce („dědičnost CRC").

Tento článek vysvětluje oba mechanismy detailně, na základě původního zdrojového kódu FSoE a automaticky generovaných vyhledávacích tabulek v Tables.c.

Polynom a dvě tabulky

FSoE CRC používá 17-bitový polynom

$$ P(x) = x^{16} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x + 1 $$

balený jako 0x39B7 (člen $x^{16}$ je implicitní). CRC je zpracováváno MSB-first („normální", neodrážený směr).

Dvě vyhledávací tabulky o 256 položkách jsou předpočítány z tohoto polynomu:

Tabulka	Vzorec	Posuny	Význam
`CRC16_TABLE` ($T_0$)	$T_0[i] = (i \cdot x^{16}) \bmod P$	8	Standardní bajtová tabulka
`CRC16_TABLE2` ($T_3$)	$T_3[i] = (i \cdot x^{40}) \bmod P$	32	Slice-by-4 tabulka = $T_0$ aplikováno 4× (bajt $i$ + 3 nulové bajty)

Obě tabulky jsou generovány načtením $i$ do horního bajtu 16-bitového registru a posunem vlevo, XORováním polynomu vždy, když je bit 15 nastaven:

table-entry.c

for (n = 0; n < 8 + 8*k; n++)
    crc = (crc & 0x8000) ? ((crc << 1) ^ 0x39B7) : (crc << 1);

for (n = 0; n < 8 + 8*k; n++)
    crc = (crc & 0x8000) ? ((crc << 1) ^ 0x39B7) : (crc << 1);

Krok aktualizace pro každý bajt

Každý bajt je vložen do CRC s tímto vzorem (opakováno pro každý bajt ve výpočtu):

fsoe-update.c

w1 = aCRCTab1[crc >> 8];       /* T0[crc_hi]  -- posun CRC registru o 1 bajt */
w2 = aCRCTab2[input_byte];     /* T3[input]   -- vložit vstupní bajt  */
w  = w1 ^ w2;
crc = (w & 0xFF) | ((w >> 8 ^ crc_lo) << 8);

w1 = aCRCTab1[crc >> 8];       /* T0[crc_hi]  -- posun CRC registru o 1 bajt */
w2 = aCRCTab2[input_byte];     /* T3[input]   -- vložit vstupní bajt  */
w  = w1 ^ w2;
crc = (w & 0xFF) | ((w >> 8 ^ crc_lo) << 8);

Zjednodušeně (to lze ověřit rozbalením bajtových operací):

$$ \text{crc}_{\text{new}} = (\text{crc}_{\text{lo}} \ll 8) \;\oplus\; T_0[\text{crc}_{\text{hi}}] \;\oplus\; T_3[\text{input}] $$

Člen $(\text{crc}{\text{lo}} \ll 8) \oplus T_0[\text{crc}{\text{hi}}]$ je přesně standardní MSB-first posun CRC registru o jeden bajt (ekvivalentní zpracování nulového bajtu). Pak je $T_3[\text{input}]$ XORováno.

Jak se to liší od standardního CRC-16

Standardní bajtová aktualizace CRC-16 by byla:

$$ \text{crc}_{\text{std}} = (\text{crc}_{\text{lo}} \ll 8) \;\oplus\; T_0[\text{crc}_{\text{hi}} \oplus \text{input}] $$

což se rozbalí na:

$$ \text{crc}_{\text{std}} = (\text{crc}_{\text{lo}} \ll 8) \;\oplus\; T_0[\text{crc}_{\text{hi}}] \;\oplus\; T_0[\text{input}] $$

FSoE kód nahrazuje $T_0[\text{input}]$ za $T_3[\text{input}]$. Protože CRC aritmetika je lineární nad GF(2):

$T_0[\text{input}] = (\text{input} \cdot x^{16}) \bmod P$ — vstupní bajt na své přirozené pozici
$T_3[\text{input}] = (\text{input} \cdot x^{40}) \bmod P$ — vstupní bajt posunutý o 24 bitů (3 bajty) výše

Takže každý vstupní bajt dostává extra faktor $x^{24}$ ve srovnání se standardním CRC. Po zpracování $n$ bajtů $b_0 \dots b_{n-1}$ z počáteční hodnoty $\text{startCrc}$ (která sama je vložena jako první 2 bajty):

$$ \text{FSoE CRC} = \left( \text{startCrc} \cdot x^{8n} + \sum_{k=0}^{n-1} b_k \cdot x^{40 + 8(n-1-k)} \right) \bmod P $$

versus standard:

$$ \text{Standard CRC} = \left( \text{startCrc} \cdot x^{8n} + \sum_{k=0}^{n-1} b_k \cdot x^{16 + 8(n-1-k)} \right) \bmod P $$

Jediný rozdíl je $x^{40}$ vs $x^{16}$ pro každý datový bajt — extra $x^{24}$ na bajt. Ekvivalentně, FSoE CRC je CRC zprávy jako by každý bajt byl následován 3 nulovými bajty, ale s počáteční hodnotou posunutou pouze o skutečný počet bajtů (ne o počet s paddingem). To je vlastní varianta specifická pro FSoE, neekvivalentní žádné standardní konvenci padded-CRC.

Pořadí zpracování bajtů

CRC je resetováno na 0 na začátku každé iterace, pak jsou bajty zpracovávány v tomto pořadí:

example.txt

oldCRC-Lo, oldCRC-Hi, ConnID-Lo, ConnID-Hi, SeqNo-Lo, SeqNo-Hi, Command, [Data...]

oldCRC-Lo, oldCRC-Hi, ConnID-Lo, ConnID-Hi, SeqNo-Lo, SeqNo-Hi, Command, [Data...]

oldCRC pochází z parametru startCrc (CRC předchozího rámce — viz Dědičnost níže)
ConnID je čteno z konce PDU: au8Data[size-2] (Lo) a au8Data[size-1] (Hi)
SeqNo pochází z ukazatele seqNo
Command je na au8Data[OFFS_COMMAND]
Data začíná na au8Data[OFFS_DATA]

Dědičnost CRC — dvě úrovně

Úroveň 1: Dědičnost mezi rámci (řetěz `startCrc` / `oldCRC`)

První dva bajty vložené do každého výpočtu CRC jsou CRC předchozího rámce (startCrc). To vytváří řetěz přes rámce:

$$ \begin{aligned} \text{CRC rámce } N &= f(\text{data rámce } N,\; \text{CRC rámce } N{-}1) \\ \text{CRC rámce } N{+}1 &= f(\text{data rámce } N{+}1,\; \text{CRC rámce } N) \end{aligned} $$

CRC každého rámce závisí na všech předchozích CRC rámců. Útočník nemůže přehrát starý rámec, protože by se řetěz CRC přerušil.

Parametr oldCrc se používá pro detekci kolize v cyklu do…while:

collision-avoidance.c

} while (crc == oldCrc && (bRcvDir & NEW_CRC) != 0);

} while (crc == oldCrc && (bRcvDir & NEW_CRC) != 0);

Pokud se nově vypočítané CRC náhodou rovná CRC předchozího rámce, číslo sekvence je inkrementováno (seqNo[0]++, přeskakující nulu) a CRC je přepočítáno. To pokračuje, dokud se CRC neliší od oldCrc, čímž se zajišťuje, že žádné dva po sobě jdoucí rámce nikdy nesdílejí stejné CRC — bezpečnostní požadavek pro detekovatelnost kolizí CRC.

Úroveň 2: Intra-frame dědičnost (základ `crc_common`)

V rámci jedné PDU, když payload přesahuje 10 bajtů, je vloženo více CRC (CRC₀, CRC₁, CRC₂, …) — každé chrání 2-bajtový datový segment. Klíčovým mechanismem je crc_common.

Krok 1 — Vypočítat společný základ (7 bajtů zpracováno):

crc-common.c

crc = 0;
/* zpracovat: oldCRC-Lo, oldCRC-Hi, ConnID-Lo, ConnID-Hi,
            SeqNo-Lo, SeqNo-Hi, Command */
crc_common = crc;    /* uloženo zde */

crc = 0;
/* zpracovat: oldCRC-Lo, oldCRC-Hi, ConnID-Lo, ConnID-Hi,
            SeqNo-Lo, SeqNo-Hi, Command */
crc_common = crc;    /* uloženo zde */

Tento základ zapouzdřuje všechna „hlavičková" pole: zděděné staré CRC, Connection ID, Sequence Number a Command bajt.

Krok 2 — CRC₀ (první segment, pokračující z crc_common):

crc0.c

/* pokračovat z crc_common: zpracovat Data[0], Data[1] */
/* výsledek = CRC₀  (uloženo/ověřeno na pCrc) */

/* pokračovat z crc_common: zpracovat Data[0], Data[1] */
/* výsledek = CRC₀  (uloženo/ověřeno na pCrc) */

Krok 3 — CRCᵢ pro i ≥ 1 (následující segmenty, každý restartující z crc_common):

crci.c

crc = crc_common;           /* RESTART ze sdíleného základu */
/* zpracovat: Index-Lo (i & 0xFF), Index-Hi (i >> 8),
            Data[2i], Data[2i+1] */
/* výsledek = CRCᵢ  (uloženo/ověřeno na další pozici pCrc) */

crc = crc_common;           /* RESTART ze sdíleného základu */
/* zpracovat: Index-Lo (i & 0xFF), Index-Hi (i >> 8),
            Data[2i], Data[2i+1] */
/* výsledek = CRCᵢ  (uloženo/ověřeno na další pozici pCrc) */

Struktura cyklu:

multi-crc-loop.c

while (size >= 4) {         /* každá iterace = 2 datové bajty + 2 CRC bajty */
    crc = crc_common;       /* restart ze sdíleného základu */
    /* vložit: i_lo, i_hi, data[2i], data[2i+1] */
    /* ověřit/vložit CRC na pCrc[0..1] */
    size -= 4;
    pSafeData += 4;
    pCrc += 4;
    i++;
}

while (size >= 4) {         /* každá iterace = 2 datové bajty + 2 CRC bajty */
    crc = crc_common;       /* restart ze sdíleného základu */
    /* vložit: i_lo, i_hi, data[2i], data[2i+1] */
    /* ověřit/vložit CRC na pCrc[0..1] */
    size -= 4;
    pSafeData += 4;
    pCrc += 4;
    i++;
}

Proč je indexový bajt důležitý

Každé segmentové CRCᵢ zahrnuje index $i$ (1-based, jako 2-bajtová little-endian hodnota) mezi Command a Data. To zajišťuje, že i když dva segmenty obsahují identické datové bajty, jejich CRC se budou lišit, protože index se liší. Bez indexu by prohození dvou datových segmentů zůstalo nezjištěno.

Vizualizace

Následující diagram ukazuje, jak funguje dědičnost CRC přes rámce a v rámci jedné multi-CRC PDU. Každé segmentové CRC restartuje z crc_common (sdílený základ) a CRC každého rámce se stává startCrc pro další rámec.

Zkratky použité v diagramu

Označení	Význam
`oC.Lo`, `oC.Hi`	oldCRC (`oC`) — CRC předchozího rámce, předané jako `startCrc`; rozděleno na low/high bajt
`CID.Lo`, `CID.Hi`	Connection ID (ConnID) — low/high bajt, čteno z posledních 2 bajtů PDU
`Sq.Lo`, `Sq.Hi`	Sequence Number (SeqNo) — low/high bajt čísla sekvence rámce
`Cmd`	bajt Command — opcode příkazu FSoE na offsetu `OFFS_COMMAND`
`D0`, `D1`, `D2`, …	bajty Data payloadu (začínající od `OFFS_DATA`)
`i.Lo`, `i.Hi`	index segmentu `i` (od 1, little-endian) — low/high bajt, vložen do CRCᵢ pro i ≥ 1
`N.Lo`, `N.Hi`	v rámci N+1: low/high bajt CRC₀ rámce N (který se stává oldCRC pro rámec N+1)
`CRC₀`, `CRC₁`, `CRC₂`	hodnota CRC vypočtená pro segment 0, 1, 2 — každá se vkládá (nebo ověřuje) v PDU

Společný základ (crc_common)

Datový bajt

CRC (vloženo/ověřeno)

Index

ConnID

Dědičnost mezi rámci: CRC₀ každého rámce se stává startCrc (oldCRC) dalšího rámce

Frame N−1

CRC₀: oC.Lo oC.Hi CID.Lo CID.Hi Sq.Lo Sq.Hi Cmd D0 D1

→ CRC₀ = 0xDD27 (example)

→

Frame N (startCrc = 0xDD27)

crc_common (sdílený základ pro všechny segmenty)

0x27 0xDD CID.Lo CID.Hi Sq.Lo Sq.Hi Cmd

CRC₀: (ze společného) D0 D1 CRC₀

CRC₁: (restart společného) i.Lo i.Hi D2 D3 CRC₁

CRC₂: (restart společného) i.Lo i.Hi D4 D5 CRC₂

→

Frame N+1 (startCrc = CRC₀ rámce N)

CRC₀: N.Lo N.Hi CID.Lo CID.Hi Sq.Lo Sq.Hi Cmd D0 D1

→ CRC₀ napájí Frame N+2…

CRC₀ = f( oldCRC, ConnID, SeqNo, Command, Data[0], Data[1] )
CRCᵢ = f( crc_common, Index=i, Data[2i], Data[2i+1] ) pro i ≥ 1
crc_common = f( oldCRC, ConnID, SeqNo, Command ) /* uloženo, nevysílá se */
nextFrame.startCrc = thisFrame.CRC₀

Vlevo: Frame N−1 produkuje CRC₀ = 0xDD27. Uprostřed: Frame N používá 0xDD27 jako svůj startCrc — první dva bajty vložené do každého výpočtu CRC. Společný základ (modrý) je vypočítán jednou a znovu použit pro každý segment. Každé segmentové CRC restartuje z tohoto základu, přidává svůj index a datové bajty a produkuje nezávislé CRC. Vpravo: CRC₀ rámce N se stává startCrc pro Frame N+1, čímž pokračuje řetěz.

Rozložení PDU

Rozložení bajtů PDU (rekonstruované z přístupů k polím v CalcCrc) závisí na celkové velikosti:

example.txt

size = 6  (1 datový bajt, 1 CRC):
  [Command, Data0, CRC0Lo, CRC0Hi, ConnIDLo, ConnIDHi]

size = 7..10  (2 datové bajty, 1 CRC):
  [Command, Data0, Data1, CRC0Lo, CRC0Hi, ConnIDLo, ConnIDHi]

size > 10  (multi-CRC, 2+2k datových bajtů):
  [Command, Data0, Data1, CRC0(2), Data2, Data3, CRC1(2),
   Data4, Data5, CRC2(2), ..., ConnIDLo, ConnIDHi]

size = 6  (1 datový bajt, 1 CRC):
  [Command, Data0, CRC0Lo, CRC0Hi, ConnIDLo, ConnIDHi]

size = 7..10  (2 datové bajty, 1 CRC):
  [Command, Data0, Data1, CRC0Lo, CRC0Hi, ConnIDLo, ConnIDHi]

size > 10  (multi-CRC, 2+2k datových bajtů):
  [Command, Data0, Data1, CRC0(2), Data2, Data3, CRC1(2),
   Data4, Data5, CRC2(2), ..., ConnIDLo, ConnIDHi]

ConnID je vždy na posledních 2 bajtech (au8Data[size-2..size-1])
CRC₀ je na offsetu 2 (size ≤ 6) nebo offsetu 3 (size > 6)
Každý další segment je 4 bajty: 2 data + 2 CRC
size -= 7 zohledňuje první část (ConnID 2 + CRC₀ 2 + Command 1 + Data 2), pak size -= 4 na každý další segment

Referenční hodnoty CRC

Následující referenční hodnoty byly vygenerovány věrnou transkripcí původní funkce CalcCrc a nezávisle ověřeny pomocí bit-po-bitu polynomiálního dělení dlouhým dělením (bez vyhledávacích tabulek). Všechny vstupy používají startCrc = 0x0000, seqNo = 0x0001, oldCrc = 0x0000 pokud není uvedeno jinak.

Test	size	startCrc	ConnID	Cmd	Data	CRC₀	CRC₁	CRC₂	CRC₃
1	6	0x0000	0x1234	0x01	`AB`	0x2C82	—	—	—
2	7	0x0000	0x1234	0x01	`AB CD`	0xDD27	—	—	—
3	11	0x0000	0x1234	0x01	`AB CD EF 12`	0xDD27	0x05A5	—	—
4	15	0x0000	0x1234	0x01	`AB CD EF 12 34 56`	0xDD27	0x05A5	0x93AA	—
5	7	0x0000	0x5678	0x05	`01 02`	0x82DC	—	—	—
6b	7	0xDD27	0x1234	0x01	`AB CD`	0x41F5	—	—	—
7	7	0xBEEF	0x4242	0x03	`DE AD`	0x945E	—	—	—
8	11	0x0000	0x0000	0x00	`00 00 00 00`	0xC864	0x7BC5	—	—
9	15	0x0000	0xFFFF	0xFF	`FF FF FF FF FF FF`	0x2669	0xDB40	0xCD65	—
10	19	0x0000	0xCAFE	0x02	`10 20 30 40 50 60 70 80`	0xE6BD	0x687A	0xB265	0x657C

Test 6b demonstruje dědičnost mezi rámci: používá CRC₀ z Testu 2 (0xDD27) jako svůj startCrc, produkující odlišné CRC (0x41F5) pro stejná data — ukazuje, jak řetěz dědičnosti mění CRC i když je payload identický.

Shrnutí

Mechanismus FSoE CRC má dvě vrstvy dědičnosti:

Mezi rámci: CRC₀ předchozího rámce je vloženo do CRC dalšího rámce jako první dva bajty, čímž se vytváří řetěz, který brání replay útokům. Cyklus do…while zajišťuje, že žádné dva po sobě jdoucí rámce nesdílejí stejné CRC.
Intra-frame: Pro multi-segment PDU je sdílený základ crc_common (obsahující oldCRC, ConnID, SeqNo, Command) vypočítán jednou a znovu použit jako výchozí bod pro každé segmentové CRC. Každý segment přidává svůj index a 2 datové bajty, produkující nezávislé CRC, které chrání proti přeuspořádání segmentů.

Samotný krok aktualizace je standardní MSB-first posun CRC-16 registru, ale se vstupním bajtem vloženým přes $T_3$ (tabulka $x^{40}$) místo $T_0$ (tabulka $x^{16}$), což dává každému datovému bajtu extra faktor $x^{24}$. To činí FSoE CRC vlastní variantou, neekvivalentní žádné standardní konvenci CRC-16.

Související příspěvky