On relations between the basic notions of differential cryptanalysis.pdf Разностный (дифференциальный) анализ [1] —это распространённый подход к анализу стойкости итеративных блочных шифров, однако несмотря на его популярность и наличие ряда разновидностей [2-5] к настоящему времени не выработана строгая единообразная терминология, его описывающая: основные понятия вводятся либо не строго, либо с использованием авторских определений. Такая ситуация не мешает разрабатывать атаки на шифры, но приводит к тому, что одни и те же понятия определяются по-разному даже признанными учёными. Кроме того, отсутствуют формализованные связи между основными понятиями данного метода: характеристики могут называться дифференциалами, дифференциалы могут объединяться с характеристиками, вероятность усечённой характеристики может вычисляться по аналогии с неусечённой, хотя корректность подобных действий строго не обоснована. Некоторые проблемы теоретического обоснования разностного анализа уже затрагивались в работах отечественных и зарубежных авторов. В [6] предложена модель марковского шифра и сформулирована гипотеза стохастической эквивалентности, в [7] предложена модель для создания шифра, доказуемо стойкого к классическим вариантам разностного и линейного анализа. Работа [8] посвящена изложению разностного анализа в общем виде применительно к произвольным итеративным блочным шифрам с аддитивным раундовым ключом, в работе [9] теоретически исследована вероятность сохранения однобитовой разности после сложения и вычитания. Автор [10] аналитически вычисляет вероятность успеха разностной атаки в зависимости от параметров блочных шифров. Заметим также, что отечественные учёные уже обращались к выработке общей криптографической терминологии, хотя разностный анализ детально не затрагивался [11, 12]. Рассмотрим некоторые вопросы, возникающие при изучении существующей терминологии разностного анализа. Мы не будем классифицировать эти вопросы, а только покажем, что существуют вполне конкретные несоответствия. Вопрос 1. Входит ли шифр в определения дифференциала и характеристики? Вопрос возникает в связи с тем, что одни авторы определяют дифференциалы и характеристики соответственно как пару или набор блоков (чисел) [1], а другие говорят о разностях открытых и шифрованных текстов [3, 6]. В первом случае дифференциалы и характеристики, состоящие из одинаковых разностей, могут относиться к разным шифрам, а во втором случае подразумевается конкретизация шифра. Вопрос 2. Входит ли вероятность в определения дифференциалов и характеристик? В исходной работе по разностному анализу [1] характеристика определяется как набор разностей и только затем вводится понятие вероятности характеристики применительно к конкретному шифру. В то же время автор [8] определяет характеристику как последовательность, состоящую и из разностей, и из вероятностей. Вопрос 3. Является ли объединение дифференциалов характеристикой? Во многих работах авторы строят дифференциалы и характеристики, называя похожие объекты по-разному. Например, в работе [13] объект ( и п \ 8 РаУнДов, / п п\ 8 РаУВД°в , и t (W (a, b, 0,c)-> (e,e, 0, 0) -> (g,h,/, 0) назван усечённой характеристикой, а объект (0, a, 0, 0) ——^ (0, b, c, d) ——^ (h, h, /, g) — уже усечённым дифференциалом. Вопрос 4. Можно ли объединять дифференциал и характеристику? В работе [1] даётся определение объединения двух характеристик. В более поздних работах [3, 6] появились понятия дифференциала, а также усечённых дифференциалов и характеристик, однако строгих определений объединения этих объектов не введено. Другими словами, не даются ответы на вопросы о возможности объединения усечённых и неусечённых характеристик и дифференциалов. Вопрос 5. Как вычислять вероятность объединения усечённых характеристик и дифференциалов? В [6] вводится понятие марковского шифра и показывается, что, согласно уравнению Колмогорова — Чепмена, вероятность характеристики для такого шифра равна произведению вероятностей характеристик, из которых она состоит. Для усечённых характеристик и дифференциалов такого утверждения нет. Вопрос 6. Является ли дифференциал характеристикой? В работе [6] отмечено, что однораундовые дифференциал и характеристика «совпадают». Отсюда вытекает актуальность установления соответствий между характеристиками и дифференциалами вне зависимости от числа раундов, а также установления соответствий между ними и их усечёнными аналогами. Список перечисленных вопросов может быть расширен, но и его достаточно, чтобы увидеть существующие проблемы. В настоящей работе предлагается один из возможных наборов определений, позволяющий сформировать единообразную систему понятий, которая согласована с существующими терминами. Формализованы соответствия между основными понятиями, в частности показано, что в рамках предлагаемого набора определений дифференциал, характеристика и усечённый дифференциал являются усечёнными характеристиками. Формализовано и обобщено понятие объединения дифференциалов и характеристик. Основной идеей, лежащей в основе предлагаемой системы понятий, является использование масок для работы с неизвестными битами в усечённых разностях. Определение 1. Пусть I = (го,... , rT} С {0,1,... , R}, где T ^ R, причём Го = 0 и rT = R. Пусть также А = (йг0,... , йгт) и M = (mV0,..., mVT) —упорядоченные множества, где йг G (0,1}s, mV G (0,1}s, mV = 0 и r G I. Тогда упорядоченная тройка (I, A,M) называется R-раундовой усечённой характеристикой. Обозначим её t £"Т° т°\ Vi—V0 раундов , V1 V1 . V2 —Vi раундов гт—VT-1 РаУнДов V , (й 0, m 0) -> (й 1, m 1) -> ...-> (й т, m т). В этом определении роли масок играют величины mV. При T =1 и, следовательно, Гт = R и I = {r0,ri} усечённая характеристика является усечённым дифференциалом, а при единичных масках усечённые характеристики и дифференциалы являются неусечёнными. Отсюда следует эквивалентность однораундовых характеристик и дифференциалов. Свойство «усечённости» выражается не только в наличии масок, но и в том, что задействованы не все раунды. Часто маски имеют вид, подобный (032,132, 032,132), другими словами, все биты определённых подблоков масок равны 0 или 1 одновременно, поэтому усечённые характеристики обычно обозначаются следующим образом: (?, а, ?, b) ^ (?, ?, ?, c) ^ (d, e, ?, f) ^ (?, g, h, ?), где а, b, c, d, e, f, g, h G (0,1}1, l — размер подблока. Определение 2. Пусть E — R-раундовый блочный шифр с блоком размера s, (I, A, M) — R-раундовая усечённая характеристика и p G [0,1]. Будем говорить, что шифр E допускает (имеет) усечённую характеристику (I, A,M) с вероятностью p, если при случайно и независимо выбранных ключах раундов и блоках открытого текста C0 и D0 выполняется равенство P((CV 1 0 Dг 1 )&mV 1 = йг 1 &mV 1,..., (CVT 0 DVT)&mVT = = йгт&mVT |(CV0 0 DV0)&mV0 = йг0&mV0)= p. Определение 3. Характеристика (/, Д, M) присоединима к R-раундовой характеристике (If Д , M), если выполняются равенства mR = m0 и $R&mR = 5°&m°. Определение 4. Пусть H = (/, Д, M) и H2 = (/, Д, M) —соответственно R- и R-раундовые усечённые характеристики, причём H2 присоединима к Hi, тогда обз-единением Hi и H2 назовём характеристику H = (/, Д, M), где I = {0 = f0,..., fy =_R + r0,R + fi,..., R + % = R + R}, Д = ОТ0,...,£fi,... ,£fTP) и M = = (mr0,... , mrT, mri,... , mrT). По аналогии с операцией конкатенации будем использовать обозначение H = Hi | H2. Определение 5. Пусть дана последовательность усечённых характеристик Hi, ..., Hl, для которых выполняется следующее свойство: Hj+1 может быть присоединена к Hj, l = 1,..., L — 1. Тогда объединением L характеристик Hi, H2, ..., Hl называется характеристика H = (... ((Hi|H2)|H3)| .. .)|Hl. Легко видеть, что определённая таким образом операция объединения ассоциативна, поэтому можно использовать запись H = Hi|H21H31 ... |Hl. Используя введённые определения, легко показать, что любую усечённую характеристику можно представить в виде объединения усечённых дифференциалов. Вычислить вероятность объединения усечённых характеристик можно с использованием уравнения Колмогорова — Чемпена по аналогии с тем, как это сделано в [6] для неусечёных характеристик. Утверждение 1. Пусть марковский шифр E представим в виде композиции E = Ei о ... о EL, где Ej, l = 1,... , L, могут быть раундами или композицией раундов. Пусть также Ej допускает некоторую характеристику Hj с вероятностью pj. Тогда шифр E допускает характеристику H = Hi| ... |HL с вероятностью p1 • ... • pL. Из этого утверждения следует очевидная справедливость общепринятого обозначения для характеристик, состоящих из нескольких дифференциалов: До-► Д1-► Д2-►...-► Дь-i-► Дь; Pi P2 P3 PL-1 PL . Rраундов . Rраундов . Дш -^ Дш1ё -^ ^^out. P q

Скачать электронную версию публикации

Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. No. 4. P. 3-72.

Пестунов А. И. Блочные шифры и их криптоанализ // Вычислительные технологии. 2007. Т. 12. Спец. вып. №4. С. 42-49.

Knudsen L. Truncated and higher order differentials // LNCS. 1995. V. 1008. P. 196-211.

Biham E., Biryukov A. and Shamir A. Cryptanalysis of Skipjack reduced to 31 round using impossible differentials // J. Cryptology. 2005. No. 18. P. 291-311.

De Canniere C., Biryukov A, and Preneel B. An introduction to block cipher cryptanalysis // Proc. IEEE. 2006. V. 94. No. 2. P. 346-356.

Lai X. and Massey J. Markov ciphers and differential cryptanalysis // LNCS. 1991. V. 547. P.17-38.

Vaudenay S. Decorrelation: a theory for block cipher security // J. Cryptology. 2003. No. 16. P. 249-286.

Агибалов Г. П. Элементы теории дифференциального криптоанализа итеративных блочных шифров с аддитивным раундовым ключом // Прикладная дискретная математика. 2008. №1. С. 34-42.

Пестунов А. И. О вероятности протяжки однобитовой разности через сложение и вычитание по модулю // Прикладная дискретная математика. 2012. №4. С. 53-60.

Selguk A. A. On probability of success in linear and differential cryptanalysis // J. Cryptology. 2007. No. 21. P. 131-147.

Словарь криптографических терминов / под ред. Б. А. Погорелова и В.Н.Сачкова. М.: МНЦМО, 2006. 94с.

Погорелое Б. А., Черемушкин А. В., Чечета С. И. Об определении основных криптографических понятий // Доклад на конф. «Математика и безопасность информационных технологий», МаБИТ-03, МГУ, 23-24 октября 2003. M., 2003.

Knudsen L. R., Robshaw M. J. B., and Wagner D. Truncated differentials and Skipjack // LNCS. 1999. V. 1666. P. 165-180.