Оценки сложности дифференциальной атаки при различных параметрах блочного шифра

УДК 519.7

ОЦЕНКИ СЛОЖНОСТИ ДИФФЕРЕНЦИАЛЬНОЙ АТАКИ ПРИ РАЗЛИЧНЫХ ПАРАМЕТРАХ БЛОЧНОГО ШИФРА1

А. И. Пестунов

Дифференциальный криптоанализ [1] является распространенным подходом к построению атак на блочные шифры. Однако, как было замечено в [2], большинство существующих на сегодняшний день результатов криптоанализа блочных шифров представляют собой конкретные атаки на конкретные шифры. В работе [2] частично восполняется данный пробел. В предположении, что ключ является аддитивным, описывается дифференциальная атака в общем виде и сводится к решению системы уравнений.

В настоящей работе акцент делается на то, что в ряде случаев дифференциальная атака не является детерминированной, то есть она имеет вероятность успеха и неудачи. Под успехом понимается тот факт, что, отработав, атака на выходе даст верный искомый ключ. В частности, в работах, посвященных дифференциальному криптоанализу шифров MARS и CAST-256, описывались атаки, для которых подсчитывались вероятности успеха [3, 4].

Схемы этих атак похожи, различие заключается по сути только в дифференциальных характеристиках, на основании которых атаки строятся. В связи с этим возникает идея описать алгоритм в общем виде в зависимости от различных параметров блочного шифра и тем самым позволить криптоаналитику построить дифференциальную характеристику и автоматически получить вероятность успеха и сложность атаки, основанной на этой характеристике. Таким образом, криптоаналитик сфокусируется на специфических свойствах шифра, не отвлекаясь на построение атаки. В настоящей работе реализуется эта идея и рассчитывается сложность атаки при различных параметрах блочного шифра с целью достичь вероятности успеха не менее 99 %.

Дифференциальная атака в общем виде

Пусть имеется дифференциальная характеристика с разностью входных блоков Ainp и разностью выходных блоков A0ut. Атака, направленная на отыскание подключа последнего раунда и основанная на данной характеристике, выглядит так:

1. Сформировать G групп различных пар блоков Ag, Bg (g = 1,..., G; t = 1,..., T) с разностью Ainp.

2. Для каждой из пар (Ag, Bg) запросить пару шифртекстов Xg = Cipher(Ag) и

= Cipher(Bg), полученные G • T пар шифртекстов сохранить в памяти.

3. Перебрать все возможные значения искомого подключа k Є {0,1,..., 2n — 1} и для каждого из них выполнить следующие действия:

а) g := 1;

б) с помощью последнего раунда и подключа k расшифровать сохраненные в памяти пары шифртекста из группы g и получить пары Ptg и Qg ;

в) если Ptg ф Qg = A0ut для всех t = 1,...,T, то k — это неправильный подключ-кандидат. Отбросить его и перейти к п. 3, где выбрать следующий подключ-кандидат; если хотя бы одна из пар обеспечивает условие Pt ф Qg = Aout, то перейти к п. г;

1 Работа поддержана грантом в рамках Лаврентьевского конкурса молодежных проектов СО РАН 2010-2011 г.

г) если д < С, то д := д + 1 и перейти к п. б; иначе к — это верный подключ.

Параметры описанной атаки зависят от вероятности дифференциальной характеристики, параметров блочного шифра и желаемой вероятности успеха атаки. В данной работе параметры С и Т подбирались таким образом, чтобы вероятность атаки составляла на менее 99%. Затем полученные значения использовались для вычисления сложности атаки.

Результаты расчетов для некоторых параметров шифра приведены в таблице.

Расчет параметров атаки и ее сложности при различных параметрах шифра

Параметры шифра Параметры атаки Сложность

Размер Размер пере- Вероятность Коли- Количество Выбран- Память, Коли-

блока, бираемого характе- чество пар блоков ные байт чество

бит подключа, бит ристики групп (С) в группе (Т) блоки шифро- ваний

64 32 2-ій 1 2-19 220 223 253

2-32 1 2-35 236 239 269

2-48 2 2-51 253 256 286

64 2-16 1 2-19 220 223 285

2-32 2 2-35 237 240 2102

2-48 4 2-51 254 257 2119

96 2-16 2 2-19 221 224 2118

2-32 3 2-35 238 241 2135

2-48 6 2-51 255 258 2152

128 2-16 2 2-19 221 224 2150

2-32 4 2-35 238 241 2167

2-48 8 2-51 255 258 2184

128 32 2-16 1 2-19 220 224 253

2-32 1 2-35 236 240 269

2-48 1 2-51 252 256 285

2-64 1 2-67 268 272 2101

2-80 1 2-83 284 288 2117

2-96 1 2-99 2100 2104 2133

2-112 2-115 2117 2121 2150

64 2-16 1 2-19 220 224 285

2-32 1 2-35 236 240 2101

2-48 1 2-51 252 256 2117

2-64 1 2-67 268 272 2133

2-80 1 2-83 284 288 2149

2-96 2-99 2101 2105 2166

2-112 2-115 2118 2122 2183

96 2-16 1 2-19 220 224 2117

2-32 1 2-35 236 240 2133

2-48 1 2-51 252 256 2149

2-64 1 2-67 268 272 2165

2-80 2 2-83 285 289 2182

2-96 3 2-99 2102 2106 2199

2-112 6 2-115 2119 2123 2216

128 2-16 1 2-19 220 224 2149

2-32 1 2-35 236 240 2165

2-48 1 2-51 252 256 2181

2-64 2 2-67 269 273 2198

2-80 2 2-83 285 289 2214

2-96 4 2-99 2102 2106 2231

2-112 8 2-115 2119 2123 2248

ЛИТЕРАТУРА

1. Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptol. 1991. V.4. P. 3-72.

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

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

4. Пестунов А. И. Дифференциальный криптоанализ блочного шифра CAST-256 // Безопасность информационных технологий. 2009. № 4. С. 57-62.

УДК 519.7

О СЛАБОМ КЛАССЕ АЛГОРИТМОВ РАЗВЁРТЫВАНИЯ КЛЮЧА ОТНОСИТЕЛЬНО МЕТОДА СВЯЗАННЫХ КЛЮЧЕЙ1

М. А. Пудовкина

В открытой литературе появляется всё больше работ, посвященных атакам на алгоритмы шифрования на основе метода связанных ключей и основанных на слабостях алгоритма развёртывания ключа (см., например, [1-8]). Однако имеется небольшое число работ, в которых описываются классы слабых алгоритмов развёртывания ключа или исследуются их свойства. Данную работу можно отнести к их числу.

Обозначим: N — множество натуральных чисел; No — множество натуральных чисел с нулем; n, r, d, l E N; Vn — n-мерное векторное пространство над полем GF(2); l — число раундов шифрования блочного алгоритма; 2 ^ r < l; gk : Vn ^ Vn — раундовая функция; K = Vd — ключевое множество.

В данной работе рассматриваются функция зашифрования и алгоритм развёртывания ключа р* = (8, р), такие, что существуют число r E N, r ^ l, и отображения А : V[ ^ Vn, 8 : K ^ Vrar, р : V[ ^ Vn, удовлетворяющие следующим свойствам:

1) (r — 1)  n < d ^ r  n;

2) 8(k) = (ko,...,kr—1);

3) для любого i E N0 выполняется равенство

(ki,..., ki+i—i) p(ki,..., ki+r—1), где ki+l+j A(ki+j , ..., ki+r— 1+j ), j 0 , ..., l r;

4) раундовая функция на всех раундах не зависит от номера раунда;

5) = 9k' для любых различных k, k' E V^;

6) существует такая функция ф : Vn х Vn ^ Vn, что для всех k E Vn, a E Vn выполняется равенство k = ф(а,в), где в = agk.

Отметим, что условие 5 является естественным и встречается практически во всех алгоритмах блочного шифрования в открытой литературе. Условие 2 означает, что по любой последовательности из r раундовых ключей ki,..., ki+r— 1 для некоторого i E {0, ...,l — r} может быть найден ключ шифрования k E K. Чаще всего ключ шифрования k совпадает с вектором (k0,..., kr—1), т. е. 8 — тождественное отображение. Отметим также, что условие 6 может иногда не выполняться. Кроме того, отображение р

хРабота выполнена при поддержке гранта Президента РФ НШ № 4.2008.10.