Entropy computation for oscillator-based physical random number generators. (English) Zbl 07814956
Summary: In this paper, we provide a complete set of algorithms aimed at the design and security evaluation of oscillator-based True Random Number Generators (TRNG). While depending on some TRNG design assumptions, the proposed algorithms use as inputs the statistical parameters of the underlying random physical process such as the clock jitter originating from the thermal noise and give a lower bound of the entropy rate of the generated bit stream as output. We describe the general structure of a TRNG composed of multiple free-running oscillators and samplers, the outputs of which are post-processed by an entropy conditioner. Depending on the specification of the entropy conditioner, which can usually be any Boolean function, we describe several algorithmic optimizations. We then explain how to compute and efficiently manage the entropy rate at the output of such a post-processing block and at the output of the generator as a whole.
MSC:
| 68P25 | Data encryption (aspects in computer science) |
| 94A60 | Cryptography |
| 94A62 | Authentication, digital signatures and secret sharing |
Keywords:
hardware random number generators; free-running oscillators; stochastic models; entropy; dedicated statistical testsSoftware:
GitHubReferences:
| [1] | Allini, EN; Skorski, M.; Petura, O.; Bernard, F.; Laban, M.; Fischer, V., Evaluation and monitoring of free running oscillators serving as source of randomness, Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2018, 3, 214-242, 2018 · doi:10.46586/tches.v2018.i3.214-242 |
| [2] | R. B. Ash. Information Theory. Dover Publications, Inc., New York, 1990. Corrected reprint of the 1965 original. · Zbl 0768.94005 |
| [3] | B. Barak and S. Halevi. An architecture for robust pseudo-random generation with applications to /dev/random. In Proc. of the 12th ACM Conference on Computer and Communication Security (CCS’05), pages 203-212, 2005. |
| [4] | Baudet, M.; Lubicz, D.; Micolod, J.; Tassiaux, A., On the Security of Oscillator-based Random Number Generators, Journal of Cryptology, 24, 398-425, 2011 · Zbl 1251.94021 · doi:10.1007/s00145-010-9089-3 |
| [5] | P. Bayon, L. Bossuet, A. Aubert, and V. Fischer. Electromagnetic analysis on ring oscillator-based true random number generators. In 2013 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1954-1957, 2013. |
| [6] | Bernard, F.; Fischer, V.; Valtchanov, B., Mathematical Model of Physical RNGs Based on Coherent Sampling, Tatra Mountains Mathematical Publications, 45, 1, 1-14, 2010 · Zbl 1274.94041 · doi:10.2478/v10127-010-0001-1 |
| [7] | A. Cherkaoui, V. Fischer, L. Fesquet, and A. Aubert. A Very High Speed True Random Number Generator with Entropy Assessment. In G. Bertoni and J. S. Coron, editors, Cryptographic Hardware and Embedded Systems - CHES 2013, volume 8086 of LNCS, pages 179-196. Springer, 2013. |
| [8] | M. Dichtl. Bad and Good Ways of Post-processing Biased Physical Random Numbers. In Fast Software Encryption - FSE 2007, volume 4593 of LNCS, pages 137-152. Springer Verlag, 2007. · Zbl 1153.94368 |
| [9] | Fino, B.; Algazi, V., Unified Matrix Treatment of the Fast Walsh-Hadamard Transform, IEEE Transactions on Computers, 100, 11, 1142-1146, 1976 · Zbl 0357.44004 · doi:10.1109/TC.1976.1674569 |
| [10] | Fischer, V.; Bernard, F.; Bochard, N., Modern random number generator design - Case study on a secured PLL-based TRNG, It - Information Technology, 61, 1, 3-13, 2019 · doi:10.1515/itit-2018-0025 |
| [11] | V. Fischer and D. Lubicz. Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG. In L. Batina and M. Robshaw, editors, Cryptographic Hardware and Embedded Systems - CHES 2014, volume 8731 of LNCS, pages 527-543. Springer, 2014. |
| [12] | T. Guneysu. True Random Number Generation in Block Memories of Reconfigurable Devices. In International Conference on Field-Programmable Technology - FPT 2010, pages 200-207. IEEE Press, 2011. |
| [13] | P. Haddad, F. Bernard, V. Fischer, and Y. Teglia. On the Assumption of Mutual Independence of Jitter Realizations in P-TRNG Stochastic Models. In Design, Automation and Test in Europe - DATE 2014, Dresden, Germany. IEEE, 2014. |
| [14] | W. Killmann and W. Schindler. A Design for a Physical RNG with Robust Entropy Estimators. In E. Oswald and P. Rohatgi, editors, Cryptographic Hardware and Embedded Systems - CHES 2008, volume 5154 of LNCS, pages 146-163. Springer, 2008. |
| [15] | W. Killmann and W. Schindler. A proposal for: Functionality classes for random number generators, version 2.0. [online] Available at: https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_31_Functionality_classes_for_random_number_generators_e.pdf, 2011. Accessed: 2023-10-31. |
| [16] | M. Laban, M. Drutarovsky, V. Fischer, and M. Varchola. Platform for testing and evaluation of PUF and TRNG implementations in FPGAs. In TRUDEVICE - 6th Conference on Trustworthy Manufacturing and Utilization of Secure Devices (TRUDEVICE 2016), Barcelona, Spain, November 2016. |
| [17] | D. Lubicz. TRNG Test Suite. [online] Available at: https://github.com/dlubicz/MOTRNG, 2022. Accessed: 2022-01-23. |
| [18] | Markettos, AT; Moore, SW; Clavier, Christophe; Gaj, Kris, The Frequency Injection Attack on Ring-Oscillator-Based True Random Number Generators, Cryptographic Hardware and Embedded Systems - CHES 2009, 317-331, 2009, Berlin Heidelberg: Springer, Berlin Heidelberg · doi:10.1007/978-3-642-04138-9_23 |
| [19] | Mureddu, U.; Bochard, N.; Bossuet, L.; Fischer, V., Experimental study of locking phenomena on oscillating rings implemented in logic devices, IEEE Transactions on Circuits and Systems I: Regular Papers, 66, 7, 2560-2571, 2019 · doi:10.1109/TCSI.2019.2900017 |
| [20] | M. Peter and W. Schindler. A proposal for Functionality classes for random number generators, version 2.35 - DRAFT. [online] Available at: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Certification/Interpretations/AIS_31_Functionality_classes_for_random_number_generators_e.pdf, 2022. Accessed: 2023-10-31. |
| [21] | W. Schindler and W. Killmann. Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications. In B. S. Kaliski, C. Koç, and C. Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2002, volume 2523 of LNCS, pages 431-449. Springer, 2003. · Zbl 1019.65502 |
| [22] | Shannon, CE, A Mathematical Theory of Communication, Bell System Tech. J., 27, 379-423, 623-656, 1948 · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb00917.x |
| [23] | Sunar, B.; Martin, WJ; Stinson, DR, A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks, IEEE Transactions on Computers, 56, 1, 109-119, 2007 · Zbl 1391.94799 · doi:10.1109/TC.2007.250627 |
| [24] | G. Taylor and G. Cox. Behind Intel’s New Random-Number Generator. [online] Available at: https://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator, 2011. Accessed: 2023-10-31. |
| [25] | M. Varchola and M. Drutarovsky. New High Entropy Element for FPGA Based True Random Number Generators. In S. Mangard and F.X. Standaert, editors, Cryptographic Hardware and Embedded Systems - CHES 2010, volume 6225 of LNCS, pages 351-365. Springer, 2010. · Zbl 1434.94079 |
| [26] | I. Vasyltsov, E. Hambardzumyan, Y.-S. Kim, and B. Karpinskyy. Fast Digital TRNG Based on Metastable Ring Oscillator. In E. Oswald and P. Rohatgi, editors, Cryptographic Hardware and Embedded Systems - CHES 2008, volume 5154 of LNCS, pages 164-180. Springer, 2008. |
| [27] | X. Wu, Y. Ma, J. Yang, T. Chen, and J. Lin. On the Security of TRNGs Based on Multiple Ring Oscillators. In S. Chen, K. Choo, X. Fu, W. Lou, and A. Mohaisen, editors, Security and Privacy in Communication Networks - SecureComm 2019, volume 305 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. Springer, 2019. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
