Paper 2022/169

SP 800-22 and GM/T 0005-2012 Tests: Clearly Obsolete, Possibly Harmful

Markku-Juhani O. Saarinen

Abstract

When it comes to cryptographic random number generation, poor understanding of the security requirements and ``mythical aura'' of black-box statistical testing frequently leads it to be used as a substitute for cryptanalysis. To make things worse, a seemingly standard document, NIST SP 800-22, describes 15 statistical tests and suggests that they can be used to evaluate random and pseudorandom number generators in cryptographic applications. The Chinese standard GM/T 0005-2012 describes similar tests. These documents have not aged well. The weakest pseudorandom number generators will easily pass these tests, promoting false confidence in insecure systems. We strongly suggest that SP 800-22 be withdrawn by NIST; we consider it to be not just irrelevant but actively harmful. We illustrate this by discussing the ``reference generators'' contained in the SP 800-22 document itself. None of these generators are suitable for modern cryptography, yet they pass the tests. For future development, we suggest focusing on stochastic modeling of entropy sources instead of model-free statistical tests. Random bit generators should also be reviewed for potential asymmetric backdoors via trapdoor one-way functions, and for security against quantum computing attacks.

Note: Update History: 2022-Apr-12: Accepted to SSR 2022, updated. ( https://ssr2022.com/ ) 2022-Mar-05: Expanded with additional commentary. 2022-Feb-15: Written as a Comment on "SP 800-22 Rev. 1a Decision Proposal." ( https://csrc.nist.gov/News/2022/proposal-to-revise-sp-800-22-rev-1a )