Abstract
Physical Unclonable Functions (PUFs) have properties that make them very attractive for a variety of security-related applications. Due to their inherent dependency on the physical properties of the device that contains them, they can be used to uniquely bind an application to a particular device for the purpose of IP protection. This is crucial for the protection of FPGA applications against illegal copying and distribution. In order to exploit the physical nature of PUFs for reliable cryptography a so-called helper data algorithm or fuzzy extractor is used to generate cryptographic keys with appropriate entropy from noisy and non-uniform random PUF responses. In this paper we present for the first time efficient implementations of fuzzy extractors on FPGAs where the efficiency is measured in terms of required hardware resources. This fills the gap of the missing building block for a full FPGA IP protection solution. Moreover, in this context we propose new architectures for the decoders of Reed-Muller and Golay codes, and show that our solutions are very attractive from both the area and error correction capability points of view.
Chapter PDF
Similar content being viewed by others
Keywords
References
Pappu, R.S., Recht, B., Taylor, J., Gershenfeld, N.: Physical one-way functions. Science 297(6), 2026–2030 (2002)
Tuyls, P., Schrijen, G.-J., S̆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)
Trusted Computing Group: TPM main specification. Technical Report Version 1.2 Revision 94 (March 2006)
Gassend, B., Clarke, D.E., van Dijk, M., Devadas, S.: Silicon physical unknown functions. In: Atluri, V. (ed.) ACM Conference on Computer and Communications Security — CCS 2002, pp. 148–160. ACM, New York (2002)
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)
Škorić, B., Bel, T., Blom, A., de Jong, B., Kretschman, H., Nellissen, A.: Randomized resonators as uniquely identifiable anti-counterfeiting tags. Technical report, Philips Research Laboratories (January 28, 2008)
Kean, T.: Cryptographic rights management of FPGA intellectual property cores. In: ACM/SIGDA International Symposium on Field-Programmable Gate Arrays — FPGA 2002, pp. 113–118 (2002)
Simpson, E., Schaumont, P.: Offline Hardware/Software Authentication for Reconfigurable Platforms. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 311–323. Springer, Heidelberg (2006)
Guajardo, J., Kumar, S.S., Schrijen, G.J., Tuyls, P.: Physical Unclonable Functions and Public Key Crypto for FPGA IP Protection. In: International Conference on Field Programmable Logic and Applications — FPL 2007, August 27-30, 2007, pp. 189–195. IEEE, Los Alamitos (2007)
Linnartz, J.P.M.G., Tuyls, P.: New Shielding Functions to Enhance Privacy and Prevent Misuse of Biometric Templates. In: Kittler, J., Nixon, M.S. (eds.) AVBPA 2003. LNCS, vol. 2688, pp. 393–402. Springer, Heidelberg (2003)
Dodis, Y., Reyzin, M., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004)
Suh, G.E., O’Donnell, C.W., Devadas, S.: AEGIS: A Single-Chip Secure Processor. IEEE Design & Test of Computers 24(6), 570–580 (2007)
Dijk, M.v., Lim, D., Devadas, S.: Reliable Secret Sharing With Physical Random Functions. Computation Structures Group Memo 475, CSAIL — Massachusetts Institute of Technology (2004)
Gassend, B.: Physical Random Functions. Master’s thesis, Computer Science and Artificial Intelligence Laboratory, MIT Computation Structures Group Memo 458 (February 2003)
Juels, A., Wattenberg, M.: A Fuzzy Commitment Scheme. In: Motiwalla, J., Tsudik, G. (eds.) ACM Conference on Computer and Communications Security — ACM CCS 1999, November 1-4, 1999, pp. 28–36. ACM, New York (1999)
Hao, F., Anderson, R., Daugman, J.: Combining Crypto with Biometrics Effectively. IEEE Transactions on Computers 55(9), 1081–1088 (2006)
Hochquenghem, A.: Codes Correcteurs D’erreurs. Chiffres 2, 147–156 (1959)
Bose, R.C., Ray-Chaudhuri, D.K.: On a Class of Error-Correcting Binary Group Codes. Information and Control 3, 68–79 (1960)
Forney Jr., G.D.: Concatenated Codes. Research Monograph No. 37. MIT Press, Cambridge (1966)
Blahut, R.E.: Theory and Practice of Error Control Codes, 1st edn. Addison-Wesley Publishing Company, Reading (1985)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland Mathematical Library, vol. 16. North-Holland/Elsevier, Amsterdam (1977)
Carter, L., Wegman, M.N.: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)
Xilinx: Device Reliability Report — Fourth Quarter 2007. Technical Report UG116 (v4.3) (February 6, 2008), http://www.xilinx.com/support/documentation/
Altera: Reliability Report 45 — Q2 2007. Technical report (2007), http://www.altera.com/literature/lit-index.html .
MacKay, D.J.C.: Good Error-Correcting Codes Based on Very Sparse Matrices. IEEE Transactions on Information Theory 45(2), 399–431 (1999)
Levine, B.A., Reed Taylor, R., Schmit, H.: Implementation of Near Shannon Limit Error-Correcting Codes Using Reconfigurable Hardware. In: IEEE Symposium on Field-Programmable Custom Computing Machines — FCCM 2000, April 17-19, 2000, pp. 217–226. IEEE Computer Society, Los Alamitos (2000)
Brack, T., Kienle, F., Wehn, N.: Disclosing the LDPC code decoder design space. In: Gielen, G.G.E. (ed.) Conference on Design, Automation and Test in Europe — DATE 2006, European Design and Automation Association, Leuven, Belgium, March 6-10, 2006, pp. 200–205 (2006)
Bösch, C.: Efficient fuzzy extractors for reconfigurable hardware. Master’s thesis, Chair for System Security, Department of Electrical Engineering and Information Science, Ruhr-Universität Bochum (March 2008)
Desset, C., Macq, B., Vandendorpe, L.: Block error-correcting codes for systems with a very high BER: Theoretical analysis and application to the protection of watermarks. Signal Processing: Image Communication 17(5), 409–421 (2002)
Desset, C., Macq, B.M., Vandendorpe, L.: Computing the word-, symbol-, and bit-error rates for block error-correcting codes. IEEE Transactions on Communications 52(6), 910–921 (2004)
Krawczyk, H.: LFSR-based Hashing and Authentication. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 129–139. Springer, Heidelberg (1994)
Nevelsteen, W., Preneel, B.: Software Performance of Universal Hash Functions. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 24–41. Springer, Heidelberg (1999)
Kaps, J.P., Yüksel, K., Sunar, B.: Energy Scalable Universal Hashing.. IEEE Trans. Computers 54(12), 1484–1495 (2005)
Vanstone, S.A., van Oorschot, P.C.: An Introduction to Error Correcting Codes with Applications. Kluwer Academic Publishers, Dordrecht (1989)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bösch, C., Guajardo, J., Sadeghi, AR., Shokrollahi, J., Tuyls, P. (2008). Efficient Helper Data Key Extractor on FPGAs. In: Oswald, E., Rohatgi, P. (eds) Cryptographic Hardware and Embedded Systems – CHES 2008. CHES 2008. Lecture Notes in Computer Science, vol 5154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85053-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-85053-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85052-6
Online ISBN: 978-3-540-85053-3
eBook Packages: Computer ScienceComputer Science (R0)