On Stochastic Security of Pseudorandom Sequences

Abstract. Cryptographic primitives such as secure hash functions (e.g., SHA1, SHA2, and SHA3) and symmetric key block ciphers (e.g., AES and TDES) have been commonly used to design pseudorandom generators with counter modes (e.g., in NIST SP800-90A standards). It is assumed that if these primitives are secure then the sequences generated by pseudorandom generators based on these primitives are indistinguishable from sequences from true random sources. How-ever, no systematic research and analysis have been done to support this assump-tion. Based on complexity theoretic results for pseudorandom sequences, this pa-per analyzes stochastic properties of long sequences produced by pseudorandom generators DRBG-SHA from NIST SP800-90A. A collection of 6TB random se-quences are generated and it is observed that the statistical distance between the collection of generated sequences and uniform distribution is around 0.07 (with 0 for statistically indistinguishable and 1 for completely distinguishable). We then try to see whether other seeding approaches to pseudorandom generators could be used to reduce the statistical distance. For example, we carried out experiment with dynamic seeding approach. The experimental results show that the collec-tion of sequences generated by the revised seeding approach is also at least 0.07 statistically away from the collection of uniform chosen sequences. Though the statistical distance 0.07 is acceptable in practice for most applications, the pre-ferred distance of a cryptographic “random oracle ” from a true random source should be smaller than 0.03 with the sample size of 1000 sequences (2TB bits).