Security Analysis of Arbiter PUF and Its Lightweight Compositions Under Predictability Test

Phuong Ha Nguyen, Durga Prasad Sahoo, Rajat Subhra Chakraborty, Debdeep Mukhopadhyay

TL;DR

This paper introduces a new statistical test, HDT(e, t), to better evaluate the unpredictability of Physically Unclonable Functions (PUFs), a crucial security property. The authors demonstrate that existing tests are insufficient and that their new test can reveal vulnerabilities in common PUF designs like Arbiter PUFs, leading to a more robust security analysis.

What Problem Does This Paper Address?

Physically Unclonable Functions (PUFs) are hardware security primitives that leverage unique manufacturing variations to create device-specific keys. A critical security property for PUFs is unpredictability, meaning an adversary shouldn't be able to predict a PUF's response to a given challenge based on previously observed challenge-response pairs (CRPs). While existing tests like the Hamming Distance Test (HDT(t)) and Propagation Criteria (PC(t)) aim to measure this unpredictability, this paper argues they are insufficient. The authors show that even if these tests pass (indicating an average output transition probability of 0.5), an adversary might still exploit specific patterns to predict responses. This leaves PUF designs vulnerable to attacks, especially in applications like authentication and secure key generation.

Methods

The core contribution of this paper is the introduction of a new statistical test called HDT(e, t). This test is a refinement of existing methods, specifically considering a "mismatch pattern vector" e (representing the differences between two challenge bits) along with the Hamming distance t between them. The authors propose that for a PUF to be truly unpredictable, the HDT(e, t) value should be close to 0.5 for all possible mismatch patterns e and Hamming distances t.

They provide a comprehensive analytical discussion of HDT(e, t), HDT(t), and PC(t) for three prominent PUF designs:

  • Arbiter PUF (APUF): A classic, low-complexity PUF.
  • XOR APUF: A composition of multiple APUFs to enhance security.
  • Lightweight Secure PUF (LSPUF): Designed with an input network to improve security.

Furthermore, the paper develops an Adaptive Chosen-Challenge Attack (ACCA) based on the HDT(e, t) test. This attack allows an adversary to predict responses to unknown challenges by strategically choosing a "best" pattern e with a poor HDT(e, t) value and querying the PUF with a related challenge.

Datasets

Not discussed in the paper. The authors use simulated and FPGA-implemented PUF instances for evaluation.

Key Insights and Ideas

  • HDT(e, t) is a more general and powerful test: The paper demonstrates that if a PUF passes the HDT(e, t) test, it automatically satisfies HDT(t) and PC(t), but the reverse is not true. This highlights the limitations of the older tests.
  • Average predictability doesn't guarantee security: Even if a PUF exhibits an average output transition probability of 0.5 (passing HDT(t) and PC(t)), specific mismatch patterns e can still have probabilities far from 0.5, revealing exploitable information.
  • LSPUF's input network is not a silver bullet: While designed to improve unpredictability, the input network of LSPUF doesn't fully prevent attacks based on the HDT(e, t) property, particularly for certain patterns.
  • Challenge size matters for attack effectiveness: The ACCA attack's prediction accuracy generally improves with larger challenge sizes, indicating that longer PUFs might be more vulnerable to this type of statistical attack.
  • FPGA implementations show poorer HDT(e, t) than simulations: Experimental results indicate that real-world FPGA implementations of PUFs tend to have worse HDT(e, t) values compared to their simulated counterparts, suggesting that noise and manufacturing variations can exacerbate unpredictability issues.

Key Results

  • The proposed HDT(e, t) test is shown to be superior to HDT(t) and PC(t) in identifying statistical weaknesses in APUF, XOR APUF, and LSPUF designs.
  • An ACCA attack is demonstrated, which can predict PUF responses with high accuracy by exploiting poor HDT(e, t) values. For instance, the prediction accuracy for simulated APUFs can reach over 97% for larger challenge sizes.
  • Theoretical analysis and experimental validation (simulations and FPGA implementations) confirm the findings for APUF, XOR APUF, and LSPUF.
  • The paper provides analytical expressions for HDT(e, t) for APUF and XOR APUF.

Limitations and Future Work

  • Reliability of FPGA PUFs: The paper notes that FPGA-based PUFs are not 100% reliable, and while they use majority voting to mitigate this, it can still influence HDT(e, t) values. The authors suggest that while noise affects HDT(e, t), the effect is not significant unless reliability is very poor.
  • Computational complexity of HDT(t) and PC(t): Computing HDT(t) and PC(t) is described as "compute-intensive," especially for larger challenge sizes, limiting exhaustive analysis.
  • Future Work: The authors state their future work will be directed at utilizing the concepts developed in this paper to provide a testing and evaluation methodology for the unpredictability property of PUF designs in the context of statistical attacks. They also suggest modifying the LSPUF input network to achieve ideal HDT(e, t) values.

Summary updated

BibTeX
@article{nguyen2017security,
  author = {Phuong Ha Nguyen and Durga Prasad Sahoo and Rajat Subhra Chakraborty and Debdeep Mukhopadhyay},
  title = {{Security Analysis of Arbiter PUF and Its Lightweight Compositions Under Predictability Test}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2017},
}

Loading related content...

Figure