Towards Hardware-Intrinsic Security (eBook)

Foreword 5
Contents 8
List of Contributors 11
Part I Physically Unclonable Functions (PUFs) 15
Physically Unclonable Functions: A Study on the State of the Art and Future Research Directions 16
Roel Maes and Ingrid Verbauwhede 16
1 Introduction 16
2 PUF Terminology and Measures 17
2.1 Challenges and Responses 17
2.2 Inter- and Intra-distance Measures 18
2.3 Environmental Effects 19
3 PUF Instantiations 19
3.1 Non-electronic PUFs 20
3.2 Analog Electronic PUFs 23
3.3 Delay-Based Intrinsic PUFs 25
3.4 Memory-Based Intrinsic PUFs 29
3.5 PUF Concepts 32
4 PUF Properties 34
4.1 Property Description 34
4.2 Property Check 36
4.3 Least Common Subset of PUF Properties 37
5 PUF Application Scenarios 41
5.1 System Identification 41
5.2 Secret Key Generation 42
5.3 Hardware-Entangled Cryptography 42
6 PUF Discussions and Some Open Questions 43
6.1 Predictability Versus Implementation Size 43
6.2 Formalization of PUF Properties 44
6.3 Reporting on PUF Implementation Results 45
7 Conclusion 46
References 47
Hardware Intrinsic Security from Physically Unclonable Functions 51
Helena Handschuh, Geert-Jan Schrijen, and Pim Tuyls 51
1 Introduction 51
2 Rethinking Secure Key Storage Mechanisms 53
2.1 Limitations of Current Key Storage Mechanisms 53
2.2 A Radical New Approach to Secure Key Storage 54
3 Hardware Intrinsic Security 55
3.1 Physically Unclonable Functions 55
3.2 Examples of PUFs 56
3.3 Secure Key Storage Based on PUFs 59
4 Quality of a PUF 60
4.1 Reliability 61
4.2 Security 62
5 Conclusions 63
References 64
From Statistics to Circuits: Foundations for Future Physical Unclonable Functions 66
Inyoung Kim, Abhranil Maiti, Leyla Nazhandali, Patrick Schaumont, Vignesh Vivekraja, and Huaiye Zhang 66
1 Introduction 66
2 Components and Quality Factors of a PUF Design 68
2.1 Components of a PUF 68
2.2 PUF Quality Factors 69
2.3 Sources of CMOS Variability and Compensation of Unwanted Variability 70
3 Circuit-Level Optimization of PUF 72
3.1 Methodology 73
3.2 Background: Operating Voltage and Body Bias 73
3.3 Effect of Operating Voltage and Body Bias on PUF 75
4 Architecture-Level Optimization of PUF 76
4.1 Compensation of Environmental Effects 77
4.2 Compensation of Correlated Process Variations 78
5 Identity Mapping and Testing 79
5.1 Statistical Preliminaries 80
5.2 A New Test Statistic: Q 82
5.3 Experimental Results 85
5.4 Compensation of Environmental Effects 86
5.5 Open Challenges 87
6 Conclusions 87
References 87
Strong PUFs: Models, Constructions, and Security Proofs 90
Ulrich Rührmair, Heike Busch, and Stefan Katzenbeisser 90
1 Introduction 90
2 Implementations of Strong Physical Unclonable Functions 91
3 Physical Unclonable Functions: Toward a Formal Definition 93
3.1 Physical One-Way Functions 93
3.2 Physical Unclonable Functions 95
3.3 Physical Random Functions 97
4 Alternative Attack Models 97
4.1 Semi-formal Models for Strong PUFs 98
4.2 The Digital Attack Model 100
5 Identification Schemes Based on Strong PUFs 101
5.1 PUF-Based Identification Schemes 101
5.2 Security of PUF-Based Identification in the Digital Attack Model 102
6 Conclusions 105
References 105
Part II Hardware-Based Cryptography 108
Leakage Resilient Cryptography in Practice 109
François-Xavier Standaert, Olivier Pereira, Yu Yu, Jean-Jacques Quisquater, Moti Yung, and Elisabeth Oswald 109
1 Introduction 109
2 Background 112
2.1 Notations 112
2.2 Definition of a Leakage Function 112
3 Unpredictability vs. Indistinguishability 114
4 Physical Assumptions: Local vs. Global Approach 117
4.1 Analogy with Classical Cryptanalysis 120
5 Leakage Resilient PRGs 120
5.1 On the Difficulty of Modeling a Leakage Function 120
5.2 Theoretical Security Analysis and Limitations 122
5.3 Proving Leakage Resilience with Random Oracles 123
5.4 Practical Security Analysis 126
6 Initialization Issues 129
6.1 Breaking [34] with a Standard DPA 129
6.2 Secure Initialization Process 130
6.3 A More Elegant (and Standard) Construction 131
6.4 Remark on the Impossibility of a Secure Initialization Process with an Adaptive Selection of the Leakages 132
7 Generalization to PRFs 134
8 Remark on the Impossibility of Proving the Leakage Resilience for the Forward Secure PRG of Fig. 6a in the Standard Model 136
9 Open Problems 136
10 Further Details 138
10.1 Security Metric 138
10.2 Proof of Theorem 1 138
10.3 Proof of Theorem 2 140
References 142
Memory Leakage-Resilient Encryption Based on Physically Unclonable Functions 145
Frederik Armknecht, Roel Maes, Ahmad-Reza Sadeghi, Berk Sunar,and Pim Tuyls 145
1 Introduction 145
2 Related Work 147
3 Memory Attacks 148
4 Preliminaries 149
5 Physically Unclonable Functions 150
6 Pseudorandom Functions Based on PUFs 152
7 Encrypting with PUF-(w)PRFs 156
7.1 General Thoughts 156
7.2 A Stream Cipher Based on PUF-PRFs 157
7.3 A Block Cipher Based on PUF-PRFs 159
8 SRAM PRFs 163
8.1 Physical Implementation Details of Static Random Access Memory (SRAM) 164
8.2 The SRAM PUF Construction 164
8.3 SRAM PUF Parameters and Experimental Validation 166
8.4 From SRAM PUF to SRAM PRF 167
8.5 A Concrete Block Cipher Realization Based on SRAM-PRFs 170
9 Conclusions 171
References 171
Part III Hardware Attacks 175
Hardware Trojan Horses 176
Mohammad Tehranipoor and Berk Sunar 176
1 What Is the Untrusted Manufacturer Problem? 176
2 Hardware Trojans 178
3 A Taxonomy of Hardware Trojans 179
4 A High-Level Attack: Shadow Circuits 181
5 Trojan Detection Methodologies 182
5.1 Trojan Detection Using Side-Channel Signal Analysis 182
5.2 Trojan Activation Methods 187
6 Design-for-Hardware-Trust Techniques 189
7 Circuit Obfuscation as a Countermeasure 193
References 194
Extracting Unknown Keys from Unknown Algorithms Encrypting Unknown Fixed Messages and Returning No Results 197
Yoo-Jin Baek, Vanessa Gratzer, Sung-Hyun Kim, and David Naccache 197
1 Introduction 197
2 The Intuition 198
3 Notations and Statistical Tools 199
4 The Attack 200
4.1 The Exhaust Routine 200
5 Practical Experiments 202
6 Implications and Further Research 205
References 205
Part IV Hardware-Based Policy Enforcement 206
License Distribution Protocols from Optical Media Fingerprints 207
Ghaith Hammouri, Aykutlu Dana, and Berk Sunar 207
1 Introduction 207
2 Pits and Lands 209
2.1 Source of Variation 209
2.2 Single Location Characterization 211
3 Experimental Validation 211
4 CD Fingerprinting 215
4.1 Fuzzy Extractors 216
4.2 Fingerprint Extraction 217
4.3 Entropy Estimation and 128-Bit Security 218
5 Robustness of the Fingerprint 222
6 License Distribution Protocol 222
6.1 Simple Distribution Protocol 223
6.2 Secure Reader Protocol 224
6.3 Online Distribution Protocol 225
7 Conclusion 226
References 227
Anti-counterfeiting: Mixing the Physical and the Digital World 229
Darko Kirovski 229
1 Introduction 229
1.1 Classification 230
2 Desiderata for Anti-counterfeiting Technologies 230
3 Digitizing the Physical World 232
4 Applications 234
5 Review of Existing Methodologies 234
5.1 RF-DNA 236
5.2 Challenge/Response COA Systems 237
6 Conclusion 238
References 238
Part V HardwareSecurity in Contactless Tokens 240
Anti-counterfeiting, Untraceability and Other Security Challenges for RFID Systems: Public-Key-Based Protocols and Hardware 241
Yong Ki Lee, Lejla Batina, Dave Singelee, Bart Preneel, andIngrid Verbauwhede 241
1 Introduction 241
2 Security and Privacy Requirements 242
2.1 Security Objectives 242
2.2 Privacy Objectives 243
2.3 General Objectives 244
3 State of the Art 245
3.1 Authentication Protocols Based on Private-Key Cryptography 245
3.2 Authentication Protocols Based on PUFs 246
3.3 Authentication Protocols Based on Public-Key Cryptography 246
4 Untraceable Authentication Protocols Based on ECC 247
4.1 Notation 247
4.2 EC-RAC II 247
4.3 Randomized Schnorr Protocol 248
4.4 Man-in-the-Middle Attacks 248
5 EC-RAC IV 250
6 Search Protocol 251
6.1 Protocol Description 251
6.2 Search Protocol Analysis 253
6.3 Combining Authentication Protocols 255
7 Implementation 255
7.1 Overall Architecture 256
7.2 New MALU Design 256
7.3 Performance Evaluation 258
8 Conclusions 258
References 259
Contactless Security Token Enhanced Security by Using New Hardware Features in Cryptographic-Based Security Mechanisms 262
Markus Ullmann and Matthias Vögeler 262
1 Introduction 262
1.1 Benefits of Contactless Smart Cards 262
1.2 Security Limitation of Supposed Security Mechanisms for an Authenticated Connection Establishment Between Terminals and Contactless Cards 262
1.3 Security Limitation of Device Authentication Protocols Based on Irrevocable Authentication Certificates 264
2 Contactless Security Token 266
2.1 Flexible Display Technology 266
2.2 Real-Time Clock 267
2.3 Buttons 268
3 Authenticated Connection Establishment 268
3.1 Password-Based Cryptographic Protocols 268
3.2 Password Authenticated Connection Establishment (PACE) 268
3.3 Security Token Operation 270
3.4 Security Analysis of PACE Using Fresh Passwords 270
3.5 Brute-Force Online-Attacks on Passwords 271
4 Secure Time Synchronization 272
4.1 Time Values 272
4.2 Time Server-Based Synchronization Protocols 273
4.3 Security Requirements for Time Synchronization 274
4.4 Secure Time Synchronization Protocols 275
4.5 Security and Performance Analysis 277
5 Applications 279
5.1 Authentication of Internet Services 279
6 Conclusion 281
References 281
Enhancing RFID Security and Privacy by Physically UnclonableFunctions 283
Ahmad-Reza Sadeghi, Ivan Visconti, and Christian Wachsmann 283
1 Introduction 283
1.1 Contribution 284
2 High-Level RFID System and Requirement Analysis 285
2.1 System Model 285
2.2 Trust and Adversary Model 285
2.3 Security and Privacy Threats 286
2.4 Security and Privacy Objectives 286
3 Related Work 286
3.1 Privacy-Preserving RFID Protocols 286
3.2 RFID Protocols Based on Physically Unclonable Functions 287
3.3 Privacy Models for RFID 289
4 RFID Security and Privacy Model of Vaudenay [67] 290
4.1 General Notation 290
4.2 Pseudorandom Function (PRF) 290
4.3 Physically Unclonable Function (PUF) 291
4.4 System Model 292
4.5 Adversary Model 293
4.6 Definition of Correctness, Security, and Privacy 296
5 A PUF-Based Destructive-Private RFID Protocol 297
5.1 Correctness 298
6 Security Analysis 299
6.1 Tag Authentication 299
6.2 Destructive Privacy 300
7 Conclusion 303
References 304
Part VI Hardware-Based Security Architectures and Applications 308
Authentication of Processor Hardware Leveraging Performance Limits in Detailed Simulations and Emulations 309
Daniel Y. Deng, Andrew H. Chan, and G. Edward Suh 309
1 Introduction 309
2 Threat Model 311
3 Authentication Approach 312
4 Hardware Design 315
4.1 Microarchitectural Features 315
4.2 Checksum Computation 316
4.3 New Instructions 318
4.4 Non-determinism 318
5 Challenge Program 319
6 Evaluation 321
6.1 Overheads 321
6.2 Effectiveness 322
6.3 Deterministic Execution 323
6.4 Security Discussion 324
7 Related Work 326
8 Conclusion 327
References 327
Signal Authentication in Trusted Satellite Navigation Receivers 330
Markus G. Kuhn 330
1 Introduction 330
1.1 Environmental Assumptions 331
1.2 Related Technologies 332
1.3 Goals 333
2 Techniques 334
2.1 Secret Spreading Sequences 334
2.2 Individual Receiver Antenna Characteristics 337
2.3 Consistency with Reference Receivers 337
2.4 Receiver-Internal Plausibility Tests 339
2.5 Some Other Ideas 343
3 Comparison 344
4 Conclusions 346
References 346
On the Limits of Hypervisor- and Virtual Machine Monitor-Based Isolation 348
Loic Duflot, Olivier Grumelard, Olivier Levillain, and Benjamin Morin 348
1 Introduction 348
2 Compartmented Systems 349
2.1 Traditional Architectures and Definition of a Trusted Computing Base 349
2.2 Attacker Model 350
3 Attack Paths 350
3.1 Taxonomy of Attack Vectors 350
4 Design of a DIMM Backdoor 353
4.1 Overview of DDR DIMM 353
4.2 Principle of the Backdoor 354
4.3 Proof of Concept Implementation 354
5 Exploitation 358
5.1 Difficulties 358
5.2 Use of the Hidden Functions to Access Sensitive Data 359
5.3 Use of the Backdoor as a means for Privilege Escalation 361
6 Countermeasures 362
7 Conclusion and Future Work 363
References 363
Efficient Secure Two-Party Computation with Untrusted Hardware Tokens 366
Kimmo Järvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider 366
1 Introduction 366
1.1 Our Setting, Goals, and Approach 367
1.2 Envisioned Applications 368
1.3 Our Contributions and Outline 369
1.4 Related Work 369
2 Preliminaries 370
2.1 Garbled Circuits (GC) 371
3 Architecture, System, and Trust Model 372
4 Token-Assisted Garbled Circuit Protocols 373
4.1 Protocols Overview and Security 373
4.2 Circuit Representation 375
4.3 GC Creation with Stateful Token (Secure Counter) 377
4.4 GC Creation with Stateless Token (No Counter) 378
5 Further Optimizations 378
5.1 Optimizing Memory of Client 379
5.2 Optimizing Runtime of Token by Caching 379
6 Proof-of-Concept Implementation 380
6.1 Architecture 381
6.2 Prototype Implementation 382
References 383
Towards Reliable Remote Healthcare Applications Using Combined Fuzzy Extraction 386
Jorge Guajardo, Muhammad Asim, and Milan Petkovic 386
1 Introduction 386
2 Remote Patient Monitoring Services and Data Reliability Issues 389
2.1 Data Reliability Issues 390
3 Fuzzy Extractors, PUFs, and Biometrics 391
3.1 Preliminaries 391
3.2 Physical Unclonable Functions 393
3.3 Biometrics 395
3.4 The Need for Fuzzy Extractors 395
4 Combining PUFs and Biometrics 398
4.1 A Practical Simplification 402
4.2 Other Variations 403
4.3 Security and Safety 403
5 Conclusions 404
References 404