Abstract
In this paper, we present a novel formal analysis scheme considering that the fabrication of a batch of \(N > 1\) PUFs is equivalent to drawing random instances of Boolean mappings. We model PUFs as black-box Boolean functions of dimension \(m \times 1\) and show combinatorially that random designs of such \(m \times 1\) functions exhibit correlation-spectra which can be used to characterize random and thus good designs of PUFs. We first develop theoretical results to quantize the correlation values and subsequently find the expected number of pairs of such Boolean functions which should belong in different regions of the spectra. We extend the concept of correlation to PUFs and theoretically prove that a randomly chosen sample of PUFs and Boolean functions follow the same distribution. In addition to this, we show through extensive experimental results that a randomly chosen sample of such PUFs also resembles the correlation-spectra property of the overall PUF population. We finally propose a formal analysis tool for evaluation of PUFs by observing the correlation-spectra of the PUF instances under test. We show through experimental results on 50 FPGAs that when the PUFs are infected by faults the usual randomness tests for the PUF outputs such as uniformity, fail to detect any aberration. However, the spectral-pattern is clearly shown to get affected, which we demonstrate by standard statistical measure like KL Divergence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It may be noted that while there are potential methods of introducing faults in PUF circuits, the objective of the paper is to study the effects of faults on the Boolean spectrum of PUF instances.
- 2.
We have omitted the bin for correlation value 1, as these correspond to the self pairs.
- 3.
From here on, we will refer it as 5-4 DAPUF.
References
Bolotnyy, L., Robins, G.: Physically unclonable function-based security and privacy in RFID systems. In: Fifth Annual IEEE International Conference on Pervasive Computing and Communications, PerCom 2007, pp. 211–220. IEEE (2007)
Chatterjee, U., Sahoo, D.P., Mukhopadhyay, D., Chakraborty, R.S.: Trustworthy proofs for sensor data using FPGA based physically unclonable functions. In: Design, Automation and Test in Europe Conference and Exhibition (DATE), pp. 1504–1507. IEEE (2018)
Delvaux, J., Peeters, R., Gu, D., Verbauwhede, I.: A survey on lightweight entity authentication with strong PUFs. ACM Comput. Surv. (CSUR) 48(2), 26 (2015)
Delvaux, J., Verbauwhede, I.: 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)
Ganji, F.: On the Learnability of Physically Unclonable Functions. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76717-8
Ganji, F., Tajik, S., Fäßler, F., Seifert, J.-P.: Strong machine learning attack against PUFs with no mathematical model. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 391–411. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53140-2_19
Herder, C., Yu, M., Koushanfar, F., Devadas, S.: Physical unclonable functions and applications: a tutorial. Proc. IEEE 102(8), 1126–1141 (2014)
Hori, Y., Yoshida, T., Katashita, T., Satoh, A.: Quantitative and statistical performance evaluation of arbiter physical unclonable functions on FPGAs. In: International Conference on Reconfigurable Computing and FPGAs, pp. 298–303, December 2010
Immler, V., Hiller, M., Obermaier, J., Sigl, G.: Take a moment and have some t: hypothesis testing on raw PUF data. In: 2017 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pp. 128–129. IEEE (2017)
Khalafalla, M., Gebotys, C.: PUFs deep attacks: enhanced modeling attacks using deep learning techniques to break the security of double arbiter PUFs. In: 2019 Design, Automation and Test in Europe Conference and Exhibition (DATE), pp. 204–209. IEEE (2019)
Kullback, S., Leibler, R.A.: On information and sufficiency. Ann. Math. Stat. 22(1), 79–86 (1951)
Machida, T., Yamamoto, D., Iwamoto, M., Sakiyama, K.: A new mode of operation for arbiter PUF to improve uniqueness on FPGA. In: 2014 Federated Conference on Computer Science and Information Systems, pp. 871–878. IEEE (2014)
Maes, R., Van Herrewege, A., Verbauwhede, I.: PUFKY: a fully functional PUF-based cryptographic key generator. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 302–319. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_18
Maiti, A., Gunreddy, V., Schaumont, P.: A systematic method to evaluate and compare the performance of physical unclonable functions. In: Athanas, P., Pnevmatikatos, D., Sklavos, N. (eds.) Embedded Systems Design with FPGAs, pp. 245–267. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-1362-2_11
O’Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, New York (2014)
Ravikanth, P.S.: Physical one-way functions. Ph.D. thesis, Massachusetts (2001)
Rioul, O., Solé, P., Guilley, S., Danger, J.: On the entropy of physically unclonable functions. In: IEEE International Symposium on Information Theory (ISIT), pp. 2928–2932, July 2016
Rührmair, U.: Oblivious transfer based on physical unclonable functions. In: Acquisti, A., Smith, S.W., Sadeghi, A.-R. (eds.) Trust 2010. LNCS, vol. 6101, pp. 430–440. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13869-0_31
Rührmair, U., Busch, H., Katzenbeisser, S.: Strong PUFs: models, constructions, and security proofs. In: Sadeghi, A.R., Naccache, D. (eds.) Towards Hardware-Intrinsic Security, pp. 79–96. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14452-3_4
Sahoo, D.P., Bag, A., Patranabis, S., Mukhopadhyay, D., Chakraborty, R.S.: Fault-tolerant implementations of physically unclonable functions on FPGA. In: Chakraborty, R., Mathew, J., Vasilakos, A. (eds.) Security and Fault Tolerance in Internet of Things, pp. 129–153. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-02807-7_7
Sarkar, P., Maitra, S.: Cross-correlation analysis of cryptographically useful boolean functions and S-boxes. Theory Comput. Syst. 35(1), 39–57 (2002)
Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication and secret key generation. In: 44th ACM/IEEE Design Automation Conference, pp. 9–14, June 2007
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)
Wang, Y., Wang, C., Gu, C., Cui, Y., O’Neill, M., Liu, W.: Theoretical analysis of delay-based PUFs and design strategies for improvement. In: 2019 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1–5. IEEE (2019)
Zhang, B., Srihari, S.N.: Properties of binary vector dissimilarity measures. In: Proceedings of JCIS International Conference on Computer Vision, Pattern Recognition, and Image Processing, vol. 1 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Chatterjee, D., Hazra, A., Mukhopadhyay, D. (2019). Formal Analysis of PUF Instances Leveraging Correlation-Spectra in Boolean Functions. In: Bhasin, S., Mendelson, A., Nandi, M. (eds) Security, Privacy, and Applied Cryptography Engineering. SPACE 2019. Lecture Notes in Computer Science(), vol 11947. Springer, Cham. https://doi.org/10.1007/978-3-030-35869-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-35869-3_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-35868-6
Online ISBN: 978-3-030-35869-3
eBook Packages: Computer ScienceComputer Science (R0)