учебники, программирование, основы, введение в,

 

Алгоритмы симметричного шифрования. Разработка Advanced Encryption Standard (AES)

 

Разработка Advanced Encryption Standard (AES)
Обзор процесса разработки AES
Инициатива в разработке AES принадлежит NIST. Основная цель состояла в создании федерального стандарта (FIPS), который бы описывал алгоритм шифрования, используемый для защиты информации как в государственном, так и в частном секторе.
Конкуренция среди финалистов была достаточно серьезной, и в результате длительного процесса оценки NIST выбрал Rijndael в качестве алгоритма AES. Мы кратко рассмотрим этот процесс и суммируем различные характеристики алгоритмов, которые были описаны на данном этапе. Следующий раздел представляет собой обзор разработки AES и обсуждение деталей алгоритмов.
Историческая справка
2 января 1997 года NIST объявил о начале разработки AES, и 12 сентября 1997 года были представлены официальные требования к алгоритмам. В этих требованиях указывалось, что целью NIST является разработка неклассифицированного, хорошо проанализированного алгоритма шифрования, доступного для широкого применения. Как минимум алгоритм должен быть симметричным и блочным и поддерживать длину блока 128 бит и длину ключа 128, 192 и 256 бит.
20 августа 1998 года NIST анонсировал пятнадцать кандидатов на алгоритм AES на первой конференции кандидатов AES (AES1), и было предложено прокомментировать их характеристики. Данные алгоритмы были разработаны промышленными и академическими кругами двенадцати стран. Вторая конференция кандидатов AES (AES2) была проведена в марте 1999 года с целью обсуждения результатов анализа предложенных алгоритмов. В августе 1999 года были представлены выбранные NIST пять финалистов. Ими стали MARS, RC6™, Rijndael, Serpent и Twofish.
Обзор финалистов
Все пять финалистов являются итерационными блочными алгоритмами шифрования: они определяют преобразование, которое повторяется определенное число раз над блоком шифруемых или дешифруемых данных. Шифруемый блок данных называется plaintext; зашифрованный plaintext называется ciphertext. Для дешифрования в качестве обрабатываемого блока данных используется ciphertext. Каждый финалист также определяет метод создания серии ключей из исходного ключа, называемый управлением ключом. Полученные ключи называются подключами. Функции раунда используют в качестве входа различные подключи для конкретного блока данных.
У каждого финалиста первая и последняя криптографические операции являются некоторой формой перемешивания подключей и блока данных. Такие операции, используемые на начальном шаге первого раунда и заключительном шаге последнего раунда, называются pre- и post-забеливанием (whitening) и могут быть определены отдельно.
Существуют также некоторые другие технические особенности финалистов. Четыре финалиста определяют таблицы подстановки, называемые S-box: AxB-битный S-box заменяет А входных битов на В выходных битов. Три финалиста определяют функции раунда, являющиеся сетью Фейштеля. В классической сети Фейштеля одна половина блока данных используется для модификации другой половины блока данных, затем половины меняются местами. Два финалиста не используют сеть Фейштеля, в каждом раунде обрабатывают параллельно весь блок данных, применяя подстановки и линейные преобразования; таким образом, эти два финалиста являются примерами алгоритмов, использующих линейно-подстановочное преобразование.
Далее рассмотрим каждый из алгоритмов в алфавитном порядке; профили и оценки будут представлены в следующих разделах.
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- и pos-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).
При объявлении финалистов представители NIST предложили обсудить и прокомментировать алгоритмы. На третьей конференции кандидатов AES (AES3), состоявшейся в апреле 2000 года, представленные комментирии были рассмотрены. Период открытого обсуждения был завершен 15 мая 2000 года.
Критерий оценки
В сентябре 1997 года, объявив об алгоритмах кандидатов, специалисты NIST определили общий критерий, который должен использоваться при сравнении алгоритмов.
Критерий оценки был разделен на три основных категории:

  1. Безопасность.
  2. Стоимость.
  3. Характеристики алгоритма и его реализации.

Безопасность является важнейшим фактором при оценке и сравнении таких возможностей как стойкость алгоритма к криптоанализу, исследование его математической основы, случайность выходных значений алгоритма и относительная безопасность по сравнению с другими кандидатами.
Стоимость является второй важной областью оценки, которая характеризует лицензионные требования, вычислительную эффективность (скорость) на различных платформах и требования к памяти. Так как одной из целей NIST была возможность широкой доступности алгоритма AES без лицензионных ограничений, обсуждались в основном требования защиты интеллектуальной собственности и потенциальные конфликты. Рассматривалась также скорость работы алгоритма на различных платформах. При первом обсуждении основное внимание уделялось скорости, связанной со 128-битными ключами. При втором обсуждении рассматривались аппаратные реализации и скорости, связанные со 192- и 256-битными ключами. Также важно рассматривать требования памяти и ограничения программной реализации.
Третьей областью оценки являлись характеристики алгоритма и реализации, такие как гибкость, аппаратное и программное соответствие и простота алгоритма. Гибкость включает возможность алгоритма:

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

Должна быть возможность реализовать алгоритм как аппаратно, так и программно, эффективность смешанных (firmware) реализаций также считается преимуществом. Относительная простота разработки алгоритма также является фактором оценки.
На первом и втором этапах обсуждения стало очевидно, что различные выводы, полученные при анализе, часто переходят из одного рассмотренного выше критерия в другой. Таким образом, критерии стоимости и характеристик алгоритма рассматривались вместе в качестве второго критерия после безопасности.
Результаты второго этапа обсуждения
Считается, что второй этап обсуждения начинается с официального объявления пяти финалистов AES 20 августа 1999 года и заканчивается официальным завершением обсуждений 15 мая 2000 года.
NIST выполнил анализ оптимизированных реализаций алгоритмов на ANSI C и Java, которые были предоставлены после первого этапа обсуждений. При тестировании реализаций на ANSI C основное внимание уделялось скорости выполнения на компьютерах, использующих различных комбинации процессоров, операционных систем и компиляторов. Код Java был протестирован на скорость и используемую память на различных системах. Дополнительно было выполнено статистическое тестирование.
Процесс выбора
Была проведена серия встреч, чтобы выработать стратегию выбора алгоритма AES. В результате этих встреч все пришли к выводу, что выбранный алгоритм обеспечивает достаточную безопасность на обозримое будущее, эффективен на различных платформах и в различных окружениях, обеспечивает приемлемую гибкость с учетом возможных требований в будущем.


Методология и результаты выбора
Принципы выбора алгоритма
Команда NIST до выбора алгоритма должна была принять несколько фундаментальных решений:
  • Принять количественный или качественный критерий при выборе алгоритма.
  • Выбрать один или несколько алгоритмов в качестве AES.
  • Выбрать запасной алгоритм(ы).
  • Рассмотреть предложения по модификации алгоритмов.

Кратко рассмотрим полученные результаты.
Качественный или количественный критерий
На одной из первых встреч по планированию второго этапа обсуждений была рассмотрена возможность количественного подхода, используя который каждый алгоритм или комбинация алгоритмов будет получать определенное количество очков, основываясь на критерии оценки. Как при осуществлении такого подхода определить конкретные значения и обеспечить сравнение алгоритмов? Количественный подход также обеспечивает явные веса для каждого выбранного фактора AES. Тем не менее, было достигнуто соглашение, что степень субъективности в критерии приведет к большому количеству дискуссий. Было также высказано предположение, что определение количественной системы счетчиков невозможно без широкого обсуждения того, что такая система является объективной. Поэтому был сделан вывод, что количественный подход неприменим, и было решено рассмотреть его после первого этапа обсуждений. То есть было решено рассмотреть безопасность алгоритма, выполнение, реализацию и остальные характеристики и принять решение, основываясь на качественной оценке каждого алгоритма - помня, что обсуждение безопасности является самым главным.
Количество алгоритмов AES
В течение первого и второго этапов обсуждений было высказано несколько аргументов относительно количества алгоритмов, которые должны быть выбраны для включения в AES. Дополнительно был сделан вывод относительно "запасного" алгоритма для случая, если будет выбран единственный AES-алгоритм, и последующие изменения окажутся невозможными. Это может произойти в случае, например, фактической атаки на алгоритм или простого обсуждения свойств. Было решено, что это необходимо считать частью параметров, которые в дальнейшем будут рассматриваться как часть процесса выбора.
Некоторые аргументы, выдвинутые в защиту нескольких алгоритмов (против единственного алгоритма), включают:

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

Были также высказаны мнения в пользу единственного алгоритма (и/или против нескольких алгоритмов). Некоторые из этих аргументов таковы:

  • Использование нескольких AES-алгоритмов уменьшает интероперабельность и увеличивает стоимость продукта.
  • Несколько алгоритмов могут представлять собой определенное число "атак на интеллектуальную собственность", направленных против реализаций.
  • Описание нескольких алгоритмов может вызвать обсуждение вопросов безопасности любого из алгоритмов.
  • Аппаратные реализации могут лучше использовать доступные ресурсы, оптимизируя выполнение единственного алгоритма, а не нескольких алгоритмов.

Во время второго этапа обсуждались эти и другие проблемы, касающиеся единственного или нескольких алгоритмов AES. Как выяснилось, существует вероятность, доказываемая коммерческими продуктами сегодня, что скоро продукты будут реализовывать несколько алгоритмов, которые определяются нуждами потребителей, требованиями интеоперабельности с наследуемыми или собственными системами и так далее. Тройной DES, который NIST предлагает сделать в обозримом будущем соответствующим FIPS-алгоритмом, доступен во многих коммерческих продуктах, как и другие FIPS и не-FIPS алгоритмы. Следовательно, считается, что наличие этих нескольких алгоритмов в конкретном продукте обеспечивает большую степень надежности, как и наличие нескольких длин ключей в AES. В случае атаки на выбранный алгоритм NIST предлагает задействовать соответствующие исследованные опции, которые включают использование других финалистов AES, у которых отсутствуют подобные атаки, либо в случае необходимости определить полностью новые подходы.
В соответствии с выводами об интеллектуальной собственности отмечалось, что если будет выбрано несколько алгоритмов AES, то возникнет необходимость реализовывать все AES-алгоритмы, таким образом создавая дополнительные риски в отношении интеллектуальной собственности.
На конференции AES3 состоялась дискуссия по поводу количества алгоритмов, которые должны быть включены в AES. Большинство присутствующих выразили поддержку выбора единственного алгоритма. Некоторые поддержали и выбор запасного алгоритма, но не было согласовано, как это должно быть выполнено. Указанное выше мнение было отражено в письменных комментариях, представленных в NIST многими из присутствующих на конференции.
Перед тем как принять решение в пользу единственного алгоритма AES, были рассмотрены все комментарии и аргументы. Остальные соответствующие FIPS алгоритмы будут обеспечивать определенную степень надежности, единственный же AES-алгоритм обеспечивает интероперабельность, способствует решению проблем интеллектуальной собственности.
Запасной алгоритм
Как уже отмечалось, существует взаимосвязь между обсуждениями проблемы нескольких алгоритмов AES и выбором запасного алгоритма, особенно в случае единственного алгоритма AES. Backup может иметь несколько форм, от алгоритма, который требуется реализовывать в продуктах AES ("cold backup"), до определяемого в AES запасного алгоритма ("hot backup"). Было доказано, что запасной алгоритм во многом эквивалентен второму AES-алгоритму, так как многие пользователи пожелают, чтобы даже "cold backup" был реализован в продуктах.
Итак, имея

  • представления о том, что запасной алгоритм должен de facto требоваться в продуктах;
  • сомнения относительно потенциальной применимости в связи с возможными достижениями криптоанализа;
  • заинтересованность NIST в обеспечении интероперабельности;
  • доступность в коммерческих продуктах других алгоритмов (как FIPS, так и не-FIPS);

было принято решение не выбирать запасной алгоритм.
Как и в случае с другими стандартами на криптографические алгоритмы, NIST продолжит исследования в области криптоанализа AES-алгоритма, и стандарт будет пересматриваться каждые пять лет. Если полученные результаты потребуют более быстрой реакции, NIST будет действовать соответствующим образом и рассмотрит все возможные момент альтернативы.
Модификация алгоритмов
На первом и втором этапах обсуждения был отмечен интерес к увеличению числа раундов в некоторых алгоритмах. Во многих случаях увеличение количества раундов объяснялось. Так, про Rijndael было сказано, что число раундов Rijndael обеспечивает достаточный запас безопасности по отношению к атакам криптоанализа.
При обсуждении были отмечены следующие результаты и введены понятия:

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

После многочисленных обсуждений приведенных выше аргументов было решено рекомендовать не изменять количество раундов AES-алгоритма.

Технические детали второго этапа обсуждений
Общая безопасность
Представленный здесь анализ был выполнен с использованием исходных спецификаций финалистов, полученных до начала второго этапа.
Безопасность являлась самым важным фактором при оценке финалистов. В отношении какого-либо из алгоритмов никаких атак не зафиксировано.
Были зафиксированы только атаки против простейших вариантов алгоритмов, когда число раундов было уменьшено или были сделаны упрощения другими способами. Ниже дается краткое описание этих атак против вариантов с уменьшенным числом раундов, а также перечислены необходимые вычислительные ресурсы и ресурсы памяти.
Трудно оценить важность атак на варианты с уменьшенным числом раундов. С одной стороны, варианты с уменьшенным числом раундов на самом деле являются другими алгоритмами, и таким образом атаки на них никак не характеризуют безопасность исходных алгоритмов. Алгоритм может быть безопасен при n раундах, даже если он уязвим при n-1 раунде. С другой стороны, обычной практикой в современном криптоанализе являются попытки сконструировать атаки на варианты с уменьшенным числом раундов. С этой точки зрения вполне понятны попытки оценить "резерв безопасности" рассматриваемых кандидатов, основываясь на атаках на варианты с уменьшенным числом раундов.
Одним из возможных критериев резерва безопасности является число, на которое полное число раундов алгоритма превышает наибольшее число раундов, при котором возможна атака. Существует ряд причин, объясняющих, почему не следует полагаться исключительно на подобную метрику для определения силы алгоритма; тем не менее, данная метрика резерва безопасности может быть полезна.
NIST рассмотрел и другие характеристики финалистов, которые могут повлиять на их безопасность. Уверенность в анализе безопасности, выполненном при разработки AES, зависит от происхождения алгоритмов и принципов их разработки, а также от трудности анализа конкретных комбинаций операций, используемых в каждом алгоритме.
Атаки на варианты с уменьшенным числом раундов
Ниже в таблице приведены атаки на варианты с уменьшенным числом раундов. Для каждой атаки в таблице указано число раундов, при котором может осуществляться атака, длина ключа, тип атаки и необходимые ресурсы. Для атаки может требоваться три категории ресурсов: вычислительные, память, информация.
В столбце "Текст" указана информация, необходимая для осуществления атаки, в частности, количество блоков незашифрованного текста и соответствующих им блоков зашифрованного данным ключом текста. Для большинства атак противнику недостаточно перехватить произвольные тексты; незашифрованный текст должен иметь конкретную форму, выбранную противником. Такие незашифрованные тексты называются выбранными незашифрованными текстами. Следует заметить, что существуют атаки, которые могут использовать любой известный незашифрованный текст в противоположность выбранному незашифрованному тексту.
В столбце "Байты памяти" указано наибольшее число байтов памяти, которые требуются в любой точке осуществления атаки; это необязательно эквивалентно хранению всей необходимой информации.
Столбец "Операции" содержит ожидаемое число операций, которое необходимо для осуществления атаки. Трудно преобразовать данное число в оценку времени, так как время зависит от вычислительных возможностей, а также от возможности параллельного выполнения процедур. Природа операций также является определенным фактором; обычно рассматриваются операции полного шифрования, но операцией может быть также частичное шифрование или другая операция. Даже в случае полного шифрования для выполнения может требоваться различное время. Следовательно, число операций, необходимых для атаки, должно рассматриваться только как приблизительная основа для сравнения различных атак.
Могут использоваться различные наборы тестов, обеспечивающие полный перебор ключей. В принципе, таким способом может быть атакован любой блочный алгоритм шифрования. Для трех вариантов размера ключа AES полный перебор ключей требует в среднем 2127, 2191 или 2255 операций. Даже наименьшее из этих чисел говорит о том, что на сегодняшний день атака посредством перебора всех ключей не имеет практического значения.


Таблица 4.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 - информация недоступна.
Полный перебор ключа требует меньше памяти и информации и может легко выполняться параллельно с использованием нескольких процессоров. Таким образом, любую атаку, требующую операций больше, чем необходимо при полном переборе ключей, осуществить сложнее. По этой причине многие из атак на варианты с уменьшенным числом раундов относятся только к большей длине ключа AES, хотя и в данном случае требования выполнения не представляют сегодня практического интереса. Аналогично требования памяти важны для многих атак на варианты с уменьшенным числом раундов.
То же относится к информации, необходимой для выполнения атак на варианты с уменьшенным числом раундов. Почти все такие атаки требуют более 230 шифрований выбранного текста; другими словами, более биллиона шифрований, а иногда даже больше. Даже если один и тот же ключ используется такое количество раз, не представляется реальным для противника собрать такое количество информации. Например, в случае линейной или дифференциальной атаки на DES требуется 243 известного незашифрованного текста и 247 шифрований выбранного незашифрованного текста. Тем не менее, случаи подобных атак против DES известны.
Одна из моделей для сбора такого большого количества информации требует от противника физического доступа к одному или нескольким устройствам шифрования, которые используют тот же самый секретный ключ. В этом случае другим полезным набором тестов является набор, который не требует хранить всю "codebook", т.е. таблица содержит только блоки зашифрованного текста, соответствующие каждому возможному блоку незашифрованного текста. Такая таблица требует для хранения 2132 байт памяти.
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 можно считать набором из 264 различных криптосистем. 64-битное количество (представляющее собой 64 бита из исходных 128 бит энтропии), которое получено из исходного ключа, управляет выбором криптосистемы. Для любой конкретной криптосистемы 64 оставшиеся бита используются для ключа. Как результат такого разделения 128 битов высказываются утверждения, что Twofish может быть подвержен атаке divide-and-conquer. При такой атаке взломщик выясняет, какая из 264 криптосистем используется, а затем определяет ее ключ. Однако не существует общей атаки, соответствующей указанной стратегии. Это означает, что если атакующий столкнулся с задачей дешифрования зашифрованного 128-битным ключом текста, то неясно, как разделить 128-битный ключ энтропии. С другой стороны, если 128-битный ключ используется повторно, то каждое применение может дать некоторую информацию о выбранной криптосистеме. Если атакующий имеет возможность выполнять повторяющееся исследование активной криптосистемы, то он имеет возможность определить, какая из 264 криптосистем используется. То же можно сказать и о большей длине ключа (в общем случае для 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 был подвергнут критике за сложность, которая затрудняет его анализ.

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика