×

Comparative analysis of random generators. (English) Zbl 07293164

Pillwein, Veronika (ed.) et al., Algorithmic combinatorics: enumerative combinatorics, special functions and computer algebra. Proceedings of the workshop on combinatorics, special functions and computer algebra (Paule60), Research Institute of Symbolic Computation (RISC), Hagenberg, Austria, May 17–18, 2018. In honour of Peter Paule on his 60th birthday. Cham: Springer. Texts Monogr. Symb. Comput., 181-196 (2020).
Summary: We report on experiments with selected software and hardware (pseudo)random generators under controlled conditions and compare their throughput and consumed entropy. In software, we distinguish between number theoretic generators (which come with corresponding security reductions) and generators based on AES. True random generators covered by our study are the physical hardware generator PRG310-4 and the generators /dev/random and /dev/urandom as implemented in the Linux kernel.
For the entire collection see [Zbl 1455.68025].

MSC:

68W30 Symbolic computation and algebraic computation

Software:

Nginx; gmp
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Werner Alexi, Benny Chor, Oded Goldreich & Claus P. Schnorr (1988). RSA and Rabin functions: Certain Parts are As Hard As the Whole. SIAM Journal on Computing17(2), 194-209. ISSN 0097-5397. https://doi.org/10.1137/0217013. · Zbl 0644.94011 · doi:10.1137/0217013
[2] Frank Bergmann (2019). Professionelle Zufallsgeneratoren für kryptografisch sichere Zufallszahlen. http://www.ibbergmann.org/.
[3] D. J. Bernstein (2014). cr.yp.to: 2014.02.05: Entropy Attacks! http://blog.cr.yp.to/20140205-entropy.html. Last access 27 June 2015.
[4] L. Blum, M. Blum & M. Shub (1986). A simple unpredictable pseudo-random number generator. SIAM Journal on Computing15(2), 364-383. https://doi.org/10.1137/0215025. · Zbl 0602.65002 · doi:10.1137/0215025
[5] A. Borodin, J. von zur Gathen & J. E. Hopcroft (1982). Fast parallel matrix and GCD Computations. Information and Control52, 241-256. http://dx.doi.org/10.1016/S0019-9958(82)90766-5. Extended Abstract in Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago IL (1982). · Zbl 0507.68020 · doi:10.1016/S0019-9958(82)90766-5
[6] BSI (2019a). Kryptographische Verfahren: Empfehlungen und Schlüssellängen. Technische Richtlinie BSI TR-02102-1, Bundesamt für Sicherheit in der Informationstechnik, Bonn, Germany. https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.pdf.
[7] BSI (2019b). Overview of Linux kernels with NTG.1-compliant random number generator /dev/random. Technical report, Bundesamt für Sicherheit in der Informationstechnik. https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Studien/LinuxRNG/NTG1_Kerneltabelle_EN.pdf.
[8] Aleksei Burlakov, Johannes vom Dorp, Joachim von zur Gathen, Sarah Hillmann, Michael Link, Daniel Loebenberger, Jan Lühr, Simon Schneider & Sven Zemanek (2015a). Comparative analysis of pseudorandom generators. In Proceedings of the 22nd Crypto-Day, 9-10 July 2015, Munich. Gesellschaft für Informatik. http://fg-krypto.gi.de/fileadmin/fg-krypto/Handout-22.pdf.
[9] Aleksei Burlakov, Johannes vom Dorp, Sarah Hillmann, Michael Link, Jan Lühr, Simon Schneider & Sven Zemanek (2015b). Comparative analysis of pseudorandom generators: Source code. BitBucket. https://bitbucket.org/sirsimonrattle/15ss-taoc.
[10] Jim Clarke (2019). An Optimist’s View of the 4 Challenges to Quantum Computing. IEEE Spectrumhttps://spectrum.ieee.org/tech-talk/computing/hardware/an-optimists-view-of-the-4-challenges-to-quantum-computing.
[11] Scott Contini & Igor E. Shparlinski (2005). On Stern’s Attack Against Secret Truncated Linear Congruential Generators. In Information Security and Privacy—10th Australasian Conference, ACISP 2005, Brisbane, Australia, July 4-6, 2005. Proceedings, Colin Boyd & Juan Manuel González Nieto, editors, volume 3574 of Lecture Notes in Computer Science, 52-60. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-26547-4 (Print) 978-3-540-31684-8 (Online). ISSN 0302-9743. https://doi.org/10.1007/11506157_5. · Zbl 1127.94342 · doi:10.1007/11506157_5
[12] Stephen A. Cook (1971). The Complexity of Theorem-Proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights OH, 151-158. ACM Press. · Zbl 0253.68020
[13] Mikhail Dyakonov (2018). The Case Against Quantum Computing. IEEE Spectrum. https://spectrum.ieee.org/computing/hardware/the-case-against-quantum-computing.
[14] D. Eastlake, J. Schiller & S. Crocker (2005). Randomness Requirements for Security. BCP 106, RFC Editor. http://www.rfc-editor.org/rfc/rfc4086.txt.
[15] R. Fischlin & C. P. Schnorr (2000). Stronger Security Proofs for RSA and Rabin Bits. Journal of Cryptology13(2), 221-244. https://doi.org/10.1007/s001459910008. Communicated by Oded Goldreich. · Zbl 1060.94018 · doi:10.1007/s001459910008
[16] Joachim von zur Gathen & Daniel Loebenberger (2018). Why one cannot estimate the entropy of English by sampling. Journal of Quantitative Linguistics25(1), 77-106. https://doi.org/10.1080/09296174.2017.1341724. · doi:10.1080/09296174.2017.1341724
[17] Oded Goldreich (2001). Foundations of Cryptography, volume I: Basic Tools. Cambridge University Press, Cambridge. ISBN 0-521-79172-3. · Zbl 1007.94016 · doi:10.1017/CBO9780511546891
[18] Oded Goldreich, Amit Sahai & Salil Vadhan (1999). Can Statistical Zero Knowledge Be Made Non-interactive? Or On the Relationship of \(\mathcal{S}\mathcal{Z}\mathcal{K}\) and \(\mathcal{N}\mathcal{I}\mathcal{S}\mathcal{Z}\mathcal{K} \). In Advances in Cryptology: Proceedings of CRYPTO 1999, Santa Barbara, CA, M. Wiener, editor, volume 1666 of Lecture Notes in Computer Science, 467-484. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-48405-9 (Online) 978-3-540-66347-8 (Print). ISSN 0302-9743. https://doi.org/10.1007/3-540-48405-1_30. · doi:10.1007/3-540-48405-1_30
[19] Torbjörn Granlund (2014). The GNU Multiple Precision Arithmetic Library. C library. https://gmplib.org/. Last access 25th June 2015.
[20] Shay Gueron (2010). Intel^® Advanced Encryption Standard (AES) New Instructions Set: White paper. Technical report, Intel Corporation.
[21] Zvi Gutterman, Benny Pinkas & Tzachy Reinman (2006). Analysis of the Linux Random Number Generator. In Proceedings of the 2006 IEEE Symposium on Security and Privacy, 371-385. IEEE Computer Society. ISBN 0-7695-2574-1. https://doi.org/10.1109/SP.2006.5. Also available at http://eprint.iacr.org/2006/086. · doi:10.1109/SP.2006.5
[22] Johan Håstad & Adi Shamir (1985). The Cryptographic Security of Truncated Linearly Related Variables. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, 356-362. ACM, New York, NY, USA. ISBN 0-89791-151-2. https://doi.org/10.1145/22145.22184. · doi:10.1145/22145.22184
[23] Wolfgang Killmann & Werner Schindler (2008). A Design for a Physical RNG with Robust Entropy Estimators. In CHES 2008, Elisabeth Oswald & Pankaj Rohatgi, editors, volume 5154 of LNCS, 146-163. ISBN 978-3-540-85052-6. https://doi.org/10.1007/978-3-540-85053-3_10. · doi:10.1007/978-3-540-85053-3_10
[24] Wolfgang Killmann & Werner Schindler (2011). A proposal for: Functionality classes for random number generators. Anwendungshinweise und Interpretationen zum Schema AIS 20/AIS 31, Bundesamt für Sicherheit in der Informationstechnik, Bonn, Germany. https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_31_Functionality_classes_for_random_number_generators_e.pdf?__blob=publicationFile. Version 2.0.
[25] Patrick Lacharme, Andrea Röck, Vincent Strubel & Marion Videau (2012). The Linux Pseudorandom Number Generator Revisited. https://eprint.iacr.org/2012/251.pdf. Last access 27 June 2015.
[26] D. H. Lehmer (1951). Mathematical methods in large-scale computing units. In Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 13-16 September 1949, volume 26 of Annals of the Computation Laboratory of Harvard University, 141-146. Harvard University Press, Cambridge, Massachusetts. https://archive.org/details/proceedings_of_a_second_symposium_on_large-scale_. · Zbl 0045.40001
[27] Daniel Loebenberger & Michael Nüsken (2014). Notions for RSA integers. International Journal of Applied Cryptography3(2), 116-138. ISSN 1753-0571 (online), 1753-0563 (print). http://dx.doi.org/10.1504/IJACT.2014.062723. · Zbl 1351.94061 · doi:10.1504/IJACT.2014.062723
[28] Stephan Müller (2019). Documentation and Analysis of the Linux Random Number Generator. Technical report, atsec information security GmbH for the Federal Office for Information Security. https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN.pdf.
[29] NGINX (2016). Sizing Guide for Deploying NGINX Plus on Bare Metal Servers. Technical report, NGINX Inc. https://cdn-1.wp.nginx.com/wp-content/files/nginx-pdfs/Sizing-Guide-for-Deploying-NGINX-on-Bare-Metal-Servers.pdf. Last access 16 August 2017.
[30] NIST (2001a). Federal Information Processing Standards Publication 197—Announcing the ADVANCED ENCRYPTION STANDARD (AES). National Institute of Standards and Technology. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf. Federal Information Processings StandardsPublication 197.
[31] NIST (2001b). NIST Special Publication 800-38A: Recommendation for Block Cipher Modes of Operation.
[32] NIST (2015). NIST Special Publication 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf.
[33] Joan B. Plumstead (1982). Inferring a Sequence Generated by a Linear Congruence. Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago IL 153-159. https://doi.org/10.1109/SFCS.1982.73. Published as Joan Boyar, Inferring Sequences Produced by Pseudo-Random Number Generators, Journal of the ACM 36 (1), 1989, pages 129-141, https://doi.org/10.1145/58562.59305. · Zbl 0667.94006 · doi:10.1145/58562.59305
[34] Werner Schindler & Wolfgang Killmann (2003). Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications. In Cryptographic Hardware and Embedded Systems—CHES 2002, Jr. Burton S. Kaliski, Çetin K. Koç & Christof Paar, editors, volume 2523 of LNCS, 431-449. Springer-Verlag, Berlin, Heidelberg. ISSN 0302-9743 (Print), 1611-3349 (Online). https://doi.org/10.1007/3-540-36400-5_31. · Zbl 1019.65502 · doi:10.1007/3-540-36400-5_31
[35] Bruce Schneier (2008). Random Number Bug in Debian Linux. Weblog. https://www.schneier.com/blog/archives/2008/05/random_number_b.html.
[36] Chris Searle (2008). Increase entropy on a 2.6 kernel Linux box. https://www.chrissearle.org/2008/10/13/Increase_entropy_on_a_2_6_kernel_linux_box/. Last access 27 June 2015.
[37] Adi Shamir (1983). On the Generation of Cryptographically Strong Pseudorandom Sequences. ACM Trans. Comput. Syst.1(1), 38-44. ISSN 0734-2071. https://doi.org/10.1145/357353.357357. · doi:10.1145/357353.357357
[38] Peter W. Shor (1999). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review41(2), 303-332. · Zbl 1005.11507 · doi:10.1137/S0036144598347011
[39] Ron Steinfeld, Josef Pieprzyk & Huaxiong Wang (2006). On the Provable Security of an Efficient RSA-Based Pseudorandom Generator. In Advances in Cryptology: Proceedings of ASIACRYPT 2006, Shanghai, China, Xuejia Lai & Kefei Chen, editors, volume 4284 of Lecture Notes in Computer Science, 194-209. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-49475-1. ISSN 0302-9743 (Print) 1611-3349 (Online). https://doi.org/10.1007/11935230_13. · Zbl 1172.94597 · doi:10.1007/11935230_13
[40] Jacques Stern (1987). Secret linear congruential generators are not cryptographically secure. Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles CA 421-426.
[41] Theodore Ts’o (2016). Commit of ChaCha based urandom to Linux kernel. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=e192be9d9a30555aae2ca1dc3aad37cba484cd4a. Last access 29 August 2017.
[42] Umesh V. Vazirani & Vijay V. Vazirani (1984). Efficient and Secure Pseudo- · Zbl 0579.65005
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.