# 5G-Compliant Authentication Protocol for RFID
## 4 Analysis
### Active Adversaries  
An adversary, according to the assumed threat model, can intercept, replay and/or modify messages exchanged by the tag and the reader. Replaying messages from previous sessions is prevented by (a) using random numbers \(r_{i}\) and \(r_{s}\), that randomise all the computed values for that session, and (b) using MACs for integrity checks, which prevent messages being altered in transit. A more formal proof is given below. The 5G-compliant RFID protocol is secure against the alteration of the flows by an active adversary. Proof. : The proof is divided into two parts. We first prove that the flows exchanged during the initialization: \(\langle r_{i},SUPICi,PK1 Ci,PK2 Ci,AUTNi\rangle\) and \(\langle CONFi\rangle\) form sets where none of whose elements can be altered and get accepted (Lemma 3). Then, we prove that this also happens for the flows \(\langle r_{s},ARt,AUTNt\rangle\) and \(\langle RESt,CKt,IKt,INTRESt\rangle\) of the tag during the authentication (Lemma 4). The flow, in which the reader forwards \(R,AUTN\) to the tag during the authentication, is not included in the proof because it is identical to the flow in 5G-AKA. Note also that \"altered messages\" refers to the case where some parts are modified while others remain the same. The case where the entire set is replaced by another set is analyzed later, where two situations can be further distinguished, depending on whether the used set of messages are forged by an adversary, or generated by a genuine party and later replayed (replay attack). The messages \(\langle r_{i},SUPICi,PK1 Ci,PK2 Ci,AUTNi\rangle\) and \(\langle CONFi\rangle\) form a set that cannot be altered and get accepted. Proof. : (Sketch) By contradiction, assume that there exists a probabilistic polynomial time (PPT) adversary (algorithm) that is able to alter this set and get accepted. We first consider \(AUTNi\), and distinguish three cases:  
1. \(AUTNi\) is not changed and some or all of the other values are changed. This is not possible because it implies that the adversary is able to compute a collision (same output, different input) for the MAC \(AUTNi\). 2. \(AUTNi\) is changed but some or all of the other values remain unchanged. Again, this is not possible because it implies that the adversary is able to compute a valid \(AUTNi\) for a different input that will get accepted with non-negligible probability, without knowing \(k_{t}\). 3. \(AUTNi\) and the input is changed. Again the adversary cannot compute with non-negligible probability a valid \(AUTNi\) for a given input without knowing \(k_{t}\). Next consider \(CONFi\). Again, if the adversary only changes values of the input, then this will not be accepted because \(CONFi\) is an MAC. Similarly, \(CONFi\) cannot be changed and get accepted, because it cannot be computed without knowing \(k_{t}\). **Lemma 4**: _The messages \(\langle r_{s}\), \(ARt\), \(AUTNt\rangle\) and \(\langle RESt\), \(CKt\), \(IKt\), \(INTREST\rangle\) form a set that cannot be altered and get accepted._  
Again, we consider the cases of \(AUTNt\) and \(INTERSt\) separately. The first case is identical to Lemma 3, by replacing: \(AUTNi\) and the input \(\langle r_{i}\), \(SUPI\), \(PK1 Ci\), \(PK2 Ci\rangle\), by \(AUTNt\) and the input \(\langle r_{s}\), \(ARt\rangle\). The same argument applies to \(INTERSt\). In this case, we replace \(AUTNi\) and input \(\langle r_{i}\), \(SUPI\), \(PK1 Ci\), \(PK2 Ci\rangle\), by \(INTRESt\) and input \(\langle r_{s}\), \(REST,CKt\), \(IKt\rangle\). We have shown that the flows of the 5G-compliant RFID protocol cannot be distinguished from random flows by a PPT adversary \(\mathcal{A}\). This implies that \(\mathcal{A}\) cannot compute the private key \(k_{t}\) from such flows. **Corollary 1**: _An active adversary cannot obtain the private key \(k_{t}\) used to generate the flows of the 5G-compliant RFID protocol._  
We only consider efficient (PPT) adversaries \(\mathcal{A}\).