nach oben

Journal of Cryptographic Engineering

Erschienen in:

19.03.2019 | Regular Paper

Why attackers lose: design and security analysis of arbitrarily large XOR arbiter PUFs

verfasst von: Nils Wisiol, Marian Margraf

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In a novel analysis, we formally prove that arbitrarily many Arbiter PUFs can be combined into a stable XOR Arbiter PUF. To the best of our knowledge, this design cannot be modeled by any known oracle access attack in polynomial time. Using majority vote of arbiter chain responses, our analysis shows that with a polynomial number of votes, the XOR Arbiter PUF stability of almost all challenges can be boosted exponentially close to 1; that is, the stability gain through majority voting can exceed the stability loss introduced by large XORs for a feasible number of votes. Considering state-of-the-art modeling attacks by Becker and Rührmair et al., our proposal enables the designer to increase the attacker’s effort exponentially while still maintaining polynomial design effort. This is the first result that relates PUF design to this traditional cryptographic design principle.

Vorheriger Artikel An automated framework for exploitable fault identification in block ciphers

Nächster Artikel Side-channel robustness analysis of masked assembly codes using a symbolic approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

For the sake of easier notation, we chose to model challenges as vectors in \(\{-1,1\}^{n}\) rather than \(\{0,1\}^{n}\). If desired, all results can be transformed into \(\{0,1\}^{n}\) challenges by “encoding” inputs bits with a function \(\rho :\{0,1\}\rightarrow \{-1,1\}\), where \(\rho (0)=1\) and \(\rho (1)=-1\). This way, we can write \(\rho (b)=(-1)^{b}\) and have the convenient property \(\rho (b_{1}\oplus b_{2})=\rho (b_{1})\cdot \rho (b_{2})\), where \(\oplus \) denotes addition modulo 2 and \(\cdot \) denotes multiplication over \({\mathbb {Z}}\). Any output of our model can be transformed by \(\rho ^{-1}\).

Code at https://github.com/nils-wisiol/pypuf/tree/2019-why-attackers-lose.

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

Armknecht, F., Maes, R., Sadeghi, A.-R., Sunar, B., Tuyls, P..: Memory leakage-resilient encryption based on physically unclonable functions. In: Matsui M (ed) Proceedings of the Advances in Cryptology–ASIACRYPT 2009: 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6–10, 2009, pp. 685–702. Springer, Berlin (2009)

Armknecht, F., Moriyama, D., Sadeghi, A.-R., Yung, M.: Towards a unified security model for physically unclonable functions. Proc. RSA Conf. Top. Cryptol. 9610, 271–287 (2016)MathSciNetMATH

Becker, G.T.: The gap between promise and reality: on the insecurity of XOR arbiter PUFs. In: International Workshop on Cryptographic Hardware and Embedded Systems, pp. 535–555. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-48324-4_27

Berry, Andrew C.: The accuracy of the Gaussian approximation to the sum of independent variates. Trans. Am. Math. Soc. 49(1), 122–122 (1941)MathSciNetCrossRefMATH

Delvaux, J., Verbauwhede, I.: Side channel modeling attacks on 65nm arbiter PUFs exploiting CMOS device noise. In: 2013 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pp. 137–142. IEEE (2013)

Delvaux, Jeroen, Verbauwhede, Ingrid: Fault injection modeling attacks on 65 nm arbiter and RO Sum PUFs via environmental changes. IEEE Trans. Circuits Syst. I: Regul. Pap. 61(6), 1701–1713 (2014)CrossRef

Devadas, S.: Physical unclonable functions (PUFS) and secure processors. In: Workshop on Cryptographic Hardware and Embedded Systems (2009)

Devadas, S., Suh, E., Paral, S., Sowell, R., Ziola, T., Khandelwal, V.: Design and implementation of PUF-based “unclonable” RFID ICs for anti-counterfeiting and security applications. In: 2008 IEEE International Conference on RFID (Frequency Identification), IEEE RFID 2008, pp. 58–64 (2008)

10.

Esseen, Carl-Gustaf: On the Liapounoff Limit of Error in the Theory of Probability. Almqvist & Wiksell, Stockholm (1942)MATH

11.

Ganji, F., Krämer, J., Seifert, J.-P., Tajik, S.: Lattice basis reduction attack against physically unclonable functions. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1070–1080. ACM (2015)

12.

Ganji, F., Tajik, S., Fäßler, F., Seifert, J.-P.: Strong machine learning attack against PUFs with no mathematical model. Lect. Notes Comput. Sci. (including subseries Lecture Notes in Arti cial Intelligence and Lecture Notes in Bioinformatics) 9813, 391–411 (2016)MATH

13.

Ganji, F., Tajik, S., Seifert, J.-P.: Why attackers win: On the learnability of XOR arbiter PUFs. In: Trust and Trustworthy Computing, pp. 22–39. Springer (2015)

14.

Ganji, Fatemeh, Tajik, Shahin, Seifert, Jean-Pierre: PAC learning of arbiter PUFs. J. Cryptogr. Eng. 6(3), 249–258 (2016)CrossRef

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. ACM (2002)

16.

Gassend, B., Clarke, D., van Dijk, M., Devadas, S.: Delay-based circuit authentication and applications. In: Proceedings of the 2003 ACM symposium on Applied computing-SAC ’03, pp. 294. ACM Press, New York (2003)

17.

Gassend, Blaise, Lim, Daihyun, Clarke, Dwaine, Van Dijk, Marten, Devadas, Srinivas: Identification and authentication of integrated circuits. Concurrency and Computation: Practice and Experience 16(11), 1077–1098 (2004)CrossRef

18.

Gassend, Blaise, Van Dijk, Marten, Clarke, Dwaine, Devadas, Srinivas: Controlled physical random functions. Secur. Noisy Data Priv. Biom. Secure Key Storage Anti-Count. 10(4), 235–253 (2007)

19.

Guo, Q., Ye, J., Gong, Y., Hu, Y., Li, X.: Efficient attack on non-linear current mirror PUF with genetic algorithm. In: 2016 IEEE 25th Asian Test Symposium (ATS), pp. 49–54 (2016)

20.

Kalyanaraman, M., Orshansky, M.: Novel strong PUF based on nonlinearity of MOSFET subthreshold operation. In: Proceedings of the 2013 IEEE International Symposium on Hardware-Oriented Security and Trust, HOST 2013, pp. 13–18 (2013)

21.

Kumar, R., Burleson, W.: On design of a highly secure PUF based on non-linear current mirrors. In: 2014 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pp. 38–43. IEEE (2014)

22.

Lim, D., Lee, J.W., Gassend, B., Suh, G.E., Van Dijk, M., Devadas, S.: Extracting secret keys from integrated circuits. IEEE Trans. Very Large Scale Integr. Syst. 13(10), 1200–1205 (2005)CrossRef

23.

Lohrke, H., Tajik, S., Boit, C., Seifert, J.-P.: No place to hide: contactless probing of secret data on FPGAs. Cryptology ePrint Archive, Report 2016/593 (2016)

24.

Majzoobi, M., Dyer, E., Elnably, A., Koushanfar, F.: Rapid FPGA delay characterization using clock synthesis and sparse sampling. In: IEEE International Test Conference (ITC), Austin, TX (2010)

25.

Majzoobi, Mehrdad, Kharaya, Akshat, Koushanfar, Farinaz, Devadas, Srinivas: Automated design, implementation, and evaluation of arbiter-based PUF on FPGA using programmable delay lines. IACR Cryptol. 2014, 639 (2014)

26.

Majzoobi, Mehrdad, Koushanfar, Farinaz, Srinivas, Devadas: FPGA PUF using programmable delay lines. IEEE Int. Workshop Inf. Forens. Secur. 2010, 2010 (2010)

27.

Merli, D., Schuster, D., Stumpf, F., Sigl, G.: Semi-invasive EM attack on FPGA RO PUFs and countermeasures. Workshop on Embedded Systems Security, pp. 1–9 (2011)

28.

Merli, D., Schuster, D., Stumpf, F., Sigl, G.: Side-channel analysis of PUFs and fuzzy extractors. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6740, pp. 33–47. LNCS (2011)

29.

Nedospasov, D., Seifert, J.-P., Helfmeier, C., Boit, C.: Invasive PUF analysis. In: Proceedings-10th Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2013, pp. 30–38 (013)

30.

Pappu, Ravikanth, Recht, Ben, Taylor, Jason, Gershenfeld, Neil: Physical one-way functions. Science 297(5589), 2026–2030 (2002)CrossRef

31.

Ruhrmair, U., Martinez-Hurtado, J.L., Xu, X., Kraeh, C., Hilgers, C., Kononchuk, D., Finley, J.J., Burleson, W.P.: Virtual proofs of reality and their physical implementation. In: 2015 IEEE Symposium on Security and Privacy, vol. 2015-July, pp. 70–85. IEEE (2015 May)

32.

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. ACM (2010)

33.

Rührmair, Ulrich, Sölter, Jan, Sehnke, Frank, Xiaolin, Xu, Mahmoud, Ahmed, Stoyanova, Vera, Dror, Gideon, Schmidhuber, Jürgen, Burleson, Wayne, Devadas, Srinivas: PUF modeling attacks on simulated and silicon data. IEEE Trans. Inf. Forens. Secur. 8(11), 1876–1891 (2013)CrossRef

34.

Rührmair, Ulrich, Xiaolin, Xu, Sölter, Jan, Mahmoud, Ahmed, Majzoobi, Mehrdad, Koushanfar, Farinaz, Burleson, Wayne: Efficient power and timing side channels for physical unclonable functions. Cryptogr. Hardw. Embed. Syst. 8731, 476–492 (2014)MATH

35.

Spenke, A., Breithaupt, R., Plaga, R.: An arbiter PUF secured by remote random reconfigurations of an FPGA. In: International Conference on Trust and Trustworthy Computing, pp. 140–158. Springer (2016)

36.

Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication and secret key generation. In: Proceedings of the 44th Annual Design Automation Conference, pp. 9–14. ACM (2007)

37.

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.) Proceedings of the Cryptographic Hardware and Embedded Systems-CHES 2014: 16th International Workshop, Busan, South Korea, September 23–26, 2014. pp. 493–509. Springer, Berlin (2014)

38.

Tajik, S., Lohrke, H., Ganji, F., Seifert, J.-P., Boit, C.: Laser fault attack on physically unclonable functions. In: 2015 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), pp. 85–96. IEEE (2015)

39.

Tehranipoor, M., Wang, C.: Introduction to Hardware Security and Trust, vol. 9781441980. Springer, Berlin (2012)CrossRef

40.

Vijayakumar, A., Kundu, S.: A novel modeling attack resistant PUF design based on non-linear voltage transfer characteristics. In: Design, Automation & Test in Europe Conference & Exhibition (DATE), 2015, DATE ’15, pp. 653–658. IEEE Conference Publications, New Jersey (2015)

41.

Yu, M.D.M., Hiller, M., Delvaux, J., Sowell, R., Devadas, S., Verbauwhede, I.: A lockdown technique to prevent machine learning on PUFs for lightweight authentication. IEEE Trans. Multi-Scale Comput. Syst. 2(3), 146–159 (2016)CrossRef

42.

Илья Сергееич Тюрин. Уточнение верхних оценок констант в теореме Ляпунова. У с п е х и м а т е м а т и ч е с к и х н а у к, 65(3):201-202, 2010

Titel: Why attackers lose: design and security analysis of arbitrarily large XOR arbiter PUFs
verfasst von: Nils Wisiol
Marian Margraf
Publikationsdatum: 19.03.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 3/2019
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-019-00204-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2019

Automatic generation of HCCA-resistant scalar multiplication algorithm by proper sequencing of field multiplier operands

Triathlon of lightweight block ciphers for the Internet of things

Polynomial direct sum masking to protect against both SCA and FIA

Side-channel robustness analysis of masked assembly codes using a symbolic approach

Mixed-radix Naccache–Stern encryption

An automated framework for exploitable fault identification in block ciphers