## 5 Security Analysis of the Repaired Protocol
### Impersonation, Man-in-the-Middle and Replay Attacks  
The protocol provides a sound mutual authentication between an _SN_ and an _FN_/_HN_. The adversary defined in Section 3.1 models the necessary capabilities that requires performing impersonation, man-in-the-middle, and replay attacks. The goals of this adversary are as follows: (Goal 1) Convincing either an _SN_ or a _UN_ to misbelieve that a legitimate partner is participating in a communication within the timeout period; (Goal 2) Having better strategy than the wild guess in distinguishing a session key \(k_{s}\) against a random string with the same length. We show that there is no adversary to effectively, and with non-negligible probability, achieve either of these goals.  
Goal 1 happens when either _UN_ accepts or _SN_ accepts. We separately discuss these cases.  
* The _UN_ accepts. This happens if and only if \(tid_{N}=h(id_{N}^{*},t_{N},c_{N}^{*},r_{N}^{*})\). We assume that the _SN_ does not generate a \(tid_{N}\) after \(t^{*}-\Delta T\), otherwise it violates definition of Goal 1. If this equation is true but the hash \(h(id_{N}^{*},t_{N},c_{N}^{*},r_{N}^{*})\) has never been computed, this will happen only with \(p=2^{-\text{length}(h)}\).  
Figure 4: The repaired protocol.  
If this equation is true and the hash has been computed before, we may conclude that it is not produced by a legitimate \(SN\) and \(UN\). This is due to the fact that \(id_{N}\) is unique and \(SN\) does not produce any at \(t_{N}\) and \(UN\) would never send computed \(tid_{N}\). Therefore, the only possibility is that the adversary computes the hash by itself. This happens only if the adversary has \(id_{N}\) and \(c_{N}\) which are not sent over the network. This is bounded by \(p^{2}\times q_{h}\) where \(q_{h}\) is the maximum number of the hashes that are able to query with reasonable resources.
* The \(SN\) accepts. This happens if and only if the value of the \(\beta\) is equal to \(h(x_{N}^{+},r_{N},f_{N}^{*},\eta,\mu)\). Similarly, if the hash was never computed, the probability is bounded by \(p\). If the hash is previously computed by the \(UN\), the same \(SN\) (with \(id_{N}^{*}\)) has already sent a login request with \(r_{N}^{*}\). Since \(r_{N}^{*}\) is randomly chosen, this happens only with \(p\times q_{E}\), where \(q_{E}\) is the total number of the sessions executed by the \(SN\). Otherwise, the adversary should correctly guess \(id_{N}^{*}\) and \(c_{N}\), which happen only with \(p^{2}\times q_{h}\).  
To sum up, the occurrence of Goal 1 has a probability lower than \((q_{E}+2)p+2q_{h}p^{2}\), where \(p=2^{-\text{length}(h)}\), \(q_{E}\) is the total number of the sessions executed by the \(SN\), and \(q_{h}\) is the total number of the hashes that are able to be computed by the adversary with reasonable resources. This number is negligible when the length of the hash is large.  
Goal 2 happens only when the \(UN\) accepts and the hash \(h(id_{N},r_{N},f_{N},x_{N})\) has been computed by the adversary since \(k_{s}\) is never transmitted. However, \(id_{N}\) and \(x_{N}\) are both secret. A correct guess of this variable is bounded by \(p^{2}\times q_{h}\).  
Considering the probability to concurrently achieve the both Goals 1 and 2, an attacker may cast as an impersonation attack, a man-in-the-middle attack, or a replay attack has a probability less than \((q_{E}+2)p+3q_{h}p^{2}\).