# PUF and Chaotic Map-Based Authentication Protocol for Underwater Acoustic Networks
## 4 Formal Security Analysis
\(A\) is allowed to execute multiple Execute and Send queries. The Test query is permitted to execute at most once. We identified \(q_{se}\), \(q_{h}\), \(q_{Send}\), and \(q_{Exe}\) as the execute numbers of symmetric encryption, hash operation, Send, and Execute queries, respectively. \(l_{se}\), \(l_{h}\), \(n\), and \(l_{pw}\) are the lengths of the output of symmetric encryption, hash operation, transcript, and password, respectively. The advantage of breaking \(\mathcal{P}\) by \(A\) in PPT is:\[Adv_{\mathcal{P}}^{A}\leq\frac{q_{\mathcal{S}e}^{2}}{2^{l_{\mathcal{N}}}}+\frac{q_{ \mathcal{H}}^{2}}{2^{l_{\mathcal{N}}}}+\frac{\left(q_{\mathcal{S}end}+q_{ \mathcal{E}xe}\right)^{2}}{n}+\frac{q_{\mathcal{S}end}}{2^{l_{\mathcal{P}}w-1}}+ 2 Adv_{A}^{CMDLP}\]  
Proof. : We assume that the adversary \(A\) tends to break the scheme \(\mathcal{P}\) in the probabilistic polynomial time (PPT). Meanwhile, we define games, denoted as \(Game_{i}(0\leq i\leq 4)\), to simulate multiple attacks launched by \(A\). According to \(Game_{i}\), the event \(Ev_{i}(0\leq i\leq 4)\) represents that \(A\) breaks \(\mathcal{P}\) in \(Game_{i}\). The games are defined as:  
\(Game_{0}\): This game simulates the real attack launched by \(A\). First, \(A\) guesses the random bit \(r\); hence, we have:  
\[Adv_{\mathcal{P}}^{A}=|2\mathrm{Pr}[Ev_{0}]-1| \tag{5}\]  
\(Game_{1}\): This game simulates the eavesdropping attack. \(A\) executes multiple Execute queries and at most one Test query. After obtaining the output of the Test query, \(A\) has to figure out if the output is the session key according to the captured transcripts, \(\{K_{U},M_{5},M_{7},M_{9},M_{10},M_{11},M_{13},T_{i}\}\). Here, \(K_{U}=T_{ru}(x)mod\ q\), \(M_{5}=E_{K_{U-G}}(id_{i}\parallel Sid_{j}\parallel rug\parallel M_{4})\), \(M_{7}=E_{S_{j}}\left(h(id_{i}\parallel r)\parallel Gid_{k}\parallel Sid_{j} \parallel K_{U}\parallel T_{2}\right)\), \(M_{9}=T_{rs}(x)mod\ q\), \(M_{10}=h(Gid_{k}\parallel Sid_{j}\parallel SK\parallel M_{9}\parallel T_{3})\), \(M_{11}=h(S_{j}\parallel M_{9}\parallel M_{10}\parallel T_{3}\parallel h(id_{ i}\parallel r))\), \(M_{13}=E_{rug}(r\parallel M_{12})\), and timestamps. \(SK=h\left(T_{rs}(K_{U})\parallel K_{U}\parallel M_{9}\parallel Gid_{k} \parallel Sid_{j}\parallel h(id_{i}\parallel r)\right)=h\left(T_{ru}(M_{9}) \parallel K_{U}\parallel M_{9}\parallel Gid_{k}\parallel Sid_{j} \parallel h(id_{i}\parallel r)\right)\). This session key is based on CMDLP, and \(A\) cannot compute \(SK\) according to the messages or figure out the relationship between the session key and the transcripts because the one-way hash function, random numbers, and timestamps are used. Therefore, we have:  
\[Pr[Ev_{0}]=Pr[Ev_{1}] \tag{6}\]  
\(Game_{2}\): This game simulates \(A\) and executes the Execute and Send queries to launch the collision attacks among transmitted messages. These messages are symmetric encrypted or hashed. According to the birthday paradox, the probability of collision of the symmetric encryption is \(\frac{q_{\mathcal{S}e}^{2}}{2^{l_{\mathcal{N}}+1}}\). The probability of hash collision is \(\frac{q_{\mathcal{H}}^{2}}{2^{l_{\mathcal{N}}+1}}\). The collision probability of transcripts is \(\frac{\left(q_{\mathcal{S}end}+q_{\mathcal{E}xe}\right)^{2}}{2^{l_{\mathcal{N} }}}\). Therefore, we have:  
\[Pr[Ev_{2}]-Pr[Ev_{1}]\leq\frac{q_{\mathcal{S}e}^{2}}{2^{l_{\mathcal{N}}+1}}+ \frac{q_{\mathcal{H}}^{2}}{2^{l_{\mathcal{N}}+1}}+\frac{\left(q_{\mathcal{S} end}+q_{\mathcal{E}xe}\right)^{2}}{2n} \tag{7}\]  
\(Game_{3}\): This game simulates that after the Corrupt query is executed, [PERSON] launches guessing attacks on the password. [PERSON] can obtain \(\{h(. ),\)\(M_{0},\)\(M_{1}\}\) stored in the smart card. Here, \(M_{0}=T_{rk}(x)\ mod\ q\) and \(M_{1}=h(id_{i}\parallel G_{k})\bigoplus h(id_{i}\parallel pw_{i})\).