О вероятности протяжки однобитовой разности через сложение и вычитание по модулю | ПДМ. 2012. № 4(18).

О вероятности протяжки однобитовой разности через сложение и вычитание по модулю

Доказано, что вероятность протяжки однобитовой разности через сложение и вычитание по модулю равна 1, если этот бит является старшим, и 1j2, если этот бит отличен от старшего. Проведённые эксперименты подтверждают эти результаты.

Speeds of convergence in limit theorems for joint distributions of some random binary mappings characteristics.pdf Введение Разностный (дифференциальный) анализ [1] вместе со всевозможными своими разновидностями (см., например, [2-5]) является одним из наиболее распространённых методов исследования стойкости блочных шифров. К настоящему моменту в рамках этого подхода разработано довольно много атак, однако крайне редко построение характеристик и дифференциалов, лежащих в основе данных атак, а также вычисление их вероятностей обосновывается строго математически. Отметим некоторые работы, посвящённые теоретической обоснованности разностного анализа. В [6] предложена модель так называемого марковского шифра, в рамках которой вычисляются вероятности характеристик и дифференциалов. В [7] сформулирована гипотеза стохастической эквивалентности, используемой, например, при оценке вероятности успеха разностных атак. В [8] разработана модель, в рамках которой можно создать шифр, доказуемо стойкий к разностному и линейному анализу. Работа [9] посвящена изложению разностного анализа в общем виде применительно к произвольным итеративным блочным шифрам с аддитивным раундовым ключом. Другой важной проблемой является изучение возможности так называемой про-(propagation) разности через различные операции, используемые в блочном шифре, т. е. в оценивании вероятности того, что пара блоков (подблоков) с определённой разностью преобразуется в пару блоков с такой же или другой, но также определённой разностью. В частности, в работе по разностному анализу шифра RC5 [10] утверждается, что однобитовая разность остаётся неизменной после операции сложения с вероятностью 1/2 или с вероятностью 1, если этот единственный бит — старший. Данное утверждение никак не обосновывается, за исключением того, что проводятся некоторые эксперименты, подтверждающие достоверность разработанной атаки. В работах по разностному анализу шифров MARS [11] и CAST-256 [12] также используется этот факт со ссылкой на [10]. В настоящей работе данные факты доказываются математически строго и осуществляется экспериментальная проверка полученных теоретических результатов. Под протяжкой разности двоичных векторов X ф Y через операцию о понимается разность D = (X о Z) ф (Y о Z) со случайным двоичным вектором Z. Вероятность того, что D = X ф Y, называется вероятностью этой протяжки. 1. Предварительные замечания Проиллюстрируем обозначенную проблему на примере операций XOR и циклического сдвига, которые обозначим соответственно через ф и

Ключевые слова

блочный шифр, дифференциальный криптоанализ, разностный анализ, block cipher, differential cryptanalysis, difference propagation

Авторы

ФИООрганизацияДополнительноE-mail
Пестунов Андрей ИгоревичИнститут вычислительных технологий СО РАН, г. Новосибирскнаучный сотрудникpestunov@gmail.com
Всего: 1

Ссылки

Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. No. 4. P. 3-72.
Wagner D. The boomerang attack // LNCS. 1999. V. 1636. P. 156-170.
Kelsey J., Kohno T, and Schneier B. Amplified boomerang attacks against reduced-round MARS and Serpent // LNCS. 2001. V. 1978. P. 75-93.
Biham E., Biryukov A, and Shamir A. Cryptanalysis of Skipjack reduced to 31 round using impossible differentials // LNCS. 1999. V. 1592. P. 12-23.
Пестунов А. И. Блочные шифры и их криптоанализ // Вычислительные технологии. 2007. Т. 12, спец. вып. №4. С. 42-49.
Lai X. and Massey J. Markov ciphers and differential cryptanalysis // LNCS. 1991. V. 547. P.17-38.
Nyberg K. and Knudsen L. Provable security against a differential attack // J. Cryptology. 1995. No. 8. P. 27-37.
Vaudenay S. Decorrelation: a theory for block cipher security // J. Cryptology. 2003. No. 16. P. 249-286.
Агибалов Г. П. Элементы теории дифференциального криптоанализа итеративных блочных шифров с аддитивным раундовым ключом // Прикладная дискретная математика. 2008. №1(1). С. 34-42.
Biryukov A. and Kushilevitz E. Improved cryptanalysis of RC5 // LNCS. 1998. V. 1403. P.85-99.
Пестунов А. И. Дифференциальный криптоанализ блочного шифра MARS // Прикладная дискретная математика. 2009. №4(6). С. 56-63.
Пестунов А. И. Дифференциальный криптоанализ блочного шифра CAST-256 // Безопасность информационных технологий. 2009. № 4. С. 57-62.
Боровков А. А. Теория вероятностей. М.: Наука, 1976. 352 с.
Боровков А. А. Математическая статистика. М.: Наука, 1984. 472 с.
Burwick C. et al. MARS — a candidate cipher for AES // NIST AES Proposal, 1999.
Пестунов А. И. Статистический анализ современных блочных шифров // Вычислительные технологии. 2007. Т. 12. №2. С. 122-129.
www.gladman.me.uk — Brian Gladman's Home Page. 2012.
 О вероятности протяжки однобитовой разности через сложение и вычитание по модулю | ПДМ. 2012. № 4(18).

О вероятности протяжки однобитовой разности через сложение и вычитание по модулю | ПДМ. 2012. № 4(18).

Полнотекстовая версия