Advanced Encryption Standard - Advanced Encryption Standard


Из Википедии, свободной энциклопедии
Advanced Encryption Standard
(Rijndael)
AES-SubBytes.svg
SubBytes шаг, один из четырех этапов в раунде AES
генеральный
Конструкторы Винсент Рэймен , Джоан Daemen
Первое издание 1998
Происходит от Площадь
Наследники Анубис , Grand Cru
сертификация AES победитель, CRYPTREC , NESSIE , NSA
Cipher подробно
Основные размеры 128, 192 или 256 бит
размеры блоков 128 бит
Состав Замещение-перестановка сети
Туры 10, 12 или 14 (в зависимости от размера ключа)
Лучший общественный криптоанализ
Атаки были опубликованы , что вычислительно быстрее , чем полная грубой силой атаки , хотя ни в 2013 не вычислительно возможным. Для AES-128, ключ может быть восстановлен с помощью вычислительной сложности 2 126,1 использования атаки по полной двудольной графе . Для biclique атак на AES-192 и AES-256, вычислительные сложности 2 189,7 и 2 254,4 соответственно применяются. Связанные ключи атака может сломать AES-192 и AES-256 со сложностями 2 176 и 2 99.5 во время и данных, соответственно.

Advanced Encryption Standard ( AES ), также известный под своим первоначальным названием Rijndael ( Голландский произношение: [rɛindaːl] ), является спецификацией для шифрования электронных данных , установленных в США Национальным институтом стандартов и технологий (NIST) в 2001 году.

AES является подмножеством Rijndael блочного шифра , разработанный двумя бельгийскими криптографами, Винсент Rijmen и Joan Daemen , которые представили предложение NIST во время процесса отбора AES . Rijndael представляет собой семейство шифров с различными ключевыми и размерами блоков.

Для AES, NIST выбраны три члена семейства Rijndael, каждый с размером блока 128 бит, а три различные длины ключа: 128, 192 и 256 бит.

AES был принят правительством США и в настоящее время используется во всем мире. Он заменяет стандарт шифрования данных (DES), который был опубликован в 1977 г. Алгоритм описывается AES является симметричным ключом алгоритма , то есть тот же ключ используется как для шифрования и дешифрования данных.

В Соединенных Штатах, AES был объявлен NIST в США FIPS PUB 197 (FIPS 197) от 26 ноября 2001 г. Это заявление было сделано после процесса стандартизации пять лет , в которых были представлены и оценены пятнадцать конкурирующих конструкций, до шифра Rijndael был выбран как наиболее подходящий (см Advanced Encryption Standard процесс для получения более подробной информации).

AES вступил в силу в качестве федерального стандарта правительства 26 мая 2002 года, после утверждения министром торговли . AES входит в стандарте ISO / IEC 18033-3. AES доступен во многих различных пакетах шифрования, и является первым (и единственным) общедоступным шифром одобрен Агентством национальной безопасности (NSA) для совершенно секретной информации при использовании в АНБЕ утвержден криптографический модуль (см Security ПЯ , ниже).

Окончательные стандарты

Advanced Encryption Standard (AES) определяется в каждом из:

  • FIPS PUB 197: Advanced Encryption Standard (AES)
  • ISO / IEC 18033-3 :: Блочные шифры

Описание шифра

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

AES работает на 4 × 4 столбцам порядка массив байтов, называется состоянием . Большинство расчетов AES выполняются в определенной конечной области .

Например, если есть 16 байт, эти байты представлены в виде этого двумерного массива:

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

  • 10 раундов для 128-битных ключей.
  • 12 раундов для 192-битных ключей.
  • 14 раундов для 256-битных ключей.

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

высокоуровневое описание алгоритма

  1. KeyExpansion -round ключи выводятся из шифровального ключа с использованием ключа расписания Rijndael в . AES требует отдельного 128-битового блока круглого ключа для каждого раунда плюс еще один.
  2. Начальное добавление круглого ключа:
    1. AddRoundKey -Каждая байт состояния в сочетании с блоком круглого ключа с использованием побитового XOR .
  3. 9, 11 или 13 раундов:
    1. SubBytes -a нелинейный шаг подстановки , где каждый байт заменяется на другой в соответствии с таблицей перекодировки .
    2. ShiftRows -a шаг транспозиции , где последние три строки состояния сдвигаются циклически определенное число шагов.
    3. MixColumns -a линейную операция смешивания , которая действует на столбцах состояния, сочетающий в себе четыре байта в каждом столбце.
    4. AddRoundKey
  4. Финальный раунд (что делает 10, 12 или 14 раундов в общей сложности):
    1. SubBytes
    2. ShiftRows
    3. AddRoundKey

В SubBytes шаг

В SubBytes шаге, каждые байты в состоянии заменяются ее вступлением в фиксированной 8-битной таблице поиска, S ; б IJ = S (A IJ ) .

В SubBytes шаге, каждые байты в государственном массиве заменяются SubByte с использованием 8-битной заместительной коробки . Эта операция обеспечивает нелинейность в шифре . S-окно , используемое происходит от мультипликативного обратного над GF (2 8 ) , как известно, обладают хорошими свойствами нелинейности. Для того, чтобы избежать атак на основе простых алгебраических свойств, то S-бокс строится путем объединения обратной функции с обратимым аффинным преобразованием . S-бокс также выбран , чтобы избежать каких - либо неподвижных точек (и так является психоз ), т.е. , а также любые противоположные неподвижные точки, то есть . При выполнении дешифрования, то InvSubBytes шаг (обратный SubBytes ) используется, который требует первого взятия обратного аффинного преобразования , а затем найти мультипликативный обратный.

В ShiftRows шаг

В ShiftRows шаге байтов в каждой строке состояния циклически сдвигают влево. Количество мест каждый байт сдвинутых отличается для каждой строки.

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

MixColumns шаг

В MixColumns шаге, каждый столбец состояния умножается с фиксированным полиномом .

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

Во время этой операции каждый столбец преобразуется с использованием фиксированной матрицы (матрица левой умноженное на колонке дает новое значение столбца в состоянии):

Умножение матриц состоит из умножения и сложения записей. Записи в 8-битные байты рассматриваются как коэффициенты полинома порядка . Сложение просто XOR. Умножение по модулю неприводимым многочленом . Если обрабатываются бит за битом, а затем, после сдвига, условные исключающая ИЛИ с 1В 16 должны быть выполнены , если сдвинутое значение больше , чем FF 16 (переполнение должно быть исправлено путем вычитания генерации полинома). Это особые случаи обычного умножения в .

В более общем смысле, каждый столбец рассматривается как многочлен над и затем умножается по модулю с фиксированным полиномом . Коэффициенты отображаются в их шестнадцатеричном эквиваленте двоичного представления битовых многочленов от . MixColumns шаг также можно рассматривать как умножение на показанной конкретной матрицы РМР в конечной области . Этот процесс описан далее в статье RIJNDAEL MixColumns .

AddRoundKey шаг

В AddRoundKey шаге, каждые байты состояния объединяются с байтом круглых подключе с использованием XOR операций (⊕).

В AddRoundKey стадии, подраздел объединяется с состоянием. Для каждого раунда подраздел выводится из основного ключа с использованием ключа график RIJNDAEL в ; каждый подраздел имеет тот же размер , как состояние. Подключ добавляется путем объединения каждого байта состояния с соответствующим байтом подключ с использованием побитового XOR .

Оптимизация шифра

В системах с 32-битными или более длинными словами, можно ускорить выполнение этого шифра путем комбинирования SubBytes и ShiftRows шагов с MixColumns шагом путем преобразования их в последовательность из таблицы поиска. Для этого требуется четыре 256-входа 32-разрядные таблицы (вместе занимающие 4096 байт). Круглая затем может быть выполнены с операциями подстановки 16 таблиц и 12 32-битные исключающие ИЛИ операции, которым следует четыре 32-битных исключающих или операций в AddRoundKey стадии. В качестве альтернативы, операция таблицы поиска может быть выполнена с помощью одного 256-входа 32-битной таблицы (занимающих 1024 байт) , а затем круговой операция вращения.

Использование байт-ориентированный подход, то можно объединить SubBytes , ShiftRows и MixColumns шаги в единый операции округления.

Безопасность

До мая 2009 года, только успешные опубликованные нападения на полную AES были нападениями со стороны каналов на некоторых конкретных реализациях. Агентство национальной безопасности (NSA) рассмотрело все AES финалистов, включая Rijndael, и заявил , что все они были в достаточной безопасности для правительства США , не классифицированные данных. В июне 2003 года правительство США объявило о том , что AES может быть использован для защиты секретной информации :

Дизайн и прочность всех ключевых длинами алгоритма AES (то есть, 128, 192 и 256) являются достаточными для защиты секретной информации до уровня SECRET. TOP SECRET информация потребуется использовать либо длиной ключа 192 или 256. Реализация AES в продуктах, предназначенных для защиты систем национальной безопасности и / или информации, должны быть проверены и сертифицированы АНБ до их приобретения и использования.

AES имеет 10 раундов для 128-битных ключей, 12 раундов для 192-битных ключей и 14 раундов для 256-битных ключей.

К 2006 году, наиболее известные атаки были на 7 раундов для 128-битных ключей, 8 раундов для 192-битных ключей и 9 раундов для 256-битных ключей.

Известные атаки

Для криптографов, криптографический «перерыв» это что - то быстрее , чем грубая силы атаки - то есть, выполняя один пробное дешифрование для каждого возможного ключа в последовательности (см криптоанализа ). Таким образом, разрыв может включать в себя результаты, которые неосуществимы с учетом современных технологий. Несмотря на то , непрактично, теоретические перерывы иногда может обеспечить понимание факторов уязвимости. Самая большая успешная общеизвестный перебор атака на алгоритм шифрования широко реализован блок-шифр была против 64-битного RC5 ключа по distributed.net в 2006 году.

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

AES имеет довольно простую алгебраическую структуру. В 2002 году теоретическая атака, назвал « XSL нападение », заявил Николя Куртуа и Йозеф Pieprzyk , якобы , чтобы показать слабость в алгоритме AES, частично из - за низкой сложности его нелинейных компонентов. С тех пор, другие документы показали , что атака, как первоначально представлено, является неосуществимой; см XSL нападение на блочных шифров .

В процессе выбора AES, разработчики конкурирующих алгоритмов писали алгоритма Rijndael в «... мы обеспокоены [его] использовать ... в системах безопасности критичных.» В октябре 2000 года , однако, в конце процесса отбора AES, Брюс Шнайер , разработчик из конкурирующих алгоритмов Twofish , писал , что в то время как он думал , что успешные научные нападения на Rijndael будут развиваться , когда - нибудь, он не «считает , что кто -то будет когда - либо обнаружить атаку , которая позволит кому - то читать Rijndael трафик».

В 2009 году новая атака связанных ключах было обнаружено , что использует простоту расписания ключей AES и имеет сложность 2 119 . В декабре 2009 года он был улучшен до 2 99.5 . Это является продолжением до нападения обнаруженной ранее в 2009 году Алекс Бирюков , Дмитрий Ховратович и Ивица Николич, со сложностью 2 96 для одного из каждых 2 35 ключей. Тем не менее, связанные ключевые атаки не вызывают беспокойства в любом правильно спроектированной криптографическом протоколе, как правильно спроектированный протокол (т.е. на реализацию программное обеспечение) будет заботиться , чтобы не допустить связанные ключи, по существу, сдерживающего средство злоумышленника подбора ключей для связанности.

Другая атака на своем блоге Брюс Шнайер 30 июля 2009 года и выпущен как препринт 3 августа 2009 г. Эта новая атака, Алекс Бирюков, Орр Дункельмана, Натан Келлер, Дмитрий Ховратович и Ади Шамира , против AES-256 который использует только два связанных ключей и 2 39 раз , чтобы восстановить полный 256-битный ключ в 9-раундовом версии или 2 45 раз в течение 10-раундовом версии с более сильным типом соответствующего подключа нападения, или 2 70 время для 11-раундовом версия. 256-битное AES использует 14 раундов, так что эти атаки не являются эффективными против полного AES.

Практичность этих атак с более сильными связанными ключами была подвергнута критике, например, в статье о «избранности ключевых отношений-в-середине» атаки на AES-128 авторством Винсент Rijmen в 2010 году.

В ноябре 2009 года , первая известный ключ Отличительная атаки против уменьшенной 8-раундовой версии AES-128 была выпущена как препринт. Этот известный ключ Отличительная атака является улучшение отскока, или запуск из-середине атаки, против AES-подобных перестановок, которые рассматривают два последовательных раундов перестановки в применении так называемой супер-Sbox. Он работает на 8-раундовом версии AES-128, с временной сложностью 2 48 , и сложности памяти 2 32 . 128-битное AES использует 10 раундов, так что эта атака не эффективна против полного AES-128.

Первые атаки ключа восстановления на полной AES должны были Андрей Богданов, Дмитрий Ховратович и христианского Рехбергер, и были опубликованы в 2011 годе атакой является атакой по полной двудольной графе и быстрее , чем грубая сила фактора примерно четыре. Это требует 2 126,2 операции для восстановления ключа AES-128. Для AES-192 и AES-256, 2 190,2 и 2 254,6 необходимы операции, соответственно. Этот результат был дополнительно улучшен до 2 126,0 для AES-128, 2 189,9 для AES-192 и 2 254,3 для AES-256, который в настоящее время являются лучшими результатами в ключевом восстановлении атаки против AES.

Это очень небольшой прирост, как 126-битный ключ (вместо 128-бита) будет по- прежнему принимать миллиарды лет до грубой силы на текущем и в обозримом будущем аппаратного обеспечения. Кроме того , авторы расчета лучшую атаку , используя свою технику на AES с 128 битным ключом требует хранения 2 88 бит данных. Это работает около 38000000000000 терабайт данных, что больше , чем все данные , хранящиеся на всех компьютерах , на планете в 2016 году Как таковой, это серьезно непрактично атака , которая не имеет никакого практического значения на безопасность АЭС. Сложность пространства позже была улучшена до 2 56 бит, который составляет 9007 терабайта.

Согласно документам Snowden , АНБ проводит исследования , является ли криптографическая атака на основе тау статистики может помочь сломать AES.

В настоящее время не существует никакого известного практический атака, которая позволила бы кто-то без знания ключа, чтобы считывать данные, зашифрованные AES при правильной реализации.

Атаки со стороны каналов

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

В апреле 2005 года , DJ Бернштейн объявил кэш-временную атаку , которые он использовал , чтобы сломать собственный сервер , который использовал OpenSSL AES шифрование «s. Наступление требуется более 200 миллионов выбранных открытых текстов. Пользовательский сервер был разработан , чтобы дать, как много информации о времени , насколько это возможно (отчеты сервера обратно число машинных циклов , принимаемых операции шифрования); однако, как Бернштейн указывал, «снижение точности меток времени сервера, или устранение их из ответов сервера, не останавливает атаку: клиент просто использует тайминги туда-обратно на основе его локальные часов, и компенсирует повышенный шум путем усреднения по большему числу выборок «.

В октябре 2005 года , Даг Арне Osvik, Ади Шамир и Эран Tromer представили документ , демонстрирующий несколько кэша-синхронизацию атаки против реализации в AES , найденной в OpenSSL и в Linux dm-cryptфункции шифрования разделов. Одна атаки была в состоянии получить весь ключ AES только после 800 операций запуска шифров, в общей сложности 65 миллисекунд. Эта атака требует злоумышленника , чтобы иметь возможность запускать программы на одной и той же системы или платформы, производящем AES.

В декабре 2009 года было опубликовано нападение на некоторых аппаратных реализаций , которые использовали дифференциальный анализ неисправностей и позволяет восстановление ключа с сложностью- 32 .

В ноябре 2010 года Эндре Бангертер, Дэвид Gullasch и Стефан Krenn опубликовали статью, в которой описала практический подход к «близком к реальному времени» восстановлению секретных ключей от AES-128 без необходимости либо шифрованного текста или текста. Этот подход также работает на AES-128 реализаций, которые используют таблицы сжатия, такие как OpenSSL. Как и некоторые ранее атаки это один требует возможности запускать непривилегированные коды на системе, выполняющее шифрование AES, которое может быть достигнуто с помощью вредоносной программы гораздо легче, чем реквизиции корневой учетной записи.

В марте 2016 года, Ашок Кумар С., Рави Пракаш Гири и Бернард Менезес представил очень эффективную атаку бокового канала на реализации AES, что может восстановить полный 128-битный AES ключ всего за 6-7 блоков открытого текста / шифротекста, который является существенным улучшением по сравнению с предыдущими работами, которые требуют от 100 до миллиона шифров. Предлагаемая атака требует стандартной привилегии пользователя, как и предыдущие нападения и алгоритмы копировально-поисковых выполняющихся минуту.

Многие современные процессоры имеют встроенные аппаратные инструкции для AES , которые будут защищать от временных связанных с атаками бокового канала.

проверка NIST / CSEC

Модуль проверки программы Cryptographic (CMVP) работает совместно правительства Соединенных Штатов Национальный институт стандартов и технологий Отдел безопасности (NIST) Компьютер и Центр безопасности коммуникаций (CSE) правительства Канады. Использование криптографических модулей проверенных в NIST FIPS 140-2 требуется правительство Соединенных Штатов для шифрования всех данных , который имеет классификацию Sensitive но классифицировано (SBU) или выше. Из NSTISSP № 11, Национальная политика , регулирующие приобретение обеспечения безопасности информации: «Шифрование продуктов для защиты секретной информации будет сертифицировано АНБ, и средства шифрования , предназначенные для защиты конфиденциальной информации , будут сертифицированы в соответствии с NIST FIPS 140-2.»

Правительство Канады также рекомендует использовать FIPS 140 проверенных криптографических модулей в несекретных приложениях его отделов.

Хотя NIST публикации 197 ( «FIPS 197») является единственным документом , который охватывает алгоритм AES, как правило , производители приближаются к CMVP под FIPS 140 и просить , чтобы иметь несколько алгоритмов (например, тройной DES или SHA1 ) , подтвержденным в то же самое время. Поэтому редко можно найти криптографические модули, которые однозначно FIPS 197 подтверждено и сама NIST обычно не принимают время , чтобы перечислить FIPS 197 проверенных модулей отдельно на своем общедоступном веб - сайте. Вместо FIPS 197 проверки , как правило , только в списке «Одобрено FIPS: AES» нотации (с определенным FIPS 197 номер сертификата) в текущем списке FIPS 140 проверенных криптографических модулей.

Алгоритм проверка программа Cryptographic (CAVP) позволяет независимой проверке правильности выполнения алгоритма AES по разумной цене. Успешные результаты проверки в настоящее время перечислены на странице NIST Validations. Это тестирование является предварительным условием для проверки модуля FIPS 140-2, описанной ниже. Тем не менее, успешная проверка CAVP никоим образом не означает, что криптографический модуль реализации алгоритма является безопасным. Криптографический модуль отсутствует FIPS 140-2 или специальное одобрение АНБ не считается безопасным правительством США и не может быть использован для защиты правительственных данных.

FIPS 140-2 является сложной задачей для достижения технически и финансово. Существует стандартизированную батарея тестов, а также элемент обзора исходного кода, который должен быть принят в течение нескольких недель. Стоимость для выполнения этих тестов через уполномоченную лабораторию может быть значительной (например, более $ 30 000 долларов США) и не включает в себя время, необходимое для написания, тестирование, документа и подготовить модуль для проверки. После проверки, модули должны быть повторно представлены и повторную оценку, если они будут изменены в любом случае. Это может варьироваться от простых обновлений делопроизводства, если функциональность безопасности не изменилась к более значительному набору повторного тестирования, если функциональные возможности безопасности повлияли изменения.

Тестовые векторы

Тестовые векторы представляют собой набор известных шифров для данного входа и ключа. NIST распределяет ссылку тестовых векторов AES как AES Известна Ответ Test (КАТ) векторы.

Спектакль

Высокая скорость и низкие требования к RAM были критерии процесса отбора AES. В качестве выбранного алгоритма, AES хорошо зарекомендовал себя на самых разнообразных аппаратных средств, от 8-битных смарт - карт для высокопроизводительных компьютеров.

Об одном Pentium Pro , шифрование AES требует 18 тактов на байт, что эквивалентно пропускной способности около 11 Мбайт / с для процессора 200 МГц. На 1,7 ГГц Pentium M пропускной способности составляет около 60 МБ / с.

На Intel Core i3 / i5 / i7 и AMD Ryzen процессоров с поддержкой AES-NI набора команд расширения, пропускная способность может быть несколько Гб / с (даже более 10 Гб / с).

Реализации

Смотрите также

Заметки

  1. ^ Основные размеры 128, 160, 192, 224 и 256 бит поддерживаются алгоритмом Rijndael, но только основные размеры 128, 192, и 256-битовые указаны в стандарте AES.
  2. ^ Блок размеры 128, 160, 192, 224 и 256 бит поддерживаютсяпомощью алгоритма Rijndael для каждого размера ключа, но только 128-битный размер блока задан в стандарте AES.
  3. ^ Крупноблочных вариантов Rijndael использовать массив с дополнительными столбцами, но всегда четыре строки.
  4. ^ Rijndael варианты с большим размером блокаимеют немного разные смещения. Для блоков размером 128 бит и 192 бит, сдвигая шаблон является то же самое. Строкасмещается левой круговой набайт. Для 256-битового блока в первый ряд не меняетсяи смещение для второго, третьего и четвертого ряда составляет 1 байт, 3 байта и 4 байтасоответственно, это изменение относится только к шифра Rijndael при использовании с 256-битным блоком в , поскольку AES не использует 256-битные блоки.
  5. ^ АЭ Известный Ответ Test (КАТ) Векторы доступны в формате Zip внутри сайта NIST здесь Архивировано 2009-10-23 в Wayback Machine .

Рекомендации

внешняя ссылка