Abstract
Strong Physically Unclonable Functions (PUFs) are critical for hardware security but often lack rigorous cryptanalytic evaluation due to the exponential complexity of calculating non-linearity (NL) for large challenge spaces. This paper presents the SQnL framework, which efficiently estimates NL using a heuristic homomorphicity test and the Piling-up lemma. By analyzing individual PUF instances, the framework identifies weak units that might otherwise pass standard machine learning robustness tests, providing a more comprehensive security assessment for 64-bit and 128-bit PUF architectures.
Introduction
Physically Unclonable Functions (PUFs) serve as unique hardware identifiers, leveraging manufacturing variations to create challenge-response pairs. For a PUF to be cryptographically secure, it must exhibit high non-linearity to resist linear approximation attacks. However, "Strong PUFs" with $2^{64}$ or more possible challenges pose a significant computational hurdle; traditional methods like the Walsh-Hadamard Transform require the full truth table, which is infeasible at these scales. Consequently, security evaluations often default to testing resilience against Machine Learning (ML) attacks, potentially overlooking fundamental cryptanalytic weaknesses.
The SQnL Framework
The authors propose the SQnL framework to bridge this gap. The framework operates by estimating the probability that a PUF instance fails a linear property test, rather than calculating exact NL values.
The framework consists of three main components:
- PUF Homomorphicity Test (HT): This test checks if the PUF function $f$ satisfies the property $f(\sum x_i) = \bigoplus f(x_i)$ for a set of random inputs. The failure probability ($P_t$) of this test is used to derive mathematical bounds for the instance's non-linearity.
- Piling-up Lemma Adaptation: To handle complex XOR-based compositions (e.g., XOR Arbiter PUFs), the framework utilizes the Piling-up lemma from linear cryptanalysis. This allows the estimation of a multi-stream PUF's NL by combining the estimates of its constituent parts.
- Instance-Specific Analysis: Unlike aggregate studies, SQnL evaluates individual simulated instances. This is crucial because manufacturing variations can lead to "bad" instances with low NL, even if the overall design is robust on average.
Experimental Setup
The study utilized simulated data from PyPUF, covering several architectures: Arbiter PUF (APUF), Feed-Forward APUF (FF-APUF), Bistable Ring PUF (BRPUF), and their XOR-composed variants. For validation, small-scale PUFs (up to 24 bits) were compared against exact NL values computed via Sagemath.
Key Insights and Results
The framework demonstrated high accuracy, with estimated bounds consistently capturing true NL values for smaller bit-lengths. As challenge lengths and the number of XORs ($k$) increased, the framework successfully scaled to 64-bit and 128-bit instances.
A critical finding was the "Bad Instance" Discovery: random weight variations in simulation (mimicking manufacturing) can produce instances with significantly lower NL. SQnL effectively isolates these weak units. Furthermore, the analysis revealed a surprising result regarding FF-APUFs: while often considered more ML-resilient, they actually exhibit lower non-linearity than standard APUFs of the same length, highlighting a disconnect between ML robustness and classical cryptanalytic strength.
The framework is highly efficient, providing reliable estimates with as few as $10^6$ observations—a tiny fraction of the total challenge space. The authors found that a tuple length of $t=3$ offers the best balance between accuracy and computational cost.
Conclusion and Future Work
The SQnL framework provides a scalable, computationally efficient method for quantifying the cryptanalytic strength of Strong PUFs. While high non-linearity is a necessary condition for security, the authors note it does not guarantee resilience against all ML-based modeling attacks. Future research will focus on bridging the gap between cryptanalytic NL and ML-robustness metrics and applying the framework to physical silicon data to further validate its real-world utility.
Summary updated