Efficiency analysis of gradient statistical attack on block ciphers RC6, MARS, CAST-128, IDEA, Blowfish

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.

RC6, MARS, CAST-128, IDEA, Blowfish, gradient attack, statistical attack, cryptoanalysis, block ciphers, RC6, MARS, CAST-128, IDEA, Blowfish

1. Knudsen L., Meier W. Correlations in RC6 with a reduced number of rounds // FSE 2000. LNCS 1978(2000). Springer–Verlag. P. 94–108.

2. Меняшев А.А., Монарев В.А., Рябко Б.Я., Фионов А.Н. Применение градиентной статистической атаки к блоковым шифрам RC5, RC6 И SAFER // Научно-практический журнал «Информационное противодействие терроризму», 2006. №7. С. 189-193.

3. Монарёв В.А., Лубкин А.М. Эффективная атака на блоковый шифр RC6 // Вестник СибГУТИ, 2010. №4. С. 55-60.

4. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации, 2006, Москва. С. 181-202.

5. Pябко Б.Я., Монарев В.А., Шокин Ю.И. Новый тип атак на блоковые шифры // Проблемы передачи информации, 2005. т. 41. н.4. С. 181– 128.

6. Шнайер Б. Прикладная криптография// NewYork:Wiley, 1996. P. 124-147.

7. 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.

8. Рябко Б.Я., Пестунов А.И. «Стопка книг» как новый статистический тест для случайных чисел // Пробл. передачи информации, 2004. Т. 40. вып. 1. C. 73-78.

9. L'Ecuyer P. Tables of linear congruential generators of different sizes and good lattice structure // Math. of Comp, 1999. Vol. 68. P. 249-260.

10. Кнут Д.Э. Искусство программирования. Т. 2: Получисленные алгоритмы. М.: Изд. дом «Вильямс», 2000.С. 60-148.

11. 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).

12. 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.

13. 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).

14. Пестунов А.И. Теоретическое исследование свойств статистического теста «стопка книг». Вычислительные технологии 2006, Т.11, №6. C. 96-102.

15. Пестунов А.И. Дифференциальный криптоанализ блочного шифра MARS // Прикладная дискретная математика 2009. №6. C. 56-63.

16. 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.

17. Schneier Bruce. The Blowfish Encryption Algorithm -- One Year Later // Dr. Dobb's Journal, 1995. P. 101-137.

18. 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.

19. Rivest R.L., Robshaw M.J.B., Sidney R., and Yin Y.L. The RC6 BlockCipher, 1998. P. 42-57.

20. Carolynn Burwick Don Coppersmith. The MARS Encryption Algorithm. [Электронный ресурс]. URL: http://csis.bits-pilani.ac.in (дата обращения: 24.05.2011).

21. Schneier Bruce. Applied Cryptography, (2nd edition). John Wiley & Sons. 1996. PP. 334–335.

22. 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.