Симметричный алгоритм блочного шифрования Advanced Encryption Standart

О чем эта статья

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


Вступление

В 80-х годах основным симметричным криптоалгоритмом для внутреннего применения в США являлся DES (Data Encryption Standard). Однако уже в 90-х годах стали проявляться его основные недостатки. Главным из которых являлась длина ключа, составляющая 56 бит. Такой размер становился недостаточно большим ввиду постоянного роста производительности ЭВМ, так как ключ мог быть вскрыт методом обычного перебора всех возможных вариантов шифрования.

По этим причинами в 1997 году NIST (National Institute of Standards and Technology,) объявил конкурс на новый стандарт симметричного криптоалгоритма. Были установлены следующие обязательные требования к кандидатам:

  • 128-битный размер блока шифруемых данных;

  • Не менее 3 размеров ключей (128, 192, 256 бит), которые должны поддерживаться алгоритмом;

  • Использование операций, легко реализуемых и аппаратно, и программно;

  • Простота структуры шифра, чтобы заинтересованные стороны могли самостоятельно проводить криптоанализ;

Победителем этого конкурса, названного AES – Advanced Encryption Standard, стал алгоритм Rijndael (далее алгоритм AES). Он продемонстрировал устойчивость к атакам, относительно низкий уровень энергопотребления и относительно небольшое время работы. Кроме того, алгоритму присущ внутренний параллелизм, за счет этого эффективно используются процессорные ресурсы, и дополнительно уменьшается время работы алгоритма.

Основные понятия

Давайте рассмотрим основные понятия, необходимые для лучшего понимания работы алгоритма.

Прежде всего отметим, что алгоритм AES оперирует байтами, которые интерпретируются как элементы конечного поля F(28). В этом поле определены операции сложения и умножения двух элементов, результатом которых, в свою очередь, также является элемент этого поля. Рассмотрим каждую из операций:

  • Сложение выполняется с помощью операции xor. Операция выполняется над двоичными числами поразрядно, то есть для двух байт P = { p7, p6, p5, p4, p3, p2, p1, p0 } и Q = { q7, q6, q5, q4, q3, q2, q1, q0 } результатом будет R = { r7, r6, r5 , r4, r3, r2, r1, r0 }, где ri = pi xor ri .

  • Умножение. Для этой операции используется представление байта в виде полинома: p(x) = p7x7 + p6x6 + p5x5 + p4x4 + p3x3 + p2x2 + p1x + p0 , умножение в поле F(28) в таком представлении производится по модулю неприводимого в этом поле многочлена m(x) = x8 + x4 + x3 + x + 1. Таким образом, для того, чтобы получить результат умножения двух чисел в поле F(28), мы должны представить их в виде полиномов p(x) и q(x), затем взять остаток от деления на многочлен m(x) произведения p(x) и q(x), то есть r(x) = p(x)q(x) mod (m(x)), и получить коэффициенты полинома r(x), которые являются 8-битовым числом числом в поле F(28).

Описания алгоритма шифрования

Давайте теперь перейдем от математики к описанию самого алгоритма шифрования AES c размером ключа 128 бит.

Предварительно входные данные разбиваются на блоки по 16 байт, если полный размер не кратен 16 байтам, то данные дополняется до размера, кратного 16 байтам. Блоки представляются в виде матрицы 4x4 — state. Далее происходит процедура расширения ключа и к каждому блоку state применяются операции 2-4. Итак, алгоритм состоит из следующих шагов:

  1. Расширение ключа - KeyExpansion;

  2. Начальный раунд - сложение state с основным ключом;

  3. 9 раундов шифрования, каждый из которых состоит из преобразований:

    · SubBytes

    · ShiftRows

    · MixColumns

    · AddRoundKey

  4. Финальный раунд, состоящий из преобразований:

    · SubBytes

    · ShiftRows

    · AddRoundKey

Рассмотрим подробнее каждое из представленных выше преобразований:

  • SubBytes - замена байтов state по таблице S-box. Каждый байт представляется в виде двух шестнадцатеричных чисел b = (x, y), где x определяется 4 старшими разрядами b, а y — 4 младшими. В таблице S-box размера 16x16 находятся значения для замены исходного байта: значение b' на пересечении строки x и столбца y S-box используется в качестве замены исходному байту b.

  • ShiftRows — циклический сдвиг строк state. Нулевая строка остается на месте, первая смещается влево на 1 байт, вторая на 2 байта и третья на 3 соответственно.

  • MixColumns — умножения каждого столбца state на фиксированную матрицу. Таким образом осуществляется линейное преобразование над столбцами state. Причем умножение и сложение производится по правилам, описанным выше.

  • AddRoundKey — раундовый ключ поэлементно добавляется к state с помощью поразрядного XOR.

  • KeyExpansion — процедура расширения основного ключа для создания раундовых ключей, которые затем используются в раундах шифрования. Расширенный ключ состоит из 44 четырехбайтовых слов (wi): 4 слова на основной ключ и по 4 слова на 10 раундовых ключей. Таким образом, полная длина расширенного ключа составляет 1408 бит.

    Операция расширения ключа использует массив Rcon и состоит из следующих действий:

    • Четыре слова основного ключа переносятся в первые четыре слова расширенного ключа.

    • Если число i без остатка делится на 4, то wi =SubBytes(RotByte(wi-1 )) xor Rconi/4 .

    • Иначе: wi = wi-4 xor wi-1 .

Операция RotByte производит циклическую перестановку байта исходного слова: { x0, x1, x2, x3 } → { x3 , x0 , x1 , x2 }.

Ниже показан пример, демонстрирующий генерацию 2 первых слов первого раундового ключа.

https://www.youtube.com/watch?v=CxU4ROAYGzs
https://www.youtube.com/watch?v=CxU4ROAYGzs

Описание алгоритма дешифрования

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

  1. Расширение ключа - KeyExpansion;

  2. 9 раундов дешифрования, каждый из которых состоит из преобразований:

    · AddRoundKey — суммирование state с раундовым ключом;

    · InverseMixColumns — обратная перестановка столбцов state;

    · InverseShiftRows — обратный циклический сдвиг столбцов state;

    · SubBytes — замена байтов state по обратной таблице замен InverseS- box;

  3. Финальный раунд:

    · AddRoundKey

    · InverseShiftRows

    · InverseSubBytes

Другие версии AES

Стандарт допускает только одно значение длины блока state— 128 бит для 3 версий алгоритма AES. В то время как размер ключа в разных версиях отличается: AES-192 использует 192 — битный размер основного ключа и производит 12 раундов шифрования, а AES-256 — 256 битный размер основного ключа и 14 раундов шифрования.

Большее количество раундов делает шифрование сложнее. Таким образом, AES-256 обладает наиболее безопасной реализацией. Однако следует заметить, что чем длиннее ключ и больше раундов, тем выше требование к производительности.

В таблице, показанной ниже, количество Nk - количество слов в ключе, Nb - количество слов в блоке и Nr - количество раундов соответственно.

Примеры атак на AES

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

  1. Атака по времени.

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

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

    Возможные методы противодействия такому виду атаки:

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

    · Добавлять ко времени выполнения операции задержки случайной длительности, это значительно затруднит проведение атаки таким способом.

  2. Атака по энергопотреблению.

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

    Возможными методами противодействия такому виду атаки являются:

    · Балансировка энергопотребления — при проведении операции задействовать все аппаратные части устройства.

    · Обеспечение независимости флуктуаций энергопотребления и происходящих в системе процессов.

Можно ли восстановить расширенный ключ, зная какой-либо из раундовых?

Достаточно интересный вопрос, возникший у меня при написании этой статьи.

Для ответа на него давайте рассмотрим расширенный ключ как ряд 32-х битных слов: w0, w1, w2, w3, …, w40, w41, w42, w43, где w0, w1, w2, w3 - 128-битный ключ AES, а w40, w41, w42, w43 - последний раундовый ключ. Процесс расширения ключа определяется как wi = wi-4 xor Fi(wi-1), где Fi - это рассмотренная выше функция, определяемая процедурой KeyExpansion. Начиная с w0, w1, w2, w3 этот процесс позволяет вычислить остальную часть расширенного ключа.

Теперь давайте предположим, что злоумышленнику известен последний раундовый ключ шифрования AES-128. Он может переписать процесс расширения ключа следующим образом: wj = wj+4 xor Fj+4(wj+3). Это получается простой заменой j = i - 4 и переупорядочиванием. Таким образом, злоумышленник, имея в распоряжении w40, w41, w42, w43 ,cможет восстановить все слова вплоть до w0 .

Эта проблема становится не столь критичной в случае с AES-192 и AES-256. Действительно, если атакующему удается получить один раундовый ключ из 256-битного ключа AES, это уменьшает количество возможных вариантов AES ключей с 2256 до 2128, в таком случае восстановить полный ключ все еще невозможно с вычислительной точки зрения.

Преимущества AES

К основным преимуществам данного алгоритма относят:

  • Рассеивание — изменение любого знака ключа или открытого текста влияет на большое количество знаков шифротекста.

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

  • Не подвержен многим видам криптоаналитических атак, таких как: дифференциальный криптоанализ, линейный криптоанализ, square — атака.

  • Байт-ориентированная структура, что дает хорошие перспективы для реализации алгоритма в будущих процессорах.

  • Высокое быстродействие на различных платформах.

Заключение

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

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 13

    +1
    Очередной реферат на Хабре? Поиском пользоваться не обязательно?

    Вот статья про AES
    и вот
    и вот
      +2

      Не нравится – не читайте, в чём проблема?

        0
        INan_banan:
        • Зарегистрирован «15 декабря 2020 в 12:51 по приглашению НЛО»
        • Опубликовал «так себе статью» с тегами «Информационная безопасность, Криптография, Алгоритмы».

        Что одногруппник автора этой «так себе статьи»?
          0

          Если для Вас все статьи, опубликованные достаточно осведомлёнными и образованными студентами последнего курса бакалавра лучшего технического вуза страны, – «так себе», то, очевидно, проблему нужно искать не там, где её ищете Вы. Не забывайте, что Хабр – общий ресурс для публикаций, а не Ваш частный.

            +1
            Значит я угадал… и "+" вы ставите сами себе в пределах группы.

            Если для Вас все статьи, опубликованные достаточно осведомлёнными и образованными студентами последнего курса бакалавра лучшего технического вуза страны, – «так себе», то, очевидно, проблему нужно искать не там, где её ищете Вы.

            Сколько пафоса то.

            Да. Реферат представляющий себе банальную компиляцию общеизвестной в узких кругах информации — это просто реферат. Пусть и добротно сделанный на студенческом уровне. Но уже в 1000й раз!
            Накопали бы, например, инфу (пусть и на уровне слухов) про то как звали «AES» в девичестве… про то какие у него конкуренты были… и пр. Сравнение с «Кузнечик» например.
            А эти подробности оооочень интересны и нетривиальны.
            Вот тогда этот пафос про «студентов и вуза» был бы оправдан.

            Так что для меня такой реферат — это «так себе статья» с тегом «Информационная безопасность, Криптография». Пусть и для реферата нормально написано.

            Но я не преподаватель, что бы «по работе» в 100 раз читать реферат «как работает AES» или реферат с неправильным определением «скремблера» дернутым из Вики (где то же «так себе» автор его задал)

            Не забывайте, что Хабр – общий ресурс для публикаций, а не Ваш частный.

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

            И так хабр помойкой становится…

              0

              Именно в этом и проблема, что данная информация известна только в узких кругах. Может Вы и разбираетесь в этой теме, а кто-то нет. Никто не говорил, что статьи на Хабре нацелены на профессионалов.

                0

                Если Вы не забыли, то не все могут лайкать статьи на Хабре, так что «накрутить» бы не вышло.

                  +1

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


                  Так что достаточно просто избежать слива кармы (не выкладывать откровенный оскорбительный бред) — и вуаля каждый кто выложил свою статью может лайкнуть друга.


                  Очень напоминает историю с индексом Хирша и взаимным цитированием.


                  Возникает всего один вопрос — зачем? Я еще понимаю индекс Хирша крутить — от него напрямую зависят фин. потоки лабы. Но в чем суть баловства с курсовыми и их лайками на хабре?

                    0
                    Зачет автоматом? )
              0

              «Если для Вас все статьи, опубликованные достаточно осведомлёнными и образованными студентами последнего курса бакалавра лучшего технического вуза страны,»


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

        +2
        Все авторы «так себе статей» с тегами «Информационная безопасность, Криптография, Алгоритмы» зарегистрированы приблизительно в одно время. 20 декабря 2020 года. Все статьи имеют похожий стиль изложения (как реферат) и представляют простую компиляцию информации. Причем, зачастую даже не особо утруждаясь изложить своими словами прочитанное.

        Судя по количеству "+" (около 20) которые появляются практически одновременно в момент публикации и в похожих количествах — это группы одного потока.

        Студенты а так же их преподаватели. Ну имейте же совесть!
        Найдите другую площадку для публикации рефератов и манипуляций с лайками!
          –2

          А что мешает Вам найти другую площадку для чтения статей? Почему же их тогда публикуют, если они «так себе»? Критика должна быть обоснованной и объективной. Я Вам больше скажу, многие статьи имеют такой стиль, если же Вам нравится читать скучную научную литературу, и Вы не знаете о таком стиле, как научпоп, то ресурс стоило бы, действительно, сменить или же задавать вопросы не авторам, а модераторам.

            0
            Научпоп — это когда интересно читать непосвященным людям. Тогда и плюсы будут ставить не только одногруппники. А у вас у всех — сухая перепечатка известных фактов, понадёрганные картинки и избитые темы, которые все уже видели сто раз.
            Что сможет извлечь из вашей статьи человек, который (до сих пор) не в курсе про AES? Ни че го.
            В гугле миллиарды статей и видео по запросу «AES for dummies» с анимацией, кто-то даже вроде на бумажке делал.

            Если так обстоят дела у «бакалавров последнего курса лучшего технического вуза», то это всё очень грустно.

            Я предлагаю вам отличную тему для криптостатьи, совершенно бесплатно — новый S-Box для AES. Принт буквально сегодня вышел.

            И новое и интересное (если сможете человеческим языком объяснить).

        Only users with full accounts can post comments. Log in, please.