Modeling Attack Security of Physical Unclonable
Functions based on Arbiter PUFs
vorgelegt von
Master of Science (SUNY)
Nils Wisiol
ORCID: 0000-0003-2606-614X
an der Fakultät IV – Elektrotechnik und Informatik
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
– Dr. rer. nat. –
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr.-Ing. Jan Nordholz
Gutachter: Prof. Dr. Jean-Pierre Seifert
Gutachter: Prof. Dr. Marian Margraf
Gutachter: Prof. Dr. Stefan Katzenbeisser
Gutachter: Prof. Debdeep Mukhopadhyay, Ph.D.
Tag der wissenschaftlichen Aussprache: 25. April 2022
Berlin 2022
The concept of Physical Unclonable Functions (PUFs) is an attempt to base cryptog-
raphy on physical possession. This is in contrast to conventional cryptography, where
the essential difference of participants in a cryptographic protocol is their knowledge of
secret information such as keys and nonces.
The literature has a rich body of suggestions for the realization of PUFs. This thesis
explores designs of variants and compositions of the Arbiter PUF, which has been in-
troduced in 2002 as a CMOS-compatible, electrical PUF design, and has received much
research attention since then, albeit being insecure with respect to modeling attacks.
After revisiting modeling attacks on the Arbiter PUF and XOR Arbiter PUF, we
demonstrate attacks against the Lightweight Secure XOR Arbiter PUF, Feed-Forward
Arbiter PUF, and the Interpose PUF. We introduce two novel PUF designs, the Beli PUF
and the LP-PUF, and analyze their security against modeling attacks. We concluding
that the LP-PUF is resilient against currently known modeling attacks.
Physical Unclonable Functions (PUFs) sind ein Versuch, Kryptographie auf der Ba-
sis von physikalischem Besitz aufzubauen, anstatt, wie bisher üblich, Teilnehmer eines
kryptographischen Protokolls anhand ihrer Kenntnis oder Unkenntnis eines kryptogra-
phischen Geheimnisses wie beispielsweise Schlüsseln oder Nonces zu unterscheiden.
In der Literatur gibt es viele Vorschläge für die Implementierung von PUFs. Diese
Dissertation untersucht PUF Designs, welche auf Variationen und Kombinationen des
Arbiter PUF Designs beruhen. Arbiter PUFs wurden 2002 als CMOS-kompatibles, ele-
krtisches PUF Design vorgestellt und haben in der Wissenschaft viel Aufmerksamkeit
erhalten, wenn auch die Arbiter PUF unsicher hinsichtlich Modellierungsangriffen ist.
Nach der Vorstellung bisheriger Modellierungsangriffe auf die Arbiter PUF und XOR
Arbiter PUF zeigen wir Angriffe auf die Lightweight Secure XOR Arbiter PUF, Feed-
Forward PUF und Interpose PUF. Anschließend stellen wir zwei neue PUF Designs, die
Beli PUF und die LP-PUF vor und untersuchen ihre Sicherheit gegen Modellierungs-
angriffe. Wir folgern, dass die LP-PUF resilient gegen bekannte Modellierungsangriffe
ist.
Contents
1. Introduction 5
2. Physical Unclonable Functions 9
2.1. Security Properties and Metrics . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2. AttackerModel................................. 12
2.3. ModelingAttacks................................ 12
2.3.1. Machine Learning Attacks . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.2. Specialized Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.3. Provable Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4. HardwareSecurity ............................... 14
3. XOR Arbiter PUF 16
3.1. ArbiterPUF .................................. 16
3.2. XORArbiterPUF ............................... 18
3.3. Metrics ..................................... 20
3.3.1. Systematic Bias of XOR Arbiter PUFs . . . . . . . . . . . . . . . . 20
3.3.2. Implementation............................. 23
3.4. Logistic Regression Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.5. PhysicalAttacks ................................ 28
3.6. Neural Network Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6.1. Revisited: Santikellur et al. . . . . . . . . . . . . . . . . . . . . . . 29
3.6.2. Revisited: Aseeri et al. . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.6.3. Revisited: Mursi et al. . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6.4. Comparison .............................. 40
3.7. Arbitrarily Large XOR Arbiter PUFs . . . . . . . . . . . . . . . . . . . . . 41
3.7.1. Stability................................. 42
3.7.2. ArbiterPUF .............................. 43
3.7.3. Majority Vote Arbiter PUF . . . . . . . . . . . . . . . . . . . . . . 44
3.7.4. XOR Arbiter PUF . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.7.5. Number of Votes Required . . . . . . . . . . . . . . . . . . . . . . . 48
3.7.6. Simulation................................ 50
3.8. Reliability-Based Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4. XOR Arbiter PUFs with Input Transformation 53
4.1. Input Transformations: Classic vs. Random . . . . . . . . . . . . . . . . . 53
4.1.1. Pseudorandom Input Transformation . . . . . . . . . . . . . . . . . 54
4.1.2. LocalMinima.............................. 55
3
4.2. Input Transformations: Lightweight Secure . . . . . . . . . . . . . . . . . 55
4.2.1. Feature Vector Correlation . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.2. ImprovedAttack ............................ 58
4.3. PermutationPUF................................ 60
5. Interpose PUF 62
5.1. SplittingAttack ................................ 63
5.1.1. Initial Modeling of the Lower Layer via Random Interpose Bits . . 63
5.1.2. Modeling of the Upper Layer . . . . . . . . . . . . . . . . . . . . . 65
5.1.3. Divide-and-Conquer Attack . . . . . . . . . . . . . . . . . . . . . . 67
5.2. Results and Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 68
5.3. Neural Network Splitting Attack . . . . . . . . . . . . . . . . . . . . . . . 69
5.4. Variants of the Interpose PUF . . . . . . . . . . . . . . . . . . . . . . . . 71
5.4.1. Design Details and Motivation . . . . . . . . . . . . . . . . . . . . 71
5.4.2. Empirical Results of Deep Learning Modeling Attacks . . . . . . . 75
6. Feed-Forward Arbiter PUF 77
6.1. Design...................................... 77
6.2. Evolution Strategies Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.3. Neural Network Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7. Beli PUF 82
7.1. Design ..................................... 82
7.2. Model Based on Additive Delay Model . . . . . . . . . . . . . . . . . . . . 83
7.3. Implementation and Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.4. GenericMLPAttack.............................. 87
7.5. Specialized Neural Network Attack . . . . . . . . . . . . . . . . . . . . . . 87
8. LP-PUF 91
8.1. Design ..................................... 91
8.2. Metrics ..................................... 93
8.3. SplittingAttack ................................ 95
8.4. ReliabilityAttack ............................... 96
8.5. MLPAttack .................................. 98
8.6. Limitations ................................... 99
9. pypuf: Python Software Library for PUF Research 101
10.Conclusion 102
Bibliography 105
A. Arbiter PUF Additive Delay Model 114
B. Permutation PUF 116
4
1. Introduction
In all cryptographic applications deployed today, what distinguishes the legitimate user
from an adversary is the knowledge of secret information, usually called the secret key.
Such secret keys are found everywhere where cryptography is used, including in comput-
ers of microscopic scale embedded in digital door keys, credit cards, and passports. As
cryptographic algorithms and implementations matured over the years, attacks based on
weaknesses of the used ciphers and software code became harder, and gaining access to
the secret key itself became an important attack strategy, as a revealed secret key causes
all security guarantees of the employed scheme to collapse [AK96; Mah97; KK99].
To remove this weakness, a branch of research on Physical Unclonable Functions
(PUFs) emerged [Pap+02], where the difference of the legitimate user and adversary
is not defined by knowledge, but by possession of a physical object. The physical ob-
ject, called PUF token, is assumed to exhibit highly individual physical behavior when
prompted with an electric or optical input. Further, it is assumed to be (physically) un-
clonable, meaning that it is inherently impossible to produce two exactly identical tokens.
The envisioned secret-free cryptography shall be based on this unique response behavior
of each individual unclonable token.
While such PUF-based, secret-free cryptography is by definition immune against at-
tacks that recover any secret key, it may be possible to study the individual behavior of a
PUF token and extrapolate its behavior using a mathematical model, in which case it is
impossible for a remotely connected party to tell original PUF token and mathematical
model apart. In this case, the security of any cryptographic application would collapse,
just like in the case of a leaked secret key.
An important tool to create such models from observed behavior is machine learning,
a highly parameterized and generic approach to create predictions from observed data by
using specialized software. In the past two decades, machine learning has emerged as the
tool of choice for PUF modeling attacks [Gas+04; Rüh+10], where an attacker creates a
model of a PUF token which can be used to predict PUF responses with high accuracy,
thereby breaking the token’s security. Studies on modeling attacks hence represent an
essential part of research on PUFs and secret-free cryptography.
In the past 20 years, a large variety of PUF designs and attack strategies have been
developed. In this thesis, we revisit milestone designs and attacks, present new analysis
strategies, and conclude with a novel PUF design secure against all known modeling
attacks.
In Chapter 2, we formally introduce the notion of Physical Unclonable Functions and
discuss desired security properties, most importantly, existential unforgeability under
chosen and known message attacks.
In Chapter 3, we discuss the design rationale of the Arbiter PUF and XOR Arbiter
5
Loading more pages...