sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-394Research ArticleСтатьиАнализ эффективности градиентной статистической атаки на блоковые шифры RC6, MARS, CAST-128, IDEA, Blowfish в системах защиты информацииEfficiency analysis of gradient statistical attack on block ciphers RC6, MARS, CAST-128, IDEA, BlowfishЛысякА. С.LysyakA. S.accemt@gmail.comРябкоБ. Я.RyabkoB. Ya.boris@ryabko.netФионовА. Н.FionovA. N.fionov@sibsutis.ruСибГУТИ; НГУRussian FederationСибГУТИRussian Federation2013261020220185109Copyright © Лысяк А.С., Рябко Б.Я., Фионов А.Н., 20222022Лысяк А.С., Рябко Б.Я., Фионов А.Н.Lysyak A.S., Ryabko B.Y., Fionov A.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/394

Данная работа посвящена экспериментальному исследованию статистических методов в криптоанализе на примере блоковых шифров RC6, MARS, CAST-128, IDEA и Blowfish. Предложенная градиентная атака основана на статистическом тесте «стопка книг». Описанные схемы и модификации атаки позволяют значительно уменьшить трудоёмкость нахождения секретного ключа по сравнению с ранее известными видами атак. В данной работе проведены исследования эффективности градиентной статистической атаки, показаны пределы её современной практической и теоретической применимости (9 раундов шифра RC6, 21 раунд MARS и 4 раунда CAST-128), выведены аналитические зависимости между эффективно атакуемыми раундами и временно́й и аппаратной сложностью атаки. Кроме того, для шифров RC6 и MARS разработаны модификации градиентной атаки, значительно сокращающие временну́ю и операционную сложность. Также в данной работе показан метод подбора оптимальных параметров атаки; исследована операционная и пространственная трудоёмкости и их зависимости от параметров теста и объёма шифротекста; показаны теоретические потребности в вычислительных ресурсах, необходимых для осуществления атаки.

This paper is devoted to the pilot study of statistical techniques in cryptanalysis on the basis of block ciphers RC6, MARS, CAST-128, IDEA and Blowfish. The suggested gradient attack is based on statistical test attack called the «book stack». The described scheme and modifed attacks can significantly reduce the complexity of finding the secret key in comparison with previously known types of attacks. This paper studies the effectiveness of gradient statistical attack demonstrating its modern practical and theoretical application (9 rounds of RC6, 21 rounds of MARS and 4 rounds of CAST-128). Analytical dependence between effectively attacked rounds and time/hardware complexity is derived. In addition, in the case of RC6 and MARS, modifications significantly reducing space and operational complexity were developed. Also, this paper shows a selection method of optimum parameters of attack; operational and space complexity were investigated and their dependence on parameters and ciphertext size were shown. Theoretical demand for computing power needed to carry out the attack is described.

градиентная атакастатистическая атакакриптоанализблоковые шифрыRC6MARSCAST-128IDEABlowfishgradient attackstatistical attackcryptoanalysisblock ciphersRC6MARSCAST-128IDEABlowfishReferencesKnudsen L., Meier W. Correlations in RC6 with a reduced number of rounds // FSE 2000. LNCS 1978(2000). Springer–Verlag. P. 94–108.Knudsen L., Meier W. Correlations in RC6 with a reduced number of rounds // FSE 2000. LNCS 1978(2000). Springer–Verlag. P. 94–108.Меняшев А.А., Монарев В.А., Рябко Б.Я., Фионов А.Н. Применение градиентной статистической атаки к блоковым шифрам RC5, RC6 И SAFER // Научно-практический журнал «Информационное противодействие терроризму», 2006. №7. С. 189-193.Меняшев А.А., Монарев В.А., Рябко Б.Я., Фионов А.Н. Применение градиентной статистической атаки к блоковым шифрам RC5, RC6 И SAFER // Научно-практический журнал «Информационное противодействие терроризму», 2006. №7. С. 189-193.Монарёв В.А., Лубкин А.М. Эффективная атака на блоковый шифр RC6 // Вестник СибГУТИ, 2010. №4. С. 55-60.Монарёв В.А., Лубкин А.М. Эффективная атака на блоковый шифр RC6 // Вестник СибГУТИ, 2010. №4. С. 55-60.Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации, 2006, Москва. С. 181-202.Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации, 2006, Москва. С. 181-202.Pябко Б.Я., Монарев В.А., Шокин Ю.И. Новый тип атак на блоковые шифры // Проблемы передачи информации, 2005. т. 41. н.4. С. 181– 128.Pябко Б.Я., Монарев В.А., Шокин Ю.И. Новый тип атак на блоковые шифры // Проблемы передачи информации, 2005. т. 41. н.4. С. 181– 128.Шнайер Б. Прикладная криптография// NewYork:Wiley, 1996. P. 124-147.Шнайер Б. Прикладная криптография// NewYork:Wiley, 1996. P. 124-147.Ryabko B.Ya., Monarev V.A. Using information theory approach to randomness testing // Journal of Statistical Planning and Inference, 2005. Vol. 133. № 1. PP. 95-110.Ryabko B.Ya., Monarev V.A. Using information theory approach to randomness testing // Journal of Statistical Planning and Inference, 2005. Vol. 133. № 1. PP. 95-110.Рябко Б.Я., Пестунов А.И. «Стопка книг» как новый статистический тест для случайных чисел // Пробл. передачи информации, 2004. Т. 40. вып. 1. C. 73-78.Рябко Б.Я., Пестунов А.И. «Стопка книг» как новый статистический тест для случайных чисел // Пробл. передачи информации, 2004. Т. 40. вып. 1. C. 73-78.L'Ecuyer P. Tables of linear congruential generators of different sizes and good lattice structure // Math. of Comp, 1999. Vol. 68. P. 249-260.L'Ecuyer P. Tables of linear congruential generators of different sizes and good lattice structure // Math. of Comp, 1999. Vol. 68. P. 249-260.Кнут Д.Э. Искусство программирования. Т. 2: Получисленные алгоритмы. М.: Изд. дом «Вильямс», 2000.С. 60-148.Кнут Д.Э. Искусство программирования. Т. 2: Получисленные алгоритмы. М.: Изд. дом «Вильямс», 2000.С. 60-148.Pestunov A. Statistical Analysis of the MARS Block Cipher // Cryptology ePrint Archive. Report 2006/217 [Электронный ресурс]. URL:http://eprint.iacr.org/2006/217 (дата обращения: 18.06.2011).Pestunov A. Statistical Analysis of the MARS Block Cipher // Cryptology ePrint Archive. Report 2006/217 [Электронный ресурс]. URL:http://eprint.iacr.org/2006/217 (дата обращения: 18.06.2011).Ryabko B., Monarev V. Using information theory approach for randomness testing // J. of Statistical Planning and Reference. 2005. Vol. 133, N 1. P. 95-110.Ryabko B., Monarev V. Using information theory approach for randomness testing // J. of Statistical Planning and Reference. 2005. Vol. 133, N 1. P. 95-110.Doroshenko S., Ryabko B. The experimental distinguishing attack on RC4 // Cryptology ePrint Archive. Report 2006/070. 2006. [Электронный ресурс]. URL:http://eprint.iacr.org/ 2006/070 (дата обращения: 21.10.2011).Doroshenko S., Ryabko B. The experimental distinguishing attack on RC4 // Cryptology ePrint Archive. Report 2006/070. 2006. [Электронный ресурс]. URL:http://eprint.iacr.org/ 2006/070 (дата обращения: 21.10.2011).Пестунов А.И. Теоретическое исследование свойств статистического теста «стопка книг». Вычислительные технологии 2006, Т.11, №6. C. 96-102.Пестунов А.И. Теоретическое исследование свойств статистического теста «стопка книг». Вычислительные технологии 2006, Т.11, №6. C. 96-102.Пестунов А.И. Дифференциальный криптоанализ блочного шифра MARS // Прикладная дискретная математика 2009. №6. C. 56-63.Пестунов А.И. Дифференциальный криптоанализ блочного шифра MARS // Прикладная дискретная математика 2009. №6. C. 56-63.Biham E., Dunkelman O., Keller N. A New Attack on 6-Round IDEA // Lecture Notes in Computer Science. Berlin, Heidelberg: Springer-Verlag, 2007. V. 4593. P. 211-224.Biham E., Dunkelman O., Keller N. A New Attack on 6-Round IDEA // Lecture Notes in Computer Science. Berlin, Heidelberg: Springer-Verlag, 2007. V. 4593. P. 211-224.Schneier Bruce. The Blowfish Encryption Algorithm -- One Year Later // Dr. Dobb's Journal, 1995. P. 101-137.Schneier Bruce. The Blowfish Encryption Algorithm -- One Year Later // Dr. Dobb's Journal, 1995. P. 101-137.Meier W., Brugg-Windisch HTL., Switzerland. Workshop on the theory and application of cryptographic techniques on Advances in Сryptology EUROCRYPT '93 Proceedings. Secaucus, NJ, USA: Springer-Verlag New York, Inc, 1994. P. 371-385.Meier W., Brugg-Windisch HTL., Switzerland. Workshop on the theory and application of cryptographic techniques on Advances in Сryptology EUROCRYPT '93 Proceedings. Secaucus, NJ, USA: Springer-Verlag New York, Inc, 1994. P. 371-385.Rivest R.L., Robshaw M.J.B., Sidney R., and Yin Y.L. The RC6 BlockCipher, 1998. P. 42-57.Rivest R.L., Robshaw M.J.B., Sidney R., and Yin Y.L. The RC6 BlockCipher, 1998. P. 42-57.Carolynn Burwick Don Coppersmith. The MARS Encryption Algorithm. [Электронный ресурс]. URL: http://csis.bits-pilani.ac.in (дата обращения: 24.05.2011).Carolynn Burwick Don Coppersmith. The MARS Encryption Algorithm. [Электронный ресурс]. URL: http://csis.bits-pilani.ac.in (дата обращения: 24.05.2011).Schneier Bruce. Applied Cryptography, (2nd edition). John Wiley & Sons. 1996. PP. 334–335.Schneier Bruce. Applied Cryptography, (2nd edition). John Wiley & Sons. 1996. PP. 334–335.Demirci Hüseyin, Türe Erkan, Selçuk Ali Aydin. A New Meet in the Middle Attack on The IDEA Block Cipher, 10th Annual Workshop on Selected Areas in Cryptography, 2004.Demirci Hüseyin, Türe Erkan, Selçuk Ali Aydin. A New Meet in the Middle Attack on The IDEA Block Cipher, 10th Annual Workshop on Selected Areas in Cryptography, 2004.

The authors declare that there are no conflicts of interest present.