The Cyber-Physical Architecture of vehicles is composed of sensors, actuators, and electronic control units all communicating over shared communication buses. For historical reasons the internal communication buses, as the Controller Area Network (CAN), do not implement security mechanisms; the communications are assumed to be “trusted.” Recently these trusted relations have been challenged and leveraged to launch cyber-physical attacks against modern vehicles. As a result, it becomes urgent to enhance the security features of vehicles and notably the robustness of the CAN bus which represents an important channel of attacks.

In this work we develop identifier randomization procedures whose aim is to protect the CAN protocol from reverse-engineering, replay, and injection attacks. The idea behind this proposition is to constantly change the message identifiers in a random fashion in a way that both sender and receiver can recover the original message identifier but not the adversary. We present the main challenges of the CAN-ID randomization solution, we highlight the weaknesses of state-of-the-art solutions presented in other scientific papers, and we propose and study candidate solutions to overcome these weaknesses. To compare our solutions to state-of-the-art solution, we propose to use the entropy and the conditional entropy as a metrics of security. Results show that the randomization functions that we propose outperform the state-of-the-art solution in terms of both entropy and conditional entropy.

Authors and Affiliations

1. Télécom ParisTech, Paris, France

   Khaled Karray, Jean-Luc Danger & Sylvain Guilley

2. Secure-IC S.A.S., Cesson-Sévigné, France

   Jean-Luc Danger

3. Secure-IC, Paris, France

   Sylvain Guilley

4. École normale supérieure, Paris, France

   Sylvain Guilley

5. PSA-GROUPE, Paris, France

   M. Abdelaziz Elaabid

Corresponding author

Correspondence toKhaled Karray.

Editors and Affiliations

1. İstinye University, İstanbul, Turkey

   Çetin Kaya Koç

2. Nanjing University of Aeronautics and Astronautics, Nanjing, China

   Çetin Kaya Koç

3. University of California Santa Barbara, Santa Barbara, CA, USA

   Çetin Kaya Koç

Appendix

Letid_o be a random variable representing original identifiers whose outcome isid₁,id₂, …,id_N with probabilitiesP(id₁),P(id₂), …,P(id_N). We consider a second random variableid_r representing randomized identifiers whose outcome is in [0, 2ⁿ − 1].

1.1Entropy of Fixed Mapping

The entropy of the fixed mapping solutions (IA-CAN, equal intervals, frequency intervals) is the following:

• IA-CAN:H_IA-CAN(id_r) = H(id_o) + a

• Equal Intervals:H_EI(id_r) = H(id_o) + n −log₂(N)

• Frequency Intervals:H_FI(id_r) = n

Proof

According to the fixed mapping randomization functions (IA-CAN, equal intervals, frequency intervals), each identifierid_i is randomized over a fixed intervalI_i of widthW(I_i). We begin by computing the probability that the random variableid_r takes the valuex ∈ [0, 2ⁿ]:

The conditional probability ofid_r knowing the original identifierid_o = id_i:

Since the intervalsI_i are nonoverlapping:\(\forall x \in I_i, \forall j \neq i \rightarrow 1_{I_j} (x) = 0 \)

We can thus simplify the expression:\(\forall x \in I_i, \forall j \neq i \rightarrow \sum _{j =1}^{N} P(id_j) \frac {1_{I_j} (x)}{W(I_j)} = P(id_i) \frac {1_{I_i} (x)}{W(I_i)} \)

• IA-CAN entropy: ∀i ∈ [1,N],W(I_i) = 2^a

  $$\displaystyle \begin{aligned}H(id_r) = \sum_{i=1}^N \sum_{x \in I_i } P(id_i) \frac{1 }{2^a} \times \log_2 \left(\frac{1}{P(id_i) \frac{1}{2^a}}\right) = H(id_o) + a\end{aligned}$$

• Equal interval entropy:\(\forall i \in [1,N],\ W(I_i) = \frac {2^n}{N}\)

  $$\displaystyle \begin{aligned}H(id_r) = \sum_{i=1}^N \sum_{x \in I_i } P(id_i) \frac{1}{\frac{2^n}{N}} \times \log_2 \left(\frac{1}{P(id_i) \frac{1}{\frac{2^n}{N}}}\right) = H(id_o) + n - \log_2(N)\end{aligned}$$

• Frequency interval entropy: ∀i ∈ [1,N],W(I_i) = 2ⁿ × P(id_i)

  $$\displaystyle \begin{aligned}H(id_r) = \sum_{i=1}^N \sum_{x \in I_i } P(id_i) \frac{1}{ 2^n \times P(id_i)} \times \log_2 \left(\frac{1}{P(id_i) \frac{1}{2^n \times P(id_i)}}\right) = n\end{aligned}$$

□

1.2Conditional Entropy of Fixed Mapping

The conditional entropy of randomized identifiers knowing the original identifiers of the fixed mapping solutions (IA-CAN, equal intervals, frequency intervals) is the following:

• IA-CAN:H_IA-CAN(id_r|id_o) = a

• Equal Intervals:H_EI(id_r|id_o) = n −log₂(N)

• Frequency Intervals:H_FI(id_r|id_o) = n − H(id_o)

Proof

□

1.3Entropy of Dynamic Intervals

Let\(id_o^t\) be a Markov chain over the space of original identifiers (id₁,id₂, …id_N). And the matrix M presented in Eq. (25) be its transition matrix. Letid_r be the random variable over [0, 2ⁿ − 1], generated using the dynamic interval randomization strategy applied to\(id_o^t\). We haveH_DI(id_r) = n

Proof

where\(W(I_{i,j})= P(id_j^{t+1} | id_i^t) \times 2^{n} is\ the\ width\ of\ the\ interval\ I_{i,j}\)

\(\forall x \in [0,2^n -1 ], \sum _j^N 1_{I_{i,j}} (x) = 1\)

□

1.4Entropy of Arithmetic Masking

Proof

□

1.5Conditional Entropy of Arithmetic

The arithmetic masking conditional entropy is:

Proof

□

1.6Fixed Mapping Optimality Proof

If we adopt a fixed mapping randomization strategy, the optimal solution in terms of conditional entropy is the frequency interval solutions.

Proof

In the context of fixed mapping, we want to find the best decomposition of intervals that maximizes the conditional entropy. We previously showed that the conditional entropy of all fixed mapping solutions can be expressed asH(id_r|id_o) =∑_{i ∈ [1,N]}P(id_i) ×log₂(W_i), whereI_i is the randomization interval ofid_i of widthW(I_i). For the fixed mapping solutions, the intervals are nonoverlapping. Besides the width of each intervalI_i is positive (W(I_i) ≥ 0) and their sum equals 2ⁿ. Thus we define the following problem:

Subject to the following constraints:

To find the solution to this problem, we use the Lagrangian multiplier:

and solve the equation system:\(\frac {\partial \mathcal {L} }{\partial W_i} = 0, \quad\forall i \in [1,N]\)

We have:\(\frac {\partial H} {\partial W_i} = P(id_i) \times \frac {1} {W_i} \) and\(\frac {\partial h_0}{\partial W_i} = 1\) and\(\frac {\partial h_j}{\partial W_i} = -1\) if (i = j), 0 otherwise

Resolving this system of equations gives:

Hence:

□

Reprints and permissions

© 2018 Springer Nature Switzerland AG

Policies and ethics