2. Home
  3. ARCHIVE
  4. 2024
  5. VOL 46, NO 3 (2024)
  6. pp. 22-38

STATISTICAL TESTS FOR CHECKING INDEPENDENCE OF RANDOM VARIABLES, WHICH DESCRIBE SEQUENCES GENERATION IN CRYPTOALGORITHMS

L.V. Kovalchuk, I.V. Koriakov, O.Yu. Bespalov

Èlektron. model. 2024, 46(3):22-38

https://doi.org/10.15407/emodel.46.03.022

ABSTRACT

When a crypto-primitive, whose functions include the generation of a random/pseudo-random gamma, is admitted to operation, a necessary part of its quality checking is a statistical testing of its output gamma and, often, intermediate gamma(s). Such requirement is applied, for example, to random/pseudo-random number generators (RNG/PRNG), stream ciphers, and block ciphers in different "stream" modes (such as OFB, CBC, etc). There exist widely used and well-known tools for checking the statistical properties of sequences and generators, which are based on a set of statistical tests, like NIST STS set, Diehard, etc.

At the same time, the other and very similar question, about independence of the sequences (more precisely — independence of the corresponding random variables, that the considered sequences are their realizations) generated in such cryptoalgorithms, usually doesn’t attract enough attention. Nevertheless, it is also of great importance, because the dependence of the sequences can lead to predictability of the output gamma, which makes the cryptoprimitive vulnerable to statistical attacks. Therefore, there are no adequate and suitable tools for checking independence of different sequences, generated in the algorithms. In this work we deve­loped and justified new set of three statistical tests for checking independence of random va­riables, which realizations are internal or output sequences in encryption algorithms or RNG/PRNG. We also calculated reference values for limit statistics for different parameters of sequences and different significance levels of tests. Results of tests applications for independent and dependent random variables are given, which confirm correctness of proposed tests.

KEYWORDS

Statistical tests, random (pseudorandom) number generator, stream ciphers, independent random variables (sequences).

REFERENCES

  1. International Organization for Standardization. (2017). Information technology — Security techniques — Modes of operation for an n-bit block cipher (reviewed and confirmed in 2023) — ISO/IEC Standard No. 10116:2017.
  2. Bassham L., Rukhin A., Soto J., Nechvatal J., Smid M., Leigh S., Levenson M., Vangel M., Heckert N. and Banks D. (2010), A statistical test suite for random and pseudorandom number generators for cryptographic applications, Special Publication (NIST SP), National Institute of Standards and Technology, Gaithersburg, MD,
    https://doi.org/10.6028/NIST.SP.800-22r1a
  3. Marsaglia G. The Marsaglia random number CDROM. URL: https://github.com/jeff Thompson/DiehardCDROM (date of access: 27.04.2024).
  4. Robert G. B. DieHarder: a gnu public license random number tester, v. 3.31.2beta URL: https://rurban.github.io/dieharder/manual/dieharder.pdf (date of access: 27.04.2024).
  5. Luengo E.A., Villalba L.J.G. 2021. Recommendations on statistical randomness test batteries for cryptographic purposes. ACM Computing Surveys. Vol. 54, no. 4 , P. 1-34.
    https://doi.org/10.1145/3447773
  6. Kovalchuk L.V., Koriakov I.V., Alekseychuk A.N. Krip: high-speed hardware-oriented stream cipher based on a non-autonomous nonlinear shift register. 2023. Cybernetics and System Analysis 59, P. 16-26. URL: https://doi.org/10.1007/s10559-023-00538-6 (date of access: 27.04.2024).
  7. Anderson, T.W. (1958). An introduction to multivariate statistical analysis. John Wiley & Sons, New York.
  8. ДСТУ 9041:2020 Інформаційні технології. Криптографічний захист інформації. Алгоритм шифрування коротких повідомлень, що ґрунтується на скручених еліп­тичних кривих Едвардса. Чинний від 2020-11-01. Київ: УкрНДНЦ, 2020. IV, 36 с.
  9. Maurer U.M. A universal statistical test for random bit generators. 1992. Journal of Cryptology 5. P. 89-105.
    https://doi.org/10.1007/BF00193563
  10. Khintchine A. Über einen Satz der Wahrscheinlichkeitsrechnung.1924. Fundamenta Mathematicae. 6. Iss. 1. P. 9-20.
    https://doi.org/10.4064/fm-6-1-9-20
  11. Kolmogoroff A. Über das Gesetz des iterierten Logarithmus. 1929. Mathematische Annalen.101. P. 126-135.
    https://doi.org/10.1007/BF01454828
  12. Feller, W. (1968). An introduction to probability theory and its applications, 1. Wiley. URL: https://www.academia.edu/31507704/An_Introduction_to_probability_ Theory_ by_William_Feller (date of access: 27.04.2024).
  13. Kochana R., Kovalchuk L., Korchenko O., Kuchynska N. Statistical Tests Independence Verification Methods. 2021. Procedia Computer Science. Vol. 192. P. 2678-2688.
    https://doi.org/10.1016/j.procs.2021.09.038

Full text: PDF