Математика и математическое моделирование. 2018; : 35-56
О статистическом тестировании блочных шифров
https://doi.org/10.24108/mathm.0518.0000132Аннотация
Блочные шифры образуют один из основных классов криптографических алгоритмов. Одной из важнейших задач, возникающих в процессе разработки блочных шифров, как и любых других криптографических алгоритмов, является анализ их криптостойкости. В процессе такого анализа часто применяется статистическое тестирование блочных шифров. Обзору литературы, связанной с вопросами статистического тестирования блочных шифров, посвящена настоящая работа.
В первом разделе работы кратко и неформально обсуждаются подходы к определению понятия случайной последовательности, в том числе, подходы Колмогорова, фон Мизеса, Мартин-Лёфа и подход, связанный с непредсказуемостью. Однако все эти подходы к определению случайности оказываются неприменимыми на практике напрямую.
Второй раздел посвящен статистическим тестам двоичных последовательностей. В нем приведены краткие описания тестов, входящих в наборы статистических тестов DieHard, NIST STS, RaBiGeTe.
В третьем разделе приведена необходимая для дальнейшего изложения информация о режимах работы блочных шифров.
Четвертый раздел посвящен методикам статистического тестирования блочных шифров. Обычно такие методики заключаются в том, что на основе тестируемого блочного шифра производится построение тех или иных генераторов псевдослучайных последовательностей, выходные последовательности которых подвергается тестированию с помощью какого-либо набора статистических тестов. Приводятся подходы к построению таких генераторов.
Описана наиболее известная из методик статистического тестирования блочных шифров – методика, использованная NIST для статистического тестирования шифров, поданных на конкурс AES. Кроме того, приводятся другие методики, упоминаемые в литературе.
В заключении делается вывод о том, что существует необходимость разработки новых методик статистического тестирования блочных шифров.
Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 16-07-00542.
Список литературы
1. Vadhan S.P. Pseudorandomness. Boston: Now Publ., 2012. 338 p.
2. Downey R.G., Hirschfeldt D.R. Algorithmic randomness and complexity. N.Y.: Springer, 2010. 855 p.
3. Ming Li, Vitanyi P. An introduction to Kolmogorov complexity and its applications. N.Y.: Springer, 2014. 550 p.
4. Nies A. Computability and randomness. Oxf.; N.Y.: Oxf. Univ. Press, 2009. 433 p.
5. Верещагин Н.К., Успенский В.А., Шень А. Колмогоровская сложность и алгоритмическая случайность. М.: МЦНМО, 2013. 575 p.
6. Колмогоров А.Н. Три подхода к определению понятия «количество информации» // Проблемы передачи информации. 1965. Т. 1. №. 1. С. 3–11.
7. Martin-Löf P. The definition of random sequences // Information and Control. 1966. Vol. 9. No. 6. Pp. 602–619. DOI: 10.1016/S0019-9958(66)80018-9
8. Mises R.v. Grundlagen der Wahrscheinlichkeitsrechnung // Mathematische Zeitschrift. 1919. Vol. 5. No. 1-2. Pp. 52–99. DOI: 10.1007/BF01203155
9. Muchnik A.A., Semenov A.L., Uspensky V.A. Mathematical metaphysics of randomness // Theoretical Computer Science. 1998. Vol. 207. No. 2. Pp. 263–317. DOI: 10.1016/S0304-3975(98)00069-3
10. Кнут Д.Э. Искусство программирования: пер с англ. 3-е изд. Т. 2: Получисленные алгоритмы. М.: Издат. Дом «Вильямс», 2000. 828 с. [Knuth D.E. The art of computer programming. In 3 vol. 3rd ed. Reading: Addison-Wesley Publ. Co., 1997].
11. Marsaglia G. The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness. Режим доступа: http://ftpmirror.your.org/pub/misc/diehard (дата обращения 22.11.2018).
12. Brown R.G., Eddelbuettel D., Bauer D. Dieharder: A random number test suite. Version 3.31.1. Режим доступа: http://webhome.phy.duke.edu/~rgb/General/dieharder.php (дата обращения 22.11.2018).
13. Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Spec. Publ. 2001. 800-22 revision 1a. Режим доступа: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SPS00-22b.pdf (дата обращения 22.11.2018).
14. Bassham L.E., Rukhin A.L., Soto J., Nechvatal J.R., Smid M.E., Leigh S.D., Levenson M., Vangel M., Heckert N.A., Banks D.L. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Spec. Publ. 2010. 800-22 revision 1a. Режим доступа: https://www.nist.gov/publication/statistical-test-suite-random-and-pseudorandom-number-generators-cryptographic (дата обращения 26.11.2018).
15. Soto J. Statistical testing of random number generators // 22nd National information systems security conf.: NISSC’1999 (Arlington, Virginia, USA, October 18-21, 1999): Proc. Vol. 10. 1999. 12 p. Режим доступа: https://csrc.nist.gov/csrc/media/publication/conference-paper/1999/10/21/proceedings-of-the-22nd-nisc-1999-documents/papers/p24.pdf (дата обращения 26.11.2018).
16. L’Ecuyer P., Simard R. TestU01: A C library for empirical testing of random number generators // ACM Trans. on Mathematical Software.2007. Vol. 33. No. 4. Article 22. DOI: 10.1145/1268776.1268777
17. RaBiGeTe MT. Режим доступа: http://cristianopi.altervista.org/RaBiGeTe_MT/ (дата обращения 26.11.2018).
18. PractRand Documentation. Режим доступа: http://pracrand.sourceforge.net/ (дата обращения 26.11.2018).
19. Maurer U.M. A universal statistical test for random bit generators // J. of Cryptology. 1992. Vol. 5. No. 2. Pp. 89–105. DOI: 10.1007/BF00193563
20. Massey J. Shift-register synthesis and BCH decoding // IEEE Trans. on Information Theory. 1969. Vol. 15. No. 1. Pp. 122–127. DOI: 10.1109/TIT.1969.1054260
21. Atti N.B., Diaz–Toca G.M., Lombardi H. The Berlekamp-Massey algorithm revisited // Applicable Algebra in Engineering, Communication and Computing. 2006. Vol. 17. No. 1. Pp. 75–82. DOI: 10.1007/s00200-005-0190-z
22. Good I.J. The serial test for sampling numbers and other tests for randomness // Math. Proc. of the Cambridge Philosophical Soc. 1953. Vol. 49. No. 2. Pp. 276-284. DOI: 10.1017/S030500410002836X
23. Rukhin A.L. Approximate entropy for testing randomness // J. of Applied Probability. 2000. Vol. 37. No. 1. Pp. 88–100. DOI: 10.1239/jap/1014842270
24. Rukhin A.L. Statistical testing of randomness: New and old procedures // Randomness through computation: Some answers, more questions / Ed. by H. Zenil. Ch. 3. Singapore: World Scientific, 2011. Pp. 33–51. DOI: 10.1142/9789814327756_0003
25. Шнайер Б. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си: пер. с англ. М.: Триумф, 2002. 815 с. [Schneier B. Applied cryptography: Protocols, algorithms and source code in C. 2nd ed. N.Y.: Wiley, 1996. 784 p.].
26. ГОСТ Р 34.13-2015. Информационная технология (ИТ). Криптографическая защита информации. Режимы работы блочных шифров. Введ. 2016-01-01. М.: Стандартинформ, 2016.
27. Soto J. Randomness tеsting of the advanced encryption standard candidate algorithms. U.S. Dep. of Commerce. Technology Administration. Nat. Inst. of Standards and Technology. 1999. Режим доступа: https://pdfs.semanticscholar.org/65e1/ccfe7d0e3b68c2bb2acdbc35eb7b046f6430.pdf (дата обращения 26.11.2018).
28. Soto J., Bassham L. Randomness testing of the advanced encryption standard finalist candidates. U.S. Dep. of Commerce. Technology Administration. Nat. Inst. of Standards and Technology. 2000. Режим доступа: https://ws680.nist.gov/publication/get_pdf.cfm?pub_id=151216 (дата обращения 26.11.2018).
29. Murphy S. The power of NIST’s statistical testing of AES candidates. 2000. Режим доступа: http://www.isg.rhbnc.ac.uk/~sean/StatsRev.pdf (дата обращения 26.11.2018).
30. Долгов В.И., Настенко А.А. Большие шифры — случайные подстановки. Проверка статистических свойств шифров, представленных на украинский конкурс с помощью набора тестов NIST STS // Системи обробки iнформацiї. 2012. № 7(105). С. 2–16.
31. Filiol E. A new statistical testing for symmetric ciphers and hash functions // Information and communications security: ICICS 2002: Intern. conf. on information and communications security. B.; Hdbl.: Springer, 2002. Pp. 342 -353. DOI: 10.1007/3-540-36159-6_29
32. Katos V. A randomness test for block ciphers // Applied Mathematics and Computation. 2005. Vol. 162. No. 1. Pp. 29–35. DOI: 10.1016/j.amc.2003.12.122
33. Alani M.M. Testing randomness in ciphertext of block-ciphers using Diehard tests // Intern. J. of Computer Science and Network Security. 2010. Vol. 10. No. 4. Pp. 53–57.
Mathematics and Mathematical Modeling. 2018; : 35-56
On Statistical Testing of Block Ciphers
https://doi.org/10.24108/mathm.0518.0000132Abstract
Block ciphers form one of the main classes of cryptographic algorithms. One of the challenges in development of block ciphers, like any other cryptographic algorithms, is the analysis of their cryptographic security. In the course of such analysis, statistical testing of block ciphers is often used. The paper reviews literature on statistical testing of block ciphers.
The first section of the paper briefly and informally discusses approaches to the definition of the concept of a random sequence, including the Kolmogorov, von Mises, and Martin-Löf approaches and the unpredictability-related approach. However, all these approaches to the definition of randomness are not directly applicable in practice.
The second section describes statistical tests of binary sequences. It provides brief descriptions of the tests included in the DieHard, NIST STS, RaBiGeTe statistical test suites.
The third section provides the appropriate information to present further the operation modes of block ciphers.
The fourth section deals with techniques for statistical testing of block ciphers. Usually such techniques lie in the fact that based on the block cipher under test, various generators of the pseudorandom sequences are built, with their output sequences being tested using any suite of statistical tests. The approaches to the construction of such generators are given.
The paper describes the most known statistical test technique for block ciphers among the submitted for the AES competition. It is a technique the NIST uses for statistical testing of ciphers. In addition, there are other techniques mentioned in the literature.
In conclusion the paper states that there is a need to develop new techniques for statistical testing of block ciphers.
The paper support was provided from the Russian Foundation for Basic Research in the framework of the research project No. 16-07-00542 supported
References
1. Vadhan S.P. Pseudorandomness. Boston: Now Publ., 2012. 338 p.
2. Downey R.G., Hirschfeldt D.R. Algorithmic randomness and complexity. N.Y.: Springer, 2010. 855 p.
3. Ming Li, Vitanyi P. An introduction to Kolmogorov complexity and its applications. N.Y.: Springer, 2014. 550 p.
4. Nies A. Computability and randomness. Oxf.; N.Y.: Oxf. Univ. Press, 2009. 433 p.
5. Vereshchagin N.K., Uspenskii V.A., Shen' A. Kolmogorovskaya slozhnost' i algoritmicheskaya sluchainost'. M.: MTsNMO, 2013. 575 p.
6. Kolmogorov A.N. Tri podkhoda k opredeleniyu ponyatiya «kolichestvo informatsii» // Problemy peredachi informatsii. 1965. T. 1. №. 1. S. 3–11.
7. Martin-Löf P. The definition of random sequences // Information and Control. 1966. Vol. 9. No. 6. Pp. 602–619. DOI: 10.1016/S0019-9958(66)80018-9
8. Mises R.v. Grundlagen der Wahrscheinlichkeitsrechnung // Mathematische Zeitschrift. 1919. Vol. 5. No. 1-2. Pp. 52–99. DOI: 10.1007/BF01203155
9. Muchnik A.A., Semenov A.L., Uspensky V.A. Mathematical metaphysics of randomness // Theoretical Computer Science. 1998. Vol. 207. No. 2. Pp. 263–317. DOI: 10.1016/S0304-3975(98)00069-3
10. Knut D.E. Iskusstvo programmirovaniya: per s angl. 3-e izd. T. 2: Poluchislennye algoritmy. M.: Izdat. Dom «Vil'yams», 2000. 828 s. [Knuth D.E. The art of computer programming. In 3 vol. 3rd ed. Reading: Addison-Wesley Publ. Co., 1997].
11. Marsaglia G. The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness. Rezhim dostupa: http://ftpmirror.your.org/pub/misc/diehard (data obrashcheniya 22.11.2018).
12. Brown R.G., Eddelbuettel D., Bauer D. Dieharder: A random number test suite. Version 3.31.1. Rezhim dostupa: http://webhome.phy.duke.edu/~rgb/General/dieharder.php (data obrashcheniya 22.11.2018).
13. Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Spec. Publ. 2001. 800-22 revision 1a. Rezhim dostupa: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SPS00-22b.pdf (data obrashcheniya 22.11.2018).
14. Bassham L.E., Rukhin A.L., Soto J., Nechvatal J.R., Smid M.E., Leigh S.D., Levenson M., Vangel M., Heckert N.A., Banks D.L. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Spec. Publ. 2010. 800-22 revision 1a. Rezhim dostupa: https://www.nist.gov/publication/statistical-test-suite-random-and-pseudorandom-number-generators-cryptographic (data obrashcheniya 26.11.2018).
15. Soto J. Statistical testing of random number generators // 22nd National information systems security conf.: NISSC’1999 (Arlington, Virginia, USA, October 18-21, 1999): Proc. Vol. 10. 1999. 12 p. Rezhim dostupa: https://csrc.nist.gov/csrc/media/publication/conference-paper/1999/10/21/proceedings-of-the-22nd-nisc-1999-documents/papers/p24.pdf (data obrashcheniya 26.11.2018).
16. L’Ecuyer P., Simard R. TestU01: A C library for empirical testing of random number generators // ACM Trans. on Mathematical Software.2007. Vol. 33. No. 4. Article 22. DOI: 10.1145/1268776.1268777
17. RaBiGeTe MT. Rezhim dostupa: http://cristianopi.altervista.org/RaBiGeTe_MT/ (data obrashcheniya 26.11.2018).
18. PractRand Documentation. Rezhim dostupa: http://pracrand.sourceforge.net/ (data obrashcheniya 26.11.2018).
19. Maurer U.M. A universal statistical test for random bit generators // J. of Cryptology. 1992. Vol. 5. No. 2. Pp. 89–105. DOI: 10.1007/BF00193563
20. Massey J. Shift-register synthesis and BCH decoding // IEEE Trans. on Information Theory. 1969. Vol. 15. No. 1. Pp. 122–127. DOI: 10.1109/TIT.1969.1054260
21. Atti N.B., Diaz–Toca G.M., Lombardi H. The Berlekamp-Massey algorithm revisited // Applicable Algebra in Engineering, Communication and Computing. 2006. Vol. 17. No. 1. Pp. 75–82. DOI: 10.1007/s00200-005-0190-z
22. Good I.J. The serial test for sampling numbers and other tests for randomness // Math. Proc. of the Cambridge Philosophical Soc. 1953. Vol. 49. No. 2. Pp. 276-284. DOI: 10.1017/S030500410002836X
23. Rukhin A.L. Approximate entropy for testing randomness // J. of Applied Probability. 2000. Vol. 37. No. 1. Pp. 88–100. DOI: 10.1239/jap/1014842270
24. Rukhin A.L. Statistical testing of randomness: New and old procedures // Randomness through computation: Some answers, more questions / Ed. by H. Zenil. Ch. 3. Singapore: World Scientific, 2011. Pp. 33–51. DOI: 10.1142/9789814327756_0003
25. Shnaier B. Prikladnaya kriptografiya: Protokoly, algoritmy, iskhodnye teksty na yazyke Si: per. s angl. M.: Triumf, 2002. 815 s. [Schneier B. Applied cryptography: Protocols, algorithms and source code in C. 2nd ed. N.Y.: Wiley, 1996. 784 p.].
26. GOST R 34.13-2015. Informatsionnaya tekhnologiya (IT). Kriptograficheskaya zashchita informatsii. Rezhimy raboty blochnykh shifrov. Vved. 2016-01-01. M.: Standartinform, 2016.
27. Soto J. Randomness testing of the advanced encryption standard candidate algorithms. U.S. Dep. of Commerce. Technology Administration. Nat. Inst. of Standards and Technology. 1999. Rezhim dostupa: https://pdfs.semanticscholar.org/65e1/ccfe7d0e3b68c2bb2acdbc35eb7b046f6430.pdf (data obrashcheniya 26.11.2018).
28. Soto J., Bassham L. Randomness testing of the advanced encryption standard finalist candidates. U.S. Dep. of Commerce. Technology Administration. Nat. Inst. of Standards and Technology. 2000. Rezhim dostupa: https://ws680.nist.gov/publication/get_pdf.cfm?pub_id=151216 (data obrashcheniya 26.11.2018).
29. Murphy S. The power of NIST’s statistical testing of AES candidates. 2000. Rezhim dostupa: http://www.isg.rhbnc.ac.uk/~sean/StatsRev.pdf (data obrashcheniya 26.11.2018).
30. Dolgov V.I., Nastenko A.A. Bol'shie shifry — sluchainye podstanovki. Proverka statisticheskikh svoistv shifrov, predstavlennykh na ukrainskii konkurs s pomoshch'yu nabora testov NIST STS // Sistemi obrobki informatsiї. 2012. № 7(105). S. 2–16.
31. Filiol E. A new statistical testing for symmetric ciphers and hash functions // Information and communications security: ICICS 2002: Intern. conf. on information and communications security. B.; Hdbl.: Springer, 2002. Pp. 342 -353. DOI: 10.1007/3-540-36159-6_29
32. Katos V. A randomness test for block ciphers // Applied Mathematics and Computation. 2005. Vol. 162. No. 1. Pp. 29–35. DOI: 10.1016/j.amc.2003.12.122
33. Alani M.M. Testing randomness in ciphertext of block-ciphers using Diehard tests // Intern. J. of Computer Science and Network Security. 2010. Vol. 10. No. 4. Pp. 53–57.
