## 5 Security Analysis  
A large amount of software and abstraction can make the vehicle susceptible to cyber-attacks. Thus, MT-SOTA security remains a significant requirement for software updates over the air. As explained previously, the fundamental security primitive of the MT-SOTA is based on the security of both the signature scheme and hash function. The digital signature scheme should be strongly unforgeable. The cryptographic hash functions should satisfy the three criteria of preimage resistance, second-preimage resistance, and collision resistance. The security advantage of our proposed Merkle-tree-based digital signature consists of the insertion of another layer of security using additional hash steps to generate the root. **FactI: Security of Merkle-Tree-Based Signature**  
Given a randomly chosen software image, the probability that an adversary without knowledge of the entire tree (software image hashes) can forge a modified image with a valid signature is negligible if a cryptographic (specifically, one-wayness and collision-resistance) hash function is used to construct the tree. Proof. : Suppose that there is an adversary who knows some details about the Merkle tree (index of leaf node, number of leaf nodes, value of the root node). The first scenario would be that the attacker finds the same valid signature for a modified local software image. Finding such a signature would mean breaking the Merkle tree signature and obtaining the OEM private key. If the attacker is not able to accomplish this, it needs to find, for a given software image of a hash function, another software image with the same hash value. A hash function in which this is feasible is not second-preimage-resistant. Thus, if the hash function in use is second-preimage-resistant, the attacker will not be able to find the same signature. Thus, the Merkle-tree-based signature scheme is secure, as long as the signature is secure and the hash function used is second-preimage-resistant. **Fact2: Authentication of the individual software image**  
Given a software image intended for a specific vehicle ECU, the adversary's capability to install the image on another ECU is negligible due to the unforgeability of the digital signature. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Height** & **Max Number of Node** & **Tree Storage in Bytes** \\ \hline
1 & 2 & 96 \\
2 & 4 & 224 \\
3 & 8 & 480 \\
4 & 16 & 992 \\
5 & 32 & 2016 \\
6 & 64 & 4064 \\
7 & 128 & 8160 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Merkle tree storage size based on number of used software clusters. Proof. : Suppose that there is an adversary who manages to alter the manifest information to change the destination ECU of the updated software image, for example from ECU-A to ECU-B. The prover has used the private key associated with the public key of ECU-A. If the attacker is able to change the update process and succeed into sending the image to ECU-B, the verifier decrypts it with the public key of ECU-B and thus the verification fails. Given that OemR has a unique private/public key pair assigned to each ECU and the keys are well protected and secured, the attacker will not succeed in installing unintended software on an ECU. **Fact3: Resilience to the leakage of information**  
Given that the ECU has access to the other software images whose hashes constitute the leaf nodes of the tree, there is no need for the prover to send proof nodes (sibling path) as these can be calculated in the ECU when software clusters are local to the ECU. An adversary who does not know the details of the other software images cannot obtain any meaningful information through eavesdropping on the proposed MT-SOTA proposal. Proof 3: Since the size of the Merkle tree and the information about the software images are managed by the OEM repository and not by the image repository, there is no relationship between the signature size, structure, and size of the Merkle tree, making it impossible for the adversary to know about other software images and their hashes.