×

New statistical randomness tests: 4-bit template matching tests. (English) Zbl 1424.62020

Summary: For cryptographic algorithms, secret keys should be generated randomly as the security of the system depends on the key and therefore generation of random sequences is vital. Randomness testing is done by means of statistical randomness tests. In this work, we show that the probabilities for the overlapping template matching test in the NIST test suite are only valid for a specific template and need to be recalculated for the other templates. We calculate the exact distribution for all 4-bit templates and propose new randomness tests, namely template matching tests. The new tests can be applied to any sequence of minimum length 5504 whereas the overlapping template matching test in the NIST test suite can only be applied to sequences of minimum length \(10^6\). Moreover, we apply the proposed tests to biased nonrandom data and observe that the new tests detect the nonrandom behavior of the generator even for a bias of 0.001, whereas the template matching tests in NIST cannot detect that bias.

MSC:

62F03 Parametric hypothesis testing
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alcover PM, Guillam´on A, Ruiz MC. New randomness test for bit sequences. Informatica 2013; 24: 339-356. · Zbl 1360.94292
[2] Charalambides AC. Enumerative Combinatorics. London, UK: CRC Press, 2002.
[3] Daeman J, Rijmen V. The Design of Rijndael:AES - The Advanced Encryption Standard. Berlin, Germany:Springer-Verlag, 2002. · doi:10.1007/978-3-662-04722-4
[4] Do˘ganaksoy A, C¸ alık C¸ , Sulak F, Turan MS. New randomness tests using random walk. In: 2nd National Conference Proceedings; 15-17 December 2006; Ankara, Turkey.
[5] Do˘ganaksoy A, Golo˘glu F. On Lempel-Ziv complexity of sequences. In: Guang G, editor. Sequences and Their Applications - SETA 2006 4th International Conference Proceedings; 24-28 September 2006; Beijing, China. Berlin, Germany: Springer-Verlag, 2006, pp. 180-189. · Zbl 1152.94378 · doi:10.1007/11863854_15
[6] Do˘ganaksoy A, Sulak F, U˘guz M, S¸eker O, Akcengiz Z. New statistical randomness tests based on length of runs. Mathematical Problems in Engineering 2015; 2015: 626408. · Zbl 1395.94280
[7] Do˘ganaksoy A, Tezcan C. An alternative approach to Maurer’s universal statistical test. In: Information Security and Cryptology Conference ISC Turkey 2006 3rd International Conference Proceedings; 25-27 December 2008; Ankara, Turkey. pp. 187-189.
[8] Goldberg I, Wagner D. Randomness and the Netscape browser. Dr Dobb’s Journal-Software Tools for the Professional Programmer 1996; 21: 66-70.
[9] Hamano K, Kaneko T. Correction of overlapping template matching test included in NIST randomness test suite. IEICE T Fund Electr 2007; 90: 1788-1792.
[10] Hamano K, Sato F, Yamamoto H. A new randomness test based on linear complexity profile. IEICE T Fund Electr 2009; 92: 166-172.
[11] Hamano K, Yamamoto H. A randomness test based on t-codes. In: International Symposium on Information Theory and Its Applications - ISITA 2008; 7-10 December 2008; Auckland, New Zealand. New York, NY, USA: IEEE, 2008, pp. 1-6. · doi:10.1109/ISITA.2008.4895570
[12] Hamano K, Yamamoto H. A randomness test based on t-complexity. IEICE T Fund Electr 2010; 93: 1346-1354.
[13] Katos V. A randomness test for block ciphers. Appl Math Comput 2005; 162: 29-35. · Zbl 1060.94021
[14] Knuth DE. The Art of Computer Programming, Volume 2. Seminumerical Algorithms. 3rd ed. Boston, MA, USA: Addison-Wesley Longman Publishing, 1997. · Zbl 0895.68055
[15] L’Ecuyer P, Simard R. Testu01: A C library for empirical testing of random number generators. ACM T Math Software 2007; 33: 22. · Zbl 1365.65008 · doi:10.1145/1268776.1268777
[16] Matsumoto M, Nishimura T. Mersenne Twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM T Model Comput S 1998; 8: 3-30. · Zbl 0917.65005 · doi:10.1145/272991.272995
[17] Maurer U. A universal statistical test for random bit generators. J Cryptol 1992; 5: 89-105. · Zbl 0790.94014 · doi:10.1007/BF00193563
[18] Menezes AJ, Vanstone SA, Van Oorschot PC. Handbook of Applied Cryptography. Boca Raton, FL, USA: CRC Press, 1996. · Zbl 0868.94001 · doi:10.1201/9781439821916
[19] Okutomi H, Kaneda M, Yamaguchi K, Nakamuro K. A study on the randomness evaluation method using NIST randomness test. In: Symposium on Cryptography and Information Security - International Conference Proceedings; 2006.
[20] Ruhkin A. Testing randomness: a suite of statistical procedures. Theor Probab Appl+ 2001; 45: 111-132. · Zbl 1171.62329 · doi:10.1137/S0040585X97978087
[21] Rukhin AL, Soto J, Nechvatal J, Smid M, Barker E, Leigh S, Levenson M, Vangel M, Banks D, Heckert A et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications Sp 800-22 Rev. 1a. Gaithersburg, MD, USA: Booz-Allen and Hamilton, 2010. · doi:10.6028/NIST.SP.800-22r1a
[22] Soto J, Bassham L. Randomness Testing of the Advanced Encryption Standard Finalist Candidates. Gaithersburg, MD, USA: Booz-Allen and Hamilton, 1999.
[23] Sulak F. A new statistical randomness test: saturation point test. International Journal of Information Security Science 2013; 2: 81-85.
[24] Sulak F, Do˘ganaksoy A, Ege B, Ko¸cak O. Evaluation of randomness test results for short sequences. In: Carlet C, Pott A, editors. Sequences and Their Applications - SETA10 6th International Conference Proceedings; 13-17 September 2010; Paris, France. Berlin, Germany: Springer-Verlag, 2010, pp. 309-319. · Zbl 1257.62128 · doi:10.1007/978-3-642-15874-2_27
[25] Takeda Y, Huzii M, Kamakura T, Watanabe N, Sugiyama T. The Problem of Template Matching Test in the Testing Randomness by NIST. IEICE Technical Report. Tokyo, Japan: IEICE, 2005.
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.