More Web Proxy on the site http://driver.im/

Article

Strong Machine Learning Attack Against PUFs with No Mathematical Model

Authors:

Fabian Fäβler,

Jean-Pierre SeifertAuthors Info & Claims

Proceedings of the 18th International Conference on Cryptographic Hardware and Embedded Systems --- CHES 2016 - Volume 9813

Pages 391 - 411

https://doi.org/10.1007/978-3-662-53140-2_19

Published: 17 August 2016 Publication History

Abstract

Although numerous attacks revealed the vulnerability of different PUF families to non-invasive Machine Learning ML attacks, the question is still open whether all PUFs might be learnable. Until now, virtually all ML attacks rely on the assumption that a mathematical model of the PUF functionality is known a priori. However, this is not always the case, and attention should be paid to this important aspect of ML attacks. This paper aims to address this issue by providing a provable framework for ML attacks against a PUF family, whose underlying mathematical model is unknown. We prove that this PUF family is inherently vulnerable to our novel PAC Probably Approximately Correct learning framework. We apply our ML algorithm on the Bistable Ring PUF BR-PUF family, which is one of the most interesting and prime examples of a PUF with an unknown mathematical model. We practically evaluate our ML algorithm through extensive experiments on BR-PUFs implemented on Field-Programmable Gate Arrays FPGA. In line with our theoretical findings, our experimental results strongly confirm the effectiveness and applicability of our attack. This is also interesting since our complex proof heavily relies on the spectral properties of Boolean functions, which are known to hold only asymptotically. Along with this proof, we further provide the theorem that all PUFs must have some challenge bit positions, which have larger influences on the responses than other challenge bits.

References

[1]

Altera: Cyclone IV Device Handbook. Altera Corporation, San Jose 2014

[2]

Angluin, D.: Queries and concept learning. Mach. Learn. 24, 319---342 1988

[3]

Armknecht, F., Maes, R., Sadeghi, A., Standaert, O.X., Wachsmann, C.: A formalization of the security features of physical functions. In: 2011 IEEE Symposium on Security and Privacy SP, pp. 397---412 2011

[4]

Armknecht, F., Moriyama, D., Sadeghi, A.R., Yung, M.: Towards a unified security model for physically unclonable functions. In: Sako, K. ed. CT-RSA 2016. LNCS, vol. 9610, pp. 271---287. Springer, Heidelberg 2016

[5]

Arvind, V., Köbler, J., Lindner, W.: Parameterized learnability of k-juntas and related problems. In: Hutter, M., Servedio, R.A., Takimoto, E. eds. ALT 2007. LNCS LNAI, vol. 4754, pp. 120---134. Springer, Heidelberg 2007

[6]

Blum, A.L., Langley, P.: Selection of relevant features and examples in machine learning. Artif. Intell. 971, 245---271 1997

[7]

Chen, Q., Csaba, G., Lugli, P., Schlichtmann, U., Rührmair, U.: The bistable ring PUF: a new architecture for strong physical unclonable functions. In: 2011 IEEE International Symposium on Hardware-Oriented Security and Trust HOST, pp. 134---141. IEEE 2011

[8]

Fischer, P., Simon, H.U.: On learning ring-sum-expansions. SIAM J. Comput. 211, 181---192 1992

[9]

Freund, Y.: Boosting a weak learning algorithm by majority. Inf. Comput. 1212, 256---285 1995

[10]

Freund, Y., Schapire, R.E.: A decision-theoretic generalization of on-line learning and an application to boosting. J. Comp. Syst. Sci. 551, 119---139 1997

[11]

Friedgut, E.: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 181, 27---35 1998

[12]

Ganji, F., Tajik, S., Seifert, J.P.: Let me prove it to you: RO PUFs are provably learnable. In: The 18th Annual International Conference on Information Security and Cryptology 2015

[13]

Ganji, F., Tajik, S., Seifert, J.-P.: Why attackers win: on the learnability of XOR arbiter PUFs. In: Conti, M., Schunter, M., Askoxylakis, I. eds. TRUST 2015. LNCS, vol. 9229, pp. 22---39. Springer, Heidelberg 2015

[14]

Ganji, F., Tajik, S., Seifert, J.P.: PAC learning of arbiter PUFs. J. Cryptographic Eng. Spec. Sect. Proofs 2014, 1---10 2016

[15]

Gassend, B., Clarke, D., Van Dijk, M., Devadas, S.: Silicon physical random functions. In: Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 148---160 2002

[16]

Guajardo, J., Kumar, S.S., Schrijen, G.-J., Tuyls, P.: FPGA intrinsic PUFs and their use for IP protection. In: Paillier, P., Verbauwhede, I. eds. CHES 2007. LNCS, vol. 4727, pp. 63---80. Springer, Heidelberg 2007

[17]

Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The WEKA data mining software: an update. ACM SIGKDD Explor. Newslett. 111, 10---18 2009

[18]

Helfmeier, C., Boit, C., Nedospasov, D., Seifert, J.P.: Cloning physically unclonable functions. In: 2013 IEEE International Symposium on Hardware-Oriented Security and Trust HOST, pp. 1---6 2013

[19]

Helfmeier, C., Nedospasov, D., Tarnovsky, C., Krissler, J.S., Boit, C., Seifert, J.P.: Breaking and entering through the silicon. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, pp. 733---744. ACM 2013

[20]

Helmbold, D., Sloan, R., Warmuth, M.K.: Learning integer lattices. SIAM J. Comput. 212, 240---266 1992

[21]

Holcomb, D.E., Burleson, W.P., Fu, K.: Initial SRAM state as a fingerprint and source of true random numbers for RFID tags. In: Proceedings of the Conference on RFID Security, vol. 7 2007

[22]

Kalai, G., Safra, S.: Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. In: Computational Complexity and Statistical Physics, Santa Fe Institute Studies on the Sciences of Complexity, pp. 25---60 2006

[23]

Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge 1994

[24]

Koushanfar, F.: Hardware metering: a survey. In: Tehranipoor, M., Wang, C. eds. Introduction to Hardware Security and Trust, pp. 103---122. Springer, New York 2012

[25]

Lee, J.W., Lim, D., Gassend, B., Suh, G.E., Van Dijk, M., Devadas, S.: A technique to build a secret key in integrated circuits for identification and authentication applications. In: 2004 Symposium on VLSI Circuits. Digest of Technical Papers, pp. 176---179 2004

[26]

Maes, R.: Physically Unclonable Functions: Constructions, Properties and Applications. Springer, Heidelberg 2013

[27]

Maes, R., van der Leest, V., van der Sluis, E., Willems, F.: Secure key generation from biased PUFs. In: Güneysu, T., Handschuh, H. eds. CHES 2015. LNCS, vol. 9293, pp. 517---534. Springer, Heidelberg 2015

[28]

Mossel, E., O'Donnell, R., Servedio, R.A.: Learning functions of k relevant variables. J. Comp. Syst. Sci. 693, 421---434 2004

[29]

O'Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge 2014

[30]

Pappu, R., Recht, B., Taylor, J., Gershenfeld, N.: Physical one-way functions. Science 2975589, 2026---2030 2002

[31]

Rivest, R.L.: Learning decision lists. Mach. Learn. 23, 229---246 1987

[32]

Ron, D., Rubinfeld, R., Safra, M., Samorodnitsky, A., Weinstein, O.: Approximating the influence of monotone boolean functions in $$O\sqrt{n}$$ query complexity. ACM Trans. Comput. Theory TOCT 44, 11 2012

[33]

Rührmair, U., Sehnke, F., Sölter, J., Dror, G., Devadas, S., Schmidhuber, J.: Modeling attacks on physical unclonable functions. In: Proceedings of the 17th ACM Conference on Computer and Communications Security, pp. 237---249 2010

[34]

Saha, I., Jeldi, R.R., Chakraborty, R.S.: Model building attacks on physically unclonable functions using genetic programming. In: 2013 IEEE International Symposium on Hardware-Oriented Security and Trust HOST, pp. 41---44. IEEE 2013

[35]

Schapire, R.E.: The strength of weak learnability. Mach. Learn. 52, 197---227 1990

[36]

Schapire, R.E., Freund, Y.: Boosting: Foundations and Algorithms. MIT Press, Cambridge 2012

[37]

Schuster, D., Hesselbarth, R.: Evaluation of bistable ring PUFs using single layer neural networks. In: Holz, T., Ioannidis, S. eds. Trust 2014. LNCS, vol. 8564, pp. 101---109. Springer, Heidelberg 2014

[38]

Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications Corresp. IEEE Trans. Inf. Theory 305, 776---780 1984

[39]

Tajik, S., Dietz, E., Frohmann, S., Seifert, J.-P., Nedospasov, D., Helfmeier, C., Boit, C., Dittrich, H.: Physical characterization of arbiter PUFs. In: Batina, L., Robshaw, M. eds. CHES 2014. LNCS, vol. 8731, pp. 493---509. Springer, Heidelberg 2014

[40]

Weste, N.H.E., Harris, D.: CMOS VLSI Design: A Circuits and Systems Perspective, 4th edn. Addison Wesley, Boston 2010

[41]

Xu, X., Rührmair, U., Holcomb, D.E., Burleson, W.P.: Security evaluation and enhancement of bistable ring PUFs. In: Mangard, S., Schaumont, P. eds. Radio Frequency Identification. LNCS, vol. 9440, pp. 3---16. Springer, Heidelberg 2015

[42]

Yamamoto, D., Takenaka, M., Sakiyama, K., Torii, N.: Security evaluation of Bistable Ring PUFs on FPGAs using differential and linear analysis. In: 2014 Federated Conference on Computer Science and Information Systems FedCSIS, pp. 911---918 2014

Cited By

Balijabudda VAcharya KChakraborty RChakrabarti I(2023)Theoretical Enumeration of Deployable Single-Output Strong PUF Instances Based on Uniformity and Uniqueness ConstraintsInformation Systems Security10.1007/978-3-031-49099-6_5(77-87)Online publication date: 16-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49099-6_5
Doosti MKumar NDelavar MKashefi E(2021)Client-server Identification Protocols with Quantum PUFACM Transactions on Quantum Computing10.1145/34841972:3(1-40)Online publication date: 30-Sep-2021
https://dl.acm.org/doi/10.1145/3484197
Tsiokanos IMiskelly JGu CO’neill MKarakonstantis G(2021)DTA-PUF: Dynamic Timing-aware Physical Unclonable Function for Resource-constrained DevicesACM Journal on Emerging Technologies in Computing Systems10.1145/343428117:3(1-24)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1145/3434281
Show More Cited By

Strong Machine Learning Attack Against PUFs with No Mathematical Model
1. Computing methodologies
2. Theory of computation

Recommendations

Adversarial Attack against Modeling Attack on PUFs
DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

The Physical Unclonable Function (PUF) has been proposed for the identification and authentication of devices and cryptographic key generation. A strong PUF provides an extremely large number of device-specific challenge-response pairs (CRP) which can ...
Machine Learning Vulnerability Analysis of FPGA-based Ring Oscillator PUFs and Counter Measures
Physical Unclonable Functions (PUFs) exploit the manufacturing process variations inherent in silicon-based chips to generate unique secret keys. Although PUFs are supposed to be unclonable or unbreakable, researchers have found that they are vulnerable ...
Tamper resistance evaluation of PUF implementation against machine learning attack
ICBEA '17: Proceedings of the 2017 International Conference on Biometrics Engineering and Application

Recently, the semiconductor counterfeiting has become a serious problem. To counter this problem, Physical Unclonable Function (PUF) has been attracted attention. However, the risk of machine learning attacks for PUF is pointed out. To verify the safety ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the 18th International Conference on Cryptographic Hardware and Embedded Systems --- CHES 2016 - Volume 9813

August 2016

41 pages

ISBN:9783662531396

Editors:
Benedikt Gierlichs
KU Leuven, Leuven, Belgium
,
Axel Y. Poschmann
NXP Semiconductors Germany GmbH, Hamburg, Germany

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Balijabudda VAcharya KChakraborty RChakrabarti I(2023)Theoretical Enumeration of Deployable Single-Output Strong PUF Instances Based on Uniformity and Uniqueness ConstraintsInformation Systems Security10.1007/978-3-031-49099-6_5(77-87)Online publication date: 16-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49099-6_5
Doosti MKumar NDelavar MKashefi E(2021)Client-server Identification Protocols with Quantum PUFACM Transactions on Quantum Computing10.1145/34841972:3(1-40)Online publication date: 30-Sep-2021
https://dl.acm.org/doi/10.1145/3484197
Tsiokanos IMiskelly JGu CO’neill MKarakonstantis G(2021)DTA-PUF: Dynamic Timing-aware Physical Unclonable Function for Resource-constrained DevicesACM Journal on Emerging Technologies in Computing Systems10.1145/343428117:3(1-24)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1145/3434281
Tebelmann LDanger JPehl M(2020)Self-secured PUF: Protecting the Loop PUF by MaskingConstructive Side-Channel Analysis and Secure Design10.1007/978-3-030-68773-1_14(293-314)Online publication date: 1-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-68773-1_14
Brasser FDavi LDhavlle AFrassetto TDinakarrao SRafatirad SSadeghi ASasan ASayadi HZeitouni SHomayoun HMitra TKumar A(2018)Advances and throwbacks in hardware-assisted securityProceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems10.5555/3283552.3283567(1-10)Online publication date: 30-Sep-2018
https://dl.acm.org/doi/10.5555/3283552.3283567
Elnaggar RChakrabarty K(2018)Machine Learning for Hardware SecurityJournal of Electronic Testing: Theory and Applications10.1007/s10836-018-5726-934:2(183-201)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s10836-018-5726-9
Ganji FTajik SSeifert J(2018)A Fourier Analysis Based Attack Against Physically Unclonable FunctionsFinancial Cryptography and Data Security10.1007/978-3-662-58387-6_17(310-328)Online publication date: 26-Feb-2018
https://dl.acm.org/doi/10.1007/978-3-662-58387-6_17

View Options

View options

Media

Figures

Other

Tables

View Table of Contents