Upgrading Frequency Test for Overlapping Vectors and Fill Tree Tests

• Autorzy: Mańk Krzysztof

Identyfikatory

DOI

10.24425/ijet.2025.153591

• Języki publikacji: EN

Abstrakty

EN

Randomness testing is one of the essential and easiest tools for evaluating cryptographic primitives. The faster we can test with more refined tests, the greater volume of datathat can be reliably tested. This paper we analyze three tests. Starting with a range of observations made for a well-known frequency test for overlapping vectors in binary sequence testing, for which we have obtained precise chi-square statistic computed in O dt2dt instead of O 22dt time, without precomputed tables. Next we focused on two tests from Dieharder: the DAB Fill Tree Test and the DAB Fill Tree 2 Test — for which the probability functions originally were determined empirically. We also draw attention to the errors found in their implementations and the insufficient exploration of the tested sequence in the second test. Even though these tests have been in the package for over 10 years, their significant shortcomings have not been noticed until now.

Słowa kluczowe

EN

randomness testing; overlapping vectors testing; NIST STS; Dieharder

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 2
• Strony: 451--459
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Mańk Krzysztof

• Military University of Technology, Poland

Bibliografia

• [1] R. G. Brown, “Dieharder: A random number test suite.” [Online]. Available: https://webhome.phy.duke.edu/∼rgb/General/dieharder.php
• [2] G. Marsaglia, “The marsaglia random number cdrom including the diehard battery of tests of randomness,” 1995. [Online]. Available: web.archive.org/web/20160125103112/http://stat.fsu.edu/pub/diehard/
• [3] I. Good, “The serial test for sampling numbers and other tests for randomness,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 49, pp. 276-284, 1953. [Online]. Available: https://doi.org/10.1017/S030500410002836X
• [4] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A statistical test suite for random and pseudorandom number generators for cryptographic applications,” NIST Special Publication SP 800-22 Revision 1a, 2010. [Online]. Available: https://doi.org/10.6028/NIST.SP.800-22r1a
• [5] A. Alhakim, J. Kawczak, and S. Molchanov, “On the class of nilpotent markov chains, i. the spectrum of covariance operator,” Markov Processes and Related Fields, vol. 4, pp. 629-652, 01 2004.
• [6] A. Alhakim, “On the eigenvalues and eigenvectors of an overlapping markov chain,” Probability Theory and Related Fields, vol. 128, pp. 589-605, 04 2004. [Online]. Available: https://doi.org/10.1007/s00440-003-0321-z
• [7] P. Billingsley, Probability and Measure” (3rd ed.). John Wiley & Sons, 1995. [Online]. Available: www.colorado.edu/amath/sites/default/files/attached-files/billingsley.pdf
• [8] K. Mańk, “Test czestości dla nakładajacych sie wektorów (in polish: Frequency test for overlapping vectors),” Cyberprzestepczość i ochrona informacji - Bezpieczeństwo w internecie tom II, Wydawnictwo Wyższej Szkoły Menedżerskiej w Warszawie, 2013.
• [9] P. L’Ecuyer and R. Simard, “Testu01: A c library for empirical testing of random number generators,” ACM Trans. Math. Softw., vol. 33, pp. 1-40, 01 2007. [Online]. Available: https://doi.org/10.1145/1268776.1268777
• [10] G. P. E. and M. S. Nikulin, A guide to chi-squared testing. Wiley, 1996.

Uwagi

1. Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).

2. This work was supported by the grant No. DOB/002/RON/ID1/2018 by The National Centre for Research and Development.