Reading a text without its key: naming the cipher, peeling off encodings, counting letters, breaking nomenclators, replaying the Enigma breaks of the 1930s and 1940s, checking anagrams.
Randomness Tests
Runs NIST SP 800-22’s fifteen statistical tests (2010) on pasted bits, hex or text, a file, the binary digits of e, π, √2 and √3, or a generator, each giving a P-value against chance; and FIPS 140-1’s four power-up tests (1994) on 20,000 bits. All 64 of Appendix B’s values for the constants are reproduced, with NIST’s program’s constants where they differ from the standard’s.
Terms
About this tool
History
NIST’s Special Publication 800-22, the Statistical Test Suite, gathers fifteen tests of whether a sequence of bits could have come from a fair coin; its revision 1a appeared in April 2010, and NIST’s reference program, sts, was last revised as version 2.1.2 in July 2014. Earlier, FIPS 140-1 (1994) set four quick tests that a cryptographic module’s generator had to pass at power-up. FIPS 140-2 (2001) narrowed their bounds, and its Change Notice 2 of December 2002 struck them out.
How it works
Each test reduces the sequence to one statistic — a count of ones, runs or patterns, the peaks of its spectrum, the rank of bit matrices, the shift register that makes each block — and compares it with its law for a random sequence; the P-value is the chance of a result at least as far off. Below α the test calls the sequence non-random, as it wrongly calls a random one once in a hundred at α = 0.01. Serial and approximate entropy take the longest patterns the standard allows the length, 16 and 10 bits at a million. Up to 1,000,000 bits are tested; the digits of e, π, √2 and √3 are computed on the device, e by summing 1/k! in halves, π by the Chudnovskys’ series, the roots by Newton’s method.
How it was checked
The four constants begin as NIST’s sample files do, and all 64 of Appendix B’s P-values for them are reproduced within a millionth. Two need the constants of NIST’s program rather than the standard’s: its overlapping-template probabilities overwrite the correction the standard prints, and its linear-complexity table has 0.01047 for 0.010417; both P-values are shown. The worked examples of Section 2 recompute, ten only once a misprinted figure is mended — the spectral test’s 2.6.4 and 2.6.8 have 5 and 48 peaks under the threshold, not 4 and 46 — and 2.8.8 and 2.10.8 print the program’s P-value; the incomplete gamma function meets Appendix E’s values.
Limits
Passing proves nothing: a sequence can pass every test and still be predictable, as any good pseudo-random generator is to whoever knows its seed. Failing one test once is expected of a random sequence; NIST judges a generator by the share of many sequences that pass and by how evenly their P-values spread, which takes many runs and is not built here. NIST’s fifth sample, from its G-SHA-1 generator, could not be regenerated and is left out.
- A. Rukhin et al., rev. L. Bassham et al., NIST Special Publication 800-22 Rev. 1a, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications” (April 2010)
- NIST, sts-2.1.2, the reference program of SP 800-22 (9 July 2014), and its release notes
- FIPS PUB 140-1, “Security Requirements for Cryptographic Modules” (11 January 1994), §4.11.1
- FIPS PUB 140-2 (25 May 2001), §4.9.1, with Change Notices 1 (10 October 2001) and 2 (3 December 2002)
- IBM, System/360 Scientific Subroutine Package, Version III (360A-CM-03X), subroutine RANDU, as kept on a DECUS tape of the package (1973)