# A Lightweight and Practical Anonymous Authentication Protocol Based on Bit-Self-Test PUF
## 4 Formal Security Analysis
### Security Analysis  
First, we consider an adversary \(A\) who has control over the radio communication channel between the device \(D\) and the server \(S\). \(A\) is required to model the following query methods in polynomial time. * **Transmit**\((S,M_{1},A_{2},M_{3})\): After \(A\) receives \(M_{1}\) from \(S\), \(A\) sends message \(A_{2}\) to \(S\) and receives message \(M_{3}\) from \(S\);
* **Enquiry**\((D,A_{1},M_{2},A_{3})\): \(A\) sends \(A_{1}\) to the device, receives \(M_{2}\) from the device, and then sends \(A_{3}\) to the device;
* **Execute**\((D,S)\): When executing a protocol between \(D\) and \(S\), \(A\) needs to intercept this channel;
* **Blocking**\((A)\): \(A\) is required to block a part of the protocol and interrupt the synchronization between \(D\) and \(S\);
* **Reveal**\((D)\): This query simulates the ability of the adversary to compromise the device and obtain confidential information stored in its memory. \(A\) can invoke the Transmit, Enquiry, Execute, and Blocking queries multiple times, but can only invoke the Reveal query once, since obtaining confidential information stored in the device memory can lead to physical destruction of the device chip. **Lemma 1**. : _The proposed protocol can resist modeling attacks or machine learning._  
The modeling attack on the PUF is predicated on obtaining a sufficient number of CRPs, whereas, in the proposed protocol, c and h are not transmitted in plaintext during protocol execution; the response r is encrypted using a non-linear PRF when transmitted in the communication channel, and the attacker cannot have the opportunity to obtain enough CRPs on the communication channel, which makes it exponentially more difficult for an attacker to simulate the mapping relationship between c and r, and modeling attacks on PUF become particularly difficult [25]. Moreover, the attacker who wants to obtain enough CRPs to perform machine learning and modeling attacks on the PUF can only obtain c and h stored in the NVM by probing the chip's memory using the Reveal query, but this will simultaneously destroy the PUF circuit integrated into the chip and change its mapping relationships, so even if the attacker obtains c and h, they will not be able to recover the response r. Thus, the proposed protocol based on BST-PUF has sufficient resistance to modeling attacks or machine learning. **Lemma 2**. : _The secret data on the device will not be compromised in the proposed authentication protocol, even if the Reveal query is invoked._The device does not need to store important information about the key, and the \(k_{1}\) associated with response parameters is used as a shared key for both parties, which is generated with \(c_{1}\) and \(h_{1}\) as the input of the _KEY.Rec_ in real time. Thus, if adversary A uses the Reveal query to obtain secret information on the device's memory, it may only be able to steal helper data \(h_{1}\) and challenge \(c_{1}\). According to Lemma 1, we know that adversary A cannot recover the response \(r_{1}\) and thus cannot generate the key \(k_{1}\). Therefore, the leakage of the challenge \(c_{1}\) and helper data \(h_{1}\) does not lead to the leakage of the response \(r_{1}\). Moreover, any physical means of accessing the PUF will alter its CRP mapping, ultimately invalidating the device's legal identity. The adversary A invokes the Reveal query and also fails to associate the device's identity. Because the proposed protocol uses temporary ID, the adversary cannot associate the device by obtaining ID information. Moreover, because the data used for authentication at the device are updated after each successful authentication, and the challenge is randomly generated by the TRNG, the key information must be known if adversary \(A\) wants to associate the identity of the device. However, even if the Reveal query is invoked, the adversary \(A\) cannot obtain the key information (Lemma 1). Proof.