Общая безопасность

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

Безопасность являлась самым важным фактором при оценке финалистов. В отношении какого-либо из алгоритмов никаких атак не зафиксировано.

Были зафиксированы только атаки против простейших вариантов алгоритмов, когда число раундов было уменьшено или были сделаны упрощения другими способами. Ниже дается краткое описание этих атак против вариантов с уменьшенным числом раундов, а также перечислены необходимые вычислительные ресурсы и ресурсы памяти.

Трудно оценить важность атак на варианты с уменьшенным числом раундов. С одной стороны, варианты с уменьшенным числом раундов на самом деле являются другими алгоритмами, и таким образом атаки на них никак не характеризуют безопасность исходных алгоритмов. Алгоритм может быть безопасен при n раундах, даже если он уязвим при n-1 раунде. С другой стороны, обычной практикой в современном криптоанализе являются попытки сконструировать атаки на варианты с уменьшенным числом раундов. С этой точки зрения вполне понятны попытки оценить "резерв безопасности" рассматриваемых кандидатов, основываясь на атаках на варианты с уменьшенным числом раундов.

Одним из возможных критериев резерва безопасности является число, на которое полное число раундов алгоритма превышает наибольшее число раундов, при котором возможна атака. Существует ряд причин, объясняющих, почему не следует полагаться исключительно на подобную метрику для определения силы алгоритма; тем не менее, данная метрика резерва безопасности может быть полезна.

NIST рассмотрел и другие характеристики финалистов, которые могут повлиять на их безопасность. Уверенность в анализе безопасности, выполненном при разработки AES, зависит от происхождения алгоритмов и принципов их разработки, а также от трудности анализа конкретных комбинаций операций, используемых в каждом алгоритме.

Атаки на варианты с уменьшенным числом раундов

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

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

В столбце "Байты памяти" указано наибольшее число байтов памяти, которые требуются в любой точке осуществления атаки; это необязательно эквивалентно хранению всей необходимой информации.

Столбец "Операции" содержит ожидаемое число операций, которое необходимо для осуществления атаки. Трудно преобразовать данное число в оценку времени, так как время зависит от вычислительных возможностей, а также от возможности параллельного выполнения процедур. Природа операций также является определенным фактором; обычно рассматриваются операции полного шифрования, но операцией может быть также частичное шифрование или другая операция. Даже в случае полного шифрования для выполнения может требоваться различное время. Следовательно, число операций, необходимых для атаки, должно рассматриваться только как приблизительная основа для сравнения различных атак.

Могут использоваться различные наборы тестов, обеспечивающие полный перебор ключей. В принципе, таким способом может быть атакован любой блочный алгоритм шифрования. Для трех вариантов размера ключа AES полный перебор ключей требует в среднем 2¹²⁷, 2¹⁹¹ или 2²⁵⁵ операций. Даже наименьшее из этих чисел говорит о том, что на сегодняшний день атака посредством перебора всех ключей не имеет практического значения.

Таблица 4.1. Атаки на варианты с уменьшенным числом раундов
Алгоритм, раунды	Раунды (длина ключа)	Тип атаки	Текст	Байты памяти	Операции
MARS 16 Core (C) 16 Mixing (M)	11C	Amp. Boomerang	2^65	2^70	2^229
16M, 5C	Meet-in-Middle		2^236	2^232
16M, 5C	Diff. M-i-M	2^50	2^197	2^247
6M, 6C	Amp. Boomerang	2^69	2^73	2^197
RC6 20		Stat. Disting.	2^118	2^112	2^122
	Stat. Disting.	2^94	2^42	2^119
14 (192,256)	Stat. Disting.	2^110	2^42	2^135
14 (192,256)	Stat. Disting.	2^108	2^74	2^160
15 (256)	Stat. Disting.	2^119	2^138	2^215
Rijndael 10 (128)		Truncated Diff.	2^9	Small	2^9
	Truncated Diff.	2^11	Small	2^40
	Truncated Diff.	2^32	7*2^32	2^72
	Truncated Diff.	6*2^32	7*2^32	2^44
7 (192)	Truncated Diff.	19*2^32	7*2^32	2^155
7 (256)	Truncated Diff.	21*2^32	7*2^32	2^172
	Truncated Diff.	2^128 - 2^199	2^61	2^120
8 (256)	Truncated Diff.	2^128 - 2^199	2^101	2^204
9 (256)	Related Key	2^77	NA	2^224
Rijndael 12 (192)	7 (192)	Truncated Diff.	2^32	7*2^32	2^184
7 (256)	Truncated Diff.	2^32	7*2^32	2^200
Rijndael 14 (256)	7 (192, 256)	Truncated Diff.	2^32	7*2^32	2^140
Serpent 32	8 (192, 256)	Amp. Boomerang	2^113	2^119	2^179
6 (256)	Meet-in-Middle		2^246	2^247
	Differential	2^83	2^40	2^90
	Differential	2^71	2^75	2^103
6 (192, 256)	Differential	2^41	2^45	2^163
7 (256)	Differential	2^122	2^126	2^248
8 (192, 256)	Amp. Boomerang	2^128	2^133	2^163
8 (192, 256)	Amp. Boomerang	2^110	2^115	2^175
9 (256)	Amp. Boomerang	2^110	2^212	2^252
Twofish 16	6 (256)	Impossible Diff.	NA	NA	2^256
	Related Key	NA	NA	NA

NA - информация недоступна.

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

То же относится к информации, необходимой для выполнения атак на варианты с уменьшенным числом раундов. Почти все такие атаки требуют более 2³⁰ шифрований выбранного текста; другими словами, более биллиона шифрований, а иногда даже больше. Даже если один и тот же ключ используется такое количество раз, не представляется реальным для противника собрать такое количество информации. Например, в случае линейной или дифференциальной атаки на DES требуется 2⁴³ известного незашифрованного текста и 2⁴⁷ шифрований выбранного незашифрованного текста. Тем не менее, случаи подобных атак против DES известны.

Одна из моделей для сбора такого большого количества информации требует от противника физического доступа к одному или нескольким устройствам шифрования, которые используют тот же самый секретный ключ. В этом случае другим полезным набором тестов является набор, который не требует хранить всю "codebook", т.е. таблица содержит только блоки зашифрованного текста, соответствующие каждому возможному блоку незашифрованного текста. Такая таблица требует для хранения 2¹³² байт памяти.

MARS

Существует много способов упростить MARS для анализа, так как он имеет гетерогенную структуру, состоящую из четырех различных типов раундов. 16 раундов с ключом криптографического ядра разделены 16 раундами перемешивания без использования ключа, а также pre- и post-whitening.

Известны четыре атаки на три упрощенных варианта MARS. Первый вариант включает 11 раундов ядра без раундов перемешивания и забеливания. Предложен новый тип урезанной дифференциальной атаки, названной boomerang-amplifier. Второй вариант включает забеливание и все 16 раундов перемешивания, но снижает количество раундов ядра с 16 до 5. В данном варианте предложены две различные атаки meet-in-the-middle; для такой атаки противнику не требуется выбирать незашифрованные тексты. Третий вариант включает забеливание, но снижает как число раундов перемешивания, так и число раундов ядра с 16 до 6.

RC6

Известны две атаки на варианты RC6, представляющие небольшие, но итерационные статистические предположения относительно функции раунда. Полученные статистические взаимосвязи между определенной формой входов и соответствующими им выходами могут быть использованы для нахождения отличия определенного числа раундов RC6 от случайной перестановки. Предполагается, что различие подключей является равномерно случайным. Атака представляет собой метод восстановления секретного ключа для 12-, 14- и 15-раундовых вариантов.

Rijndael

Спецификация Rijndael описывает урезанную дифференциальную атаку для 4-, 5- и 6-раундовых вариантов Rijndael на основе 3-раундовых отличий Rijndael. Данная атака названа Square, по имени алгоритма шифрования, к которому она впервые была применена.

Возможно также создание атак на варианты Rijndael, непосредственно полученных из Square-атаки. Square-атака может быть расширена на 7-раундовый вариант Rijndael с помощью дополнительного раунда для подключей. В таблице были приведены результаты для 192- и 256-битных ключей, когда общее число операций остается меньше, чем требуется для экстенсивного перебора.

Serpent

Используется amplified boomerang технология для создания 7 раундов отличий в Serpent, что приводит к атаке на вариант Serpent с 8 раундами для 192- и 256-битных ключей. Уточнение основано на экспериментальном наблюдении уменьшения текстов, памяти и обработки, требуемых для атаки; также предлагается расширение атаки на 9-раундовый вариант. Кроме того, возможна стандартная атака meet-in-the-middle и дифференциальные атаки на 8-раундовый вариант Serpent, что требует полного codebook.

Twofish

Обнаружены две атаки на варианты Twofish. Пять раундов дифференциала используются для атаки 6-раундового варианта Twofish при 256-битном ключе, что требует количества выполняемых операций, эквивалентного тому, которое необходимо для экстенсивного поиска. Если pre- и post-whitening из варианта удалить, то атака может быть расширена на 7 раундов; в качестве альтернативы вариант из 6 раундов может быть атакован со сложностью, меньшей чем экстенсивный перебор для каждой длины ключа. Также возможны атаки на Twofish с уменьшенным числом раундов, для которого упрощения сделаны другими способами, например с помощью фиксированных S-boxes, посредством удаления забеливания или подключей или допуская частичное угадывание ключа.

Пока не известны атаки на Twofish с помощью простого уменьшения числа раундов. Известны дифференциальные характеристики 6 раундов, которые применимы только к определенным зависящим от ключа S-boxes, таким образом атака оказывается возможной только на определенное подмножество ключей. Данное конкретное подмножество ключей может рассматриваться как класс слабых ключей, так как авторы утверждают, что характеристики, подобные этим, непосредственно приводят к атакам на 7- и 8-раундовые варианты Twofish.

Резерв безопасности

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

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

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

Разработка метрики основана на небольшом числе раундов, атаки на которые в настоящий момент технически возможны. Не существует исходного определения количества анализируемых раундов или даже общего числа раундов, определенного для каждого алгоритма. Например, должно ли забеливание в MARS, Twofish, RC6 и Rijndael считаться раундом или частью раунда? MARS имеет 16 раундов перемешивания без использования ключа и 16 раундов ядра с использованием ключа: является MARS 16-раундовым алгоритмом, 32-раундовым или чем-то промежуточным? Должны ли атаки игнорировать раунды перемешивания? Должны ли варианты с уменьшенным числом раундов Serpent или Rijndael требовать какой-либо модификации заключительного раунда? Другим неопределенным фактором является длина ключа, особенно для Rijndael, в котором число раундов зависит от длины ключа.

Какие типы атак должны анализироваться? Одни атаки будут успешными только против небольшой доли ключей; для других требуются операции шифрования для неизвестных ключей; третьи определяют различия для выходов случайных перестановок без явного метода восстановления ключа; некоторые атаки основаны на экспериментальных предположениях. Более того, атаки требуют различных ресурсов; многие даже предполагают, что атакующему доступен весь codebook.

Таким образом, NIST не пытался сократить свои исследования ресурсов безопасности финалистов до единственной метрики. Были рассмотрены все предложенные данные и использовано исходное число анализируемых раундов относительно общего числа раундов, указанного для алгоритма. Результат приведен ниже для каждого финалиста.

Заметим, что раунды, определенные для кандидатов, не обязательно сопоставимы друг с другом. Например, алгоритмы, основанные на сети Фейштеля, т.е. MARS, RC6 и Twofish, требуют двух раундов для изменения полного слова данных, в то время как для Rijndael и Serpent это выполняется в единственном раунде.

MARS: результаты для MARS зависят от обработки "wrapper", например, pre- и post-whitening и 16 раундов перемешивания без использования ключа, которые окружают 16 раундов ядра с использованием ключа. Без подобного wrapper 11 из 16 раундов ключа могут быть атакованы. С wrapper MARS имеет намного больше раундов, чем то количество, которое может быть атаковано: только 5 из 16 раундов ядра или 21 из 32 общего числа раундов может быть атаковано. Либо, если wrapper считать как часть раунда с ключом, то 7 из 18 раундов может быть атаковано. Для любого из этих случаев MARS демонстрирует достаточно большой резерв безопасности.

RC6: атаки созданы для 12, 14 и 15 из 20 раундов RC6, в зависимости от длины ключа. Тем самым RC6 показывает адекватный резерв безопасности.

Rijndael: для 128-битных ключей 6 или 7 из 10 раундов Rijndael могут быть атакованы, атака на 7 раундов требует полного codebook. Для 192-битных ключей 7 из 12 раундов могут быть атакованы. Для 256-битных ключей 7, 8 или 9 из 14 раундов могут быть атакованы. Атака на 8 раундов требует полного codebook и атака на 9 раундов требует шифрования для неизвестных ключей. Rijndael демонстрирует адекватный резерв безопасности.

Serpent: атаки созданы для 6, 8 или 9 из 32 раундов Serpent, в зависимости от длины ключа. Serpent показывает адекватный резерв безопасности.

Twofish: предпринята атака на 6 из 16 раундов Twofish, которая требует операций шифрования для неизвестных ключей. Другая атака, предложенная для 6 раундов для 256-битного ключа, является более эффективной, чем экстенсивный поиск ключа. Twofish демонстрирует адекватный резерв безопасности.

Принципы разработки и происхождение алгоритмов

Исторические корни, лежащие в основе принципов разработки, влияют на доверие к алгоритму и на анализ его безопасности. Это также применимо к составным элементам алгоритма, таким как S-boxes. Требуется много времени для разработки атак на неизвестные технологии, традиционные технологии обычно анализируются больше, особенно если уже существует атака на них. Например, сеть Фейштеля хорошо изучена, т.к. она применяется в DES, и три финалиста используют варианты этой конструкции. Другим элементом, способным повлиять на доверие к алгоритму, является разработка S-boxes, которые могут содержать различные скрытые "люки". Это обсуждается далее для каждого финалиста.

MARS: разнородная структура раунда MARS не исследована. Как раунд перемешивания, так и раунд ядра основаны на сети Фейштеля со значительными изменениями. MARS использует много различных операций, большинство из которых традиционны. Материал ключа и данные применяются для регулирования различных операций ротации. S-box создается детерминировано с учетом требуемых свойств; таким образом, спецификация MARS утверждает, хотя это маловероятно, что MARS содержит какую-либо структуру, которая может использоваться в качестве люка для атаки. Спецификация MARS не рассматривает какой-либо алгоритм в качестве своего предшественника.

RC6: разработка RC6 развивалась из разработки RC5, который анализировался несколько лет. Безопасность обоих алгоритмов основана на переменных ротациях как основной источник нелинейности; S-boxes в алгоритме не существует. Операция переменной ротации в RC6, в отличие от RC5, регулируется квадратичной функцией от данных. Управление ключом в RC6 и RC5 не отличается. Структура раунда RC6 является вариантом сети Фейштеля. Спецификация RC6 утверждает, что в RC6 не существует люков, потому что при вычислении ключа используется только часть RC6, которая математически хорошо изучена.

Rijndael: Rijndael является байт-ориентированным алгоритмом шифрования, основанным на "Квадрате (Square)". Представляется, что Square-атака является отправной точкой для дальнейшего анализа. Типы операций подстановки и перестановки, используемые в Rijndael, являются стандартными. S-box имеет математическую структуру, основанную на комбинации инверсии в поле Галуа и афинного преобразования. Хотя данная математическая структура может помочь в осуществлении атаки, структура не является скрытой. Спецификация Rijndael утверждает, что если есть подозрение, что S-box содержит люк, то S-box может быть заменен.

Serpent: Serpent является байт-ориентированным алгоритмом. Типы операций подстановки и перестановки являются стандартными. S-boxes создаются детерминировано, как и в случае DES, и обладают теми же свойствами; спецификация Serpent устанавливает, что при такой конструкции нет опасения, что существуют люки. Спецификация Serpent не рассматривает какой-либо алгоритм в качестве своего предшественника.

Twofish: Twofish использует незначительную модификацию сети Фейштеля. Спецификация не рассматривает какой-либо алгоритм в качестве своего предшественника, но существует несколько предшествующих алгоритмов, которые разделяют важные свойства Twofish, такие как зависящие от ключа S-boxes и подходы к их разработке. Спецификация Twofish предполагает, что Twofish не имеет люков и доказывает это утверждение несколькими аргументами, включая переменные S-boxes.

Простота

Простота является свойством, влияние которого на безопасность трудно оценивать. С одной стороны, сложные алгоритмы могут считаться менее удобными для атаки. С другой стороны, результаты легче получить для простого алгоритма, и простой алгоритм проще проанализировать. Следовательно, при анализе AES легче выполнить анализ более простого алгоритма.

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

Для стандартного дифференциального криптоанализа реально используемые типы операций влияют на строгость анализа безопасности. Если материал ключа перемешивается с данными только операцией XOR, как в Serpent и Rijndael, то пары незашифрованного текста с данной XOR разницей являются естественными входами, и анализ безопасности относительно очевиден. Если материал ключа перемешивается с данными более чем в одной операции, как в случае остальных финалистов, то исходного описания разницы не существует, и анализ безопасности требует больших усилий. Аналогично, использование переменных ротаций в MARS и RC6 скрывает возможность получения ясных результатов относительно безопасности при линейных и дифференциальных атаках.

Другим аспектом простоты, который относится к анализу безопасности, является масштабируемость. Если упрощенный вариант может, например, создаваться с меньшей длиной блока, то проводить эксперименты с вариантами становится легче, и при этом изучаются свойства исходного алгоритма. Считается, что отсутствие уменьшенных версий MARS существенно затрудняет анализ и экспериментирование. Аналогично, "реальные" масштабируемые в сторону упрощения варианты Twofish создавать трудно. Оба требования являются правдоподобными, хотя следует заметить, что спецификации MARS и Twofish содержат достаточный анализ своих элементов разработки. В спецификации Serpent утверждается, что создать масштабируемый в сторону упрощения вариант Serpent нетрудно. RC6 и Rijndael являются масштабируемыми в силу способа разработки.

Статистическое тестирование

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

При полном тестировании каждый из алгоритмов создает выглядящие случайными выходы для каждой из длин ключа. Для тестирования уменьшенного числа раундов выходы предыдущего раунда должны быть случайными, как и выходы каждого последующего раунда. Оказалось, что выходы MARS проявляют случайность на 4 и более раундах ядра, RC6 и Serpent - на 4 и более раундах, Rijndael - на 3 и более раундах, Twofish - на 2 и более раундах.

Количественная мера, включающая степень полноты, лавинный эффект и критерий ограничения лавинного эффекта, является "неясной при случайных перестановках после очень небольшого числа раундов" для всех финалистов.

В заключении следует отметить, что ни один из финалистов не является статистически отличимым от случайной функции.

Другие замечания по безопасности

Существует много обзоров, касающихся различных свойств, которые могут влиять на безопасность финалистов.

MARS: разнородная структура MARS и разнообразие операций обеспечивают защиту от неизвестных атак. Управление ключом в MARS требует нескольких стадий перемешивания.

RC6: перемешивание, осуществляемое в RC6 при управлении ключом, считается преимуществом с точки зрения безопасности.

Rijndael: обсуждаются три понятия, касающиеся математической структуры Rijndael и потенциальных уязвимостей. Во-первых, все операции алгоритма выполняются над целым байтом, а не над отдельными битами; это свойство позволяет осуществлять Square-атаку на варианты с уменьшенным числом раундов. Более того, при симметричном перемещении байтов уязвимость повышается. Для нарушения симметрии при управлении ключом используются различные константы раунда, причем эти константы имеют только один бит. Если Rijndael упростить таким образом, чтобы опустить эти константы раунда, шифрование будет сравнимо с ротацией каждого слова данных и подключей на байт.

Во-вторых, Rijndael является наиболее линейным. Можно показать, как применить линейное отображение на биты в каждом байте без изменения всего алгоритма, компенсируя линейное отображение в остальных элементах алгоритма, включая управление ключом. Аналогично, поле Галуа, лежащее в основе S-box, может быть представлено различными базисными векторами или преобразовано в другие поля Галуа с другими определяющими полиномами. Другими словами, математическая структура Rijndael допускает много эквивалентных формулировок. Существует предположение, что выполняя серию преобразований над S-box, атакующий может найти формулировку Rijndael, имеющую уязвимости.

Третье утверждение относится к относительно простой алгебраической формуле для S-box, которая приведена в спецификации Rijndael. Формула является полиномом степени 254 над данным полем Галуа, но в полиноме существует только девять термов, что намного меньше, чем ожидается для обычно случайно созданного S-box того же размера. Математическое выражение для повторения нескольких раундов Rijndael будет намного более сложным, но увеличение размера выражения как функции от числа раундов должно быть проанализировано в деталях.

Также отмечается, что атакующий, который восстанавливает или угадывает соответствующие биты подключей Rijndael, имеет возможность вычислить дополнительные биты подключей. (В случае DES это свойство помогает сконструировать линейные и дифференциальные атаки).

Serpent: Serpent имеет небольшой размер S-boxes, хотя следует отметить, что они хорошо разработаны с учетом линейного и дифференциального криптоанализа. Атакующий, который восстанавливает или угадывает соответствующие биты подключей, имеет возможность вычислить дополнительные биты подключей.

Twofish: Twofish использует новое понятие, которое состоит в формировании зависящих от ключа S-boxes. Это обеспечивает нестандартную зависимость между безопасностью алгоритма и структурой управления ключом и S-boxes. В случае 128-битного ключа (когда существует 128-битная энтропия) Twofish можно считать набором из 2⁶⁴ различных криптосистем. 64-битное количество (представляющее собой 64 бита из исходных 128 бит энтропии), которое получено из исходного ключа, управляет выбором криптосистемы. Для любой конкретной криптосистемы 64 оставшиеся бита используются для ключа. Как результат такого разделения 128 битов высказываются утверждения, что Twofish может быть подвержен атаке divide-and-conquer. При такой атаке взломщик выясняет, какая из 2⁶⁴ криптосистем используется, а затем определяет ее ключ. Однако не существует общей атаки, соответствующей указанной стратегии. Это означает, что если атакующий столкнулся с задачей дешифрования зашифрованного 128-битным ключом текста, то неясно, как разделить 128-битный ключ энтропии. С другой стороны, если 128-битный ключ используется повторно, то каждое применение может дать некоторую информацию о выбранной криптосистеме. Если атакующий имеет возможность выполнять повторяющееся исследование активной криптосистемы, то он имеет возможность определить, какая из 2⁶⁴ криптосистем используется. То же можно сказать и о большей длине ключа (в общем случае для k-битных ключей криптосистема определяется k/2 битами энтропии).

Эта особенность Twofish называется свойством разделения ключа. Зависимость S-boxes в Twofish только от 64 бит энтропии в случае 128-битного ключа была специально предусмотрена разработчиками. Это решение является некоторым аналогом безопасности/эффективности, включающих определение числа раундов в системах с фиксированной функцией раунда. Утверждается, что если S-boxes зависят от 128 бит энтропии, то число раундов Twofish можно уменьшить, чтобы избежать отрицательного влияния на свойства ключа и/или количество исходного материала.

Краткая характеристика финалистов

Как уже отмечалось, ни против одного из финалистов не существует общих атак. Однако определение уровня безопасности, обеспечиваемого финалистами, является достаточно приблизительным. Суммируем некоторые известные характеристики безопасности финалистов.

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 был подвергнут критике за сложность, которая затрудняет его анализ.

5. Лекция: Алгоритмы симметричного шифрования. Часть 3. Разработка Advanced Encryption Standard (AES) (продолжение): Рассматриваются характеристики алгоритмов, являющихся финалистами конкурса AES. Представлены особенности программной реализации каждого из финалистов, возможность их реализации в окружениях с ограничениями пространства, возможность вычисления на лету подключей для каждого алгоритма.

Дата добавления: 2014-12-23