Симметричный алгоритм блочного шифрования 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(2⁸). В этом поле определены операции сложения и умножения двух элементов, результатом которых, в свою очередь, также является элемент этого поля. Рассмотрим каждую из операций:

• Сложение выполняется с помощью операции xor. Операция выполняется над двоичными числами поразрядно, то есть для двух байт P = { p_7, p₆, p₅, p₄, p₃, p₂, p₁, p₀ } и Q = { q₇, q₆, q₅, q₄, q₃, q₂, q₁, q₀ } результатом будет R = { r₇, r₆, r₅ , r₄, r₃, r₂, r₁, r₀ }, где r_i = p_i xor r_i .

• Умножение. Для этой операции используется представление байта в виде полинома: p(x) = p₇x⁷ + p₆x⁶ + p₅x⁵ + p₄x⁴ + p₃x³ + p₂x² + p₁x + p₀ , умножение в поле F(2⁸) в таком представлении производится по модулю неприводимого в этом поле многочлена m(x) = x⁸ + x⁴ + x³ + x + 1. Таким образом, для того, чтобы получить результат умножения двух чисел в поле F(2⁸), мы должны представить их в виде полиномов p(x) и q(x), затем взять остаток от деления на многочлен m(x) произведения p(x) и q(x), то есть r(x) = p(x)q(x) mod (m(x)), и получить коэффициенты полинома r(x), которые являются 8-битовым числом числом в поле F(2⁸).

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

Давайте теперь перейдем от математики к описанию самого алгоритма шифрования 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 четырехбайтовых слов (w_i): 4 слова на основной ключ и по 4 слова на 10 раундовых ключей. Таким образом, полная длина расширенного ключа составляет 1408 бит.

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

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

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

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

Операция RotByte производит циклическую перестановку байта исходного слова: { x₀, x₁, x₂, x₃ } → { x₃ , x₀ , x₁ , x₂ }.

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

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

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

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 обладает наиболее безопасной реализацией. Однако следует заметить, что чем длиннее ключ и больше раундов, тем выше требование к производительности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для ответа на него давайте рассмотрим расширенный ключ как ряд 32-х битных слов: w₀, w₁, w₂, w₃, …, w₄₀, w₄₁, w₄₂, w₄₃, где w₀, w₁, w₂, w₃ - 128-битный ключ AES, а w₄₀, w₄₁, w₄₂, w₄₃ - последний раундовый ключ. Процесс расширения ключа определяется как w_i = w_i-4 xor F_i(w_i-1), где F_i - это рассмотренная выше функция, определяемая процедурой KeyExpansion. Начиная с w₀, w₁, w₂, w₃ этот процесс позволяет вычислить остальную часть расширенного ключа.

Теперь давайте предположим, что злоумышленнику известен последний раундовый ключ шифрования AES-128. Он может переписать процесс расширения ключа следующим образом: w_j = w_j+4 xor F_j+4(w_j+3). Это получается простой заменой j = i - 4 и переупорядочиванием. Таким образом, злоумышленник, имея в распоряжении w₄₀, w₄₁, w₄₂, w₄₃ ,cможет восстановить все слова вплоть до w₀ .

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

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

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

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

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

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

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

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

Заключение

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