Разработка Advanced Encryption Standard (AES)
Понимая слабость и уязвимость стандарта DES, NIST (Национальный Институт стандартов и технологий (США)) в 1997 году стал инициатором проведения конкурса на разработку нового криптографического стандарта, который должен был стать преемником DES. Требования к новому стандарту были следующими:
блочный шифр.
длина блока, равная 128 битам.
ключи длиной 128, 192 и 256 бит.
Конкурс вызвал значительный интерес, в нём участвовало большое количество разработчиков. Дополнительные рекомендации кандидатам включали:
использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);
ориентация на 32-разрядные процессоры;
не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нём не заложено каких-либо недокументированных возможностей.
Кроме того, алгоритм, претендующий на то, чтобы стать стандартом, должен распространяться по всему миру на неэксклюзивных условиях и без платы за пользование патентом.
20 августа 1998 года на 1-й конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish. В последующих обсуждениях эти алгоритмы подвергались всестороннему анализу, причём исследовались не только криптографические свойства, такие как стойкость к известным атакам, отсутствие слабых ключей, хорошие статистические свойства, но и практические аспекты реализации: оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания. Проверка кандидатов на предмет формирования случайных двоичных последовательностей осуществлялась с помощью набора статистических тестов NIST.
В течение первого раунда тестирование проводилось со 128-битными ключами. Лишь 9 алгоритмов из 15 смогли пройти статистические тесты, а именно: CAST-256, DFC, E2, LOKI-97, MAGENTA, MARS, Rijndael, SAFER+ и Serpent. Оставшиеся алгоритмы показали некоторые отклонения в тестах на случайный характер формируемых ими двоичных последовательностей
В марте 1999 года прошла 2-я конференция AES, а в августе 1999 года были объявлены 5 финалистов: MARS, RC6, Rijndael, Serpent и Twofish. Все эти алгоритмы были разработаны авторитетными криптографами с мировыми именами. На 3-й конференции AES в апреле 2000 года авторы выступили с докладами о своих алгоритмах.
MARS выполняет последовательность преобразований в следующем порядке: сложение с ключом в качестве pre-whitening (предварительное «забеливание»), 8 раундов прямого перемешивания без использования ключа, 8 раундов прямого преобразования с использованием ключа, 8 раундов обратного преобразования с использованием ключа, 8 раундов обратного перемешивания без использования ключа и вычитание ключа в качестве post-whitening («постзабеливание»). 16 раундов с использованием ключа называются криптографическим ядром. Раунды без ключа используют два 8х16-битных S-boxes, операции сложения и XOR. В дополнение к этим элементам раунды с ключом используют 32-битное умножение ключа, зависимые от данных циклические сдвиги и добавление ключа. Как раунды перемешивания, так и раунды ядра являются раундами модифицированной сети Фейстеля, в которых четверть блока данных используется для изменения остальных трех четвертей блока данных. MARS был предложен корпорацией IBM.
RC6 является параметризуемым семейством алгоритмов шифрования, основанных на сети Фейстеля; для AES было предложено использовать 20 раундов. Функция раунда в RC6 задействует переменные циклические сдвиги, которые определяются квадратичной функцией от данных. Каждый раунд также включает умножение по модулю 32, сложение, XOR и сложение с ключом. Сложение с ключом также используется для pre- и post-whitening. RC6 был предложен лабораторией RSA.
Rijndael представляет собой алгоритм, использующий линейно-подстановочные преобразования и состоящий из 10, 12 или 14 раундов в зависимости от длины ключа. Блок данных, обрабатываемый с использованием Rijndael, делится на массивы байтов, и каждая операция шифрования является байт-ориентированной. Функция раунда Rijndael состоит из четырех слоев. В первом слое для каждого байта применяется S-box размерностью 8х8 бит. Второй и третий слои являются линейными перемешиваниями, в которых строки рассматриваются в качестве сдвигаемых массивов и столбцы перемешиваются. В четвертом слое выполняется операция XOR байтов подключа и каждого байта массива. В последнем раунде перемешивание столбцов опущено. Rijndael предложен Joan Daemen (Proton World International) и Vincent Rijmen (Katholieke Universiteit Leuven).
Serpent является алгоритмом, использующим линейно-подстановочные преобразования и состоящим из 32 раундов. Serpent также определяет некриптографические начальную и заключительную перестановки, которые облегчают альтернативный режим реализации, называемый bitslice. Функция раунда состоит из трех слоев: операция XOR с ключом, 32-х параллельное применение одного из восьми фиксированных S-boxes и линейное преобразование. В последнем раунде слой XOR с ключом заменен на линейное преобразование. Serpent предложен Ross Anderson (University of Cambridge), Eli Biham (Technion) и LarsKnudsen (University of California San Diego).
Twofish является сетью Фейстеля с 16 раундами. Сеть Фейстеля незначительно модифицирована с использованием однобитных ротаций. Функция раунда влияет на 32-битные слова, используя четыре зависящих от ключа S-boxes, за которыми следуют фиксированные максимально удаленные отдельные матрицы в GF(28), преобразование псевдо-Адамара и добавление ключа. Twofish был предложен Bruce Schneier, John Kelsey и Niels Ferguson (Counterpane Internet Security, Inc.), Doug Whiting (Hi/fn, Inc.), David Wagner (University of California Berkley) и Chris Hall (Princeton University).
Во втором раунде оценка пригодности финалистов первого раунда в качестве генераторов случайных чисел проводилось на основе 192-битных и 256-битных ключей. Продолжительность статистических тестов NIST составило несколько месяцев, причем вычисления производились на множестве рабочих станциях “Sun Ultra”. Все данные формировались и обрабатывались в режиме онлайн. В результате второго раунда было показано, что каждый из пяти вышеуказанных алгоритмов формирует абсолютно случайную бинарную последовательность и поэтому может быть использован в качестве генератора псевдослучайных чисел, причем имеется возможность использования ключей размерами 128, 192 и 256 бит.
Голоса на конференции AES2 распределились следующим образом:
Rijndael: 86 за, 10 против
Serpent: 59 за, 7 против
Twofish: 31 за, 21 против
RC6: 23 за, 37 против
MARS: 13 за, 83 против
Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FPGA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Рэймен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.
2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, 26 ноября 2001 года AES был принят как FIPS 197, а пользователи, наконец, смогли вместо труднопроизносимого названия алгоритма Rijndael использовать существенно более простое словосочетание AES.
Безопасность являлась самым важным фактором при оценке финалистов. В отношении собственно алгоритмов (полных) никаких атак зафиксировано не было. Зафиксированы были только атаки против упрощённых вариантов алгоритмов, когда число раундов было уменьшено или были сделаны упрощения другими способами.
С одной стороны, варианты с уменьшенным числом раундов на самом деле являются другими алгоритмами, и таким образом атаки на них никак не характеризуют безопасность собственно исходных алгоритмов. Алгоритм может быть безопасен при n раундах, даже если он уязвим при n-1 раунде. С другой стороны, обычной практикой в современном криптоанализе являются попытки сконструировать атаки на варианты с уменьшенным числом раундов. С этой точки зрения вполне понятны попытки оценить "резерв безопасности" рассматриваемых кандидатов, основываясь на атаках на варианты с уменьшенным числом раундов.
Одним из возможных критериев резерва безопасности является число, на которое полное число раундов алгоритма превышает наибольшее число раундов, при котором возможна атака. Существует ряд причин, объясняющих, почему не следует полагаться исключительно на подобную метрику для определения силы алгоритма; тем не менее, данная метрика резерва безопасности может быть полезна.
Атаки на варианты с уменьшенным числом раундов
Алгоритм, раунды
|
Раунды (длина ключа)
|
Тип атаки
|
Текст
|
Байты памяти
|
Операции
|
MARS 16 Core (C)
16 Mixing (M)
|
11C
|
Amp. Boomerang
|
265
|
270
|
2229
|
16M, 5C
|
Meet-in-Middle
|
8
|
2236
|
2232
|
16M, 5C
|
Diff. M-i-M
|
250
|
2197
|
2247
|
6M, 6C
|
Amp. Boomerang
|
269
|
273
|
2197
|
RC6 20
|
14
|
Stat. Disting.
|
2118
|
2112
|
2122
|
12
|
Stat. Disting.
|
294
|
242
|
2119
|
14 (192,256)
|
Stat. Disting.
|
2110
|
242
|
2135
|
14 (192,256)
|
Stat. Disting.
|
2108
|
274
|
2160
|
15 (256)
|
Stat. Disting.
|
2119
|
2138
|
2215
|
Rijndael
10 (128)
|
4
|
Truncated Diff.
|
29
|
Small
|
29
|
5
|
Truncated Diff.
|
211
|
Small
|
240
|
6
|
Truncated Diff.
|
232
|
7*232
|
272
|
6
|
Truncated Diff.
|
6*232
|
7*232
|
244
|
7 (192)
|
Truncated Diff.
|
19*232
|
7*232
|
2155
|
7 (256)
|
Truncated Diff.
|
21*232
|
7*232
|
2172
|
7
|
Truncated Diff.
|
2128 - 2199
|
261
|
2120
|
8 (256)
|
Truncated Diff.
|
2128 - 2199
|
2101
|
2204
|
9 (256)
|
Related Key
|
277
|
NA
|
2224
|
Rijndael
12 (192)
|
7 (192)
|
Truncated Diff.
|
232
|
7*232
|
2184
|
7 (256)
|
Truncated Diff.
|
232
|
7*232
|
2200
|
Rijndael
14 (256)
|
7 (192, 256)
|
Truncated Diff.
|
232
|
7*232
|
2140
|
Serpent 32
|
8 (192, 256)
|
Amp. Boomerang
|
2113
|
2119
|
2179
|
6 (256)
|
Meet-in-Middle
|
512
|
2246
|
2247
|
6
|
Differential
|
283
|
240
|
290
|
6
|
Differential
|
271
|
275
|
2103
|
6 (192, 256)
|
Differential
|
241
|
245
|
2163
|
7 (256)
|
Differential
|
2122
|
2126
|
2248
|
8 (192, 256)
|
Amp. Boomerang
|
2128
|
2133
|
2163
|
8 (192, 256)
|
Amp. Boomerang
|
2110
|
2115
|
2175
|
9 (256)
|
Amp. Boomerang
|
2110
|
2212
|
2252
|
Twofish 16
|
6 (256)
|
Impossible Diff.
|
NA
|
NA
|
2256
|
6
|
Related Key
|
NA
|
NA
|
NA
|
NA – информация недоступна.
В итоге финалисты продемонстрировали следующие характеристики, относящиеся к безопасности: ни против одного из пяти алгоритмов не существует общих известных атак, поэтому определение уровня безопасности является достаточно приблизительным:
MARS показывает высокую степень резерва безопасности. Кратко охарактеризовать MARS трудно, потому что фактически MARS реализует два различных типа раунда. MARS даже критиковали за сложность, которая может препятствовать анализу его безопасности.
RC6 показал адекватный резерв безопасности. Однако RC6 критиковали за небольшой резерв безопасности по сравнению с другими финалистами. С другой стороны, все высоко оценили простоту RC6, облегчающую анализ безопасности. RC6 произошел от RC5, который уже достаточно хорошо проанализирован.
Rijndael показал адекватный резерв безопасности. Резерв безопасности довольно трудно измерить, потому что число раундов изменяется в зависимости от длины ключа. Rijndael критиковался по двум направлениям: что его резерв безопасности меньше, чем у других финалистов, и что его математическая структура может привести к атакам. Тем не менее, его структура достаточно проста и обеспечивает возможность анализа безопасности.
Serpent показал значительный резерв безопасности. Serpent также имеет простую структуру, безопасность которой легко проанализировать.
Twofish показал высокий резерв безопасности. Поскольку Twofish использует зависящую от ключа функцию раунда, для него замечания о резерве безопасности могут иметь меньшее значение, чем для других финалистов. Зависимость S-boxes Twofish только от k/2 битов энтропии в случае k-битного ключа позволяет сделать вывод, что Twofish может быть подвегнут divide-and-conquer-атаке, хотя такая атака не найдена. Twofish был подвергнут критике за сложность, которая затрудняет его анализ.
|
