Инд. авторы:	Пестунов А.И.
Заглавие:	Влияние веса Хэмминга разности на вероятность её сохранения после арифметических операций
Библ. ссылка:	Пестунов А.И. Влияние веса Хэмминга разности на вероятность её сохранения после арифметических операций // Прикладная дискретная математика. Приложение. - 2014. - № 7. - С.49-51. - ISSN 2226-308X.
Внешние системы:	РИНЦ: 22025274;
Реферат:	eng: Despite the fact that differential cryptanalysis is a widely used approach to cryptanalysis of iterative block ciphers, the authors of differential attacks rarely provide their strict mathematical reasoning. However, some steps in this direction have been already made. For instance, X. Lai and J. Massey (1991) suggested a model of so-called Markov iterative block cipher and formulated a hypothesis of stochastic equivalence. K. Nyberg and L. Knudsen (1994) showed that it is possible to create a cipher resistant to differential cryptanalysis, and, later, S. Vaudenay (2003) developed a model for creating such a cipher. G. P. Agibalov (2008) presented a general description of differential cryptanalysis for arbitrary iterative block ciphers with additive round keys. A. A. Selcuk analytically calculated probability of a differential attack success. A.I. Pestunov (2013) suggested a formalization of the basic differential cryptanalysis notions and used it for their systematization. One more important, though not thoroughly investigated problem, is finding out how does two-values difference propagate through operations used in block ciphers. The problem consists in estimating the probability that a pair of values with a fixed difference is transformed by an operation into another fixed difference. For some operations (e. g. bitwise rotation or XOR) this task is rather simple, while for some commonly used operations such as modulo addition, subtraction and multiplication, it is not a trivial one. When developing an attack on RC5, A. Biryukov and E. Kushilevitz (1998) claimed that a one-bit difference remains unchanged after modulo addition with the probability 1/2 (or with the probability 1 if the difference is located in the most significant bit). The claim has not been proved theoretically but the authors carried out some experiments verifying the attack. In works devoted to differential cryptanalysis of MARS and CAST-256, A. I. Pestunov (2009) used this fact referencing the paper of A. Biryukov and E. Kushilevitz and verifying developed attacks. Besides, in the second paper (about CAST-256) he used an experimentally found relation between the Hamming weight of a difference and the probability that this difference is preserved after modulo addition. In the current paper, the existence of this relation is proved theoretically. Exactly, it is proved that the difference of two values is preserved after their modulo addition or subtraction with a third randomly chosen value with the probability 2 or 2 -(h-1), if the most significant bit of the difference is equal to 0 or to 1 respectively. The obtained results extend the results obtained by A. I. Pestunov (2013) for one-bit differences rus: Теоретически исследована зависимость между вероятностью сохранения разности двух величин после их сложения (вычитания) по модулю с третьей равномерно распределённой величиной и весом Хэмминга этой разности. Под разностью понимается общепринятая в криптоанализе операция XOR. Доказано, что если старший бит разности равен 0, то вероятность её сохранения равна 2 -h, где h - вес Хэмминга разности, и равна 2 -(h-i), если старший бит разности равен 1.
Ключевые слова:	блочный шифр; разностный анализ; дифференциальный криптоанализ; Hamming weight; Block cipher; differential cryptanalysis; вес Хэмминга;
Издано:	2014
Физ. характеристика:	с.49-51
Цитирование:	1. Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems//J. Cryptology. 1991. No. 4. P. 3-72. 2. Lai X. and Massey J. Markov ciphers and differential cryptanalysis//LNCS. 1991. V. 547. P.17-38. 3. Nyberg K. and Knudsen L. Provable security against a differential attack//J. Cryptology. 1995. No. 8. P. 27-37. 4. Vaudenay S. Decorrelation: a theory for block cipher security//J. Cryptology. 2003. No. 16. P. 249-286. 5. Агибалов Г. П. Элементы теории дифференциального криптоанализа итеративных блочных шифров с аддитивным раундовым ключом//Прикладная дискретная математика. 2008. №1. С. 34-42. 6. Selcuk A. A. On probability of success in linear and differential cryptanalysis//J. Cryptology. 2007. No. 21. P. 131-147. 7. Пестунов А. И. О связях между основными понятиями разностного анализа итеративных блочных шифров//Прикладная дискретная математика. Приложение. 2013. №6. С. 44-48. 8. Biryukov A. and Kushilevitz E. Improved cryptanalysis of RC5//LNCS. 1998. V. 1403. P.85-99. 9. Пестунов А. И. Дифференциальный криптоанализ блочного шифра MARS//Прикладная дискретная математика. 2009. №4. С. 56-63. 10. Пестунов А. И. Дифференциальный криптоанализ блочного шифра CAST-256//Безопасность информационных технологий. 2009. № 4. С. 57-62. 11. Пестунов А. И. О вероятности протяжки однобитовой разности через сложение и вычитание по модулю//Прикладная дискретная математика. 2012. №4. С. 53-60. 12. Пестунов А. И. О влиянии веса Хэмминга разности двух величин на вероятность её сохранения после сложения и вычитания//Дискретный анализ и исследование операций. 2013. Т. 20. №5. С. 58-65.