Security Evaluation of Bistable Ring PUFs on FPGAs using Differential and Linear Analysis

• Autorzy: Dai Yamamoto , Masahiko Takenaka , Kazuo Sakiyama , Naoya Torii
• Języki publikacji: EN

Abstrakty

EN

Physically Unclonable Function (PUF) is expected to be an innovation for anti-counterfeiting devices for secure ID generation, authentication, etc. In this paper, we propose novel methods of evaluating the difficulty of predicting PUF responses (i.e. PUF outputs), inspired by well-known differential and linear cryptanalysis. According to the proposed methods, we perform a first third-party evaluation for Bistable Ring PUF (BR-PUF), proposed in 2011. The BR-PUFs have been claimed that they have a resistance against the response predictions. Through our experiments using FPGAs, we demonstrate, however, that BR-PUFs have two types of correlations between challenges and responses, which may cause the easy prediction of PUF responses. First, the same responses are frequently generated for two challenges (i.e. PUF inputs) with small Hamming distance. A number of randomly-generated challenges and their variants with Hamming distance of one generate the same responses with the probability of 0.88, much larger than 0.5 in ideal PUFs. Second, particular bits of challenges in BR-PUFs have a great impact on the responses. The value of responses becomes `1' with the high probability of 0.71 (> 0.5) when just particular 5 bits of 64-bit random challenges are forced to be zero or one. In conclusion, the proposed evaluation methods reveal that BR-PUFs on FPGAs have some correlations of challenge-response pairs, which helps an attacker to predict the responses.(original abstract)

Słowa kluczowe

EN

Authentication; Data encryption; Data encryption technique

PL

Uwierzytelnianie; Szyfrowanie danych; Techniki szyfrowania danych

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 911--918

Twórcy

autor

Dai Yamamoto

• Fujitsu Laboratories Ltd.

autor

Masahiko Takenaka

• Fujitsu Laboratories Ltd.

autor

Kazuo Sakiyama

• The University of Electro-Communications, Japan

autor

Naoya Torii

• Fujitsu Laboratories Ltd.

Bibliografia

• "Characterization of the Bistable Ring PUF," in Design, Automation & Test in Europe Conference & Exhibition (DATE 2012), 2012. doi: 10.1109/DATE.2012.6176596. [Online]. Available: http://doi.ieeecomputersociety.org/10.1109/DATE.2012.6176596
• Biham E. and Shamir A., "Differential Cryptanalysis of DES-like Cryptosystems," J. Cryptology, vol. 4, no. 1, pp. 3-72, 1991. doi: 10.1007/BF00630563. [Online]. Available: http://dx.doi.org/10.1007/BF00630563
• Chen Q, Csaba G., Lugli P., Schlichtmann U., and Ruhrmair U., "The Bistable Ring PUF: A New Architecture for Strong Physical Unclonable Functions," in Hardware-Oriented Security and Trust (HOST 2011), 2011. doi: 10.1109/HST.2011.5955011. [Online]. Available: http://dx.doi.org/10.1109/HST.2011.5955011
• Gassend B., Clarke D. E., van Dijk M., and Devadas S., "Silicon physical random functions," in ACM Conference on Computer and Communications Security, 2002. doi: 10.1145/586110.586132 pp. 148-160. [Online]. Available: http://doi.acm.org/10.1145/586110.586132
• Gassend B., Clarke D., Lim D., van Dijk M., and Devadas S., "Identification and Authentication of Integrated Circuits," Concurrency - Practice and Experience, vol. 16, no. 11, pp. 1077-1098, 2004. doi: 10.1002/cpe.805. [Online]. Available: http://dx.doi.org/10.1002/cpe.805
• Lee J. W., Lim D., Gassend B., Suh G. E., van Dijk M., and Devadas S., "A Technique to Build a Secret Key in Integrated Circuits for Identification and Authentication Applications," in IEEE VLSI Circuits Symposium 2004, 2004. doi: 10.1109/VLSIC.2004.1346548 pp. 176-179. [Online]. Available: http://dx.doi.org/10.1109/VLSIC.2004.1346548
• Maes R. and Verbauwhede I., "Physically Unclonable Functions: A Study on the State of the Art and Future Research Directions," in Towards Hardware Intrinsic Security: Foundation and Practice. Springer, 2010, pp. 3-37. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-14452-3 1
• Maiti A., Gunreddy V., and Schaumont P., "A Systematic Method to Evaluate and Compare the Performance of Physical Unclonable Functions," in Embedded Systems Design with FPGAs. Springer New York, 2013, pp. 245-267. [Online]. Available: http://dx.doi.org/10.1007/978-1-4614-1362-2 11
• Matsui M., "Linear Cryptoanalysis Method for DES Cipher," in EUROCRYPT, 1993. doi: 10.1007/3-540-48285-7 33 pp. 386-397. [Online]. Available: http://dx.doi.org/10.1007/3-540-48285-7 33
• Pappu R. S., "Physical One-Way Functions," Ph.D. dissertation, Massachusetts Institute of Technology, 2001.
• Ruhrmair U., Sehnke F., Solter J., Dror G., Devadas S., and Schmidhuber J., "Modeling Attacks on Physical Unclonable Functions," in ACM Conference on Computer and Communications Security, 2010. doi: 10.1145/1866307.1866335 pp. 237-249. [Online]. Available: http://dx.doi.org/10.1145/1866307.1866335
• Su Y., Holleman J., and Otis B. P., "A Digital 1.6pJ/bit Chip Identification Circuit Using Process Variations," Solid-State Circuits, IEEE Journal of, vol. 43, no. 1, pp. 69-77, 2008. doi: 10.1109/JSSC.2007.910961. [Online]. Available: http://dx.doi.org/10.1109/JSSC.2007.910961
• Su Y., Holleman J., and Otis B., "A 1.6pJ/bit 96% Stable Chip-ID Generating Circuit using Process Variations," in IEEE International Solid-State Circuits Conference (ISSCC 2007), 2007. doi: 10.1109/ISSCC.2007.373466 pp. 406-611. [Online]. Available: http://dx.doi.org/10.1109/ISSCC.2007.373466
• Suh G. E. and Devadas S., "Physical Unclonable Functions for Device Authentication and Secret Key Generation," in Design Automation Conference (DAC 2007), 2007. doi: 10.1109/DAC.2007.375043 pp. 9-14. [Online]. Available: http://doi.ieeecomputersociety.org/10.1109/DAC.2007.375043
• Torrance R. and James D., "The State-of-the-Art in IC Reverse Engineering," in Cryptographic Hardware and Embedded Systems (CHES 2009), 2009. doi: 10.1007/978-3-642-04138-9 26 pp. 363-381. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-04138-9 26
• Ward R. and Molteno T., "Table of Linear Feedback Shift Registers," University of Otago, New Zealand, Tech. Rep., 2007. [Online]. Available: http://www.eej.ulst.ac.uk/~ian/modules/EEE515/files/old files/lfsr/lfsr table.pdf
• Yamamoto D., Takenaka M., and Torii N., "Performance and Security Evaluation of BR-PUF on FPGAs (in Japanese)," in The 30th Symposium on Cryptography and Information Security (SCIS 2013), 2013.