Recommendations on Statistical Randomness Test Batteries for Cryptographic Purposes

  1. Almaraz Luengo, Elena 1
  2. García Villalba, Luis Javier 2
  1. 1 Group of Analysis, Security and Systems (GASS), Department of Statistic and Operational Research, Faculty of Mathematical Science, Universidad Complutense de Madrid (UCM)
  2. 2 Group of Analysis, Security and Systems (GASS), Department of Software Engineering and Artificial Intelligence (DISIA), Faculty of Computer Science and Engineering, Office 431, Universidad Complutense de Madrid (UCM)
Revista:
ACM Computing Surveys

ISSN: 0360-0300,  1557-7341

Año de publicación: 2021

Volumen: 54

Número: 4

Páginas: 1-34

Tipo: Artículo

DOI: 10.1145/3447773 GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: ACM Computing Surveys

Resumen

Security in different applications is closely related to the goodness of the sequences generated for such purposes. Not only in Cryptography but also in other areas, it is necessary to obtain long sequences of random numbers or that, at least, behave as such. To decide whether the generator used produces sequences that are random, unpredictable and independent, statistical checks are needed. Different batteries of hypothesis tests have been proposed for this purpose.In this work, a survey of the main test batteries is presented, indicating their pros and cons, giving some guidelines for their use and presenting some practical examples.

€ Ver financiación

Información de financiación

Financiadores

  • UCM
    • FEI-EU-19-04

Referencias bibliográficas

  • 10.1109/TCSI.2011.2108050
  • 10.5555/2699234.2699235
  • 10.1109/18.669305
  • 10.1109/TII.2018.2815985
  • 10.1109/TIFS.2015.2471279
  • Brown R. G., (2014), Dieharder: A random number test suite (version 3.31.1).
  • Caelli W., (1999), Crypt-X Package Documentation
  • G. Casella and R. L. Berger. 2002. Statistical Inference (2nd ed.). Duxbury Thomson Learning. G. Casella and R. L. Berger. 2002. Statistical Inference (2nd ed.). Duxbury Thomson Learning.
  • Information Technology Laboratory ST., (2010), Computer Security Resource Center
  • Demirhan H., (2016), J. Stat.: Stat. Actuar. Sci., 9, pp. 1
  • 10.1177/0037549717726145
  • Doganaksoy A., Proceedings of the National Cryptology Symposium II.
  • Doganaksoy A., Proceedings of the Information Security and Cryptography Conference.
  • 10.1155/2015/626408
  • 10.3906/elk-1503-214
  • D. Eddelbuettel. 2019. RDieharder. Retrieved from https://CRAN.R-project.org/package=RDieHarder. D. Eddelbuettel. 2019. RDieharder. Retrieved from https://CRAN.R-project.org/package=RDieHarder.
  • 10.1145/200883.200896
  • 10.1214/aoms/1177692552
  • M. Fischler. 2002. Distribution of minimum distance among N random points in d dimensions. DOI:https://doi.org/10.2172/794005 M. Fischler. 2002. Distribution of minimum distance among N random points in d dimensions. DOI:https://doi.org/10.2172/794005
  • 10.5555/3037673.3037694
  • 10.1049/el:19980499
  • 10.1016/S0893-9659(00)00191-9
  • Gentle J. E., Random Number Generation and Monte Carlo Methods (2nd. ed.)
  • Gjorgjievski S., Proceedings of the ICT Innovations. Springer International Publishing, Cham, 80–92
  • 10.1017/S030500410002836X
  • 10.1109/18.868485
  • 10.1109/18.256486
  • 10.1109/TIT.2016.2530084
  • J. Hernández-Castro J. Sierra A. Seznec A. Izquierdo and A. Ribagorda. 2005. The strict avalanche criterion randomness test. Math. Comput. Simul. 68 (Feb. 2005) 1–7. DOI:https://doi.org/10.1016/j.matcom.2004.09.001 J. Hernández-Castro J. Sierra A. Seznec A. Izquierdo and A. Ribagorda. 2005. The strict avalanche criterion randomness test. Math. Comput. Simul. 68 (Feb. 2005) 1–7. DOI:https://doi.org/10.1016/j.matcom.2004.09.001
  • 10.1109/TII.2019.2923553
  • 10.1109/TIT.2019.2947045
  • 10.1049/el:19870268
  • D. Knuth and A. Yao. 1976. The Complexity of Nonuniform Random Number Generation. 357–4428. D. Knuth and A. Yao. 1976. The Complexity of Nonuniform Random Number Generation. 357–4428.
  • D. E. Knuth. 1997. The Art of Computer Programming Volume 2/Seminumerical Algorithms (3rd. ed.). Addison-Wesley Longman Publishing Boston MA. D. E. Knuth. 1997. The Art of Computer Programming Volume 2/Seminumerical Algorithms (3rd. ed.). Addison-Wesley Longman Publishing Boston MA.
  • 10.1109/TIT.2009.2027483
  • 10.1145/1268776.1268777
  • P. L’Ecuyer and R. Simard. 2009. TestU01-1.2.3. Retrieved from http://simul.iro.umontreal.ca/testu01/tu01.html. P. L’Ecuyer and R. Simard. 2009. TestU01-1.2.3. Retrieved from http://simul.iro.umontreal.ca/testu01/tu01.html.
  • 10.1109/TIFS.2019.2908798
  • H. Maaranen K. Miettinen and M. M. Mákelá. 2003. Using Quasi Random Sequences in Genetic Algorithms. Springer Netherlands Dordrecht 33–44. DOI:https://doi.org/10.1007/978-94-017-2494-4_4 H. Maaranen K. Miettinen and M. M. Mákelá. 2003. Using Quasi Random Sequences in Genetic Algorithms. Springer Netherlands Dordrecht 33–44. DOI:https://doi.org/10.1007/978-94-017-2494-4_4
  • Marsaglia G., (2016), The Marsaglia random number CDROM: Including the diehard battery of tests of randomness
  • 10.18637/jss.v007.i03
  • Martin H., (2016), IEEE Trans. Industr. Info., 12, pp. 91, 10.1109/TII.2015.2502183
  • M. Mascagni and J. Ren. 2003. Sprng user’s guide: Physical model tests. Retrieved from http://www.sprng.org/Version2.0/physical-model-tests.html. M. Mascagni and J. Ren. 2003. Sprng user’s guide: Physical model tests. Retrieved from http://www.sprng.org/Version2.0/physical-model-tests.html.
  • 10.1145/358407.358427
  • 10.5555/148544.148545
  • Oak R., (1953), Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS’19)
  • 10.1109/TIFS.2017.2656473
  • 10.1109/TIFS.2012.2185227
  • Ross S. M., Simulation
  • R. Y. Rubinstein and D. P. Kroese. 2016. Simulation and the Monte Carlo Method (3rd. ed.). John Wiley & Sons. R. Y. Rubinstein and D. P. Kroese. 2016. Simulation and the Monte Carlo Method (3rd. ed.). John Wiley & Sons.
  • Rukhin A., (2000), Testing randomness: A suite of statistical procedures. Theory Prob. Appl. 45 (apr
  • A. L. Rukhin J. Soto J. R. Nechvatal M. E. Smid E. Barker S. Leigh M. Levenson M. Vangel D. Banks A. Heckert J. Dray and S. Vo. 2010. SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Technical Report. Gaithersburg MD. A. L. Rukhin J. Soto J. R. Nechvatal M. E. Smid E. Barker S. Leigh M. Levenson M. Vangel D. Banks A. Heckert J. Dray and S. Vo. 2010. SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Technical Report. Gaithersburg MD.
  • 10.1016/j.jspi.2004.02.010
  • 10.1016/S0378-3758(03)00149-6
  • Zhu S., Proceedings of the Conference on Advances in Cryptology (ASIACRYPT’16)
  • Sadique J. K. M., (2012), J. Theor. Phys. Cryptogr., 1, pp. 18
  • 10.1016/j.diin.2011.06.005
  • M. Sýs D. Klinec K. Kubícek and P. Svenda. 2019. BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES 3-DES MD5 MD6 and SHA-256. M. Obaidat and E. Cabello (eds). Springer Cham 123–149. DOI:https://doi.org/10.1007/978-3-030-11039-0_7 M. Sýs D. Klinec K. Kubícek and P. Svenda. 2019. BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES 3-DES MD5 MD6 and SHA-256. M. Obaidat and E. Cabello (eds). Springer Cham 123–149. DOI:https://doi.org/10.1007/978-3-030-11039-0_7
  • A. Tayfur and B. Melamed. 2007. Simulation Modeling and Analysis with ARENA. Elsevier Science & Technology. A. Tayfur and B. Melamed. 2007. Simulation Modeling and Analysis with ARENA. Elsevier Science & Technology.
  • D. B. Thomas W. Luk P. H. W. Leong and J. D. Villasenor. 2007. Gaussian random number generators. Comput. Surveys 39 4 (2007) 11:01–11:38. D. B. Thomas W. Luk P. H. W. Leong and J. D. Villasenor. 2007. Gaussian random number generators. Comput. Surveys 39 4 (2007) 11:01–11:38.
  • 10.1109/TIFS.2018.2850770
  • Vaskova A., (2011), Proceedings of the IEEE 17th International On-line Testing Symposium. 179–181
  • Vattulainen I., (1995), Phys. Rev. Eng., 52, pp. 3205
  • Voss J., An Introduction to Statistical Computing: A Simulation-Based Approach, 10.1002/9781118728048
  • J. Walker. 2014. ENT—A pseudorandom number sequence test program. Retrieved from https://www.fourmilab.ch/random/. J. Walker. 2014. ENT—A pseudorandom number sequence test program. Retrieved from https://www.fourmilab.ch/random/.
  • 10.1109/TIFS.2019.2947871