# A Secure and Efficient Authentication Scheme for Fog-Based Vehicular Ad Hoc Networks
## 5 Security Analysis
### Formal Analysis
#### 5.1.7 Real-or-Random Model
\begin{table}
\begin{tabular}{p{142.3 pt} p{142.3 pt}} \hline \hline
**Query** & **Description** \\ \hline \multirow{3}{*}{\(Execute(\textit{Ta}_{V_{i}^{t}}^{k_{1}},\textit{Ta}_{FN_{i}}^{k_{2}},\textit{Ta }_{CS}^{k_{3}})\)} & \(A\) can eavesdrop messages transmitted via public channels between \(\textit{Ta}_{V_{i}^{t}}^{k_{1}},\textit{Ta}_{FN_{i}}^{k_{2}}\), and \(\textit{Ta}_{CS}^{k_{3}}\). \(A\) can perform passive attacks with these messages. \\ \hline \multirow{3}{*}{\(CorruptSC(\textit{Ta}_{V_{i}^{t}}^{k_{1}})\)} & \(A\) can obtain secret values stored in the stolen smart card of \(\textit{Ta}_{V_{i}^{t}}^{k_{1}}\) by performing this query. \\ \cline{2-3}  & By performing this query, \(A\) can send a message, \(\textit{Msg}\), to a participant, \(\textit{Ta}_{x}^{k_{n}}\). Furthermore, \(A\) can obtain a response message from a participant, \(\textit{Ta}_{x}^{k_{n}}\). \\ \hline \multirow{3}{*}{\(Test(\textit{Ta}_{x}^{k_{n}})\)} & In the last game, \(A\) performs this query. When this query is performed, an unbiased coin, \(c\), is tossed. The head represents \(1\) and the tail represents \(0\). If \(c=1\), then \(\textit{Ta}_{x}^{k_{n}}\) returns the session key, \(SK\); If \(c=0\), then \(\textit{Ta}_{x}^{k_{n}}\) returns a random number. In other cases, \(\textit{Ta}_{x}^{k_{n}}\) returns \(NULL\). If \(A\) correctly guesses that the returned value is the session key, \(SK\), \(A\) wins the game. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Queries in the real-or-random (RoR) model. \[AVTG_{WIGM_{1}}(A)=AVTG_{WIGM_{0}}(A). \tag{3}\]
* \(GM_{2}\): In this game, \(A\) performs the _Send_ and _Hash_ queries to calculate the session key, \(SK\). To obtain the values needed for calculating the session key, \(SK\), \(A\) must determine the hash collision using messages from the public channel. Thus, we obtain the following equation due to the birthday paradox [35]: \[|AVTG_{WIGM_{2}}(A)-AVTG_{WIGM_{1}}(A)|\leq\frac{q_{hq}^{2}}{2|Hash|}.\] (4)
* \(GM_{3}\): In this game, \(A\) tries to compute \(SK\) with the messages \((D_{1}=R_{1},RID_{i},Q_{i},ID_{j})\), \((D_{2}=R_{1},RID_{i},R_{2},r_{2}R_{1},L_{j},ID_{j})\), \((D_{3}=K_{ij},R_{3},r_{3}R_{1},Auth_{j})\), and \((D_{4}=K_{ij},r_{2}R_{3},\)\(Auth_{i})\). However, the session key, \(SK\), consists of \(R_{i-j-cs}=r_{3}\cdot r_{2}\cdot r_{1}\cdot P\), derived from the ECCDH problem. Therefore, we obtain the following inequality: \[|AVTG_{WIGM_{3}}(A)-AVTG_{WIGM_{2}}(A)|\leq Adv_{M}^{ECC}(A).\] (5)
* \(GM_{4}\): In the last game, \(A\) performs the \(CorruptSC\) query and extracts \((N_{i}^{*},M_{i},s_{0})\) from \(SC\). However, \(A\) cannot compute the session key, \(SK\), because the smart card values are masked with a hash function using \(ID_{i}\) and \(PSW_{i}\). Thus, we obtain the following inequality using the Zipf law [36]: \[|AVTG_{WIGM_{4}}(A)-AVTG_{WIGM_{3}}(A)|\leq max\{C^{\prime}s_{send}^{^{\prime} },\frac{q_{send}}{2^{l}}\}.\] (6)  
At the end of all games, \(A\) must guess whether or not \(r\) is correct from the _Test_ query. Therefore, we obtain the following equation:  
\[AVTG_{WIGM_{4}}(A)=\frac{1}{2}. \tag{7}\]  
We derive the following equation from Equation (2) and (3):  
\[ \begin{split}\frac{1}{2}Advp(A)&=|AVTG_{WIGM_{0}}( A)-\frac{1}{2}|\\ &=|AVTG_{WIGM_{1}}(A)-\frac{1}{2}|.\end{split}  \tag{8}\]  
We also compute the following equation from Equations (7) and (8):  
\[\frac{1}{2}Advp(A)=|AVTG_{WIGM_{1}}(A)-AVTG_{WIGM_{4}}(A)|. \tag{9}\]  
We apply the triangular inequality to the Equation (9). \[ \begin{split}\frac{1}{2}Advp(A)&=|AVTG_{WIGM_{1}} (A)-AVTG_{WIGM_{4}}(A)|\\ &\leq|AVTG_{WIGM_{1}}(A)-AVTG_{WIGM_{3}}(A)|\\ &+|AVTG_{WIGM_{3}}(A)-AVTG_{WIGM_{4}}(A)|\\ &\leq|AVTG_{WIGM_{1}}(A)-AVTG_{WIGM_{2}}(A)|\\ &+|AVTG_{WIGM_{2}}(A)-AVTG_{WIGM_{3}}(A)|\\ &+|AVTG_{WIGM_{3}}(A)-AVTG_{WIGM_{4}}(A)|\\ &\leq\frac{q_{hq}^{2}}{2|Hash|}+Adv_{M}^{ECC}(A)+max\{C^{\prime}s _{send}^{^{\prime}},\frac{q_{send}}{2^{l}}\}.\end{split}