Preview

Математика и математическое моделирование

Расширенный поиск

О статистическом тестировании блочных шифров

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.


Для цитирования:


Ключарёв П.Г. О статистическом тестировании блочных шифров. Математика и математическое моделирование. 2018;(5):35-56. https://doi.org/10.24108/mathm.0518.0000132

For citation:


Klyucharev P.G. On Statistical Testing of Block Ciphers. Mathematics and Mathematical Modeling. 2018;(5):35-56. (In Russ.) https://doi.org/10.24108/mathm.0518.0000132

Просмотров: 99


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)