Efficient Fuzzy Extraction of PUF-Induced Secrets: Theory and Applications

详细信息    查看全文

• 关键词：Fuzzy extractor ; Secure sketch ; Min ; entropy ; Physically unclonable function ; Coding theory
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9813
• 期：1
• 页码：412-431
• 全文大小：587 KB
• 参考文献：1.Aysu, A., Gulcan, E., Moriyama, D., Schaumont, P., Yung, M.: End-to-end design of a PUF-based privacy preserving authentication protocol. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 556–576. Springer, Heidelberg (2015)CrossRef
  2.Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.-X., Yu, Y.: Leftover hash lemma, revisited. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 1–20. Springer, Heidelberg (2011)CrossRef
  3.Becker, G.T.: On the pitfalls of using arbiter-PUFs as building blocks. IEEE Trans. CAD Integr. Circuits Syst. 34(8), 1295–1307 (2015)CrossRef
  4.Bhargava, M., Mai, K.: An efficient reliable PUF-based cryptographic key generator in 65nm CMOS. In: Design, Automation & Test in Europe Conference & Exhibition, DATE 2014, Dresden, Germany, 24–28 March 2014, pp. 1–6 (2014)
  5.Bösch, C., Guajardo, J., Sadeghi, A.-R., Shokrollahi, J., Tuyls, P.: Efficient helper data key extractor on FPGAs. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 181–197. Springer, Heidelberg (2008)CrossRef
  6.Boyen, X.: Reusable cryptographic fuzzy extractors. In: Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, Washington, DC, USA, 25–29 October 2004, pp. 82–91 (2004)
  7.Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)MathSciNet CrossRef MATH
  8.Delvaux, J., Gu, D., Schellekens, D., Verbauwhede, I.: Helper data algorithms for PUF-based key generation: overview and analysis. IEEE Trans. CAD Integr. Circ. Syst. 34(6), 889–902 (2015). http://​dx.​doi.​org/​10.​1109/​TCAD.​2014.​2370531 CrossRef
  9.Delvaux, J., Peeters, R., Gu, D., Verbauwhede, I.: A survey on lightweight entity authentication with strong PUFs. ACM Comput. Surv. 48(2), 26 (2015)CrossRef
  10.Delvaux, J., Verbauwhede, I.: Fault injection modeling attacks on 65nm arbiter and RO sum PUFs via environmental changes. IEEE Trans. Circuits Syst. 61–I(6), 1701–1713 (2014)CrossRef
  11.Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)MathSciNet CrossRef MATH
  12.Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, New York (1968)
  13.Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNet CrossRef MATH
  14.Van Herrewege, A., van der Leest, V., Schaller, A., Katzenbeisser, S., Verbauwhede, I.: Secure PRNG seeding on commercial off-the-shelf microcontrollers. In: TrustE 2013, Proceedings of the 2013 ACM Workshop on Trustworthy Embedded Devices, pp. 55–64 (2013)
  15.Hiller, M., Merli, D., Stumpf, F., Sigl, G.: Complementary IBS: application specific error correction for PUFs. In: 2012 IEEE International Symposium on Hardware-Oriented Security and Trust, HOST 2012, 3–4 June 2012, pp. 1–6 (2012)
  16.Holcomb, D.E., Burleson, W.P., Fu, K.: Power-up SRAM state as an identifying fingerprint and source of true random numbers. IEEE Trans. Comput. 58(9), 1198–1210 (2009)MathSciNet CrossRef
  17.Koeberl, P., Li, J., Rajan, A., Wu, W.: Entropy loss in PUF-based key generation schemes: the repetition code pitfall. In: 2014 IEEE International Symposium on Hardware-Oriented Security and Trust, HOST 2014, Arlington, VA, USA, 6–7 May 2014, pp. 44–49 (2014)
  18.MacWiliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland Mathematical Library (Book 16). North Holland Publishing Co., New York (1977)
  19.Maes, R.: Physically unclonable functions: constructions, properties and applications. Ph.D. thesis, KU Leuven (2012). Ingrid Verbauwhede (promotor)
  20.Maes, R.: An accurate probabilistic reliability model for silicon PUFs. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 73–89. Springer, Heidelberg (2013)CrossRef
  21.Maes, R., Tuyls, P., Verbauwhede, I.: A soft decision helper data algorithm for SRAM PUFs. In: ISIT 2009, IEEE International Symposium on Information Theory, pp. 2101–2105 (2009)
  22.Maes, R., van der Leest, V., van der Sluis, E., Willems, F.: Secure key generation from biased PUFs: extended version. J. Cryptogr. Eng. 6(2), 121–137 (2016)CrossRef
  23.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)CrossRef
  24.Reyzin, L.: Entropy loss is maximal for uniform inputs. Technical report BUCS-TR-2007-011, Department of Computer Science, Boston University, September 2007
  25.Tuyls, P., Schrijen, G.-J., Škorić, B., van Geloven, J., Verhaegh, N., Wolters, R.: Read-proof hardware from protective coatings. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 369–383. Springer, Heidelberg (2006)CrossRef
  26.van der Leest, V., Schrijen, G.-J., Handschuh, H., Tuyls, P.: Hardware intrinsic security from D flip-flops. In: Proceedings of the Fifth ACM Workshop on Scalable Trusted Computing, STC 2010, pp. 53–62 (2010)
  27.Van Herrewege, A.: Lightweight PUF-based key and random number generation. Ph.D. thesis, KU Leuven, 2015. Ingrid Verbauwhede (promotor)
  28.Van Herrewege, A., Katzenbeisser, S., Maes, R., Peeters, R., Sadeghi, A.-R., Verbauwhede, I., Wachsmann, C.: Reverse fuzzy extractors: enabling lightweight mutual authentication for PUF-enabled RFIDs. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 374–389. Springer, Heidelberg (2012)CrossRef
  29.Yu, H., Leong, P.H.W., Hinkelmann, H., Möller, L., Glesner, M., Zipf, P.: Towards a unique FPGA-based identification circuit using process variations. In: FPL 2009, International Conference on Field Programmable Logic and Applications, pp. 397–402 (2009)
  30.Yu, M., Devadas, S.: Secure and robust error correction for physical unclonable functions. IEEE Des. Test Comput. 27(1), 48–65 (2010)CrossRef
  
• 作者单位：Jeroen Delvaux (15) (16)
  Dawu Gu (16)
  Ingrid Verbauwhede (15)
  Matthias Hiller (17)
  Meng-Day (Mandel) Yu (15) (18) (19)
  
  15. KU Leuven, ESAT/COSIC and iMinds, Kasteelpark Arenberg 10, B-3001, Leuven, Belgium
  16. Shanghai Jiao Tong University, CSE/LoCCS, 800 Dongchuan Road, Shanghai, 200240, China
  17. Chair of Security in Information Technology, Technical University of Munich, Munich, Germany
  18. Verayo Inc., San Jose, USA
  19. CSAIL, MIT, Cambridge, USA
  
• 丛书名：Cryptographic Hardware and Embedded Systems ¨C CHES 2016
• ISBN：978-3-662-53140-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9813

文摘

The device-unique response of a physically unclonable function (PUF) can serve as the root of trust in an embedded cryptographic system. Fuzzy extractors transform this noisy non-uniformly distributed secret into a stable high-entropy key. The overall efficiency thereof, typically depending on error-correction with a binary [n, k, d] block code, is determined by the universal and well-known \((n-k)\) bound on the min-entropy loss. We derive new considerably tighter bounds for PUF-induced distributions that suffer from, e.g., bias or spatial correlations. The bounds are easy-to-evaluate and apply to large non-trivial codes, e.g., BCH, Hamming and Reed-Muller codes. Apart from an inherent reduction in implementation footprint, the newly developed theory also facilitates the analysis of state-of-the-art error-correction methods for PUFs. As such, we debunk the reusability claim of the reverse fuzzy extractor. Moreover, we provide proper quantitative motivation for debiasing schemes, as this was missing in the original proposals.